Almost Sure Convergence of Average Reward Temporal Difference Learning

Weaknesses: 1. My major concern is that as the authors mentioned, the additive noise assumption in Assumption 4.5 is quite strong assumption. For example, in bounding, the additive noise assumption plays a key role. At least in the context of RL, this assumption seems to be not a mild assumption, and not commonly use used, as opposed to the argument in the abstract by the authors. With this assumption, I believe many open problems in RL can be solved.

To clarify, while Assumption 4.5 concerning $\epsilon_1$ might appear to be a strong assumption in isolation, we already allow for Markovian noise $Y_t$ in our analysis, without imposing any assumptions on its structure. This represents a significant advancement, as existing works do not address the case of non-expansive mappings with Markovian noise. The additive noise $\epsilon_1$ is introduced only to establish a specific proof for average reward TD, and in many practical applications, $\epsilon_1 = 0$ while still accommodating the much less restrictive Markovian noise, which is weaker than i.i.d. or Martingale noise. Therefore, the assumption does not limit the applicability of our framework.

Furthermore, Theorem 2, which applies the stochastic approximation result to average reward TD, does not rely on any assumptions regarding $\epsilon_1$. Instead, it builds solely on Assumption 5.1 concerning the egodicity of the Markov Chain, which together with the update rule for average reward TD ensures the conditions of Assumptions 4.1–4.5 are met.

2. The analysis of stochastic approximation with Markovian noise has been well-studied in the literature, in particular using the Poisson equation. Therefore, it is questionable, what is the difficulty of applying such technique to the analysis of SKM.

We argue that stochastic approximation with Markovian noise for non-expansive mappings has received limited attention in the literature. Most works on stochastic approximation, including those by Kushner and Yin or Borkar, do not address this specific setting. If the reviewer is aware of existing works that study stochastic approximation with non-expansive mappings and Markovian noise, we would welcome specific references.

Additionally, while stochastic approximation techniques using the Poisson decomposition are well-established, our analysis required bounding the novel terms $\bar{\epsilon_n}^(j)$ and $\bar{\bar{\epsilon_n}}^(j)$ for $j = \{1, 2, 3\}$ to ensure the almost sure stability of our iterates. This task was highly non-trivial and represents a critical component of our proof. We elaborate on the novelty of our approach and its relationship to prior work utilizing Poisson decomposition in stochastic approximation in the second paragraph of the Related Work section.

Finally, while the technique itself may appear straightforward to some, the novelty and utility of our result are independent of the perceived difficulty of the analysis. Importantly, this result enables us to provide the first proof of almost sure convergence for the most prominent algorithm in average reward MDPs after 25 years.

Questions:

$e$ in equation (1) has not been defined previously.

We explicitly defined $e$ in lines 51-52 as the all-one column vector.

Before addressing the authors' questions, I would like to clarify my previous comment by providing additional details.

First, recall that equation (1) admits a unique solution up to an additive constant, meaning that the set in (2) is one-dimensional. Consequently, finding a solution to (1) is an underdetermined problem. However, by adding a constraint to fix the additive constant, the problem becomes well-posed. The standard condition used in the optimal control community (where this problem is often called "ergodic") is to fix $\sum_{i}v_{\pi}(i)=0$.

To ensure this condition holds, we can adjust the algorithm in (Average Reward TD) as follows:

where $\delta_{t+1} = (R_{t+1}-J_t+u_t(S_{t+1})-u_t(S_t))$. My point is that $u$ matches the original process $v$ proposed by the authors in (Average Reward TD) up to an additive constant, i.e., $v_t = u_t + c_te$ where $c_t$ is a real number. The values of $c_t$ can be computed as

Therefore, one can easily pass from $u$ to $v$ and vice versa.

In my previous comment, I made two key points:

