PaperlayerView exact revision on arXiv

Source-linked AI summary

Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes

Guanghui Lan

arXiv:2102.00135v6cs.LGcs.AImath.OC

TL;DR

The paper addresses RL optimization with convex policy regularizers despite highly nonconvex value objectives and unavailable exact action-value functions. It develops deterministic, approximate, and stochastic policy mirror descent methods, establishing linear convergence and new sampling-complexity bounds while broadening the regularizers expressible in RL.

  • Problem

    The paper studies RL problems with strongly convex or general convex regularizers and seeks efficient methods despite highly nonconvex policy objectives and unavailable exact action-value information.

  • Method

    It develops PMD, APMD, and stochastic variants using generalized monotonicity and separate control of stochastic-estimation bias and total expected error.

  • Results

    Linear convergence is established for the proposed methods, with O(|S||A|/(με)) and O(|S||A|/ε^2) sampling complexities for strongly and general convex regularizers under multiple-trajectory sampling.

  • Takeaways & Limitations

    Convex regularizers expand RL modeling to include constraints, action-state correlations, and policy risk or utility functions.

  • Takeaways & Limitations

    With function approximation, an additional bias may restrict convergence guarantees to a neighborhood of the optimum unless the feature span contains the true value functions.

Abstract

from arXiv · show

We present new policy mirror descent (PMD) methods for solving reinforcement learning (RL) problems with either strongly convex or general convex regularizers. By exploring the structural properties of these overall highly nonconvex problems we show that the PMD methods exhibit fast linear rate of convergence to the global optimality. We develop stochastic counterparts of these methods, and establish an ${\cal O}(1/ε)$ (resp., ${\cal O}(1/ε^2)$) sampling complexity for solving these RL problems with strongly (resp., general) convex regularizers using different sampling schemes, where $ε$ denote the target accuracy. We further show that the complexity for computing the gradients of these regularizers, if necessary, can be bounded by ${\cal O}\{(\log_γε) [(1-γ)L/μ]^{1/2}\log (1/ε)\}$ (resp., ${\cal O} \{(\log_γε) (L/ε)^{1/2}\}$)for problems with strongly (resp., general) convex regularizers. Here $γ$ denotes the discounting factor. To the best of our knowledge, these complexity bounds, along with our algorithmic developments, appear to be new in both optimization and RL literature. The introduction of these convex regularizers also greatly expands the flexibility and applicability of RL models.

1 Introduction

The paper studies RL problems with convex or strongly convex policy regularizers and develops deterministic and stochastic policy mirror descent methods for these settings. It exploits generalized monotonicity to obtain linear convergence and establishes sampling and regularizer-gradient complexity bounds.

  • Problem class: Convex regularizers unify strongly convex and general convex RL formulations while modeling constraints, action-state correlations, and policy risk or utility.The general convex class includes the unregularized case h_π = 0; strong convexity is defined by μ > 0.
  • Problem class: The RL objective is to find an optimal policy over state-wise simplex constraints, although its value-function formulation is highly nonconvex in the policy.The paper uses an objective weighted by a positive state distribution, including the optimal policy’s stationary distribution ν*.
  • Algorithms and convergence: PMD achieves linear convergence for strongly convex regularizers, while APMD uses adaptive perturbations to achieve linear convergence for general convex regularizers.The analysis uses generalized monotonicity from a variational-inequality reformulation rather than Bellman-operator contraction.
  • Algorithms and convergence: Stochastic PMD and SAPMD separately control estimator bias and overall expected error, enabling convergence guarantees under stochastic first-order information.The separate treatment reflects that the bias can often be reduced faster than the total expected error.
  • Complexity: O(|S||A|/(με)) and O(|S||A|/ε^2) sampling complexities are established for strongly and general convex regularizers with multiple independent trajectories.With CTD and regularity assumptions, the same orders can be achieved with a single trajectory and Markovian noise.
  • Complexity: Approximate solutions to regularizer subproblems preserve the convergence and sampling guarantees, while accelerated gradient descent bounds the complexity of computing ∇h_π.The subproblems generally lack explicit solutions unless the regularizer is simple, such as absent or given by KL divergence.

