Loss Dynamics of Temporal Difference Reinforcement Learning

Summary

In summary, they study how learning dynamics and plateaus depend on feature structure, learning rate, discount factor, and reward function in the case of batch TD(0) for policy evaluation. This paper applies concepts from statistical physics to study typical case learning curves for TD learning in linear FAs with nonlinear but fixed features (specifically, their study is targeted at policy evaluation with batch TD(0)). They conjecture a Gaussian feature equivalence: roughly, having a high-dim feature vector, the learning curves of a TD learner are conjectured to be equivalent to that of one with Gaussian features having matching mean and correlations. Further, this view allows them to use a Spectral Perspective to find a proxy for what would constitute a harder reward function to optimize (showing alignment between learning rate progress vs. the measure; shaped reward being simpler than sparse reward).

Strengths

- A step in an important direction: towards better understanding the learning dynamics of TD methods - Proposing a creative tool for the analysis of TD methods - Good exposition of related works - Paper is well-motivated and clearly written - Claims are carefully stated and supported: no overstated claims - Experiments are pretty interesting and carefully designed

Weaknesses

- Considering tasks have a finite horizon (fixed T), it has not been made clear if the experiments are run using features that have a good representation of the remaining time in them or not. Of course, this could be my misunderstanding (to be clarified by authors in the Questions section). - Not sure whether the comparison between fixed and annealing learning rates make too much sense in the context of this study (to be clarified by authors in the Questions section).

Questions

1. Are the results of the Discount Factor analysis (Fig. 3b) for a dense reward scenario? Wouldn’t this be a very different case with sparse rewards due to the issues studied by van Seijen et al. (2019)? 2. Isn’t annealing the learning rate a condition (even for tabular TD(0)) to guarantee asymptotic convergence to the optimal V with probability 1? If yes, what is the comparison of Fig. 5c vs 5d really showing us in the context of this paper? - van Seijen *et al.* [NeurIPS 2019], "Using a Logarithmic Mapping to Enable Lower Discount Factors in Reinforcement Learning".

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

Limitations have been discussed sufficiently well.

Summary

This paper looks to introduce a new theory for the learning dynamics in the online batch policy evaluation setting for temporal difference learning. The paper introduces the Gaussian Equivalence Conjecture, which postulates that the learning curves in TD can be modeled by Gaussian features (with per-time-step mean and covariance over features and all trajectories). Along with this modeling assumption, the work does not prove this conjecture, but instead assumes this conjecture to be true to show empirical results in modeling policy evaluation learning curves analytically on a simple gridworld MDP with “place cell” features. Using this assumption and the example MDP, the work first shows results fitting their model with the learning curve of online policy evaluation, which is interesting in itself. Using this modeling assumption, the authors provide insight into the “hardness” of certain policy evaluation tasks and how it relates to their TD learning model with an example comparing sparse vs dense reward functions in policy evaluation. Beyond this, the work also shows examples (on the same domain) of their theory of learning dynamics predicting the effects of batch size, discount factor, learning rate and learning rate annealing. Finally, the work also uses this model to explain and predict what happens to learning dynamics in the case of reward shaping. The work uses this proposed model to reshape rewards to improve timescales of convergence by rotating the reward-scaling weights to be more aligned with features of high variance.

Strengths

Overall, I think the work is of great interest to the reinforcement learning community with a good amount of both theoretical and empirical results to back their proposed model of learning dynamics. The paper poses and answers well-founded questions, and is also well written. I only have a few (albeit important) questions I’ll pose below.

Weaknesses

My biggest issue with this paper in its current state is its set up. Currently, the proposed model is just a conjecture that seems to fit well with this one set of features (that are Gaussian it seems!) in this one gridworld environment. All the results seem to hinge on this conjecture being true, as evinced by the claim “We do not aim to provide a rigorous proof of this conjecture for TD learning but instead compute the learning curve implied by this assumption and compare to experiments on simple Markov Decision Processes”. Different forms of feature construction have been proposed throughout reinforcement learning history, including tile coding, polynomials, fourier basis etc. I’m still not convinced that this Gaussian model will carry over to learning dynamics with different features and different environments. While this is essentially my only concern with this paper (it’s very well written!), I think it is quite an important concern to address. Due to this concern, I have decided to only give this paper a weak accept. If more feature construction methods and more environments were included in these results, I would definitely be open to raising this score!

