PaperlayerView exact revision on arXiv

Source-linked AI summary

Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policy

Boyi Liu, Qi Cai, Zhuoran Yang, Zhaoran Wang

arXiv:1906.10306v3cs.LGmath.OCstat.ML

TL;DR

PPO and TRPO have empirical success in deep reinforcement learning, but their global convergence is less understood amid nonconvexity and accumulating evaluation and improvement errors. This paper analyzes neural-network variants through infinite-dimensional mirror descent and proves convergence to the optimal policy at a sublinear rate.

  • Problem

    Despite empirical success, global convergence guarantees for PPO and TRPO with neural-network policy and action-value parametrizations remain unclear, as do convergence rates and the effects of those parametrizations.

    Source: §1 · p. 2

  • Method

    The authors model ideal policy updates as infinite-dimensional mirror descent under one-point monotonicity and analyze neural-network approximations to policy evaluation and improvement.

    Source: §3 · p. 7

  • Results

    O(1/K) convergence to the optimal policy is established for neural PPO, with O(1/ε^2) TD and SGD iterations sufficient for ε-accurate policy evaluation and improvement.

    Source: §1 · p. 3

  • Takeaways & Limitations

    With linear activations, the results cover classical linear function approximation, including the tabular setting.

    Source: §1 · p. 4

    Choosing the optimal penalty coefficient is difficult in practice, and line search is often needed.

    Source: §4.3 · p. 14

Abstract

from arXiv · show

Proximal policy optimization and trust region policy optimization (PPO and TRPO) with actor and critic parametrized by neural networks achieve significant empirical success in deep reinforcement learning. However, due to nonconvexity, the global convergence of PPO and TRPO remains less understood, which separates theory from practice. In this paper, we prove that a variant of PPO and TRPO equipped with overparametrized neural networks converges to the globally optimal policy at a sublinear rate. The key to our analysis is the global convergence of infinite-dimensional mirror descent under a notion of one-point monotonicity, where the gradient and iterate are instantiated by neural networks. In particular, the desirable representation power and optimization geometry induced by the overparametrization of such neural networks allow them to accurately approximate the infinite-dimensional gradient and iterate.

1 Introduction

The introduction addresses the gap between PPO and TRPO’s empirical success and limited global-convergence theory. It presents a neural-network variant with a nonasymptotic global convergence rate and an analysis that treats policy evaluation and improvement errors within a mirror-descent framework.

Motivation and analysis

  • The analysis addresses how neural-network TD evaluation and SGD policy improvement approximate ideal updates, while accounting for their errors compounding across PPO and TRPO iterations.Overparameterization supports global sublinear convergence of the MSBE and MSE errors to zero.Source: §1 · pp. 2–3

Contribution

  • The analysis covers variants of PPO and TRPO whose policy and action-value function use randomly initialized, overparametrized two-layer neural networks.With linear activations, the results also cover linear function approximation, including the tabular setting.Source: §1 · pp. 3–4
  • O(1/K) convergence to the optimal policy is established for neural PPO, with O(1/ε^2) TD and SGD iterations sufficient for the policy-evaluation and policy-improvement subproblems.The rate is for the number K of PPO iterations; the subproblem iteration bounds attain ε accuracy.Source: §1 · p. 3

Analysis

  • The authors frame ideal infinite-dimensional policy updates as mirror descent and use one-point monotonicity to establish convergence toward the optimal policy.The exact action-value function acts as the dual iterate and the ideal policy as the primal iterate.Source: §1 · p. 3

Related work

  • Neu et al. (2017) establish global convergence for TRPO with infinite-dimensional updates and exact action-value functions, whereas this work gives neural-network guarantees and nonasymptotic rates.The paper also gives iteration complexity for the policy-improvement and policy-evaluation subproblems.Source: §1 · p. 4

2 Background

The background specifies the reinforcement-learning setting and the policy quantities used to describe performance. It introduces PPO and TRPO updates, including their relationship and the KL-divergence convention used by the paper’s variants.

Markov Decision Process

  • The setting is a Markov decision process with compact state space, finite action space, transition kernel, reward function, and discount factor γ in (0, 1).Source: §2 · p. 5
  • A policy’s performance is tracked using its action-value function; the state-value function, advantage, and stationary state and state-action distributions are also defined.Source: §2 · p. 5

PPO and TRPO

  • PPO updates use an advantage estimator and a KL penalty, with the penalty parameter adjusted by line search in practice.Source: §2 · p. 5
  • The paper treats PPO as a Lagrangian relaxation of TRPO, with equivalent updates when the multiplier is chosen appropriately; its variants reverse the KL arguments relative to the originals.The authors focus on PPO and state that these variants, like the originals, allow approximate policy improvement using SGD and enjoy global convergence.Source: §2 · p. 6

