Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper focuses on the theoretical analysis (especially on the non-asymptotic sample efficiency) of two algorithms under the average-reward setting: (1) TD($\lambda$) with linear function approximation under Markovian observation noise (2) tabular Q-learning in the synchronous setting.

Previous works have obtained similar finite-sample guarantees under the discounted setting. However, this work focuses on the average-reward setting where the Bellman equation is known to have multiple fixed points. For the TD($\lambda$) analysis, the authors work in a subspace to get the unique solution of the projected Bellman equation. For the Q-Learning case, the Bellman operator is a contraction under the span seminorm.
main_review: The paper provides the first known finite-sample guarantees using both constant and diminishing step sizes of two widely applicable algorithms in RL. 

There are, however, several points that can benefit the manuscript if tended to:

1)  It would be helpful to highlight the substantial differences in a nutshell from the present analysis and from [Zhang et al, 2021].

2) The paper proposed convergence guarantees for the TD learning algorithm and the Q-learning algorithm. However, currently, the sense of how tight the proposed convergence theorem and analysis are reflected in real/practical scenarios is missing.

The paper would greatly benefit from further theoretical/experimental discussions that investigate:

i)How does the change from discounted setting to the average-reward setting affect the terms in the main theorem (compared with [Zhang et al, 2021])?

ii) How does this algorithm converge in practice? In what zone does the theoretical analysis match the practical performance?

Overall, this paper provides insightful and novel theoretical results that broaden our analyzing tools on td learning and Q-learning under the stochastic approximation framework.
limitations_and_societal_impact: The authors addressed that one of the limitations of their work is that it is unclear whether Assumption 4 is necessary for establishing any finite time convergence bound.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper establishes the first finite-sample convergence results for average-reward TD(\lambda) policy evaluation with linear function approximation and average-reward tabular Q-learning in the synchronous setting. 
main_review: Strengths:
1. This work provides novel theoretical results for average-reward MDP with solid technical contributions;
2. The paper is well-written and the ideas are clearly explained.

I have several questions:

1. The current results are: policy evaluation with linear function approximation and tabular control. I wonder why the authors did not further extend to control with linear function approximation. Is there any technical challenge in achieving that?

2. The current convergence is to the best solution in the linear space i.e., \theta^*. I wonder whether the algorithm is robust to model misspecification, i.e., if the value function can not really be linearly represented, how the representation error (\|V-\Phi\theta^*\|) would affect the convergence.

3. In line 81, do you mean LSPE(\lambda) instead of LSTD(\lambda)?



limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the average reward TD-learning and Q-learning. In detail, the authors analyze the TD-$\lambda$ learning with linear function approximation. A finite sample analysis is given for the constant step size and diminishing step size. They also provide a finite-sample analysis of Q-learning in a tabular setting. The main contribution in this paper is how to deal with the constant shift in Bellman equality. In detail, in the TD-learning part, their analysis does not need to assume the uniqueness of the limit point of TD-$\lambda$. In the Q-learning part, they build the contraction based on the distance between two function classes to consider the constant shift.
main_review: This paper is well organized and written. It provides a solid theoretical tool to analyze the constant shift in the value function. However, for the TD-learning part, the proof technique is similar to [1]. The result, including the constant step size and the diminishing step size, is also similar to [1]. Therefore, the contribution of this paper is somehow limited, and the result cannot be considered groundbreaking.

Another drawback in the Q-learning part is the proposed algorithm needs a generative model which allows simulating the trajectory for $J$ step given arbitrary initial state and action $(s, a)$. This will make the algorithm impractical, comparing to an algorithm receiving the initial state from an unknown distribution.

I tend to suggest marginally reject this paper due to the limitation of contribution. I'd like to change my adjust my rating after discussion.

[1] Bhandari, Jalaj, Daniel Russo, and Raghav Singal. "A finite time analysis of temporal difference learning with linear function approximation." Conference on learning theory. PMLR, 2018.
limitations_and_societal_impact: There's no negative societal impact in this paper.

Suggestions:

The paper is overall easy to follow.  In Corollary 1, I'll suggest the authors restate that the learning rate is set as the case (b) in Theorem 1. It confused me at first because it is not well-clarified. 

Furthermore, there's a series of works [2, 3] also providing finite-time analysis in the average reward setting using Actor-Critic with linear function approximation. However, all these works require the unique limit point of TD. Therefore, it would be interesting if the authors can comment about how the proposed method in this paper can be extended to these works to remove such uniqueness assumption. These comments will help readers understanding the contribution of this paper better.

[2] Qiu, Shuang, et al. "On Finite-Time Convergence of Actor-Critic Algorithm." IEEE Journal on Selected Areas in Information Theory 2.2 (2021): 652-664.

[3] Wu, Yue, et al. "A finite time analysis of two time-scale actor critic methods." Advances in Neural Information Processing Systems, 2020.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper focuses on the infinite-horizon average-reward setting and develops the non-asymptotic upper bound for TD($\lambda$) with linear function approximation and tabular Q-learning. Its upper bounds match the best-known results on the discounted-reward MDP for $\epsilon$-accuracy. Its technique used to deal with the non-uniqueness of the limit point seems new, and its construction of Lyapunov function from noticing the connection between the span seminorm and the infimal convolution is a non-trivial observation. 
main_review: Thanks for this well-written work with solid theoretical analysis on the infinite-horizon average-reward RL problem. I agree that this paper has its own technical novelty in dealing with the non-uniqueness of limit points. All derived upper bounds nearly match the existing infinite-horizon discounted-reward RL problem. There are several of my concerns regarding this paper:
1.	I am not clear if the average-reward setting is practical in real-life applications since most of the cited applications ([2], [3], and [4]) are from 20 years ago. Is there any more recent work using this setup?
2.	Assumption 3 in Section 4.3 seems unnatural for me. For the traditional discounted-reward setup, there is no such assumption. Does this assumption automatically hold for discounted-reward MDP? 
3.	From Theorem 2, it seems that $\gamma$ is comparable with the discounted factor. However, the dependence on $\gamma$ is worse than the best-known result on discounted-reward Q-learning: In the paper below, the order of $1/(1-\gamma)$ is 4 rather than 5.
Li, Gen, et al. "Is Q-learning minimax optimal? a tight sample complexity analysis." arXiv preprint arXiv:2102.06548 (2021).
Moreover, the analysis of tabular Q-learning is not as complete as TD($\lambda$). In Section 3.3, this paper introduces two learning rate schedules: constant learning rate and decaying learning rate. But for tabular Q-learning, this paper only considers the decaying learning rate. So, I think there are still many works that should be done on the Q-learning section. 

In summary, this paper can be further improved by introducing more recent applications and adding more explanations on the non-standard assumption. Regarding the Q-learning section, I don’t think it is complete enough, as stated above, so I cannot give a clear accept.    
limitations_and_societal_impact: Since this paper is purely theoretical, the limitations and societal impact section are not applicable.
review_title: null

Meta-review: This paper proves the sample complexity of $TD(\lambda)$ learning and Q-learning in the average reward setting. After the author response and reviewer discussion, the paper gathers enough support from the reviewers. Thus, I recommend acceptance. 

Decision: Accept (Poster)