2 Optimality Conditions and Generalized Monotonicity

Although the RL value objective is highly nonconvex, the paper reformulates its optimality conditions as a variational inequality with generalized monotonicity. This structure supports the subsequent design of efficient policy mirror descent algorithms.

  • Optimality conditions: The value function is highly nonconvex in the policy, but the objective can be reformulated as a variational inequality with generalized monotonicity.The nonconvexity arises because policy components multiply one another in the value-function definitions.
  • Gradient characterization: The paper computes value-function gradients using discounted state visitation distributions and transition matrices induced by the policy.The induced transition matrix satisfies P^π(i,j) = Σ_a π(a|i)P(j|i,a).
  • Optimality conditions: The optimality condition for the weighted value objective leads to a variational inequality that can be extended to nonsmooth regularizers.The nonsmooth formulation replaces the differentiable regularizer treatment with a suitable variational inequality problem.
  • Generalized monotonicity: A generalized performance-difference lemma establishes the monotonicity relation used to analyze the variational inequality.The argument compares two feasible policies and uses their value-function differences and induced trajectories.
  • Generalized monotonicity: Because V^π(s) − V^π*(s) ≥ 0 for feasible policies, the variational inequality satisfies generalized monotonicity.The paper then exploits this structural property to design efficient algorithms for the RL problem.

3 Deterministic Policy Mirror Descent

The deterministic PMD framework updates policies through a proximal mapping based on action-value information and Bregman distance. Strongly convex regularizers yield linear convergence, while adaptive perturbations extend linear convergence to general convex regularizers under suitable schedules.

  • Basic PMD method: PMD updates each policy through a proximal mapping using a stepsize, a variational-inequality operator such as Qπ, and Bregman distance.The operator may be the action-value function or an approximation.
  • Basic PMD method: The PMD analysis uses a three-point lemma and generalized monotonicity rather than Bellman-operator contraction.This supports analysis of the overall nonconvex RL problem without relying on Bellman contraction properties.
  • Basic PMD method: Linear convergence holds for PMD with strongly convex regularizers, in both function value and distance to the optimal solution.The result uses a constant stepsize rule for µ > 0.
  • Basic PMD method: For general convex regularizers, direct PMD achieves a sublinear rate requiring O(1/(1 −γ)ε) iterations for an ε-solution.This matches the dependence on (1−γ) and ε of the previously best-known natural policy gradient complexity.
  • Approximate policy mirror descent method: APMD adds an adaptive perturbation term to the value functions or proximal mapping, reducing to PMD when the perturbation vanishes.The perturbation preserves the subproblem’s difficulty while allowing a broader algorithmic form.
  • Approximate policy mirror descent method: With τk = τ0γk and 1 + ηkτk = 1/γ, APMD achieves O(kγk) convergence for constant τ0 and O(γk) when τ0 = 1/k.A related epoch schedule reaches O(logγ(ε)) iterations for an ε-solution in the strongly convex setting.
  • Approximate policy mirror descent method: For general RL problems, linear convergence of the solution sequence cannot be guaranteed once the perturbation coefficient τk becomes sufficiently small.Asymptotic convergence may still follow from continuity and compactness, but a rate requires additional structural properties.

4 Stochastic Policy Mirror Descent

