Neural Temporal-Difference and Q-Learning Provably Converge to Global Optima

Qi Cai; Zhuoran Yang; Jason D. Lee; Zhaoran Wang

Source-linked AI summary

Neural Temporal-Difference and Q-Learning Provably Converge to Global Optima

Qi Cai, Zhuoran Yang, Jason D. Lee, Zhaoran Wang

arXiv:1905.10027v2May 24, 2019cs.LGcs.AImath.OCstat.ML

TL;DR

Neural temporal-difference learning faces divergence risks from stochastic semigradients and nonlinear value-function approximation. The paper establishes global convergence results for MSPBE optimization and extends them to (soft) Q-learning.

Problem
Nonlinear value-function approximation creates bias in stochastic semigradients and possible divergence, leaving global convergence unclear.
Method
The paper uses overparameterized nonlinear function approximation to establish nonasymptotic global convergence results.
Results
Neural TD reaches the global optimum of MSPBE at rate 1/T with population semigradients and extends global convergence to (soft) Q-learning.
Takeaways & Limitations
The results connect global convergence in policy evaluation with policy improvement through neural (soft) Q-learning.
Takeaways & Limitations
The analysis includes a finite-state-space requirement and contrasts with settings where nonlinear TD converges only to a local MSPBE optimum.

Abstract

from arXiv · show

Temporal-difference learning (TD), coupled with neural networks, is among the most fundamental building blocks of deep reinforcement learning. However, due to the nonlinearity in value function approximation, such a coupling leads to nonconvexity and even divergence in optimization. As a result, the global convergence of neural TD remains unclear. In this paper, we prove for the first time that neural TD converges at a sublinear rate to the global optimum of the mean-squared projected Bellman error for policy evaluation. In particular, we show how such global convergence is enabled by the overparametrization of neural networks, which also plays a vital role in the empirical success of neural TD. Beyond policy evaluation, we establish the global convergence of neural (soft) Q-learning, which is further connected to that of policy gradient algorithms.

1 Introduction

The paper addresses the unclear convergence of neural TD by proving global, sublinear convergence under overparametrization, extending the analysis to neural (soft) Q-learning and policy-gradient variants.

Motivation: The theory targets a gap between neural TD’s practical generalization and prior guarantees limited to local optima or possible divergence.Nonlinear TD is guaranteed only local asymptotic convergence, while neural TD can diverge because of biased semigradients and neural nonlinearity.
Contribution: Neural TD converges to the global optimum of MSPBE at rate 1/T with population semigradients and at rate 1/√T with stochastic semigradients.The value function is represented by a sufficiently wide multilayer neural network.
Contribution: For a broad class of reinforcement-learning problems, neural TD attains zero MSPBE because the projected function class has reproducing-kernel Hilbert-space representation power.The relevant kernel is associated with the random initialization.
Contribution: Under stronger regularity conditions, neural (soft) Q-learning converges at the same rate to the global MSPBE optimum for policy optimization.Q-learning extends the result beyond policy evaluation because it also supports policy improvement.
Contribution: The analysis also establishes global convergence for a policy-gradient variant by exploiting the connection between (soft) Q-learning and policy-gradient algorithms.The connection is made to policy-gradient methods cited in the paper.
Contribution: Overparametrization enables implicit local linearization and one-point monotonicity, addressing divergence, semigradient bias, and MSPBE nonconvexity.The implicit linearization varies smoothly along the solution path, while monotonicity drives evolution toward the global optimum.

2 Background

The paper formulates policy evaluation for value and action-value functions, then defines Bellman-error objectives and their projected approximation for Q-functions.

Policy evaluation learns value and action-value functions under a policy, whose performance is measured by expected total reward.
The Bellman evaluation operator maps Q-functions to expected one-step rewards plus discounted successor values, with Qπ as its fixed point.
Q-learning policy evaluation minimizes mean-squared Bellman error, while function approximation motivates minimizing the projected mean-squared Bellman error instead.
The projection operates onto a function class that may be linear, locally linearized, or induced by neural Q-function approximation.
The analysis primarily samples state-transition tuples independently from the stationary distribution, with temporal dependence handled separately in Appendix G.

