The RL Perceptron: Generalisation Dynamics of Policy Learning in High Dimensions

Summary

This paper focuses on developing theories for the learning dynamics of policy gradient reinforcement learning (RL) algorithms with a particular focus on high-dimensional latent feature space. As an early work along this direction, the authors study a binary-action environment setup for simplicity. The authors develop ODE-based learning dynamic equations that generalizes across diverse protocols, including different policy horizons, the existance of failure penalties, and the choices of dense / sparse rewards. The authors further develop theories for optimal learning rate, optimal horizon scheduling, and learnability with respect to these hyperparameters. The authors finally conduct an experiment on vision-based Procgen Bossfight environment and demonstrate that under more general settings, similar phenomena arise as their theoretical model developed under simpler setups.

Strengths

Overall the paper is well-structured and well-written. Under the binary-action environment setup, the ODE dynamics model developed by the authors is shown to accurately describe diverse common learning setups. There are also extensive experiments and plots that illustrate the difference of learning dynamics under different environment and optimization parameters, which provide much insights for the readers.

Weaknesses

In the main paper, the latent feature space dimension $D$ is fixed to 900 except Procgen. It would be helpful if authors provide more analysis on the influence of latent dimension $D$ on the learning dynamics. Empirically, for which $D$ is author's proposed ODE-based learning dynamics equation still accurate? For Fig. 6b, Plotting environments of different episode lengths by comparing their "Number of episodes" seems misleading. Authors claim that agents learn slower for environments with shorter episode lengths, but this is not accurate. If one compares the total time step of learning (num episodes * episode length), agents acturally learn faster on these shorter horizon environments.

Questions

See "weakness" section above. Minor typos: - Equation 2: looks like 1-eps_g is defined as disagreement instead of eps_g. - Line 194, Fig. 3c -> Fig. 2c

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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

3 good

Contribution

3 good

Limitations

Limitations need to be explicitly addressed in the conclusion section, including (1) the simplicity of the problem setup studied by the paper (binary action scenarios); and (2) the paper's focus on shallow, one-layer neural network that takes high dimensional feature as input. For more general applications, neural networks typically consist of many layers, activations, and normalizations stacked on top of each other, so empirical analysis in these scenarios will be particularly helpful.

Summary

This paper proposes a model for solving high-dimensional problems in reinforcement learning (RL) referred to as the RL perceptron. The model is used as a framework for analyzing generalization dynamics of simple neural networks for RL tasks. More precisely, the model employs a student teacher design in which the student takes a sequence of choices and the correct choices are given via the teacher. However, the student does not have access to the correct choice at every step but rather only receives a signal at the end of each episode. As such, the model is studied as a sequential version of the perceptron algorithm. The work first derives a set of differential equations that capture the learning dynamics of the model. The dynamics are analyzed via the overlap of the weight vectors of the student and teacher respectively. The manuscript studies multiple reward settings: a vanilla setting that constitutes sparse rewards, a setting with penalty at every step and a setting where the agent is given small sub-rewards after a certain amount of time. Each of the proposed settings provides insights into how different reward functions lead to different solutions for optimal parameters when solving the system. The derivation of optimal hyperparameters demonstrates that annealing the learning rate and building a curriculum of episodes are crucial for optimal convergence. Then, it is shown that there exist phase transitions under different learning rates that can lead to convergence to sub-optimal minima and that there is a speed-accuracy tradeoff when varying reward functions. Lastly an experimental section provides insides in the practical properties of the algorithm that closely follow the analytical results on the speed-accuracy tradeoff.

Strengths

1.) First, I would like to say that I enjoyed reading this paper. I think it is well written and well structured with a clear line of reasoning throughout the manuscript. The figures are illustrative of the analysis and the captions are sufficiently descriptive to understand the plots quickly. 2.) The idea of employing a perceptron-like algorithm in order to understand the policy gradient system dynamics is novel to the best of my knowledge and the generated insights are interesting. I think this is a nice contribution as it offers a way to analyze high-dimensional RL systems in a different way than the commonly employed linear MDPs. 3.) The manuscript is technically sound and the analysis provides a good understanding of the proposed algorithm and its inner workings. I did check the math in the appendix for crude errors and was unable to find any but I did not try to understand all the math in detail. 4.) The manuscript provides a way to think about RL systems that is not common and I think it is likely going to be useful in understanding some parts of the systems that may have been hard to understand previously. As such, I think it is a decent contribution that can likely be built upon by others in the sub-field of policy gradient methods.

