Pith. sign in

REVIEW 3 minor 64 references

A diffusion approximation for TD learning separates the projected Bellman contraction from Markovian sampling effects and accounts for the constant-stepsize error floor.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.3

2026-06-26 22:20 UTC pith:AMIF6PQN

load-bearing objection The paper gives a clean SDE model for linear TD(0) that separates the projected Bellman contraction from Markovian sampling noise and writes the resulting stationary covariance explicitly.

arxiv 2606.18183 v1 pith:AMIF6PQN submitted 2026-06-16 stat.ML cs.LGmath.PR

A Diffusion Approximation for Temporal-Difference Learning with Linear Features under Markovian Noise

M. Forzo , E. Monzio Compagnoni , A. Russo , A. Pacchiano This is my paper
classification stat.ML cs.LGmath.PR
keywords temporal difference learningdiffusion approximationMarkovian noiselinear function approximationprojected Bellman operatorerror floorstochastic differential equationconstant stepsize
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper develops a stochastic differential equation model for temporal difference learning with linear features when the underlying data arrives from a Markov chain rather than independent samples. This approximation extends the classical ODE description, which only tracks average behavior, by including the random fluctuations that set the nonzero error level observed with fixed step sizes. It isolates the contraction produced by the projected Bellman operator from the diffusive influence of the Markov chain's long-run covariance. A reader would care because the model supplies an explicit mechanism for the persistent error that appears in practice and does not vanish as iterations continue. If the approximation holds, it supplies a tool for predicting how changes in features or chain statistics affect the final accuracy without driving the step size to zero.

Core claim

We introduce a stochastic differential equation approximation for linear TD(0) under Markovian noise. The resulting model distinguishes the contraction dynamics governed by the projected Bellman operator from the influence of Markovian sampling. As a consequence, the model explains the constant-stepsize error floor through the interaction between Markovian long-run covariance and the contraction geometry of the projected Bellman operator.

What carries the argument

The SDE approximation whose drift follows the projected Bellman operator while its diffusion term encodes the long-run covariance of the Markovian sampling process.

Load-bearing premise

The TD(0) process with linear features under Markovian noise admits a valid diffusion approximation that separates contraction from sampling effects at the scale of constant step sizes.

What would settle it

Run constant-stepsize TD(0) on a small Markov chain whose long-run covariance is known exactly, then compare the observed asymptotic error variance against the explicit formula derived from the SDE; a statistically significant mismatch at small but fixed step sizes would falsify the claim.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • The asymptotic error variance for constant-stepsize TD(0) is given by an explicit interaction between the long-run covariance matrix and the geometry of the projected Bellman operator.
  • The separation of drift and diffusion terms allows the mixing properties of the Markov chain to be analyzed independently of the contraction rate.
  • The model predicts how different linear feature maps change the error floor by altering the alignment between features and the covariance structure.
  • The approximation remains valid in the regime where the step size is small yet held fixed, capturing the balance that produces a nonzero steady-state error.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same diffusion limit could be derived for other linear RL algorithms such as SARSA or gradient TD to compare their error floors under identical Markovian conditions.
  • Feature selection procedures might be designed to minimize the quadratic form that couples the covariance to the contraction operator, thereby lowering the floor without changing the step size.
  • The framework suggests that adaptive step-size rules informed by online covariance estimates could reduce the interaction term and achieve lower error than any fixed step size.
  • Nonlinear extensions would require replacing the linear projected Bellman operator with a state-dependent contraction, but the separation between mean dynamics and sampling noise might still apply.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 3 minor

Summary. The paper develops a diffusion (SDE) approximation for the linear TD(0) algorithm with function approximation when the underlying samples are generated by a Markov chain. The approximation isolates the linear contraction induced by the projected Bellman operator from the additive driving noise whose covariance is the long-run covariance of the Markovian noise process; the resulting Ornstein-Uhlenbeck process is then used to characterize the stationary covariance (error floor) that persists under constant step size.

Significance. If the invariance-principle argument is rigorous, the work supplies a concrete continuous-time model that explains why the asymptotic error of constant-step-size TD depends on the interaction between the contraction geometry of the projected Bellman operator and the Markov chain’s long-run covariance. This separation is a useful addition to the existing ODE theory and could inform step-size selection and variance-reduction analyses in reinforcement learning.