1. On the one hand, $u$ is defined by a linear stochastic algorithm, as described in the section "Hardness with linear function approximation," and it satisfies the conditions under which Tsitsiklis & Roy (1999) proved almost sure convergence. Therefore, $u$ converges almost surely to some $u_{\pi}$. Furthermore, it is straightforward to verify that $u_{\pi}$ is a solution to (1).
2. On the other hand, the authors claim that $v$ converges to a sample-path-dependent fixed point. I believe they do not adequately define what is meant by a "sample-path-dependent fixed point". I contend that a more precise statement is that $v$ converges up to an additive constant to $u_{\pi}$, with this additive constant, namely $c_t$ as defined above, not converging to any deterministic limit. In other words, the sample-path dependence described by the authors is fully characterized by $u_{\pi}$ and $(c_{t}(\omega))_{t\geq0}$ for almost all $\omega \in \Omega$ (where $\Omega$ represents the ambient probability space).

To summarize, I assert that this perspective simplifies both the problem and the proofs, providing a more precise characterization of the asymptotic behavior of $v$. This is why I believe the contributions of this paper are insufficient for publication in ICLR.

Now, I will briefly respond to the authors' questions:

1. Q:' Does the reviewer mean that given this linear TD algorithm, there is no need to use the tabular TD we studied at all, or the convergence of this linear TD implies the convergence our tabular TD?' R: I assert that the two are equivalent since $v_t = u_t + c_te$, implying that studying the asymptotic behavior of one provides the asymptotic behavior of the other.
2. Q: 'Does it mean $\Phi$ is obtained by shifting ("additive constant") our feature $I$ by $1/|S|$?' R: The algorithm I propose involves a simple projection step onto the set of vectors $u$ satisfying $\sum_{i}u(i)=0$ after each step of (Average Reward TD). Thus, dim(Im$(\Phi))=|S|-1$, and $\Phi$ should be defined as I proposed (while the precise form of $\Phi$ may differ, it should have the same general structure; I leave the details to the authors).
3. Regarding the last paragraph in the latter authors' response : I agree that $v_{\pi}$ (defined in line 65) does not satisfy $\sum_iv_{\pi}(i)=0$ in general. Nonetheless, we have that $v_{\pi}=u_{\pi}+c_{\pi}e$ for some constant $c_{\pi}$. I acknowledge that I did not address the determination of the constant $c_{\pi}$, nor did the authors with their method. Since both algorithms rely solely on the Bellman equation (1), neither can capture $c_{\pi}$. However, I do not consider this an issue, as knowledge of $v_{\pi}$ up to an additive constant is sufficient and well-established in the optimal control community.

Thanks for your comments. Before we proceed to a response, could you clarify what $\Phi(i, i)$ is in your construction? It seems sth is missing now.

We thank the reviewer for clarification. We want to confirm with the reviewer if our understanding of the implication of this construction is correct so we can provide an effective response.

For this new feature matrix, it has the property that $e^\top \Phi w = 0$ for any $w$ where $e$ is an all one vector. Let $v(i) = \Phi(i, :) w$ be the state value approximation for $i$ using $w$ under this feature matrix. Then this construction ensures that $\sum_i v(i) = 0$. Let's assume for now the true value function satisfies $\sum_i v_\pi(i) = 0$. Then by running linear TD with this feature, we are able to converge to the true value function. In other words, linear TD with this feature matrix is a practical algorithm to find the true value function and can achieve the same goal as the tabular TD we studied. Does the reviewer mean that given this linear TD algorithm, there is no need to use the tabular TD we studied at all, or the convergence of this linear TD implies the convergence our tabular TD? If it is the latter case, we would appreciate if the reviewer could give more hints on how the equivalence can be established. In particular, we failed to understand what "constant with respect to the state" mean. Does it mean $\Phi$ is obtained by shifting ("additive constant") our feature $I$ by $1/|S|$? But the last column is dropped after this shifting so we failed to see the equivalence.