Weaknesses

a.) The connection to policy gradients was not immediately clear to me. It might make sense to move equation 9 in place of equation 1 and highlight the connection between the perceptron update rule and the REINFORCE algorithm in a brief sentence. I think it would be good to highlight that the update rule uses an approximation that is only accurate early in training. b.) The limitations of the model are addressed rather sparsely. I think the work would benefit from having a clearer picture of the weaknesses of the approach which would enable researchers to use it and improve upon it in the future. c.) The model seems to be unable to solve the benchmark problem fully. However, it is hard to tell whether that is just a limitation of the model or whether the task is hard the way it is designed with the changes in the manuscript. Having a baseline performance line in the plot or giving a brief sentence of what the expected performance of a commonly used RL algorithm on the benchmark is would be very useful to determine the capabilities of the method. d.) I think one key thing that is missing from the paper and would make it a very strong contribution is to show the relationship between the proposed model and common deep RL methods. It would have been nice to have a direct comparison from the proposed method to a neural network approach using standard REINFORCE-like updates to see if there is a correlation produced from insights of the RL-perceptron with the behavior of the regular deep neural network. I do understand that space is limited though. ---- Overall, I think changes that could improve the manuscript would establish the model's connections to other research that people have done in the area. This could, for instance, include baseline performances, transfer of insights to other methods or any theoretical results that put the work into reference with commonly knows results. Minor clarity suggestions: * Line 250, there is a broken off sentence in there that should be removed. * Line 562 equation reference is missing.

Questions

Q1: What is the relationship between the proposed algorithm and standard policy gradient approaches with deep neural networks? Are there any conclusions that can be transferred from the RL perceptron to standard deep RL algorithms? Q2: What is the expected performance on the benchmark task where we would consider the task solved? Is it possible to win 100% of the time? This seems to be crucial information in order to determine the practical utility of the algorithm. Q3: One question that I have is about the connection between the proposed method and the standard perceptron algorithm. Is there a reduction from the RL perceptron to the standard perceptron? Suppose the model is updated at the end of every epoch. I’m thinking something along the following lines. Let n be the number of correct guesses made by the algorithm and N be the number of total timesteps in a trajectory. Then N-n is the number of incorrect guesses. Assume the sparse reward model where we have to be correct on k guesses to see a reward. Now, take a full trajectory as an input to the algorithm. If k < n, label the trajectory positive, otherwise negative. Of course there is some detail missing that would include the teacher in the labeling process but you should get a rough idea. If such a reduction exists it would reduce the problem to binary classification of whether or not a certain action sequence will lead to success.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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

3 good

Contribution

3 good

Limitations

I do not believe there is any negative societal impact that needs to be addressed regarding this work. The limitations are addressed rather sparsely. As stated before, I believe that the manuscript would benefit from more structured limitations sections. One limitation that I see is that the model currently requires actions to be discrete and (possibly ?) binary. While for a first version of the model this is absolutely fine, this might be something that researchers can work on in the future. Another limitation of the model is that it seems to not be able to fully solve the suggested benchmark problems. Again, I don't believe this to be an issue for the manuscript as the goal is not to provide a state-of-the-art model but rather to make progress towards understanding the learning dynamics of deep RL systems. Yet, in the future a goal should be to have models that can be described analytically that also achieve comparably high performance on realistic tasks.

Summary

The authors develop a set of differential equations that describe the learning dynamics in high-dimensional settings, allowing for a quantitative analysis of learning behaviors. This framework enables the computation of optimal hyper-parameter schedules and the visualization of phase diagrams for learnability. It also serves as a starting point for exploring RL scenarios closer to real-world situations, including those with conditional next states. The RL perceptron can be used to investigate various training practices, such as curricula, and advanced algorithms like actor-critic methods. The authors aim to gain analytical insights from the differential equations, particularly regarding how initialization and learning rate affect an agent's learning process. Overall, their research highlights the complex interplay between task, reward, architecture, and algorithm in modern RL systems.

Strengths

* The paper tackles an important problem of understanding high dimensional RL policies. * The method section seems theoritically sound.

Weaknesses

Experiments are not convincing. For a paper investigating such an important problem, the paper should have shown results on multiple environments.

Questions

I don't have any questions.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

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

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

A considerable limitation of the paper is the lack of a comprehensive evaluation of the method. The paper provides only results on one experiment. I would suggest the authors conduct more thourough experiments in order to make the applicability of method more clear.