The paper develops stochastic PMD methods because exact action-value functions are unavailable in practical RL. SPMD and SAPMD analyze stochastic bias and error separately, yielding convergence results for strongly and general convex regularizers, including last-iterate linear convergence for SAPMD.

  • Motivation: Exact action-value functions are impractical because they involve infinite sums and unknown transition dynamics, motivating stochastic estimators.The stochastic methods replace exact Q-functions with estimators of the action-value functions.
  • Stochastic-error treatment: Separating estimator bias ςk from total expected error σk enables faster bias reduction and improves the analysis and sampling-complexity bounds.The paper explicitly contrasts this treatment with classic stochastic mirror descent.
  • Methods: SPMD replaces Qπk with a stochastic estimator Qπk,ξk, while SAPMD makes the analogous substitution in the approximate PMD update.Both methods are stochastic counterparts of their deterministic policy mirror descent methods.
  • SPMD convergence: Unlike deterministic PMD, SPMD does not guarantee that the value function is non-increasing during stochastic iterations.The loss of monotonicity is a direct consequence of stochastic action-value information.
  • SPMD convergence: For general convex regularizers, SPMD uses a randomly selected iterate and has a sublinear convergence term, requiring at least O(1/ε) updates.SAPMD is introduced to address these shortcomings.
  • SAPMD convergence: SAPMD establishes a linear convergence rate for the last generated policy, so deployed policies can continuously improve without random or average-iterate output.The paper also derives a probability guarantee for achieving f(πk) − f(π∗) ≤ ε.

5 Stochastic Estimation for Action-value Functions

This section develops stochastic PMD methods for estimating action-value functions under independent-trajectory and online CTD sampling schemes, with convergence and sampling guarantees for strongly and general convex regularizers.

  • Multiple independent trajectories: Multiple independent trajectories estimate action-value functions by generating trajectories from state-action pairs under the current policy.The scheme uses M_k independent trajectories of length T_k for each state-action pair.
  • Strongly convex regularizers: O(log_γ ε) SPMD iterations yield an ε-solution for strongly convex regularizers, with total samples bounded by the section’s trajectory estimates.The guarantee concerns E[f(π̄) − f(π*) + μ/(1−γ)D(π̄,π*)] ≤ ε.
  • Strongly convex regularizers: O(|S||A|/(μ ε)) sampling complexity is established for strongly convex regularizers with multiple independent trajectories.The paper identifies this bound as new for RL problems with strongly convex regularizers, despite the nonconvex formulation.
  • General convex regularizers: O(log |A|/[(1−γ)^5 ε^2]) SPMD iterations suffice for an ε-solution with general convex regularizers under the stated single-trajectory sampling setup.The result is stated for M_k = 1 and a priori fixed iteration count.
  • General convex regularizers: O(log_γ ε) SAPMD iterations achieve an ε-solution for general convex regularizers, with sampling complexity bounded under the corresponding trajectory scheme.The analysis also reports a slightly better logarithmic dependence for one SAPMD sampling bound than for the comparable SPMD bound.
  • Online sampling: Conditional temporal difference estimation handles online single-trajectory data, while its analysis separately controls estimator bias and expected error.The CTD approach is used to estimate Q^π in SPMD; estimating Q^{π,τ} in SAPMD is described as similar.
  • Online sampling: Function approximation introduces an additional gradient bias unless the feature span contains the true value functions, yielding convergence only to a neighborhood.It can nevertheless reduce gradient-computation dependence from |S| × |A| to the number of columns of Φ.

6 Efficient Solution for General Subproblems

This section analyzes inexact PMD subproblems solved with accelerated gradient descent, showing that controlled prox-mapping errors preserve the methods’ convergence and complexity guarantees.

  • General subproblem solution: Accelerated gradient descent is used to solve smooth convex prox-mapping subproblems when regularizer gradients are Lipschitz continuous.The section assumes h_π is differentiable with gradient Lipschitz constant L.
  • General subproblem solution: The generalized AGD analysis is formulated in terms of distance D_xx0, which supports convergence analysis for inexact SPMD and SAPMD.The result is adapted from standard AGD guarantees to fit the inexact PMD subproblems.
  • Inexact SPMD: Inexact SPMD retains its iteration and sampling complexities when prox-mapping errors satisfy ε_k ≤ (1−γ)^2 2^{−(⌊(k+1)/l⌋+2)}.The required errors decrease geometrically with the iteration grouping parameter l.
  • Inexact SPMD: The total gradient-computation bound for h follows by combining the prox-subproblem condition number with the AGD convergence estimate.The resulting bound is stated after combining the subproblem conditioning and Lemma 19.
  • Inexact SAPMD: Inexact SAPMD uses AGD for perturbed subproblems and analyzes the resulting recursion under decreasing regularization and prox-error sequences.The SAPMD proof applies the same AGD framework to the perturbed value functions and regularized subproblem.
  • Inexact SAPMD: Inexact SAPMD preserves its iteration and sampling complexities when ε_k satisfies the stated decreasing accuracy condition.The paper states that the inexact solution barely affects these complexities under that condition.

