PaperlayerView exact revision on arXiv

Source-linked AI summary

A unified view of entropy-regularized Markov decision processes

Gergely Neu, Anders Jonsson, Vicenç Gómez

arXiv:1705.07798v1cs.LGcs.AIstat.ML

TL;DR

The paper addresses how to unify and analyze entropy-regularized average-reward reinforcement learning in MDPs. It extends the MDP linear-programming formulation to convex regularization and derives a Bellman-like dual using conditional entropy. The framework shows that exact TRPO converges to the optimal policy, while entropy-regularized policy-gradient approximations may fail to converge to a fixed point.

  • Problem

    The paper seeks a unified theoretical treatment of entropy-regularized average-reward reinforcement-learning algorithms and their convergence behavior.

  • Method

    The paper extends MDP linear programming to convex regularization and uses conditional entropy of joint state-action distributions to derive a dual problem resembling Bellman optimality equations.

  • Results

    Exact TRPO converges to the optimal policy, while approximation steps in the entropy-regularized policy-gradient method of Mnih et al. may lead to bad local optima or divergence.

  • Takeaways & Limitations

    The convex-optimization framework theoretically justifies existing reinforcement-learning algorithms and highlights potential problems in heuristic methods.

  • Takeaways & Limitations

    The paper does not provide a statistical justification for entropy regularization, and whether it provably improves exploration in unknown MDPs remains open.

Abstract

from arXiv · show

We propose a general framework for entropy-regularized average-reward reinforcement learning in Markov decision processes (MDPs). Our approach is based on extending the linear-programming formulation of policy optimization in MDPs to accommodate convex regularization functions. Our key result is showing that using the conditional entropy of the joint state-action distributions as regularization yields a dual optimization problem closely resembling the Bellman optimality equations. This result enables us to formalize a number of state-of-the-art entropy-regularized reinforcement learning algorithms as approximate variants of Mirror Descent or Dual Averaging, and thus to argue about the convergence properties of these methods. In particular, we show that the exact version of the TRPO algorithm of Schulman et al. (2015) actually converges to the optimal policy, while the entropy-regularized policy gradient methods of Mnih et al. (2016) may fail to converge to a fixed point. Finally, we illustrate empirically the effects of using various regularization techniques on learning performance in a simple reinforcement learning setup.

1. Introduction

The paper develops a convex-optimization framework connecting entropy-regularized average-reward MDP objectives with Bellman-like equations and learning algorithms. It uses this connection to analyze convergence and identify potential failures in existing methods.

  • Motivation: Greedy Bellman-equation solutions can be far from optimal in unknown, partially known, or misspecified environments.Regularization is presented as a principled response to this issue.
  • Motivation: Entropy regularization has been used in reinforcement learning for safe exploration, risk-sensitive policies, and modeling imperfect decision-makers.The paper situates its framework within broader uses of entropy regularization in machine learning and reinforcement learning.
  • Framework: The framework extends MDP linear programming to convex regularization and establishes Lagrangian duality between a regularized average-reward objective and entropy-regularized Bellman equations.Using conditional entropy of joint state-action distributions produces nonlinear equations resembling Bellman optimality equations.
  • Algorithmic connections: TRPO and entropy-regularized policy-gradient methods are interpreted as approximate Mirror Descent and Dual Averaging methods, respectively.Both are also interpreted as regularized policy-iteration methods.
  • Convergence analysis: The exact TRPO method converges to the optimal policy, whereas approximation steps in the method of Mnih et al. may cause bad local optima or divergence.The paper identifies these methods as instances where the convex-optimization view provides theoretical justification or exposes possible inconsistencies.
  • Scope: The paper analyzes the average-reward formulation while noting that its conclusions remain valid in discounted and episodic settings.The paper is organized around linear-programming, convex-programming, and dynamic-programming formulations of regularized MDPs.

2. Preliminaries on Markov decision processes

The paper formulates average-reward MDP optimization through stationary state-action distributions and an equivalent linear program. Under stated assumptions, the LP recovers the optimal average reward and Bellman value functions.

  • MDP setup: An MDP consists of finite states and actions, transition probabilities, and rewards, with the learner repeatedly observing states, selecting actions, transitioning, and receiving rewards.The section studies the long-run average-reward criterion.
  • MDP setup: Stationary policies map each state to an action distribution, and under mild conditions they can maximize the average-reward criterion.The analysis assumes a unichain MDP, in which every stationary policy induces a unique stationary state distribution.
  • Assumptions: The single-recurrent-class assumption is restrictive because it prevents policies from covering different parts of the state space, although later sections do not require it.This simplifying assumption is distinct from the unichain assumption used for the broader setup.
  • Linear-programming formulation: The average reward is linear in the stationary state-action distribution, so optimal policy search can be written as a linear program over feasible stationary distributions.A stationary distribution induces both a state distribution and a policy through conditional normalization.
  • Linear-programming formulation: The LP optimum induces an optimal policy on recurrent states, while actions in transient states may be chosen arbitrarily under the stated assumption.The feasible-distribution set is a compact polytope, making the maximum well-defined.
  • Dual formulation: Strong LP duality identifies the optimal LP value with the optimal average reward, and the dual variables at optimum solve the average-reward Bellman optimality equations.The value-function solution is not unique because constant shifts preserve the equations; an additional normalization can make it unique.

