Multi-Action Restless Bandits with Weakly Coupled Constraints: Simultaneous Learning and Control
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_ | 1866917856677986304 |
|---|---|
| author | Fu, Jing Moran, Bill Niño-Mora, José |
| author_facet | Fu, Jing Moran, Bill Niño-Mora, José |
| contents | We study a system with finitely many groups of multi-action bandit processes, each of which is a Markov decision process (MDP) with finite state and action spaces and potentially different transition matrices when taking different actions. The bandit processes of the same group share the same state and action spaces and, given the same action that is taken, the same transition matrix. All the bandit processes across various groups are subject to multiple weakly coupled constraints over their state and action variables. Unlike the past studies that focused on the offline case, we consider the online case without assuming full knowledge of transition matrices and reward functions a priori and propose an effective scheme that enables simultaneous learning and control. We prove the convergence of the relevant processes in both the timeline and the number of the bandit processes, referred to as the convergence in the time and the magnitude dimensions. Moreover, we prove that the relevant processes converge exponentially fast in the magnitude dimension, leading to exponentially diminishing performance deviation between the proposed online algorithms and offline optimality. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_03326 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Multi-Action Restless Bandits with Weakly Coupled Constraints: Simultaneous Learning and Control Fu, Jing Moran, Bill Niño-Mora, José Optimization and Control Machine Learning Probability 90B36 (Primary) 90B15, 90B22 (Secondary) We study a system with finitely many groups of multi-action bandit processes, each of which is a Markov decision process (MDP) with finite state and action spaces and potentially different transition matrices when taking different actions. The bandit processes of the same group share the same state and action spaces and, given the same action that is taken, the same transition matrix. All the bandit processes across various groups are subject to multiple weakly coupled constraints over their state and action variables. Unlike the past studies that focused on the offline case, we consider the online case without assuming full knowledge of transition matrices and reward functions a priori and propose an effective scheme that enables simultaneous learning and control. We prove the convergence of the relevant processes in both the timeline and the number of the bandit processes, referred to as the convergence in the time and the magnitude dimensions. Moreover, we prove that the relevant processes converge exponentially fast in the magnitude dimension, leading to exponentially diminishing performance deviation between the proposed online algorithms and offline optimality. |
| title | Multi-Action Restless Bandits with Weakly Coupled Constraints: Simultaneous Learning and Control |
| topic | Optimization and Control Machine Learning Probability 90B36 (Primary) 90B15, 90B22 (Secondary) |
| url | https://arxiv.org/abs/2412.03326 |