PaperlayerView exact revision on arXiv

Source-linked AI summary

Trust Region Policy Optimization

John Schulman, Sergey Levine, Philipp Moritz, Michael I. Jordan, Pieter Abbeel

arXiv:1502.05477v5cs.LG

TL;DR

Gradient-based policy optimization has struggled to consistently outperform gradient-free search, especially for challenging control problems. TRPO develops a theoretically grounded trust-region procedure with practical approximations and achieves monotonic improvement across robotic locomotion and Atari tasks, with little hyperparameter tuning.

  • Problem

    Gradient-based policy methods have not consistently outperformed gradient-free search, despite stronger sample-complexity guarantees for challenging control problems.

  • Method

    TRPO proves monotonic improvement for trust-region policy updates, then approximates the procedure into scalable single-path and vine algorithms for nonlinear stochastic policies.

  • Results

    TRPO learned neural-network controllers for swimming, walking, and hopping and convolutional policies from raw Atari images, outperforming prior methods across challenging tasks.

  • Takeaways & Limitations

    TRPO provides a scalable, theoretically grounded approach that empirically succeeds on high-dimensional robotic control and image-based game-playing tasks.

  • Takeaways & Limitations

    The theoretical bound initially applies only to restrictive mixture policies, so practical updates must extend beyond that policy class.

Abstract

from arXiv · show

We describe an iterative procedure for optimizing policies, with guaranteed monotonic improvement. By making several approximations to the theoretically-justified procedure, we develop a practical algorithm, called Trust Region Policy Optimization (TRPO). This algorithm is similar to natural policy gradient methods and is effective for optimizing large nonlinear policies such as neural networks. Our experiments demonstrate its robust performance on a wide variety of tasks: learning simulated robotic swimming, hopping, and walking gaits; and playing Atari games using images of the screen as input. Despite its approximations that deviate from the theory, TRPO tends to give monotonic improvement, with little tuning of hyperparameters.

1 Introduction

The introduction situates policy optimization among policy iteration, policy gradient, and derivative-free stochastic methods, noting the practical appeal of simple derivative-free approaches and challenges for ADP and gradient-based methods. It then presents TRPO as a practical approximation to a theoretically justified policy-improvement procedure and introduces single-path and vine variants.

  • Background: Policy optimization algorithms fall into three broad categories: policy iteration, policy gradient, and derivative-free stochastic optimization methods.Policy iteration alternates value estimation and policy improvement, while policy gradient methods estimate expected-return gradients from sample trajectories.
  • Motivation: Derivative-free methods such as CEM and CMA are preferred on many problems because they achieve good results while remaining simple to understand and implement.The passage gives Tetris and continuous-control settings as examples motivating this preference.
  • Motivation: ADP and gradient-based methods are described as unable to consistently match stochastic optimization methods, while CMA has succeeded on challenging locomotion tasks with hand-engineered, low-dimensional policy classes.The passage specifically identifies Tetris as a benchmark where stochastic optimization methods are difficult to beat.
  • Contribution: The authors first prove that minimizing a surrogate objective guarantees policy improvement with non-trivial step sizes, then approximate this procedure to derive TRPO.TRPO is presented as the resulting practical algorithm.
  • Contribution: TRPO includes a single-path variant for model-free settings and a vine variant that requires the system to be restored to previously visited states.The supplied passage truncates the description after stating that the vine method requires state restoration.

2 Preliminaries

This section formalizes discounted MDPs, policies, value functions, and advantage-based policy improvement. It motivates local policy updates by showing their first-order connection to performance while highlighting the difficulty of choosing safe step sizes and the limitations of mixture-policy guarantees.

  • MDP and policy definitions: An infinite-horizon discounted MDP is specified by finite state and action sets, transitions, rewards, an initial-state distribution, and discount factor γ ∈(0, 1).Policies stochastically select actions, generating trajectories from the initial-state distribution through the policy and transition dynamics.
  • Value and advantage functions: The expected return η(π) is analyzed using the standard state-action value, value, and advantage functions.These quantities provide the basis for expressing another policy’s performance through advantages accumulated along its trajectories.
  • Policy improvement: A policy update is guaranteed to improve or preserve η when its expected advantage is nonnegative at every state.Exact policy iteration chooses the action maximizing the current policy’s advantage and improves whenever a positively advantageous, visited state-action pair exists.
  • Approximate policy updates: Approximate updates can have negative expected advantage in some states, while the changed policy’s visitation frequencies make direct optimization difficult.The local surrogate uses the current policy’s visitation frequencies instead of those of the updated policy, and matches η to first order for differentiable parameterized policies.
  • Safe update motivation: A sufficiently small step that improves the local surrogate also improves η, but the first-order result does not determine an appropriate step size.Conservative policy iteration supplies explicit improvement lower bounds, yet its mixture-policy class is restrictive and does not cover general stochastic policies conveniently.

