A Theory of Regularized Markov Decision Processes

By Matthieu Geist, Bruno Scherrer, Olivier Pietquin. 2019

417 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

AlgaeDICE: Policy Gradient from Arbitrary Experience (2019, methodology): “The regularization we employ is inspired by previous uses of regularization in RL. Adding regularization to MDPs (Neu et al., 2017; Geist et al., 2019) has been investigated for many diﬀerent purposes in the literature, including exploration (de Farias and Van Roy, 2000; Haarnoja et al., 2017,…”
Safe Policy Improvement with Soft Baseline Bootstrapping (2019, methodology): “…they would be either too conservative if the proximity regularization is applied with respect to the fixed baseline, or would converge to the fixed point obtained when solving the MLE MDP if the proximity regularization is moving with the last policy update (Corollary 3 of Geist et al., 2019).”
On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift (2019, methodology): “Assuming bounded concentrability coefficient, there are a notable set of provable average case guarantees for the MD-MPI algorithm [Geist et al., 2019] (see also [Azar et al.”
From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization (2020, background): “Generally speaking, in the sequential setting, learning in games can be addressed by either approximate dynamic programming in the perfect information case (Lagoudakis & Parr, 2002; Pérolat et al., 2015; 2016; Pérolat et al., 2016; 2017; Geist et al., 2019), regret minimization algorithms (Zinkevich”
Revisiting Design Choices in Proximal Policy Optimization (2020, positive): “This objective has not been studied empirically but has been the main focus of theoretical studies around PPO [11, 14, 16].”
Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes (2019, methodology): “…secondorder method due to the use of its particular preconditioner, and provide an iteration complexity to achieve an ǫ-optimal policy that is at most 2 (1−γ)2ǫ iterations, improving upon previous related results of [Even-Dar et al., 2009, Geist et al., 2019] (see Table 1 caption and Section 2).”
RLAIF: Scaling Reinforcement Learning from Human Feedback with AI Feedback (2023, neutral): “Op-tionally, a Kullback-Leibler (KL) divergence term D KL is added to the objective to penalize π RLθ for deviating from the original SFT policy π SFT , controlled by the hyperparameter β (Fox et al., 2015; Geist et al., 2019).”
Provably Good Batch Reinforcement Learning Without Great Exploration (2020, background): “When comparing to onpolicy policy optimization [15, 34, 2, 13], the constant C is akin to the density ratio with respect to an optimal policy in those works, though we pay an additional price on the size of densities.”
VIREL: A Variational Inference Framework for Reinforcement Learning (2018, background): “It is wellunderstood that optimal policies under regularised Bellman operators are more stochastic than under their equivalent unregularised operators [20].”
A Theoretical Analysis of Deep Q-Learning (2019, methodology): “plicable to ReLU networks due to the huge capacity of deep neural networks. Furthermore, various extensions of FQI are studied in Antos et al. (2008a); Farahmand et al. (2009); Tosatto et al. (2017); Geist et al. (2019) to handle continuous actions space, ensemble learning, and entropy regularizatio”
Recent advances in reinforcement learning in finance (2021, methodology): “Geist et al. (2019) proposed a unified framework to analyze the above algorithms via a regularized Bellman operator.”
Bellman-consistent Pessimism for Offline Reinforcement Learning (2021, methodology): “This property has been leveraged in many prior works, although typically in online RL settings [Even-Dar et al., 2009; Agarwal et al., 2019; Geist et al., 2019; Cai et al., 2020; Shani et al., 2020].”
A General Theoretical Paradigm to Understand Learning from Human Preferences (2023, background): “The constraint of staying close to a known reference policy can be satisfied e.g., by using KL regularisation (Geist et al., 2019) and its role is to avoid model drift (Lazaridou et al., 2020; Lu et al., 2020).”
Dealing with Non-Stationarity in MARL via Trust-Region Decomposition (2021, background): “Each reinforcement learning problem can be formulated as optimization problems from two distinct perspectives, i.e., Geist et al. (2019) and Shani et al. (2020) have utilized the mirror descent scheme (10) and update the policy iteratively as follows where KL( · , · ) denotes the Bregman divergence…”
Reinforcement Learning: Theory and Algorithms (2019, methodology): “The analysis of the MD-MPI algorithm [Geist et al., 2019] also implies a O(1/T ) rate for the NPG, though with worse dependencies on other parameters.”
Co-Adaptation of Algorithmic and Implementational Innovations in Inference-based Deep Reinforcement Learning (2021, background): “KL control fixes πp and converges to a regularizedoptimal policy in an exact case [15, 64].”
Provably Efficient Exploration in Policy Optimization (2019, background): “Such a notion of robustness partially justifies the empirical advantages of KL-regularized policy optimization (Neu et al., 2017; Geist et al., 2019).”
RLAIF vs. RLHF: Scaling Reinforcement Learning from Human Feedback with AI Feedback (2023, background): “Optionally, a Kullback-Leibler (KL) divergence term D KL is added to the objective to penalize π RLθ for deviating from the original SFT policy π SFT , controlled by the hyperparameter β (Fox et al., 2015; Geist et al., 2019).”
Munchausen Reinforcement Learning (2020, background): “(4)It can be related to the unregularized optimal q-function, ‖q ∗ − q∗‖∞ ≤ τ ln |A| 1−γ [15].”
Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning? (2019, background): “…dynamic programming results typically require ∞ -bounded errors, the notion of concentrability (originally due to (Munos, 2005)) permits sharper bounds in terms of average-case function approximation error, provided that the concentrability coefﬁcient is bounded (e.g. see Munos (2005) 2019)).”