PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPs

Lior Shani, Yonathan Efroni, Shie Mannor

arXiv:1909.02769v2cs.LGmath.OCstat.ML

TL;DR

TRPO has been treated as a heuristic despite limited convergence guarantees. This paper analyzes its adaptive proximity mechanism through convex-analysis trust-region ideas in planning and sample-based settings, showing global convergence and faster rates for regularized MDPs.

  • Problem

    TRPO is popular but has limited convergence guarantees, and finite-sample analyses had not demonstrated faster rates from regularization in MDPs.

  • Method

    The paper analyzes adaptive TRPO through mirror-descent-style Bregman geometry in planning and sample-based tabular discounted MDPs.

  • Results

    Sample-Based TRPO achieves global convergence at ˜O(1/√N) and regularized MDPs achieve ˜O(1/N), while its best policy in hindsight improves and its asymptotic performance matches CPI.

  • Takeaways & Limitations

    NE-TRPO is supported as a viable alternative to CPI rather than an approximate heuristic, with better sample-complexity dependence on (1−γ)^−1.

  • Takeaways & Limitations

    The regularization results address optimization only, leaving broader positive and negative implications of regularization in RL for future work.

Abstract

from arXiv · show

Trust region policy optimization (TRPO) is a popular and empirically successful policy search algorithm in Reinforcement Learning (RL) in which a surrogate problem, that restricts consecutive policies to be 'close' to one another, is iteratively solved. Nevertheless, TRPO has been considered a heuristic algorithm inspired by Conservative Policy Iteration (CPI). We show that the adaptive scaling mechanism used in TRPO is in fact the natural "RL version" of traditional trust-region methods from convex analysis. We first analyze TRPO in the planning setting, in which we have access to the model and the entire state space. Then, we consider sample-based TRPO and establish $\tilde O(1/\sqrt{N})$ convergence rate to the global optimum. Importantly, the adaptive scaling mechanism allows us to analyze TRPO in regularized MDPs for which we prove fast rates of $\tilde O(1/N)$, much like results in convex optimization. This is the first result in RL of better rates when regularizing the instantaneous cost or reward.

1 Introduction

The paper addresses limited convergence guarantees for TRPO by interpreting its adaptive proximity term as a principled trust-region mechanism rooted in convex analysis. It analyzes planning and sample-based variants, including regularized MDPs.

  • TRPO in reinforcement learning: RL trust-region methods iteratively combine a linearized objective with a proximity term that keeps consecutive policies close.This connects TRPO to mirror descent and trust-region optimization.
  • TRPO in reinforcement learning: TRPO has been widely used despite limited understanding of its convergence guarantees and its treatment as a heuristic.
  • Research question: The paper asks what form the proximity term should take in trust-region methods for RL.
  • Adaptive TRPO: Adaptive TRPO interprets the policy-dependent proximity term as a natural RL analogue of traditional convex trust-region methods.The method is analyzed through NE-TRPO and Projected Policy Gradient.
  • Main results: Sample-based TRPO obtains a ˜O(1/√N) convergence rate to the global optimum, while regularized MDPs admit a faster ˜O(1/N) rate.The faster regularized rate is presented as the first such evidence in RL.

2 Mirror Descent in Convex Optimization

Mirror descent is a first-order trust-region method that combines objective linearization with a Bregman-distance proximity term. Regularization can improve convergence from ˜O(1/N) to ˜O(1/N) in the stated convex-optimization results, while biasing the solution.

  • Mirror descent: Mirror descent minimizes a linear approximation of a convex objective together with a Bregman-distance term keeping iterates close.The update uses the gradient at the current iterate and a stepsize.
  • Convergence: ˜O(1/N) is the stated convergence rate for mirror descent in the general convex case.
  • Convergence: ˜O(1/N) is the improved rate stated for functions that are strongly convex with respect to the Bregman distance.
  • Regularization: Regularizing with a strongly convex function can enable faster convergence but adds bias to the solution of the unregularized problem.Setting λ = 0 returns to the unregularized convex case.
  • Choices of distance: In the Euclidean case, mirror descent becomes projected gradient descent with an orthogonal projection onto the convex set.
  • Choices of distance: With negative entropy, the Bregman distance is the Kullback–Leibler divergence and mirror descent becomes exponentiated gradient descent with a closed-form solution.

3 Preliminaries and Notations

