PaperlayerView exact revision on arXiv

Source-linked AI summary

Finite-Sample Analysis of Proximal Gradient TD Algorithms

Bo Liu, Ji Liu, Mohammad Ghavamzadeh, Sridhar Mahadevan, Marek Petrik

arXiv:2006.14364v2cs.LGstat.ML

TL;DR

GTD methods lacked finite-sample guarantees, particularly for off-policy reinforcement learning. The paper formulates GTD methods as stochastic gradients of a primal-dual saddle-point objective, derives finite-sample bounds, and proposes projected and accelerated variants. The resulting analysis supports improved methods, with GTD2-MP substantially reducing MSPBE and variance relative to GTD2 in the Baird example.

  • Problem

    The paper addresses the lack of finite-sample analysis for GTD algorithms and convergent off-policy reinforcement learning methods.

  • Method

    The paper formulates GTD objectives as convex-concave saddle-point problems and applies stochastic-gradient analysis, including projected and Mirror-Prox variants.

  • Results

    The paper derives finite-sample performance bounds and reports that GTD2-MP substantially reduces MSPBE and variance relative to GTD2 in the Baird example.

  • Takeaways & Limitations

    The saddle-point formulation provides finite-sample guarantees for GTD methods and supports more efficient accelerated variants.

  • Takeaways & Limitations

    The online-learning analysis does not cover general slowly mixing Markov-chain sampling, which is left for future work.

Abstract

from arXiv · show

In this paper, we analyze the convergence rate of the gradient temporal difference learning (GTD) family of algorithms. Previous analyses of this class of algorithms use ODE techniques to prove asymptotic convergence, and to the best of our knowledge, no finite-sample analysis has been done. Moreover, there has been not much work on finite-sample analysis for convergent off-policy reinforcement learning algorithms. In this paper, we formulate GTD methods as stochastic gradient algorithms w.r.t.~a primal-dual saddle-point objective function, and then conduct a saddle-point error analysis to obtain finite-sample bounds on their performance. Two revised algorithms are also proposed, namely projected GTD2 and GTD2-MP, which offer improved convergence guarantees and acceleration, respectively. The results of our theoretical analysis show that the GTD family of algorithms are indeed comparable to the existing LSTD methods in off-policy learning scenarios.

1 INTRODUCTION

The paper addresses the lack of finite-sample guarantees for GTD methods, especially in off-policy reinforcement learning. It reformulates GTD algorithms through a saddle-point objective and develops finite-sample analyses and improved methods.

  • Motivation: Off-policy learning is difficult because the target and exploratory behaviors differ, and finite-sample analysis in this setting remains challenging.The paper situates GTD methods within this longstanding stability and analysis problem.
  • Problem: Existing GTD algorithms provide asymptotic convergence properties but are not true stochastic gradient methods for their original objectives.Their objective gradients contain products of expectations that cannot be sampled directly without bias from a single sample.
  • Approach: The paper formulates GTD methods as true stochastic gradient algorithms using a primal-dual saddle-point objective.This formulation supports a unified finite-sample analysis and the design of revised GTD methods.
  • Motivation: Finite-sample analysis of gradient TD algorithms is important because real applications provide only limited data.Existing finite-sample RL analyses largely focus on batch, LSTD-based, and on-policy methods.
  • Contributions: The paper provides the first finite-sample analysis for gradient TD algorithms and studies improved convergence, acceleration, and biased importance sampling.These contributions are analyzed within the proposed saddle-point framework.

2 PRELIMINARIES