7 Concluding Remarks

The paper develops deterministic and stochastic PMD variants for convex-regularized RL, establishes convergence and sampling guarantees, and analyzes inexact prox-mapping solutions.

  • Convergence: PMD has linear convergence for strongly convex regularizers and sublinear convergence for general convex regularizers.The conclusion summarizes these rates for the base PMD method.
  • Convergence: APMD adds adaptive perturbations to action-value functions and achieves linear convergence for general convex regularizers.This extends the convergence guarantee beyond the strongly convex case for standard PMD.
  • Stochastic methods: Stochastic PMD and APMD methods converge under conditions controlling both estimator bias and overall expected error.The analysis treats these two error components separately.
  • Sampling complexity: The paper derives sampling bounds using a generative model and conditional temporal difference estimation for online trajectories.The latter requires a bias bound for action-value estimation.
  • Inexact subproblems: The paper also specifies required prox-subproblem accuracy so PMD-type methods retain their convergence and sampling guarantees.This is addressed through accelerated gradient methods for smooth convex regularizers.

Appendix A: Concentration Bounds for l∞-bounded Noise

The appendix develops concentration tools for bounded-noise action-value estimators, including bounds on maxima of finite collections of sub-exponential variables.

  • Concentration bounds: The appendix begins by bounding the expectation of the maximum of finitely many sub-exponential random variables.The bound is used as a concentration tool for subsequent estimator analysis.
  • Concentration bounds: The sub-exponential norm is defined through an exponential-moment threshold for the absolute value of a random variable.The appendix denotes this norm by ||X||_ψ1.
  • Concentration bounds: Centering preserves sub-exponentiality, enabling an exponential-moment bound for each centered variable over a restricted range of λ.The centered variables inherit a norm bound proportional to the original scale parameter σ.
  • Concentration bounds: E[max_i X_i] is bounded by a scale factor times (log n + 1) plus the common mean bound.The result follows by applying the exponential-moment inequality with λ chosen at the edge of its admissible range.
  • Application to estimation: The appendix applies these concentration ideas to squared action-value estimation errors formed from independent trajectory returns.For each state-action pair, the estimator uses M_k independent trajectories of length T_k.

Appendix B: Bias for Conditional Temporal Difference Methods

The appendix derives bias relations for conditional temporal-difference methods by taking successive conditional expectations and applying Jensen-type inequalities and prior lemmas. A telescoping argument after normalization by Γ_t yields the stated result, using the initialization relation θ̄_1 = θ_1.

  • Jensen’s inequality together with Lemmas 16 and 17 supplies intermediate bounds used in the bias analysis.
  • Conditional expectation over ζ_t gives θ_{t+1} an update involving F^{π}(θ_t) and the bias term δF_t.The relation is obtained from equation (5.11) conditional on ζ^{⌈t−1⌉}.
  • Further expectation and linearity of F produce the averaged recursion θ̄_{t+1} = θ̄_t − β_tF^{π}(θ̄_t) + β_tδ̄F_t.
  • Dividing equation (7.3) by Γ_t and taking a telescopic sum yields the result, with θ̄_1 = θ_1 providing the initial relation.
Loading 2102.00135v6…