We also note that for average reward MDP, we only have $\sum_i d(i) v_\pi(i) = 0$ where $d$ is the stationary distribution and $\sum_i v_\pi(i) = 0$ is not necessarily true. Let $D$ be a diagonal matrix with the diagonal being $d$. Following the reviewer's idea, we might need to consider a feature matrix $\Phi' = D^{-1} \Phi$ so that we have $d^\top \Phi' w = 0$. But the linear TD with $\Phi'$ is not a practical algorithm because $D$ is unknown. Furthermore, it is again not clear how the convergence of linear TD with $\Phi'$ would imply the convergence of our tabular TD and we would appreciate more hints. Now it is not shifting. Instead, it is (1) shifting (2) dropping the last column and (3) rescaling. So we failed to see the equivalence.

I believe the authors have misunderstood that $u_t$ is not itself the parameterization but rather the parametrized projected value function. Therefore, they need to introduce a separate parameterization, say $\theta \in \mathbb{R}^{|S|-1}$, such that $u = \Phi \theta$ resides in $E$, the $(|S|-1)$-dimensional subspace of $\mathbb{R}^{|S|}$ that I defined in my previous responses.

Once again, I strongly advise the authors to take a few days to perform the calculations themselves, as it is increasingly evident that they do not fully grasp the main related works relevant to their submission.

The changes I propose are not new nor original to me. They are a straightforward application of the work by Tsitsiklis & Roy (1999), with $\Phi$ chosen appropriately so that we can construct an alternative algorithm with two key properties: 1) it is equivalent to the algorithm proposed in this submission, meaning that one can derive the iterations of one from the other (with the need to track a few additional low-dimensional values, specifically the constant $c_t$ mentioned in my previous comments); 2) it yields a matrix $A=\Phi^{\top}D(P-I)\Phi$ that is negative definite.

The idea is simple: the matrix $D(P-I)$ is not negative definite solely because of $e$, as we have $e^{\top}D(P-I)=0$. However, one can easily verify that this is the only problematic direction. In other words, $x^{\top}D(P-I)x < 0$ for any $x \in E - {0}$, where $E =${ $x \mid \sum_i x_i = 0$}. Since $E$ is a $(|S|-1)$-dimensional vector space, the linear parametrization induced by the desired $\Phi$ should also be $(|S|-1)$-dimensional, making $\Phi$ of dimension $|S| \times (|S| - 1)$. Consequently, $A$ is clearly $(|S| - 1) \times (|S| - 1)$ dimensional, which makes sense, as the goal is to eliminate the single ill-conditioned direction.

After reflecting more on the problem due to the authors’ inquiries, my opinion of their paper has shifted. In short, a straightforward application of existing literature yields the same results as those proved in the paper, but with significantly milder assumptions and much simpler proofs. I therefore believe the contributions of this paper are quite limited and indicate that the authors may lack a strong understanding of the primary literature in the field of their submission. It might be worth reconsidering submission in this domain.

I will not provide further responses, as I have already dedicated considerable time to this review and provided ample guidance in my comments. For a competent researcher, these hints should be sufficient to derive a complete proof, provided they invest the necessary time and effort to work through it carefully.

I disagree with the authors and feel they could have taken more time to attempt solving the issue themselves before asking for further clarification.

The matrix of interest is not the one given in the authors' latest response. It is $A = \Phi^{\top}D(P - I)\Phi$, as I have already indicated. The remaining task is to determine the precise form of $\Phi$, which is not difficult but requires some effort. This is why I preferred to leave this task to the authors. Starting from the algorithm I described, we arrive at a slightly modified $\Phi$ compared to my initial suggestion. Specifically, we find that $\Phi^{\top} = (I_{|S|-1}, -e)\in\mathbb{R}^{(|S|-1)\times|S|}$.

Using the same approach as Tsitsiklis & Roy (1999), we can then demonstrate that $A$ is negative definite. This, together with the ODE method, implies almost sure convergence.

Ultimately, this proof is much more concise and straightforward than the one proposed by the authors, while requiring much weaker assumptions. If the authors still do not understand, I suggest they spend a few days working through the calculations themselves rather than asking me directly, as I am not their supervisor.