The preliminaries define off-policy value estimation, linear value-function approximation, TD objectives, and the sampling difficulties underlying GTD analysis. They also review why standard GTD updates are not true stochastic gradients and situate the paper among finite-sample and saddle-point approaches.

  • RL setting: Reinforcement learning models an agent interacting with a stochastic environment, commonly represented as a Markov decision process.Policy evaluation seeks the value function of a given policy through the Bellman operator.
  • RL setting: In off-policy learning, the behavior policy generates data while a different target policy is evaluated using importance-weighting factors.The importance factor is ρ_i = π(a_i|s_i)/π_b(a_i|s_i).
  • Approximation: When the state space is large or infinite, the value function is approximated linearly as ˆv = Φθ using a feature matrix.The paper defines empirical Bellman operators, TD errors, and sample estimates of A, b, and C for this approximation.
  • GTD objectives: GTD algorithms target the norm of the expected TD update and the mean-square projected Bellman error, which can be unified through a matrix-weighted objective.The projection operator uses the feature covariance matrix and is assumed to rely on a nonsingular covariance matrix.
  • GTD objectives: The original GTD and GTD2 updates are not true stochastic gradients because their gradients contain products of expectations whose single-sample products are biased.Auxiliary variables address the product structure, but this prevents direct use of standard stochastic-gradient finite-sample analysis.
  • Off-policy sampling: Rejected sampling can discard many samples when behavior and target policies differ substantially.A rejected sample does not update the parameter when the target policy assigns zero probability to the selected action.
  • Related work: Prior finite-sample bounds largely concern LSTD-style or on-policy methods, while this paper connects GTD analysis with primal-dual and saddle-point formulations.The reviewed literature includes limited off-policy results and several alternative formulations of the learning problem.
  • Related work: The paper explores GTD algorithms as stochastic gradients of convex-concave saddle-point formulations, related to proximal reinforcement learning and mirror-map methods.This places the approach alongside variational-inequality, linear-inverse-problem, and quadratic-objective formulations.

3 SADDLE-POINT FORMULATION OF GTD ALGORITHMS

The paper converts NEU and MSPBE optimization into convex-concave saddle-point problems, making GTD and GTD2 true stochastic gradient methods. This enables finite-sample analysis and more efficient stochastic optimization variants.

  • Saddle-point formulation: NEU and MSPBE are written as convex-concave saddle-point objectives with a positive-definite matrix M.The formulation uses F(θ) = 0 and a quadratic regularizer K(y) = 1/2||y||^2_M.
  • Algorithmic consequence: The saddle-point representation permits stochastic-gradient convergence analysis and the use of stochastic Mirror-Prox to derive more efficient GTD variants.The same formulation supports finite-sample performance bounds and accelerated GTD/GTD2 methods.
  • Saddle-point formulation: For fixed θ, maximizing the saddle objective over y recovers one-half of the unified NEU or MSPBE objective.The choice M = I yields NEU, while M = C yields MSPBE.
  • Saddle-point formulation: The maximizing auxiliary variable y∗(θ) can be computed analytically because the objective is an unconstrained quadratic in y.This gives y∗(θ) = M^-1(b − Aθ).
  • Algorithmic consequence: GTD and GTD2 are true stochastic gradient algorithms for the saddle objective, using M = I and M = C, respectively.Their updates result from replacing A, b, and C with unbiased sample estimates.

4 FINITE-SAMPLE ANALYSIS

The paper develops finite-sample analysis for revised GTD algorithms by casting them as stochastic gradient methods for a saddle-point problem. Under boundedness, non-singularity, light-tail, and sampling assumptions, it derives high-probability performance bounds for on-policy and off-policy learning.

  • Revised GTD algorithms: The revised algorithms project θ and y onto bounded convex feasible sets and use a unified matrix M for GTD and GTD2 analysis.M is the identity for GTD and the covariance matrix C for GTD2.
  • Assumptions: The analysis assumes a saddle point lies in the feasible sets, covariance matrices are non-singular, features and importance weights are bounded, and estimators have controlled tails.The light-tail condition is required for the high-probability bound.
  • Sampling setting: The finite-sample bounds apply to training data whose initial states are i.i.d. samples from a distribution ξ, separately covering on-policy and off-policy settings.The sampling scheme is also motivated by high-dimensional problems where least-squares matrix inversion is impractical.
  • General finite-sample bound: Proposition 3 gives a high-probability bound on the saddle-point error of the averaged GTD output after n iterations.The bound depends on the feasible-set radius, variance, and τ, where τ = 1 for GTD and τ = σmax(C) for GTD2.
  • Performance bounds: On-policy and off-policy performance bounds translate saddle-point error into value-function performance guarantees for GTD and GTD2.The off-policy result requires a condition on Ξ that limits the discrepancy between behavior and target policies.

