A Diffusion Approximation for Temporal-Difference Learning with Linear Features under Markovian Noise Mattia Forzo 1 Enea Monzio Compagnoni * 2 Alessio Russo * 3 Aldo Pacchiano 3
arXiv:2606.18183v1 [stat.ML] 16 Jun 2026
Abstract
Finite-time analyses keep the discrete recursion and give non-asymptotic error bounds under i.i.d. or Markovian data (Korda & Prashanth (2015); Bhandari et al. (2018); Srikant & Ying (2019); Mitra (2024); Lee & Orabona (2025); Mou et al. (2024)). Such bounds typically have the form “decaying transient plus an O(α) variance floor”. Recent advances also provide refined statistical and inference guarantees for linear stochastic approximation under Markovian noise (Samsonov et al. (2025)).
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.
Our aim is complementary: we introduce a non-asymptotic continuous-time model that explains the leading stochastic term producing this floor. The tool we bring to bear is the SDE approximation of stochastic algorithms, a now well-established viewpoint whose modern, non-asymptotic form rests on the weak (distributional) approximation theory for numerical SDE schemes (Mil’shtein (1986)). Building on this, Li et al. (2017; 2019) introduced stochastic modified equations: SDEs whose drift and diffusion are fixed by matching the leading one-step moments of the algorithm, approximating the law of the iterates—rather than their sample paths—up to an error controlled by the stepsize. Within this framework, SGD is modeled as a diffusion whose covariance is set by the gradient-noise statistics (Mandt et al. (2017)), and the regime in which such SDEs faithfully track the optimizer has itself been characterized (Li et al. (2021)). The machinery extends beyond vanilla SGD to asynchronous SGD, adaptive methods such as RMSprop and Adam, sharpness-aware minimization, minimax optimization, distributed and compressed training, differentially private training, and optimization under (L0 , L1 )smoothness (An et al., 2020; Malladi et al., 2022; Compagnoni et al., 2023; 2024; 2025b;a; 2026b;a).
1. Introduction and related work TD learning is a central algorithm for policy evaluation in reinforcement learning (Sutton (1988); Sutton & Barto (2018)), with a long line of theoretical analyses. With linear features and a fixed policy, the asymptotic behavior of TD-learning for policy evaluation is described as a deterministic dynamical system by the linear ODE θ̇ = b − Aθ,
(1)
which is at the heart of classical stochastic-approximation analysis of TD (Tsitsiklis & Van Roy (1997); Kushner & Yin (2003); Borkar (2008); Mou et al. (2024); Samsonov et al. (2025)). The ODE approach proves where TD should go, but, by construction, it cannot capture higher-order effects.
Beyond serving as approximations, these models are also analysis and design tools: they have been used with stochastic-control arguments to select learning rates and batch sizes (Li et al. (2017; 2019); Zhao et al. (2022)), to derive scaling laws tying hyperparameters to the batch size and other noise sources (Jastrzebski et al. (2018); Malladi et al. (2022); Compagnoni et al. (2025b;a)), and to obtain convergence bounds, stationary approximations, and Lyapunovstyle stability arguments for the loss dynamics (Orvieto & Lucchi (2019); Compagnoni et al. (2023; 2024; 2025b; 2026a)). Non-Gaussian variants—Lévy-driven (Zhou et al.
* Equal contribution; 1 Technical University of Munich (TUM), Munich, Germany 2 University of Basel, Basel, Switzerland 3 Boston University, Boston, USA. Correspondence to: Mattia Forzo <[email protected]>.
Accepted at ICML 2026 Workshop on Decision-Making from Offline Datasets to Online Adaptation: Black-Box Optimization to Reinforcement Learning.
1
A Diffusion Approximation for Linear TD Learning under Markovian Noise
(2020)) and fractional-Brownian (Lucchi et al. (2022)) formulations—capture phenomena beyond Brownian diffusion at the cost of more specialized assumptions. Across all of these settings, the recurring payoff is the same: the diffusion term exposes how algorithmic noise interacts with the geometry of the problem, something the underlying ODE cannot see. We bring this viewpoint to reinforcement learning, where the driving noise is Markovian rather than i.i.d.; identifying the correct long-run covariance is precisely what makes a weak SDE approximation of TD possible. Through this lens, we complement existing admissible-stepsize guarantees for linear TD and recover recent non-asymptotic central-limit behavior for Markovian recursions (Srikant (2026)).
on-policy setting, positive stability follows from full column rank of the feature matrix in L2 (µ) (Tsitsiklis & Van Roy, 1997). Assumption (A3) is the same stability condition that makes the ODE converge to θ⋆ . Markov decision process. We consider policy evaluation for a fixed policy. The policy induces a finite-state irreducible and aperiodic Markov chain (Sk )k≥0 with stationary distribution µ. Rewards may be random; we assume that Rk+1 is conditionally independent of the past given (Sk , Sk+1 ), with law depending only on the transition (Sk , Sk+1 ). Thus, the observation driving the TD update Zk = (Sk , Sk+1 , Rk+1 ) is itself a Markov chain. We denote by PZm its m-step transition kernel, i.e. PZm (z, A) = P(Zk+m ∈ A | Zk = z). PZ denotes PZ1 . Its mixing behavior is inherited from the state chain (Sk ), since the reward component does not introduce additional temporal dependence beyond (Sk , Sk+1 ). We use ϱ(m) := supz ∥PZm (z, ·) − ν∥TV to denote its mixing profile, where ν denotes the stationary law of (Zk ).
We analyze the constant stepsize case, from which the classical Robbins–Monro regime follows by considering vanishing diffusion. For stepsize α, the ODE captures the O(1) drift of TD, √ while random fluctuations around that drift are of order α. A more natural object at this scale is therefore an SDE: √ dΘt = (b − AΘt ) dt + α B(Θt ) dWt , (2) B(θ)B(θ)⊤ = Γ(θ).
Temporal difference learning. Let ϕ : S → Rd be a feature map, γ ∈ [0, 1), and Vθ (s) = ϕ(s)⊤ θ. TD(0) with constant stepsize α is
The change is not merely notational. Compared to the classical ODE (1), a new term B appears. This is the term encoding the information about the noise and whose study lets us answer questions such as: How does Markovian sampling influence TD? Which feature map or policy produces less long-run TD noise? What is the variance dynamics? Moreover, the ODE path is encoded in the drift coefficient of the SDE, so that the ODE emerges from taking the expectation of the SDE.
θk+1 = θk + α Rk+1 + γϕ(Sk+1 )⊤ θk − ϕ(Sk )⊤ θk ϕ(Sk ).
(3)
For z = (s, s′ , r), write b̂(z) = r ϕ(s),
Â(z) = ϕ(s)(ϕ(s) − γϕ(s′ ))⊤ ,
and define H(θ, z) = b̂(z) − Â(z)θ, b = Eν [b̂(Z)],
Contributions. While prior work characterizes either asymptotic behavior via ODEs or finite-time bounds via discrete analysis, our approach provides a unified continuoustime stochastic model capturing both drift and fluctuations at finite time, adding interpretability to the known finite-time results. Technically, we use the Markov-chain Poisson equation to decompose correlated TD noise into a martingale term plus a telescoping coboundary. This identifies the diffusion covariance as the long-run covariance of the TD noise. We also construct an affine factor B(θ) of this covariance. Finally, we derive stability and local Gaussian estimates that turn the diffusion approximation into a diagnostic.
h(θ) = b − Aθ,
A = Eν [Â(Z)],
where ν denotes the stationary law of Zk . The TD fixed point is θ⋆ = A−1 b when A is nonsingular.
3. From TD discrete recursion to an SDE The goal of this section is to construct a continuous-time stochastic model that captures both the mean dynamics and the leading-order fluctuations of the TD recursion. While classical ODE methods describe only the average behavior, they fail to account for the stochastic effects that determine the steady-state error. To address this limitation, we introduce a diffusion approximation in the form of a stochastic differential equation (SDE).
2. Assumptions and problem setting
Specifically, we derive an order-1 weak approximation of the TD iterates in the sense of Li et al. (2017), namely:
Assumptions. (A1) The chain (Sk ) is finite, irreducible, and aperiodic. (A2) Features and rewards are bounded: ∥ϕ(s)∥ ≤ Kϕ and |r| ≤ KR . (A3) A is positive stable, i.e. every eigenvalue of A has positive real part; equivalently, the ODE matrix −A is Hurwitz. In the standard discounted
max 0≤k≤T /α
|Eφ(θk ) − Eφ(Θkα )| ≤ Cα, φ sufficiently regular.
2
A Diffusion Approximation for Linear TD Learning under Markovian Noise Table 1. Comparison of stepsize conditions in finite-time analyses of TD/linear SA under Markovian noise.
Work
Without projection
Not explicit function of tmix
Not function of horizon T
✓ × ✓ ✓ ✓ ✓ ✓
× × × × × ✓ ✓
× ✓ × ✓ × × ✓
Korda & Prashanth (2015) Bhandari et al. (2018) Srikant & Ying (2019) Mitra (2024) Mou et al. (2024) Lee & Orabona (2025) This work
Remarkably, sufficiently regular is not very restrictive. For example, all polynomials are included, so all moments can be compared. We refer to Section C for details.
Effective covariance. The effective covariance field is Γ(θ) = Eπ (uθ (Z1 ) − PZ uθ (Z0 )) (6) · (uθ (Z1 ) − PZ uθ (Z0 ))⊤ .
Main challenges. Deriving such a model presents three main challenges. First, the update noise in TD is Markovian and therefore temporally correlated, preventing a direct application of standard diffusion approximations developed for i.i.d. noise. Second, the diffusion term must capture the cumulative effect of these correlations. Third, the SDE must remain well-posed even when this covariance is singular, necessitating a suitable factorization of the covariance.
Equivalently, if Cm (θ) = Eπ [gθ (Z0 )gθ (Zm )⊤ ], then X Γ(θ) = C0 (θ) + Cm (θ) + Cm (θ)⊤ .
If the data were i.i.d., all lag terms would vanish and Γ(θ) would reduce to the one-step covariance. The lag terms in (7) are the mathematical record of temporal dependence. They can either inflate or reduce the diffusion depending on the sign of the correlations, while slow mixing makes more terms contribute to the sum. Proposition 3.1 (Mixing controls quadratic forms of the diffusion). Under (A1)–(A2), there are constants c0 , c1 > 0 depending only on the bounded TD components such that, for every θ ∈ Rd and every M ⪰ 0,
Approach. We address these challenges as follows. Using the Poisson equation associated with the underlying Markov chain, we decompose the TD noise into a martingale component and a telescoping coboundary term, which allows us to isolate the effective diffusion covariance Γ(θ). We then construct an affine factorization B(θ) such that B(θ)B(θ)⊤ = Γ(θ), ensuring sufficient regularity of the SDE coefficients. This construction is crucial to guarantee well-posedness even when Γ(θ) is singular.
tr(M Γ(θ)) ≤ tr(M ) τcorr (c0 + c1 ∥θ∥)2 , X τcorr = 1 + 4 ϱ(m).
Moreover, τcorr is equivalent, up to universal constants, to the usual total-variation mixing time tmix (1/4). A proof of Proposition 3.1 is given in Section D. We remark that τcorr < ∞ by (A1).
Let
gθ (z) = H(θ, z) − h(θ),
(8)
m≥1
We conclude the section by stating a theorem that formalizes the weak convergence of the TD iterates to the solution of the SDE (2). Poisson decomposition.
(7)
m≥1
Eπ [gθ (Z)] = 0.
Worst-direction and total noise. Proposition 3.1 gives, by taking M = vv ⊤ , ∥Γ(θ)∥op ≤ τcorr (c0 +c1 ∥θ∥)2 , while M = Id yields tr(Γ(θ)) ≤ d τcorr (c0 + c1 ∥θ∥)2 . The first quantity is the largest directional variance of the TD noise, whereas the second is the total injected variance. Since ∥Γ(θ)∥op ≤ tr(Γ(θ)) ≤ d ∥Γ(θ)∥op , the gap between the two measures how spread out the noise is across parameter directions. This motivates tr(Γ(θ)) deff (θ) := ∈ [1, d], (9) ∥Γ(θ)∥op
For each fixed θ, let uθ be the centered solution of the Poisson equation uθ − PZ uθ = gθ .
(4)
Then the TD noise admits the decomposition gθk (Zk ) = uθk (Zk ) − uθk (Zk+1 ) + ξk+1 , ξk+1 = uθk (Zk+1 ) − PZ uθk (Zk ),
(5)
where (ξk+1 ) is a martingale difference. The first two terms in (5) form a coboundary. This is the step that converts Markovian correlation into a martingale diffusion without assuming independent samples. For details, refer to Section C.
whenever Γ(θ) ̸= 0. Thus τcorr controls the worst-direction amplitude, while deff (θ) measures how many directions are effectively noisy. 3
A Diffusion Approximation for Linear TD Learning under Markovian Noise
One may take ρA ∝ 1/λmax (P ), while CA depends on the condition number of P , the linear-growth constant of B, and the norm of the bounded TD components.
A Lipschitz diffusion coefficient. The effective covariance Γ(θ) aggregates temporally correlated noise and may be singular (see Section E), so its principal square root need not be Lipschitz. For the SDE to serve as a stable and interpretable continuous-time proxy for the TD iterates, its drift and diffusion coefficients should have such regularity. To this end, we construct an affine factor B(θ).
This recovers the usual constant-stepsize TD picture. The added information is the interpretation of the error floor. Finite-time TD analyses prove upper bounds with comparable ingredients; the SDE explains why those ingredients appear. A proof of Theorem 3.4 is presented in Section F. Remark 3.5 (Removing localization a posteriori). The stopping in Theorem 3.3 is a technical localization device used to obtain uniform weak-error estimates on bounded sets. It is not part of the final SDE model. The localization can be removed a posteriori; see Section G for a rigorous proof and a brief discussion of the impact this has on the standard analysis pipeline.
Proposition 3.2 (Affine factorization with sparsity bound). Assume (A1)–(A2). Let n be the number of states and κ := maxs |{s′ : P π (s′ | s) > 0}|. Then, there exists an integer q ≤ min {d(d + 1), 2nκ} and an affine map d
d×q
B:R →R
,
B(θ) = B0 +
d X
θ i Bi ,
(10)
i=1
such that Γ(θ) = B(θ)B(θ)⊤ for all θ. Hence, B is globally Lipschitz and has linear growth.
Insights into stepsize choice. The stepsize parameter α in Theorem 3.4 is the same constant stepsize as in the TD recursion. Hence, the SDE stability bound directly translates into the TD regime: for sufficiently small stepsize α, the iterates remain stable and concentrate in an O(α) neighborhood of the TD fixed point. Table 1 places this condition in context with representative finite-time guarantees for linear TD under Markovian noise. The table should be read with some qualifications. These are discussed in Section H.
The explicit construction of such B(θ), along with its probabilistic interpretation, is given in Section E. The SDE model for TD. Theorem 3.3 (TD–SDE weak approximation). Assume (A1)–(A3). Fix T, R < ∞ and let θkR , ΘR kα denote the stopped TD recursion and the stopped SDE (2) when they leave the ball {∥θ∥ ≤ R}, respectively. Then, for every sufficiently regular test function φ, max 0≤k≤T /α
Finally, we state a comprehensive result on the noise structure of TD. We prove finite-time estimates on how far the SDE of TD is from being an Ornstein-Uhlenbeck process and provide an explicit evolution equation of the covariance.
Eφ(θkR ) − Eφ(ΘR kα ) ≤ CT,R α.
Theorem 3.6 (Local Gaussian and covariance dynamics). √ Assume (A1)–(A3). Let Xtα = (Θt − θ⋆ )/ α with 2 sup(0,α] E ∥X0α ∥ < ∞. On every finite interval [0, T ], there exists a constant CT < ∞, independent of α ∈ (0, 1], such that 1/2 √ α. (12) sup ∥Xtα − Gt ∥L2 ≤ CT
Theorem 3.3 makes rigorous the statement ”the SDE models TD”: the SDE (2) is a weak approximation of the discrete TD recursion, i.e. the law of the SDE sampled at matching time kα is close to the law of the discrete iterate θk . A proof of this fact along with a recipe to reproduce it for general discrete recursions can be found in Section C.
0≤t≤T
3.1. Consequences: stability and Gaussian structure
where G is the Ornstein–Uhlenbeck process
An immediate payoff of the SDE formulation is that stability and covariance analysis become continuous-time calculations. Let P = P ⊤ ≻ 0 solve the Lyapunov equation A⊤ P + P A = I. The conditioning of this matrix measures how strongly the drift contracts, appearing as the constant in the deterministic part of the estimate below.
dGt = −AGt dt + B(θ⋆ ) dWt ,
(13)
Hence the leading covariance Σt = Cov(Gt ) satisfies Σ̇t = −AΣt − Σt A⊤ + Γ(θ⋆ ).
Theorem 3.4 (SDE stability and finite-time error). Assume (A1)–(A3) and let B be the affine factor in (10). The SDE (2) has a unique global strong solution for every α > 0. Moreover, for sufficiently small α and Et = Θt − θ⋆ : 2 2 E ∥Et ∥ ≤ CA e−ρA t E ∥E0 ∥ + CA α τcorr d¯eff ,
G0 = X0α .
(14)
If (A3) holds, Σt converges to the unique solution of AΣ + ΣA⊤ = Γ(θ⋆ ). Theorem 3.6, whose proof is given in Section I, shows that near the fixed point TD errors are locally Gaussian. In particular, the covariance equation identifies both the size and the geometry of the constant-stepsize error floor. At stationarity, different directions can have different residual
(11)
tr(Γ(θ)) where d¯eff := supθ:Γ(θ)̸=0 ∥Γ(θ)∥ ≤ d. op
4
A Diffusion Approximation for Linear TD Learning under Markovian Noise
1.25
Trajectory - Biased Ring TD SDE
Distance to Optimum - Biased Ring
θ0
10
1.00
TD: ‖θk − θ ⋆ ‖2
SDE: ‖Θkα − θ ⋆ ‖2
0
‖θ − θ ⋆ ‖2
0.75
θ2
0.50 0.25 0.00
θ⋆
10−1
10−2
−0.25 −0.50 0.5
1.0
0
1.5
θ1
10000
Iterate k
15000
(b) Empirical mean squared distance to θ⋆ .
(a) Empirical mean parameter trajectory.
Trajectory - Directed Cycle 1.25
5000
TD SDE
Distance to Optimum - Directed Cycle
θ0
TD: ‖θk − θ ⋆ ‖2
100
SDE: ‖Θkα − θ ⋆ ‖2
‖θ − θ ⋆ ‖2
1.00
θ2
0.75 0.50 0.25 0.00 −0.25
θ⋆
0.0
10−1
10−2
10−3
0.5
θ1
1.0
1.5
0
10000
20000
Iterate k
30000
(d) Empirical mean squared distance to θ⋆ .
(c) Empirical mean parameter trajectory.
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 residual variance is governed by the alignment between Markovian noise and weakly contracting directions.
making explicit stability, covariance dynamics, and distributional properties that are otherwise inaccessible. The framework also provides a diagnostic view of admissible stepsize regimes. The technical contributions are the identification of the long-run covariance Γ(θ), the quantification of its dependence on mixing, and the construction of the affine factor B(θ).
Numerical verification. Figure 1 compares TD with the global TD–SDE on two finite Markov reward processes. The agreement is assessed at the ensemble level, consistent with the weak approximation in Theorem 3.3; full experimental details and trajectory plots are deferred to Section J.
Limitations and extensions. The present version assumes bounded rewards and features. This makes error bounds more straightforward; extending the analysis to finite second moments appears natural. Further natural extensions include analysis of other reinforcement learning algorithms and general stochastic approximation methods.
4. Scope and conclusion The present note introduces an SDE modeling framework for TD(0) with linear function approximation under Markovian noise. It generalizes the classical ODE description and adds interpretability to discrete finite-time bounds by 5
A Diffusion Approximation for Linear TD Learning under Markovian Noise
Impact Statement
compression, and adaptivity under (l0 , l1 )-smoothness: An SDE approach. In International Conference on Machine Learning, 2026a.
This paper presents theoretical work aimed at advancing the foundations of machine learning and stochastic approximation. It introduces tools for analyzing the stochastic dynamics of reinforcement-learning algorithms and does not involve datasets, deployed systems, or direct user-facing applications. Its likely impact is methodological: it may help researchers understand variance, stability, and covariance structure in TD and related stochastic approximation algorithms. We do not identify direct negative societal impacts beyond those associated with the downstream systems to which such algorithms may be applied.
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, 2026b. URL https://openreview. net/forum?id=hSpA4DAoMk. Glynn, P. W. and Meyn, S. P. A liapunov bound for solutions of the poisson equation. The Annals of Probability, 24(2): 916–931, 1996. 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.
References 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(4):851–873, 2020.
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.
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.
Kushner, H. J. and Yin, G. G. Stochastic Approximation and Recursive Algorithms and Applications. Springer, 2 edition, 2003.
Borkar, V. S. Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge University Press, 2008.
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.
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.
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.
Compagnoni, E. M., Orvieto, A., Kersting, H., Proske, F. N., and Lucchi, A. SDEs for minimax optimization. In International Conference on Artificial Intelligence and Statistics, pp. 4834–4842. PMLR, 2024. Compagnoni, E. M., Islamov, R., Proske, F. N., and Lucchi, A. Unbiased and sign compression in distributed learning: Comparing noise resilience via SDEs. In Proceedings of the 28th International Conference on Artificial Intelligence and Statistics, volume 258 of Proceedings of Machine Learning Research, pp. 4087–4095. PMLR, 2025a. URL https://proceedings.mlr. press/v258/compagnoni25a.html.
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(1):1474–1520, 2019.
Compagnoni, E. M., Liu, T., Islamov, R., Proske, F. N., Orvieto, A., and Lucchi, A. Adaptive methods through the lens of SDEs: Theoretical insights on the role of noise. In The Thirteenth International Conference on Learning Representations, 2025b. URL https://openreview. net/forum?id=ww3CLRhF1v.
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.
Li, Z., Malladi, S., and Arora, S. On the validity of modeling SGD with stochastic differential equations (SDEs). In Advances in Neural Information Processing Systems, 2021.
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.
Compagnoni, E. M., Islamov, R., Proske, F. N., Lucchi, A., Orvieto, A., and Gorbunov, E. On the interaction of noise, 6
A Diffusion Approximation for Linear TD Learning under Markovian Noise
Mandt, S., Hoffman, M. D., and Blei, D. M. Stochastic gradient descent as approximate bayesian inference. Journal of Machine Learning Research, 18(134):1–35, 2017.
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.
Meyn, S. P. and Tweedie, R. L. Markov Chains and Stochastic Stability. Cambridge University Press, 2 edition, 2009. Mil’shtein, G. N. Weak approximation of solutions of systems of stochastic differential equations. Theory of Probability & Its Applications, 30(4):750–766, 1986. Mitra, A. A simple finite-time analysis of td learning with linear function approximation. arXiv preprint arXiv:2403.02476, 2024. 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:41–153, 2024. 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. Orvieto, A. and Lucchi, A. Continuous-time models for stochastic optimization algorithms. In Advances in Neural Information Processing Systems, volume 32, 2019. Samsonov, S., Sheshukova, M., Moulines, E., and Naumov, A. Statistical inference for linear stochastic approximation with markovian noise. arXiv preprint arXiv:2505.19102, 2025. Srikant. Rates of convergence in the central limit theorem for markov chains, with an application to td learning. arXiv preprint arXiv:2401.15719, 2026. Srikant, R. and Ying, L. Finite-time error bounds for linear stochastic approximation and td learning. In Conference on Learning Theory (COLT), 2019. Sutton, R. S. Learning to predict by the methods of temporal differences. Machine Learning, 3(1):9–44, 1988. Sutton, R. S. and Barto, A. G. Reinforcement learning: An introduction. MIT press, 2018. Tsitsiklis, J. N. and Van Roy, B. An analysis of temporaldifference learning with function approximation. IEEE Transactions on Automatic Control, 42(5):674–690, 1997. 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. 7
A Diffusion Approximation for Linear TD Learning under Markovian Noise
A. Notation, assumptions, and appendix roadmap Symbol
Meaning
Zk = (Sk , Sk+1 , Rk+1 ) b̂(z), Â(z) H(θ, z) = b̂(z) − Â(z)θ h(θ) = b − Aθ gθ (z) = H(θ, z) − h(θ) uθ ξk+1 Γ(θ) B(θ) ϱ(m) τcorr
observation driving the TD update random affine components of one TD update TD increment stationary mean field centered Markovian noise centered Poisson solution, uθ − PZ uθ = gθ martingale increment from the Poisson decomposition long-run covariance of the TD noise affine factor satisfying B(θ)B(θ)⊤ = Γ(θ) total-variation mixing profile of Zk P 1 + 4 m≥1 ϱ(m)
The appendix is organized as follows. Section B collects boundedness and Poisson-equation facts. Section C derives the diffusion approximation of the discrete TD recursion. Section D proves the mixing bound from Proposition 3.1. Section E constructs a Lipschitz covariance factor. Section F proves SDE stability. Section G shows how the localization introduced in Theorem 3.3 is removed by means of Theorem 3.4. Section H elaborates on the new insights about stepsize guarantees for convergence of TD. Section I proves finite-time Gaussian estimates and covariance dynamics of TD noise stated in Theorem 3.6. Section J gives the complete construction, numerical discretization, hyperparameters, and plotting conventions for the experiments in Figure 1.
B. Preliminaries Lemma B.1 (Bounded TD components). Under (A2), sup b̂(z) ≤ KR Kϕ ,
sup Â(z)
z
op
z
≤ (1 + γ)Kϕ2 .
Consequently, there are constants c0 , c1 , Lg < ∞ such that ∥g(θ, z)∥ ≤ c0 + c1 ∥θ∥ ,
∥g(θ, z) − g(θ′ , z)∥ ≤ Lg ∥θ − θ′ ∥ .
Proof. The first bound follows from ∥r(s, s′ )ϕ(s)∥ ≤ KR Kϕ . For the matrix term, ϕ(s)(ϕ(s) − γϕ(s′ ))⊤ op ≤ ∥ϕ(s)∥ ∥ϕ(s) − γϕ(s′ )∥ ≤ (1 + γ)Kϕ2 . Since g(θ, z) = (b̂(z) − b) − (Â(z) − A)θ, the Lipschitz and linear-growth bounds follow by taking suprema over the finite state space. Recall, that PZ is the transition kernel of the Markov chain (Zk ), i.e. PZ (z, A) = P(Zk+1 ∈ A | Zk = z). For finite irreducible and aperiodic chains, the mixing profile ϱ(m) := supz ∥PZm (z, ·) − π∥TV decays geometrically. Standard Poisson-equation results for Markov chains (Meyn & Tweedie, 2009; Glynn & Meyn, 1996) therefore give the following explicit form. Lemma B.2 (Poisson solution). Assume (A1)–(A2). For each fixed θ, the centered Poisson equation uθ − PZ uθ = gθ ,
Eπ [uθ ] = 0,
has the unique solution uθ (z) =
X m≥0
8
PZm gθ (z).
A Diffusion Approximation for Linear TD Learning under Markovian Noise
Moreover, uθ is affine in θ and there are constants Cu , Lu < ∞ such that ∥uθ − uθ′ ∥∞ ≤ Lu ∥θ − θ′ ∥ .
∥uθ ∥∞ ≤ Cu (c0 + c1 ∥θ∥), Proof. Since Eπ [gθ ] = 0, PZm gθ (z) =
Z
gθ (z ′ ) PZm (z, dz ′ ) − π(dz ′ ) ,
and hence ∥PZm gθ ∥∞ ≤ 2 ϱ(m) ∥gθ ∥∞ . Geometric decay of ϱ(m) implies absolute convergence in sup norm and gives the stated bound. Linearity of the equation and the affine form of gθ imply that uθ is affine. Applying the same bound to gθ − gθ′ gives the Lipschitz estimate. Centering follows from stationarity of π and termwise integration.
C. How the TD–SDE approximation is obtained This section has two purposes. First, it explains the general recipe for obtaining a diffusion approximation from a discrete stochastic recursion. Second, it applies this recipe to linear TD under Markovian noise. The point is not only to justify Theorem 3.3, but also to make explicit the construction that turns a noisy recursion into a continuous-time SDE. C.1. A short recipe: from a recursion to an SDE We briefly recall the principle underlying stochastic modified equations and adapt it to our setting. The key idea is that a global weak approximation follows from a local one-step moment matching. Consider a recursion of the form ¯ k , Zk ), θk+1 = θk + ∆(θ and a candidate SDE dΘt = h(Θt ) dt +
√
α B(Θt ) dWt .
d
Fix a point θ ∈ R . Let
¯ ∆(θ) := θ1 − θ
denote the one-step increment of the recursion started at θ, and let ∆(θ) := Θα − θ be the increment of the SDE over a time interval of length α. The SDE is chosen so that these two increments match at the level of their leading moments. Concretely, one computes: ¯ E[∆(θ)]
and
¯ ∆(θ) ¯ ⊤ ], E[∆(θ)
and selects h and B so that the SDE increment satisfies E[∆(θ)] = αh(θ) + O(α2 ), E[∆(θ)∆(θ)⊤ ] = α2 h(θ)h(θ)⊤ + α2 B(θ)B(θ)⊤ + O(α3 ). If these leading terms match those of the recursion, and higher moments are controlled, we then obtain an order-1 weak approximation by results in Li et al. (2017). In particular, for any sufficiently smooth test function φ of at most polynomial growth, max |Eφ(θk ) − Eφ(Θkα )| ≤ Cα. 0≤k≤T /α
What changes under Markovian noise. When the noise is i.i.d., the covariance B(θ)B(θ)⊤ is simply the one-step ¯ covariance of ∆(θ). Under Markovian sampling, this is no longer correct: temporal correlations accumulate across time. The correct object is the long-run covariance of the noise process. Identifying this covariance is the main additional step in the TD setting. 9
A Diffusion Approximation for Linear TD Learning under Markovian Noise
C.2. Applying the recipe to TD The TD recursion can be written as θk+1 = θk + αH(θk , Zk ) = θk + αh(θk ) + αgθk (Zk ), where h(θ) = b − Aθ,
gθ (z) = H(θ, z) − h(θ),
Eπ [gθ (Z)] = 0.
The deterministic part immediately identifies the candidate drift: h(θ) = b − Aθ. If the variables Zk were independent, the diffusion covariance would simply be Eπ [gθ (Z)gθ (Z)⊤ ]. However, in TD the observations are generated by a Markov chain, so the noise terms are correlated. The one-step covariance misses the cumulative contribution of these correlations. The main task is therefore to identify the correct effective covariance. C.3. Removing Markovian dependence with the Poisson equation For each fixed θ, let uθ solve the centered Poisson equation uθ − PZ uθ = gθ . Then gθk (Zk ) = ξk+1 + {uθk (Zk ) − uθk (Zk+1 )}, where ξk+1 = uθk (Zk+1 ) − PZ uθk (Zk ),
E[ξk+1 | Fk ] = 0.
Thus the Markovian noise is decomposed into two pieces: Markovian noise = martingale noise + coboundary. The coboundary is a telescoping term. Indeed, for K ≤ T /α, α
K−1 X
{uθk (Zk ) − uθk (Zk+1 )}
k=0
= α{uθ0 (Z0 ) − uθK−1 (ZK )} + α
K−1 X
{uθk (Zk ) − uθk−1 (Zk )}.
k=1
On a stopped ball {∥θ∥ ≤ R}, uθ is bounded and Lipschitz in θ, while ∥θk+1 − θk ∥ = O(α). Hence sup K≤T /α
α
K−1 X
{uθk (Zk ) − uθk (Zk+1 )} = O(α).
k=0
Therefore, at the diffusion scale, TD behaves like θk+1 ≈ θk + αh(θk ) + αξk+1 . C.4. The effective covariance The martingale increment has conditional covariance Q(θ, z) = E (uθ (Z1 ) − PZ uθ (z))(uθ (Z1 ) − PZ uθ (z))⊤ | Z0 = z . 10
A Diffusion Approximation for Linear TD Learning under Markovian Noise
Averaging over the stationary distribution gives the effective covariance Γ(θ) = Eπ [Q(θ, Z0 )]. Equivalently, Γ(θ) = Eπ (uθ (Z1 ) − PZ uθ (Z0 )) · (uθ (Z1 ) − PZ uθ (Z0 ))⊤ . This is also the long-run covariance of the original centered TD noise: X Γ(θ) = C0 (θ) + Cm (θ) + Cm (θ)⊤ , m≥1
where Cm (θ) = Eπ [gθ (Z0 )gθ (Zm )⊤ ]. This identity is the key structural point. The diffusion covariance is not only the instantaneous variance of TD noise; it also contains all lagged correlations created by the Markov chain. C.5. Moment matching for TD The effective one-step TD increment is ¯ ∆(θ) = αh(θ) + αξk+1 . Its leading moments are ¯ E[∆(θ)] = αh(θ) + O(α2 ), and ¯ ∆(θ) ¯ ⊤ ] = α2 h(θ)h(θ)⊤ + α2 Γ(θ) + O(α3 ). E[∆(θ) The candidate SDE is therefore dΘt = h(Θt ) dt +
√
α B(Θt ) dWt ,
B(θ)B(θ)⊤ = Γ(θ).
Over a time interval of length α, its increment satisfies the same expansions: E[∆(θ)] = αh(θ) + O(α2 ), and E[∆(θ)∆(θ)⊤ ] = α2 h(θ)h(θ)⊤ + α2 Γ(θ) + O(α3 ). Thus the SDE matches the leading drift and the leading covariance of the TD recursion. By the first-order moment-matching theorem for stochastic modified equations, max 0≤k≤T /α
Eφ(θkα,R ) − Eφ(Θα,R kα ) ≤ CT,R α,
for all φ continuous of at most polynomial growth. C.6. Takeaway The construction follows a simple conceptual recipe. First, write the recursion as new iterate = old iterate + drift + noise. Second, identify the correct noise covariance at the diffusion scale. For i.i.d. noise this is the one-step covariance. For Markovian noise it is the long-run covariance, obtained here through the Poisson equation. Third, choose a factor B(θ) satisfying B(θ)B(θ)⊤ = Γ(θ). Finally, write the SDE whose one-step moments match those of the recursion: √ dΘt = h(Θt ) dt + α B(Θt ) dWt . For linear TD under Markovian noise, this procedure yields precisely the SDE in Theorem 3.3. 11
A Diffusion Approximation for Linear TD Learning under Markovian Noise
D. Time correlations and diffusion size Proof of Proposition 3.1. For a unit vector v, define fθ,v (z) = v ⊤ gθ (z). It is centered and bounded by ∥gθ ∥∞ . From the long-run covariance representation, X v ⊤ Γ(θ)v = Eπ [fθ,v (Z0 )2 ] + 2 Eπ [fθ,v (Z0 )fθ,v (Zm )]. m≥1 2
The variance term is at most ∥gθ ∥∞ . For m ≥ 1, Z
π(dz)fθ,v (z)PZm fθ,v (z)
|Eπ [fθ,v (Z0 )fθ,v (Zm )]| =
2
2
≤ 2 ∥fθ,v ∥∞ ϱ(m) ≤ 2 ∥gθ ∥∞ ϱ(m). Hence, for every unit vector v,
v ⊤ Γ(θ)v ≤ 1 + 4
X
2
ϱ(m) ∥gθ ∥∞ .
m≥1
By Lemma B.1, v ⊤ Γ(θ)v ≤ τcorr (c0 + c1 ∥θ∥)2 . Now let M ⪰ 0 and write its spectral decomposition as M=
d X
λj vj vj⊤ ,
λj ≥ 0,
∥vj ∥ = 1.
j=1
Since Γ(θ) is positive semidefinite, tr(M Γ(θ)) =
d X
λj vj⊤ Γ(θ)vj .
j=1
Using the previous bound for each vj gives tr(M Γ(θ)) ≤
d X
λj τcorr (c0 + c1 ∥θ∥)2 = tr(M ) τcorr (c0 + c1 ∥θ∥)2 .
j=1
It remains to relate τcorr to the usual mixing time. Let tmix (ε) = min{m : ϱ(m) ≤ ε} and choose ε = 1/4. Standard submultiplicativity of the pairwise total-variation distance gives X ϱ(m) ≤ 2tmix (1/4), m≥1
and hence τcorr ≤ 1 + 8tmix (1/4). Conversely, by the definition of tmix (1/4), ϱ(m) > 1/4 for m < tmix (1/4), so X τcorr = 1 + 4 ϱ(m) > tmix (1/4). m≥1
E. A convenient choice of the diffusion factor The SDE only depends on the covariance through the identity B(θ)B(θ)⊤ = Γ(θ). 12
A Diffusion Approximation for Linear TD Learning under Markovian Noise
Thus B(θ) does not have to be the principal square root Γ(θ)1/2 . This distinction is useful because the principal square root can be not regular enough for the SDE formulation when Γ(θ) is singular. √ Indeed, even in dimension one, the map a 7→ a is not Lipschitz near zero. Hence, without a uniform lower bound Γ(θ) ⪰ λId on the region of interest, Lipschitz regularity of Γ(θ)1/2 is not automatic. Such a lower bound would amount to assuming that the effective TD noise excites every parameter direction. This is a nondegeneracy condition stronger than what we need. We instead use the square-integrability of rewards to build a different factor B(θ) that is affine in θ. Proof of Proposition 3.2. Write gθ (z) = g
(0)
(z) +
d X
θi g (i) (z),
i=1 ′
where, for z = (s, s , r), g (0) (z) = rϕ(s) − b,
g (i) (z) = (A − Â(z))ei .
For i ≥ 1, g (i) (s, s′ , r) = Aei − ϕ(s) ϕi (s) − γϕi (s′ ) , so g (i) depends only on the transition edge (s, s′ ), and not on the reward sample. By linearity of the Poisson equation, uθ = u(0) +
d X
θi u(i) ,
u(i) =
i=1
X
PZm g (i) .
m≥0
For i ≥ 1, since g (i) is reward-free and the reward variable does not affect future state transitions, every PZm g (i) is reward-free. Therefore u(i) is reward-free for every i ≥ 1. The martingale increment has the affine decomposition ξθ = ξ (0) +
d X
θi ξ (i) ,
ξ (i) = u(i) (Z1 ) − PZ u(i) (Z0 ).
i=1
For i ≥ 1, ξ (i) depends only on the state-transition structure. Hence its scalar components are measurable with respect to the reachable edge (S, S ′ ), and therefore lie in a linear space of dimension at most nκ. It remains to account for the i = 0 coefficient. Write R = r̄(S, S ′ ) + ε,
E[ε | S, S ′ ] = 0.
The mean-reward part r̄(S, S ′ )ϕ(S) is edge-measurable, so it lies in the same edge space of dimension at most nκ. The centered reward noise contributes functions of the form 1{(S,S ′ )=(s,s′ )} ε, which span at most one additional L2 -mode per reachable edge. Hence the scalar components of all coefficients {ξ (i) : 0 ≤ i ≤ d} belong to a finite-dimensional subspace H ⊂ L2 with dim(H) ≤ 2nκ. On the other hand, since there are d(d + 1) scalar components {(ξ (i) )r : 0 ≤ i ≤ d, 1 ≤ r ≤ d}, 13
A Diffusion Approximation for Linear TD Learning under Markovian Noise
the general Hilbert-space construction gives dim(H) ≤ d(d + 1). Thus we may take q = dim(H) ≤ min{d(d + 1), 2nκ}. Let e1 , . . . , eq be an orthonormal basis of H, and define B(θ) ∈ Rd×q by Brℓ (θ) = ⟨(ξθ )r , eℓ ⟩L2 ,
1 ≤ r ≤ d,
1 ≤ ℓ ≤ q.
Since ξθ is affine in θ, every entry of B(θ) is affine in θ. Hence B is globally Lipschitz and has linear growth. Finally, because each (ξθ )r ∈ H, Parseval’s identity gives (B(θ)B(θ)⊤ )rs =
q X
⟨(ξθ )r , eℓ ⟩L2 ⟨(ξθ )s , eℓ ⟩L2
ℓ=1
= ⟨(ξθ )r , (ξθ )s ⟩L2 = E (ξθ )r (ξθ )s = Γ(θ)rs . Therefore B(θ)B(θ)⊤ = Γ(θ), yielding the desired conclusion. Remark E.1 (Edge count, sparsity, and reward-noise structure). Consider E = {(s, s′ ) : P π (s′ |s) > 0},
κ = max |{s′ : P π (s′ |s) > 0}|. s
Since each state has at most κ outgoing transitions and there are n states, we always have |E| ≤ nκ. Equality holds when every state has exactly κ outgoing edges; otherwise |E| can be strictly smaller. The refined bound q ≤ 2nκ captures the fact that the effective noise dimension is governed by the transition graph rather than the ambient dimension d. However, the precise contribution of the reward depends on how reward randomness is structured. State-dependent vs. edge-dependent noise.
There are two canonical regimes:
• State-dependent noise: R = r̄(S, S ′ ) + εS ,
εS depends only on S.
In this case, the centered noise contributes at most one independent direction per state. Hence the noise dimension is controlled by n, and one can obtain a sharper bound of order nκ or even n depending on structure. • Edge-dependent noise: R = r̄(S, S ′ ) + εS,S ′ ,
εS,S ′ depends on the edge.
Here each transition (s, s′ ) may carry its own independent noise mode. This yields up to one additional L2 -direction per edge, leading to the bound q ≤ 2|E|.
14
A Diffusion Approximation for Linear TD Learning under Markovian Noise
Illustration.
Consider a state s with three possible successors s1 , s2 , s3 . The two regimes are illustrated below. State-dependent noise.
Edge-dependent noise.
Edge
Mean reward r̄(s, s′ )
Noise
Edge
Mean reward r̄(s, s′ )
Noise
(s, s1 ) (s, s2 ) (s, s3 )
5 2 −1
N (0, 1) N (0, 1) N (0, 1)
(s, s1 ) (s, s2 ) (s, s3 )
5 2 −1
N (0, 1) 0 Unif[-1,1]
In the state-dependent case, all transitions share the same noise source, so the number of independent noise directions does not grow with the number of outgoing edges. In contrast, in the edge-dependent case, each transition can introduce a distinct noise mode, and the effective dimension scales with |E|. Probabilistic interpretation of the Hilbertian construction. The Hilbert-space construction gives an intrinsic interpretation. The Brownian directions correspond to orthonormal L2 modes spanning all scalar components of the martingale increment ξθ . Writing Wt = (Wt1 , . . . , Wtq ), where the components are independent one-dimensional Brownian motions, the diffusion term becomes B(θ) dWt =
q X
B·ℓ (θ) dWtℓ .
ℓ=1
Thus each column of B(θ) describes the loading of the TD martingale noise onto one orthogonal noise mode eℓ . The SDE noise is therefore a finite superposition of independent Brownian perturbations associated with the finite-dimensional L2 span generated by (i) (ξ )r : 0 ≤ i ≤ d, 1 ≤ r ≤ d .
F. Proof of SDE stability Proof of Theorem 3.4. By Proposition 3.2, the diffusion coefficient B is affine. Hence it is globally Lipschitz and has linear growth. Since the drift h(θ) = b − Aθ is also globally Lipschitz and has linear growth, the SDE dΘt = (b − AΘt ) dt +
√
α B(Θt ) dWt
admits a unique global strong solution for every α > 0. It remains to prove the stability estimate. Let θ⋆ = A−1 b, Then dEt = −AEt dt +
Et = Θt − θ⋆ . √
α B(θ⋆ + Et ) dWt .
Since A is positive stable, there exists a unique symmetric positive definite matrix P solving A⊤ P + P A = I. Define the Lyapunov function V (e) = e⊤ P e. Let λmin (P ) and λmax (P ) denote the extremal eigenvalues of P . Then λmin (P )∥e∥2 ≤ V (e) ≤ λmax (P )∥e∥2 . 15
A Diffusion Approximation for Linear TD Learning under Markovian Noise
Applying Itô’s formula to V (Et ) gives LV (e) = −2e⊤ P Ae + α tr P B(θ⋆ + e)B(θ⋆ + e)⊤
= −e⊤ (A⊤ P + P A)e + α tr(P Γ(θ⋆ + e)) = −∥e∥2 + α tr(P Γ(θ⋆ + e)) . By Proposition 3.1 with M = vv ⊤ , ∥Γ(θ)∥op ≤ τcorr (c0 + c1 ∥θ∥)2 . With the effective noise dimension in (9), with the convention deff (θ) = 0 if Γ(θ) = 0, we have tr(Γ(θ)) = deff (θ) ∥Γ(θ)∥op . Therefore,
tr(P Γ(θ⋆ + e)) ≤ ∥P ∥op tr(Γ(θ⋆ + e)) = ∥P ∥op deff (θ⋆ + e) ∥Γ(θ⋆ + e)∥op 2 ≤ λmax (P ) d¯eff τcorr c0 + c1 ∥θ⋆ + e∥ ,
where d¯eff :=
sup deff (θ) ≤ d. θ:Γ(θ)̸=0
Using
2
(c0 + c1 ∥θ⋆ + e∥)2 ≤ 2(c0 + c1 ∥θ⋆ ∥)2 + 2c21 ∥e∥ , we obtain
2 2 LV (e) ≤ − ∥e∥ + α τcorr d¯eff K0 + K1 ∥e∥ ,
where one may take K0 = 2λmax (P )(c0 + c1 ∥θ⋆ ∥)2 , Choose α0 > 0 small enough that
Then
K1 = 2λmax (P )c21 .
1 1 − ατcorr d¯eff K1 ≥ , 2
∀α ∈ (0, α0 ).
1 2 LV (e) ≤ − ∥e∥ + α τcorr d¯eff K0 . 2
Using ∥e∥2 ≥ V (e)/λmax (P ), this implies LV (e) ≤ −ρA V (e) + α τcorr K0 ,
ρA :=
1 . 2λmax (P )
Taking expectations in Itô’s formula and applying Gronwall’s inequality yields EV (Et ) ≤ e−ρA t EV (E0 ) +
α τcorr d¯eff K0 1 − e−ρA t . ρA
Finally, converting back from V to the Euclidean norm gives λmax (P ) −ρA t α τcorr d¯eff K0 e E∥E0 ∥2 + λmin (P ) ρA λmin (P ) −ρA t 2 = κ(P ) e E∥E0 ∥ + 2κ(P ) ατcorr d¯eff K0 ,
E∥Et ∥2 ≤
(P ) is the conditioning number of the (symmetric) matrix P . Renaming constants gives where κ(P ) := λλmax min (P ) 2
2
E ∥Et ∥ ≤ CA e−ρA t E ∥E0 ∥ + CA α τcorr d¯eff . 16
A Diffusion Approximation for Linear TD Learning under Markovian Noise
where CA depends on the Lyapunov geometry of A, in particular on the condition number of P , and on the linear-growth constants of B. The same estimate also gives sup E∥Θt ∥2 < ∞, t≥0
because Θt = Et + θ⋆ . Hence the unique solution to (2) has uniformly bounded second moment.
G. Removal of localization The weak approximation theorem is stated for stopped processes. This section records the standard argument showing that, once global stability of the SDE is known, the localization can be removed on every finite time interval. (R)
Corollary G.1 (Removal of localization). Let (Θt )t≥0 denote the unique strong solution of the SDE obtained by stopping the coefficients of (2) outside the ball {∥θ∥ ≤ R}, and let (Θt )t≥0 denote the unique global strong solution of (2). Then for every T > 0, (R) lim P sup ∥Θt − Θt ∥ = 0 = 1. R→∞
0≤t≤T
Equivalently, (R)
sup ∥Θt
P
− Θt ∥ − → 0,
R → ∞.
0≤t≤T
Consequently, any weak limit identified for the localized processes coincides with the weak limit of the original process on every finite time interval. Proof. Define the exit time of the full solution τR := inf{t ≥ 0 : ∥Θt ∥ ≥ R}. By construction of the localized coefficients and pathwise uniqueness of strong solutions, (R)
Θt
= Θt
for all t ≤ τR .
Therefore, (R)
− Θt ∥ = 0
(R)
− Θt ∥ = 0 ≥ P(τR > T )
sup ∥Θt
on the event {τR > T }.
0≤t≤T
Hence P
sup ∥Θt
0≤t≤T
=1−P
sup ∥Θt ∥ ≥ R . 0≤t≤T
The final probability converges to zero as R → ∞ because Theorem 3.4 gives global existence and finite moments on every finite time interval. This proves the first claim. The convergence in probability follows immediately: for every ε > 0, P
(R)
sup ∥Θt
− Θt ∥ > ε ≤ P(τR ≤ T )
0≤t≤T
= P sup ∥Θt ∥ ≥ R −→ 0. 0≤t≤T
The final statement follows because two processes whose sup-norm distance on [0, T ] converges to zero in probability have the same weak limits. 17
A Diffusion Approximation for Linear TD Learning under Markovian Noise
Localization argument and the reversal of the standard analysis pipeline. The localization used above is only a proof device, standard in stochastic analysis. We are not assuming that the TD iterates are bounded as a modeling condition, nor are we modifying the algorithm by imposing boundedness. In particular, this is different from projected linear TD, where the recursion itself is changed by applying a projection step. Here the localization is introduced only temporarily to control estimates, and is then removed a posteriori using the stability of the full SDE. Actually, this should be regarded as a feature of the novel framework we are presenting. Both ODE methods and finite-time analysis need to prove some form of iterates non-explosion before starting the analysis of the algorithms recursion. The SDE approach reverses the order: first consider a process in which the iterates are artificially made bounded, then study the stability of the obtained SDE. It will be precisely this stability that, along with convergence of the algorithm, reveals that iterates were bounded in the first place and therefore the stopping device was never active.
H. Additional discussion on stepsize comparisons The comparison in Table 1 should be interpreted as a qualitative summary rather than a strict ordering of results. Existing works consider different stepsize schedules, including constant, decaying, and Robbins–Monro stepsizes. Guarantees obtained for sufficiently small constant stepsizes typically imply the corresponding decaying-stepsize behavior by allowing the stepsize to decrease over time. Thus, the table focuses on whether a result identifies a regime in which the admissible stepsize is uniform with respect to the horizon and does not explicitly require projection. A second qualification concerns the dependence on mixing. Even when a stepsize condition is not written as an explicit function of the mixing time, it can still depend on the Markov chain through other problem-dependent constants. Different policies induce different transition kernels, and hence different temporal correlations and mixing behavior, as emphasized by Nagaraj et al. (2020). In this sense, “not a function of tmix ” means that the stated admissible regime does not require inserting an explicit upper bound on the mixing time into the stepsize choice; it does not mean that the dynamics are independent of mixing. Our result should also be contrasted with the curvature-free slow-regime analysis of Lee & Orabona (2025). With their terminology, their stepsize condition is curvature-free in the slow regime, whereas our SDE stability estimate is curvaturedependent through the Lyapunov geometry of A, encoded by the solution P of A⊤ P + P A = I. This dependence is natural for our purpose. The fact we recover a curvature-dependent result is due to our choice of explicitly tracking contraction and stochastic fluctuations to show how the SDE framework is able to clarify finite-time results. Nothing prevents the SDE framework to yield curvature-free results.
I. Proof of Gaussian estimates Proof of Theorem 3.6. We split the proof into four steps. √ Step 1: rescaled dynamics. Since h(θ⋆ ) = 0, dividing the SDE (2) by α gives √ dXtα = −AXtα dt + B(θ⋆ + αXtα ) dWt .
(15)
Step 2: comparison with the frozen Ornstein–Uhlenbeck process. Let G solve dGt = −AGt dt + B(θ⋆ ) dWt ,
G0 = X0α .
Set Dt := Xtα − Gt . Subtracting the dynamics of G from (15), dDt = −ADt dt + B(θ⋆ +
√
αXtα ) − B(θ⋆ ) dWt ,
By Proposition 3.2, B is affine, hence globally Lipschitz. Thus, for some LB < ∞, √ √ B(θ⋆ + αx) − B(θ⋆ ) F ≤ LB α ∥x∥ . 18
D0 = 0.
(16)
(17)
A Diffusion Approximation for Linear TD Learning under Markovian Noise 2
Step 3: finite-time L2 bound. Applying Itô’s formula to ∥Dt ∥ gives 2
d ∥Dt ∥ = −2⟨Dt , ADt ⟩ dt √ 2 + B(θ⋆ + αXtα ) − B(θ⋆ ) F dt + dMt , where Mt is a martingale. Since A is fixed, there is cA < ∞ such that 2
−2⟨x, Ax⟩ ≤ cA ∥x∥ . Taking expectations and using (17), Z t
2
E ∥Dt ∥ ≤ cA
2
E ∥Ds ∥ ds + L2B α
Z t
0
2
E ∥Xsα ∥ ds.
0
On every finite interval [0, T ], the SDE has finite second moments because its coefficients are globally Lipschitz with linear growth. Hence, for each T < ∞, 2 sup E ∥Xsα ∥ < ∞. 0≤s≤T
Consequently, for 0 ≤ t ≤ T , Z t
2
E ∥Dt ∥ ≤ cA
2
E ∥Ds ∥ ds + CT α. 0
By Grönwall’s lemma,
2
sup E ∥Dt ∥ ≤ CT α. 0≤t≤T
Equivalently,
1/2 √
sup ∥Xtα − Gt ∥L2 ≤ CT
α.
0≤t≤T
Step 4: covariance dynamics. Since G is linear, −At
Gt = e
Z t G0 +
e−A(t−s) B(θ⋆ ) dWs .
0
Thus Gt is Gaussian whenever G0 is Gaussian, and its covariance Σt := Cov(Gt ) satisfies Σ̇t = −AΣt − Σt A⊤ + Γ(θ⋆ ), because B(θ⋆ )B(θ⋆ )⊤ = Γ(θ⋆ ). If (A3) holds, then −A is Hurwitz. Therefore the Lyapunov equation AΣ + ΣA⊤ = Γ(θ⋆ ) has a unique solution, and the covariance flow converges to it, i.e. Σt → Σ, concluding the proof. Interpretive and diagnostic value of Theorem 3.6. Near the fixed point, TD errors are approximated by a Gaussian law. This provides a way to compare feature maps or policies through the effective noise covariance Γ(θ⋆ ), and to estimate the residual variance after the transient phase. The covariance dynamics also shows that the error is generally anisotropic: at stationarity, (14) gives the directional diagnostic Var v ⊤ (Θ∞ − θ⋆ ) ≈ αv ⊤ Σv, thus not only recovering the classical O(α) floor but also showing which directions v are noisier. Analogously, we note that at stationarity tr(Σ∞ ) = tr(P Γ(θ⋆ )), thus 2
E ∥Θ∞ − θ⋆ ∥ ≈ α tr(P Γ(θ⋆ )). The matrix Γ(θ⋆ ) identifies the noisy directions, while P identifies the directions that are slow to contract under the drift −A. Hence tr(P Γ(θ⋆ )) measures the amount of TD noise injected into directions that are not rapidly damped by the projected Bellman dynamics. 19
A Diffusion Approximation for Linear TD Learning under Markovian Noise
This motivates the contraction-weighted effective noise dimension dP eff :=
tr(P Γ(θ⋆ )) , ∥P ∥op ∥Γ(θ⋆ )∥op
(18)
whenever Γ(θ⋆ ) ̸= 0. Combining this identity with Proposition 3.1 shows that the OU variance floor is governed not only by the mixing factor τcorr , which controls the worst-direction noise amplitude, but also by the alignment between noisy directions and slowly contracting directions, as quantified by dP eff .
J. Numerical experiment details This section documents the experiments shown in Figure 1. Both examples are finite Markov reward processes induced by a fixed policy; there are no actions to simulate. Rewards are deterministic functions of the current state, so the observation chain used in the computation is the pair chain Zk = (Sk , Sk+1 ), which is the deterministic-reward specialization of the general chain (Sk , Sk+1 , Rk+1 ) used in the main text. All TD state chains are initialized at stationarity and all parameter paths start from the deterministic vector θ0 . TD and SDE paths are sampled independently; only average statistics are compared. Mean field and TD recursion. For a finite state space S = {0, . . . , n − 1}, transition matrix P , stationary distribution µ, feature map ϕ : S → Rd , discount γ, and deterministic reward r(s), the experiment computes A=
X
⊤ X µs ϕ(s) ϕ(s) − γ Pss′ ϕ(s′ ) ,
b=
X
(19)
s′
s∈S
µs r(s)ϕ(s),
(20)
s∈S
and θ⋆ = A−1 b. The TD recursion is θk+1 = θk + α r(Sk ) + γϕ(Sk+1 )⊤ θk − ϕ(Sk )⊤ θk ϕ(Sk ). Pair-chain representation.
(21)
Let Z = {(s, s′ ) : Pss′ > 0}.
The stationary law and transition matrix of the pair chain are πZ (s, s′ ) = µs Pss′ ,
Q(s,s′ ),(s′ ,s′′ ) = Ps′ s′′ .
(22)
For z = (s, s′ ), define bb(z) = r(s)ϕ(s),
b A(z) = ϕ(s)(ϕ(s) − γϕ(s′ ))⊤ .
The centered TD noise is affine in θ: b gθ (z) = bb(z) − b + (A − A(z))θ =: cz + Lz θ. SDE discretization.
(23)
The global TD–SDE is simulated on the matched grid tk = kα by Euler–Maruyama: Θk+1 = Θk + α(b − AΘk ) + αB(Θk )ζk ,
The factor α in the stochastic term follows from the SDE coefficient N (0, αIq ). 20
√
ζk ∼ N (0, Iq ).
(24)
αB(Θt ) and the Brownian increment ∆Wk ∼
A Diffusion Approximation for Linear TD Learning under Markovian Noise
Experiment instances.
The two examples in Figure 1 are generated as follows.
Quantity
Biased ring
directed cycle
States/features Discount Stepsize Initialization Runs Iterations Seed Transitions Features Reward Angles Pair states
n = 5, d = 2 γ = 0.95 α = 10−3 (1.65, 1.05) M = 1024 K = 1.6 × 104 178 Ps,s+1 = 0.88, Ps,s = 0.08, Ps,s−1 = 0.04 Φsℓ ∼ N (0, 1) once r(s) ∼ N (0, 1) once – |Z| = 15
n = 8, d = 2 γ = 0.50 α = 10−3 (1.55, 1.20) M = 1024 K = 3.3 × 104 42 Ps,s+1 = 0.80, Ps,s = 0.20 ϕ(s) = (cos ωs , sin ωs ) r(s) = 0.08 cos(2ωs ) ωs = 2πs/n |Z| = 16
Table 2. Finite Markov reward processes and simulation parameters for Figure 1. The biased ring uses random features and rewards drawn once with the stated seed and then kept fixed.
Plotting convention. The trajectory panels plot empirical mean paths in parameter space for TD and for the global TD– SDE. The gray contours are level sets of (θ − θ⋆ )⊤ PL (θ − θ⋆ ), where PL solves the Lyapunov equation A⊤ PL + PL A = I. The distance panels plot empirical estimates of E∥θk − θ⋆ ∥2 and E∥Θkα − θ⋆ ∥2 on a logarithmic scale; shaded regions are empirical 10–90% quantile bands over the independent runs. These plots should not be read as a pathwise coupling between TD and the SDE. They compare ensemble statistics, matching the weak approximation statement in Theorem 3.3.
21