Zero-one 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 given subset G of infinite sequence of natural numbers. The set G, called the goal, is assumed to be a Borel tail set. The Controller’s choices are restricted: having taken a sequence h = (a0, . . . , at) of actions prior to any stage t+1, she must choose an action at at stage t+1 from a non-empty,finite subset A(h) of natural numbers. The set A(h) is chosen from a distribution p, independently over all stages and histories. We consider several information structures defined by how far ahead 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.
Area: CS31 - Random Games (Xavier Venel)
Keywords: Random tree, Game Theory, Kolmogorov's 0-1 Law
Please Login in order to download this file