3 Neural PPO

Neural PPO approximates policy improvement and policy evaluation with separate neural-network subproblems. It uses SGD for the policy and TD learning for the action-value function, then combines these steps into the algorithm analyzed in the next section.

Neural network parametrization

  • The policy and action-value function are represented by two-layer ReLU networks with fixed output weights and trainable input weights.The input weights are restricted to a ball around their random initialization.Source: §3 · p. 6

Policy Improvement

  • Policy improvement converts the objective into a least-squares subproblem for an energy-based policy that approximates the ideal infinite-dimensional update.Sampling actions from the auxiliary distribution is intended to approximate the ideal update evenly across actions and permits off-policy sampling.Source: §3 · p. 7

Policy Evaluation

  • Policy evaluation estimates the current policy’s action-value function by minimizing mean squared Bellman error with a neural network and a TD update.Source: §3 · p. 8

Neural PPO

  • Neural PPO assembles the policy-improvement SGD and policy-evaluation TD subproblems into one algorithm.The algorithm specifies the numbers of SGD, TD, and PPO iterations and applies the corresponding updates at each iteration.Source: §3 · p. 8

4 Main Results

The results analyze how neural-network policy-improvement and policy-evaluation errors affect PPO, then establish global convergence of neural PPO under stated regularity assumptions.

4 Main Results

  • The main-results analysis establishes global convergence by characterizing errors from solving policy-improvement and policy-evaluation subproblems.The stated analysis assumes bounded rewards and regularity conditions on the action-value function class and stationary distribution.Source: §4 · p. 9, §4.1 · p. 10

4.1 Errors of Policy Improvement and Policy Evaluation

  • With sufficiently large equal network widths, the policy-improvement and policy-evaluation errors decay at rate 1/T in the subproblem iterations.T is the number of TD and SGD iterations in Algorithm 1.Source: §4.1 · p. 11

4.2 Error Propagation

  • The error-propagation analysis quantifies how neural approximations to the action-value function and improved policy affect the ideal infinite-dimensional policy update.The paper identifies these propagation lemmas as key to establishing neural PPO’s global convergence.Source: §4.2 · pp. 12–13

4.3 Global Convergence of Neural PPO

  • Neural PPO globally converges toward the optimal policy under Assumptions 4.1, 4.3, and 4.4.The theorem’s bound includes accumulated policy-improvement and policy-evaluation errors, which may vary across problems.Source: §4.3 · pp. 13–14

5 Proof Sketch

The proof sketch casts neural PPO as infinite-dimensional mirror descent with primal and dual errors, using one-point monotonicity to establish global convergence. It also presents algorithms for policy improvement and policy evaluation.

5 Proof Sketch

  • The proof casts neural PPO as infinite-dimensional mirror descent with primal and dual errors and uses one-point monotonicity to establish global convergence.The argument combines mirror-descent analysis with a one-step KL-divergence descent result.Source: §5 · pp. 15–16
  • The performance difference lemma expresses L(π) − L(π∗) through an expectation involving Qπ and the difference between π and π∗.The expectation is taken under ν∗ and scaled by (1 − γ)^−1.Source: §5 · p. 15
  • One-point monotonicity restricts the policy comparison to the optimal policy, unlike classical monotonicity, which compares any pair of policies.The paper views Qπ as the gradient of L(π) and π as the primal iterate.Source: §5 · p. 15

A Algorithms in Section 3

  • Section 3 presents algorithms for solving the policy-improvement and policy-evaluation subproblems, respectively via SGD and TD.The listed procedures are titled “Policy Improvement via SGD” and “Policy Evaluation via TD.”Source: A Algorithms in Section 3 · p. 23

B Supplementary Lemma in Section 3

The supplementary lemma relates policy-improvement error to the distance between the computed and ideal improved policies. A small error makes those policies close, supporting the use of the policy-improvement subproblem.

B Supplementary Lemma in Section 3

  • The lemma quantifies policy-improvement error through the distance between policies induced by solving the policy-improvement subproblem.The subproblem is identified as (3.5).Source: B Supplementary Lemma in Section 3 · p. 23
  • When policy-improvement error εk+1 is small, the computed policy πθk+1 is close to the ideal improved policy bπk+1.The ideal policy is the comparison point for the lemma.Source: B Supplementary Lemma in Section 3 · p. 24
  • This closeness justifies solving the policy-improvement subproblem in (3.5) to obtain the improved policy.The lemma connects subproblem accuracy to proximity to the ideal update.Source: B Supplementary Lemma in Section 3 · p. 24

C Proof of Proposition 3.1

The proof of Proposition 3.1 formulates the policy-improvement subproblem and its Lagrangian before concluding the proposition.

C Proof of Proposition 3.1

D Proofs for Section 4.1