The paper studies finite tabular discounted MDPs with stationary policies, defines regularized costs and value operators, and distinguishes full-state planning from scalar sample-based objectives.

  • MDP setting: The setting is an infinite-horizon discounted MDP with finite state and action sets, transition kernel P, bounded costs, and discount factor γ ∈ (0, 1).
  • Policy evaluation: A policy’s value is represented through discounted costs and the transition matrix induced by its stationary policy.The value satisfies the resolvent form (I − γP^π)^−1c^π.
  • Bellman operators: Policy optimization uses policy-evaluation and optimal Bellman operators, both γ-contractions whose fixed points are v^π and v*.
  • Regularized MDPs: Euclidean and negative-entropy choices define the regularization geometry and yield distinct bounds on the regularized cost.The negative-entropy choice uses H(π(· | s)) + log A.
  • Sample-based objectives: When the state space is large, full-state dynamic programming is computationally infeasible, motivating a scalar objective that averages policy values under a state-space measure μ.

4 Linear Approximation of a Policy’s Value

The paper derives a closed-form linear approximation of a policy’s value for regularized MDPs and uses discounted visitation frequencies to choose TRPO’s adaptive proximity scaling.

  • The analysis studies the directional derivative of the objective over the convex set of policies.This linear approximation is the key bridge between mirror-descent analysis and MDP policy optimization.
  • A closed-form expression is provided for the linear approximation of a policy’s value.The result is stated as Proposition 1 for policies π and π′.
  • The proposition’s proof applies a Policy Gradient Theorem derived for regularized MDPs.
  • The adaptive proximity scaling is chosen using the discounted visitation frequency induced by the current policy.This choice allows techniques from convex optimization to be used in the RL analysis.

5 Uniform Trust Region Policy Optimization

Uniform TRPO uses an adaptive Bregman-distance scaling to obtain simplified policy updates and convergence to the global optimum, with faster rates for regularized MDPs.

  • Uniform Trust Region Policy Optimization: Uniform TRPO is a trust-region planning algorithm with an adaptive proximity term for solving the policy optimization objective.Its PolicyUpdate procedure yields PPG and NE-TRPO as alternative instances.
  • Uniform Trust Region Policy Optimization: The adaptive Bregman-distance scaling makes the non-convex MDP analysis amenable to techniques from mirror descent and convex analysis.The resulting update rule is a direct consequence of this scaling choice.
  • Convergence rates: ˜O(1/N) convergence is established for regularized MDPs, while the unregularized case has the slower ˜O(1/√N) rate.The rates hold with a proper choice of learning rate.
  • Policy updates: The update simplifies from optimization over the full policy set to independent optimization over the action simplex for each state.This simplification follows because the adaptive transition operator is component-wise nonnegative.
  • Regularization: Regularization produces a biased solution: the regularized MDP’s optimal policy is not necessarily optimal when evaluated on the unregularized MDP.The trade-off is faster convergence for the regularized problem.
  • Sample-Based TRPO: Sample-Based TRPO relaxes access to the entire state space while retaining similar convergence rates in N.

6 Exact and Sample-Based TRPO

The paper develops exact and sample-based adaptive TRPO variants for scalar policy objectives, connecting their updates to mirror-descent-style adaptive proximal steps. Both obtain global convergence guarantees, with faster rates under regularization.

  • Exact TRPO: Exact TRPO adapts Uniform TRPO to the scalar objective and uses the ν-restart distribution in its linearized term.Its adaptive Bregman scaling depends on ν and the current policy.
  • Sample-Based TRPO: Sample-Based TRPO replaces full-state access with sampled trajectories from a ν-restart model while retaining an adaptive proximal update.Its proximal objective is an unbiased-in-expectation counterpart of Exact TRPO’s objective.
  • Sample-Based TRPO: Sample-Based TRPO performs optimization only on states visited during each episode, unlike exact methods that update all relevant states.The adaptive scaling makes this state-local update possible.
  • Convergence guarantees: ˜O(1/√N) and ˜O(1/N) are the convergence rates for unregularized and regularized cases, respectively.The sample-based method converges to an approximate solution, similarly to CPI.
  • Sample complexity: Sample-Based TRPO has better polynomial sample complexity in (1−γ)^−1 than CPI, while regularized versions have superior dependence on ǫ.The comparison uses the best policy so far for TRPO and the last policy for CPI.
  • Optimization perspective: PPG and NE-TRPO instantiate sample-based projected and exponentiated gradient descent methods for solving MDPs.The analysis does not rely on improvement arguments or early stopping, yet asymptotic performance is equivalent to CPI.

7 Related Works

The related-work discussion positions this paper as a tabular, trust-region analysis with global guarantees and regularization-dependent rates, distinguishing it from prior gradient, approximate, and neural-network approaches.

  • Policy-search analyses: Prior gradient-based policy-search analyses mainly establish local-optimum convergence under varying conditions, whereas this work studies trust-region policy search in tabular RL with global guarantees.
  • Regularized MDPs: Earlier entropy-regularized MDP work supplied no convergence rates, unlike this paper.
  • Approximate policy iteration: Approximate policy-iteration analyses using MD-like updates require uniform state access and can incur a worse concentrability coefficient than Cπ∗.That coefficient can be infinite even when Cπ∗ is finite.
  • Projected policy gradients: A prior projected-policy-gradient analysis depends on both S and Cπ∗, while Exact TRPO’s rate does not depend on either quantity.
  • Neural-network analysis: A neural-network TRPO variant reported O(ǫ^−8) sample complexity, compared with O(ǫ^−4) obtained here when other factors are neglected.

