Regret bounds for restless Markov bandits

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 first represents the setting as an MDP which exhibits some special structural properties. In order to grasp...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2014-11, Vol.558, p.62-76
Main Authors: Ortner, Ronald, Ryabko, Daniil, Auer, Peter, Munos, Rémi
Format: Article
Language:English
Subjects:
Agglomeration
Algorithms
Approximation
Artificial Intelligence
Computer Science
Homomorphisms
Learning
Markov chains
Markov decision processes
Markov processes
Policies
Regret
Restless bandits
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 first represents the setting as an MDP which exhibits some special structural properties. In order to grasp this information we introduce the notion of ε-structured MDPs, which are a generalization of concepts like (approximate) state aggregation and MDP homomorphisms. We propose a general algorithm for learning ε-structured MDPs and show regret bounds that demonstrate that additional structural information enhances learning. Applied to the restless bandit setting, this algorithm achieves after any T steps regret of order O˜(T) with respect to the best policy that knows the distributions of all arms. We make no assumptions on the Markov chains underlying each arm except that they are irreducible. In addition, we show that index-based policies are necessarily suboptimal for the considered problem.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2014.09.026