The analysis unifies SGD and TD through a meta-algorithm, then uses local linearization to analyze neural-network updates. It establishes a Lipschitz property for the network function and bounds linearization-related errors.

D Proofs for Section 4.1

  • The proof generalizes earlier analyses under a unified framework accounting for SGD and TD, which correspond to stochastic gradients and stochastic semigradients.The meta-algorithm recovers policy improvement with SGD and policy evaluation with TD under specified choices of its components.Source: D Proofs for Section 4.1 · pp. 25–26
  • The network function uα is 1-Lipschitz continuous with respect to α.Source: D Proofs for Section 4.1 · p. 26

D.1 Local Linearization

  • The analysis uses a local linearization at random initialization to show that the overparametrized network behaves similarly to that linearization.The proof section then establishes global convergence of the meta-algorithm, implying global convergence of SGD and TD.Source: D Proofs for Section 4.1 · p. 26, §D.1 · p. 26
  • The local-linearization analysis bounds discrepancy terms using the network width m and the parameter displacement bound R_u.The supplied proof fragments state an O(R_u m^−1/2) bound for the identified terms.Source: §D.1 · pp. 30–31

D.2 Global Convergence

D.2 analyzes global convergence of the meta-algorithm by defining a learning target and bounding its stochastic updates. The theorem uses a two-layer neural-network approximation and supports results for two parameter settings.

D.2 Global Convergence

  • The analysis defines an approximate stationary point α* as the learning target and establishes existence and uniqueness for the associated fixed-point solution.The target is introduced before the global-convergence proof.Source: §D.2 · p. 32
  • Theorem D.4 analyzes the meta-algorithm with stepsize η = T^-1/2 when T ≥ 64/(1 − μ)^2, using a two-layer neural-network approximation.The supplied theorem passage does not include its bound.Source: §D.2 · pp. 32–33
  • Theorem D.4 is applied to obtain Theorems 4.5 and 4.6 under separate choices of distributions, function approximators, and parameters.The passages specify fθ for Theorem 4.5 and Qω for Theorem 4.6.Source: §D.2 · pp. 36–37

E.1 Proof of Lemma 4.7

These proofs bound the errors involved in the policy-improvement analysis and conclude results for Lemmas 4.7–4.9. The Lemma 4.7 proof separates Q-function learning error from the error of fitting the improved policy.

E.1 Proof of Lemma 4.7

  • The Lemma 4.7 proof decomposes the bound into Q-function learning error and error from fitting the improved policy.It bounds these two terms separately before combining them.Source: §E.1 · pp. 37, 39

E.2 Proof of Lemma 4.8

  • The proof of Lemma 4.8 finishes by establishing bound (4.6).The passage identifies the ℓ∞-norm and Cauchy–Schwarz inequalities in deriving the bound.Source: §E.2 · p. 39

E.3 Proof of Lemma 4.9

  • The proof of Lemma 4.9 uses Qω's 1-Lipschitz continuity in ω and the constraint ∥ωk − ω0∥2 ≤ Rω.Source: §E.3 · p. 39

F Proof of Corollary 4.11

The proof of Corollary 4.11 combines the bounds in (F.1) and (F.2) with Theorem 4.10.

F Proof of Corollary 4.11

  • The proof invokes Theorems 4.5 and 4.6 to bound εk+1, with the stated rate expression beginning O(RfT^-1/4 + R^(5/4)…).The supplied passage truncates the expression, so its remaining terms are not reported.Source: F Proof of Corollary 4.11 · p. 40
  • The proof sums (F.1) and (F.2) over k + 1 ∈ [K] and substitutes the result into Theorem 4.10 to obtain Corollary 4.11.Source: F Proof of Corollary 4.11 · p. 40
  • The combined bounds are used as the input to Theorem 4.10 before the corollary is concluded.Source: F Proof of Corollary 4.11 · p. 40

G Proofs of Section 5

The section proves results used in Section 5, including an identity for the advantage function and a KL-based bound. One proof follows Lemma 6.1 of Kakade and Langford (2002).

G Proofs of Section 5

  • Lemma 5.1's proof follows Lemma 6.1 of Kakade and Langford (2002).Source: G Proofs of Section 5 · p. 40
  • The proof uses Aπ(s, a) = Qπ(s, a) − Vπ(s) = (1 − γ)r(s, a) + γE[Vπ(s′)] − Vπ(s) to relate advantage to value and action-value functions.The expectation is over s′ drawn from P(· | s, a).Source: G Proofs of Section 5 · p. 41
  • The Lemma 5.2 proof uses Pinsker’s inequality to rearrange a KL-divergence difference between successive policies.The displayed difference is KL(π* ∥ πθk) − KL(π* ∥ πθk+1).Source: G Proofs of Section 5 · pp. 41–42

Related papers

Loading 1906.10306v3…