A Robust $\widetilde{\mathcal{O}}(1/\sqrt{T})$ Rate for Unprojected TD Learning with Linear Function Approximation

Francesco Orabona; Wei-Cheng Lee

REVIEW 3 major objections 4 minor 2 cited by

A Robust $\widetilde{\mathcal{O}}(1/\sqrt{T})$ Rate for Unprojected TD Learning with Linear Function Approximation

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Projection-free TD(0) converges at the robust ~1/√T rate under Markovian noise

desk verdict First unprojected TD(0) robust rate looks real and important; the main stress-test worry is a misreading, though Lemma B.5 has a genuine conditional-expectation typo. read the letter →

arxiv 2506.01052 v3 pith:XCEBT2SS submitted 2025-06-01 cs.LG math.OCstat.ML

Wei-Cheng Lee , Francesco Orabona This is my paper · ORCID

classification cs.LGmath.OCstat.ML

keywords temporaldifferencelearninglinearfunctionapproximationMarkoviannoisefinite-timeanalysisprojection-freeTD(0)robustconvergencerateself-boundingiterates

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that plain TD(0) with linear function approximation converges in expectation at a rate of about $\|\theta^*\|_2^2/\sqrt{T}$ even when the data come from a single Markovian trajectory and the algorithm never projects its iterates. Prior finite-time analyses that avoided curvature assumptions needed a projection step to keep the iterates bounded, while projection-free analyses relied on a strong-convexity parameter that can be arbitrarily small. The paper identifies a self-bounding property of TD updates: with a stepsize of order $\log(t+3)/(\sqrt{t+1}\log T)$ and a sufficiently large constant, the expected squared norm of every iterate stays within $O(\max\{r_\infty^2/\phi_\infty^2, \|\theta^*\|^2\})$. This property is what allows the robust $1/\sqrt{T}$ rate to hold without projection, resolving in the affirmative an open question from earlier work. It matters because the robust rate is preferable when the problem's curvature is unknown or small, and the unprojected algorithm is what practitioners actually run.

What carries the argument

The load-bearing object is the self-bounding property of the TD update, formalized as Theorem D.1. For the stepsize $\eta_t = \frac{\log(t+3)}{c\phi_\infty^2\log T\sqrt{t+1}}$ with $c>281$ and horizon condition $\log T \ge (\log(2\sqrt T)/\log(1/\alpha)+1)^{3/4}$, the proof shows $E\|\theta_t\|_2^2 \le \rho_c^2 \max\{r_\infty^2/\phi_\infty^2, \|\theta^*\|_2^2\}$ by induction on the recursion for $E\|\theta_t-\theta^*\|_2^2$. The recursion decomposes the TD direction into a martingale difference, a Markovian bias term, and the mean-path update; the bias is controlled by waiting a mixing lag $s_k=\log(2\sqrt t)/\log(1/\alpha)$ after which $C\alpha^{s_k}\le 1/\sqrt t$. The potential $f(\theta)=(1-\gamma)\|V_\theta-V_{\theta^*}\|_D^2+\gamma\|V_\theta-V_{\theta^*}\|_{\mathrm{Dir}}^2$ carries the convergence measure because it makes the identity $\langle -\bar g(\theta),\theta-\theta^*\rangle=f(\theta)-f(\theta^*)$ exact rather than an inequality.

What would settle it

On a finite MDP with an irreducible aperiodic chain whose mixing parameter $\alpha$ is close to 1, choose $T$ satisfying the theorem's horizon condition and run unprojected TD(0) with $c$ just above 281; if any iterate has $E\|\theta_t\|_2^2 > \rho_c^2\max\{r_\infty^2/\phi_\infty^2, \|\theta^*\|_2^2\}$ before time $T$, the bounded-iterates theorem is false.

Watch

Extended reading notes

Core claim

