A Theory of Regularized Markov Decision Processes

Matthieu Geist; Bruno Scherrer; Olivier Pietquin

Source-linked AI summary

A Theory of Regularized Markov Decision Processes

Matthieu Geist, Bruno Scherrer, Olivier Pietquin

arXiv:1901.11275v2Jan 31, 2019cs.LGstat.ML

TL;DR

Regularized reinforcement-learning algorithms use varied regularizers and often have ad-hoc analyses. The paper develops a general regularized-MDP theory using regularized Bellman operators and Legendre-Fenchel transforms, covering modified policy iteration and analyzing error propagation. It also connects the framework to Mirror Descent and convex optimization.

Problem
Existing regularized reinforcement-learning algorithms use different principles, specific regularizers, and ad-hoc analyses.
Method
The paper builds regularized MDPs and modified policy-iteration schemes from regularized Bellman operators and Legendre-Fenchel transforms.
Results
The framework derives variations of existing algorithms and analyzes their related error propagation.
Takeaways & Limitations
The theory provides a general framework connecting regularized dynamic programming with convex optimization, especially Mirror Descent.
Takeaways & Limitations
The convergence rate of MD-MPI remains an open question, although a sublinear rate is considered possible.

Abstract

from arXiv · show

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.

1. Introduction

Existing reinforcement-learning algorithms use regularization for motivations including exploration and robustness, but often rely on specific regularizers and ad-hoc analyses. The paper proposes a general theory based on regularized MDPs, Bellman operators, and convex duality.

Entropy, KL, and Tsallis regularization appear across policy-iteration and value-iteration algorithms, including TRPO, DPP, Soft Q-learning, SAC, and sparse policies.These approaches use different regularization choices and algorithmic schemes.
Existing algorithms share regularization but are derived from different principles and generally receive algorithm-specific analyses.
The proposed framework generalizes regularized MDPs through a regularized Bellman operator and an associated Legendre-Fenchel transform.It studies theoretical properties and regularized approximate dynamic-programming schemes.
The framework provides error-propagation analysis for many existing algorithms and connects regularized dynamic programming to Mirror Descent and convex optimization.
The work is complementary to prior unified and smoothed dynamic-programming treatments because it considers a different MDP setting, regularized quantity, and dynamic-programming approach.

2. Background

The background defines finite discounted MDPs and classical Bellman operators, then introduces strongly convex regularizers through the Legendre-Fenchel transform. These constructions recover smoothed and sparse policy-selection operators.

Unregularized MDPs: An MDP consists of finite state and action spaces, a transition kernel, a reward function, and a discount factor γ in (0, 1).
Unregularized MDPs: A policy assigns an action distribution to each state, and its Bellman evaluation operator is a γ-contraction with unique fixed point vπ.
Unregularized MDPs: The Bellman operator can be expressed as the state-wise expected action-value q under the policy, while the optimality operator and greedy policies follow from the same construction.
Legendre-Fenchel transform: For a strongly convex function Ω on action distributions, its Legendre-Fenchel transform Ω* supplies the convex-optimization dual used in regularized action selection.
Background: The exposition assumes finite spaces for simplicity, while stating that the results extend to more general cases.
Legendre-Fenchel transform: Negative Shannon entropy yields a smoothed maximum and softmax policy, whereas negative Tsallis entropy yields sparsemax as the maximizing policy.

3. Regularized MDPs

Regularized MDPs modify Bellman evaluation by subtracting a convex policy penalty, with optimality obtained through its convex conjugate. The resulting operators retain contraction properties and define regularized values and policies while relating them to the original MDP.

Regularized Bellman operators: Regularized Bellman evaluation replaces expected action value with ⟨πs, qs⟩ − Ω(πs), and state-wise maximization yields the conjugate Ω* and a greedy policy.
Regularized Bellman operators: Both regularized Bellman operators are γ-contractions, enabling unique fixed-point regularized value functions.
Regularized value functions: A policy's regularized value is its unregularized value under the modified reward rπ − Ω(π).
Regularized value functions: The greedy policy induced by the regularized optimal value is the unique optimal regularized policy.
Regularized value functions: Regularization changes the optimization problem and requires relating regularized and unregularized value functions to assess performance in the original MDP.
Related Works: The regularized Bellman operator provides a principled generalization of existing results and the central building block for regularized approximate dynamic programming.

4. Regularized Modified Policy Iteration

Regularized modified policy iteration provides a single framework that alternates regularized greedy and partial evaluation steps, recovering value and policy iteration as special cases. The framework also instantiates several entropy- and KL-regularized algorithms and supports error-propagation analysis.

