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 (27)

• Online Regret Bounds for Undiscounted Continuous Reinforcement Learning
• On the Sample Complexity of Reinforcement Learning with a Generative Model
• Understanding Domain Randomization for Sim-to-real Transfer
• Selecting the State-Representation in Reinforcement Learning
• Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism
• Thompson Sampling for Learning Parameterized Markov Decision Processes
• Optimal Regret Bounds for Selecting the State Representation in Reinforcement Learning
• Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes
• Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits
• Exploration-Exploitation Trade-off in Reinforcement Learning on Online Markov Decision Processes with Global Concave Rewards
• Normal Bandits of Unknown Means and Variances: Asymptotic Optimality, Finite Horizon Regret Bounds, and a Solution to an Open Problem
• Delegative Reinforcement Learning: learning to avoid traps with a little help
• Online Learning for Stochastic Shortest Path Model via Posterior Sampling
• A Survey of Exploration Methods in Reinforcement Learning
• Model-Based Reinforcement Learning Exploiting State-Action Equivalence
• Near-optimal Regret Bounds for Stochastic Shortest Path
• Towards Tight Bounds on the Sample Complexity of Average-reward MDPs
• Improved Regret Bound and Experience Replay in Regularized Policy Iteration
• Provably Efficient Multi-Task Reinforcement Learning with Model Transfer
• Bad-Policy Density: A Measure of Reinforcement Learning Hardness
• Convergence Rates of Posterior Distributions in Markov Decision Process
• Fundamental Limits of Reinforcement Learning in Environment with Endogeneous and Exogeneous Uncertainty
• Near-optimal Bayesian Solution For Unknown Discrete Markov Decision Process
• Structural Return Maximization for Reinforcement Learning
• When do discounted-optimal policies also optimize the gain?
• Optimal Nudging: Solving Average-Reward Semi-Markov Decision Processes as a Minimal Sequence of Cumulative Tasks
• Communication Efficient Parallel Reinforcement Learning