8 Conclusions and Future Work

The paper analyzes Uniform and Sample-Based TRPO through two adaptive-proximity instances and establishes global convergence, faster regularized rates, and favorable comparisons with CPI.

  • Contributions: PPG and NE-TRPO are the two analyzed instances of Uniform and Sample-Based TRPO.
  • Convergence results: ˜O(1/√N) convergence to the global optimum is established for both instances, with a faster ˜O(1/N) rate for regularized MDPs.
  • Comparison with CPI: Sample-Based TRPO’s best policy in hindsight improves, although its policy sequence need not be improving as in CPI.
  • Comparison with CPI: Sample-Based TRPO matches CPI asymptotically and has better dependence on (1−γ)^−1 in sample complexity.
  • Future work: Future work includes seeking linear convergence or proving its impossibility, and studying regularization beyond optimization.

List of Appendices

The appendices supply convex-analytic assumptions, extended value-function machinery for off-simplex arguments, and fixed-point properties supporting the TRPO analysis.

  • Convex-analytic assumptions: The Bregman-distance assumptions require ω to be proper, closed, convex, and differentiable over dom(∂ω).The optimal set of the optimization problem is also assumed nonempty.
  • Bregman distances: Negative entropy yields KL divergence, while one-half the squared Euclidean norm yields Euclidean distance on the state-wise action simplex.
  • Optimization domain: The optimization domain is enforced by an extended-real indicator that equals 0 inside C and ∞ outside C.
  • Regularized policy gradients: The appendix re-derives the regularized tabular policy-gradient theorem and its directional derivative using extended value functions for off-simplex arguments.
  • Definitions: The extended value and q functions generalize standard RL quantities to y∈R^{S×A}, with notation adjusted for the generalized discussion.
  • Extended Bellman operators: For y sufficiently close to the simplex component-wise, the operator T_y is a max-norm contraction with fixed point v(y).The fixed point satisfies v_s(y)=(T_yv(y))_s.

B.2 Policy Gradient Theorem for Regularized MDPs

The paper derives policy-gradient and directional-derivative tools for regularized MDPs, then uses them to formulate TRPO updates through linearized values and Bregman proximities. The analysis applies to both Euclidean and negative-entropy geometries, including non-convex objectives.

  • Policy Gradient Theorem: The regularized policy-gradient theorem is derived for tabular policies using extended value and q-functions.The derivation proceeds through fixed-point relations and discounted transition operators.
  • TRPO Update: TRPO minimizes a linear approximation of the policy value plus a Bregman proximity term around the current policy.The zeroth-order value term does not affect the minimizer, so the update depends on the directional derivative and proximity penalty.
  • Fundamental Inequality: Adaptive scaling yields a vector-valued fundamental inequality for the non-convex RL objective, replacing the usual convex gradient inequality with a directional-derivative argument.The inequality is statewise and combines Bregman-distance terms with regularization and step-size terms.
  • TRPO Update: Uniform TRPO admits Euclidean projected updates and negative-entropy non-Euclidean updates, the latter using KL divergence and a closed-form solution.The Euclidean geometry yields orthogonal projection, while negative entropy yields an analytic exponentiated-gradient-style update.
  • Assumptions and Bounds: The analysis relies on convexity and strong-convexity properties of the chosen Bregman distances even though the value objective itself is non-convex.The Euclidean and non-Euclidean cases use corresponding bounds on the regularizer and Bregman distance.

C.4 Proof of Theorem 2

The proof establishes policy improvement and convergence for Uniform TRPO, then connects Exact TRPO to the same update framework. Exact TRPO uses scalar objectives and a concentrability assumption to convert statewise guarantees into global guarantees.

  • Uniform TRPO Policy Improvement: Uniform TRPO improves the value at every iteration for both Euclidean and non-Euclidean variants and any λ ≥ 0.The result follows from the update optimality condition, the learning-rate choice, and non-negativity of the Bregman distance.
  • Uniform TRPO Convergence: The Uniform TRPO convergence theorem bounds the iterate sequence for all N ≥ 1.The proof uses the fundamental inequality, telescoping Bregman terms, policy improvement, and geometry-dependent bounds.
  • Exact TRPO Setup: Exact TRPO minimizes a scalar objective rather than a vector objective, which complicates the analysis and requires a finite concentrability coefficient.The coefficient connects the statewise update guarantee to the global objective under the optimal policy’s state distribution.
  • Exact TRPO Setup: Exact TRPO and Uniform TRPO are connected through their update rules, with Euclidean and negative-entropy choices corresponding to projected and NE-TRPO instances.The Exact TRPO update is solved component-wise using the same Euclidean and non-Euclidean policy-update procedures.
  • Exact TRPO Analysis: The Exact TRPO proof derives a scalar fundamental inequality from a statewise inequality and the concentrability assumption.This inequality then supports convergence-rate results for both unregularized and regularized Exact TRPO.