reg-MPI alternates a regularized greedy step producing πk+1 with a partial regularized evaluation step producing vk+1.
With m = 1, reg-MPI recovers regularized value iteration; with m = ∞, it recovers regularized policy iteration.
Soft Q-learning, SAC, MPO, and related methods can be interpreted as practical instantiations of regularized greedy or evaluation steps.These instantiations use regularizers such as negative entropy, Tsallis entropy, or KL divergence.
For any regularizer, the greedy policy can be computed analytically through ∇Ω∗ or approximated with direct optimization and parameterized policies.The Legendre-Fenchel transform connects the regularizer to the greedy policy, while direct optimization is available when the transform is not analytic.
The analysis propagates errors from both regularized greedy and evaluation steps and establishes convergence and rate-of-convergence results.
The resulting loss bound matches the unregularized AMPI bound up to regularization, with no dependence on m, while empirical benefits remain unexplained by the bound alone.The authors hypothesize that stochastic policies may lower concentrability coefficients and that regularized greedy steps may control approximation error, leaving finite-sample analysis for future work.

5. Mirror Descent Modified Policy Iteration

Mirror Descent Modified Policy Iteration replaces fixed regularization with a Bregman divergence relative to the previous policy, connecting modified policy iteration to proximal Mirror Descent. Its analysis relates regularized greedy updates to unregularized policy loss and bounds regret under exact and approximate computation.

MD-MPI penalizes divergence from the previous policy, addressing the mismatch between regularized solutions and the original unregularized MDP.The divergence is generated by a strongly convex regularizer and is zero at the previous policy.
The greedy update resembles proximal Mirror Descent, with −qk acting as the gradient; two variants differ in how partial evaluation is regularized.Type 1 uses the previous policy's regularizer, while type 2 uses the current policy's regularizer; current-policy regularization simplifies to partial unregularized evaluation.
MD-MPI recovers or relates to established algorithms including TRPO and DPP, while its broader analysis is not claimed to cover every special case.TRPO corresponds to type 2 with m = ∞ and KL divergence, whereas DPP is a reparametrization of type 1 with m = 1.
The analysis handles errors in both greedy and evaluation steps and derives regret, ℓp, and best-policy loss bounds for MD-MPI.Controlling average regret controls the loss of the best policy computed so far, motivating selection of that policy instead of the last iterate.
In the exact case, both MD-MPI types share a convergence rate, while approximate analysis propagates cumulative normalized errors rather than emphasizing only recent iterations.The changing Bregman regularizer requires a distinct notion of approximate regularized greediness and a technical relation between regularized and unregularized quantities.
The convergence rate of MD-MPI's loss remains open, although a sublinear rate is considered possible.The Bregman penalty slows greediness relative to classical dynamic programming and is discussed as potentially favoring stability in approximate settings.

6. Conclusion

The paper presents a general theory and modified policy-iteration scheme for regularized MDPs, while identifying extensions and open questions for future work.

The framework modifies Bellman evaluation using either a fixed convex function or a Bregman divergence between consecutive policies.
A general modified policy iteration scheme derives variations of existing regularized reinforcement-learning algorithms and supports analysis of error propagation.
The framework connects approximate dynamic programming with proximal convex optimization, temporal consistency equations, policy search, inverse reinforcement learning, and zero-sum Markov games.
Open questions include combining error propagation with finite-sample analysis, selecting regularizers for particular contexts, and handling schemes that combine fixed regularizers with divergences.

A. Proofs of section 3

The proofs establish that regularized Bellman operators retain key structural properties of their unregularized counterparts, including monotonicity, affine behavior, distributivity, and contraction.

The proof section establishes properties of the regularized Bellman operators before deriving their policy and value-function results.
The regularized evaluation operator is affine and monotone, while the optimality operator preserves monotonicity through the Legendre-Fenchel transform.
The evaluation operator satisfies distributivity under constant shifts, with the shift scaled by the discount factor γ.
Both regularized operators have the same contraction factor as their unregularized counterparts.
Strong convexity makes the policy greedy with respect to the optimal regularized value function unique and optimal.
The proofs relate regularized and unregularized values and bound the performance of the regularized optimal policy for the original problem.

B. Proofs of section 4

The section-4 results require no new proofs because the established regularized quantities satisfy the same properties as their unregularized counterparts.

Section 4 results follow by replacing unregularized value functions and Bellman operators with their regularized counterparts in existing proofs.
The Mirror Descent Modified Policy Iteration proofs are less straightforward than the section-4 proofs.

C. Proofs of section 5

The proofs develop bounds for Mirror Descent Modified Policy Iteration using Bregman-divergence identities, error decompositions, and regret analyses adapted from approximate policy iteration.

