Online Nonstochastic Model-Free Reinforcement Learning

Summary

This paper introduces an extension to model-free RL that has its roots in non-stochastic control. The main idea is to adjust a nominal control of a base policy (from e.g. a RL algorithm) by a control signal that can be computed from estimates of the process noise. As a main contribution, the authors present three distinct methods to compute those noise estimates.

Strengths

- Control theory provides us with many ideas that can be exploited and possibly transferred to model-free RL algorithms. Thus, I think it is important to think about how such ideas can be utilized and adapted to make RL-algorithms more reliable, sample-efficient etc. - The ideas are formally justified and the derivations appear to be mostly correct. For LDS, the authors provide convergence proofs of their method. - The paper is well structured and well written. The contributions are clearly set out and the structure of the paper allows the reader to follow along easily. - The authors provide example code for some of their experiments.

Weaknesses

- The results suggest, that PD1 produces similar results to the baseline and that PD2 was only able to really outperform its baseline on one task (noisy hopper). The only PD-estimator that consistently beat its baseline was PD3, which uses a simulator to compute the disturbance signal. Now, the question arises, whether this is still a model-free algorithm or not, since we would need this model also during inference. The paper would benefit from more evidence, that at least PD2 provides stronger performance than the baseline. Furthermore, it would be interesting to see if you could use a learned model to compute the disturbance and how this would affect performance. - In the definition of PD(1), in Line 169, the term on the right-hand side is called "gradient of a TD error.". I do not think that this is an accurate statement. Recall that the TD-Error is defined as $$c(x_t, u_t) + \gamma V_\pi(x_{t+1}) - V_\pi(x_t).$$ From the definition of $Q$ and $V$ and $\mathbf{\hat w_t}$, we can derive $$ \begin{align*} &\gamma V_\pi(f(x_t, u) + w_t) - (Q_\pi(x_t, u) - c(x_t, u)) \\ &=\gamma V_\pi(\hat x_{t+1}) - (\underbrace{c(x_t, u) + \gamma \mathbb E_{x_{t+1}}[V_\pi(x_{t+1})]}_{=Q(x_t, u)} - c(x_t, u)) \\ &= \gamma (V_\pi(\hat x_{t+1}) - \mathbb E_{x_{t+1}}[V_\pi(x_{t+1})]), \end{align*} $$ which I would not call a TD error (it does not measure the consistency of the value function over timesteps). It appears to me that it is more like a measure between the expected value of the next state and the value of the predicted next state. - In the evaluation, the plots are kind of hard to read. I would recommend to increase the font size for the axis/legend, especially for Fig. 3.

Questions

- TD-Error: (See above) - Why does PD2 not improve the performance in noisy walker and only marginally in noisy ant? - Line 173: Here the authors state that the gradient of $V_\pi$ can be efficiently estimated online. This needs more explanation in my opinion, since it is not clear how this is done and why we do not have this gradient term in equations (1) and (2). - Code: You provided code for the LDS experiments. Why not also for the robotics environments?

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

3 good

Presentation

3 good

Contribution

2 fair

Limitations

The authors did not dicsuss the limitations of their approach.

Summary

This work introduces the notion of disturbance-based policies for model-free reinforcement learning, as opposed to traditional state-based policies. The disturbances capture unmodeled deviations from observed dynamics. In the model-free setting, since these disturbances are not known to the learner, the paper proposes three signals which can be used as pseudo-disturbances. These include the gradient of the TD error, the difference between auxiliary value functions of consecutive states, and the difference between the observed state and a simulated state. These three signals each require different assumptions and have their own advantages and disadvantages. These can recover the true perturbations up to linear transformations assuming time-invariant linear dynamical systems and a linear policy. A new algorithm, MF-GPC, is introduced which can adapt existing RL methods under this framework. Notably, this approach has sublinear regret bound under certain assumptions. Experiments on noisy versions of OpenAI gym environments demonstrate the effectiveness of the proposed method.

Strengths

The paper presents a novel paradigm for model-free reinforcement learning based on unmodeled disturbances. There is an existing line of work on disturbance-based techniques which employ model-based control. However, this paper is the first work to extend this approach to the model-free setting, to the best of my knowledge. The use of various signals as pseudo-disturbances is an original idea and the three proposed variants seem sound. The mathematical guarantees that these pseudo-disturbances are linear transformations of the true disturbance for linear systems, as well as the regret bound for MF-GPC, are valuable contributions and strengthen the quality of the paper. The concepts introduced in the paper are presented with sufficient clarity.

Weaknesses

The practical applicability of the proposed framework raises some concerns. Among the three proposed pseudo-disturbances, PD3 requires an accurate simulator which is in most cases not available. PD2 can be applied to specific systems where there are additional signals available from the environment. PD1 seems to be the one most generally applicable to typical RL environments and dynamical systems, however it is unreliable and the empirical results demonstrate the ineffectiveness of this signal. See questions for detailed comments. Another consideration is that the analysis considers linear dynamical systems and the regret bounds and the guarantees require further assumptions. While such constraints are typical when performing rigorous analysis, it does raise the question of how generally applicable this framework is to various other types of systems.