D.4 Convergence proof of Exact TRPO

The Exact TRPO analysis proves monotone policy improvement and derives convergence bounds from its statewise update inequality. The sample-based extension estimates the exact update from restart-model samples, while finite-trajectory estimation can introduce bias.

  • Policy Improvement: Exact TRPO improves the value for both Euclidean and non-Euclidean variants for any λ ≥ 0.The proof applies the Bregman three-point identity and handles both visited and unvisited states.
  • Convergence: The Exact TRPO convergence theorem provides bounds for the sequence generated by Exact TRPO for all N ≥ 1.The proof combines the fundamental inequality, telescoping sums, policy improvement, and Euclidean or non-Euclidean geometry bounds.
  • Sample-Based Extension: Sample-Based TRPO estimates Exact TRPO updates using samples from a ν-restart model instead of accessing the entire state space.Its expected update agrees with the exact update under an unbiased q-function estimation process.
  • Sample-Based Limitation: Finite-horizon trajectory truncation introduces bias into the estimator of qπk.The unbiased analysis assumes that sample trajectories are not truncated.
  • Sample-Based Update: The sample-based optimization decomposes statewise over visited states, while policies at unvisited states are kept unchanged.The implementation represents sampled state-action estimates with indicator functions and chooses πk+1(· | s) = πk(· | s) for unvisited states.

E.5 Approximation Error Bound

The analysis separates sample-based approximation error into sampling and trajectory-truncation components, then combines their bounds to establish convergence guarantees for Sample-Based TRPO.

  • Error decomposition: Sampling error arises from replacing expectations with empirical means over finite trajectories, while truncation error arises from finite trajectory lengths.The analysis treats unbiased full-trajectory estimation first, then accounts for truncation-induced bias.
  • Unbiased sampling: The unbiased q-function estimator uses full trajectory unrolling and is analyzed using concentration bounds over deterministic policies.Hoeffding’s inequality and a union bound control empirical deviations uniformly over the policy space.
  • Truncated sampling: Finite trajectory truncation makes the estimator biased, with separate contributions from truncated state sampling and truncated q-function estimation.The resulting bias is controlled by choosing a sufficiently large trajectory length T.
  • Combined bound: The combined approximation-error lemma incorporates both finite-sampling error and truncation bias for Sample-Based TRPO.The required trajectory count in each iteration is selected to make the approximation error proportional to the target tolerance.
  • Convergence theorem: Sample-Based TRPO proves convergence for the best policy in hindsight because the analysis lacks the improvement guarantees used for exact TRPO.The resulting theorem is stated with high probability over the sampling process.

F Useful Lemmas

The useful lemmas bound regularized Bellman quantities, policy-update terms, and gradient changes for exact and sample-based TRPO in Euclidean and non-Euclidean settings.

  • Regularized Bellman bounds: The regularized Bellman operator is connected to the q-function through bounds expressed using the action-space dual norm.The dual norm is L1 in the Euclidean case and L∞ in the non-Euclidean case.
  • Exact and uniform updates: Uniform and Exact TRPO updates satisfy bounds on their relevant q-function and Bregman-gradient terms in both geometries.These bounds support the convergence analysis by controlling update magnitudes across iterations.
  • Entropy-gradient behavior: In the non-Euclidean case, entropy gradients are unbounded near deterministic policies, but their growth is bounded logarithmically so determinism is reached only after infinite time.This behavior is stated for both exact and sample-based analyses.
  • Sample-based updates: Sample-Based TRPO obeys analogous update bounds, with an additional A factor introduced by importance sampling in the q-function approximation.The sample-based bounds apply to states visited during the iteration.
  • Gradient changes: The technical lemmas also bound the change in the Bregman-generating-function gradient between consecutive sample-based policies.The bound follows from first-order optimality and the update inequalities.

G Useful Lemmas from Convex Analysis

This section invokes standard convex-analysis results for Bregman distances and non-Euclidean proximal updates, under convexity and strong-convexity assumptions.

  • Three-points lemma: The three-points lemma expresses an inner product of gradient differences as a signed combination of three Bregman distances.It applies when the generating function is proper, closed, convex, and differentiable on the relevant domain.
  • Second prox theorem: The non-Euclidean second prox theorem requires convexity of the generating function and auxiliary function, compatible domains, and strong convexity of the constrained generator.The stated strong-convexity parameter satisfies σ > 0.
Loading 1909.02769v2…