5 ACCELERATED ALGORITHM

The paper uses Stochastic Mirror-Prox to construct accelerated GTD variants from the saddle-point formulation. These variants are called GTD-MP and GTD2-MP.

  • Accelerated algorithm: The saddle-point formulation enables both finite-sample stochastic-gradient analysis and the use of more efficient optimization algorithms.This connects the revised GTD analysis to algorithmic improvements beyond the original methods.
  • Accelerated algorithm: The paper reports an experimental comparison between GTD2 and GTD2-MP in Section 7.The supplied passage identifies the comparison but does not state its outcome.

6 FURTHER ANALYSIS

The paper extends finite-sample analysis to accelerated GTD methods and examines practical limitations involving biased importance weights, online samples, and TDC. The analysis supports acceleration through saddle-point solvers but leaves some settings unresolved.

  • 6.1 ACCELERATION ANALYSIS: GTD2-MP uses stochastic Mirror-Prox to accelerate convergence, while stochastic accelerated primal-dual methods can attain the optimal saddle-point rate.The paper also notes that detailed descriptions of these solvers are omitted because of space limitations.
  • 6.2 LEARNING WITH BIASED ρt: Unbounded importance weights and biased estimates make the stochastic gradient inexact, worsening convergence and performance bounds.The analysis models biased importance-weight estimation through stochastic-gradient methods with an inexact oracle.
  • 6.2 LEARNING WITH BIASED ρt: Exact importance-weight estimation is therefore important because inexact estimates may cause disastrous estimation error.
  • 6.3 FINITE-SAMPLE ANALYSIS OF ONLINE LEARNING: For online learning, the analysis applies when the underlying Markov chain mixes sufficiently quickly; slow mixing requires an extension left for future work.Interactive samples are not i.i.d., which creates the additional Markov-chain dependence considered in this limitation.
  • 6.4 DISCUSSION OF TDC ALGORITHM: The analysis is limited for TDC because TDC appears not to have an explicit saddle-point representation.TDC incorporates the optimal auxiliary variable into the θ update through a quasi-stationary two-time-scale scheme.
  • 6.4 DISCUSSION OF TDC ALGORITHM: TDC may converge faster when its optimal auxiliary variable has a closed-form or easily computed solution, but it requires more restrictions than GTD2.Unlike GTD and GTD2, TDC is a two-time-scale algorithm and does not minimize an objective function.

7 EMPIRICAL EVALUATION

The empirical evaluation compares GTD2-MP with GTD2 across Baird, chain, and energy-management domains, focusing on value-function approximation. Across these experiments, GTD2-MP shows lower MSPBE and variance, greater stepsize robustness, and better reported performance in transient and steady-state behavior.

  • 7 EMPIRICAL EVALUATION: The evaluation focuses on policy evaluation and value-function approximation rather than control-learning performance.Control-learning comparisons are not reported.
  • 7.1 BAIRD DOMAIN: GTD2-MP substantially reduces both MSPBE and variance relative to GTD2 in the Baird example.The comparison averages 8,000 steps over 200 runs.
  • 7.2 50-STATE CHAIN DOMAIN: GTD2-MP is much more robust to stepsize choice than GTD2 in the 50-state chain domain.Figure 2 compares the true value function with GTD and GTD2-MP approximations across multiple stepsizes.
  • 7.3 ENERGY MANAGEMENT DOMAIN: GTD2-MP performs better than GTD2 during the transient state and reaches a better steady-state solution in the energy-management domain.The off-policy evaluation problem does not have a solution for Aθ = b, so the optimal MSPBE and MSBE do not reduce to 0.

8 SUMMARY

