Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper analyzes the stability issues in Q learning and SARSA with epsilon greedy exploration. The authors use Differential Inclusion (DI) theory to analyze the behavior of Q learning and SARSA. The authors use numerical examples to illustrate their theory.
strength_and_weaknesses: Strength:

The stability issue of Q learning and SARSA is very important. The paper uses a novel technique named Differential Inclusion (DI) theory to study this problem. This technique is not very common in the RL community, and I think it's quite interesting to introduce this technique to the community.

Weakness:

1) Although epsilon-greedy is an important method, it is known that this approach is not a very smart exploration method. Therefore, it would be useful to discuss how to extend this framework to other methods.
2) The assumption B4 in page 5 seems to be quite strong. I am not sure how to interpret this assumption.
3) The experiments only use numerical simulations. It would be better to provide empirical evidence in more realistic environments.

clarity,_quality,_novelty_and_reproducibility: I think this paper is overall clearly written. However, I am not an expert in Differential Inclusion (DI) theory, so I am not able to evaluate the correctness of the results.
summary_of_the_review: The technique that this paper introduced is interesting, but since there are several issues in the paper and thus I don't think it qualifies as an ICLR publication.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work tries to explain the asymptotic behaviors of two well-known approximate RL algorithms, Q-learning and SARSA, with $\epsilon$-greedy exploration. The theoretical analysis presented in this work uses Differential Inclusion (DI) theory to analyze value-based RL methods with discontinuous behavior policy changes. Numerical examples have also been used to demonstrate the usage of the proposed theoretical result for explaining the limitation of  Q-learning and SARSA algorithms with linear function approximation and $\epsilon$-greedy exploration. 
strength_and_weaknesses: **Strength**

- The explanation of the asymptotic behavior of two well-known approximate RL algorithms, Q-learning and SARSA, with $\epsilon$-greedy exploration is quite important and constitutes a challenging open problem.
- Differential Inclusion (DI) theory can be used for analyzing value-based RL methods with discontinuous behavior policy changes.
- Numerical examples have been used to demonstrate the usage of the proposed theoretical result.

**Weaknesses**

- The intuition behind the usage of the differential Inclusion (DI) theory should be described in a more precise way.
- The theoretical analysis seems to be more related to the LSTD. Authors should elaborate if the proposed theoretical result can be also applied in the case of the LSTD algorithm.
- The usage of the proposed theorem for verification of the convergence to the optimal Q-function of the tabular versions of Q-learning and SARSA algorithms need to be examined.
clarity,_quality,_novelty_and_reproducibility: As aforementioned, this work examines the origin of the asymptotic behavior of two well-known approximate RL algorithms that constitutes a quite challenging task. For this purpose, authors resort to the  Differential Inclusion (DI) theory. Nevertheless, the intuition behind the usage of the differential Inclusion (DI) theory is not clear. Actually, Eqs. 6 and 7 should be presented in more detail. Apart from that, it seems that the theoretical analysis is more related to the LSTD algorithm. It would be really useful if authors could elaborate if the proposed theoretical result can be also applied in the case of the LSTD algorithm. Another point that should be also discussed by the authors is the usage for explaining the behavior of the tabular versions of Q-learning and SARSA algorithms without any kind of exploration. Finally, it is not clear how the proposed theory can be used in order to overcome or fix the limitations of the approximate Q-learning and SARSA algorithms.

Other questions:

- What do you mean by saying `almost surely` in Theorem 2.1?
summary_of_the_review: The theoretical analysis presented in this paper is novel, but there are some parts of the paper that are not totally clear. The most important question that needs to be answered is how we can use the proposed theory in order to overcome or fix the unexpected of the approximate Q-learning and SARSA algorithms with $\epsilon$-greedy exploration.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes to apply theory of differential inclusion to understand and explain the behavior of epsilon-greedy based value-learning algorithms with function approximation, such as Q-learning and SARSA(0) with epsilon-greedy exploration. The main result (Thm 2.1) characterizes the asymptotic behavior of aforementioned algorithms under a few assumptions.
strength_and_weaknesses: === Strength ===

The paper seems to provide a very interesting toolkit to systematically understand the behavior of value-based learning algorithm under linear FA and with epsilon-greedy exploration, which is a useful abstraction for many commonly implemented RL algorithms. This might pave the way for future investigations into similar topics.

=== Weakness ===

A potential weakness of the paper is that it is not clear what are the implications of the results in the paper and how significant they are. The main theoretical statement Thm 2.1 claims that under certain conditions, parameter iterates of such value-based algos can jitter within a set of solutions. There is little characterization of how the set of solutions relate to each other (e.g., quality of the solutions) and how one can make use of the theoretical characterization in practice.
clarity,_quality,_novelty_and_reproducibility: === Clarity ===

The paper is overall easy to follow, but presentation-wise it can be improved by better motivating the problem to be studied. 

=== Quality ===

The paper seems to have solid theoretical results, though it is not clear to me how significant are the results and how they can be useful.

=== Novelty ===

The paper is relatively novel in that it applies the new perspective of DI to understand the jittering behavior of value-based algorithms.

=== Reproduce ===

It should be straightforward to reproduce results in the paper.
summary_of_the_review: === **Background question** ===

