Zero-one Laws for a Control Problem with Random Action Sets
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916199647936512 |
|---|---|
| author | Flesch, János Predtetchinski, Arkadi Sudderth, William D Venel, Xavier |
| author_facet | Flesch, János Predtetchinski, Arkadi Sudderth, William D Venel, Xavier |
| contents | 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 chooses actions $a_{0}, a_{1}, \ldots$, one at a time. Her goal is to maximize the probability that the infinite sequence $(a_{0}, a_{1}, \ldots)$ is an element of a given subset $G$ of $\mathbb{N}^{\mathbb{N}}$. 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_{t} = (a_{0}, \ldots, a_{t-1})$ of actions prior to stage $t \in \mathbb{N}$, she must choose an action $a_{t}$ at stage $t$ from a non-empty, finite subset $A(h_{t})$ of $\mathbb{N}$. The set $A(h_{t})$ is chosen from a distribution $p_{t}$, independently over all $t \in \mathbb{N}$ and all $h_{t} \in \mathbb{N}^{t}$. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_07012 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Zero-one Laws for a Control Problem with Random Action Sets Flesch, János Predtetchinski, Arkadi Sudderth, William D Venel, Xavier Optimization and Control Probability 60F20, 90C40, 60J85 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 chooses actions $a_{0}, a_{1}, \ldots$, one at a time. Her goal is to maximize the probability that the infinite sequence $(a_{0}, a_{1}, \ldots)$ is an element of a given subset $G$ of $\mathbb{N}^{\mathbb{N}}$. 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_{t} = (a_{0}, \ldots, a_{t-1})$ of actions prior to stage $t \in \mathbb{N}$, she must choose an action $a_{t}$ at stage $t$ from a non-empty, finite subset $A(h_{t})$ of $\mathbb{N}$. The set $A(h_{t})$ is chosen from a distribution $p_{t}$, independently over all $t \in \mathbb{N}$ and all $h_{t} \in \mathbb{N}^{t}$. 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. |
| title | Zero-one Laws for a Control Problem with Random Action Sets |
| topic | Optimization and Control Probability 60F20, 90C40, 60J85 |
| url | https://arxiv.org/abs/2404.07012 |