3. Regularized MDPs: A convex-optimization view

The paper formulates regularized average-reward MDP optimization as a convex program and derives its dual. Conditional-entropy regularization yields Bellman-like equations with well-defined optimal solutions.

  • Convex formulation: The regularized MDP objective extends the average-reward linear-programming formulation by adding a convex regularization function weighted by η.The regularization parameter trades off the original objective and regularization.
  • Regularization choices: The framework studies negative Shannon entropy of the joint state-action distribution and conditional entropy as two regularization families.Their associated Bregman divergences are also used in the formulation.
  • Regularization choices: The Bregman divergence induced by conditional entropy is nonnegative, implying that conditional entropy is convex and its divergence is convex in its first argument.This convexity result extends beyond the special loop-free episodic setting.
  • Conditional-entropy duality: Using conditional-entropy divergence DC yields a dual problem closely resembling the average-reward Bellman optimality equations.The paper calls the resulting system the regularized average-reward Bellman optimality equations.
  • Conditional-entropy duality: The dual solution is well-defined, bounded, and unique up to a constant shift, with uniqueness obtainable by imposing zero expected value.Finiteness follows from maximizing a bounded function over a compact domain.

4. Dynamic programming in regularized MDPs

The paper develops dynamic-programming formulations for regularized average-reward MDPs and defines corresponding Bellman, optimality, and greedy-policy operators. These results support performance analysis and iterative algorithms based on Mirror Descent and Dual Averaging.

  • Regularized Bellman equations: The dynamic-programming treatment focuses on conditional-entropy regularization and introduces regularized Bellman equations for an arbitrary policy and reference policy.The regularized average reward appears in the policy-specific equations.
  • Regularized Bellman equations: The regularized Bellman system has a unique solution under the paper’s assumption when an additional zero-expected-value constraint is imposed.The same passage relates this result to the average-reward setting.
  • Operators and analysis: The framework defines a Bellman optimality operator and a greedy policy operator corresponding to the regularized Bellman equations and optimal policy expression.Formal definitions are provided in the appendix.
  • Operators and analysis: The paper provides a regularized counterpart to the performance-difference lemma for deriving approximate dynamic-programming algorithms.This result is presented as one of two tools useful for approximate dynamic programming.

5. Algorithms

The paper derives iterative entropy-regularized policy-optimization algorithms from a convex-programming framework, interpreting them through Mirror Descent and Dual Averaging. These interpretations clarify update mechanisms and convergence properties for REPS, DPP, TRPO, and entropy-regularized policy-gradient methods.

  • Iterative policy optimization: The framework studies two algorithmic families—Mirror Descent and Dual Averaging—to derive iterative updates for regularized MDP policies.The algorithms are developed assuming a fully known MDP, with unknown-environment evaluation considered later.
  • Mirror Descent with the relative entropy: REPS is formulated as Mirror Descent with relative-entropy Bregman divergence and converges to the optimal policy in the stated setup.The additive regularization used here differs from REPS’s constraint formulation only through the learning rate.
  • Mirror Descent with the conditional entropy: DPP performs one regularized value-iteration step by extracting a regularized greedy policy and applying the corresponding Bellman optimality operator.The convergence guarantees of Azar et al. support this approximate update.
  • Mirror Descent with the conditional entropy: TRPO performs one policy-iteration step: it evaluates the current policy and then extracts a regularized greedy policy using the current policy as baseline.Its objective approximates Mirror Descent by ignoring the effect of policy changes on the state distribution.
  • Mirror Descent with the conditional entropy: TRPO’s exact update is equivalent to MDP-E and therefore converges to the optimal policy in the stationary setting, strengthening earlier monotonic-improvement guarantees.The earlier guarantee allowed convergence to a suboptimal policy, whereas the equivalence supplies convergence to the optimum.
  • Dual Averaging with the conditional entropy: The entropy-regularized policy-gradient objective associated with A3C is non-convex and changes between iterations, so gradient descent may fail to converge to a stationary point.The non-convexity can also cause premature convergence to a bad local optimum.
  • Dual Averaging with the conditional entropy: Directly optimizing the convex regularized objective through Dual Averaging is guaranteed to converge to the optimal policy.The paper presents this as an alternative to gradient descent on the changing policy-gradient objective.

6. Experiments

The experiments evaluate entropy-regularized algorithms on a simple incrementally learned grid MDP, showing that regularization strength and update design strongly affect discovery and exploitation of the optimal path.

  • Experimental scope: The empirical comparison focuses on regularization and excludes approximation error other than model estimation, so it may not extend to other variants or approximation sources.
  • Experimental setup: The experiment challenges algorithms to discover the top-right reward path while incrementally learning dynamics, then exploit it.
  • Regularization strength: Very small η causes poor performance, whereas very large η leads to premature convergence to a greedy policy exploiting the intermediate reward.
  • Regularization strength: At intermediate η, most algorithms occasionally discover and exploit the optimal path, but RegVI never obtains the optimal policy.The results indicate that fixed η and a fixed reference policy are a poor choice in this MDP.
  • Algorithm comparison: Dual Averaging methods perform similarly and are generally slightly better than the approximate Mirror Descent variants.
  • Algorithm comparison: TRPO tends to converge faster than DPP to a locally optimal policy because DPP uses only one value update per iteration.The experiments also consider modified regularized Policy Iteration with more value updates.