We have revised the submission to provide another perspective to demonstrate that the reviewer's approach will not work. Let's assume for now it was somehow proved that $v_t = u_t + c_t e$ for the general stochastic updates with general reward (recall that this is actually not proved). We know that $\theta_t$ converges a.s., so $u_t$ converges a.s. to a fixed point. But our computation suggests that $c_t$ has a form of $c_t = \sum_{i=0}^{t-1} \alpha_i z^\top u_i$ for some fixed vector $z$ (see Appendix D.1 for the exact form of $z$). However, the convergence of $u_i$ does not imply the convergence of $c_t$. To proceed, we at least need the almost sure convergence rate of $u_t$ (this is far from enough). But to our knowledge, there is no almost sure convergence rate of average reward linear TD. If we cannot prove $c_t$ converge to a sample path dependent fixed scalar, we cannot prove that $v_t$ converge to a sample path dependent fixed point following the reviewer's approach. (We do note that our method does prove that $v_t$ converge to a sample path dependent fixed point).

I disagree with the authors. The formulation of the update of $u$ straightforwardly implies the existence of $\Phi$. Still, it is true that none of my two $\Phi$ I proposed in my previous answers were working. Since the authors are still not convinced and other reviewers start doubting, here is a full proof relying essentially on basic linear algebra.

Let us first construct $\Phi$.

Let $J\in\mathbb{R}^{N\times N}$ be the matrix with only ones, i.e., $J_{i,j}=1$ for $1\leq i,j\leq N$. Observe that the matrix $I_N-J / N$ is symmetric and has two eigenvalues: $1$ with multiplicity $N-1$ and $0$ with multiplicity $0$. Therefore there exists $Q\in\mathbb{R}^{N\times N}$ an orthogonal matrix (i.e., $Q^{\top}Q=QQ^{\top}=I_N$) such that $I_N-J/N=Q\hat{D}Q^{\top}$ where $\hat{D}=$diag$(1,1,\dots,1,0)$, i.e., $\hat{D}$ is diagonal with $N-1$ ones and one zero. Define $\Phi\in\mathbb{R}^{N\times(N-1)}$ such that $\Phi_{i,j}=Q_{i,j}$ for $1\leq i\leq N$ and $1\leq j\leq N-1$ (i.e., $\Phi$ is $Q$ without its last column). Observe that:

Moreover, it is straightforward to check that Im$(\Phi)=E:=$Vect$(e)^{\top}$, so $\Phi$ is a one-to-one correspondence from $\mathbb{R}^{N-1}$ to $E$. Take $v_0\in\mathbb{R}^N$ any initial value for the iterative method proposed by the authors. Define $c_0=\frac1N\sum_{i=1}^Nv_i$ so that $v_0-c_0e\in E$, therefore there exists $\theta_0\in\mathbb{R}^{N-1}$ such that $\Phi\theta_0=v_0-c_0e$.

Now, for $t\geq0$, define $\theta_t$ and $c_t$ by induction as

Define $u_t=\Phi \theta_t$ as the approximated value function. A straightforward induction implies that $v_t=u_t+c_te$.

Now it only remains to prove that $A=\Phi^{\top}D(P_{\pi}-I_N)\Phi$ is Hurwitz. It is sufficient to observe that $\Phi w\in E$ is orthogonal to $e$ for any $w\in\mathbb{R}^{N-1}$ and to cite the sentences of the authors line 197-201 : "Nevertheless, to proceed with the theoretical analysis, besides the standard assumption that $\Phi$ has linearly independent columns, Tsitsiklis & Roy (1999); Konda & Tsitsiklis (1999) further assume that for any $c\in\mathbb{R}$, $w\in\mathbb{R}^d$, it holds $\Phi w\neq ce$. Under this assumption, Tsitsiklis & Roy (1999) prove that $\Phi^{\top}D(P_{\pi}-I_N)\Phi$ is negative definite (Wu et al. (2020) assume this negative definiteness directly) and the iterate [{$\theta_t$}] converges almost surely."