3 Monotonic Improvement Guarantee for General Stochastic Policies

The paper extends the policy improvement bound to general stochastic policies using total variation distance, then derives an iteration scheme whose true objective is guaranteed to be non-decreasing. TRPO approximates this scheme by constraining KL divergence rather than using a penalty, enabling robustly large updates.

  • General stochastic policies: The policy improvement bound extends from mixture policies to general stochastic policies by replacing α with a distance between π and ˜π and adjusting ϵ.The chosen distance is total variation divergence.
  • Divergence bounds: Total variation divergence is related to KL divergence through DT V (p ∥q)2 ≤DKL(p ∥q), yielding a KL-based policy improvement bound.The bound uses the maximum statewise KL divergence between policies.
  • Monotonic improvement: Algorithm 1 maximizes a surrogate lower bound at each iteration, guaranteeing a monotonically improving sequence η(π0) ≤η(π1) ≤η(π2) ≤. . . .The guarantee assumes exact evaluation of the advantage values Aπ.
  • Optimization interpretation: The update procedure is a minorization-maximization algorithm whose surrogate minorizes η and equals it at the current policy.It is also reminiscent of proximal gradient methods and mirror descent.
  • Connection to TRPO: TRPO approximates Algorithm 1 by imposing a KL-divergence constraint rather than a penalty to robustly permit large policy updates.This approximation is introduced in the following section.

4 Optimization of Parameterized Policies

This section derives a practical optimization procedure for parameterized policies from theoretical foundations under finite samples and arbitrary parameterizations. It replaces impractically small penalty-based or statewise KL-constrained updates with a tractable average-KL constrained policy update.

  • Parameterized policies: The method adapts the theoretical policy-optimization formulation to parameterized policies πθ under finite sample counts and arbitrary parameterizations.The previous policy parameters are denoted θold, and objective, surrogate, and KL-divergence notation is expressed as functions of θ.
  • Trust-region update: Maximizing the constrained surrogate is guaranteed to improve the true objective under the stated KL-based formulation.The guarantee holds with equality at θ = θold.
  • Trust-region update: The theoretically motivated penalty coefficient would produce very small step sizes, motivating a trust-region constraint on KL divergence between new and old policies.The constraint is intended to enable larger steps robustly.
  • Average-KL approximation: A statewise KL-divergence constraint is impractical because it imposes a large number of constraints across the state space.The section therefore introduces a heuristic approximation based on average KL divergence.
  • Average-KL approximation: The proposed policy update solves an optimization problem using the average-KL trust-region approximation.Experiments later show similar empirical performance to the maximum KL divergence constraint in Equation (11).

5 Sample-Based Estimation of the Objective and Constraint

This section develops Monte Carlo estimators for the surrogate objective and its KL-divergence constraint, using sample averages and empirical Q-values. It presents single-path and vine sampling schemes, with vine reducing estimator variance at the cost of substantially more simulator calls.

  • Sample-Based Estimation: The objective and constraint are approximated through Monte Carlo simulation, replacing expectations with sample averages and Q-values with empirical estimates.The constrained optimization retains the expected-reward objective and per-update policy-change constraint.
  • Objective Estimation: The surrogate objective uses importance sampling after replacing discounted state visitation expectations with samples and advantage values with Q-values.Replacing advantages by Q-values changes the objective only by a constant.
  • Constraint Estimation: The constraint is an expected KL-divergence bound, Es∼ρθold [DKL(πθold(·|s) ∥πθ(·|s))] ≤δ.It limits the policy change at each update.
  • Sampling Schemes: Single-path sampling estimates Qθold from discounted future rewards along trajectories, while vine sampling branches from a rollout set using multiple actions per state.Vine rollouts can use common random numbers to reduce variance in Q-value differences.
  • Sampling Schemes: Vine sampling yields much lower variance than single-path sampling for the same number of Q-value samples, but requires far more simulator calls.The method therefore provides better advantage estimates with higher simulation cost.

6 Practical Algorithm

The practical algorithms collect sampled state-action pairs and Monte Carlo Q-values, construct estimated optimization terms, and update policy parameters through constrained optimization. They use an analytically computed Fisher information matrix and replace difficult penalty or maximum-KL formulations with tractable hard constraints.

  • Algorithm procedure: The algorithms repeatedly collect state-action pairs with Monte Carlo Q-value estimates, then construct estimated objectives and constraints from samples.They use either single-path or vine sampling procedures.
  • Algorithm procedure: Policy parameters θ are updated by approximately solving the constrained problem with conjugate gradient followed by line search.This procedure is only slightly more expensive than computing the gradient itself.
  • Fisher information matrix: The Fisher information matrix is computed analytically from the KL-divergence Hessian rather than from gradient covariance.The analytic estimator integrates over actions at each state and does not depend on the sampled action.
  • Fisher information matrix: The analytic Fisher estimator removes the need to store a dense Hessian or all policy gradients from trajectory batches while achieving a similar policy-improvement rate to the empirical FIM.These computational benefits matter in large-scale settings.
  • Theory-to-practice changes: The practical method replaces a penalty on KL divergence with a hard constraint δ because large penalty coefficients produce prohibitively small steps and are difficult to choose robustly.It also constrains DKL(θold, θ) instead of the harder-to-optimize and estimate Dmax KL(θold, θ).

