Weakly-Coupled Multi-Action Restless Bandits -- Exponential Convergence in Probability
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913040784424960 |
|---|---|
| author | Fu, Jing Moran, Bill Nino-Mora, Jose |
| author_facet | Fu, Jing Moran, Bill Nino-Mora, Jose |
| contents | We study a finite time horizon Markov decision process (MDP) consisting of several groups of multi-action finite-state restless bandit processes, which are identical within each group. The bandit processes into different groups can be rather different. The bandit processes are subject to multiple weakly coupled constraints on their state and action variables. In contrast to prior studies that considered only a few specific policies/algorithms, here, we study the behaviours of the general stochastic process and, most importantly, the design of policies that guarantee its convergence to an ideal trajectory as the problem size increases. We prove that, for any policy in a rather general class, the resulting stochastic process converges in probability to a deterministic process as the system size (measured by the number of bandits) tends to infinity, at an exponential rate. Unlike the previous proofs, our exponential convergence does not rely on any non-degenerate assumptions. It follows that the chosen policy asymptotically approaches optimality (with exponentially diminishing suboptimality) in the size dimension if and only if the deterministic process coincides with optimality. We further propose a policy and prove that, in general, it converges in probability to optimality exponentially fast in the system size. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_15683 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Weakly-Coupled Multi-Action Restless Bandits -- Exponential Convergence in Probability Fu, Jing Moran, Bill Nino-Mora, Jose Optimization and Control 93E20 (Primary) 90B36, 93E03 (Secondary) We study a finite time horizon Markov decision process (MDP) consisting of several groups of multi-action finite-state restless bandit processes, which are identical within each group. The bandit processes into different groups can be rather different. The bandit processes are subject to multiple weakly coupled constraints on their state and action variables. In contrast to prior studies that considered only a few specific policies/algorithms, here, we study the behaviours of the general stochastic process and, most importantly, the design of policies that guarantee its convergence to an ideal trajectory as the problem size increases. We prove that, for any policy in a rather general class, the resulting stochastic process converges in probability to a deterministic process as the system size (measured by the number of bandits) tends to infinity, at an exponential rate. Unlike the previous proofs, our exponential convergence does not rely on any non-degenerate assumptions. It follows that the chosen policy asymptotically approaches optimality (with exponentially diminishing suboptimality) in the size dimension if and only if the deterministic process coincides with optimality. We further propose a policy and prove that, in general, it converges in probability to optimality exponentially fast in the system size. |
| title | Weakly-Coupled Multi-Action Restless Bandits -- Exponential Convergence in Probability |
| topic | Optimization and Control 93E20 (Primary) 90B36, 93E03 (Secondary) |
| url | https://arxiv.org/abs/2604.15683 |