Almost Sure Convergence of Average Reward Temporal Difference Learning
reinforcement learning;temporal difference learning;average reward
We appreciate the time and effort that the reviewer put in handling this submission and feel deeply privileged to have such a responsive reviewer. But we have to point out that the $A$ matrix constructed in the reviewer latest comment might be incorrect. To see this, we recall that to use the results in Tsitsiklis & Roy (1999), we have to compute the expected updates of $u_t$, i.e., to find the $A$ matrix such that 
$$u_{t+1} = u_t + \alpha_{t+1} A u_t.$$
Here again we assume all rewards are 0 to simplify notations. It is our understanding that $u_t \in \mathbb{R}^{|S|}$. So for the update to make sense, the $A$ matrix has to be $|S|$ by $|S|$. But the $A$ matrix constructed by the reviewer is $|S| - 1$ by $|S| - 1$. So from a sanity check of the dimension, we believe the $A$ matrix constructed by the reviewer is wrong, unless we misunderstood the proposed algorithm by the reviewer. 

On the other hand, the $A$ matrix we constructed is $D(P - I)$. To convince the reviewer and to demonstrate that we have put due diligence into this, we attach a python script below that numerically verifies the correctness of our $A$. This script is self-contained and only needs numpy to run. A sample output is 
```
[[ 9.57424790e-05]
 [ 3.01789201e-04]
 [-3.97337865e-04]]
```

```
import numpy as np

def prob_measure(n, temp=1.0):
    logits = np.random.rand(n) / temp
    exp_logits = np.exp(logits)
    prob = exp_logits / np.sum(exp_logits)
    return prob

def stochastic_matrix(n, temp=0.5):
    m = np.array([prob_measure(n, temp) for _ in range(n)])
    return m

# Generate a stochastic matrix and compute its stationary distribution
# Each row of d is the stationary distribution
def P_and_d(n, temp, eps):
    P = stochastic_matrix(n, temp=temp)
    d = P
    while True:
        next_d = d @ P
        if np.mean(np.abs(d - next_d)) < eps:
            break
        d = next_d
    return P, d

def test_A():
    n = 3
    all_states = np.arange(n)
    P, d = P_and_d(n, temp=1, eps=1e-5)
    d = d[0]

    # randomly generate u_t
    u = np.random.rand(n, 1)

    simulated_delta_u = np.zeros_like(u)
    trials = 100000
    for i in np.arange(trials):
        s = np.random.choice(all_states, p=d)
        next_s = np.random.choice(all_states, p=P[s, :])
        td_error = u[next_s, 0] - u[s, 0]
        simulated_delta_u += -1.0 / n * td_error 
        simulated_delta_u[s, 0] += td_error
    simulated_delta_u = simulated_delta_u / trials
    true_delta_u = np.diag(d) @ (P - np.eye(n)) @ u
    print(simulated_delta_u - true_delta_u)

if __name__ == '__main__':
    test_A()
```
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 thanks the reviewer again for clarifying how to use Tsitsiklis & Roy (1999). The point we want to make is that, the ${u_t}$ updates rule the reviewer suggests doesn't seem to be related to the matrix $\Phi^\top D (P_\pi - I)\Phi$. Instead, according to our analysis in the previous reply, it is only related to the $A$ matrix (defined in the previous reply). But this $A$ matrix is not Hurwitz and does not satisfy the assumptions in Tsitsiklis & Roy (1999). 

The $u_t$ update is essentially the standard tabular average reward TD update plus some shift. So as described in our previous analysis, it's expected updates would be the summation between the expected updates of the standard TD, $D(P - I)u_t$, and the shift, $e^\top D(P - I) u_t e / |S|$. We cannot see how the $\Phi$ matrix would appear here.
Regarding the convergence of $u_t$, I am specifically referring to the authors' statements in lines 198-201:  "Konda & Tsitsiklis (1999) further assume that for any $c \in\mathbb{R}$, $w\in\mathbb{R}^d$, it holds that $\Phi w\neq ce$. Under this assumption, Tsitsiklis & Roy (1999) prove that $\Phi^{\top}D(P_{\pi} − I)\Phi$ is negative definite (Wu et al. (2020) assume this negative definiteness directly) and the iterates {wt} converges almost sure".

An alternative approach would be to prove that $\Phi D(P_{\pi}-I)\Phi^{\top}$ is Hurwitz, for $\Phi$ describing the algorithm for $u$. Then the desired results are obtained using the ODE method.

If the authors remain unconvinced, note that if Theorem 2 holds, then $u_t$ converges almost surely to a deterministic limit (which is the projection of $v_{\pi}$ onto the space with zero sum). Consequently, it is evident that proving almost sure convergence of a process to a deterministic limit is simpler than proving convergence that is sample-path-dependent.

Although I have not performed a complete analysis, I believe that the perspective I am suggesting may allow for relaxed assumptions, particularly Assumption 4.4 on the learning rate and Assumption 4.5 on noise, which seem overly restrictive.

