Relaxed Indexability and Index Policy for Partially Observable Restless Bandits
研究资源约束下只能操作部分马尔可夫过程的问题，提出基于松弛可索引性的算法，以低复杂度实现接近最优的性能，适用于运营研究和强化学习领域。
This paper addresses an important class of restless multiarmed bandit (RMAB) problems that finds broad application in operations research, stochastic optimization, and reinforcement learning. There are N independent Markov processes that may be operated, observed and offer rewards. Due to the resource constraint, we can only choose a subset of [Formula: see text] processes to operate and accrue reward determined by the states of selected processes. We formulate the problem as a partially observable RMAB with an infinite state space and design an algorithm that achieves a near-optimal performance with low complexity. Our algorithm is based on a generalization of Whittle’s original idea of indexability. Referred to as the relaxed indexability, the extended definition leads to the efficient online verifications and computations of the approximate Whittle index under the proposed algorithmic framework. This paper was accepted by Chung Piaw Teo, optimization. Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/mnsc.2022.02831 .