Questions

Throughout reading this work, I only have a few section-by-section questions: ******3.1****** Could you give more specific details with regards to this environment? Maybe even in the appendix? I don’t exactly understand what you mean when you say ‘The feature map is parameterized by the bandwidth of individual “place cells”’. ******3.2****** For Remark 2 and 5, could you elaborate a bit on “fully explainable by features”? Is this referring to the case of partial observability? or is it just the most general formulation of R as a function of (s, a, s’)? The notation for the proof for Proposition 3.1 is a bit confusing. I would suggest either simplifying by removing the notation that’s not defined here in the main paper and moving this to the appendix, or moving more of the appendix here.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

Please see the general comment made in weaknesses to address limitations.

Summary

This work utilizes concepts from statistical physics to analyze the learning dynamics of TD(0) (policy evaluation) under the assumption of Gaussian equivalence, online batch update and linear function approximation. Using the theory, it demonstrates how learning rate annealing and reward shaping can improve learning in various aspects, based on multiple synthetic experiments.

Strengths

The paper studies the learning dynamics of TD(0) from a novel perspective, which could provide readers with new insights and understandings

Weaknesses

1. The whole framework relies on an important hypothesis that is not sufficiently verified in the TD(0) context. The Gaussian equivalence conjecture is only justified using a toy MDP (Fig.1) without explaining how accurate this hypothesis is for general MDPs. The provided example is using RBF features and RBF reward, which could be favorable to the given theory. 2. The connection to least-square TD methods is missing. In the same regime as the current paper, LSTD has been extensively studied for its convergence and learning dynamics (see, for example, Tagoti and Scherrer (2015) and Pan et al., (2017)). It does not rely on the Gaussian assumption and should be compared with the convergence result in the current paper. Ref: - Tagorti, M. and Scherrer, B., 2015, June. On the Rate of Convergence and Error Bounds for LSTD (λ). In *International Conference on Machine Learning* (pp. 1521-1529). PMLR. - Pan, Y., White, A. and White, M., 2017, February. Accelerated gradient temporal difference learning. In *Proceedings of the AAAI Conference on Artificial Intelligence* (Vol. 31, No. 1). 3. It is unclear what Sec.4 is trying to demonstrate. The matrix A naturally appears in LSTD and has nothing special w.r.t. the current Gaussian equivalence setup. Minor - L136: correlation here means autocorrelation instead of Pearson product-moment correlation

Questions

Q1: Any comments on why the Gaussian equivalence assumption would hold for general MDPs? Q2: How are the current convergence results different from the typical results from the LSTD literature?

Rating

3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

1 poor

Limitations

The paper did not sufficiently explain its connection to the literature.

Summary

This paper provides a theoretical model that predicts the dynamics of TD learning. The theory assumes that the distribution of feature vectors is, in some sense, equivalent to a Gaussian distribution and predicts the value estimate at each iteration. The theory reveals a rich set of phenomena such as plateaus in TD learning.

Strengths

The complete dynamics of TD learning have not been previously studied. And the paper provides a unique perspective on this problem. The dynamics of TD learning according to the theoretical prediction are close to those in experiments, verifying the usefulness of the theory in these experiments. The theory is also consistent with some existing tricks to improve TD learning such as reward shaping and step-size annealing.

Weaknesses

The paper does not mention the limitations of its main assumption: the Gaussian Equivalence Conjecture. It verifies it using experiments in some small MDPs but these experiments do not tell when this assumption holds. The paper does not explain clearly its theoretical results, making it difficult to understand these results. The writing of the paper needs to be improved. Specifically, many sentences and notations remain confusing to readers. See Questions for details. typos: line 73: the features -> the vector of features line 78: the offline setting line 79: width -> with line 245: two "learning"s

Questions