7. Conclusion

The conclusion presents a convex-optimization framework that unifies entropy-regularized MDP algorithms and supports both theoretical justification and identification of algorithmic problems. It also states that the statistical value of entropy regularization for exploration remains unresolved.

  • The paper presents a unifying convex-optimization view of entropy-regularized MDPs.
  • This framework theoretically justifies state-of-the-art reinforcement-learning algorithms and highlights potential problems with heuristic methods.
  • The framework may support constructing more advanced reinforcement-learning algorithms by borrowing methods from convex optimization.The conclusion names Composite Objective Mirror Descent and Regularized Dual Averaging as examples.
  • The paper does not provide a statistical justification for entropy regularization, and whether it provably improves exploration remains open.

Appendix A. Complementary Technical Results

The appendix establishes convexity of the negative conditional-entropy regularizer by analyzing its Bregman divergence, which becomes an average relative entropy between conditional policies.

  • Conditional entropy: The joint state-action distribution μ induces a stationary state distribution ν_μ and conditional policy π_μ(a|x).
  • Conditional entropy: The appendix studies the negative conditional entropy of (X, A) sampled from μ as a function of μ.
  • Convexity proof: The corresponding Bregman divergence is analyzed to establish nonnegativity and thereby prove convexity of the regularizer.
  • Convexity proof: The Bregman divergence coincides with the average relative entropy between the conditional policies π_μ and π_μ′.Because it is a sum of nonnegative terms, the divergence is nonnegative on the state-action simplex.

A.2. Derivation of optimal policies

The derivation forms a Lagrangian for the constrained regularized MDP, applies stationary conditions to obtain optimal distributions and policies, and reduces the problem to dual optimization over value-related variables.

  • Generic dual derivation: The primal problem optimizes a regularized objective over stationary distributions satisfying feasibility constraints.
  • Support assumptions: The derivation assumes positive reference support and, for zero reference mass, assigns zero mass to the corresponding optimal state-action pairs.
  • Generic dual derivation: The Lagrangian uses value, average-reward, and inequality-constraint multipliers, with the advantage function defined relative to the value variables.
  • Generic dual derivation: Setting the Lagrangian gradient to zero yields the stationary system that characterizes the unique optimal solution for the regularized problem.
  • Conditional-policy regularization: For conditional-policy regularization, the optimal policy is obtained from the reference policy through an exponentiated advantage update involving λ and inequality multipliers.
  • Dual reduction: Nonnegativity makes the inequality multipliers vanish by complementary slackness, after which the dual is optimized over value variables only.
  • State-action regularization: For the state-action regularizer, the optimal distribution has the form μ′(x,a) exp(ηA(x,a)) after the dual constraints are handled.
  • Dual reduction: The optimal stationary state distribution is not required to solve the dual or compute the optimal policy.

Appendix B. The regularized Bellman operators

The appendix defines regularized Bellman operators and iteration procedures relative to a baseline policy. It establishes non-expansion, fixed-point existence, and convergence under boundedness and full-support conditions.

  • The regularized Bellman operator Tπ|π′ is defined for policy π with regularization relative to baseline π′.
  • The regularized Bellman optimality operator T∗|π′ and its associated greedy policy define regularized value and policy iteration procedures.Relative-value iteration uses a normalization δk+1, while policy iteration defines δk+1 analogously.
  • The required operator non-expansion result is established using a direct proof and an analogous complementary inequality.
  • Continuity implies that T∗|π′ has a fixed point by Brouwer’s fixed-point theorem, allowing value iteration to be treated as generalized value iteration.
  • Regularized value iteration converges to the fixed point of T∗|π′ when the initial value function is bounded and iterates remain bounded.
  • Assuming the initial reference policy has full support, every policy iterate retains full support, enabling convergence arguments for regularized value iteration.The update can assign zero probability only through an initially zero probability or an unbounded value iterate.

B.1. The proof of Lemma 3

This section derives results for regularized average-reward policy gradients and the TRPO update. It shows how TRPO’s surrogate-based update becomes a closed-form regularized greedy step relative to the previous policy.

  • The gradient of the regularized average reward is derived for a parameterized policy πθ using stationary-distribution arguments.
  • State-dependent constants can be added to the gradient multiplier because policy probabilities sum to one for each state.
  • TRPO replaces the regularized average-reward objective with a surrogate that approximates the effect of changing the policy on the stationary distribution.
  • The TRPO policy update has a closed-form expression equivalent to a regularized greedy step with respect to the previous policy’s value function.
  • The closed-form update is connected to a well-known identity stated as Lemma 3.
Loading 1705.07798v1…