Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper provides some temporal-difference (TD) learning algorithms based on the celebrated backstepping technique from control theory for addressing a family of nonlinear systems. The proposed TD algorithms are claimed to be stable and convergent in contrast with the divergent behavior of standard TD algorithms. Several existing TD generalizations have been shown as special cases of the proposed backstepping TD algorithm.    
strength_and_weaknesses: The paper draws ideas from control theory and presents stable and convergent backstepping TD algorithm for off-policy learning. The idea is interesting and seems effective. 

Strengths:
+ Interesting combinations of backstepping control with model-free TD learning
+ Well-established analysis and stability results
+ General enough to accommodate existing TD modifications

Weaknesses:
- Backstepping design and theory is suited for nonlinear control systems, but only linear BTD algorithms are discussed here
- Theoretic analysis (e.g., asymptotic/non-asymptotic convergence) of BTD is lacking
- Numerical convergence comparison against existing TD variants not provided


clarity,_quality,_novelty_and_reproducibility: The paper is generally clear, well-written, and contains some original ideas and algorithms.
summary_of_the_review: Some detailed comments are listed as follows.
1. In the Abstract, please include theoretical and numerical convergence comparison with existing TD algorithms.
2. How Eq. (5) is obtained?
3. The paper focuses only on second-order linear systems. When the order of the system increases, the backstepping technique will have a complexity explosion problem pertaining to computing the derivatives of the virtual control. So would this have an impact on the computational complexity of the proposed algorithm?
4. The paper contains quite some grammar issues.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies TD-learning for a non-linear control theory perspective. Motivated by the idea of designing stabilizing control policies for non-linear ODE systems based on the control Lyapunov function method, the paper studies TD-learning as a special case. The paper designs a novel TD-learning algorithm that is stable under linear function approximation in the off-policy learning setting, and provides extensions to GTD2 and TDC. The paper is mostly theoretical and uses a few experiments to illustrate properties of the new algorithm.
strength_and_weaknesses: === Strength ===

The paper seems to provide a novel and unifying perspective on viewing various TD-learning algorithms under linear function approximations in the off-policy learning setting. Prior work such as GTD and TDC, which have been motivated to bypass the instability of vanilla TD-learning, can be understood as special instances under the new framework proposed in this paper. The paper also suggests a new stable TD-learning algorithm, which is quite interesting in its own right.

=== Weakness ===

Overall, the intuition of the new algorithm is not very clear, despite the fact that it has been derived based on control Lyapunov function and leads to stable learning, and the fact that it can be implemented as a single time scale algorithm. The paper can be greatly improved if further intuitions and explanations of the new algorithm can be provided, beyond control-theoretic mathematical aspect of the algorithm. The experiment section of the paper is also quite simple, making it more difficult to assess the advantage of the new algorithm.
clarity,_quality,_novelty_and_reproducibility: === Clarity ===

The paper is written clearly overall. Presentation-wise, certain equations can be presented in a more visually clear manner. General readers will also appreciate more in-text explanations behind the equations.

=== Quality ===

The paper has relatively high technical quality.

=== Novelty ===

The paper is novel as far as I can see, in that it provides a novel application of non-linear control theory to the TD-learning case and has managed to derive a new algorithm too.

=== Reproduce ===

Experiment results are fairly simple and should be easily reproducible.
summary_of_the_review: A few questions and comments.

=== **Notation** ===

In Eqn 4, I suggest the author used notation other than $\lambda_t$ for the state variable. Maybe $\lambda_t$ is a standard notation in the control literature, since much of the audience has RL background, it might be better to use something like $y_t$ as the state variable, which also distinguishes from the controllable state $x_t$.

The notation $x_s(\lambda_t)$ is confusing. From what I understand, $x_s(\cdot)$ is itself a function and the index $s$ does not stand for anything. Maybe it is better to replace $x_s$ by something like $\tilde{x}$ altogether because it can be easy for certain readers to relate $s$ with the time index $t$, leading to confusions.

=== **TD-learning** ===

I think a factor of $\phi_k$ is missing from the TD-learning update in Sec 2.5, TD-learning should update as 
$$e_{k+1}=e_k+\alpha_k\rho_k\delta_k\phi_k$$
where $\phi_k$ is necessary to match the dimension against $e_k\in\mathbb{R}^n$.

In Eqn 5, $X$ should be $\Phi$.

=== **Motivation for Sec 2.6** ===

Presentation-wise, as an example, I think it would be good for the paper to provide more motivations for the behavior of GTD, GTD2 and TDC. These algorithms have been designed to improve stability of vanilla TD-learning -- can we spot from the vanilla TD-learning's update rule that it is unstable, can we say something about the non-PD of the $A$ matrix defined in Eqn 6, can we show some plots displaying the instability? This provides motivations for the class of stable TD-learning algorithms that provide motivation for this work.

I also hope the authors can provide more elaborations on the background in Sec 2.6, where they say "the idea behind these algos is to minimize the mean-square error of MSPBE". I don't immediate see how the idea of minimizing mean-square error of MSPBE is reflected in Eqn 7-8 or equations right above them. Maybe it is good to give a quick explanation here. It is also good to explain why minimizing MSPBE helps improve stability, which is not immediately clear.

=== **Sec 3.1** ===

