Regret Bounds for Restless Markov Bandits
This addresses a fundamental challenge in sequential decision-making for restless bandits, providing a theoretical guarantee with broad applicability in reinforcement learning and resource allocation.
The paper tackles the restless Markov bandit problem by proposing an algorithm that achieves $ ilde{O}(\sqrt{T})$ regret against the optimal policy, with no assumptions beyond irreducibility of the Markov chains, and demonstrates that index-based policies are suboptimal.
We consider the restless Markov bandit problem, in which the state of each arm evolves according to a Markov process independently of the learner's actions. We suggest an algorithm that after $T$ steps achieves $\tilde{O}(\sqrt{T})$ regret with respect to the best policy that knows the distributions of all arms. No assumptions on the Markov chains are made except that they are irreducible. In addition, we show that index-based policies are necessarily suboptimal for the considered problem.