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

• (More) Efficient Reinforcement Learning via Posterior Sampling
• Algorithmic Framework for Model-based Deep Reinforcement Learning with Theoretical Guarantees
• Near-optimal Reinforcement Learning in Factored MDPs
• 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
• A Sliding-Window Algorithm for Markov Decision Processes with Arbitrarily Changing Rewards and Transitions
• Fast active learning for pure exploration in reinforcement learning
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Selecting the State-Representation in Reinforcement Learning
• Variational Regret Bounds for Reinforcement Learning
• Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism
• Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs
• 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
• Posterior Sampling for Large Scale Reinforcement Learning
• An Asymptotically Optimal Policy for Uniform Bandits of Unknown Support
• Tactical Optimism and Pessimism for Deep Reinforcement Learning
• Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policies
• Surprising Negative Results for Generative Adversarial Tree Search
• Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalities
• Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits
• Regret Bounds for Reinforcement Learning with Policy Advice
• Exploration-Exploitation Trade-off in Reinforcement Learning on Online Markov Decision Processes with Global Concave Rewards
• Tightening Exploration in Upper Confidence Reinforcement Learning
• Adaptive Approximate Policy Iteration
• Normal Bandits of Unknown Means and Variances: Asymptotic Optimality, Finite Horizon Regret Bounds, and a Solution to an Open Problem
• Conservative Exploration in Reinforcement Learning
• Regret Bounds for Discounted MDPs
• Online Learning for Unknown Partially Observable MDPs
• Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function
• Online Learning for Stochastic Shortest Path Model via Posterior Sampling
• Delegative Reinforcement Learning: learning to avoid traps with a little help
• Reward Biased Maximum Likelihood Estimation for Reinforcement Learning
• Minimax Regret for Stochastic Shortest Path
• A Survey of Exploration Methods in Reinforcement Learning
• Oracle-Efficient Regret Minimization in Factored MDPs with Unknown Structure
• Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret
• Reinforcement Learning in Factored MDPs: Oracle-Efficient Algorithms and Tighter Regret Bounds for the Non-Episodic Setting
• Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• Asymptotically Optimal Sequential Experimentation Under Generalized Ranking
• Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• Fast rates for online learning in Linearly Solvable Markov Decision Processes
• Online Learning in Kernelized Markov Decision Processes
• A Provably Efficient Sample Collection Strategy for Reinforcement Learning
• Near-optimal Regret Bounds for Stochastic Shortest Path
• Model-Based Reinforcement Learning Exploiting State-Action Equivalence
• A Model-free Learning Algorithm for Infinite-horizon Average-reward MDPs with Near-optimal Regret
• Improved Regret Bound and Experience Replay in Regularized Policy Iteration
• Towards Tight Bounds on the Sample Complexity of Average-reward MDPs
• Mitigating Planner Overfitting in Model-Based Reinforcement Learning
• Posterior sampling for reinforcement learning: worst-case regret bounds
• Provably Efficient Multi-Task Reinforcement Learning with Model Transfer
• Improved Exploration in Factored Average-Reward MDPs
• Fundamental Limits of Reinforcement Learning in Environment with Endogeneous and Exogeneous Uncertainty
• Optimal Nudging: Solving Average-Reward Semi-Markov Decision Processes as a Minimal Sequence of Cumulative Tasks
• Bad-Policy Density: A Measure of Reinforcement Learning Hardness
• Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP
• Near-optimal Bayesian Solution For Unknown Discrete Markov Decision Process
• Convergence Rates of Posterior Distributions in Markov Decision Process
• Efficient Reinforcement Learning in Deterministic Systems with Value Function Generalization
• Structural Return Maximization for Reinforcement Learning
• Communication Efficient Parallel Reinforcement Learning
• When do discounted-optimal policies also optimize the gain?