The central discovery is that unprojected TD(0) has a self-bounding behavior: the expected squared distance of the iterates from the TD fixed point stays controlled by $\rho_c^2 \max\{r_\infty^2/\phi_\infty^2, \|\theta^*\|_2^2\}$ for all $t\le T$, where $\rho_c\to 2$ as the stepsize constant $c\to\infty$ and $\rho_c\to\infty$ as $c$ approaches the threshold $c>281$. From this, Theorem 4.2 proves that the averaged iterate $\bar\theta_T$ satisfies $$E\big[(1-\gamma)\|V_{\bar\theta_T}-V_{\$\theta$^*}\|$_D^{2}$ + \gamma\|V_{\bar\theta_T}-V_{\$\theta$^*}\|_{\mathrm{Dir}}^2\big] = \tilde O\!\left(\frac{c\$rho_c^{2}$\max\{r_\$infty^{2}$,\phi_\$infty^{2}$\|\$\theta$^*\|$_2^{2}$\}}{\sqrt T}\right).$$ The rate involves neither the minimal eigenvalue of $\Phi^\top D \Phi$ nor the curvature of the potential, and no projection step is used. The proof departs from contraction-based arguments and instead controls the bias induced by Markovian sampling through a mixing lag, then uses an induction to show the iterates cannot escape a bounded region.

Load-bearing premise

The argument assumes the policy's Markov chain is irreducible and aperiodic and forgets its past geometrically fast with known constants; if the chain mixes slowly, the theorem's horizon condition demands an astronomically large $T$.

Editorial extensions

If this is right

A user can run plain, projection-free TD(0) with the stated stepsize and obtain a $\tilde O(1/\sqrt T)$ convergence bound that does not require knowing or estimating the smallest curvature of the potential.
The bound depends on $\|\theta^*\|_2$ rather than on a projection radius $R\ge\|\theta^*\|_2$, so the algorithm no longer needs a user-chosen bounded set that contains the unknown solution.
Because the potential dominates $(1-\gamma)\|V_{\theta}-V_{\theta^*}\|_D^2$, the result also recovers the usual weighted squared-value error rate of projected TD.
The theorem closes the gap between fast rates that need curvature and robust rates that needed projections, at the price of only a polylogarithmic correction to the stepsize and a large-horizon condition tied to mixing.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Editorial inference: the same self-bounding induction should extend to TD($\lambda$) and Q-learning with linear approximation, as the paper suggests, but the Markovian bias argument will still require geometrically fast mixing with known constants.
Editorial inference: the large-horizon condition makes the guarantee practically relevant mainly for chains that mix quickly; for slowly mixing chains the required $T$ can be astronomically large, so the result is a proof-of-principle robustness rather than a recommendation for such regimes.
Editorial inference: when the potential actually has strong curvature, the $\tilde O(1/\sqrt T)$ rate is likely pessimistic; a parameter-free stepsize could plausibly interpolate to the $\tilde O(1/T)$ regime, which the paper lists as future work.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The headline: this paper proves the first finite-time O~(||θ*||^2/√T) rate for projection-free TD(0) with linear function approximation under Markovian noise, resolving an open question from Bhandari et al. (2018). The self-bounding iterate argument is genuinely new and not a repackaged projection or strong-convexity trick. I went through the proof carefully, and the central induction appears sound.

What is good: the bias decomposition with s_k = min(k, u_t) is the right tool. For the early segment k ≤ u_t, s_k = k, so the lagged term is exactly about θ_0, not an unjustified replacement. The stress-test worry that Lemma C.1 substitutes d_0ℓ_0 for d_kℓ_k without support does not survive contact with the text: it is d_{k−s_k}ℓ_{k−s_k}, which for k ≤ u_t is d_0ℓ_0 by definition. Later terms are controlled by the induction hypothesis and Lemma D.2. The architecture of the proof is coherent.

