Online Learning in Markov Decision Processes with Adversarially Chosen Transition Probability Distributions

2013/03/12 by Yasin Abbasi-Yadkori, Peter L. Bartlett, Abbasi-Yadkori, Yasin +3
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.1303.3055

openalex publication_date 2013/03/12 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28

Abstract

We study the problem of learning Markov decision processes with finite state and action spaces when the transition probability distributions and loss functions are chosen adversarially and are allowed to change with time. We introduce an algorithm whose regret with respect to any policy in a comparison class grows as the square root of the number of rounds of the game, provided the transition probabilities satisfy a uniform mixing condition. Our approach is efficient as long as the comparison class is polynomial and we can compute expectations over sample paths for each policy. Designing an efficient algorithm with small regret for the general case remains an open problem.

Related

• Dynamic Regret of Online Markov Decision Processes
• Online Convex Optimization in Adversarial Markov Decision Processes
• No-Regret Online Reinforcement Learning with Adversarial Losses and Transitions
• Online Markov Decision Processes with Aggregate Bandit Feedback
• Online Learning in Kernelized Markov Decision Processes