Summary

The work proposes a theoretical framework to study the average case learning behavior of deep RL policy gradient methods. The framework is based on ODEs that can describe the typical learning dynamics of PG RL agents. The framework is used in various settings to describe learning behaviors in these and a final experiment on training a policy-gradient agent in a ProcGen game is added to bridge the theory-practice gap. This final experiment verifies that a speed-accuracy trade-off exists in practice, similar as predicted by the theoretical framework.

Strengths

* The work addresses an important aspect in deep RL research as most theoretical guarantees for RL are not well connected to the practical side of deep RL. * The work sets out to provide a theoretical framework from which to study deep RL methods. * It shows how such the theoretical framework can be used to understand the influence of * delayed rewards and reward penalties * learning rate schedules and episode lengths * reward stringency

Weaknesses

* The work was very difficult to follow for me. Due to the structure of the paper, many aspects seem to "fall out of thin air". * Without Appendix A it seems impossible to begin to understand Section 2 since more assumptions about the student teacher environment are given. * It often feels like the work requires extensive prior knowledge to be understandable. * Wording is often confusing. For example, in the beginning when talking about the reward for the RL-Perceptron case Fig 1 has a description about rewards that seems permissible for very dense rewards, whereas lines 48-50 talk only about extremely sparse rewards. Overall the paper seems very interesting and full of great ideas but due to a somewhat convoluted presentation and missing details that seem to be pushed to the appendix it falls short of clearly communicating these ideas. I might have missed something obvious, but to me it seems that the paper would first need fairly substantial rewriting to be easier to parse before it can be accepted.

Questions

Could the framework be adapted to work for other RL agent types?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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

2 fair

Presentation

1 poor

Contribution

3 good

Limitations

The authors do not explicitly list limitations of their framework

Summary

The paper discusses the application and theoretical understanding of Reinforcement Learning (RL) algorithms in high-dimensional settings. The authors propose a high-dimensional model of RL that can capture a variety of learning protocols and derive its dynamics as a set of closed-form ordinary differential equations. The authors introduce the RL perceptron, a model for high-dimensional, sequential policy learning. In this model, a student network learns from a teacher network in a sequential decision-making task. The student does not observe the correct choice for each input; instead, it receives a reward that depends on whether earlier decisions are correct. The authors derive an asymptotically exact set of ODEs that describe the typical learning dynamics of policy gradient RL agents. They use these ODEs to characterize learning behavior in a diverse range of scenarios, including exploring several sparse delayed reward schemes, deriving optimal learning rate schedules and episode length curricula, identifying ranges of learning rates for which learning is 'easy,' and 'hybrid-hard,' and identifying a speed-accuracy trade-off driven by reward stringency. They also demonstrate that a similar speed-accuracy trade-off exists in simulations of high-dimensional policy learning from pixels using the procgen environment "Bossfight" and Atari "Pong". The authors aim to close the gap between theory and practice in high-dimensional RL. The paper also discusses the sample complexity in RL, statistical learning theory for RL, and dynamics of learning, providing a comprehensive overview of the current state of RL theory and practice.

Strengths

This is a robust theoretical paper that enhances our comprehension of high-dimensional RL policy learning. The paper's claims are supported by high-level experimental evidence. A significant advantage of this paper is its use of the challenging procgen "Bossfight" environment, which is much closer to the real use cases compared to the preceding works. Additionally, the "Pong" game was analyzed in the supplementary materials to demonstrate the speed-accuracy tradeoff. Another strong aspect of the paper, and a significant advantage, is its focus on analyzing the average-case scenarios rather than the worst-case ones. The authors have also released the code to reproduce the results, further strengthening the paper's credibility.

Weaknesses

To the best of my knowledge, the paper does not exhibit any significant weaknesses.

Questions

1) Do you expect any substantial changes in the main results and conclusions in the paper when bigger/deeper policies are used? 2) What about environments with higher-dimensional action space?

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

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

4 excellent

Presentation

3 good

Contribution

4 excellent

Limitations

Limitations were addressed reasonably well.

Summary