The real soft spots are smaller. Lemma B.5 is written incorrectly: it drops the conditional expectation in Ξ and proves the bound for the raw gradient g instead of E[g|F]. The constant is right, because the conditional expectation inherits the same Lipschitz constant in θ, but the displayed proof needs repair. The induction in Theorem D.1 only writes out the r∞/φ∞ ≤ d_0 case and says the other is similar; a referee will want that expanded. Table 1 contradicts the prose: it marks Bhandari et al.'s robust rate as "Without Projection", which is backwards. And the abstract simplifies the rate by dropping the max with the reward bound; the theorem statement is the honest version.

None of this breaks the main result. The proof is long and not machine-checked, but the pieces fit, and the self-bounding mechanism is worth understanding in its own right.

Who this is for: anyone working on finite-time RL theory, stochastic approximation, or TD analysis. It deserves a serious referee.

Recommendation: accept, with minor-to-moderate revisions focused on Lemma B.5 and Table 1.

Referee Report

3 major / 4 minor

Summary. The paper analyzes unprojected TD(0) with linear function approximation under Markovian sampling and proves a robust O~(1/sqrt(T)) convergence rate in expectation for the Liu-Olshevsky potential, without any projection step and without lower-bounding the curvature of the potential. The proof strategy is a self-bounding induction: the authors show that the expected squared norm of the iterates remains bounded by a constant that depends on the step-size scale parameter c, and then use this to control the bias and gradient terms in the error recursion. The main theorems are Theorem 4.2 (informal) and Theorem D.1 (formal bounded-iterates statement), with the rate following from the potential identity of Lemma 4.1. The paper also includes experiments on a synthetic MDP that qualitatively support the predicted phase transition in the step-size parameter.

Significance. If correct, this result resolves an open problem raised by Bhandari et al. (COLT 2018), giving the first finite-time robust rate for projection-free TD(0) with Markovian noise. The proof is genuinely novel: it avoids the contraction-based arguments of prior work and instead establishes a self-bounding property of the iterates, reminiscent of parameter-free SGD analyses. The paper is careful about constants and includes explicit expressions for the radius rho_c. I specifically checked the early-segment bound in Lemma C.1 that was flagged as a possible circularity; the concern does not land because the proof bounds d_{k-s_k} ell_{k-s_k}, and for k <= u_t one has s_k = k, so the quantity is exactly d0 ell_0, requiring no iterate bound. The main technical gap I found is in the proof of Lemma B.5, where the conditional-expectation definition of Xi is replaced by the raw stochastic gradient; this is load-bearing for Lemma C.1 but appears readily repairable.

major comments (3)

[Appendix B, Lemma B.5] The proof of Lemma B.5 is formally incorrect as written. The definition of Xi in Appendix A is Xi(theta_t, Z_t) = < E[g(theta_t, Z_t) | F_{t-1}] - gbar(theta_t), theta_t - theta* >, but the displayed first equality in the proof uses < g(theta_k, Z_k) - gbar(theta_k), theta_k - theta* >, omitting the conditional expectation. Since Lemma C.1 invokes Lemma B.5 to bound differences of Xi terms, this gap affects a load-bearing step. The statement itself is true and the fix is straightforward: one should apply the triangle inequality to the conditional-expectation version, use the almost-sure bound ||g(theta, o)|| <= ell_theta to control E[||g(theta, Z)|| | F], and use the fact that conditional expectation preserves the 2 phi_inf^2 Lipschitz property. Please rewrite the proof accordingly.
[Appendix C, Lemma C.1] In the first bias term, the proof silently replaces the conditioning sigma-field F_{k-1} by F_{k-1-s_k}. This equality is true, but it is not immediate and should be justified: theta_{k-s_k} is F_{k-1-s_k}-measurable, and by the Markov property the conditional distribution of Z_k given F_{k-1} is the same as that given F_{k-1-s_k} (and s_{k-s_k}). The text also uses F_{-1} for the early segment without defining it; F_{-1} should be declared as the trivial sigma-field. Without these clarifications, the proof of Lemma C.1 has a logical gap at the point where Lemma B.4 is applied.
[Appendix D, Theorem D.1] The induction hypothesis is stated as 'max_{i<=t} E[||theta_{i-1}||^2] <= rho_c^2 max{...}', which is ill-formed at the base case i=0 because theta_{-1} is not defined. It should be stated as 'max_{0 <= i <= t-1} E[||theta_i||^2] <= rho_c^2 max{...}'. Also, the proof only details the case r_infinity / phi_infinity <= d0 and says the other case is similar; this is acceptable, but the analogous beta_1, beta_2 definitions and the final fixed-point inequality for the alternative case should be given or at least clearly indicated to avoid an unverifiable 'similar' claim.

