Paper deep dive
Almost Sure Convergence of Differential Temporal Difference Learning for Average Reward Markov Decision Processes
Ethan Blaser, Jiuqi Wang, Shangtong Zhang
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%
Last extracted: 7/21/2026, 1:22:46 AM
Summary
This paper addresses the convergence of differential temporal difference (TD) learning for average reward Markov Decision Processes (MDPs). It proves the almost sure convergence of on-policy n-step differential TD using standard diminishing learning rates, eliminating the need for a 'local clock' (state visit count) required in previous works. Additionally, it derives three sufficient conditions for the convergence of off-policy n-step differential TD without a local clock, bridging the gap between theoretical guarantees and practical implementations.
Entities (10)
Relation Signals (10)
Ethan Blaser → affiliatedwith → University of Virginia
confidence 99% · Ethan Blaser ... University of Virginia
Shangtong Zhang → affiliatedwith → University of Virginia
confidence 99% · Shangtong Zhang ... University of Virginia
Jiuqi Wang → affiliatedwith → University of Virginia
confidence 99% · Jiuqi Wang ... University of Virginia
On-policy n-step differential TD → convergesalmostsurelywith → Standard Diminishing Learning Rates
confidence 95% · proving the almost sure convergence of on-policy $n$-step differential TD for any $n$ using standard diminishing learning rates
On-policy n-step differential TD → doesnotrequire → Local Clock
confidence 95% · without a local clock
Differential Temporal Difference Learning → solves → Average Reward MDP
confidence 95% · Differential temporal difference (TD) learning algorithms are a major advance for average reward RL
Off-policy n-step differential TD → convergesunderconditions → Three Sufficient Conditions
confidence 90% · derive three sufficient conditions under which off-policy $n$-step differential TD also converges
Off-policy n-step differential TD → doesnotrequire → Local Clock
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:The average reward is a fundamental performance metric in reinforcement learning (RL) focusing on the long-run performance of an agent. Differential temporal difference (TD) learning algorithms are a major advance for average reward RL as they provide an efficient online method to learn the value functions associated with the average reward in both on-policy and off-policy settings. However, existing convergence guarantees require a local clock in learning rates tied to state visit counts, which practitioners do not use and does not extend beyond tabular settings. We address this limitation by proving the almost sure convergence of on-policy $n$-step differential TD for any $n$ using standard diminishing learning rates without a local clock. We then derive three sufficient conditions under which off-policy $n$-step differential TD also converges without a local clock. These results strengthen the theoretical foundations of differential TD and bring its convergence analysis closer to practical implementations.
Tags
Links
- Source: https://arxiv.org/abs/2602.16629v1
- Canonical: https://arxiv.org/abs/2602.16629v1
Trouble viewing inline? Open PDF directly →
Full Text
64,403 characters extracted from source content.
Expand or collapse full text
Almost Sure Convergence of Differential Temporal Difference Learning for Average Reward Markov Decision Processes Ethan Blaser Jiuqi Wang Shangtong Zhang University of Virginia blaser@email.virginia.edu University of Virginia jiuqi@email.virginia.edu University of Virginia shangtong@virginia.edu Abstract The average reward is a fundamental performance metric in reinforcement learning (RL) focusing on the long-run performance of an agent. Differential temporal difference (TD) learning algorithms are a major advance for average reward RL as they provide an efficient online method to learn the value functions associated with the average reward in both on-policy and off-policy settings. However, existing convergence guarantees require a local clock in learning rates tied to state visit counts, which practitioners do not use and does not extend beyond tabular settings. We address this limitation by proving the almost sure convergence of on-policy n-step differential TD for any n using standard diminishing learning rates without a local clock. We then derive three sufficient conditions under which off-policy n-step differential TD also converges without a local clock. These results strengthen the theoretical foundations of differential TD and bring its convergence analysis closer to practical implementations. 1 Introduction The average reward is an important performance metric in Reinforcement Learning (RL, sutton2018reinforcement). Compared with the commonly used discounted total rewards performance metric, the average reward setting more heavily emphasizes the long-term behavior of the RL agent, making it particularly suitable for applications like network resource allocation (marbach1998call; bakhshi2021r; yang2024average), robotics (kober2013reinforcement), and scheduling (ghavamzadeh2007hierarchical). Differential temporal difference (TD) (wan2020learning) learning is one of the most important recent advances for average reward RL. Differential TD is designed to estimate the corresponding value function for the average reward performance metric and can be used in both on-policy and off-policy settings. However, the convergence analysis of differential TD remains less satisfactory. In wan2020learning, almost sure convergence is proved only when the stepsizes depend on a local clock. Specifically, they require the learning rates of the form αν(t,St) _ν(t,S_t), where αt _t is a sequence of deterministic, nonnegative, and diminishing scalars and a local clock (i.e., a counter) ν(t,s)ν(t,s), which counts the number of visits to a state s up to timestep t. In other words, at time t the stepsize depends not only on t, but also on the number of past visits to the current state StS_t. We argue that this local clock based learning rate is unsatisfactory for at least three reasons. First, to our best knowledge, practitioners do not actually use the local clock in their learning rates, including wan2020learning in their experiments. The local clock seems to be primarily a theoretically motivated technique (borkar2009stochastic). Although recent work demonstrates that it can occasionally be required for convergence in certain settings (chen2025non), its adoption in practical implementations remains rare. Second, the local clock cannot be used in many function approximation settings, especially those considered in sutton2018reinforcement, where the agent only has access to the feature of the current state, denoted as ϕ(St)φ(S_t), not the state StS_t itself. With only ϕ(St)φ(S_t), it is not clear how to count the visits to StS_t since the feature function ϕφ is usually not a one-to-one mapping. This means the local clock technique is only viable in the tabular setting. Third, although convergence analyses of discounted TD (sutton1988learning) also require the local clock in learning rates (jaakkola1993convergence; tsitsiklis1994asynchronous), later works removed this requirement (tsitsiklis1997analysis; liu2024ode). Therefore, there is a theoretical gap in the literature for average reward RL, and gives rise to the central question this work aims to answer: Can we establish the convergence of differential TD without using a local clock in the learning rates? This question seems trivial at first glance. After all, local clocks can be avoided in the discounted setting, so one might expect the same argument to carry over to the average reward setting. However, as we will now explain, extending that analysis to the average-reward case introduces several fundamental obstacles. The convergence of the discounted TD with a local clock rests on the global asymptotic stability (G.A.S.) of the following ODE111The ODE (1) is G.A.S. if and only if the A matrix is Hurwitz (Theorem 4.5 from khalil2002nonlinear). A matrix A is Hurwitz if the real part of any of its eigenvalues is strictly negative. dv(t)dt=Av(t), v(t)t=Av(t), (1) where v(t)∈ℝ||v(t) ^|S| can be viewed as the estimation of the value function and A∈ℝ||×||A ^|S|×|S| corresponds to the discounted TD algorithm, with |||S| being the number of states. Essentially, (1) is G.A.S. because the A matrix corresponding to discounted TD with a local clock is negative definite (n.d.)222A matrix A, not necessarily symmetric, is n.d. if for any y≠0y≠ 0, it holds that y⊤Ay<0y Ay<0. A n.d. matrix must be Hurwitz. But a Hurwitz matrix does not need to be n.d. For example, [−1100−1] [-1&10\\ 0&-1] is Hurwitz but not n.d.. When the local clock is removed from the learning rates, the corresponding ODE becomes dv(t)dt=DAv(t), v(t)t=DAv(t), (2) where D∈ℝ||×||D ^|S|×|S| is a diagonal matrix whose entries are the stationary state distribution. The change from (1) to (2) is intuitive. With a local clock, the total magnitude of updates applied to each state is forced to be the same, regardless of how frequently that state is visited. Without a local clock, the magnitude of the updates naturally depends on visitation frequency, which appears as the multiplier D in (2). For instance, when a state s is visited for the first time, the learning rate is always α1 _1 with a local clock, whereas without it the learning rate may be α100 _100 if s is first visited at time t=100t=100. Nevertheless, when A is n.d., it is straightforward to show that DADA is also n.d., implying that (2) is G.A.S., and thus that discounted TD converges even without a local clock. However, as we shall show soon, the corresponding A matrix for differential TD with the local clock is only Hurwitz and not necessarily n.d. When A is Hurwitz, whether DADA is also Hurwitz is a long-standing open problem in the linear algebra community, called the D-stability problem (johnson1974sufficient; giorgi2015overview). Progress on the D-stability problem has been limited in the past decade (kushel2019unifying; kushel2023novel; tong2024sufficient). As a result, verifying whether (2) is G.A.S. for differential TD without a local clock is substantially more challenging than it initially appears. Nevertheless, this paper makes three contributions. First, we establish the almost sure convergence of on-policy n-step differential TD for any n without the local clock. Second, we give three different sufficient conditions for the almost sure convergence of off-policy n-step differential TD without the local clock. Admittedly, our characterization in the off-policy case is incomplete and we correspondingly present our third contribution: we outline a few challenges and open problems in this area. 2 Background In this work, all vectors are column. The ℓ2 _2 norm in ℝdR^d is denoted by ∥⋅∥ ·. The identity matrix is denoted by I, and we use e to denote the all-one vector. For a matrix A∈ℝn×nA ^n× n, we denote its spectral radius by λmax(A)≐max|λ|:λ∈σ(A) _ (A) λ:λ∈σ(A), with σ(A)σ(A) as the set of eigenvalues of A. We say that a matrix A is (strictly) positive stable if ∀λ∈σ(A)∀λ∈σ(A) Reλ≥0 λ≥ 0 (Reλ>0 λ>0). It is easy to see that A is strictly positive stable if and only if −A-A is Hurwitz.333“Hurwitz” is often used in the control community while “positive stable” is often used in the linear algebra community If a matrix A has only nonnegative (positive) entries, we write A≥0A≥ 0, (A>0A>0). If a matrix A is positive definite, we write A≻0A 0. Given any vector x, ∑xΣ x denotes the sum of all elements in x. We use Ai,jA_i,j to refer to the (i,j)(i,j)-th entry of A. Definition 2.1. An M−M-matrix is a matrix of the form γI−Pγ I-P where P∈ℝn×nP ^n× n, P≥0P≥ 0, and γ≥λmax(P)γ≥ _ (P). In RL, we consider a Markov Decision Process (MDP; bellman1957markovian; puterman2014markov) with a finite state space S, a finite action space A, a reward function r:×→ℝr:S×A , a transition function p:×→[0,1]p:S×S×A→[0,1], an initial distribution p0:→[0,1]p_0:S→[0,1]. At time step 0, an initial state S0S_0 is sampled from p0p_0. At time t, given the state StS_t, the agent samples an action At∼π(⋅|St)A_t π(·|S_t), where π:×→[0,1]π:A×S→[0,1] is the policy being followed by the agent. A reward Rt+1≐r(St,At)R_t+1 r(S_t,A_t) is then emitted and the agent proceeds to a successor state St+1∼p(⋅|St,At)S_t+1 p(·|S_t,A_t). We assume the Markov chain St S_t induced by the policy π is ergodic and thus adopts a unique stationary distribution dπd_π. We define Dπ=diag(dπ)D_π=diag(d_π). The average reward (a.k.a. gain, puterman2014markov) is defined as J¯π≐limT→∞1T∑t=1T[Rt]. J_π _T→∞ 1T _t=1^TE [R_t ]. Consequently, the differential value function (a.k.a. bias, puterman2014markov) is defined as vπ(s)≐limT→∞1T∑τ=1T[∑i=1τ(Rt+i−J¯π)∣St=s].v_π(s) _T→∞ 1T _τ=1^TE [ _i=1^τ(R_t+i- J_π) S_t=s ]. The corresponding Bellman equation (a.k.a. Poisson’s equation) is then v=rπ−J¯πe+Pπv, v=r_π- J_πe+P_πv, (3) where v∈ℝ||v ^|S| is the free variable, rπ∈ℝ||r_π ^|S| is the reward vector induced by the policy π, i.e., rπ(s)≐∑aπ(a|s)r(s,a)r_π(s) _aπ(a|s)r(s,a), and Pπ∈ℝ||×||P_π ^|S|×|S| is the transition matrix induced by the policy π, i.e., Pπ(s,s′)≐∑aπ(a|s)p(s′|s,a)P_π(s,s ) _aπ(a|s)p(s |s,a). It is known (puterman2014markov) that all solutions to (3) form a set ∗≐vπ+ce∣c∈ℝ.V_* v_π+ce c . The policy evaluation problem in average reward MDPs is to estimate vπv_π, perhaps up to a constant offset cece. In the off-policy setting, an agent aims to evaluate a target policy π but follows a behavior policy μ. We define the importance sampling ratio ρ(s,a)≐π(a|s)μ(a|s)ρ(s,a) π(a|s)μ(a|s) and ρt≐ρ(St,At) _t ρ(S_t,A_t). 3 Differential Temporal Difference Learning Differential TD is designed to estimate vπv_π in an online manner. The differential TD algorithm proposed by wan2020learning only considers a one-step look-ahead. Inspired by the success of n-step TD in the discounted setting (sutton2018reinforcement), we first extend the 1-step differential TD to the n-step case. As we shall see soon, this extension is vital to the analysis in the off-policy setting. Here we only present off-policy n-step differential TD as the on-policy version is just a special case with μ=πμ=π. Suppose a trajectory S0,A0,R1,S1,…\S_0,A_0,R_1,S_1,…\ is generated by following a behavior policy μ as At∼μ(⋅∣St)A_t μ(· S_t). Since the n-step return for StS_t is only observable after reaching St+nS_t+n, the iterates vt∈ℝ||,Jt∈ℝ v_t ^|S|, J_t are updated at time t+nt+n as δt=Rt+1:t+n−nJt+n−1+vt+n−1(St+n)−vt+n−1(St), _t= R_t+1:t+n-nJ_t+n-1+v_t+n-1(S_t+n)-v_t+n-1(S_t), (4) Jt+n=Jt+n−1+ηnαt+n−1ρt:t+n−1δt, J_t+n= J_t+n-1+ ηn _t+n-1 _t:t+n-1 _t, (5) vt+n(St)=vt+n−1(St)+αt+n−1ρt:t+n−1δt, v_t+n(S_t)=v_t+n-1(S_t)+ _t+n-1 _t:t+n-1 _t, (6) where ρt:t+n−1≐∏k=t+n−1ρk _t:t+n-1 _k=t^t+n-1 _k and Rt+1:t+n≐∑k=1nRt+kR_t+1:t+n _k=1^nR_t+k are shorthands. To our knowledge, this is the first time that n-step differential TD is formalized, and the complete derivation is presented in Appendix B. When n=1n=1, it recovers the 11-step differential TD in wan2020learning. However, in the convergence analysis in wan2020learning, they replace the learning rate αt _t with αν(t,St) _ν(t,S_t). We recall that ν(t,s)ν(t,s) counts the number of visits to the state s until time t and is referred to as the local clock. In this work, we shall conduct our analysis of (6) directly without altering the learning rates. Inspired by wan2020learning, to facilitate our analysis, we first rewrite (6) to eliminate the iterates Jt\J_t\. Define Σt≐∑svt(s) _t _sv_t(s). Since the n−n-step return for StS_t is only available after time t+nt+n, we adopt the standard convention that no updates occur before the first n−n-step return is observed, so JtJ_t and vtv_t are constant for t<nt<n. Making use of the fact that vt+nv_t+n and vt+n−1v_t+n-1 differ from each other only for the StS_t-indexed entry, we obtain Jt+n−Jn−1 J_t+n-J_n-1 =∑i=0tηnαi+n−1ρi:i+n−1δi, = _i=0^t ηn _i+n-1 _i:i+n-1 _i, (7) =∑i=0tηn(vi+n(Si)−vi+n−1(Si)), = _i=0^t ηn (v_i+n(S_i)-v_i+n-1(S_i)), (8) =∑i=0tηn∑s(vi+n(s)−vi+n−1(s)), = _i=0^t ηn _s (v_i+n(s)-v_i+n-1(s)), (9) =ηn(Σt+n−Σn−1). = ηn\,( _t+n- _n-1). (10) We can then rewrite δt _t from (6) as δt _t =Rt+1:t+n−n(Jn−1+ηn(Σt+n−1−Σn−1)) =R_t+1:t+n-n (J_n-1+ ηn( _t+n-1- _n-1)) (11) +vt+n−1(St+n)−vt+n−1(St). +v_t+n-1(S_t+n)-v_t+n-1(S_t). (12) Then, (6) can be expressed more compactly as vt+n(St)=vt+n−1(St)+αt+n−1ρt:t+n−1(R~t+1:t+n v_t+n(S_t)=v_t+n-1(S_t)+ _t+n-1 _t:t+n-1 ( R_t+1:t+n (13) −ηΣt+n−1+vt+n−1(St+n)−vt+n−1(St)), -η _t+n-1+v_t+n-1(S_t+n)-v_t+n-1(S_t) ), (14) where R~t+1:t+n≐∑k=1n(Rt+k−Jn−1+ηnΣn−1) R_t+1:t+n _k=1^n(R_t+k-J_n-1+ ηn _n-1). We assume initialization with Jn−1≐0J_n-1 0 and vn−1≐0v_n-1 0 for simplifying presentation so that R~t+1:t+n=Rt+1:t+n R_t+1:t+n=R_t+1:t+n. For nonzero initialization of J0J_0 and v0v_0, we only need to conduct the same analysis in a new MDP with a shifted reward function r~(s,a)↦r(s,a)−Jn−1+ηnΣn−1 r(s,a) r(s,a)-J_n-1+ ηn _n-1 (wan2020learning). 4 Convergence of Differential Temporal Difference Learning We make the following standard assumptions. Assumption 4.1 (Ergodicity and coverage). The Markov chains induced by the behavior policy μ and target policy π are finite, irreducible, and aperiodic. The behavior policy μ covers π i.e. ∀s∈,∀a∈:π(a∣s)>0⟹μ(a∣s)>0.∀\,s ,\ ∀\,a : π(a s)>0 μ(a s)>0. The ergodicity assumption is standard for analyzing RL algorithms (bertsekas1996neuro). Furthermore, the coverage assumption is the same as in sutton2018reinforcement. From Assumption 4.1, the Markov chains induced by the behavior policy and target policy each adopt a unique stationary distribution, which we denote respectively as dπd_π and dμd_μ. Because the Markov chains are irreducible, dπ>0d_π>0 and dμ>0d_μ>0 (puterman2014markov). Assumption 4.2. The learning rates αt _t are positive, decreasing, and satisfy ∑t=0∞αt=∞,limt→∞αt=0,andαt−αt+1αt=(αt). _t=0^∞ _t=∞, _t→∞ _t=0,\,and\, _t- _t+1 _t=O( _t). (15) This is the standard set of assumptions for learning rates in stochastic approximation (borkar2009stochastic). We emphasize that this definition of the learning rates is far more widely used compared to the state visitation-dependent learning rates found in wan2020learning. For example, Assumption 4.2 is satisfied by any learning rate of the form αt=C1(n+C2)β _t= C_1(n+C_2)^β where C1C_1 and C2C_2 are constants and β∈(0.5,1]β∈(0.5,1]. Our proof of convergence will utilize some results from the stochastic approximation (SA) community. Thus, we begin by writing the update (14) as a canonical stochastic approximation update by first defining an augmented Markov chain Yt Y_t evolving in a finite state space Y as, Yt+1=(St,At,St+1,At+1,…,At+n−1,St+n). Y_t+1= (S_t,A_t,S_t+1,A_t+1,…,A_t+n-1,S_t+n). (16) From Assumption 4.1, it is clear that Yt Y_t is also irreducible and aperiodic, and we denote its stationary distribution as d_Y. Then, we can define the operator H:ℝ||×→ℝ||H:R S×Y S as, H(v,y)[s] H (v,y)[s] ≐ρ0:n−1(y)(∑k=0n−1r(sk,ak)−η∑v _0:n-1(y) ( _k=0^n-1r(s_k,a_k)-ηΣ v (17) +v(sn)−v(s0))s=s0. +v(s_n)-v(s_0) )I s=s_0. (18) where we have y≐(s0,a0,…sn)y (s_0,a_0,… s_n) and ρ0:n−1(y)≐∏k=0n−1ρ(sk,ak) _0:n-1(y) _k=0^n-1ρ(s_k,a_k). Then we can write (14) as a canonical SA algorithm according to vt+1=vt+αtH(vt,Yt+1). v_t+1=v_t+ _tH(v_t,Y_t+1). (19) Note that the SA iteration index t differs from the environment time step in (14). One SA update corresponds to an n-step block of experience, so SA step t corresponds to environment time t+n−1t+n-1, since the tuple Yt+1Y_t+1 becomes available only after observing up to St+nS_t+n. One prominent method for analyzing the asymptotic behavior of vt v_t is to regard vt v_t as Euler’s discretization of the ODE dv(t)dt v(t)t =h(v(t)) =h(v(t)) (20) where the expected operator h(v)≐y∼d[H(v,y)]h(v) _y d_Y [H(v,y)]. Using this method, the asymptotic behavior of the discrete and stochastic updates vt v_t can be characterized by the continuous and deterministic trajectories of the ODE (20), if the stability of the iterates can be established. The Borkar-Meyn theorem (borkar2000ode) establishes the desired stability given the ODE@∞ is G.A.S., which is defined as dv(t)dt v(t)t =h∞(v(t)), =h_∞(v(t)), (21) where h∞≐limc→∞h(cv)ch_∞ _c→∞ h(cv)c. Although the original work of borkar2000ode only allows for Yt Y_t to be i.i.d, recently liu2024ode generalized the Borkar-Meyn theorem to Markovian noise Yt Y_t under equally mild assumptions, an important extension which we will leverage here since our Yt Y_t in (16) is a Markov chain. We therefore proceed by studying the expected operator for (14): h(v)[s] h(v)[s] =y∼d[H(v,y)[s]] =E_y d_Y [H(v,y)[s]] (22) =μ[ρ0:n−1(y)(∑k=0n−1r(sk,ak)−η∑v = _μ [ _0:n-1(y) ( _k=0^n-1r (s_k,a_k)-ηΣ v (23) +v(sn)−v(s))s=s0] +v (s_n)-v(s) )I s=s_0 ] (24) =dμ(s)μ[ρ0:n−1(y)(∑k=0n−1r(sk,ak) = d_μ(s)E_μ [ _0:n-1(y) ( _k=0^n-1r (s_k,a_k) (25) −η∑v+v(sn)−v(s))|s0=s], -ηΣ v+v (s_n)-v(s) ) |s_0=s ], (26) where we have used μE_μ to abbreviate the expectation over the trajectory generated by ak∼μ(⋅|sk)a_k μ(·|s_k) and sk+1∼p(⋅|sk,ak)s_k+1 p(·|s_k,a_k). Isolating the reward-sum term, we define the expected n-step reward by r(n)(s) r^(n)(s) ≐μ[ρ0:n−1∑k=0n−1r(sk,ak)|s=s0] _μ [ _0:n-1 _k=0^n-1r (s_k,a_k) |s=s_0] (27) =π[∑k=0n−1r(sk,ak)|s=s0] = _π [ _k=0^n-1r (s_k,a_k) |s=s_0] (28) =∑k=0n−1(Pπkrπ)(s). = _k=0^n-1 (P_π^kr_π)(s). (29) Therefore, the expected operator for (14) is h(v) h(v) =Dμ(r(n)−ηee⊤v+Pπnv−v), =D_μ(r (n)-η e v+P_π^nv-v), (30) where DμD_μ is a diagonal matrix whose entries are dμd_μ. The corresponding ODE@∞ is dv(t)dt v(t)t =h∞(v(t))=Dμ(Pπn−I−ηee⊤)v(t)=−Av(t), =h_∞(v(t))=D_μ (P_π^n-I-η e )v(t)=-Av(t), (31) where A≐Dμ(I−Pπn+ηee⊤)A D_μ (I-P_π^n+η e ). We now outline the structure of our proof. The first milestone is to prove that the ODE (31) is G.A.S. It is then trivial to see that (20) is also G.A.S.. We will use v∞v_∞ to denote the G.A.S. equilibrium of (20) and we have h(v∞)=0h(v_∞)=0. This means that r(n)−ηee⊤v∞+Pπnv∞−v∞=0r (n)-η e v_∞+P_π^nv_∞-v_∞=0. The analysis in Appendix B.2.1 of wan2020learning, which we omit to avoid redundancy, then immediately confirms that v∞∈∗v_∞ _*. The second milestone is to invoke a result from liu2024ode (stated as Lemma A.7 in the Appendix) to prove that the iterates vt v_t generated in (14) converge to v∞v_∞ almost surely. We now proceed to carry out this proof strategy in detail. It is known that a necessary and sufficient condition for (31) to be G.A.S. is that A is strictly positive stable (Theorem 4.5 from khalil2002nonlinear). wan2020learning essentially prove that the matrix I−Pπn+ηee⊤I-P_π^n+η e is strictly positive stable. However, this does not mean that the A matrix is strictly positive stable. This is an instance of the D-stability problem. As discussed in Section 6, this is a very challenging problem in the linear algebra community. Nevertheless, to prove A is strictly positive stable, we will utilize the results from bierkens2014singular, which we present as Lemma 4.3, that establish conditions under which M-matrices (see Definition 2.1) are strictly positive stable under rank one perturbations. Lemma 4.3. (Theorem 2.7 from bierkens2014singular). Let B∈ℝn×nB ^n× n and v,w∈ℝnv,w ^n. Then B+vw⊤B+vw is strictly positive stable if: 1. B=λmax(K)I−KB= _ (K)I-K is a singular M-matrix where K∈ℝn×nK ^n× n. 2. 0 is a geometrically simple eigenvalue of B with left and right eigenvectors zl≠0z_l≠ 0 and zr≠0z_r≠ 0. (i.e. zl⊤B=0z_l B=0 and Bzr=0Bz_r=0). 3. (zl⊤v)(w⊤zr)≠0(z_l v)(w z_r)≠ 0 and either of the following conditions hold: 4. Bv=0Bv=0, or w⊤B=0w B=0. 5. v,w>0v,w>0 and 2Ki,j≥viwj∀i,j2K_i,j≥ v_iw_j\,∀\,i,j (where viv_i, respectively, wjw_j denote the i-th entry of v and the j-th entry of w) To utilize Lemma 4.3 to prove the strict positive stability of A from (31), we begin by decomposing A into the form of B+vw⊤B+vw with, A A =Dμ(I−Pπn+ηee⊤) =D_μ (I-P_π^n+η\,e\,e ) (32) =I−I+Dμ(I−Pπn)+ηdμe⊤ =I-I+D_μ(I-P_π^n)+η\,d_μ\,e (33) =I−(I+Dμ(Pπn−I))+ηdμe⊤ =I- (I+D_μ(P_π^n-I))+η d_μe (34) ≐B+ηdμe⊤, B+η d_μe , (35) where B≐I−(I+Dμ(Pπn−I))B I- (I+D_μ(P_π^n-I)), and we recall that η is a positive constant. Without any additional assumptions, we can verify the first three conditions of Lemma 4.3 in the following Lemma. Lemma 4.4. Let Assumption 4.1 hold. Then, B≐I−(I+Dμ(Pπn−I))B I- (I+D_μ(P_π^n-I)), v≐ηdμv η d_μ, and w≐ew e satisfy conditions 1-3 of Lemma 4.3. Proof. First, we verify Condition 1. If we define K≐I+Dμ(Pπn−I)K I+D_μ(P_π^n-I), we have B=I−KB=I-K. Therefore, it is sufficient to prove that λmax(K)=1 _ (K)=1. Since Dμ=diag(dμ)D_μ=diag(d_μ) with dμ>0d_μ>0 and PπnP_π^n is non‐negative, it is easy to see that K≐I+Dμ(Pπn−I)=(I−Dμ)+DμPπn K I+D_μ(P_π^n-I)=(I-D_μ)+D_μP_π^n (36) is non-negative. Additionally, computing the row sums of K, we see that it is row-stochastic: Ke Ke =(I−Dμ)e+DμPπne=e−Dμe+Dμe=e, =(I-D_μ)e+D_μP_π^ne=e-D_μe+D_μe=e, (37) where the second equality holds because the transition matrix PπnP_π^n is row-stochastic. Then, we are guaranteed that λmax(K)=1 _ (K)=1 (Theorem 8.1.22 from horn2012matrix). To verify Condition 2, we demonstrate that B has 0 as an algebraically (and therefore geometrically) simple eigenvalue with left and right eigenvectors zl,zr≠0z_l,z_r≠ 0 (i.e. zl⊤B=0z_l B=0 and Bzr=0Bz_r=0). We have kerB B =ker(I−K)=zr:Kzr=zr. = (I-K)= z_r:Kz_r=z_r. (38) Additionally, since B⊤=(I−K)⊤B =(I-K) we have kerB⊤=ker(I−K)⊤=zl:zl⊤K=zl⊤. B = (I-K) = z_l:z_l K=z_l . (39) Since PπP_π is irreducible and aperiodic by Assumption 4.1, PπnP_π^n is irreducible for every n≥1n≥ 1 (puterman2014markov). Multiplying a positive diagonal matrix and adding another positive diagonal matrix leaves the zero pattern unchanged so K=I−Dμ+DμPπnK=I-D_μ+D_μP_π^n is also irreducible. Therefore, the Perron-Frobenius theorem (Theorem 8.4.4 in horn2012matrix) guarantees that one is an algebraically simple eigenvalue of K. This implies that kerB B and kerB⊤ B are one‑dimensional, and thus zero is a geometrically simple eigenvalue of B. We identify the one-dimensional left and right kernels of B as, kerB=span(e),kerB⊤=span(dπ/dμ), B=span(e), B =span (d_π/d_μ), (40) where dπ/dμd_π/d_μ represents element-wise division. For the right kernel, it holds trivially from (38) and the fact that K is row-stochastic. For the left kernel, with B⊤=I−K⊤=Dμ−Pπn⊤DμB =I-K =D_μ-P_π^n D_μ we have, B⊤(dπdμ)=Dμ(dπdμ)−Pπn⊤Dμ(dπdμ)=dπ−Pπn⊤dπ=0. B ( d_πd_μ)=D_μ ( d_πd_μ)-P_π^n D_μ ( d_πd_μ)=d_π-P_π^n d_π=0. (41) Clearly zl=dπ/dμz_l=d_π/d_μ and zr=ez_r=e are both nonzero, so Condition 2 is satisfied. To verify Condition 3, we note that all components of e and dπdμ d_πd_μ are strictly positive, so any non-zero vector zl⊤∈span(dπdμ)z_l ( d_πd_μ) and zr∈span(e)z_r (e) will have uniform sign. Using the fact that v=ηdμv=η d_μ and w=ew=e are strictly positive, it is easy to see that (zl⊤v)(w⊤zr)=η(zl⊤dμ)(e⊤zr)≠0.(z_l v)(w z_r)=η(z_l d_μ)(e z_r)≠ 0. (42) ∎ Although we have verified Conditions 1-3 of Lemma 4.3 using only Assumption 4.1, we still need either Condition 4 or 5 to establish that A is strictly positive stable. We therefore split the analysis into two regimes. In the on-policy case with μ=πμ=π (Section 4.1), we are able to directly satisfy Condition 4. In the off-policy case (Section 4.2), additional restrictions are needed, and we provide three sufficient conditions. 4.1 On-Policy Case In the on-policy case, we consider the following assumption. Assumption 4.5 (On-policy). The behavior policy followed by the agent is the target policy, i.e., π(a|s)=μ(a|s)∀s∈,a∈π(a|s)=μ(a|s)\,∀ s ,a . To prove the strict positive stability of A in the on-policy case, since Conditions 1-3 are already in place from Lemma 4.4, it remains only to verify Condition 4. Theorem 4.6 does so, thereby establishing the strict positive stability of A. Corollary 4.7 then gives the almost-sure convergence of Differential TD. Theorem 4.6. Let Assumptions 4.1 and 4.5 hold. Then, A=B+ηdμe⊤A=B+η d_μe is strictly positive stable for any n≥1n≥ 1 and any η>0η>0. Proof. Recall from (35), we have expressed A in the form of B+vw⊤B+vw where B≐I−(I+Dμ(Pπn−I))B I- (I+D_μ(P_π^n-I)), v=ηdμv=η d_μ and w=ew=e. Lemma 4.3 states that A is strictly positive-stable once Conditions 1-3 together with either Condition 4 or 5, are satisfied. In Lemma 4.4 we verify the first three conditions of Lemma 4.3 with this choice of B,v,wB,v,w. In the on-policy case (Assumption 4.5), we have μ=πμ=π, which further gives B=I−(I+Dπ(Pπn−I)),v=ηdπ,w=e. B=I- (I+D_π(P_π^n-I)), v=η d_π, w=e. (43) To demonstrate Condition 4 holds in the on-policy setting, we show w⊤B=0w B=0 with, w⊤B=e⊤Dπ(I−Pπn)=dπ⊤(I−Pπn)=0. w B=e D_π(I-P_π^n)=d_π (I-P_π^n)=0. (44) ∎ Corollary 4.7. Let Assumptions 4.1, 4.2 and 4.5 hold. Then the iterates vt v_t in (14) satisfy: limt→∞vt=v∞,a.s. _t→∞v_t=v_∞,\ a.s., where v∞∈∗v_∞ _*. Proof. To prove the almost sure convergence of the differential TD iterates in (14) to fixed point v∞v_∞ we will utilize Corollary 8 from (liu2024ode) which we present as Lemma A.7. We proceed by verifying the requisite Assumptions A.1-A.6. Starting with Assumption A.5, in Theorem 4.6 we prove that A defined in (31) is strictly positive stable under Assumptions 4.1, 4.2, 4.5. Therefore, the ODE@∞ in (31), is G.A.S. (Theorem 4.5 from khalil2002nonlinear). Verifying the remaining assumptions is straightforward. Note that our Assumptions 4.1 and 4.2 are sufficient to directly satisfy Assumptions A.1, A.2 and A.6. We refer the reader to Remarks 1-3 of (liu2024ode) for a discussion on how these are trivially satisfied for ergodic and finite Yt Y_t. We then verify Assumption A.3 in Lemma C.1. It is easy to verify that H(x,y)H(x,y) is Lipschitz, which we present for completeness in Lemma C.2 that satisfies A.4. Then, Lemma A.7 guarantees that vt v_t converges to the invariant set of the ODE, which is a singleton we denote as v∞v_∞. ∎ 4.2 Off-Policy Case In the off‐policy setting, we consider three additional assumptions. We will first prove that there exists some η0 _0 for which for η∈(0,η0]η∈(0, _0], A is strictly positively stable using an extension of Lemma 4.3, Lemma 4.8. Lemma 4.8 (Lemma 2.11 from bierkens2014singular). Let B∈ℝn×n,v,w∈ℝn,v,w≥0B ^n× n,v,w ^n,v,w≥ 0 satisfy Conditions 1-3 of Lemma 4.3. Additionally, let 0 be an algebraically simple eigenvalue of B. Define a matrix-valued curve Γ(t):t→B+tvw⊤,t∈ℝ (t):t→ B+tvw ,t . There exists a t0>0t_0>0 such that Γ(t) (t) is strictly positive stable for t∈(0,t0]t∈(0,t_0]. Lemma 4.9. Let Assumption 4.1 hold. Then, there exits a η0>0 _0>0 such that A=B+ηdμe⊤A=B+η d_μe is strictly positive stable for η∈(0,η0]η∈(0, _0]. Proof. Recall from (35) that A=B+ηdμe⊤A=B+η d_μe where B≐I−(I+Dμ(Pπn−I))B I- (I+D_μ(P_π^n-I)). By Lemma 4.4, B, dμd_μ, and e satisfy Conditions 1-3 of Lemma 4.3. 444In Lemma 4.4, we prove this for v=ηdμv=η d_μ instead of v=dμv=d_μ. However, since η is a positive constant, its easy to see that the argument still holds. Therefore, if we set v=dμv=d_μ, w=ew=e and t=ηt=η, then A=B+tvw⊤A=B+tvw and Lemma 4.8 guarantees the existence of some t0>0t_0>0 (hence η0 _0) for which Γ(t)=B+tvw⊤ (t)=B+tvw is strictly positive stable on (0,t0](0,t_0]. It remains only to check that 0 is algebraically simple for B. To show this, we need to show that 0 is a simple root of the characteristic polynomial of B. We use χM(λ)=det(M−λI) _M(λ)= (M-λ I) to denote the characteristic polynomial of a matrix M. Recall the definition of K from (36). Then, the characteristic polynomial of B=I−KB=I-K is, χB(λ) _B(λ) =det((I−K)−λI) = ((I-K)-λ I) (45) =(−1)||det(K−(1−λ)I) =(-1)^|S| (K-(1-λ)I) (46) =(−1)||χK(1−λ). =(-1)^|S| _K(1-λ). (47) We proved in Lemma 4.6 that 11 is an algebraically simple eigenvalue of K. In other words, χK(κ) _K(κ) has a simple root at κ=1κ=1. Then the change of variable κ↦1−λκ 1-λ implies λ=0λ=0 is a simple root of χB _B. Thus 0 is an algebraically simple eigenvalue of B. Then, Lemma 4.8 proves that there exists some η0>0 _0>0 for which A=B+ηdμe⊤A=B+η d_μe is strictly positive stable on (0,η0](0, _0]. ∎ Having established that A is strictly positive–stable, the almost‐sure convergence of (14) to v∞v_∞ follows immediately by the same argument used in Corollary 4.7. In that proof, every assumption except A.5 was checked without invoking Assumption 4.5, and A.5 itself is a direct consequence of the strict positive stability of A. Therefore, we omit the proof of the corollary to avoid redundancy. Corollary 4.10. Let Assumptions 4.1, 4.2 hold. Then there exists some positive constant η0>0 _0>0 such that for η∈(0,η0]η∈(0, _0] the iterates vt v_t in (14) satisfy limt→∞vt=v∞,a.s. _t→∞v_t=v_∞,\ a.s., where v∞∈∗v_∞ _*. The main limitation of this result is that, while it guarantees some η0>0 _0>0, it does not offer a closed form for its value. To address this, we impose the additional assumption that PπnP_π^n becomes strictly positive under sufficiently large n. Under this condition, we can characterize η0 _0. Assumption 4.11. PπnP_π^n is strictly positive. Such an n is guaranteed to exist by the irreducibility of PπP_π from Assumption 4.1 (levin2017markov). Theorem 4.12. Let Assumption 4.1 and 4.11 hold. Then, A=B+ηdμe⊤A=B+η d_μe is strictly positive stable for η∈(0,η0]η∈(0, _0] where η0≐2mini,jPπn(i,j) _0 2 _i,jP_π^n(i,j). Proof. To prove that A is strictly positive stable with the addition of Assumption 4.11, we will once again utilize Lemma 4.3. Lemma 4.4 shows that B defined in (35), v=ηdμ,v=η d_μ, and w=ew=e satisfy the first three conditions of Lemma 4.3. In addition to Conditions 1-3, we will also prove that Condition 5 holds, which is sufficient to guarantee the strict positive stability of A. Because PπnP_π^n is strictly positive, we have Kij K_ij =(1−dμ(i))i=j+dμ(i)Pπn(i,j) = (1-d_μ(i))I i=j+d_μ(i)P_π^\,n(i,j) (48) ≥dμ(i)pmin∀i,j. ≥ d_μ(i)\,p_ ∀\,i,j. (49) where we define pmin≐mini,jPπn(i,j)>0p_ _i,jP_π^n(i,j)>0. For any η∈(0,η0]η∈(0, _0], we therefore have 2Kij≥2dμ(i)pmin≥ηdμ(i)=viwj,∀i,j, 2K_ij≥ 2d_μ(i)p_ ≥η d_μ(i)=v_iw_j,\,∀\,i,j, (50) so the entry-wise inequality in Condition 5 of Lemma 4.3 holds, and the theorem follows. ∎ Having established that A is strictly positive–stable, the almost‐sure convergence of (14) to v∞v_∞ follows immediately by the same argument used in Corollary 4.7. Corollary 4.13. Let Assumptions 4.1, 4.2, and 4.11 hold. Then for η∈(0,η0]η∈(0, _0], where η0≐2mini,jPπn(i,j) _0 2 _i,jP_π^n(i,j), the iterates vt v_t in (14) satisfy: limt→∞vt=v∞,a.s. _t→∞v_t=v_∞,\ a.s., where v∞∈∗v_∞ _*. Having presented two sufficient conditions on η and n, we now present the third sufficient condition on PπP_π. Namely, under the assumption that PπP_π is doubly stochastic, we are able to establish the strict positive stability of A for any η≥0η≥ 0 and n>0n>0. Assumption 4.14. PπnP_π^n is doubly stochastic (i.e. Pπne=eP_π^ne=e and e⊤Pπn=e⊤e P_π^n=e ). Admittedly, doubly stochastic matrices are a small portion of the transition matrices considered in RL. They do arise, however, in simple random walks on k-regular, undirected graphs, such as cycles and complete graphs (levin2017markov). Furthermore, doubly stochastic matrices are also a popular mathematical model (Section 8.7 horn2012matrix). Theorem 4.15. Let Assumptions 4.1, 4.2, and 4.14 hold. Then A is strictly positive-stable for every n and η>0η>0. Proof. By the Lyapunov theorem (Theorem 4.6 in khalil2002nonlinear), A is positive‐stable if and only if there exists a symmetric positive‐definite matrix M such that A⊤M+MA≻0A M+MA 0. In the off‐policy case we take M≐Dμ−1M D_μ^-1. Then with the definition of A from (31), we have A⊤M+MA A M+MA =(I−Pπn⊤+ηee⊤)+(I−Pπn+ηee⊤). =(I-P_π^n +η\,e )+(I-P_π^n+η\,e ). (51) We now show that (I−Pπn+ηee⊤)(I-P_π^n+η e ) is positive‐definite. When PπnP_π^n is doubly stochastic (so ‖Pπn‖=1 P_π^n=1), for any nonzero v∈ℝ||v ^|S|, v⊤(I−Pπn+ηee⊤)v v (I-P_π^n+η\,e )v =v⊤v−v⊤Pπnv+η(v⊤e)2 = v v-v P_π^nv+η(v e)^2 (52) ≥‖v‖2−‖Pπn‖‖v‖2+η(v⊤e)2 ≥ v^2- P_π^n v^2+η(v e)^2 (53) =(1−‖Pπn‖)‖v‖2+η(v⊤e)2 =(1- P_π^n) v^2+η(v e)^2 (54) =η(v⊤e)2>0 =η(v e)^2>0 (55) where the first inequality holds by Cauchy-Schwarz, and the second equality holds because ‖Pπn‖=1 P_π^n=1. ∎ Corollary 4.16. Let Assumptions 4.1, 4.2, and 4.14 hold. Then the iterates vt v_t in (14) satisfy: limt→∞vt=v∞,a.s. _t→∞v_t=v_∞,\ a.s., where v∞∈∗v_∞ _*. 5 Challenges and Open Problems We note that our off‐policy convergence guarantee in Corollary 4.13 rests on the conservative bound η≤η0=2mini,jPπn(i,j), η≤ _0=2 _i,jP_π^\,n(i,j), which requires PπnP_π^n to be strictly positive (Assumption 4.11). In this section, we demonstrate that empirically, this estimate for the upper bound of η is quite pessimistic. We consider a 5×55× 5 gridworld and set n=3n=3. Notably, an agent cannot reach every state in three steps. So η0=mini,jPπ3(i,j)=0 _0= _i,jP_π^3(i,j)=0 in this environment and Assumption 4.11 is violated. However, as Figure 1 shows, the algorithm still converges for a wide range of η values. This empirical result seems to suggest that the convergence can be obtained for any η. Furthermore, wan2020learning also prove the convergence for any η with local-clock-based learning rates. Then we might expect that some future work may be able to prove the convergence for any η without the local clock as well. However, we must be cautious here. anehila2022note exhibit M-matrix counterexamples satisfying Conditions 1–3 for which B+tvw⊤B+tvw fails to remain strictly positive-stable once t exceeds some finite threshold. This implies our Lemma 4.9 may not hold for large η. Crucially, the linear algebra community still lacks a tight upper bound on admissible η and has no known necessary and sufficient characterization of triples (B,v,w)(B,v,w) that ensure stability under rank-one perturbation (anehila2022note). Closing that theoretical gap would immediately yield sharper convergence guarantees here, and thus represents an important direction for future work. Figure 1: Off‐policy convergence of n–step differential TD in a 5×55× 5 gridworld (n=3n=3) for various η. Although η0=0 _0=0 here, the algorithm is stable across η. We use a variant of root mean-squared value error from tsitsiklis1999average, denoted as ‘RMSVE (TVR)’, which measures the distance of the estimated values to the nearest solution that satisfies the Bellman equation (3). The trials are averaged over 30 seeds with shaded regions as 1 standard error. The experimental details and results for other n values appear in Appendix C. 6 Related Work Average Reward RL. Several temporal difference methods have been proposed for Markov decision processes with an average-reward objective. The best known is the average reward TD algorithm of tsitsiklis1999average, whose convergence guarantees were first analyzed in the linear function approximation case, and further extended to the tabular setting by blaser2026asymptotic. The differential TD algorithm we analyze here belongs to the same family but estimates the average reward with the full temporal-difference error instead of only using the reward sample (wan2020learning). Additional TD-based algorithms for policy evaluation and control in the average-reward setting include konda2000actor; abounadi2001learning; yang2016efficient; wan2021average; zhang2021policy; zhang2020average; zhang2021breaking; he2023loosely; saxena2023off; xie2025finite. Convergence of RL Algorithms. The investigation of the almost sure convergence of RL algorithms is an active area of research. Most prior work relies on the ODE based approach (benveniste1990MP; kushner2003stochastic; borkar2009stochastic; liu2024ode), where the corresponding ODE is relatively easy to analyze (tsitsiklis1997analysis; konda2000actor; sutton2009convergent; sutton2009fast; zhang2020gradientdice; zhang2019provably; maei2011gradient; zhang2021truncated). By contrast, the ODE studied in this work is highly nontrivial to analyze, and and we still do not have a complete characterization of it. Other notable works involving nontrivial ODEs include meyn2024projected; wang2024almost. In addition to the ODE based approach, the Robbins-Siegmund theorem (robbins1971convergence) and its variant (liu2025extensions) are gaining increasing attention for establishing almost sure convergence (bertsekas1996neuro; qian2024almost; qian2025revisiting; liu2025extensions), and has recently been formally verified (zhang2025towards). Beyond (asymptotic) almost sure convergence, the L2L^2 convergence rates of RL algorithms are also widely studied. Notable works include mahadevan2014proximal; liu2015finite; wang2017finite; srikant2019finite; zou2019finite; wu2020finite; zhang2022globaloptimalityfinitesample; xie2025finite; liu2025linearq. Matrix Stability Under Perturbations and D-stability. The stability question in our paper lies within the broader D-stability problem which asks whether a given real matrix A∈ℝn×nA ^n× n remains strictly positive stable under left multiplication by any positive diagonal matrix D≻0D 0. Despite Johnson’s necessary and sufficient criteria in low dimensions (johnson1974sufficient; johnson1974d), the general case (n>4n>4) remains open, see hershkowitz1992recent and kushel2019unifying for comprehensive surveys. Our analysis is based on the results of bierkens2014singular who investigated the D-stability of M matrices under nonnegative rank-one perturbations. Their work extends a broader area of research investigating the eigenvalues and Jordan structure of rank-one perturbations of matrices (moro2003low; savchenko2004change; ding2007eigenvalues; mehl2011eigenvalue; ran2012eigenvalues; fourie2013rank; mehl2014eigenvalue; ran2021global). 7 Conclusion Learning rates that use a local clock have played an essential role in the theoretical analysis of differential TD (wan2020learning), yet they remain largely unused by practitioners. This work bridges that divide by applying D−D-stability and rank-one perturbation theory from the linear algebra community, to provide novel almost sure convergence results of differential TD. To our knowledge, this is the first use of D−D-stability and rank-one perturbation techniques in RL. We expect this approach to enable further theoretical advances in RL, such as convergence proofs for differential Q-learning (wan2020learning) and for RVI Q-learning (abounadi2001learning) without relying on a local clock. Acknowledgements EB acknowledges support from the NSF Graduate Research Fellowship under award 1842490. This work is supported in part by the US National Science Foundation under the awards I-2128019, SLES-2331904, and CAREER-2442098, the Commonwealth Cyber Initiative’s Central Virginia Node under the award V-1Q26-001, a Cisco Faculty Research Award, and an NVIDIA academic grant program award. References Appendix Appendix A Mathematical Background A.1 Main Results from liu2024ode First we will restate the main results from liu2024ode concerning the convergence of SA iterates of the form (19) for completeness. Assumption A.1. The Markov chain Yn Y_n has a unique invariant probability measure (i.e. stationary distribution), denoted by d_Y. Assumption A.2. The learning rates αn _n are positive, decreasing and satisfy ∑i=0∞αi=∞,limn→∞αn=0,andαn−αn+1αn=(αn). _i=0^∞ _i=∞, _n→∞ _n=0,\,and\, _n- _n+1 _n=O( _n). (56) Assumption A.3. Let Hc(x,y)≐1cH(cx,y)H_c(x,y) 1cH(cx,y). There exists a measurable function H∞(x,y)≐limc→∞Hc(x,y)H_∞(x,y) _c→∞H_c(x,y), a scalar function κ:ℝ→ℝκ (independent of x,yx,y), and a measurable function b(x,y)b(x,y) such that for any x,yx,y: Hc(x,y)−H∞(x,y) H_c(x,y)-H_∞(x,y) =κ(c)b(x,y), =κ(c)b(x,y), (57) limc→∞κ(c) _c→∞κ(c) =0. =0. (58) Moreover, there exists a measurable function Lb(y)L_b(y) such that for all x,x′,yx,x ,y, ‖b(x,y)−b(x′,y)‖ b(x,y)-b(x ,y) ≤Lb(y)∥x−x′∥, ≤ L_b(y)\, x-x , (59) and the expectation, Lb≐y∼dy[Lb(y)] L_b _y d_y [L_b(y) ] (60) is well-defined and finite. Assumption A.4. There exists a measurable function L(y)L(y) such that for any x,x′,yx,x ,y, ‖H(x,y)−H(x′,y)‖ H(x,y)-H(x ,y) ≤L(y)∥x−x′∥, ≤ L(y)\, x-x , (61) ‖H∞(x,y)−H∞(x′,y)‖ H_∞(x,y)-H_∞(x ,y) ≤L(y)∥x−x′∥. ≤ L(y)\, x-x . (62) Moreover, the following expectations are well‐defined and finite for every x: h(x) h(x) ≐y∼dy[H(x,y)], _y d_y [H(x,y) ], (63) h∞(x) h_∞(x) ≐y∼dy[H∞(x,y)], _y d_y [H_∞(x,y) ], (64) L L ≐y∼dy[L(y)]. _y d_y [L(y) ]. (65) Assumption A.5. As c→∞c→∞, hc(x)h_c(x) converges to h∞(x)h_∞(x) uniformly on x on any compact subsets of ℝdR^d. The ODE, dx(t)dt=h∞(x(t)) x(t)t=h_∞(x(t)) (66) has 0 as its G.A.S equilibrium. Assumption A.6. Let g denote any of the following functions: y y ↦H(x,y)(∀x), H(x,y) (∀ x), (67) y y ↦Lb(y), L_b(y), (68) y y ↦L(y). L(y). (69) Then for any initial condition Y1Y_1, it holds that limn→∞αn∑i=1n(g(Yi)−y∼dy[g(y)])=0a.s. _n→∞ _n _i=1^n (g(Y_i)-E_y d_y[g(y)] )=0 .s. (70) Lemma A.7. Let Assumptions A.1 - A.6 hold. Then the iterates xn x_n generated by (19) converge almost surely to a (sample-path-dependent) bounded invariant set of the ODE dx(t)dt=h(x(t)). x(t)t=h(x(t)). (71) Appendix B Derivation of n-step Differential TD We begin with the Bellman equation for differential TD in matrix-vector form (3). Recall that Pπ∈[0,1]||×||P_π∈[0,1]^|S|×|S| denotes the stochastic matrix of the Markov chain induced by the target policy π, rπ∈ℝ||r_π ^|S| represents the expected rewards under π, and J¯π J_π is the average reward. The one-step Bellman equation of vπv_π is vπ=rπ−J¯πe+Pπvπ. v_π=r_π- Jπ e+P_πv_π. (72) We can keep unrolling it for n steps and get vπ v_π =rπ−J¯πe+Pπ(rπ−J¯πe+Pπvπ) =r_π- J_πe+P_π (r_π- J_πe+P_πv_π) (73) =rπ−2J¯πe+Pπrπ+Pπ2vπ =r_π-2 J_πe+P_πr_π+P_π^2v_π (74) ⋮ (75) =−nJ¯πe+rπ+Pπrπ+Pπ2rπ+⋯+Pπn−1rπ+Pπnvπ =-n J_πe+r_π+P_πr_π+P_π^2r_π+·s+P_π^n-1r_π+P_π^nv_π (76) Hence, by (76), we have for all s∈s , vπ(s)= v_π(s)= [∑i=0n−1(r(Si,Ai)−J¯π)+vπ(Sn)|S0=s,Ai∼π(⋅∣Si),Si+1∼p(⋅∣Si,Ai)] [ _i=0^n-1 (r(S_i,A_i)- J_π)+v_π(S_n) |S_0=s,A_i π(· S_i),S_i+1 p(· S_i,A_i)] (77) = = vπ(s)+[∑i=0n−1(r(Si,Ai)−J¯π)+vπ(Sn)−vπ(S0)|S0=s,Ai∼π(⋅∣Si),Si+1∼p(⋅∣Si,Ai)] v_π(s)+E [ _i=0^n-1 (r(S_i,A_i)- J_π)+v_π(S_n)-v_π(S_0) |S_0=s,A_i π(· S_i),S_i+1 p(· S_i,A_i)] (78) = = vπ(s)+[ρ0:n−1(∑i=0n−1(r(Si,Ai)−J¯π)+vπ(Sn)−vπ(S0))|S0=s,Ai∼μ(⋅∣Si),Si+1∼p(⋅∣Si,Ai)]. v_π(s)+E [ _0:n-1 ( _i=0^n-1 (r(S_i,A_i)- J_π)+v_π(S_n)-v_π(S_0)) |S_0=s,A_i μ(· S_i),S_i+1 p(· S_i,A_i)]. (79) Therefore, we have the n-step bootstrapped differential TD update vt+n(St)=vt+n−1(St)+αt+n−1ρt:t+n−1(Rt+1:t+n−nJt+n−1+vt+n−1(St+n)−vt+n−1(St)) v_t+n(S_t)=v_t+n-1(S_t)+ _t+n-1 _t:t+n-1 (R_t+1:t+n-nJ_t+n-1+v_t+n-1(S_t+n)-v_t+n-1(S_t)) (80) where JtJ_t is the average reward estimate to be defined shortly. Let dμ∈[0,1]||d_μ∈[0,1]^|S| denote the stationary distribution induced by the behavior policy μ. Rearranging (76), we get nJ¯πe n J_πe =rπ+Pπrπ+Pπ2rπ+⋯+Pπn−1rπ+Pπnvπ−vπ =r_π+P_πr_π+P_π^2r_π+·s+P_π^n-1r_π+P_π^nv_π-v_π (81) J¯πe J_πe =1n(rπ+Pπrπ+Pπ2rπ+⋯+Pπn−1rπ+Pπnvπ−vπ) = 1n (r_π+P_πr_π+P_π^2r_π+·s+P_π^n-1r_π+P_π^nv_π-v_π ) (82) dμ⊤J¯πe d_μ J_πe =dμ⊤n(rπ+Pπrπ+⋯+Pπn−1rπ+Pπnvπ−vπ) = d_μ n (r_π+P_πr_π+·s+P_π^n-1r_π+P_π^nv_π-v_π ) (83) J¯π J_π =dμ⊤n(rπ+Pπrπ+⋯+Pπn−1rπ+Pπnvπ−vπ) = d_μ n (r_π+P_πr_π+·s+P_π^n-1r_π+P_π^nv_π-v_π ) (84) Therefore, by (84), we have J¯π= J_π= 1n[∑i=0n−1r(Si,Ai)+vπ(Sn)−vπ(S0)|S0∼dπ,Ai∼π(⋅∣Si),Si+1∼p(⋅∣Si,Ai)] 1nE [ _i=0^n-1r(S_i,A_i)+v_π(S_n)-v_π(S_0) |S_0 d_π,A_i π(· S_i),S_i+1 p(· S_i,A_i)] (85) = = J¯π+1n[∑i=0n−1(r(Si,Ai)−J¯π)+vπ(Sn)−vπ(S0)|S0∼dπ,Ai∼π(⋅∣Si),Si+1∼p(⋅∣Si,Ai)] J_π+ 1nE [ _i=0^n-1 (r(S_i,A_i)- J_π)+v_π(S_n)-v_π(S_0) |S_0 d_π,A_i π(· S_i),S_i+1 p(· S_i,A_i)] (86) = = J¯π+1n[ρ0:n−1(∑i=0n−1(r(Si,Ai)−J¯π)+vπ(Sn)−vπ(S0))|S0∼dμ,Ai∼μ(⋅∣Si),Si+1∼p(⋅∣Si,Ai)]. J_π+ 1nE [ _0:n-1 ( _i=0^n-1 (r(S_i,A_i)- J_π)+v_π(S_n)-v_π(S_0)) |S_0 d_μ,A_i μ(· S_i),S_i+1 p(· S_i,A_i)]. (87) As a result, we update the average reward estimate as Jt+n=Jt+n−1+ηnαt+n−1ρt:t+n−1(Rt+1:t+n−nJt+n−1+vt+n−1(St+n)−vt+n−1(St)), J_t+n=J_t+n-1+ ηn _t+n-1 _t:t+n-1 (R_t+1:t+n-nJ_t+n-1+v_t+n-1(S_t+n)-v_t+n-1(S_t)), (88) where η is a positive multiplicative constant to allow for a different update rate relative to v. Appendix C Technical Lemmas Lemma C.1. The function H(v,y)H(v,y) defined in (18) satisfies Assumption A.3. Proof. Recall that for a scalar c>0c>0, the scaled operator is defined as Hc(x,y)≐1cH(cx,y)H_c(x,y) 1cH(cx,y). Substituting the definition of H from (18), we obtain Hc(v,y)[s]=ρ0:n−1(y)(1c∑k=0n−1r(sk,ak)−η∑v+v(sn)−v(s0))s=s0. H_c(v,y)[s]= _0:n-1(y) ( 1c _k=0^n-1r(s_k,a_k)-ηΣ v+v(s_n)-v(s_0))I s=s_0. (89) This implies that the limit of the operator H∞(v,y)=limc→∞Hc(v,y)H_∞(v,y)= _c→∞H_c(v,y) is given by H∞(v,y)[s]≐ρ0:n−1(y)(−η∑v+v(sn)−v(s0))s=s0, H_∞(v,y)[s] _0:n-1(y) (-ηΣ v+v(s_n)-v(s_0))I\s=s_0\, (90) and the difference Hc(v,y)−H∞(v,y)H_c(v,y)-H_∞(v,y) simplifies to Hc(v,y)[s]−H∞(v,y)[s]=ρ0:n−1(y)(1c∑k=0n−1r(sk,ak))s=s0. H_c(v,y)[s]-H_∞(v,y)[s]= _0:n-1(y) ( 1c _k=0^n-1r(s_k,a_k))I\s=s_0\. (91) Therefore, Assumption A.3 (58) is satisfied by setting κ(c)≐1cκ(c) 1c, which vanishes as c→∞c→∞, and defining b(x,y)[s]≐ρ0:n−1(y)(∑k=0n−1r(sk,ak))s=s0. b(x,y)[s] _0:n-1(y) ( _k=0^n-1r(s_k,a_k))I\s=s_0\. (92) Importantly, b(x,y)b(x,y) is independent of x, so for all x,x′,yx,x ,y we have ‖b(x,y)−b(x′,y)‖=0\|b(x,y)-b(x ,y)\|=0. Thus, the Lipschitz condition in (59) from Assumption A.3 is trivially satisfied with Lb(y)=0L_b(y)=0, and the expectation [Lb(y)]E[L_b(y)] is finite. ∎ Lemma C.2. The function H(v,y)H(v,y) defined in (18) satisfies Assumption A.4. Proof. We first verify that H is Lipschitz continuous in the ∞−∞-norm, i.e. (61). Fix any transition y=(s0,a0,s1,…sn)y=(s_0,a_0,s_1,… s_n) and any state s. Using the indicator (s=s0) (I s=s_0), we have H(v)[s]−H(w)[s] H(v)[s]-H(w)[s] =ρ(y)[(∑k=0n−1r(sk,ak)−η∑v+v(sn)−v(s0)) =ρ(y) [ ( _k=0^n-1r (s_k,a_k)-ηΣ v+v(s_n)-v(s_0)) (93) −(∑k=0n−1r(sk,ak)−η∑w+w(sn)−w(s0))]s=s0 - ( _k=0^n-1r (s_k,a_k)-ηΣ w+w(s_n)-w(s_0)) ]I s=s_0 (94) =ρ(y)[−η∑(v−w)+(v(sn)−w(sn))−(v(s0)−w(s0))],s=s0,0,s≠s0. = casesρ(y) [-ηΣ(v-w)+(v(s_n)-w(s_n))-(v(s_0)-w(s_0)) ],&s=s_0,\\ 0,&s≠ s_0. cases (95) Hence |H(v)[s]−H(w)[s]| |H(v)[s]-H(w)[s] | ≤ρ(y)[η||‖v−w‖∞+2‖v−w‖∞],s=s0,‖v−w‖∞,s≠s0. ≤ casesρ(y) [η|S| v-w_∞+2\, v-w_∞ ],&s=s_0,\\ v-w_∞,&s≠ s_0. cases (96) The only remaining task is to upper-bound ρ(y)ρ(y) defined in (18). Under our standard “coverage” assumption (Assumption 4.1), whenever π(a|s)>0π(a|s)>0, we also have μ(a|s)>0μ(a|s)>0, and because both |||S| and |||A| are finite, there is a uniform lower bound μmin _ =mins,a:π(a∣s)>0μ(a∣s)>0. = _s,a:\,π(a s)>0μ(a s)>0. (97) This implies that ρ(y)=∏k=0n−1π(ak∣sk)μ(ak∣sk)≤(1μmin)n≐ρ¯<∞. ρ(y)= _k=0^n-1 π(a_k s_k)μ(a_k s_k)≤ ( 1 _ )^n ρ<∞. (98) Therefore, ‖H(v,y)−H(w,y)‖∞ H(v,y)-H(w,y)_∞ =maxs∈|H(v,y)[s]−H(w,y)[s]| = _s H(v,y)[s]-H(w,y)[s] (99) ≤L‖v−w‖∞, ≤ L v-w_∞, (100) where L≐max1,ρ¯(η||+2).L 1, ρ (η|S|+2). Verifying the Lipschitz continuity of H∞H_∞, starting from (90) from the proof of Lemma C.1 to avoid repetition, we have, H∞(v)[s]−H∞(w)[s] H_∞(v)[s]-H_∞(w)[s] =ρ(y)[(−η∑v+v(sn)−v(s0))−(−η∑w+w(sn)−w(s0))]s=s0 =ρ(y) [ (-ηΣ v+v(s_n)-v(s_0))- (-ηΣ w+w(s_n)-w(s_0)) ]I s=s_0 (101) =ρ(y)[−η∑(v−w)+(v(sn)−w(sn))−(v(s0)−w(s0))],s=s0,0,s≠s0. = casesρ(y) [-ηΣ(v-w)+(v(s_n)-w(s_n))-(v(s_0)-w(s_0)) ],&s=s_0,\\ 0,&s≠ s_0. cases (102) =H(v)[s]−H(w)[s] =H(v)[s]-H(w)[s] (103) Therefore, the Lipschitz continuity of H∞H_∞ holds for L as well, proving (62) holds. From equation (30), its easy to see that h is finite, verifying (63). To verify (64), its also easy to see that y∼d[H∞(v,y)[s]] _y d_Y\! [H_∞(v,y)[s] ] =μ[ρ0:n−1(y)(−η∑pv(p)+v(sn)−v(s0))Is=s0] =E_μ\! [ _0:n-1(y)\, (-η\! _pv(p)+v(s_n)-v(s_0) ) I\s=s_0\ ] (104) =dμ(s)π[−ηe⊤v+v(sn)−v(s)|s0=s] =d_μ(s)\,E_π\! [-η\,e^\! v+v(s_n)-v(s)\; |\;s_0=s ] (105) =dμ(s)[−ηe⊤v+(Pπnv)(s)−v(s)] =d_μ(s) [-η\,e^\! v+(P_π^\,nv)(s)-v(s) ] (106) =[Dμ(Pπn−I−ηee⊤)v](s). = [D_μ (P_π^\,n-I-η\,e^\! )v ](s). (107) In vector form, y∼d[H∞(v,y)]=Dμ(Pπn−I−ηee⊤)v, _y d_Y [H_∞(v,y) ]=D_μ (P_π^\,n-I-η\,e^\! )v, (108) which is clearly finite. Finally, since the Lipschitz constant L is independent of y, (65) holds trivially. ∎ Appendix D Experimental Details and Additional Results D.1 Experimental Details Our experiments were carried out in a simple, continuing gridworld. At each timestep t the agent occupies one cell in an 5×55× 5 grid, can move to any of the four orthogonal neighbors (subject to walls at the borders where an illegal move keeps the agent in the same state), and receives a unit reward each time it reaches the designated “goal” state in the bottom right corner. Rather than terminating, after reaching the goal state, the agent is put back to the start corner (top left) on the very next step with probability 1, making this a continuing task. We evaluated an off-policy, multi-step differential TD learner for a fixed ϵε-greedy target policy with ϵ=0.1ε=0.1. The behavior policy is random. The value function and reward estimate were both initialized to zero. Throughout training, the agent took actions following the random behavior policy, observed the deterministic next state and reward, and performed its n-step TD updates with Off-Policy Differential TD to estimate the value function associated with the target policy. The experiment was run for 100,000100,000 steps, and repeated with 30 random seeds. For Figure 1, the η values were reported for η=0.1,0.5,1,2η= 0.1,0.5,1,2, while keeping n=3n=3. In Figure 2, η=0.1η=0.1 and n=1,2,3,4n= 1,2,3,4. In both experiments, we used a constant learning rate α=0.01α=0.01. We now elaborate on the evaluation metric. The convergence was assessed using a variant of root-mean-squared value error from (tsitsiklis1999average) which we denote as ‘RMSVE (TVR)’, which is also used in (wan2020learning). As noted in Section 2, the solutions to the differential Bellman equation (3) form a set ∗=vπ+ceV_*= v_π+ce. Which point in this set an algorithm converges to depends on initializations and the design choices of the algorithm. Therefore, computing the value error with respect to vπv_π does not say much about convergence. To remedy this, (tsitsiklis1999average) proposed computing the error with respect to the nearest valid solution to the Bellman equations. The metric is defined as RMSVE(TVR)(v,vπ)≐infc‖v−(vπ+ce)‖dπ. (TVR)(v,v_π) _c v-(v_π+ce)_d_π. (109) Algorithmically, this amounts to computing the offset of the learned value function, subtracting it, and then computing the RMSVE with respect to vπv_π. As demonstrated in Section C.4 of wan2020learning this vπv_π can be analytically computed using the Bellman equations with the additional constraint that dπ⊤vπ=0d_π v_π=0 (effectively centering the value function). D.2 Additional Experiment on the effect of n Here, we present additional experiments, demonstrating that the conclusions from Section 5 also hold for various n values. Despite the fact that η0=0 _0=0, we empirically observe the convergence of differential TD with η=0.1η=0.1 under several choices of n. In this experiment, we used the environment described in Section D.1. Figure 2: Off‐policy convergence of n–step differential TD in a 5×55× 5 gridworld for various n with fixed η=0.1η=0.1. See Section D.1 for the complete experiment description. Despite η0=0 _0=0, we still observe the convergence of differential TD with across several n values.