minor comments (3)
  1. [§3] §3, Assumption 2.1: the mixing-rate condition on the Markov chain is stated only qualitatively; an explicit quantitative bound (e.g., on the spectral gap) would make the error term in the invariance principle easier to verify.
  2. [Eq. (12)] Eq. (12): the definition of the long-run covariance Σ appears after the SDE is written; moving the definition earlier would improve readability of the Lyapunov equation that follows.
  3. [Figure 2] Figure 2: the plotted trajectories are not labeled with the precise values of α and the feature dimension used; adding these parameters would allow direct comparison with the theoretical covariance formula.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary and significance assessment, as well as the recommendation of minor revision. The referee's description correctly identifies the separation between the projected Bellman contraction and the long-run covariance of the Markovian noise that our SDE approximation isolates. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The provided abstract and context describe the introduction of an SDE approximation for linear TD(0) that separates projected Bellman contraction from Markovian noise effects via standard invariance principles. No equations, derivations, self-citations, fitted parameters presented as predictions, or ansatzes are visible in the text. The central claim follows directly from the linear structure of TD and additive functional limits for Markov chains without reducing to its own inputs by construction. This is the most common honest finding for modeling papers whose core contribution is an approximation rather than a closed derivation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review based solely on abstract; full paper text unavailable so ledger is minimal and inferred from claim.

axioms (1)
  • domain assumption TD learning dynamics under Markovian noise admit a diffusion approximation separating contraction and sampling effects.
    This is the core modeling step asserted in the abstract.

pith-pipeline@v0.9.1-grok · 5644 in / 1054 out tokens · 30332 ms · 2026-06-26T22:20:37.743045+00:00 · methodology

0 comments
read the original abstract

Temporal difference (TD) learning with linear function approximation is a core method for policy evaluation. Its classical continuous-time description is an ordinary differential equation (ODE), which captures the asymptotic mean dynamics but neglects stochastic fluctuations determining the error floor. We introduce a stochastic differential equation (SDE) approximation for linear TD(0) under Markovian noise. The resulting model distinguishes the contraction dynamics governed by the projected Bellman operator from the influence of Markovian sampling. As a consequence, the model explains the constant-stepsize error floor through the interaction between Markovian long-run covariance and the contraction geometry of the projected Bellman operator.

Figures

Figures reproduced from arXiv: 2606.18183 by A. Pacchiano, A. Russo, E. Monzio Compagnoni, M. Forzo.

Figure 1
Figure 1. Figure 1: Numerical illustration of the TD–SDE weak approximation. The left panels compare mean paths in parameter space. The right panels report empirical estimates of E∥θk − θ ⋆ ∥ 2 and E∥Θkα − θ ⋆ ∥ 2 , with shaded empirical quantile bands over independent runs. variances. In particular, Γ(θ ⋆ ) identifies noisy directions, while P weights them by how slowly they are damped by the drift. Equivalently, the residua… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