It is a bit confusing where Eqn 9-10 come from, somehow I feel they are related to the ODE systems on page 9 right above Eqn 7, but no clear explanation is given. Eqn 9-10 defer from the ODE system right above Eqn 7 by a factor of $-\eta A\lambda_t$, whose motivation is not clear to me. The authors should provide a more clear motivation as to how one arrives at such an ODE system to start with and why adding the extra term $-\eta A\lambda_t$.

=== **BTD** ===

BTD in Eqn 14-15 are the main contributions of the paper. Though it is good that the authors have arrived at a novel TD-learning update rule that is stable in the off-policy case, overall it feels like it is not completely clear how one arrives at the new update rule in an "easy-to-understand" way. This can be better strengthened and clarified by providing more motivations for each step of the derivation, such as the origin of the ODEs in Eqn 9-10.

Meanwhile, given Eqn 16-17, it is better if the authors can provide further motivations and intuitions for the updates. Decomposing the terms in the ODE updates, can we deliver interpretation intuitions for each term, do they correspond to certain types of modified TD errors? Since the algorithm is single time-scale, it will be interesting to understand exactly what mechanism leads to the stability of the new update rule, beyond the set of math that arrives at the conclusion that the update is stable.

=== **$\eta$** ===

Thus far to me, the role of $\eta$ is mysterious and not well justified in the paper. In Eqn 9-10, the extra factor introduced $\eta$ into the ODE system. Throughout, it is not clear what role $\eta$ plays in stabilizing the ODE system. It seems that $\eta=0$ recovers GTD2, but what is the intuitive explanation for having $\eta>0$? Is it just a numerical trick, does it correspond to certain interpretable regularization? 

=== **Experiments** ===

Experiment results are probably too simplistic in the main paper. I'd appreciate a table or plots of comparison of BTD vs. GTD2, TDC and vanilla linear TD, emphatic TD on tabular domains listed in Table 1.

Since the role of $\eta$ is not clear in the BTD update and is poorly motivated, it is not clear what it means when $\eta>0$ works more poorly than $\eta=0$ (GTD2) on the Baird example. Can we characterize when to use $\eta>0$ and when to set $\eta=0$ in practice, does the theory provide any useful indications on that?

=== **Minor comments** ===

The first sentence below Sec 3.3 does not read well.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper presents a brand new approach for developing gradient TD methods from canonical control theories. The approach starts with finding an ODE of interest and then uses back-stepping to stabilizing the ODE. The approach succeeded in both recovering existing GTD methods and developing some variants.
strength_and_weaknesses: Strength: 
This paper is well written and easy to follow. Using back-stepping to develop stable off-policy RL algorithms appears novel to me and can probably open up a new direction in RL. The authors did a good job in connecting their methods with existing ones. Though I didn't check the proof line by line, I feel confident that the proof should hold.

Weaknesses: 
My major concern is that the proposed approach feels so hand-crafted. 
The development of the new algorithm starts from the ODEs in (9) and (10). I absolutely have no idea where the two ODEs come from. It seems that the ODE in (9) comes from the ODE just above (7), which is the ODE from GTD2 updates. But how do the author motivate the introduction of \eta in (9). Even we can accept that the authors somehow magically introduced this \eta, motivating (9) with the ODE from GTD still does not make sense to me. **If we do not know GTD beforehand, is there still a reasonable way to write down the ODEs in (9) and (10)?** If the authors cannot provide an affirmative and convincing answer, I do not think the proposed framework of using backing stepping is significant -- it can only start from existing solutions and cannot start from the problem
clarity,_quality,_novelty_and_reproducibility:  quality, clarity and originality are good
summary_of_the_review: See above
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Temporal difference learning is a foundational idea in reinforcement learning. But the convergence properties of the algorithm have been somewhat mysterious since its introduction. Tsititsiklis and Van Roy (1997) offered some clarity, showing that TD converges with 'on policy' sampling when linear function approximation is used. Counterexamples show divergence is possible with off policy sampling or nonlinear function approximation. Gradient temporal difference learning algorithms [Sutton et. al, 2008] represent another breakthrough, as they provably converge with off policy sampling. In all cases, the problem reduces to understanding whether the solution to a certain ODE is globally asymptotically stable. 

This paper uses the backstepping technique from nonlinear control theory to stabilize ODEs arising from the dynamics of TD. This perspective offers a new way to derive existing gradient TD algorithms and lets the authors propose some convergent alternatives. 

*Strengths:* The paper offers a fresh perspective that connects two large bodies of academic literature. All revierwers feel the paper is sound and that this connection *could* lead to useful results in the future. 

*Weaknesses*: It currently feels like GTD can be understood after-the-fact through the lens of backstepping. But currently, it still seems difficult to derive truly new algorithms from this perspective. It is possible, however, that experts in nonlinear control theory have trained intuition and will find this framework to be a key tool. 
justification_for_why_not_higher_score: As discussed above, the paper offers new perspectives which *could* prove quite useful. To my reading, spotlight presentations should show evidence of having more substantially moved the state-of-the-art.
justification_for_why_not_lower_score: The paper appears to be sound and to tackle a foundational question in RL. New perspectives, especially those that offer new links to a large literature in another field, have the potential to inspire many important future developments.
Decision: Accept: poster