I would like to clarify a few sentences in the intro section of the paper. The authors write

"The expected behavior here would be convergence to the optimal policy..."

Is the behavior expected because the representation matrix Phi contains the optimal Q-function as one of its columns, so that we should expect the linear function approximation to be able to learn the optimal Q-function and therefore optimal policy. In other words, the "expected" here is purely based on realizability of the target Q-function in the function class.

In practice, such convergence behavior is not observed. I wonder intuitively if this can be explained by the fact that though the optimal Q-function can be represented within the class of linear functions, the algorithm itself can take a path that does not lead to the optimal Q-function. This reminds me of certain conclusions in the policy gradient case, where if the function class is not closed under the policy improvement operator, there is no guarantee to convergence even though optimal Q-function is representable. Can the authors comment on the potential connection here? For general audience, it would also be interesting to understand more of the intuitions of the jittering / non-convergence behavior.

[1] Bhandari et al, 2019, Global Optimality Guarantees For Policy Gradient Methods

=== **Textbook instability** ===

I am a bit confused by the use of "textbook instability". What does this instability refer to exactly?

=== **$h$ not Lipschitz continuous***

I find the background under Eqn 1 a bit confusing in wording. If I understand correctly, $h$ is Lipschitz continuous when doing policy evaluation, as the system is linear; when doing control with $\epsilon>0$-greedy, $h$ is generally not Lipschitz continuous. Is this the case? Maybe worth clarifying more here.

=== **Main result** ===

Assumption B4 I think need further explaining. From the background under Eqn 3, $\epsilon>0,\epsilon'=0$ corresponds to Q-learning; $\epsilon'=\epsilon>0$ corresponds to SARSA(0). The $A_a$ matrix is
$$\Phi^T D_a^\epsilon (I-\gamma P_a^{\epsilon'}) \Phi$$
I think it is true that when $\epsilon'=\epsilon$, the above matrix is PD i.e., $x^T A_a x>0$ for any vector $x$, because essentially $D_a^\epsilon$ and $P_a^{\epsilon'}$ are diagonal matrix and one-step transition matrix of the same $\epsilon$-greedy policy. 

However, it is not immediately clear to me why in the Q-learning case $\epsilon'=0,\epsilon>0$ the $A_a$ matrix is also PD. If B4 is assumed true, it seems to be a very big assumption? I wonder having assumption B4 in place would be in conflict with much of the prior literature in analyzing Q-learning with FA, where it seems that obtaining theoretically justified convergence would need to impose stringent assumption on the data process, such as near on-policy [1].

[1] Melo et al, 2008, An Analysis of Reinforcement Learning with Function Approximation

=== **Presentation** ===

Presentation-wise, I'd certainly appreciate more comprehensive background introduction on DI. The whole paper is pretty dense, especially in Sec 2, where it seems tricky for general audience to understand the main technical points of the paper unless equipped with sufficient background in DI.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper presents a new analysis framework based on differential inclusion (DI) theory for analyzing value-based reinforcement learning (RL) methods with discontinuous behavior policy changes (such as Q-learning with an epsilon-greedy behavior.) Using the new framework, the paper provides an explanation of the asymptotic behaviors of both Sarsa(0) and Q-learning with an epsilon-greedy policy and linear function approximation. Finally, the paper discusses several MDP examples and shows how an algorithm’s limiting DI affects its convergence behavior.
strength_and_weaknesses: The main strength of this paper is its comprehensive introduction of the new analysis framework that provides previously missing theory on how to explain unexpected behaviors in certain algorithms under approximation.
clarity,_quality,_novelty_and_reproducibility: The paper is generally clear and easy to follow. The explanations of the concepts are detailed and thorough.

The results presented in the paper seem novel.

Given the information presented in the paper, I suspect that the results would be reproducible.

One small suggestion would be to replace the phrase “Q-value function” with “action-value function” everywhere it is used. (This is not affecting my rating, it is only my personal preference.)

summary_of_the_review: This paper presents a new framework to analyze the convergence behaviors of algorithms with discontinuous behavior policies and function approximation. This work is likely of interest to those doing RL theory research, and could be of some interest to the larger RL research community as well. Therefore I vote to accept.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This work tries to explain the asymptotic behaviors of Q-learning and SARSA with $\epsilon$-greedy exploration, and the proposed tool is the differential inclusion theory. 

The strength and weakness of this paper are both very clear.

Strength: the paper has some merits since it introduces some interesting new toolkits of differential inclusion to the study of RL. It can still be a good starting point of studying the limiting behavior of the discontinuous dynamics of the algorithms.

Weakness: the proved result is very weak. 

(1). For SARSA with linear approximation: convergence to bad point, oscillation, and convergence to good point, are all possible.
(2). For Q-learning with linear approximation where B4 may not be true: divergence, convergence to bad point, oscillation, and convergence to good point, are all possible. That is, everything is possible, nothing is really proved. 

Moreover, since the possibility to converge (or diverge/oscillate) to all type of points, there does not seem to be a way to use the proposed analysis to help the algorithm to converge to the desired points.  (The authors justification that the result may help practitioners debugging is not convincing. After incorporating all engineering tricks to make the algorithms work, the resulting code will be far away from the clean vanilla algorithm studied here. The theory may not character the real applications.)
Decision: Reject