The paper frames gradient TD methods as true stochastic gradient methods for a saddle-point primal-dual objective, enabling finite-sample analysis of off-policy learning. It also proposes projected GTD2 and accelerated GTD2-MP, while identifying extensions to sparse regularization, TDC, and tighter approximation bounds.

  • 8 SUMMARY: Gradient TD methods are formulated as true stochastic gradient methods with respect to a saddle-point primal-dual objective.This formulation enables finite-sample analysis of off-policy convergent gradient-based TD algorithms such as GTD and GTD2.
  • 8 SUMMARY: The paper proposes projected GTD2 and accelerated GTD2-MP as revised algorithms.The proposed framework is also identified as applicable to regularized sparse gradient off-policy TD methods.
  • 8 SUMMARY: Future directions include analyzing TDC, which lacks a saddle-point formulation, and obtaining tighter value-function approximation bounds.The framework is stated to support investigation of regularized sparse gradient off-policy TD methods.

A PROOF OF LEMMA 2

The proof bounds quantities needed for the finite-sample analysis by exploiting bounded features and rewards, matrix and vector norm inequalities, and a similar argument for b.

  • A PROOF OF LEMMA 2: Bounded features and rewards provide the starting point for bounding the relevant matrix quantity.The proof applies consistent matrix-norm, triangular, and vector-norm inequalities.
  • A PROOF OF LEMMA 2: The norm bound for b is derived analogously to the preceding matrix bound.The proof then concludes after establishing the required inequalities.

B PROOF OF PROPOSITION 3

The proposition proof maps the paper’s convex-concave stochastic saddle-point problem to an existing stochastic optimization result. It verifies bounded feasible sets, convex-concave Lipschitz structure, norm bounds, and a stepsize choice before obtaining a high-probability error bound.

  • B PROOF OF PROPOSITION 3: The feasible sets are non-empty, bounded, closed, and convex, while the objective is Lipschitz continuous on their product.These properties establish the conditions needed to apply the referenced stochastic saddle-point result.
  • B PROOF OF PROPOSITION 3: The saddle-point problem has solvable primal and dual formulations with equal optimal values and saddle-point solutions.The objective is convex in θ and concave in y over the feasible sets.
  • B PROOF OF PROPOSITION 3: The stochastic sub-gradient vector is defined so its deterministic counterpart belongs to the corresponding subdifferentials.This connects the stochastic update to the convex-concave saddle-point objective.
  • B PROOF OF PROPOSITION 3: In the Euclidean setting, the distance-generating functions and dual norms reduce to ℓ2-based constructions.The product space Z = Θ×Y is equipped with a corresponding distance-generating function.
  • B PROOF OF PROPOSITION 3: The proof bounds the stochastic sub-gradient quantities using norm definitions, bounded feasible sets, and an inequality for sums of nonnegative squares.These bounds determine the quantity M∗ used in the finite-sample analysis.
  • B PROOF OF PROPOSITION 3: Setting α_t = 2c/(M∗√n) and using the light-tail assumption yields a high-probability bound on Err(¯θ_n, ¯y_n).The proof applies the referenced proposition and substitutes earlier bounds on ||A||2 and ||b||2.

C PROOF OF PROPOSITION 4

The proof derives Proposition 4 by combining norm bounds, projection properties, covariance-matrix eigenvalue relations, and earlier lemmas and theorems. It concludes by assembling these bounds to obtain Eq. 33.

  • Norm and projection bounds: The proof applies the ℓ2-norm under distribution ξ and uses the target-policy kernel P with orthogonal projection Π to establish a resolvent bound.Specifically, ||(I −γΠP)−1||ξ ≤ 1/(1−γ).
  • Covariance conditioning: The term ||ΦC−1(b − A¯θn)||ξ is upper-bounded using inequalities and the relation ν = λmin(C), the smallest eigenvalue of covariance matrix C.The proof identifies ν through the spectral norm of C−1 and its largest eigenvalue.
  • Error decomposition: Using the triangle inequality, the proof separates the bound into two terms and controls the second term with Lemma 4.The first term is bounded separately before combining the results.
  • Final combination: The first-term bound uses τC = σmax(C), σmin(A⊤M−1A), and Theorem 1, after which Eqs. 42, 32, and 44 yield Eq. 33.This final combination completes the proof of Proposition 4.
Loading 2006.14364v2…