General Formulation and PCL-Analysis for Restless Bandits with Limited Observability
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915676576284672 |
|---|---|
| author | Liu, Keqin Jia, Qizhen |
| author_facet | Liu, Keqin Jia, Qizhen |
| contents | In this paper, we consider a general observation model for restless multi-armed bandit problems. The operation of the player is based on the past observation history that is limited (partial) and error-prone due to resource constraints or environmental or intrinsic noises. By establishing a general probabilistic model for dynamics of the observation process, we formulate the problem as a restless bandit with an infinite high-dimensional belief state space. We apply the achievable region method with partial conservation law (PCL) to the infinite-state problem and analyze its indexability and priority index (Whittle index). Finally, we propose an approximation process to transform the problem into which the AG algorithm of Niño-Mora (2001) for finite-state problems can be applied. Numerical experiments show that our algorithm has excellent performance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_03034 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | General Formulation and PCL-Analysis for Restless Bandits with Limited Observability Liu, Keqin Jia, Qizhen Machine Learning In this paper, we consider a general observation model for restless multi-armed bandit problems. The operation of the player is based on the past observation history that is limited (partial) and error-prone due to resource constraints or environmental or intrinsic noises. By establishing a general probabilistic model for dynamics of the observation process, we formulate the problem as a restless bandit with an infinite high-dimensional belief state space. We apply the achievable region method with partial conservation law (PCL) to the infinite-state problem and analyze its indexability and priority index (Whittle index). Finally, we propose an approximation process to transform the problem into which the AG algorithm of Niño-Mora (2001) for finite-state problems can be applied. Numerical experiments show that our algorithm has excellent performance. |
| title | General Formulation and PCL-Analysis for Restless Bandits with Limited Observability |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2307.03034 |