A Theory of Regularized Markov Decision Processes

Abstract

Many recent successful (deep) reinforcement learning algorithms make use of regularization, generally based on entropy or Kullback-Leibler divergence. We propose a general theory of regularized Markov Decision Processes that generalizes these approaches in two directions: we consider a larger class of regularizers, and we consider the general modified policy iteration approach, encompassing both policy iteration and value iteration. The core building blocks of this theory are a notion of regularized Bellman operator and the Legendre-Fenchel transform, a classical tool of convex optimization. This approach allows for error propagation analyses of general algorithmic schemes of which (possibly variants of) classical algorithms such as Trust Region Policy Optimization, Soft Q-learning, Stochastic Actor Critic or Dynamic Policy Programming are special cases. This also draws connections to proximal convex optimization, especially to Mirror Descent.

ICML 2019

Cited by in corpus (53)

• A Theoretical Analysis of Deep Q-Learning
• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
• A reinforcement learning approach to rare trajectory sampling
• Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization
• Reinforcement learning of rare diffusive dynamics
• VIREL: A Variational Inference Framework for Reinforcement Learning
• Maximum Entropy RL (Provably) Solves Some Robust RL Problems
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity
• Mirror Descent Policy Optimization
• Provably Efficient Exploration in Policy Optimization
• From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization
• Bellman-consistent Pessimism for Offline Reinforcement Learning
• Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy
• Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning
• Adversarially Guided Actor-Critic
• MADE: Exploration via Maximizing Deviation from Explored Regions
• Optimistic Policy Optimization with Bandit Feedback
• Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization
• Offline Reinforcement Learning with Value-based Episodic Memory
• Proximal Policy Optimization with Relative Pearson Divergence
• Proximal Policy Optimization with Adaptive Threshold for Symmetric Relative Density Ratio
• Greedification Operators for Policy Optimization: Investigating Forward and Reverse KL Divergences
• Adaptive Approximate Policy Iteration
• Provable Fictitious Play for General Mean-Field Games
• Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence
• Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation
• On Connections between Constrained Optimization and Reinforcement Learning
• Stable Policy Optimization via Off-Policy Divergence Regularization
• Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm
• Twice regularized MDPs and the equivalence between robustness and regularization
• Regularity and stability of feedback relaxed controls
• Robust Inverse Reinforcement Learning under Transition Dynamics Mismatch
• On Linear Convergence of Policy Gradient Methods for Finite MDPs
• Dimension-Free Rates for Natural Policy Gradient in Multi-Agent Reinforcement Learning
• Merging Deterministic Policy Gradient Estimations with Varied Bias-Variance Tradeoff for Effective Deep Reinforcement Learning
• Regularized Inverse Reinforcement Learning
• Provably Correct Optimization and Exploration with Non-linear Policies
• A Convergence Result for Regularized Actor-Critic Methods
• Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning
• Approximate Newton policy gradient algorithms
• On the Convergence of Approximate and Regularized Policy Iteration Schemes
• Logistic Q-Learning
• Bregman Gradient Policy Optimization
• Reward is enough for convex MDPs
• Convex Regularization in Monte-Carlo Tree Search
• Implicitly Regularized RL with Implicit Q-Values
• Actor-critic is implicitly biased towards high entropy optimal policies
• Robust Generalization despite Distribution Shift via Minimum Discriminating Information
• Geometric Value Iteration: Dynamic Error-Aware KL Regularization for Reinforcement Learning
• Cautious Actor-Critic
• Cautious Policy Programming: Exploiting KL Regularization in Monotonic Policy Improvement for Reinforcement Learning
• Reinforcement Learning With Sparse-Executing Actions via Sparsity Regularization
• Co-Adaptation of Algorithmic and Implementational Innovations in Inference-based Deep Reinforcement Learning