Regret Bounds for Restless Markov Bandits

Abstract

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.

In proceedings of The 23rd International Conference on Algorithmic Learning Theory (ALT 2012)

Cited by in corpus (12)

• Online Regret Bounds for Undiscounted Continuous Reinforcement Learning
• Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits
• Regret Bounds for Reinforcement Learning with Policy Advice
• Rebounding Bandits for Modeling Satiation Effects
• Bandit Learning with Delayed Impact of Actions
• Finite-Time Analysis of Round-Robin Kullback-Leibler Upper Confidence Bounds for Optimal Adaptive Allocation with Multiple Plays and Markovian Rewards
• When are Kalman-filter restless bandits indexable?
• Learning to Detect an Odd Restless Markov Arm with a Trembling Hand
• Detecting an Odd Restless Markov Arm with a Trembling Hand
• Offline RL With Resource Constrained Online Deployment
• Reinforcement Learning for Finite-Horizon Restless Multi-Armed Multi-Action Bandits
• Stationary Mixing Bandits