The Gittins index is optimal for dynamic allocation with conditionally independent filtrations
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911412457046016 |
|---|---|
| author | Wang, Christopher |
| author_facet | Wang, Christopher |
| contents | The dynamic allocation problem, also known as the `multi-armed bandit' problem, simulates a situation in which an agent is faced with a tradeoff between actions that yield an immediate reward and actions whose benefits can only be perceived in the future. In this paper, we show that the non-Markovian, discrete-time problem can be solved by following a Gittins index strategy, without the assumption that the rewards processes are independent. Instead, we require the underlying multi-parameter filtration to satisfy a conditional independence property. We provide three representations of the maximal attainable value under an optimal strategy. Furthermore, we discuss the relationship between index-type strategies and the `synchronization' paradigm from operations research. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_09350 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The Gittins index is optimal for dynamic allocation with conditionally independent filtrations Wang, Christopher Probability Optimization and Control 93E20, 60G40 (Primary) 60G48, 90B35, 90C24 (Secondary) The dynamic allocation problem, also known as the `multi-armed bandit' problem, simulates a situation in which an agent is faced with a tradeoff between actions that yield an immediate reward and actions whose benefits can only be perceived in the future. In this paper, we show that the non-Markovian, discrete-time problem can be solved by following a Gittins index strategy, without the assumption that the rewards processes are independent. Instead, we require the underlying multi-parameter filtration to satisfy a conditional independence property. We provide three representations of the maximal attainable value under an optimal strategy. Furthermore, we discuss the relationship between index-type strategies and the `synchronization' paradigm from operations research. |
| title | The Gittins index is optimal for dynamic allocation with conditionally independent filtrations |
| topic | Probability Optimization and Control 93E20, 60G40 (Primary) 60G48, 90B35, 90C24 (Secondary) |
| url | https://arxiv.org/abs/2312.09350 |