3 Neural Temporal-Difference Learning

Neural TD updates Q-function parameters using stochastic semigradients, while overparameterized networks and projection support analysis of descent toward the global MSPBE optimum.

The analysis focuses on TD(0), assumes continuous states and finite actions represented by normalized feature vectors, and leaves TD(λ) for future work.
The neural Q-function uses a ReLU network with random initialization, trains only the weight parameters, and applies an additional projection step.
The TD update is not an unbiased stochastic gradient of an objective, yet the paper proves it provides a descent direction toward the global MSPBE optimum.
As network width increases, the projected function class becomes richer, the MSPBE approaches the MSBE, and the desired Q-function is recovered.

4 Main Results

The main results characterize a unique globally optimal stationary point for an overparameterized neural TD formulation and establish nonasymptotic convergence results under stated distributional assumptions.

4 Main Results: The paper establishes global optimality and nonasymptotic convergence rates for neural TD using population and stochastic semigradients, with multi-layer extensions in Appendix F.
4.1 Properties of Stationary Point: Overparameterization keeps neuron activation patterns approximately fixed, allowing a simpler function class to characterize global convergence.
4.1 Properties of Stationary Point: An approximate stationary point exists uniquely because it is the fixed point of a projected Bellman operator that is contractive under the stationary-distribution norm.
4.1 Properties of Stationary Point: The stationary point’s Q-function is the global optimum of the MSPBE associated with projection onto the analyzed function class.
4.2 Global Convergence: The regularity condition is implied when the marginal feature distribution has a uniformly upper-bounded density over the unit sphere.
4.2 Global Convergence: The convergence theorem uses stepsize η = (1 −γ)/8 and a regularity assumption on the stationary distribution, with T iterations and network width m defining the setting.

Appendix C.5 for a detailed proof.

The analysis bounds stochastic semigradient variance and proves neural TD globally converges to the MSPBE optimum, with approximation error controlled by network width and function-class representation.

The stochastic semigradient variance determines the stepsize scaling needed for convergence.
As width m →∞, the approximate stationary solution becomes the global optimum of the MSPBE.
When Qπ is outside FB,m, the approximation error is bounded by its distance from the function class.
When Qπ lies in FB,∞, neural TD converges to Qπ and achieves zero MSPBE and MSBE objective values as T,m →∞.

5 Proof Sketch

The proof connects neural TD to a locally linearized model whose approximation error vanishes with width, enabling descent toward the MSPBE optimum and extending the argument to neural Q-learning.

5 Proof Sketch: Local linearization error vanishes as network width m increases, allowing implicit linearization to establish global convergence of neural TD.
5 Proof Sketch: Population semigradient updates descend toward the approximate stationary point up to the local-linearization error.
5 Proof Sketch: Stochastic semigradient variance is handled by rescaling the stepsize to order T^−1/2.
6.1 Neural Q-Learning: Neural Q-learning uses greedy next actions and requires stronger regularity conditions than neural TD because of the max operator.
6.2 Global Convergence: Under the exploration-policy assumptions, neural Q-learning globally converges with η of order T^−1/2.
6.3 Implication for Policy Gradient: The result extends to neural soft Q-learning and yields global convergence for a variant of policy gradient through their equivalence.

A.2 FB,∞as RKHS

As width tends to infinity, the neural function class approaches an RKHS-based class whose projected Bellman fixed point is the global MSPBE optimum under stated closure conditions.

A.2 FB,∞as RKHS: The infinite-width function class is related to an RKHS generated by the neural network’s feature map.
A.2 FB,∞as RKHS: As m →∞, the empirical feature distribution converges to its population counterpart, yielding the limiting function class.
A.2 FB,∞as RKHS: The limiting solution is a fixed point of the projected Bellman equation and therefore the global optimum of the MSPBE.
A.2 FB,∞as RKHS: If the Bellman evaluation operator is closed in the limiting class and B is sufficiently large, the projected solution equals Qπ.

B.1 Proof of Lemma 4.2

The proof establishes uniqueness through contraction of the projected Bellman operator, then shows neural TD’s locally linearized updates descend toward that fixed point with errors controlled by linearization and stochastic variance.