7 Connections with Prior Work

TRPO’s policy update provides a unifying perspective on several prior policy-update methods. Natural policy gradient, standard policy gradient, and policy iteration emerge from specific approximations or constraint choices, while TRPO’s enforced constraint distinguishes it from related KL-constrained approaches.

  • Connections with Prior Work: Natural policy gradient is a special case of TRPO’s update using linear L and quadratic DKL approximations.This yields the natural policy-gradient problem described in the paper.
  • Connections with Prior Work: TRPO enforces its divergence constraint at every update, unlike approaches that treat λ as an algorithm parameter.Experiments show this difference significantly improves performance on larger problems.
  • Connections with Prior Work: The standard policy-gradient update follows from using an ℓ2 constraint or penalty.The paper presents this as another special case of the general update framework.
  • Connections with Prior Work: Policy iteration follows by solving the unconstrained problem maximize_π L_πold(π), with L defined as in Equation (3).This connects the policy-iteration update directly to the paper’s surrogate objective.
  • Connections with Prior Work: REPS constrains state-action marginals p(s, a), whereas TRPO constrains conditionals p(a|s) and avoids REPS’s costly nonlinear inner-loop optimization.Levine and Abbeel also use a KL constraint, but for keeping policies near regions where their estimated dynamics model is valid.

8 Experiments

The experiments compare TRPO variants and baselines on sampling, step-size selection, locomotion, and Atari tasks. Single-path and vine TRPO solve challenging locomotion problems and produce competitive vision-based Atari results, with KL-constrained updates supporting robust progress.

  • Locomotion: Single-path and vine TRPO solved all locomotion problems and yielded the best solutions across five-run learning curves.Natural gradient handled easier tasks but failed to produce forward-progressing hopping and walking gaits.
  • Algorithm comparisons: KL-divergence constraints provided more robust step-size selection and faster, more consistent progress than a fixed penalty coefficient.The comparison specifically contrasts TRPO’s KL-divergence constraint with natural gradient’s fixed penalty coefficient.
  • Locomotion: CEM and CMA performed poorly on larger locomotion problems because their derivative-free sample complexity scales unfavorably with parameter count.The max-KL method learned somewhat more slowly, while average KL produced a similar overall effect to the theoretically justified maximum-KL constraint.
  • Locomotion: TRPO learned all locomotion gaits using general-purpose policies, simple reward functions, minimal prior knowledge, and no hand-architected locomotion policy classes.The tasks included underactuated, high-dimensional, contact-rich simulated robots, making them challenging.
  • Atari: On Atari, single-path and vine TRPO were evaluated on seven games from raw images using a 33,500-parameter convolutional policy, with 500 iterations taking about 30 hours on a 16-core computer.The results outperformed prior methods on some games, while performance varied substantially across random initializations.

9 Discussion

The paper establishes trust-region policy optimization as a theoretically grounded approach with monotonic-improvement guarantees and strong empirical performance. Experiments demonstrate its breadth across robotic locomotion and image-based game playing, motivating future work on large, rich function approximators.

  • Core contribution: Trust-region methods combine local expected-return optimization with a KL divergence penalty or constraint, yielding monotonic improvement theoretically and strong empirical results across challenging policy-learning tasks.The constrained approximation outperformed prior methods.
  • Robotic locomotion: Robotic controllers learned swimming, walking, and hopping in simulation using general-purpose neural networks and minimally informative rewards.The authors report no prior work had learned all three tasks from scratch with a generic policy-search method and non-engineered policy representations.
  • Game playing: Convolutional neural-network policies learned to play games from raw images despite requiring optimization of extremely high-dimensional policies.Only two prior methods reportedly achieved successful results on this task.
  • Future work: The method’s scalability and theoretical foundations motivate future training of large, rich function approximators for challenging problems.A proposed direction is robotic controllers that use vision and raw sensory data to combine perception and control.

A Proof of Policy Improvement Bound