Is T a constant or a random variable? If T is a constant you are considering the finite-horizon setting and the value function is horizon-dependent. If T is a random variable you need to specify how it is defined. "the algorithms bootstraps its current predictions to estimate future states" Not sure what you mean here. I think you mean algorithm, not algorithms. And I think you mean bootstrapping from the estimated next state's value. line 134: what are "the learning curves"? "high dimensional features" how many dimensions are needed? What do you mean when you say a set of learning curves is equivalent to another set of learning curves? eqn 3: what is the meaning of <x>_{y} in your notation? Line 138: "higher order cumulants of the features is negligible in high dimensional feature spaces under the square loss". Again, what do you mean by square loss. What do you mean by "higher" order "cumulants" of the features? Figure 1: what is this diffusion process? Proposition 3.1: what is the meaning of <>_s in the definition of L_n? Line 191: this remark seems to be much more useful. Why not present your result without assuming that B -> infty? Could you briefly explain under what conditions the theory holds when B is not infinity? Line 195: this remark also seems to be much more useful. Again, why not present your result without assuming that the value function is representable? Line 203: how is this remark different from remark 2? Line 205: what is w (without _n)? Line 209: "which can be learned easily and which require more sampled trajectories" Why is it "easily" when it requires more sampled trajectories? Line 216: "The theory predicts that," I do not see which part of your theory gives this result. Furthermore, how is this result different from the rate of convergence in a linear dynamical system? Proposition 5.1: what is a fixed point of a learning curve? How is eqn B.24 derived?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

N/A

Summary

This paper introduces the concept of statistical physics to analyze reinforcement learning models. The authors propose a theory of learning dynamics for RL, with an emphasis on the role of linear function approximation. They investigate how strategies such as learning rate annealing and reward shaping can positively modify learning dynamics and surmount plateaus. The paper concludes by revealing new tools for developing a theory of learning dynamics in RL, thereby setting the stage for future research in this domain.

Strengths

1. This paper introduces a novel method using statistical physics to formulate a theory of learning dynamics in RL. 2. The authors derive an analytical formula for the typical learning curve, demonstrating how their theory can predict the scaling of both learning convergence speed and performance plateaus based on problem parameters. This predictive ability is a significant advantage of the paper. 3. The paper outlines how this theory can assist in understanding and guiding design principles when selecting meta-parameters in RL algorithms. Such insights can enable practitioners to gain a deeper comprehension of how these factors influence the RL learning process.

Weaknesses

1. The paper does have limitations regarding practical implications. Although it presents a theoretical framework and makes predictions about learning dynamics, the methods utilized, such as linear approximation, deviate significantly from current reinforcement learning (RL) methodologies.

Questions

Is there a particular reason for choosing batch sizes that are not powers of 2, such as N=3, N=30, N=20, for the experiments? As far as I am aware, batch sizes that are powers of 2 are most commonly used for practical considerations.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

No concerns about negative societal impact.

Response

Thank you for the additional results and responses. It seems that most other authors have the same quip with the work: the Gaussian Equivalence Conjecture. Given the new results presented in the rebuttal PDF, I believe the the Gaussian Equivalence Conjecture is a decent modelling assumption that represents a representative range of feature representations. With these new results, I am bumping my score up to a 7. If accepted, I believe the work to be a valuable contribution to the reinforcement learning community, and opens up new directions of research in trying to understand and model TD(0) learning curves. On that note, a final suggestion: instead of assuming a _conjecture_ over features, why not phrase it as a _modelling assumption_ instead? Much of reinforcement learning is just (good or bad) modelling assumptions made over the world. This change of argument might serve the paper better.

Reviewer response needed

Hello Reviewer, The authors have endeavoured to address your comments in their rebuttal. The rebuttal phase is a key part of the NeurIPS review process. I invite you to read and respond to the author's comments as soon as possible, latest tomorrow, to give everyone time to continue and conclude the discussion. Thank you for helping make NeurIPS a great conference for our community.

Reviewer response needed

Hello Reviewer, The authors have endeavoured to address your comments in their rebuttal. The rebuttal phase is a key part of the NeurIPS review process. I invite you to read and respond to the author's comments as soon as possible, latest tomorrow, to give everyone time to continue and conclude the discussion. Thank you for helping make NeurIPS a great conference for our community.

Reviewer response needed

Hello Reviewer, The authors have endeavoured to address your comments in their rebuttal. The rebuttal phase is a key part of the NeurIPS review process. I invite you to read and respond to the author's comments as soon as possible, latest tomorrow, to give everyone time to continue and conclude the discussion. Thank you for helping make NeurIPS a great conference for our community.

Thanks for the clarifications

Thank you for your response. I remain positive about the paper and would like to see it accepted. My questions were clarified by the authors and as such I do not require any additions to the paper.

Discussion Follow Up

We are following up to hear if our rebuttal addressed the main concerns of this reviewer or if they have any remaining questions that should be answered before the discussion period ends. Thank you for your time.