minor comments (4)

[Appendix A] The line 'F_t in sigma{Z_0,...,Z_t}' should be 'F_t = sigma{Z_0,...,Z_t}'.
[Section 4, proof of Theorem 4.2(b)] The lower bound on the sum of step sizes is written as >= 2 sqrt(T)/(c phi_inf^2 log^2(T+3)) in one place, but the preceding line gives the exact bound 2 sqrt(T) - 2 over the same denominator; the -2 term should be tracked or the inequality stated with the exact form.
[Appendix D, heading] The sentence 'We can now give the formal statement and prove part (b) in Theorem 4.2: Theorem D.1' is misleading, because Theorem D.1 is the formal bounded-iterates statement (part (a)), not the rate statement (part (b)). Please rephrase.
[Section 4, Theorem 4.2] The dependency on the mixing parameter alpha in the condition 'T sufficiently large' is stated only informally in Theorem 4.2; the precise condition in Theorem D.1 is log T >= (log(2 sqrt(T))/log(1/alpha) + 1)^{3/4}. Consider stating this condition (or a simplified sufficient condition) in the main theorem for clarity.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the convergence rate and bounded-iterates theorem are derived from explicit Markov-mixing and Lipschitz lemmas, not from the target statement.

full rationale

The derivation chain is self-contained against external benchmarks once Assumptions 1 and 2 are accepted. The robust rate in Theorem 4.2(b) is obtained by telescoping an explicit recurrence, using Lemma 4.1 (Liu and Olshevsky) to identify the potential decrement, Lemma 4.4-4.6 (Bhandari et al.) to bound gradients and Lipschitz constants, and Lemma C.1 to control the bias term under geometric mixing. The bounded-iterates property in Theorem D.1 is proved by a genuine induction: the induction hypothesis bounds E[||θ_i||^2] for i < t, Lemma D.2 controls cross terms, and the radius ρ_c is chosen to satisfy a fixed-point inequality rather than assumed from the conclusion. No parameter is fitted to the convergence quantity, and no target inequality is used as an input. The Liu-Olshevsky potential depends on θ* by definition, but that is the quantity being bounded, not a circular presupposition of the bound. The paper does cite work by co-author Orabona and Pál for an analogy in SGD and Cutkosky and Orabona in a future-work sentence, but these citations are not load-bearing evidence for the TD rate. The reviewer-flagged concern in Lemma C.1 about replacing d_k ℓ_k with d_0 ℓ_0 for early k is a potential correctness gap in the proof, not a circularity: it does not reduce the theorem to its own assumption, and under the task rules internal proof errors are outside the circularity verdict. Overall, no circular step can be exhibited from the paper's equations.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

All constants are explicit and analytic; no parameter is fitted to data. The only hand-chosen number is the step-size scale c, but the proof gives a threshold and the bound degrades predictably as c approaches the threshold. The central claim relies on standard domain assumptions (mixing, bounded features) and on two cited technical lemmas from prior work, neither authored by the present authors.

free parameters (1)

step-size scale c = c ≥ 281, theoretical threshold (279+3√8837)/2
A hand-chosen algorithmic constant in the stepsize η_t = log(t+3)/(c φ∞^2 log T √(t+1)). It is not fitted to data, but the theorem requires c > 281 and the bound's constants depend on ρ_c(c).