The three-point identity for Bregman divergences is used to derive the key Mirror Descent Modified Policy Iteration lemma.
The proofs use nonnegativity of the Bregman divergence and the identity relating regularized operators to divergence-penalized updates.
The analysis bounds Bellman residuals, shifts, distances, losses, and regrets for both MD-MPI types.
The proofs account for approximation errors in value updates and greedy steps when relating residuals to losses and regret.
The regret analysis reuses approximate modified policy-iteration arguments, with additional terms arising from Bregman divergences and initial-policy dependence.
Corollaries derive alternative regret and loss bounds by applying a concentration lemma, Hölder’s inequality, and limiting arguments.

D.1. Dynamic programming and optimization

The framework extends regularized modified policy iteration with weighted regularizers, yielding regret bounds and unique regularized optimal policies. It also connects regularized greedy computation to Mirror Descent and temporal-consistency methods.

Optimality and connections: Regularized greedy computation resembles a Mirror Descent step, with the policy in primal space and the q-function in dual space.The framework suggests deriving further dynamic-programming methods from proximal convex optimization.
Weighted regularization: Weighted reg-MPI uses regularizers of the form Ω_k = α_kΩ, with positive decreasing weights α_k.The scheme changes the regularizer across iterations, analogous to varying a learning-rate parameter.
Weighted regularization: Theorem 5 bounds regret under positive decreasing regularizer weights after K iterations.The proof controls the Bellman residual, distance, shift, loss, and accumulated regret.
Weighted regularization: O(1/K) average-regret convergence for MD-MPI becomes weight-dependent; α_k in O(1/k) yields average regret in O(ln K/K).The stated rate illustrates how regularizer weighting affects convergence.
Optimality and connections: Strongly convex regularization makes regularized greedy policies and the regularized optimal policy unique.The optimal policy and value function are characterized as unique solutions of the regularized Bellman equations.
Optimality and connections: For negative entropy, the optimality equations simplify into a temporal consistency equation used to estimate optimal value-policy pairs.Extensions to Tsallis entropy require a Legendre-Fenchel Lagrangian with learnable Lagrange multipliers.

D.3. Regularized policy gradient

The paper extends policy-gradient optimization to regularized MDPs using occupancy measures and a regularized gradient theorem. It notes that the resulting gradient can differ from the usual entropic policy gradient and leaves empirical comparisons for future work.

Objective and gradient: Regularized policy search maximizes a value objective while incorporating the regularizer into the MDP framework.The objective is defined using a user-specified initial-state distribution and its induced value function.
Objective and gradient: The γ-weighted occupancy measure d^ν,π captures state-action visitation under policy π from initial distribution ν.It is defined as (1 − γ)ν(I − γP_π)^−1, with d^ν,π(s,a) = d^ν,π(s)π(a|s).
Objective and gradient: Theorem 6 provides the gradient of the regularized objective J_Ω for regularized MDPs.The derivation uses the nabla-log trick, chain rule, and value functions associated with regularized policy-gradient terms.
Scope and limitation: The regularized policy-gradient expression may differ from the usual entropic policy gradient because it involves the regularized q-function.The authors propose replacing Ω with a Bregman divergence and leave empirical comparisons among resulting approaches for future work.

D.4. Regularized inverse reinforcement learning

Regularization makes the inverse-reinforcement-learning solution identifiable at the level of a unique optimal policy and permits construction of a compatible reward when the model and policy are known. The result is well-defined but not yet practical, and the framework is extended conceptually to zero-sum Markov games.

Regularized IRL: Classical IRL is ill-posed because multiple rewards, including null reward, can explain expert behavior.Under null reward, every policy is optimal in the unregularized formulation.
Regularized IRL: With regularization, the optimal policy is unique; negative entropy with null reward selects the unique uniform maximum-entropy policy.This provides a well-defined regularized formulation of the inverse problem.
Regularized IRL: Given the model and a known optimal regularized policy, one can construct a reward for which that policy is uniquely optimal.The construction is justified through uniqueness of regularized greediness and the regularized Bellman optimality equation.
Regularized IRL: The construction is not very practical; in the entropic case, it yields a reward proportional to the policy log-probability.The authors suggest that the general framework could support more practical IRL algorithms.
Zero-sum Markov games: Regularized zero-sum Markov games can be constructed using two strongly convex player regularizers and minimax operators.The regularized evaluation operator remains a γ-contraction, supporting unique fixed-point value functions and greedy policies.
Zero-sum Markov games: The unregularized error-propagation analysis can be adapted to regularized games, but extension to Bregman-divergence regularization remains future work.This marks a scope boundary for the game-theoretic extension.