REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs

Abstract

We provide an algorithm that achieves the optimal regret rate in an unknown weakly communicating Markov Decision Process (MDP). The algorithm proceeds in episodes where, in each episode, it picks a policy using regularization based on the span of the optimal bias vector. For an MDP with S states and A actions whose optimal bias vector has span bounded by H, we show a regret bound of ~O(HSpAT). We also relate the span to various diameter-like quantities associated with the MDP, demonstrating how our results improve on previous regret bounds.

Appears in Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence (UAI2009)

Cited by in corpus (8)

• Online Regret Bounds for Undiscounted Continuous Reinforcement Learning
• On the Sample Complexity of Reinforcement Learning with a Generative Model
• Selecting the State-Representation in Reinforcement Learning
• Thompson Sampling for Learning Parameterized Markov Decision Processes
• Optimal Regret Bounds for Selecting the State Representation in Reinforcement Learning
• Normal Bandits of Unknown Means and Variances: Asymptotic Optimality, Finite Horizon Regret Bounds, and a Solution to an Open Problem
• Structural Return Maximization for Reinforcement Learning
• Optimal Nudging: Solving Average-Reward Semi-Markov Decision Processes as a Minimal Sequence of Cumulative Tasks