assumptions (4)

domain assumption Assumption 1: the policy-induced Markov chain is irreducible and aperiodic, with geometric mixing in Theorem 3.1
Used throughout Lemma C.1 to control the bias term via C α^{s_k} ≤ 1/√t; also enters the horizon condition in Theorem D.1.
domain assumption Assumption 2: feature matrix Φ has full column rank and ||φ(s)||_2 ≤ φ∞; rewards are bounded by r∞
Needed for the TD fixed point θ* to be unique and for all norm bounds on gradients and on ℓ_k in the proofs.
domain assumption Lemma 4.1 from Liu and Olshevsky [2021, Theorem 1]: < -gbar(θ), θ-θ* > = f(θ) - f(θ*)
This exact equality is the engine of the convergence analysis; the paper cites the lemma rather than proving it, and the cited work is not by the present authors.
standard math Lemmas 4.5 and 4.6 from Bhandari et al. [2018] bounding the mixing bias and giving Lipschitz continuity of g and gbar
Used in Lemma C.1 and in Lemmas B.4 and B.5 to decompose and bound the bias term; these are background technical results taken from prior work.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Robust $\widetilde{\mathcal{O}}(1/\sqrt{T})$ Rate for Unprojected TD Learning with Linear Function Approximation." pith.science (2026). https://pith.science/paper/XCEBT2SS

@misc{pith2026250601052,
  author       = {Pith},
  title        = {Pith review of: A Robust $\widetilde\mathcalO(1/\sqrtT)$ Rate for Unprojected TD Learning with Linear Function Approximation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XCEBT2SS}},
  note         = {Machine review of arXiv:2506.01052}
}

abstract

We investigate the finite-time convergence properties of Temporal Difference (TD) learning with linear function approximation, a cornerstone of reinforcement learning. We are interested in the so-called ``robust'' setting, where the convergence guarantee does not depend on the potential function's minimal curvature. While prior work has established convergence guarantees in this setting, these results typically rely on the artificial assumption that each iterate is projected onto a bounded set. Removing such a condition was left as an open problem by Bhandari et al. (COLT'18), hypothesizing the need for additional ``regularity conditions''. In this paper, we show that the simple unprojected TD(0) converges with a rate of $\widetilde{\mathcal{O}}\left(\frac{\|\theta^*\|^2_2}{\sqrt{T}}\right)$ in expectation, even in the presence of Markovian noise. We do not require an additional regularity condition, but only a minor polylog correction to the learning rate. Our analysis reveals a novel self-bounding property of the TD updates and exploits it to guarantee bounded iterates.

Figures

Figures reproduced from arXiv: 2506.01052 by the authors.

**Figure 1.** Sweep over the stepsize scale c (columns: boundedness ratio, divergence rate, suboptimality gap). Rows correspond to different feature scalings, which change the spectrum of Φ⊤DΦ (the plot annotates the minimum eigenvalue and condition number for each row). where R is a parameter of the algorithm and it must be chosen to satisfy R ≥ ∥θ ∗∥2 , where ∥θ ∗∥2 is unknown. Our result recovers the above bound since ∥Vθ − Vθ… view at source ↗

