Friday, March 17th

11.30 - 12.30 

Luiss | Viale Romania, 32 | Room 310

Arkadi Predtetchinski (Maastricht University)
0-1 Laws for a Control Problem with Random Action Sets

In many control problems there is only limited information about the actions that will be available at future stages. We introduce a framework where the controller sequentially chooses actions a0, a1, ... one at a time. Her goal is to maximize the probability that the infinite sequence a0, a1,... is an element of a subset G of the set of infinite sequences of natural numbers. The set G is assumed to be a Borel tail set. The controller's choices are restricted: having taken a sequence ht of actions prior to stage t, she must choose a decision at stage t from a restricted set A(ht) of natural number. The set A(ht) is chosen randomly from a distribution pt, independently over all time periods and past histories. We consider several information structures defined by how far into the future the controller knows what actions will be available. In the special case where all the action sets are singletons (and thus the controller is a dummy), Kolmogorov’s 0-1 law says that the probability for the goal to be reached is 0 or 1. We construct a number of counterexamples to show that in general the value of the control problem can be strictly between 0 and 1, and derive several sufficient conditions for the 0-1 "law" to hold.

Joint work with Janos Flesch, William Sudderth, Xavier Venel