The proof decomposes policy-performance differences into per-timestep advantages, then uses coupled trajectories to bound the discrepancy between η(˜π) and Lπ(˜π). It finally replaces the coupling parameter with a bound on total variation divergence between the policies.

  • Performance decomposition: Policy-performance difference η(˜π)−η(π) decomposes into a sum of per-timestep advantages.The expectation is taken over trajectories generated by ˜π.
  • Policy coupling: An α-coupled policy pair jointly samples actions so that π and ˜π disagree with probability at most α at each state.Equivalently, the policies agree with probability at least 1−α.
  • Trajectory coupling: Coupling induces paired trajectories, allowing the proof to separate timestep-t advantage expectations according to whether earlier actions disagree.The proof tracks nt, the number of disagreements before timestep t, and uses P(nt=0)≥(1−α)^t.
  • Surrogate-loss bound: Summing the per-timestep bounds controls the difference between η(˜π) and Lπ(˜π), using ϵ=maxs,a |Aπ(s,a)|.The bound is obtained after subtracting the corresponding performance and surrogate-loss expressions.
  • Total variation connection: Total variation divergence supplies the coupling parameter: distributions with DT V(pX∥pY)=α admit a joint distribution agreeing with probability 1−α.Thus, a uniform statewise TV bound yields an α-coupled policy pair with the policies as marginals.

B Perturbation Theory Proof of Policy Improvement Bound … D Approximating Factored Policies with Neural Networks

The appendices provide an alternative perturbation-theory proof of the policy-improvement bound and an efficient implementation of TRPO’s constrained optimization. They also explain Fisher-vector products and neural-network parameterizations for continuous and factored discrete policies.

  • B Perturbation Theory Proof of Policy Improvement Bound: Perturbation theory rewrites the policy-performance difference using resolvents of the two policies’ transition operators.The proof defines G and ˜G as discounted resolvents and sets ∆ = P˜π − Pπ.
  • B Perturbation Theory Proof of Policy Improvement Bound: The leading perturbation term uses the value function and discounted state distribution, while the O(∆2) term is bounded through total variation and ℓ1 operator norms.The derivation identifies rG with v and Gρ0 with ρπ, then uses ∥G∥1 = ∥˜G∥1 = 1/(1 −γ) and ∥∆∥1 = 2α.
  • C Efficiently Solving the Trust-Region Constrained Optimization Problem: TRPO approximately solves its constrained optimization by computing a search direction from linear and quadratic approximations, then line-searching to enforce nonlinear improvement and feasibility.The search direction approximately solves Ax = g, with A representing the Fisher information matrix and the quadratic KL constraint.
  • C Efficiently Solving the Trust-Region Constrained Optimization Problem: Conjugate gradients avoid explicitly forming the full Fisher matrix or its inverse by using matrix-vector products, and the maximal step length is determined from the quadratic KL constraint.For search direction s ≈ A−1g, the step uses β = 2δ/sT As, with sT As obtained by a Hessian-vector product.
  • C.1 Computing the Fisher-Vector Product: The Fisher information matrix factors as JT MJ, making Fisher-vector products computable as y → JT MJy using automatic differentiation and distribution-specific multiplication by M.The product can also be averaged over datapoints, while generic Hessian-vector products offer an easier but slightly less efficient alternative.
  • C.1 Computing the Fisher-Vector Product: 10 conjugate-gradient iterations were effective, but Fisher-vector products could consume more than 90% of computation before data subsampling reduced the burden.The passage states that higher k did not yield faster policy improvement and that each product costs about as much as computing the objective gradient.
  • D Approximating Factored Policies with Neural Networks: For continuous spaces, a dense neural network outputs Gaussian means with state-independent diagonal covariance and separately parameterized log standard deviations.The policy samples actions from p(a|µ), where the network maps state features to the Gaussian mean.
  • D Approximating Factored Policies with Neural Networks: For Atari’s factored discrete actions, a neural network applies softmax separately to each factor, producing normalized categorical probabilities whose concatenated parameters define µ.The action is a tuple of integer-valued components, and dim µ = PK k=1 Nk.

E Experiment Parameters · F Learning Curves for the Atari Domain

The paper specifies experiment parameters for continuous-control and Atari tasks, including vine and single-path algorithms. It also presents Atari learning curves, where plotted cost equals negative reward for historical reasons.

  • E Experiment Parameters: Table 2 lists parameters for continuous-control tasks using vine and single-path (SP) algorithms.
  • E Experiment Parameters: The continuous-control parameter table covers both vine and single-path (SP) algorithms.
  • E Experiment Parameters: Table 3 lists the parameters used for the Atari domain.
  • E Experiment Parameters: The Atari parameter table is presented separately from the continuous-control parameter table.
  • F Learning Curves for the Atari Domain: Figure 5 presents learning curves for the Atari domain.
  • F Learning Curves for the Atari Domain: The Atari plots use cost = negative reward for historical reasons.
Loading 1502.05477v5…