64 extracted references · 4 canonical work pages · 1 internal anchor

  1. [1]

    IEEE Transactions on Automatic Control , volume=

    An Analysis of Temporal-Difference Learning with Function Approximation , author=. IEEE Transactions on Automatic Control , volume=

  2. [2]

    International Conference on Machine Learning (ICML) , year=

    On TD(0) with Function Approximation: Concentration Bounds and a Centered Variant , author=. International Conference on Machine Learning (ICML) , year=

  3. [3]

    Conference on Learning Theory (COLT) , year=

    A Finite Time Analysis of Temporal Difference Learning with Linear Function Approximation , author=. Conference on Learning Theory (COLT) , year=

  4. [6]

    Stochastic Approximation: A Dynamical Systems Viewpoint , author=

  5. [7]

    Stochastic Approximation and Recursive Algorithms and Applications , author=

  6. [8]

    Conference on Learning Theory (COLT) , year=

    Finite-time Error Bounds for Linear Stochastic Approximation and TD Learning , author=. Conference on Learning Theory (COLT) , year=

  7. [9]

    Proceedings of the 34th International Conference on Machine Learning (ICML) , series=

    Stochastic Modified Equations and Adaptive Stochastic Gradient Algorithms , author=. Proceedings of the 34th International Conference on Machine Learning (ICML) , series=

  8. [10]

    Journal of Machine Learning Research , volume=

    Stochastic Gradient Descent as Approximate Bayesian Inference , author=. Journal of Machine Learning Research , volume=

  9. [11]

    Machine Learning , volume=

    Learning to Predict by the Methods of Temporal Differences , author=. Machine Learning , volume=

  10. [12]

    Reinforcement learning:

    Sutton, Richard S and Barto, Andrew G , year =. Reinforcement learning:

  11. [15]

    Mathematical Statistics and Learning , volume=

    Optimal and Instance-dependent Guarantees for Markovian Linear Stochastic Approximation , author=. Mathematical Statistics and Learning , volume=

  12. [16]

    Advances in Neural Information Processing Systems , volume=

    Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms , author=. Advances in Neural Information Processing Systems , volume=

  13. [17]

    and Tweedie, Richard L

    Meyn, Sean P. and Tweedie, Richard L. , title =

  14. [18]

    and Meyn, Sean P

    Glynn, Peter W. and Meyn, Sean P. , title =. The Annals of Probability , volume =

  15. [19]

    Mil'shtein, G. N. , title =. Theory of Probability & Its Applications , volume =. 1986 , publisher =

    1986

  16. [20]

    Journal of Machine Learning Research , volume =

    Li, Qianxiao and Tai, Cheng and E, Weinan , title =. Journal of Machine Learning Research , volume =. 2019 , publisher =

    2019

  17. [21]

    Advances in Neural Information Processing Systems , year =

    Li, Zhiyuan and Malladi, Sadhika and Arora, Sanjeev , title =. Advances in Neural Information Processing Systems , year =

  18. [22]

    Information and Inference: A Journal of the IMA , volume =

    An, Jing and Lu, Jianfeng and Ying, Lexing , title =. Information and Inference: A Journal of the IMA , volume =. 2020 , publisher =

    2020

  19. [23]

    Advances in Neural Information Processing Systems , year =

    Malladi, Sadhika and Lyu, Kaifeng and Panigrahi, Abhishek and Arora, Sanjeev , title =. Advances in Neural Information Processing Systems , year =

  20. [24]

    Advances in Neural Information Processing Systems , volume =

    Orvieto, Antonio and Lucchi, Aurelien , title =. Advances in Neural Information Processing Systems , volume =

  21. [25]

    Has it Trained Yet? NeurIPS 2022 Workshop , year =

    Zhao, Jim and Lucchi, Aurelien and Proske, Frank Norbert and Orvieto, Antonio and Kersting, Hans , title =. Has it Trained Yet? NeurIPS 2022 Workshop , year =

    2022

  22. [26]

    Three Factors Influencing Minima in

    Jastrzebski, Stanis. Three Factors Influencing Minima in. International Conference on Artificial Neural Networks , year =

  23. [27]

    Zhou, Pan and Feng, Jiashi and Ma, Chao and Xiong, Caiming and Hoi, Steven C. H. and E, Weinan , title =. Advances in Neural Information Processing Systems 33 , pages =

  24. [28]

    Advances in Neural Information Processing Systems , year =

    Lucchi, Aurelien and Proske, Frank Norbert and Orvieto, Antonio and Bach, Francis and Kersting, Hans , title =. Advances in Neural Information Processing Systems , year =

  25. [29]

    International Conference on Machine Learning , pages =

    Compagnoni, Enea Monzio and Biggio, Luca and Orvieto, Antonio and Proske, Frank Norbert and Kersting, Hans and Lucchi, Aurelien , title =. International Conference on Machine Learning , pages =. 2023 , organization =

    2023

  26. [30]

    International Conference on Artificial Intelligence and Statistics , pages =

    Compagnoni, Enea Monzio and Orvieto, Antonio and Kersting, Hans and Proske, Frank Norbert and Lucchi, Aurelien , title =. International Conference on Artificial Intelligence and Statistics , pages =. 2024 , organization =

    2024

  27. [31]

    The Thirteenth International Conference on Learning Representations , year =

    Compagnoni, Enea Monzio and Liu, Tianlin and Islamov, Rustem and Proske, Frank Norbert and Orvieto, Antonio and Lucchi, Aurelien , title =. The Thirteenth International Conference on Learning Representations , year =

  28. [32]

    Proceedings of the 28th International Conference on Artificial Intelligence and Statistics , series =

    Compagnoni, Enea Monzio and Islamov, Rustem and Proske, Frank Norbert and Lucchi, Aurelien , title =. Proceedings of the 28th International Conference on Artificial Intelligence and Statistics , series =. 2025 , publisher =

    2025

  29. [33]

    The Fourteenth International Conference on Learning Representations , year =

    Compagnoni, Enea Monzio and Stanghellini, Alessandro and Islamov, Rustem and Lucchi, Aurelien and Koloskova, Anastasia , title =. The Fourteenth International Conference on Learning Representations , year =

  30. [34]

    International Conference on Machine Learning , year =

    Compagnoni, Enea Monzio and Islamov, Rustem and Proske, Frank Norbert and Lucchi, Aurelien and Orvieto, Antonio and Gorbunov, Eduard , title =. International Conference on Machine Learning , year =

  31. [35]

    Stochastic modified equations for the asynchronous stochastic gradient descent

    An, J., Lu, J., and Ying, L. Stochastic modified equations for the asynchronous stochastic gradient descent. Information and Inference: A Journal of the IMA, 9 0 (4): 0 851--873, 2020

    2020

  32. [36]

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

    Bhandari, J., Russo, D., and Singal, R. A finite time analysis of temporal difference learning with linear function approximation. In Conference on Learning Theory (COLT), 2018

    2018

  33. [37]

    Borkar, V. S. Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge University Press, 2008

    2008

  34. [38]

    M., Biggio, L., Orvieto, A., Proske, F

    Compagnoni, E. M., Biggio, L., Orvieto, A., Proske, F. N., Kersting, H., and Lucchi, A. An SDE for modeling SAM : Theory and insights. In International Conference on Machine Learning, pp.\ 25209--25253. PMLR, 2023

    2023

  35. [39]

    M., Orvieto, A., Kersting, H., Proske, F

    Compagnoni, E. M., Orvieto, A., Kersting, H., Proske, F. N., and Lucchi, A. SDE s for minimax optimization. In International Conference on Artificial Intelligence and Statistics, pp.\ 4834--4842. PMLR, 2024

    2024

  36. [40]

    M., Islamov, R., Proske, F

    Compagnoni, E. M., Islamov, R., Proske, F. N., and Lucchi, A. Unbiased and sign compression in distributed learning: Comparing noise resilience via SDE s. In Proceedings of the 28th International Conference on Artificial Intelligence and Statistics, volume 258 of Proceedings of Machine Learning Research, pp.\ 4087--4095. PMLR, 2025 a . URL https://proceed...

    2025

  37. [41]

    M., Liu, T., Islamov, R., Proske, F

    Compagnoni, E. M., Liu, T., Islamov, R., Proske, F. N., Orvieto, A., and Lucchi, A. Adaptive methods through the lens of SDE s: Theoretical insights on the role of noise. In The Thirteenth International Conference on Learning Representations, 2025 b . URL https://openreview.net/forum?id=ww3CLRhF1v

    2025

  38. [42]

    M., Islamov, R., Proske, F

    Compagnoni, E. M., Islamov, R., Proske, F. N., Lucchi, A., Orvieto, A., and Gorbunov, E. On the interaction of noise, compression, and adaptivity under (l_0,l_1) -smoothness: An SDE approach. In International Conference on Machine Learning, 2026 a

    2026

  39. [43]

    M., Stanghellini, A., Islamov, R., Lucchi, A., and Koloskova, A

    Compagnoni, E. M., Stanghellini, A., Islamov, R., Lucchi, A., and Koloskova, A. Adaptive methods are preferable in high privacy settings: An SDE perspective. In The Fourteenth International Conference on Learning Representations, 2026 b . URL https://openreview.net/forum?id=hSpA4DAoMk

    2026

  40. [44]

    Glynn, P. W. and Meyn, S. P. A liapunov bound for solutions of the poisson equation. The Annals of Probability, 24 0 (2): 0 916--931, 1996

    1996

  41. [45]

    Three factors influencing minima in SGD

    Jastrzebski, S., Kenton, Z., Arpit, D., Ballas, N., Fischer, A., Bengio, Y., and Storkey, A. Three factors influencing minima in SGD . In International Conference on Artificial Neural Networks, 2018

    2018

  42. [46]

    and Prashanth, L

    Korda, N. and Prashanth, L. A. On td(0) with function approximation: Concentration bounds and a centered variant. In International Conference on Machine Learning (ICML), 2015

    2015

  43. [47]

    Kushner, H. J. and Yin, G. G. Stochastic Approximation and Recursive Algorithms and Applications. Springer, 2 edition, 2003

    2003

  44. [48]

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

    Lee, W.-C. and Orabona, F. A finite-time analysis of td learning with linear function approximation without projections or strong convexity. arXiv preprint arXiv:2506.01052, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  45. [49]

    Stochastic modified equations and adaptive stochastic gradient algorithms

    Li, Q., Tai, C., and E, W. Stochastic modified equations and adaptive stochastic gradient algorithms. In Proceedings of the 34th International Conference on Machine Learning (ICML), volume 70 of Proceedings of Machine Learning Research, pp.\ 2101--2110, 2017

    2017

  46. [50]

    Stochastic modified equations and dynamics of stochastic gradient algorithms I : Mathematical foundations

    Li, Q., Tai, C., and E, W. Stochastic modified equations and dynamics of stochastic gradient algorithms I : Mathematical foundations. Journal of Machine Learning Research, 20 0 (1): 0 1474--1520, 2019

    2019

  47. [51]

    On the validity of modeling SGD with stochastic differential equations ( SDE s)

    Li, Z., Malladi, S., and Arora, S. On the validity of modeling SGD with stochastic differential equations ( SDE s). In Advances in Neural Information Processing Systems, 2021

    2021

  48. [52]

    N., Orvieto, A., Bach, F., and Kersting, H

    Lucchi, A., Proske, F. N., Orvieto, A., Bach, F., and Kersting, H. On the theoretical properties of noise correlation in stochastic optimization. In Advances in Neural Information Processing Systems, 2022

    2022

  49. [53]

    On the SDEs and scaling rules for adaptive gradient algorithms

    Malladi, S., Lyu, K., Panigrahi, A., and Arora, S. On the SDEs and scaling rules for adaptive gradient algorithms. In Advances in Neural Information Processing Systems, 2022

    2022

  50. [54]

    D., and Blei, D

    Mandt, S., Hoffman, M. D., and Blei, D. M. Stochastic gradient descent as approximate bayesian inference. Journal of Machine Learning Research, 18 0 (134): 0 1--35, 2017

    2017

  51. [55]

    Meyn, S. P. and Tweedie, R. L. Markov Chains and Stochastic Stability. Cambridge University Press, 2 edition, 2009

    2009

  52. [56]

    Mil'shtein, G. N. Weak approximation of solutions of systems of stochastic differential equations. Theory of Probability & Its Applications, 30 0 (4): 0 750--766, 1986

    1986

  53. [57]

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

    Mitra, A. A simple finite-time analysis of td learning with linear function approximation. arXiv preprint arXiv:2403.02476, 2024

    work page arXiv 2024

  54. [58]

    J., Bartlett, P

    Mou, W., Pananjady, A., Wainwright, M. J., Bartlett, P. L., and Srikant, R. Optimal and instance-dependent guarantees for markovian linear stochastic approximation. Mathematical Statistics and Learning, 7: 0 41--153, 2024

    2024

  55. [59]

    Least squares regression with markovian data: Fundamental limits and algorithms

    Nagaraj, D., Wu, X., Bresler, G., Jain, P., and Netrapalli, P. Least squares regression with markovian data: Fundamental limits and algorithms. In Advances in Neural Information Processing Systems, volume 33, pp.\ 16666--16676, 2020

    2020

  56. [60]

    and Lucchi, A

    Orvieto, A. and Lucchi, A. Continuous-time models for stochastic optimization algorithms. In Advances in Neural Information Processing Systems, volume 32, 2019

    2019

  57. [61]

    Statistical inference for linear stochastic approximation with markovian noise

    Samsonov, S., Sheshukova, M., Moulines, E., and Naumov, A. Statistical inference for linear stochastic approximation with markovian noise. arXiv preprint arXiv:2505.19102, 2025

    work page arXiv 2025

  58. [62]

    Rates of convergence in the central limit theorem for markov chains, with an application to td learning

    Srikant. Rates of convergence in the central limit theorem for markov chains, with an application to td learning. arXiv preprint arXiv:2401.15719, 2026

    work page arXiv 2026

  59. [63]

    and Ying, L

    Srikant, R. and Ying, L. Finite-time error bounds for linear stochastic approximation and td learning. In Conference on Learning Theory (COLT), 2019

    2019

  60. [64]

    Sutton, R. S. Learning to predict by the methods of temporal differences. Machine Learning, 3 0 (1): 0 9--44, 1988

    1988

  61. [65]

    Sutton, R. S. and Barto, A. G. Reinforcement learning: An introduction . MIT press, 2018

    2018

  62. [66]

    Tsitsiklis, J. N. and Van Roy, B. An analysis of temporal-difference learning with function approximation. IEEE Transactions on Automatic Control, 42 0 (5): 0 674--690, 1997

    1997

  63. [67]

    N., Orvieto, A., and Kersting, H

    Zhao, J., Lucchi, A., Proske, F. N., Orvieto, A., and Kersting, H. Batch size selection by stochastic optimal control. In Has it Trained Yet? NeurIPS 2022 Workshop, 2022

    2022

  64. [68]

    Zhou, P., Feng, J., Ma, C., Xiong, C., Hoi, S. C. H., and E, W. Towards theoretically understanding why SGD generalizes better than Adam in deep learning. In Advances in Neural Information Processing Systems 33, pp.\ 21285--21296, 2020

    2020