Weaknesses: Although an a.s. convergence is characterized, it's not clear as to how the connection of sample path and the resulting fixed point. It would be nice to have further clarification. In the sentence of Line 149-151, the authors argued that existing analysis failed to move beyond convergence to a bounded invariant set. However, the main result in Theorem 2 falls into the same category, as it converges to V^* which is an unbounded set.

We would like to clarify the distinction between converging to a bounded invariant set and converging to a fixed point within that set. If only convergence to an invariant set is established, the value function estimate may oscillate indefinitely among different values within that set. In contrast, our analysis proves that the iterates converge to a specific fixed point within the invariant set.

When we refer to this as a "sample-path dependent fixed-point," we mean that the specific point of convergence within the invariant set depends on the initialization of the value function and the realization of the random Markovian noise process $Y_t$ and cannot be determined a-priori. While the resulting fixed-point may depend on the trajectory, the key contribution of our analysis is proving that the iterates settle to some stable, specific point within the invariant set, rather than merely remaining bounded.

Questions: The value function defined in Line 65 appears slight different from Page 250 value function definition in [1], are they equivalent? If so how to see this?

The definitions of the value function are equivalent. If you look at equation 10.9 we can see how they define the returns $G_t$ in the average reward setting. This is equivalent to our definition on line 65 (except we follow the convention where the average reward is denoted as $\bar{J_\pi}$ instead of $\bar{r}$). Then we can use the standard definition of the value function which is: v(s) = $E_{\pi}[G_t|S_t = s]$ which Sutton gives in the paragraph that follows equation 10.9.

In equation (5), why not just cancel out v(t) with the last term in h(v(t))? Is there some consideration for not doing so?

The reason is purely for notation purposes. If you look at the form of equation 3, we want to write it to match our SKM iteration form in Equation (SKM with Markovian and Additive Noise). Therefore we want to keep the extra $v_t$ outside of $H$, which means it remains outside of $h$, which is the expectation of $H$. Thats why in equation 5 it remains outside and we don't cancel it.

In the sentence of Line 149-151, the authors argued that existing analysis failed to move beyond convergence to a bounded invariant set. Are there any particular references the authors are referring to? If so, please provide them.

Thank you for pointing this out. To clarify, when we state that "existing ODE-based convergence analysis fails to move beyond convergence to a bounded invariant set," we are not implying that there are specific works using the ODE method to prove convergence to a bounded invariant set for average reward TD. Rather, we mean that existing ODE-based analysis methods are limited in that they cannot provide results beyond convergence to a bounded invariant set in this context. We have revised the paper to reflect this more precise wording.

In Line 168, it mentioned that "it cannot be used once function approximation is introduced". Can you elaborate more on this?

Count-based learning rates rely on state visitation counts to dynamically adjust the step size during updates. However, with function approximation, it's usually assumed that we have access to only features, not the state itself. Since the feature is usually not a one-to-one mapping, there is no way to count the state visits.

Maybe a question concerns future effort, where are the potentially challenges lie in analysis in order to achieve a convergence with rate rather asymptotic convergence?

This is an excellent question. Using our results on stochastic Krasnoselskii-Mann iterations with Markovian noise, we were actually able to establish a convergence rate for the expected residuals, $E[\||T v_t - v_t\||_\infty]$, of our iterates where $T$ refers to the differential bellman operator. In the discounted setting, this convergence rate could directly translate to a convergence rate to the optimal value function due to the contraction mapping property of the Bellman operator. However, in the average reward setting, $T$ is only non-expansive in the infinity norm, rather than being a contraction. This prevents us from converting the residual convergence rate into a convergence rate to the optimal value function. We did not include the expected residual convergence result in the paper because it is not a stronger theoretical result than the $L_2$ convergence rate provided in Zhang et al. (2021). Furthermore, our almost sure convergence result demonstrates convergence to a sample-path dependent fixed point, meaning that the iterates converge to a potentially random point in $V^*$. Since the specific point of convergence depends on the random realization of the Markovian noise and the initialization, we could not derive a universal convergence rate that holds across all sample paths.