B.1 Proof of Lemma 4.2: The approximate stationary point corresponds to the unique projected Bellman fixed point in the neural function class.
B.1 Proof of Lemma 4.2: The projected Bellman operator is a γ-contraction, so its projected Bellman equation has a unique fixed point.
B.1 Proof of Lemma 4.2: The locally linearized population semigradient is one-point monotone with respect to the approximate stationary point.
B.1 Proof of Lemma 4.2: Telescoping the descent inequalities yields the population and stochastic convergence bounds for neural TD.

D Proofs for Section 6

The proofs establish contraction and fixed-point properties for the projected Bellman operator, then bound stochastic and linearization errors to complete neural Q-learning convergence.

The proof extends prior linear Q-learning analysis by incorporating local-linearization error and handling soft Q-learning.The extension is explicitly described as adding local-linearization error while treating soft Q-learning in the subsequent section.
Under the stated assumptions, an approximate stationary point W ∗ exists and bQ0(· ; W ∗) is unique almost everywhere.
The projected Bellman operator is a γ/(γ + ν)-contraction, yielding a unique fixed point corresponding to W ∗.This follows from nonexpansiveness of ΠFB,m and completeness of the feasible function set.
The analysis separately bounds the variance of the semigradient and the error terms arising in the stochastic-update recursion.These bounds are combined and telescoped over iterations to prove the theorem.

E.1 Global Convergence of Neural Soft Q-Learning

This section extends global convergence from neural Q-learning to neural soft Q-learning and connects its update to a variant of policy gradient and soft actor-critic.

The softmax replacement is handled through a more general operator and its entropy-based duality.The resulting additional β−1 · log |A| term is independent of t and m.
Neural soft Q-learning inherits the convergence theorem under the stated regularity conditions, with η set to order T −1/2.The proof replaces the max operator with a softmax operator and preserves the key error bounds.
The soft Q-learning semigradient equals a variant of population policy gradient when the exploration policy is πθ.The associated estimator uses the advantage function for a KL-regularized reward and includes entropy regularization.
The resulting global convergence extends to a variant of the actor-critic algorithm, connected to soft actor-critic.

F Extension to Multi-Layer Neural Networks

The paper extends neural TD convergence analysis to multi-layer neural networks by controlling local linearization and proving a corresponding global-convergence theorem.

The multi-layer setting keeps hidden-layer weights trainable while fixing the outer weights at their random initialization.
The multi-layer analysis establishes global convergence of neural TD while abandoning Assumption 4.3 at the cost of a slightly worse local-linearization bound.
The supporting lemmas control the multi-layer network's local linearization with probability at least 1−e−Ω(log2 m) over random initialization.
Theorem F.3 requires width and radius conditions scaling with d, B, H, and m, with T and H = O(T 1/4).The theorem is stated under these scaling conditions and concerns the output of Algorithm 1.

G Extension to Markov Sampling

The Markov-sampling extension replaces independent stationary samples with sequentially sampled β-mixing trajectories and proves a corresponding stochastic-update convergence result.

The Markov-sampling analysis extends the linear-function-approximation treatment of Bhandari et al. (2018) to neural function approximation.
The Markov-chain setting is characterized using sequential samples from the chain induced by policy π and a stationary-distribution semigradient.
Dependence is handled by showing the sampling error is bounded and approximately Lipschitz continuous rather than exactly Lipschitz continuous.This produces an additional O(B7/3H9/2m−1/6 log3/2 m) term in Lemma G.2.
Under a β-mixing Markov-chain assumption, Theorem G.3 establishes convergence for Algorithm 1 with sequentially sampled tuples.The theorem retains the stated width, radius, horizon, and high-probability framework.

H.1 Proof of Lemma D.3

The proof of Lemma D.3 proceeds through maximization, expectation, an assumption-based bound, and Hölder’s inequality before concluding.

The proof begins by establishing a statement for any state s ∈S and action a ∈A, then takes the maximum over actions.
It next takes expectations with respect to random initialization and the stationary distribution of s.
Assumption 6.2 and Hölder’s inequality are then applied to bound the relevant right-hand side.
The resulting bound completes the proof of Lemma D.3.