This paper introduces a new problem definition and class of solution methods for decision making. The motivation put forward by the authors is that the current pool of solution methods do not have theoretical results that capture the neural functional classes used by practical applications in RL, leaving a gap between theory and practice. The authors claim that the model of learning by reinforcement that they propose has sufficient flexibility to capture the same class of problems as the classic RL model, and that their problem definition, despite its generality, is solvable in closed form for higher dimensionalities (and even infinite), as opposed to the classic RL model, presumably formalised as POMDPs. In addition, they claim their model (unclear whether the authors mean the solution method or the problem, see detailed comments) behaves similarly w.r.t. hyperparameters, for which they provide optimal schedules and hypersensitivity plots. Moreover, the authors claim their proposed class of problems and solution methods exhibits in practice similar behaviour as predicted by theory, and closes a gap between theory and practice, providing as evidence empirical illustrations in a particular environment, specially designed, called “Bossfight”, which they engineer using a platform for a procedurally generated environments.

Strengths

$ \textbf{Originality}$ The authors propose a new problem definition and class of solution methods for RL, particularly policy optimisation. They describe their model as a perceptron, which they call “the RL perceptron”, and analyse the learning dynamics of a particular solution method for action space of 2 discrete actions. They then define different problem instances via heuristics for various feedback signals that such a solution method can receive. The authors propose a new perspective on RL inspired by statistical mechanics and dynamical system theory. $\textbf{Quality}$ The particular math and statistical expressions the authors derive was not checked in detail beyond the first few simple update equations, which seem correct. The appendix was not verified for correctness. Plots also appear to be consistent with the experimental claims provided in text. $\textbf{Clarity}$ The paper is at times clear, with some mysterious redefinitions, naming, and confusions (see in the next sections). Although the flow is cursive, the authors do not use the general breakdown of the paper and miss important sections like a “Background” section, which is placed in the introduction. It does not bother much, but clearly marking such section can help the reader understand better what is novel and what is known. $\textbf{Significance}$ The main motivation of the paper is very important. Theoretical guarantees for solution methods with feasible at-scale practical implementations is highly desirable, since this informs us that they are generalizable to all problem instances, not just the particular settings in which they were tested in and shown good empirical results. Generalisation and theoretical guarantees in RL, particularly in policy-based methods with neural policy classes, which are the most successful algorithms used in practice, is a very important area of research.

Weaknesses

$\textbf{Motivation}$ While the motivation of the paper is very important, i.e. insufficient theoretical guarantees for policy-gradient methods with neural function classes, PG have been shown to have global convergence beyond tabular fn classes which the authors claim to be the issue. For log-linear policy classes see: Yuan et al - “Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies” - and references within. For neural policy classes see “Neural Policy Gradient Methods: Global Optimality and Rates of Convergence” -- Wang et al and references within. Both of these show global convergence, the latter for a two-layer NN, including finite-sample guarantees/convergence rates and properties of actor-critic methods, with estimated critics, required for convergence. $\textbf{Relation to RL and placement in context}$ The second main weakness of this paper is the lack of placement of their work in relation to the standard RL model used by the community through the formalism of MDPs or POMDPs, with accompanying class of solution methods. The paper would be significantly strengthened if they authors can clearly state what the limitations are with the previous class of problems described in RL via a reward signal and transition dynamics and in addition for POMDPs, how current definitions of high dimensional observation spaces proposed are better captured with their problem definition. It is unclear how the models proposed by this paper generalize beyond the log-linear policy class and action spaces of dimension 2, described within. The authors claim lack of theoretical work, yet previous work in RL has also analyzed distribution shift and generalization error, but with a different definition than the authors propose. It is unclear to me what the prior limitation in definition were and how this is a better way of capturing such quantities. Additional details in this respect would significantly strengthen the paper.. $\textbf{Purpose/Goal}$ Furthermore, it is rather confusing the purpose of the paper, i.e. it seems the authors compare problems against each other, for the same solution method, instead of comparing solution methods that are general enough to work on every problem instance. It is also confusing the setting and problem definition. It appears that the problem is not learning by trial-and-error, and that the problem instances proposed need heuristic descriptions of reward signals, horizon sizes and task termination. It is unclear the setting in which we are in, whether that is undiscounted finite-horizon, or continuing learning (infinite horizon, average reward). The authors reference terms from RL related to this but never actually formalize the problem. $\textbf{Empirical study/experimental illustration}$ Lastly, the experimental section is performed on a certain game designed in particular way, which is an illustration rather than a practical algorithmic implementation, akin to the solution methods employed in empirical RL. More details/questions in the next sections about these points. I am happy to adjust my score if I have not correctly understood the paper, and the authors provide more details on how their work can be placed in the context of RL, which would help me understand the significance and impact of the result and analysis provided.

Questions