The amount of literature in this realm is quite significant. My main issue is the limited scope of this work. For instance, the following have been very well studied:
(i) Tsitsiklis and Van Roy 1999 consider policy evaluation using linear value function approximation, where the feature vectors do not span the constant vector ...The authors argue that their assumption does not hold when considering tabular cases and that might be true, but for most applications of interest, the state and action spaces are large enough to necessitate the use of function approximations for value function estimation to ensure practicality. Hence, the importance of this work is not well motivated.

While we agree that function approximation is critical in many practical applications, the tabular setting remains a foundational component of RL. By rigorously addressing this setting, our work not only resolves an open problem but also contributes to a deeper understanding of TD learning, corrects misconceptions in the field, and establishes a solid theoretical basis for future advancements.

1. Clarifying Misconceptions: As demonstrated by our discussion with Reviewer PPQC, there is a prevalent misunderstanding in the research community that convergence results for average reward TD with linear function approximation automatically imply convergence in the tabular case. This is incorrect. A similar error also appears in a recent work Natural Policy Gradient for Average Reward Non-Stationary RL, (submission ID 12405 for ICLR 2025) which also mistakenly made this conclusion, as evidenced in their discussions with reviewers and subsequent revisions. The authors of that work have since acknowledged that almost sure convergence for linear function approximation does not imply convergence in the tabular setting. By explicitly addressing and resolving this gap, our work removes confusion and contributes a rigorous foundation for policy evaluation in the tabular setting.

2. Distinct Theoretical Contributions: From a theoretical standpoint, convergence for linear function approximation does not subsume the tabular case. The tabular setting presents unique challenges that require distinct techniques and insights. For instance, analogous challenges exist in other fields, such as topology: while Poincaré’s conjecture is straightforward in higher dimensions, its proof for $d = 3$ was exceptionally challenging and significant. Similarly, resolving convergence in the tabular case improves our theoretical understanding of temporal difference (TD) learning.

3. Broader Significance of Our Mathematical Results: Beyond addressing convergence for average-reward TD in the tabular setting, our work extends the Stochastic Krasnoselskii-Mann (SKM) iterations to include Markovian noise, providing a general mathematical result that has broader applications for proving the convergence of other RL algorithms.

(ii) Zhang et al 2021 considered the Tsitsiklis and Van Roy 1999 approach and relaxed the assumption ... They later characterize convergence in L2 space instead of asymptotic convergence and provide finite time bounds in terms of expectations of quantity of interest. The authors argue L2 convergence does not imply almost sure convergence which is true and also claim that the iterates converge to a set instead of a unique point. But if every point in this set is a solution, there is no need to obtain a unique solution since the original value function is not unique anyway.

We acknowledge the contributions of Zhang et al. (2021) in extending the Tsitsiklis and Van Roy (1999) framework by introducing a projection step. However, we maintain that L2 convergence does not imply almost sure convergence, and this distinction is crucial both theoretically and practically. To illustrate this, define a sequence of independent random variables ${z_n}$ such that $Pr(z_n = n^\nu) = \frac{1}{n}$ for $\nu < \frac{1}{2}$, and $Pr(z_n = 0) = 1- \frac{1}{n}$. Then we have $E[z_n^2] = n^{2\nu -1}$, so the sequence converges in $L^2$ for $\nu < \frac{1}{2}$. However, we have $\sum_n Pr(z_n = n^\nu) = \infty$. By the second Borel-Cantelli lemma, $z_n$ diverges to $\infty$ almost surely. This example demonstrates that $L^2$ convergence alone does not guarantee the behavior of individual realizations, a critical issue in contexts like continual learning, where a single trial dictates performance. Practically, almost sure convergence is essential for understanding the long-term behavior of learning algorithms, especially in real-world applications where only a handful of trajectories are observed.

While it is true that every point in the set to which the iterates converge is a solution, the lack of of a fixed point is also important. Without almost sure convergence to a specific point within the set, the the value function representation remains unstable which can complicate practical implementations.