**Figure 2.** Sweep over the stepsize scale c (columns: boundedness ratio, divergence rate, suboptimality gap). Rows correspond to different feature scalings, which change the spectrum of Φ⊤DΦ (the plot annotates the minimum eigenvalue and condition number for each row). 24 [PITH_FULL_IMAGE:figures/full_fig_p024_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Fast and Robust Convergence Rate for TD(0) with Linear Function Approximation, Universal Learning Steps and I.I.D. Samples
stat.ML 2026-06 unverdicted novelty 7.0 of 10

Establishes an O(1/k) MSE convergence rate for TD(0) with LFA that is independent of the smallest eigenvalue of the uncentered covariance matrix and robust to ill-conditioning.
A Diffusion Approximation for Temporal-Difference Learning with Linear Features under Markovian Noise
stat.ML 2026-06 unverdicted novelty 6.0 of 10

Presents an SDE diffusion approximation for linear TD(0) under Markovian noise that explains the constant-stepsize error floor via interaction of long-run covariance and projected Bellman operator geometry.

Reference graph

Works this paper leans on

21 extracted references · 16 canonical work pages · cited by 2 Pith papers

[1]

A finite time analysis of temporal difference learning with linear function approximation

Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference on learning theory, pages 1691--1692. PMLR, 2018

work page 2018
[2]

Deepdriving: Learning affordance for direct perception in autonomous driving

Chenyi Chen, Ari Seff, Alain Kornhauser, and Jianxiong Xiao. Deepdriving: Learning affordance for direct perception in autonomous driving. In Proceedings of the IEEE international conference on computer vision, pages 2722--2730, 2015

work page 2015
[3]

Cutkosky and Francesco Orabona

Ashok. Cutkosky and Francesco Orabona. Black-box reductions for parameter-free online learning in Banach spaces. In Proc. of the Conference on Learning Theory (COLT), 2018

work page 2018
[4]

Finite sample analysis of two-timescale stochastic approximation with applications to reinforcement learning

Gal Dalal, Gugan Thoppe, Bal \'a zs Sz \"o r \'e nyi, and Shie Mannor. Finite sample analysis of two-timescale stochastic approximation with applications to reinforcement learning. In Conference On Learning Theory, pages 1199--1233. PMLR, 2018

work page 2018
[5]

Logarithmic Sobolev inequalities for finite Markov chains

Persi Diaconis and Laurent Saloff-Coste. Logarithmic Sobolev inequalities for finite Markov chains. The Annals of Applied Probability, 6 0 (3): 0 695--750, 1996

work page 1996
[6]

Deep reinforcement learning for robotic manipulation with asynchronous off-policy updates

Shixiang Gu, Ethan Holly, Timothy Lillicrap, and Sergey Levine. Deep reinforcement learning for robotic manipulation with asynchronous off-policy updates. In 2017 IEEE international conference on robotics and automation (ICRA), pages 3389--3396. IEEE, 2017

work page 2017
[7]

DoG is SGD 's best friend: A parameter-free dynamic step size schedule

Maor Ivgi, Oliver Hinder, and Yair Carmon. DoG is SGD 's best friend: A parameter-free dynamic step size schedule. In International Conference on Machine Learning, pages 14465--14499. PMLR, 2023

work page 2023
[8]

On TD (0) with function approximation: Concentration bounds and a centered variant with exponential convergence

Nathaniel Korda and Prashanth La. On TD (0) with function approximation: Concentration bounds and a centered variant with exponential convergence. In International conference on machine learning, pages 626--634. PMLR, 2015

work page 2015

Show all 21 references

[9]

Stochastic approximation: a survey

Harold Kushner. Stochastic approximation: a survey. Wiley Interdisciplinary Reviews: Computational Statistics, 2 0 (1): 0 87--96, 2010

2010
[10]

Linear stochastic approximation: How far does constant step-size and iterate averaging go? In International conference on artificial intelligence and statistics, pages 1347--1355

Chandrashekar Lakshminarayanan and Csaba Szepesvari. Linear stochastic approximation: How far does constant step-size and iterate averaging go? In International conference on artificial intelligence and statistics, pages 1347--1355. PMLR, 2018

2018
[11]

Markov chains and mixing times, volume 107

David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017

2017
[12]

Temporal difference learning as gradient splitting

Rui Liu and Alex Olshevsky. Temporal difference learning as gradient splitting. In International Conference on Machine Learning, pages 6905--6913. PMLR, 2021

2021
[13]

Reinforcement Learning: Foundations

Shie Mannor, Yishay Mansour, and Aviv Tamar. Reinforcement Learning: Foundations. -, 2022. URL https://sites.google.com/view/rlfoundations/home

2022
[14]

A simple finite-time analysis of TD learning with linear function approximation

Aritra Mitra. A simple finite-time analysis of TD learning with linear function approximation. IEEE Transactions on Automatic Control, 2024

2024
[15]

Approximate temporal difference learning is a gradient descent for reversible policies

Yann Ollivier. Approximate temporal difference learning is a gradient descent for reversible policies. arXiv preprint arXiv:1805.00869, 2018

2018 arXiv
[16]

Parameter-free stochastic optimization of variationally coherent functions

Francesco Orabona and David P\'al. Parameter-free stochastic optimization of variationally coherent functions. arXiv preprint arXiv:2102.00236, 2021

2021 arXiv
[17]

Mastering the game of go with deep neural networks and tree search

David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madelei...

2016
[18]

Finite-time error bounds for linear stochastic approximation and td learning

Rayadurgam Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation and td learning. In Conference on Learning Theory, pages 2803--2830. PMLR, 2019

2019
[19]

Learning to predict by the methods of temporal differences

Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning, 3: 0 9--44, 1988

1988
[20]

Analysis of temporal-diffference learning with function approximation

John Tsitsiklis and Benjamin Van Roy. Analysis of temporal-diffference learning with function approximation. Advances in neural information processing systems, 9, 1996

1996
[21]

L. Xiao. Dual averaging methods for regularized stochastic learning and online optimization. Journal of Machine Learning Research, 11: 0 2543--2596, 2010

2010

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

A finite time analysis of temporal difference learning with linear function approximation

Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference on learning theory, pages 1691--1692. PMLR, 2018

work page 2018

[2] [2]

Deepdriving: Learning affordance for direct perception in autonomous driving

Chenyi Chen, Ari Seff, Alain Kornhauser, and Jianxiong Xiao. Deepdriving: Learning affordance for direct perception in autonomous driving. In Proceedings of the IEEE international conference on computer vision, pages 2722--2730, 2015

work page 2015

[3] [3]

Cutkosky and Francesco Orabona

Ashok. Cutkosky and Francesco Orabona. Black-box reductions for parameter-free online learning in Banach spaces. In Proc. of the Conference on Learning Theory (COLT), 2018

work page 2018

[4] [4]

Finite sample analysis of two-timescale stochastic approximation with applications to reinforcement learning

Gal Dalal, Gugan Thoppe, Bal \'a zs Sz \"o r \'e nyi, and Shie Mannor. Finite sample analysis of two-timescale stochastic approximation with applications to reinforcement learning. In Conference On Learning Theory, pages 1199--1233. PMLR, 2018

work page 2018

[5] [5]

Logarithmic Sobolev inequalities for finite Markov chains

Persi Diaconis and Laurent Saloff-Coste. Logarithmic Sobolev inequalities for finite Markov chains. The Annals of Applied Probability, 6 0 (3): 0 695--750, 1996

work page 1996

[6] [6]

Deep reinforcement learning for robotic manipulation with asynchronous off-policy updates

Shixiang Gu, Ethan Holly, Timothy Lillicrap, and Sergey Levine. Deep reinforcement learning for robotic manipulation with asynchronous off-policy updates. In 2017 IEEE international conference on robotics and automation (ICRA), pages 3389--3396. IEEE, 2017

work page 2017

[7] [7]

DoG is SGD 's best friend: A parameter-free dynamic step size schedule

Maor Ivgi, Oliver Hinder, and Yair Carmon. DoG is SGD 's best friend: A parameter-free dynamic step size schedule. In International Conference on Machine Learning, pages 14465--14499. PMLR, 2023

work page 2023

[8] [8]

On TD (0) with function approximation: Concentration bounds and a centered variant with exponential convergence

Nathaniel Korda and Prashanth La. On TD (0) with function approximation: Concentration bounds and a centered variant with exponential convergence. In International conference on machine learning, pages 626--634. PMLR, 2015

work page 2015