$\textbf{Confusion w.r.t. setting}$ At times it is unclear which setting the authors analyze? Is it the finite-horizon setting? There is a significant emphasis on horizon size $T$, but this in their formulation is a hyperparmeter, which a solution method optimizes, not part of the problem definition and or the objective an algorithm is trying to optimize. $\textbf{Confusion w.r.t. the feedback signal}$ Another confusion is the feedback signal. The authors propose different heuristics for defining a feedback signal, but it is unclear what their connection is with the current reward signal in the standard MDP/POMDP model. E.g. the number of times n, and the boolean task termination signal, the authors relate to sparsity, but it appears to also be related to the Markovian properties of the reward signal. Isn’t a scalar reward signal enough even for continuing problems? Since the reward rate can adequately describe the class of lifelong learning problems in RL. The authors mention the reward rate in the related work only, but throughout the paper they have an objective which they call “generalization error” or later redefined as “test error”. Next, the reward is given by a teacher represented as a neural network, where does this come from? The paper would be considerably strengthened by a clear comparison with the current model and a description of the limitations of the current model that they are trying to solve. At line 109 - they say receiving penalties is not always beneficial, but this should be a problem definition, not available for an agent to change. At line 167-which RL protocols? finite/infinite horizons? discounted/undiscounted(continuing), partially Markovian reward signals of certain orders? Line 185 -”low asymptotic performance” — for a particular solution method? Line 186 - “finite-size effects” - unclear what this means. Changing the reward changes the objective and the RL problem is known to be non-convex anyway. It is unclear how this analysis of the stationary points relates to what is known for policy-gradient methods. Line 189 - “sub-reward” ? $\textbf{Confusion on solution methods}$ The authors propose a particular model of policy gradients defined via a student network (or linear layer?) + a sigmoid activation function. It is unclear if their model/method extends to more general classes, particularly since in RL the class of solution methods extends to highly combinatorial action spaces or continuous action spaces, with log-linear, softmax, or neural function classes. $\textbf{Confusing comparisons/hyperparameter optimization}$ At times the authors compare different objective functions and say that a particular change in the reward or dynamics of the problem would yield better performance, which I find very confusing, since in general we are trying to compare the performance of different solution methods on the same problem/objective function, known or unknown. They then describe a tradeoff between problems, and how fast they are solved by the same solution method, or how well that solution method solves them (accuracy). They also appear to optimize over objectives, by doing sensitivity plots on the horizon size or the number of lives of an agent, and by comparing different feedback signals against each other claiming that one is better than another. Line 198 - “optimal schedules for both hyper-parameters” - isn’t this problem dependent? Why is the episode length a hyperparameter? Why is this under the control of a solution method/algorithm/agent? $\textbf{Confusing referrals to exploration}$ At times the authors mention exploration, but I am very confused how a shallow single layer neural network with a sigmoid function is dealing with exploration. It is even unclear how exploration is defined for the optimization problem described by the “generalization error” objective function they propose. Generalization over what? Observations? Tasks? Environments? Line 212 - “refined information” - wdym? Isn’t this changing the problem? $\textbf{Confusion about phase transitions}$ Are these transitions between different objectives? Because they change based on the problem instance. Line 253 “first-order phase transitions” - Not defined. I don't know what this means, I assume related to first-order stationary points of the objective function the solution method optimizes. $\textbf{Confusion about speed-accuracy tradeoff}$ It is unclear the significance of this quantity. Doesn’t it actually tell you the speed with which different problems are solved by the same solution method that you chose? It is not a description of a solution method. $\textbf{Clarity}$ At times the author use particular definitions without defining them, e.g., “reward stringency”, “order parameters”, “speed-accuracy” (speed of what? accuracy of what, w.r.t. what?). $\textbf{Related work}$ The authors mention they are concerned with reward rate and episode length, but generally, the continuing setting using reward rates is the infinite horizon problem setting using average reward formulation (and thus reward rates) and has no episodes, by definition being continuing, never-ending, lifelong. In the same section, the authors mention they focus on the average-case dynamics of policy-gradient methods, what does it mean “average-case”? There are reasons to use worst-case guarantees, they tell us the behaviour of an algorithm on all problem instances. Is the average case, an expectation over problems? The authors make certain referrals to terms from other fields, like statistical mechanics or heuristics from statistical physics which may be unknown to the reader and unclear on their significance. If they are important, they should be defined. $\textbf{Experimental section}$ Isn’t the dimensionality of the observation space very small to be representative of “high dimensional” observation spaces? Line 292: what is a pure random policy? Does this mean this is off-policy learning from a behaviour policy that is random? Wouldn’t that mean that the gradient-update is biased? The problem instance seems very particular. It is unclear how this particular problem instance reflects the generality of the claims set in the introductory contributions. $\textbf{Miscellaneous}$ "D" is not defined, though from context it appears to be the dimensionality of the observation space. Typo at line 250. Sentence doesn’t make any sense. “Learning with $\eta_2 This is not a …” Typo at line 246 “the the”

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

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