Regarding the last paragraph in the authors' recent response, I agree with the form of the fixed point $v(\omega) = v_{\pi} + c(\omega)$. My point is that, with the perspective I propose, we have $c(\omega) = c_{\pi} + \lim_{t\to\infty} c_t(\omega)$, which is more precise since $c_t(\omega)$ can be computed during the algorithm.
We thanks the reviewer for the detailed reply but we still failed to get why the proposed $u_t$ will converge. To simplify notations, let's say the reward is always 0. 
If we want to invoke Tsitsiklis & Roy (1999), we need to compute the expected updates of $u_t$. First, the expectation of $\delta_{t+1}$ given $u_t$ would be $e^\top D(P - I) u_t$, where $e$ is an all one vector. Then the expected updates of $u_t$ can be expressed as
$$u_{t+1} = u_t + \alpha_{t+1} (D(P - I) u_t - (e^\top D(P - I) u_t)e / |S| )$$
If we multiply by $e^\top$ on both sides of the above update, it can be seen that $e^\top u_{t+1} = e^\top u_t$.
Given this update, we would need to study the matrix $A = (I - e e^\top /|S|) D(P - I)$. But actually, we have $e^\top D(P - I) = 0$. So this $A$ is really just $D(P - I)$, which is the same as the expected updates of our tabular TD. As a result, the results in Tsitsiklis & Roy (1999) do not apply. We would appreciate if the reviewer can point out if there is any mistake in our derivation and give more hints on the convergence of $u_t$.

We also want to clarify that our Theorem 2 says that for each sample path $\omega$, there exists some fixed point $v(\omega) = v_\pi + c(\omega) e$ such that $v_t(\omega) \to v(\omega)$. Notably, this $c(\omega)$ does not depend on $t$. This is what we mean by sample path dependent fixed point -- it only depends on the sample path but not $t$. We will make more explicit in revision. In the reviewer's result, it seems to have a time dependent $c_t(\omega)$.
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:
$$
J_{t+1}=J_t+\beta_{t+1}(R_{t+1}-J_t),
$$
$$
u_{t+1}(S_t) =u_t(S_t) + \alpha_{t+1}(1-1/|S|) \delta_{t+1},
$$
$$
u_{t+1}(s) = u_t(s) - \alpha_{t+1}\delta_{t+1}/|S| \text{ for } s\neq S_t,
$$
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
$$
c_{t+1} = c_t + \alpha_{t+1}TD_{t+1}/|S|.
$$
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.
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.
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.
Yes
No ethics review needed.
Why is the asymptotic analysis for only the tabular case important? Prior results exist for applications with linear function approximations which capture almost all applications of interest. And prior literature also provides finite time bounds (although in the L2 norm sense) which are of more significance in terms of determining sample complexities, etc. The motivation for this work is not compelling in its current form.
It is theoretically interesting to examine the almost sure convergence of fixed policy evaluation in tabular settings without relying on value function projection to achieve the contraction needed for analysis.
The authors present an almost sure convergence analysis for finite state-action spaces, infinite horizon average reward in the tabular setting (that is without linear function approximation for the relative value function). There are many prior works in this regime, but the ones which are the most relevant are: (i) Tsitsiklis and Van Roy 1999 and (ii) Zhang et al 2021. The problem formulation addresses data sets obtained through Markovian sampling, with additive noises.
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 (a mild assumption which doesn't hinder the applicability of their approach in many problems). They provided an asymptotic convergence analysis for this TD learning algorithm. 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.
(ii) Zhang et al 2021 considered the Tsitsiklis and Van Roy 1999 approach and relaxed the assumption by including a projection step, where the value function vectors are projected onto a subspace where an unique representation for them exists (generally the average reward value functions aren't unique vectors and are unique only upto an additive constant, and this projection eliminates this non uniqueness). 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.  

Given all these limitations, I feel the work lacks sufficient contribution.
Yes
No ethics review needed.
1. 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?

[1] Sutton, Richard S. "Reinforcement learning: An introduction." A Bradford Book (2018).

2. 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?

3.  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.

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

5. 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?
* A long standing a.s. convergence of TD in average reward setting is investigated and convergence result is confirmed.

* A general a.s. general a.s. convergence for stochastic system with Markovian noise and additive noise is established, which might be of an independent interest.

* Discussions on existing approaches are helpful and provide clarity.
The paper studied the convergence temporal difference(TD) algorithm in average reward setting and tabular case. What differs the work from many existing literature is the focus on almost sure (a.s.) convergence. Discussions on limitations of existing approaches on a.s. is provided with clarity. A general a.s. convergence for stochastic system with Markovian noise and additive noise is established, as a result of which TD algorithm in average reward setting is established.
* 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 $\mathcal{V}_{*}$, which is an unbounded set.