Questions

1. For PD1, both the state-value and the action-value function are learned estimates. If so, calculating the pseudo-disturbances based on the error between two functions which are being learned online can be unreliable, especially in the early stages of training. This is acknowledged in the paper and the results do not offer much improvement. This is concering because among the three proposed variants, PD1 seems to be the most easily applicable to general RL setups. 2. For PD2, the experiments section mentions that the first few units of the last critic layer are used as V and Q. The reason for this choice is not clear to me, these units would not, in general, correspond to any cumulant function. An explanation from the authors would be helpful.

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

4 excellent

Presentation

3 good

Contribution

2 fair

Limitations

The paper does not address the limitations of the proposed framework. As mentioned in my review, the main limitation seems to be the usefulness of the pseudo-disturbances to generic environments and systems. In addition, the analysis is limited to linear dynamical systems, and it is not clear how this framework extends to other types of systems.

Summary

This work considers model-free RL in the setting with additive disturbances in the environments' forward dynamics. In particular, it focuses on "disturbance-based policy" which adds a correction policy to the vanilla state-based policy. Because the disturbances are unknown in model-free RL, the correction policy instead conditions on "pseudo-disturbance" which are proxies of the actual disturbance. The paper proposes and analyzes 3 pseudo-disturbances that are feasible to compute in a model-free RL setting. The main algorithm trains the disturbance-based policy in a typical model-free RL training loop and is independent of the base RL algorithm. The authors provide theoretic guarantees of the method under linear settings. Empirical results show that the algorithm brings substantial improvement in a collection of noisy control tasks.

Strengths

1. The problem setting is well-motivated and clearly formulated. 2. New concepts are nicely explained. 3. The different choices of pseudo-disturbance make sense intuitively and are well supported for their properties in the linear case. 4. Empirical results show significant benefits from the algorithm.

Weaknesses

1. The authors mention potential adversarial disturbance but empirical results are shown in environments with uniform additive noise. The paper would be stronger with experiments containing adversarial disturbances. 2. The gym experiments are done with only one baseline method. Max-entropy RL algorithms like Soft Actor-critic might be more robust to noises in the environment. I would be more convinced if the method is compared with a few more state-of-the-art methods.

Questions

This links back to weakness #2. I appreciate the fact that disturbance-based policies provide theoretic guarantees in linear settings. Does this formulation provide other benefits? How does the proposed method compare to other model-free RL methods?

Rating

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

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

The authors cover the limitation of each pseudo-disturbance. They are also upfront about PD1 not performing well in RL.

Overlooked theory contribution (new SOTA regret bounds for bandit control)

Having arrived at the end of the discussion period, we recount our contributions next. We identify three novel pseudo-disturbance signals, each occupying an incomparable region in the space of generality-performance tradeoff. We show that these can be used to train a disturbance-based policy via a new provably efficient gradient-based model-free algorithm for at-test-time adaption to unmodeled disturbances, and evaluate them empirically. We hope our responses have allayed the reviewers’ concerns, and we hope that they will consider raising their score. We would also like to take the opportunity to highlight a **core contribution** that was perhaps not as conspicuous and was missed by some reviewers. As a testament to the strength of our careful algorithm design and analysis, as stated in Line 54 of the main paper, even for the well-studied linear setting, our sub-linear guarantee is unconditionally better than best-known ones (published at NeurIPS; Cassel and Koren, and Gradu et al) in terms of its dependence on the state dimension and applicability to high-dimensional systems. Specifically, for bandit linear control, the best-known results offer a regret of $$O(\sqrt{d_xd_u d_{\min}} T^{0.75}),$$ whereas we obtain $$O(\sqrt{d_u d_{\min}} T^{0.75}),$$ where $d_x$ is the state dimension, $d_u$ is the action dimension, and $d_{\min}=\min (d_u,d_x)$. This is an unconditional (quantitative) improvement over an established line of prior work. Next, we comment on the qualitative significance of this improvement. For underactuated systems (where $d_u\leq d_x$ making these rank deficient systems harder to control), our results have no dependence on $d_x$ whatsoever; thus this algorithm is especially well suited to high dimensional state space settings. This improvement over prior work comes about due the the *correct* choice of the gradient estimator and not just an improved analysis, as we detail in Appendix E.2. (Additionally, as proved in E.2, such improvements in dimension dependence also apply to smooth losses, where the regret scales as $T^{2/3}$, unconditionally improving over an analogous result in Cassel and Koren). This is further validated empirically in Figure 3, where our method outperforms the existing state-of-the-art bandit linear control algorithm (BPC) in the high dimensional experiment. We could not adequately detail this in the main paper (we did on Line 54) due to space limitations, and due to the brunt of our focus being on the applicability and design of the pseudo-disturbance estimators. We will alter the presentation to emphasize these important contributions. **Since this is a concrete and unconditional improvement over papers published at NeurIPS, we hope that reviewers can take into account this innovation of ours in their scores.**