$\textbf{Lack of clear description of the limitations}$ The authors do not provide a clear description of the limitation of their model. It is unclear what exactly is “solvable” in closed form, is it any problem of any dimensionality with any kind of reward signal, including non Markovian? How general is the problem that is “solvable”? Does it capture all problems a POMDP would capture, and these problems are solvable? Any kind of additional information in this respect would be useful for the reader. It is also unclear what is “the average-case”. A short definition would be very useful.

Reply

Thanks for authors' rebuttal! My concerns (different latent space dimensions and Fig 6b experiment clarification) have been sufficiently addressed and I'll increase my confidence. (For "slower" in my original comments I meant a slower rate of asymptotic convergence, not the initial learning speed)

Rebuttal Response

Thank you for the detailed rebuttal. I believe you address all of my concerns. ### Regarding Presentation > We plan to move to the main text the assumptions from appendices B [...]. Does the reviewer think that these changes will improve the clarity of the paper without adding details irrelevant to the understanding of the main text? Yes absolutely! I believe that would have helped me a lot when reading the paper the first time. I agree that not everything needs to be in the main part of the paper, but it only started to click for me after I had a look at appendix B. ### Regarding reward density > May we ask the reviewer to clarify where our text might suggest dense rewards? We would like to clarify this issue in the text. I apologize. But it seems I was a particularly dense reviewer. As written in my original review, Lines 48 - 50 caused my confusion. The first part states "[... The student] receives a reward which depends on whether earlier decisions are correct. [...]" I misinterpreted this statement as meaning a reward for every decision. The second part then clearly states that the sparse reward is considered which is also confirmed by the caption of Figure 1. I didn't do a good job in communicating where my misunderstanding comes from and I apologize for that. ### Updating my score I have read all other reviews and the rebuttals. Since my initial score deviated most substantially from all other reviewers I have also re-read the paper. I now do believe that my original score was too low. I still see that the work has substantial value to the community and, as stated originally, is full of great ideas. As such it should have only been, at worst a weak reject or borderline accept. Having already stated that I believe the rebuttal to address my concerns, I do increase my score.

Rebuttal Response

Thank you for the clarifications and the rebuttal response. After reading the authors’ response I believe my initial understanding of the paper was correct in that the authors are showing properties of the problem (if the reward function or the episode length change) coupled with a particular solution method (author’s say it is the REINFORCE algorithm). I really hope the authors clarify this very important information in the paper as none of these was clear in the original manuscript (motivation, scope, purpose, problem formulation, the setting in which they operate, which I know understand to be the <<undiscounted finite horizon with episode length T>>) I never believed this paper to be providing a new solution, but I also do not completely understand the insight it would bring to RL algorithms per se. REINFORCE is not really a practical algorithm. Among the reasons is the finite horizon setting of a certain length, and sample inefficiency due to that, particularly since in practice these values need to be very large and are ill-suited for this algorithm when paired with sparse rewards. Afaik it also globally converges sublinearly for all problem instances. Log-linear policies afaik are relatively well understood and proven globally convergent with known rates, even for actor-critic algorithms with value estimated critics. I also do not fully understand what the average case really means (the explanation provided is not rigorous) if we are talking about problems not solution methods. Since we do not have any control over problems, how can there be an average case? Our contribution differs by exactly characterising the typical learning dynamics at all times, rather than at the end of training (convergence). Isn’t this what sample complexity results also show? Asymptotic complexity is something else, but iteration/sample complexity would show how learning behaves at any time. Because observations are sampled, every observation is almost guaranteed to be unique (generalisation is over observations). So observations are in fact states? Are you investigating MDPs? $\textbf{Updating my score}$ I have read all other reviews and the rebuttals. It is not clear to me that this approach will provide more insight into RL algorithms or MDP problems when used in RL algorithms, nor do I see how this explains the behavior of commonly employed methods used in practice. However, I see that the work has value to the community since other reviewers have found it useful and interesting, so I will increase my original overall score.