An Optimal-Control Approach to Infinite-Horizon Restless Bandits: Achieving Asymptotic Optimality with Minimal Assumptions
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909139870941184 |
|---|---|
| author | YAN, Chen |
| author_facet | YAN, Chen |
| contents | We adopt an optimal-control framework for addressing the undiscounted infinite-horizon discrete-time restless $N$-armed bandit problem. Unlike most studies that rely on constructing policies based on the relaxed single-armed Markov Decision Process (MDP), we propose relaxing the entire bandit MDP as an optimal-control problem through the certainty equivalence control principle. Our main contribution is demonstrating that the reachability of an optimal stationary state within the optimal-control problem is a sufficient condition for the existence of an asymptotically optimal policy. Such a policy can be devised using an "align and steer" strategy. This reachability assumption is less stringent than any prior assumptions imposed on the arm-level MDP, notably the unichain condition is no longer needed. Through numerical examples, we show that employing model predictive control for steering generally results in superior performance compared to other existing policies. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_11913 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An Optimal-Control Approach to Infinite-Horizon Restless Bandits: Achieving Asymptotic Optimality with Minimal Assumptions YAN, Chen Optimization and Control Dynamical Systems Probability 93E03, 93E20, 93B03, 93B45, 90C05, 90C40 We adopt an optimal-control framework for addressing the undiscounted infinite-horizon discrete-time restless $N$-armed bandit problem. Unlike most studies that rely on constructing policies based on the relaxed single-armed Markov Decision Process (MDP), we propose relaxing the entire bandit MDP as an optimal-control problem through the certainty equivalence control principle. Our main contribution is demonstrating that the reachability of an optimal stationary state within the optimal-control problem is a sufficient condition for the existence of an asymptotically optimal policy. Such a policy can be devised using an "align and steer" strategy. This reachability assumption is less stringent than any prior assumptions imposed on the arm-level MDP, notably the unichain condition is no longer needed. Through numerical examples, we show that employing model predictive control for steering generally results in superior performance compared to other existing policies. |
| title | An Optimal-Control Approach to Infinite-Horizon Restless Bandits: Achieving Asymptotic Optimality with Minimal Assumptions |
| topic | Optimization and Control Dynamical Systems Probability 93E03, 93E20, 93B03, 93B45, 90C05, 90C40 |
| url | https://arxiv.org/abs/2403.11913 |