Online Nonstochastic Model-Free Reinforcement Learning
Authors: Udaya Ghai
Arushi Gupta
Wenhan Xia
Karan Singh
Elad Hazan
Venue: NeurIPS 2023 poster (2023)
Keywords: Control
Reinforcement Learning
Online Learning
Regret Minimization
Bandit Linear Control
TL;DR: Disturbance-based nonstochastic control policies improve model-free RL & bandit control

Abstract: We investigate robust model-free reinforcement learning algorithms designed for environments that may be dynamic or even adversarial. Traditional state-based policies often struggle to accommodate the challenges imposed by the presence of unmodeled disturbances in such settings. Moreover, optimizing linear state-based policies pose an obstacle for efficient optimization, leading to nonconvex objectives, even in benign environments like linear dynamical systems.

Drawing inspiration from recent advancements in model-based control, we intro- duce a novel class of policies centered on disturbance signals. We define several categories of these signals, which we term pseudo-disturbances, and develop corresponding policy classes based on them. We provide efficient and practical algorithms for optimizing these policies.

Next, we examine the task of online adaptation of reinforcement learning agents in the face of adversarial disturbances. Our methods seamlessly integrate with any black-box model-free approach, yielding provable regret guarantees when dealing with linear dynamics. These regret guarantees unconditionally improve the best-known results for bandit linear control in having no dependence on the state-space dimension. We evaluate our method over various standard RL benchmarks and demonstrate improved robustness.

Online Nonstochastic
Model-Free Reinforcement Learning
Udaya Ghai 1+ Amazon
Arushi Gupta f
Princeton University & Google DeepMind
ughai@amazon.com com
arushig@princeton.co
Wenhan Xia
Karan Singh
Princeton University & Google DeepMind wxia@princeton. edu
Carnegie Mellon University
karansingh@cmm. edu
Elad Hazan
Princeton University & Google DeepMind ehazan@princeton edu
Abstract
We investigate robust model-free reinforcement learning algorithms designed for environments that may be dynamic or even adversarial. Traditional state-based policies often struggle accommodate the challenges imposed by the presence of unmodeled disturbances in such settings. Moreover, optimizing linear state-based policies pose an obstacle efficient optimization, leading to nonconvex objectives, even in benign environments like linear dynamical systems.
Drawing inspiration from recent advancements in model-based control, intro- duce a novel class of policies centered on disturbance signals. We define several categories of these signals, which we term corresponding policy classes based on them. We provide efficient and practical algorithms for optimizing these policies.
and develop
Next, examine the task of online adaptation of reinforcement learning agents the face of adversarial disturbances. Our methods seamlessly integrate with any black-box model-free approach, yielding provable regret guarantees when dealing with linear dynamics. These regret guarantees unconditionally improve the best- known results for bandit linear control in having no dependence on the state-space dimension. We evaluate our method over various standard RL benchmarks and demonstrate improved robustness.
Introduction
Model-free reinforcement learning in time-varying responsive dynamical systems is a statistically and computationally challenging problem. In contrast, model based control of even unknown and changing linear dynamical systems has enjoyed recent successes. In particular, new techniques from online learning have been applied to these linear dynamical systems (LDS) within the framework of online nonstochastic control. comprehensive survey can be found in HHzan and Singh (2022). The key innovation in the aforementioned framework is the introduction of new policy class called Disturbance-Action Control (DAC), which achieves high degree of representational capacity without compromising computational efficiency. Moreover, efficient gradient- based algorithms can
WWrk performed while at Princcton University and Google. t denotes equal contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

be employed to obtain provable regret bounds for this approach. even in the presence of adversarial noise. Crucially, these methods rely on the notion of disturbance, defined to capture unmodeled deviations between the observed and nominal dynamics, and its availability to the learner.
This paper explores the potential of applying these disturbance- hasee techniques, which have proven effective in model-based control, to model-free reinforcement learning. However, it is not immediately clear how these methods can be adapted to model-free RL, as the disturbances in model-free RL unknown to the learner.
We therefore develop the following approach to this challenge: instead of relying known disturbance, we create a new family of sigmals, which we call policies that use "Pseudo-Distee Disturbance" features to produce actions. The advantage of this approach that it has the potential to produce more robust policies. Again inspired by model-based methods, aim to augment existing reinforcement learning agents with "robustness module" that serves two purposes. Firstly, it can filter out adversarial noise from the environment and improve agent performance in noisy settings. Secondly, in cases where the environment benign and simple, such as a linear dynamical system, the augmented module will achieve a provably optimal solution. We also empirically evaluate the performance of our method on OpenAl Gym environments.
and define
1.1 Our Contributions
In this work, we make the following algorithmic and methodological contributions:
In contrast to state- bastedbased policies commonly used in RL, Section defines the notion of a disturbance-based policy. These policies augment traditional RT. approaches that rely strictly on state feedback.
We develop three distinct and novel methods (Sections
3.1
3.2
3.3
to estimate the
Pseudo- Deeuuo-Disturbacce in the model-free RI. setting.
We develop new algorithm, MF-GPC (Algorithm[) [. which adapts existing RL methods to take advantage of our Diiuddd-isttrbaeeeee framework.
We empirically evaluate our method on OpenAI Gym environments Section [ We find that our adaptation applied on top of DDPG baseline performs better than the baseline, significantly so in same cases, and has better robustness characteristics.
We prove that the proposed algorithm achieves sublinear regret for linear dynamics in Theorem 4 These regret bounds improve upon the best-known for bandit linear control in terms of their dependence on state space dimension (Appendix EE. Notably, our bounds have no dependence
the state dimension, reducing the state-of-the-art regret bound by factors of ddg for convex losses and / if losses are additionally smooth, signalling that our methodology is better suited to challenging high-dimensional under-actuated settings.
1.2 Pseudo-Disturbance based RL
fundamental primitive of the non-stochastic control framework is the distarbance. In our RL setting, the system evolves according to the following equation
X = (xx, u,) + W.,
where X₁ is the state, u, is control signal, and is a bounded, potentially adversarially chosen, disturbance. Using knowledge of the dynamics, f, non-stochastic control algorithms first compute Wr, and then compute actions via DAC, as follows
u; Absse (xt) + Σ M.
Here Tows is baseline linear controller, and M are matrices, learned via gradient descent similar algorithms. For linear systems, the DAC law a convex relaxation of linear policies, which allows us to prove regret bounds against powerful policy classes using tools from online convex optimization.
To generalize this approach, without a model or knowledge of the dynamics function f, both defining and obtaining this disturbance in order to implement DAC similar policies becomes unclear. To

---

address this, we introduce the concept of a Srrudo-Distubbanee (PD) and provide three distinct variants, each representing novel signal reinforcement learning. These signals have various advantages and disadvantages depending on the available environment:
1. The first notion is based the gradient of the temporal-difference error. It assumes the availability of a value function oracle that can be evaluated or estimated online or offline using any known methodology.
2. The second notion also assumes the availability of black-box value function ora- cle/generator. We assign artificial costs over the states and generate multiple auxiliary value functions create "value vector." The Iseudo-Disturbiin ference between the value vector at consecutive states. This signal's advantage is that it does not require any zero-order optimization mechanism for estimating the value function's gradient.
is defined as the dif-
3. The third notion assumes the availability of an environment simulator. The Pseudo- Disturbance is defined as the difference between the true state and the simulated state for specific action.
For all these DistuuDbiter variants, we demonstrate how to efficiently compute them (under the appropriate assumption of either a value function oracle or simulator). We provide reduction from any RI. algorithm to a PD-based robust counterpart that converts an RI. algorithm into one that is also robust to adversarial noise. Specifically, in the special case of linear dynamical systems our algorithm has provable regret bounds. The formal description of our algorithm, as well theorem statement, are given in Section 4 For more general dynamical systems, the learning problem is provably intractable. Nonetheless, we demonstrate the efficacy of these methods empirically.
1.3 Related Work
Model-free reinforcement learning. Reinforcement learning [Sutton and Barto 2018 approaches
are classified as model-free model-based [Janner et al. 2019 Ha and Schmidhuber 201 8 Osband and Van Roy, 2014), dependent on if they attempt to explicitly try to learn the underlying transition dynamics an agent is subject to. While the latter is often more sample efficient (Wang et al. 2019),
model-free approaches scale better that their performance does not prematurely saturate and keeps improving with number of episodes (Duan et al. [016]. In this paper, we focus adaption to unknown, arbitrary disturbances for model-free reinforcement learning algorithms,, which can be viewed as tractable restriction of the challenging adversarial MDP setting [Abbasi Yadkori et al. 2013 Model-free approaches may further be divided into policy-based [Schulman et al.) 2015
2017 value-based approaches (Mnih al. 2013), and actor-critic approaches [Barth-Maron et al. 2018 Lillicrap et al. [016]; the latter use a learnt value function to reduce the variance for policy optimization.
Robust and Adaptive reinforcement learning. Motivated by minimax performance criterion in robust control (Zhang et al., 2021 Morimoto and Doya 2005) introduced to a minimax variant of Q-leariig to enhance of he robust of policies learnt from off off-policy samples. This later extended to more tractable formulations and structured uncertainty sets in Tessler et al.) [2019]. Mankowitz
al. [2019) Pinto al. [2017]. Zhang et al. [2021] Tamar et al. [2033), including introductions of model-based variants Janner et al. 2019]. Another approach to enhance the robustness is Domain Randomization (Tobin al. 2017 Akkaya al. 2019 Chen et al. 2021a]. wherein model is trained in a variety of randomized environments in a simulator, and the resulting policy becomes robust enough to be applied in the real world. Similarly, adversarial training [Mandlekar al. 2017 Vinitsky et al. 2020 Agarwal et al. [2021) has been shown to improve performance in out-of- distribution scenarios. In contrast to the previously mentioned approaches, our proposed approach only adapts the policy to observed disturbances at test time, and does not require a modification of the training procedure. This notably means that the computational cost and sample requirement of the approach matches that of vanilla RL in training, and has the benefit of leveraging recent advances mean-reward RL, which is arguably better understood and more studied. Adaption of RL agents to new and changing environments has been similarly tackled through the lens of Meta Learning and Agarwal et al.
similar approaches [Wang et al., 2016, Nagabandi et al. 2018 Pritzel et al. 2017 7
2021).
3

---

Online nonstochastic control. The presence of arbitrary disturbances during policy execution had been for long the fields of robust optimization and control [Zhou and Doyle, 1998]. In contrast to minimax objectives considered in robust control, online nonstochastic control algorithms (seel Hazzan and Singh [202] for survey) are designed to minimize regret against a benchmark policy class, and thus compete with the best policy from the said class determined posthoc. When the benchmark policy class is sufficiently expressive, this approach has the benefit of robustness against adversarially chosen disturbances (i.e. non-Gaussian and potentially adaptively chosen [Ghai et al. 202ID. while distinctly not sacrificing performance in the typical or average case. The first nonstochastic control algorithm proposed in Agarwal et al.
with sublinear regret guarantees
[2019] for linear dynamical systems. was subsequently extended to partially observed systems Simchowitz et al., 2020], unknown
systems (Hazan et al., 2020], multi--genn systems [Ghai et al. [022] and the time- tire-ngrying case
[Minasyan et al. 2021 The regret bound was improved to a logarithmic rate in Simchowitz/ (2020) for strongly convex losses. Chen et al. [0021b extend this approach to non-linearly parameterized
policy classes, like deep neural networks. Bandit versions of the nonstochastic control setting have also been studied [Gradu al., 2020 Cassel and Koren 2020 [Sun al. 2023] and are particularly
relevant to the RL setting, which only has access to scalar rewards.
1.4 Paper Outline
After some basic definitions and preliminaries in Section 2 we describe the new Pseudo-Disturbann signals and how to create them in model-free reinforcement learning environment in Section [ In Section 4 we give a unified meta-algorithm that exploits these signals and applies them as an
augmentation to any given RL agent. Section we evaluate our methods empirically.
An overview of notation can be found in Appendix A Appendix B contains additional experimental
details. Generalization of our algorithm to discrete spaces is provided in Appendix C Section 3 are provided in Appendix D while the main theore is proved in Appendix
Proofs for
2 Setting and Preliminaries
Consider an agent adaptively choosing actions in a dynamical system with adversarial cost functions. We use notation from the control literature: x, E Rd= is vector representation of the state at time t, u, E Rd is the corresponding action. Formally, the evolution the state will follow the equations
X fx,: u,) + W.,
where w, is an arbitrary (even adversarial) disturbance the system is subject to at time t. Following this evolution, the agent suffers a cost of cx Uz).
In this work, we adapt model-free reinforcement learning algorithms to this more challenging case. The (easier) typical setting for model-free methods assume, in contrast, that the disturbance w, is sampled tid from distribution D, and that the cost functions c(x, u) is fixed and known. Central to the study of model-free methods are the notions of the state and state-action value functions, defined as the discounted sum of future costs acquired by starting at any state (or state-action pair) and thereafter following the policy æ. For any policy æ, we denote the state and state-action value functions, which are mappings from state or state/action pair to the real numbers, as
Qx u) = E Σ f'((7,, uF) x x =u Vx E E
Σ x c(x] uF7) 0=0
x3
where expectations are taken over random transitions in the environment and in the policy.
special case we consider that of linear dynamical systems. In these special instances the state involves linearly according to a linear transformation parameterized by matrices A, B, i.e.
x
Ax, + Bu, + W.-
2 Although we consider continuous state and action spaces in this section and the remainder of the main paper. we handle discrete spaces in Appendix C

---

Pseudo-Disturbance Signals and Policies
In this section we describe the three different Pseudo-Disturbance (PD) signals we can record in general reinforcement learning problem. As discussed, the motivation for this signal comes from the framework of online nonstochastic control. We consider dynamical systems with an additive misspecification noise structure,
x++1 = [x,,, Uz) Wt.
where the perturbation w, does not depend on the state. Using perturbations rather than state allows us to avoid recursive structure that makes the optimization landscape challenging and nonconvex. As discussed, we introduce Pscudo-Disturbance signals w, Rd in licu of the true disturbances. We note that the PD dimensionality du need not be the same as that of the true disturbance, dg.
An important class of policies that we consider henceforth is linear in the Sraudo-Disturbance, i.e.
IDC
T(11))
Thase (xx) +
Σ 1=1
M M.wis M4 E Rd xdw
The fact that wy does not depend on our actions allows for convex optimization of linear disturbance-action controllers in the setting of linear dynamical systems, see e.g. Hazan and Singh [2022].
Here IDAC denotes the policy class of Cwwiuraannee-ction-CCCa
would like to capture the essence of this favorable phenomenon the context of model free RL, but what would replace the perturbations w, without dynamics model f? That's the central question this section, and we henceforth give three different proposal for this signal.
An important goal in constructing these signals is that in the case of linear dynamical systems, it recovers the perturbation. This will enable us to prove regret bounds in the case the environment an LDS.
3.1 Pseudo-Disturbacee Class I: Value-Function Gradients
The first signal consider is based the gradient of the value function. The value function maps the state onto a scalar, and this information is insufficient to recreate the perturbation even if the underlying environment is linear dynamical system. To exact richer signal, we thus consider the gradient of the value function with respect to the action and state. The basic goal is to implement the following equation
W. V. Vu u) + w.) - (X,, u) c(x,, u))
where f(x, u) + w, represents the counterfactual next state after playing u at state x,, Note, this signal is gradient of the temporal-difference error (Sutton and Barto 2018). in fact being syntacti- cally similar to expected SARSA. If w, was in fact (iid) stochastic with V Qa as corresponding value functions, this term expectation would be zero. Therefore, this signal on average measures deviation introduced in x due to arbitrary or adversarial w,. We can also view this expression as
(f u) w.) VV (f u))) u=
V- is quadratic in the linear quadratic regulator setting, so this becomes linear function of w.- Computing V. V=V=(((x, u) luckily this can be efficiently estimated online. Using policy æ, with noised actions u, = a axx)) ( n, for N/0 Σ) we have the following PD estimates:
we)]u=u, analytically would require knowledge of the dynamics, but
W (X - n: (x(Qu(X,, u) - c(Xe, u))lumu
W (c(x), u.) ( Qx u,)) ' ny
(2)
These are zeroth-order gradient estimators (see Liu et al.) 2020 for more detailed exposition). Intuitively, the second estimator may have lower variance the expected SARSA error can be much smaller than the magnitude of the value function. additional benefit is that this implementation only requires scalar cost signal without needing access to differentiable cost function.
5

---

The most important property of this estimator is that it, in expectation, it produces a signal that is linearly transformation of the true disturbance if the underlying setting is linear dynamical system. This is formalized in the following lemma.
Lemma Consider time-invariant linear dynamical systems with system matrices A, B and quadratic costs, along with a linear baseline policy defined by control law u, = -K, In expectation, the pseudo disturbances ① and ② are linear transformations of the actual perturbation
E[w Tw,,
where T is a fixed linear operator that depends on the system.
3.2 Pseudo-Disturbance Class II: Vector Value Functions
The second approach derives a signal from auxiliary value functions. Concretely, instead of scalar- valued cost function d - IR, consider a vector-valued cost function e Rd Rd For such vector-valued cost, we introduce vectorized value and state-action value functions as
V Rdd + Rdd Q Rd
Rdv
In particular, we have
8
2 (x, u)
xij =x, =u Vx(x) E
Σ
rx((x])
x8 =x
Our PD signal is then
W = c(x,) VV (x++1) Q (x,, uz)
In contrast to the first approach, for a fixed set of cost functions, this approach provides deterministic PD-signal. This is very beneficial, as at inference time the DAC policy can be run without injecting additional noise and without requiring a high variance stochastic signal. This does come at a cost, as this method requires simultaneous off-policy evaluation for many auxiliary value functions (each corresponding to a different scalar cost) before DAC can be run via Q-function evaluations at inference, both of which can significantly more expensive than the first approach.
For the case of linear dynamical systems, if we use linear costs on top of linear base policy, this approach can recover the disturbances up to linear transformation. can be seen that the values corresponding to a linear cost function are linear functions of the state, and hence the vectorized versions are also linear functions of state. We formalize this as follows:
Lemma 2. Consider time-invariant linear dynamical systems with system matrices A, B, along with a linear baseline policy v defined by control law u, X, Let VE and Q be value functions for π for ii.dd zero mean noise with linear costs c(x) == Læ, then the PD-signal 3 is linear transformation
W. = Twi,
where T is fixed linear operator that depends the system and baseline policy In addition, if is full rank and the closed loop dynamics are stable, then T is full rank.
3.3 "Reudo-Disturbant Class III: Simulator Based
The last Pseudo-Disse Disturbance signal we consider requires potentially inaccurate simulator. It is intuitive, particularly simple to implement, and yet comes with theoretical guarantees.
The Pseudo-Disturrance is taken to be the difference between the actual state reached in an environ- ment, and the expected state, over the randomness the environment. To compute the expected state, we require the simulator fsim initialized at the current state. Formally.
W X fsim (xim(xx, Xx, Uz).
The simplicity of this PD is accompanied by simple lemma on its characterization of the disturbance in dynamical system, even if that system is time varying, as follows,
Lemma Suppose we have simulator Ssi such that Yx, u, [IS u) [(x, u)ll S 8, then Pseudo- Psendo-Disturbance Disturbance (4) is approximately equal the actual perturbation ||w: well I 8.

---

3,4 Merits of different Pseudo-Disturbance signals
Each of the three PD signals described in this section offers something a bit different. PD3 offers the most direct disturbance signal, but comes with the requirement of simulator. If the simulator is very accurate, this likely the strongest signal, though this method may not be suitable with large sim-to-real gap. PDI and PD2 on the other hand, do not require simulator but also have a natural trade off. PD1 simpler and easier add on top of an existing policy. However, it uses zeroth-order estimation, so the guarantees only hold in expectation and it may have high variance. On the other hand, PD2 is not stochastic estimate, but it requires auxiliary value estimation from the base policy. This may come at the cost of additional space and computational complexity. In many cases, this can be handled using the same deep Q-network except with a wider head, which may not be so onerous. We note that PD2 does not require specific domain engineered signals for the auxiliary rewards. For example, using the coordinates of the state representation was enough to demonstrate improvements over baselines in experiments. For richer, higher dimensional (visual) state spaces, this can be generalized using neural representations of state as the auxiliary reward, achieved by modulating the PD2 disturbance dimension to account for the fact that the underlying dynamics are simpler.
4 Meta Algorithm and Main Theorem
In this section we define a meta-algorithn for general reinforcement learning. The algorithm takes input existing RL method, that may may not have theoretical guarantees. It adds additional layer on top, which estimates the Pseudo-Disttubances according to one of the three methods in the previous section. It then in the past Pseudo-Disturbances. This can be viewed as a zeroth-order model-free version of the Gradient Perturbation Controller (GPC) Agarwal al. 2019
online gradient method optimize linear policy
The algorithm formally defined Algorithm A typical choice of the parametrization ((- is linear function of a window of past disturbances (ie. Disturbance Action Control (Agarwal et al.
2019
Wi-1ishh
M.W--.
(5)
Algorithm MF- GPC (Model-Free Gradient Perturbation Controller)
1: Input: Memory parameter h, learning rate y), exploration noise covariance E, initialization MiA Rd xd xh initial value and Q functions, base RL algorithm A.
2: for l=ll=... 1....... T do
3: Use action u, Thase (xx) T TWW (M*) + n, where n, is iid Gaussian, i.e.
nte 2)
4: Observe state Xt+1, and cost C2
(x
5: Compute Sseudo-Disturbance [see
w, PD PD-estimate(xx+11 Uy n.).
6: Update policy parameters using the stochastic gradient estimate (see Section 4.1
M M++ M - 17 cx 4 n & J..
where @ is an outer product and Jí. = W for 5 and more generally,
J Ôn (W
M=
7: end for 8: Optionally, update the policy Tesse and its Q, V functions using A so that they are Bellman consistent, i.c. they satisfy the policy version of Bellman equation.
7

---

We prove the following theorem for the case of linear dynamics:
Theorem (Informal Statement (see Theorem 8D), If the underlying dynamics are linear with the state evolution specified
X = Ax, + Bu, + Wt,
with dmin min(dz; d then then as long as the Eseudo-Disturbann signal We satisfies W. Two for some (possibly unknown) invertible map T, Algorithm 7 generates controls us such that for any sequence of bounded (even adversarial) We such that the following holds
Ca(s,,u)
min aElLDAG
_a(x;, + dadmin
for any any sequence of convex costs where the policy class DAC refers to all policies ा that produce a control as linear function of we. Further, if the costs et are L-smooth, the regret for Algorithm 1 admits an improved upper bound of (
In particular, the above theorem implies the stated regret bounds when the Pseudo-Disture Diauddo-Ditturbacee is estimated as described Equations (attiiionns/eetttoooo (Vector Value Function-baseed and (Simulator-base))
The regret bounds in Theorem are strict improvements over wtae-offthe-es bounds in terms of dimension dependence; the latter operate with explicit descriptions of disturbances. This is achieved by using a better choice of gradient estimator, using exploration in action-space rather than parameter- space. As a result, our bounds have no dependence on the state dimension since dmai S du As an instructive case, for high-dimensional underactuated systems, where d, < dg. our regret bounds
scale as 3/447% in contrast (dd /223//44 for convex costs from [Gradu al. 2020 Cassel
and Koren, 2020 and as (dd2/312// for smooth costs improving over (dd di (12/3) from [Cassel and Koren 2020). Note that the ratio by which we improve here can be unbounded, with larger improvements for high-dimensional (d, > 1) systems. See Appendix E.2 for further details, comparisons and proofs.
4.1 Derivation of update
In the algorithm, the key component is computing an approximate policy gradient of the cost. A complete theoretical analysis of our algorithm can be found in Appendix [.. but we provide brief sketch of the gradient calculation. Let Je( denote the expected counterfactual cost c, of following policy M with the same observed disturbances Wt- We first note that if the dynamics suitably stabilized (which should be done by Tbase). the state and cost can be approximated as function C of small window of previous controls.
(M) Em... e [Ce (x." uu(") IC D..... ( D(-1)],
where (+M) shorthand for π (W--i-ia---- MM) The expression here is that of Gaussian smoothed function, which allows us to get the following unbiased single point gradient estimate
Vu, Em... + n...... - + n1 n1-1)) En. his E CCu + nr 4 + n--A)n
We use single sample to get a stochastic gradient. Using the chain rule, which involves an outer product due to the tensor structure of M, we get stochastic gradients with respect to M as follows
Om -
(M) Re Clu((M) + .r..... (M) + n
n
9M
t=0
Finally, we note that M is slowly moving because of gradient descent, approximate
cx(x, u.) = C(u((M') + n...... u--((M") + +n-hn)
Putting everything together, we have
θr(w, (-
VirJ(MM) M-M
x cx(xi, uz) 3
nr-
(6)
2M
1=0
M=

---

Episode Return Noisy Hopper
Episode Return Naisy Walker
Episade Return Noisy Ant
304
espisode return
348-
espisode return
espisode return
200
28-
08
18
100
Steps
14r
steps
301
steps
Episode Return for PD3 Noisy Hopper
Episode Return for PD3 Naisy Walker
Episode Return for PD3 Noisy Ant
x--
esplsode return
espisode return
espisode return
130
15
04
Steps
steps
steps
Figure 1: Episode return for best performing MF-GPC model versus best performing baseline DDPG model for various OpenAl Gym environments and pseudo-estimation methods. Environment and pseudo-estimation method shown in title. Results averaged over 25 seeds. Shaded areas represent confidence intervals. We find that PD2 and PD3 perform well in these settings.
5 Experiments
We apply the MF-GPC Algorithm to various OpenAl Gym [Brockman et al., 2016) environments. We conduct our experiments in the research-first modular framework Acme [Hoffman et al. [2020]. We pick h = 5 and use the DDPG algorithm (Lillicrap et al. 2016 as our underlying baseline. We update the M matrices every 3 episodes instead of continuously to reduce runtime. We also apply weight decay to line 6 of Algorithm α Our implementation of PDJ is based on Equation 2 PD2 can be implemented with any vector of rewards. We choose linear function L given in Lemma 2 to be the identity function. Hence in reduces to the state Ty itself. We pick V and Q network architectures to be the first d2 units of the last layer of the critic network architecture. We train for 1e7 steps as a default (this is also the default in the Acme code) and if performance has not converged we extend to 1.5e7 steps. Because the M matrices impact the exploration of the algorithm, we tune the exploration parameter a for both DDPG and MF-GPC. For the baseline DDPG, we typically explore o E {0.15, 0.2, 0.25). More experimental details may be found in Appendix Section B
Results for Noisy Hopper, Walker 2D, and Ant We create a noisy Hopper, Walker 2D, and Ant environments by adding a Uniform random variable U[-0.1, 0.1] to the state. The noise is added at every step for both the DDPG baseline and our MF-GPC. We plot the results for PD2, and PD3 in Figure We find that PD2 and PD3 perform relatively well in these settings. Graphs depicting all runs for different are available in Appendix Section B. MF-GPC is not guaranteed improve performance in realistic RI settings. We find that generally PD1 does not perform well e.g. in Figure a) and some examples where applying yields performance similar to baseline are given in Appendix Section B This is likely due to the high variance of the PD estimate. We find that neither our method nor the baseline is too sensitive our hyper-parameter tuning (Figure 2 because we start with the default Acme parameters which are already well tuned for the noiseless environment.
b) ), possibly
Linear Dynamical Systems We evaluate our methods on both low dimensional (d, = 2, du 1) and a higher dimensional (dz 10, d, = 5) linear systems with sinusoidal disturbances to demonstrate the improvements in dimension of our method (labeled RBPC) over BPC [Gradu et al. 2020). We use the full information GPC (Agarwal et al. 2019) and LQR as baselines using implementations from Gradu et al. [202T]. While performance is comparable to BPC on the small system, the larger system, BPC could not be tuned to learn while RBPC improves upon the LQR

---

Episode Return Naisy Hopper
Episode
Noisy
espisode return
e5plsode return
steps
Figure 2: Left: Episode return for PDI for Noisy Hopper. We find that PDI is not effective for RL settings. Right: Syper-parament search for PD3 on Noisy Walker. We find that neither Meta-GPC nor the baseline DDPG algorithm is too sensitive to tuning.
100
Figure 3: Comparison on low dimensional (left) vs high dimensional (rights) LDS.
baseline (see Figure 3). In both experiments, h and the learning rate and exploration noise is tuned.
Conclusion
We have described a new approach for model-free RL based recent exciting advancements model based online control. Instead of using state-based policies, online nonstochastic control proposes the use of disturbance-basee possible signals, called Pseudo-Disttrrances each with its own merits and limitations. We give generic (adaptable) REINFORCE-
policies. To create disturbance signal without a model, we define three
method using the PD signals with provable guarantees: the underlying MDP is linear dynamical system, recover and improve the strong guarantees of online nonstochastic control. Preliminary promising experimental results are discussed. We believe this is first step in the exciting direction of applying tried-and-tested model-based control techniques for general reinforcement learning.
Acknowledgments and Disclosure of Funding
Elad Hazan acknowledges funding from the ONR award N000142312156, the NSF award 2134040, and Open Philanthropy.
References
Yasin Abbasi Yadkori, Peter Bartlett, Varun Kanade, Yevgeny Seldin, and Csaba Szepesvári. Online learning in markov decision processes with adversarially chosen transition probability distributions. Advances in neural information processing systems, 26, 2013.
Naman Agarwal, Brian Bullins, Elad Hazan, Sham Kakade, and Karan Singh. Online control with adversarial disturbances. In International Conference on Machine Learning, pages 11 111-119. PMLR, 2019.
Naman Agarwal, Elad Hazan, Anirudha Majumdar, and Karan Singh. A regret minimization approach to iterative learning control. International Conference on Machine Learning, pages 100-109. PMLR, 2021.
10

---

Ilge Akkaya, Marcin Andrychowicz, Maciek Chociej, Mateusz Litwin, Bob McGrew, Arthur Petron, Alex Paino, Matthias Plappert, Glenn Powell, Raphael Ribas, et al. Solving rubik's cube with robot hand. arXiv preprint arXiv: / 13, 2019.
Gabriel Barth-Maron, Matthew W Hoffman, David Budden, Will Dabney, Dan Horgan, Dhruva Tb, Alistair Muldal, Nicolas Heess, and Timothy Lillicrap. Distributed distributional deterministic policy gradients. arXiv preprint
2018.
Dimitri Bertsekas. Dynamic programming and optimal control: Volume volume 2012.
Athena scientific,
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. CoRR, abs/ a0s/1106001140, 2016. http:://///a wrw.iiiwworraaooee org/aba//////aaaoo
0656.
Asaf Cassel and Tomer Koren. Bandit linear control. Advances Neural Information Processing Systems, 33:8872-8882, 2020.
Asaf Cassel, Alon Cohen, and Tomer Koren. Rate-optimal online convex optimization in adaptive linear control. arXiv e-prints, pages arXiv-2206, 2022.
Xiaoyu Chen, Jiachen Hu, Chi Jin, Lihong Li, and Liwei Wang. Understanding domain randomization for sim-to-real transfer. arXiv preprint arXiv:2110.03239, 2021a.
Xinyi Chen, Edgar Minasyan, Jason Lee, and Elad Hazan. Provable regret bounds for deep online learning and control. arXiv preprint arXiv:2110.07807, 2021b.
Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep reinforcement learning for continuous control. In International conference machine learning. pages 1329-1338. PMLR, 2016.
Udaya Ghai, David Snyder, Anirudha Majumdar, and Elad Hazan. Generating adversarial disturbances for controller verification. In Ali Jadbabaie, John Lygeros, George J. Pappas, Pablo A. Parrilo, Benjamin Recht, Claire J. Tomlin, and Melanie N. Zeilinger, editors, Proceedings of the 3rd Conference on Learning for Dynamics and Control, volume 144 of Proceedings of Machine Learning Research, pages 1922-1204. PMLR, 07 08 June 2021.
Udaya Ghai, Udari Madhushani, Naomi Leonard, and Elad Hazan. A regret minimization approach to multi-agent control. In International Conference on Machine Learning, pages 7422-7434. PMIR, 2022.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:141..6577 2014.
Paula Gradu, John Hallman, and Elad Hazan. Non-stochastic control with bandit feedback. Advances in Neural Information Processing Systems, 13:10764-10774, 2020.
Paula Gradu, John Hallman, Daniel Suo, Alex Yu, Naman Agarwal, Udaya Ghai, Karan Singh, Cyril Zhang, Anirudha Majumdar, and Elad Hazan. Deluca-a differentiable control library: Environments, methods, and benchmarking. arXiv preprint arXiv:2102.09968 2021.
David Ha and Jürgen Schmidhuber. World models. arXiv preprini 1803. 2018.
Elad Hazan and Karan Singh. Introduction to online nonstochastic control. arXiv preprint arXiv:2211.09619 2022.
Elad Hazan, Sham Kakade, and Karan Singh. The nonstochasticc control problem. In Algorithmic Learning Theory, pages 408-421. PMLR, 2020.
Elad Hazan et Introduction to online convex optimization. Foundations and Trends Optimiza- tion, 2(3-4):157-325 2016.

---

Matthew W Hoffman, Bobak Shahriari, John Aslanides, Gabriel Barth-Maron, Nikola Momchev, Danila Sinopalnikov, Piotr Starccykk Sabela Ramos, Anton Raichuk, Damien Vincent, al. Acme: A research framework for distributed reinforcement learning. arXiv preprint arXiv:2006.00979 2020.
Michael Janner, Justin Fu, Marvin Zhang, and Sergey Levine. When to trust your model: Model-based policy optimization. Advances in neural information processing systems, 32, 2019.
Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra, Continuous control with deep reinforcement learning. ICLR, 2016.
Sijia Liu, Pin-Ye Yu Chen, Bhavya Kailkhura, Gaoyuan Zhang, Alfred O Hero III, and Pramod Varshney. A primer zeroth-order optimization in signal processing and machine learning: Principals, recent advances, and applications. IEEE Signal Processing Magazine, 37(5):33554, 2020.
Ajay Mandlekar, Yuke Zhu, Animesh Garg, Li Fei-Fei, and Silvio Savarese. Adversarially robust policy learning: Active construction of physically-plausine perturbations. In 20/7 IEEE/RS/ International Conference on Intelligent Robots and Systems (IROS), pages 3932-3939, IEEE, 2017.
Daniel Mankowitz, Nir Levine, Rae Jeong, Yuanyuan Shi, Jackie Kay, Abbas Abdolmaleki, Jost To- bias Springenberg, Timothy Mann, Todd Hester, and Martin Riedmiller. Robust reinforcement learning for continuous control with model misspecification. arXiv preprint arXiv:1906.000 1906.0756,, 2019.
Edgar Minasyan, Paula Gradu, Max Simchowitz, and Elad Hazan. Online control of unknown time- varying dynamical systems. Advances in Neural Information Processing Systems, 34: 15944- 2021.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013.
Jun Morimoto and Kenji Doya. Robust reinforcement learning. Neural computation, 17(2)3335-359 2005.
Anusha Nagabandi, Ignasi Clavera, Simin Liu, Ronald S Fearing, Pieter Abbeel, Sergey Levine, and Chelsea Finn. Learning to adapt in dynamic, real-world environments through meta-reinforcemmnt learning. arXiv preprint 1803 2018.
Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. Advances in Neural Information Processing Systems, 27, 2014.
Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforce- ment learning. In International Conference on Machine Learning, pages 2817-2826. PMLR, 2017.
Alexander Pritzel, Benigno Uria, Sriram Srinivasan, Adria Puigdomenech Badia, Oriol Vinyals, Demis Hassabis, Daan Wierstra, and Charles Blundell. Neural episodic control. In International conference on machine learning, pages 2827-2836. PMLR, 2017.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889-1897. PMLR, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint 17Xivv1707.06347, 2017.
Max Simchowitz. Making non-stochastic control (almost) as easy as stochastic, Advances Neural Information Processing Systems, 33:18318-1832) 2020.
12

---

Max Simchowitz, Karan Singh, and Elad Hazan. Improper learning for non non-stochastic control. In Conference on Learning Theory, pages 3320-3436. PMLR, 2020.
Y. Jennifer Sun, Stephen Newman, and Elad Hazan. Optimal rates for bandit nonstochastic control. arXiv preprint arXiv:2305. /3352, 2023.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Aviv Tamar, Huan Xu, and Shie Mannor. Scaling up robust mdps by reinforcement learning. arXiv preprint arXiv:13000 1336.61666 (89,,666899000 2013.
Chen Tessler, Yonathan Efroni, and Shie Mannor. Action robust reinforcement learning and applica- tions in continuous control. In International Conference on Machine Learning, pages 6215 6215-6224.
PMLR, 2019.
Josh Tobin, Rachel Fong, Alex Ray, Jonas Schneider, Wojciech Zaremba, and Pieter Abbeel. Domain randomization for transferring deep neural networks from simulation to the real world. 2017 IEEE/RSJ international conference intelligent robots and systems (IROS), pages 23-30. IEEE, 2017.
Eugene Vinitsky, Yuqing Du, Kanaad Parvate, Kathy Jang, Pieter Abbeel, and Alexandre Bayen. Robust reinforcement learning using adversarial populations. arXiv preprint arXiv:2008.01 01825. 2020.
Jane X Wang, Zeb Kurth-Nelson, Dhruva Tirumala, Hubert Soyer, Joel Z Leibo, Remi Munos, Charles Blundell, Dharshan Kumaran, and Matt Botvinick. Learning reinforcement learn. arXiv preprint 1rX55:161..05763, 2016.
Tingwu Wang, Xuchan Bao, Ignasi Clavera, Jerrick Hoang, Yeming Wen, Eric Langlois, Shunshi Zhang, Guodong Zhang, Pieter Abbeel, and Jimmy Ba. Benchmarking model-based reinforcement learning. arXiv preprint arXiv:1907.0205: 2019.
Huan Zhang, Hongge Chen, Duane Boning, and Cho-Jui Hsich. Robust reinforcement learning state observations with learned optimal adversary. arXiv preprint 1xXiv:2/01.08452 2021.
Kemin Zhou and John Comstock Doyle. Essentials of robust control, volume 104, Prentice hall Upper Saddle River, NJ, 1998.
13

---

Contents
Introduction
1.1
Our Contributions
1.2
Pseudo-Disturbann based RL
1.3
Related Work
Paper Outline
2
Setting and Preliminaries
3
Pseudo-Disturaane" Signals and Policies
3.1
Pseudo Pseudo-Disturbance Disturbance Class I: Valuc-Function Gradients
3.2
Pseudo- Dieuro-Disturaacce Class II: Vector Value Functions
6
Deetuo-Ditturbance Class III: Simulator Based
3,4
Merits of different Pscudo-Disturbance signals
Meta Algorithm and Main Theorem
4.1
Derivation update
5
Experiments
Conclusion
10
Notation
15
Experiments
15
B.1 Hopper
15
B.2 Noisy Hopper
16
B.3 Noisy Walker 2D and Ant
16
B.4 Experiments with ad advesraiial noise
17
Discrete State and Action Spaces
18
D Pseudo-Disturbanm Proofs
18
D. Proof of Lemmal
18
D.2 Proof of Lemma
19
D.3 Proof of Lemmal
20
Main Result and Dimension-efficien Bandit GPC
20
Main Result
20
Dimension Efficient Bandit GPC
20
Idealized Cost and Proof of Theorem 9
22
Proof of Supporting Claims
24
14

---

A Notation
We use the following notation consistently throughout the paper:
Symbol
Semantics
outer product
dynamics/transition function
Jsim dz
simulator dynamics/transition function
state dimension control dimension
du
d
pseudo-disturbance min(dgs du)
dmin
X2 Rd
state time control at time t
u, Rd
W; E Rd
perturbation (disturbance) at time & instantaneous cost at time pseudo-disturbance time
C
W: Rd
n, Rd
Gaussian exploration noise at time system matrices for linear dynamical system history length (i.e., number of parameters) in a policy class h-length sequence of matrices used by MF-GPC at time t policy class of h-length matrices discount factor
A, B,C
h
M
M
V, Qx
state and state-action value functions for vectorized value and Q functions for for reward vectors r(x: idealized state
VE. Or
V
C
stationary idealized cost (function of single MM) time non-stationary idealized cost (function of memory) at time Smoothed Ct using noised controls idealized cost as function of last controls at time smoothed
C
C2,8
FI
spectral norm Frobenius norm
Experiments
We test the performance of method various OpenAl Gym environments. We conduct experiments in the research-first modular framework Acme [Hoffman et al. 2020). We pick = and the DDPG algorithm [Lillicrap et al. 2016) underlying baseline. We update the M matrices every episodes instead of continuously to reduce runtime. We also apply weight decay to line 6 of Algorithm [
Our implementation is based on the Acme implementation D4PG. The policy and critic networks both have the default sizes of 256 x 256 256. We use the Acme default number of atoms as 51 for the network. We run the distributed setting with agents. The underlying learning rate of the D4PG implementation is left 3e 04. The exploration parameter, o is tuned.
Plotting We use a domain invariant exponential smoother with small smoothing parameter of 0.1 The smoothing is applied before the mean is taken over the data. To construct the confidence intervals, we take the following steps smooth the data 2) linearly interpolate each run of the data to produce a fine grid of values 3) calculate a VN on interpolated data.
B.1 Hopper
The OpenAl Gym Hopper environment a two dimensional one legged figure that consists of four body parts, namely torso, thigh, leg and foot.
15

---

basarncd
basernce
tazainod
basonnce -
recum
Steos
STE05
51635
50635
(a)
(b)
(c)
(d)
Meta--GPCo i
Meta-GPCo
wwwe pwwpeeeeeeeeeeeeeeeeee seburr
www Leter wwwpeeecceeee loplecie returrs
steps
steps
steps
steps
(c)
(f)
(g)
(h)
Figure 4: Raw data for PD Estimate 1 on Hopper. Each plot represents either the baseline or our method for different setting of the exploration parameter, o. We find that there are some outlier runs (for example the horizontal line in subfig f). We remove the two lowest return runs from each group before plotting.
B.2 Noisy Hopper
We create a Noisy Hopper environment by adding Uniform random variable U/-0.1 0.1] to qpos during training and evaluation. The noise is added every step, and both DDPG and MF-GPC evaluated on the same noisy environment.
PD1 We implement PDI for Noisy Hopper according to Equation 2 We see our results in Figure in the first column. We tune a for the D4PG baseline in the set {0.1, 0.15, 0.2, 0.25, 0.3}. We find that the = 0.1 performs the best. We tune for MF-GPC in the set 10.1, 0.15, 0.2]. We find that the o = 0.1 setting performs the best. We averaged our results over 25 seeds. Solid line represents the mean return over all runs and shaded areas represent standard error. We find that MF-GPC run with PD-1 has a small advantage compared to the DDPG baseline on Noisy Hopper. Removing outliers for PD1 for this specific experiment, when plotting, we remove the lowest runs across all groups (of both the baseline and our method). Complete raw data (with outliers included) can be in Figure
notice that some runs
be outliers. Therefore,
PD-2 PD2 can be implemented with any vector of rewards. We choose linear function L given in Lemma
2 to be the identity function. Hence in Equation reducees to the state x, itself. We pick V and Q to be the first dg units the last layer of the critic network. If d, is larger than the number of atoms of the critic network (51) we take all 51 nodes from the critic network. We find that default o = 0.15 performs well for MF-GPC so we do not tune a further.
PD-3 In practice the expectation in Equation Sisoom//reee requiies estimation. We use an average over 4 copies of the environment for this estimation.
B.3 Noisy Walker 2D and Ant
We follow the basic procedure for Hopper but train for 15 million steps instead 10 million. We report our results for the hyper-parameter sweeps in columns and of Figure We find that PD2 and PD3 perform relatively well in these settings.
PD-2 PD2 can be implemented with any vector of rewards. We choose linear function L given in Lemma to be identity function. Hence e Equation reduces to the state x, itself. Recall that d, is the dimension of the state space. We pick V and Q to be the first d, units of the last layer of the critic network. If d, is larger than the number of atoms of the critic network (51) we take all 51 nodes from the critic network.
16

---

Eaicode Return for PO2 on Nalsy Hoppar
Episode Return for FD2 Nolsy Walker
Episode Retum for PO2 on Notay Ant
esplodde return
0c20pode
Stops
stegs
steps
Eoisade Return PD3 Noisy Hosper
Episode Return for PD3 Noisy Walker
Episode Return for PO3 Noisy Ant
esplsade return
espited
Sleps
SEeDs
Figure 5: Episode return for best performing MF-GPC model versus best performing baseline DDPG model for various OpenAl Gym environments and pseudo-estimation methods. Environment and pseudo-estimation method shown title. Results averaged over 25 seeds. Shaded areas represent confidence intervals. We find that PD2 and PD3 perform well in these settings.
Episode Return for PD1 Noisy Hopper
Episode Return for PD1 Noisy HalfCheetah
return
espisode return
HE-G
8000
avaluator/es
40-
Daselnso 122
2030
Demelne:-oo 0.15
22-
steps
steps
Figure 6: Left: Episode return for PDI for Noisy Hopper. Right: Episode return for PD1 for Noisy Half Cheetah. We find that PDI not effective for RL settings.
PD-3 In practice the expectation in Equation 4 requires estimation. We use average over copies of the environment for this estimation. For Noisy Ant, we find that a default a = 0.15 performs well for MF-GPC do not tune further.
B.4 Experiments with adversarial noise
We run MF-GPC on top of DDPG baseline for the inverted pendulum environment with 1) fast gradient sign method noise [Goodfellow et al.) 2014] and 2) noise from a discretized sinusoid. We plot our results in Figure 7
Phed
Figure 7: Results from our method on the inverted pendulum environment for fast gradient sign method noise and sinusoid noise.
17

---

C Discrete State and Action Spaces
In this section, we consider differentiable parameterized random policies. For finite action space U let A {p: 4 + [0, Ene p(a) } be the probability simplex over U. Our policies, will be parameterized by M and depend on a window of past Pseudo-disturbances, providing the following distribution over actions.
7--lWi1--- M) E A"
The baseline policy, would be built into ग in this setting. For example, we could have a softmax neural net policy, and our algorithm adds residual correction the logits.
Implementation of PD signals in discrete spaces For discrete spaces, PD-2 defined via 3 is well defined, as we can still create auxiliary Q functions in the discrete space to produce our signal. Because, we no longer use Gaussian noise, PD-1 (2) can be modified follows:
W (c(x,, u.) + VV - Qn (x, u.)
VM VM
M)) M=M,
(8)
For our zeroth order gradient, use the REINFORCE:
Algorithm 2 DMF-GPC (Discrete Model-Free Gradient Perturbation Controller)
1: Input: Memory parameter h, learning rate 7), initialization M initial value and Q functions, base RL algorithm A.
2: for /= 1= do
3:
Sample action u, -
4: Observe state Xt+1, and cost C.
Cs (Xe. Uz).
5: Compute Pseudo-Disturbanee [see
W. PD esteemmtteexxx-1.. Xt, Uc ct)-
6: Update policy parameters using the stochastic gradient estimate
h-1
M + M - 17 ce up
VM
M
end for
8: Optionally, update the baseline policy parameters and its Q, V functions using A so that they are Bellman consistent, i.e. they satisfy the policy version of Bellman equation.
D Pseudo-Disturbance Proofs
In this appendix, we have the deferred proofs from Section For convenience, the lemmas have also been restated.
D.1 Proof of Lemmal 1
Lemma S. time-invariant linear dynamical systems with system matrices A, B and quadratic costs. in expectation, the pseudo disturbances and (2) is linear transformation of the actual perturbation
E[W,|x]] T Tw,,
where T is a fixed linear operator that depends on the system.
Proof. Recall from the theory of the linear quadratic regulator that the value function of an infinite horizon LDS is quadratic Bertsekas 2012),
V(x) x Px.
18

---

Thus,
VVV,(Q(X,, u) - -x,,, u)) = 1E P(Ax: + But)]
= =E1y P(Ax: + (T(())) Bn,)]
= =yB' P(Ax, + BT(xx)).
By the definition of signal, we have that
E [x, (>x++V nn Vu(Q(x;, u) c(x,, u)mlu BB' P(Ax, BT (x:)).
> (x(+1)=~~
Writing the quadratic value function also to the first term, and denoting ||x1| x Px, we have that
Ax = E 'En,n,,, [ P(Ax, + BT(x,) + w.)
Ax + (T(()) W. + Bn, 1| 1|pE--nn |
= B P(Ax, + BT(x)) + w.)
We thus conclude,
[[Wr|xx]] >VIV (x++1) (2+41)2-144 nx(x 7B3 P(Ax, + BT(x)))
=7B P(Ax: Bx(x) W:) wi) -B² P(Axi + BT(x:))
=7B Pw, -Tw.
needed.
D.2 Proof of Lemma 2
Lemma 6. Consider a line-invarian linear dynamical systems with system matrices A, B, along with a linear baseline policy x defined by control law U, -K, Let Ve and Qf be value functions for n for ii.d. zero mean noise with linear costs c(x) == Lx, then the PD-signal is linear transformation
where T is fixed linear operator that depends the system and baseline policy In addition, if L is full rank and the closed loop dynamics are stable, then T is full rank.
Proof. We first note that for linear rewards, value functions for i.i.d. the value functions without noise. As such, we have the identity
noise equivalent
Q (x,, u.) c(x) + + V (Ax; + Buj).
and so, we can rewrite or PD-signal as
w. (x(((+1) V (Ax, + Bu,)
(A + Bu, + w.) (Ax + But)
Now, it remains to show that Ve fixed linear transformation. Indeed, we have
(= = Σ ('((()))
Σ
L' =
t=
t=0
where A, A BKg is the closed loop dynamics matrix. We now have
w, (A + Bu, + w.) - (4 + Bu.) L(1 - -(1-7A,) [(Ax; + Bu, w.) (Ax: + Bu))
ILT - Wt
Now, stability of क dictates (A->A,) is full rank (even for 7 1), so if L full rank, L(I -7Aa) full rank.
19

---

D.3 Proof of Lemma!
Lemma 7. Suppose we have simulator Ssim such that Vx, u, |IS (x, u) [(x, u)l S then
(4) is approximately equal to the actual perturbation [W: well S 8.
Proof.
This Lemma immediate from the definition of the dynamics as X;-1 f(x,, u,) + We-
E Main Result and Dimensionnefficient Bandit GPC
Below, we formally state and prove the main result. Subsequent sections attest to the fact that this regret bound is an unconditional improvement over the best known Gradu et al. (2020) Cassel and Koren [2000] in terms its dependence on dimension and applicability to high-dimensional systems, even for the well-studied setting of linear control.
E.1
Main Result
9 which we state and prove in subsequent sections, we can prove the main result. Theorem 8. Consider a modification of Algorithm iimllmented using We in place of w, and choose the step size as v T and the exploration radius as ddndd
Using Theorem
If the underlying dynamics are linear and satisfy the assumptions in Section E then then as long as the Eveudo-Disturbun signal We satisfies We w for some (possibly unknown) invertible map T, with such that for any sequence of bounded (even adversarial) such that the following holds
Ee((xe,))) uz)
inf
Eei(x u s S Poly -
3/13
MEM
for any any sequence of convex costs Further, if the costs are L-smooth, the regret can be improved upper bound of
Σ Ex(xx.u)) inf MEM
E u,²) s (DD
Proof. This follows from that fact that an invertible linear transformation T of w, does not change the expressiveness of DAC policy class M except through constants related to the specifically, given a DAC policy MI.k that acts on true disturbances w.. the same exact controls are produced by DAC policy M' with MM M,T-1 acting on w. Tw.. The disturbances are also scaled by T. by As such, we can attain equivalent regret bounds with a new policy class M' with diameter scaled by ||T-||| and new bound on disturbances W" W In Theorem 9 the hidden dependence on the DAC diameter and disturbance size are polynomial, yielding at most (oly(I]T [|| scaling in the regret.
of T. More
E.2 Cimension-Effficie Bandit GPC
Under bandit feedback, the learner can only observe the cost it incurs, and does not have access function value oracles or gradients of the cost functions. This setting has been studied detail in linear control subject to adversarial disturbances using both dynamic and static regret settings; restrict our attention to the latter.
A key characteristic of our proposed algorithm is that it performs exploration in the action space, rather than the policy space. This enables us to obtain favorable trade-off between the quality of the proxy of the gradient and the amount of modification the objective (via randomized smoothing) is subject to. Leveraging this property, we show that our approach obtains a better regret bound than the best known [Cassel and Koren 2020 Gradu et al. 2020 in the literature. In particular, the best known regret bounds for this setting scale as d,,.d regret bound of ((ddddmi,733/ This is both quantitative and qualitative improvement, and carries over to the case of smooth costs too. In particular, since our bound no dependence on de whatsoever, it is equally applicable the figh-dimensiooal setting (d, > 1), which existing
In contrast, we offer
20

---

methodologies fail to scale to in the bandit setting. We stress that this improvement in the upper bound stems from the right algorithm design, and not just a tighter analysis.
In this section, we analyze Algorithm 3 a minimally modified version of Algorithm 1. which uses delayed gradient updates. As convention, hold w, for t < O when defining DAC policies in early rounds.
Algorithm 3 Bandit GPC
1: Input: Memory parameter h, learning rate 17, exploration size 6, initialization Mi.. Rd.xdxxh, and convex policy set M.
2: for 1= T do
3: Use action u, = Σ/ MfW + ôn, where n, is drawn iid from sphere uniformly i.e.
nr Uni.(
4: Observe state X(+1+ and cost c c (X uz).
5: Store the stochastic gradient estimate
dxci(x,, Up
h-1
Σ 1=0
n @
We-i-lit-i-h
6: Update using delayed gradient with euclidean projection onto M
M
II [M v/
7: end for
We make the following assumptions pertaining to costs and linear dynamics:
1. The underlying dynamics assumed to be time-invariant and linear, i.e.
Xx+1 Ax, + Bu, W1.
where Xx, W, E Rd,, u, Rd,, ||w S W and [[ S k.
2. The linear system is (1s, -t-oongyll stable: 3Q, T. such that
A= QLQ
where 1Q- < K, ||| S 1
3. The vinevnarying online cost functions cx(x,, Uz) convex and satisfy for all |x]] ||u|| < that
Co (x, < C maxx (D2, 1},, and |V,,,x, u) / u)ll < G (ma
4. We define our comparator set M .M ... x M₁ where
M. {M E [Rd. || S 2x (1 - (1)))
as in Cassel and Koren 2020 Let dmni = min(d2,
The second assumption may be relaxed to that of stabilizability, the case when the linear system by itself might be unstable, however the learner is provided with suboptimal linear controller Ko such that A + BK, (K, a)) -sstrooygly stable, via blackbox reduction outlined in Proposition (Appendix A) in Cassel et al. 2002].
Theorem 9. Choosing the step size as 17
L T
3/4 and the exploration radius as =
dd the regret of Algorithm iis upper bounded as
T inf MEM
RAgret(A) E Σ cx ui)
ui)
Σ
CxM ( d(
Furthermore, if the costs C2 is L-smooth, then choosing 2//3/ (2//3/2// the regret incurred by the algorithm admits an tighter upper bound of
(dudmin) 1 11/3--1/6 .n
Regret(A))
Σ cx(x:, u.)
inf MEM
Σ
cx
M u < T((dndmmnnT)) 2/3).
21

---

E.3
Idealized Cost and Proof of Theorem
We will prove our result by creating proxy loss with memory which accurately estimates the cost, showing that our update provides a low bias gradient estimate with suitably small variance. This will allow us prove regret bound on our proxy-lossee which we then translate regret bound on the policy itself.
Following (Agarwal al. 2019 Cassel and Koren, 2020], introduce transfer matrix that describes the effect of recent disturbances on the state.
Definition 10. For any
2h, define the disturbance-stee transfer matrix Let
L (,(Miin) A'lis +
A'M W 1+1
==1
We can also create a transfer matrix for the effect of injected noise in the control on the state: Definition 11. The noise transfer matrix is defined as + = A B.
We have the following representation of the state
2h
h-1 1
X = A
+
V
(M 1:h
W
(9)
We are also interested in counterfactual state trajectories using non-stationary DAC policies. In particular, we have Definition 12. The idealized state using policies M is defined
24
V. (M Wi-
1sh
Similarly, the idealized cost is defined as
C.(M = (Mrii)))) SMAwe-
The univariate generalization of the idealized state and cost are
(c(M) = y1 M, M....M.. C.(M) =
times
We also define (u = a ( A'BBu, + wi-1-i), un) representing the instantaneous cost as function of the last controls.
We note that
C.(M) F.
Maw h3 Σ Mew
Σ Maw---i)
We now define a smoothed version of Fr, Fis and smoothed version of C₁ Õr, that uses Fis-
(u)(() Enighwaa. [F + +dn
h-1 M
h-1
h-1
CMs(MM Fesl
M
Maw--ii)
1=0
200
We also use the following notation for idealized costs fixing a realization of the exploration noise:
C.(M[mna))
Fe.s(
M,W ni.
MW + n2.
MaW + na)
22

---

Since å = o(1), the contribution to the state space is negligible, we can use bounds from Definition of [Cassel and Koren 2020). In particular, we will use
h T)) Da.. - max W 1),
(10)
Proof of Theorem 9 policy online.
First, we state bound on how large the states can get when modifying DAC
Lemma 13. Suppose controls are played according to u, =E= Mfw, + on, where n, Sd.
and 6 = o(1), then
1. |xell ||ua|l S Da., and (x,, uz) S CD2 a,M
2. Let MM ut correspond to the counterfactual trajectory, playing DAC with parameter M for all time, then lce(x;" ) Cx(M)) <
GD²
GD2
3. (xx,, ue) C. 4t D &
The next lemma quantifies both the degree to which idcalized notion of cost tracks the true cost incurred for a DAC policy, and the resultant quality of gradient estimates thus obtained.
Lemma 14. For all t, Ce,5 is convex and
2nd h N 2.3
[[V.,s(M') 1Vlilll 5
for all E M,
(C, C.(M) < 8hGD
We begin by observing that for any & using Lemma 13 3 and the second part of Lemma [4 we have
1x=(xx", u," (M) < GD 8hGDD a.
analogous result on the difference between and idealized costs is stated below, but this time for the online algorithm itself which employs changing sequence of DAC policies.
Lemma 15.
GD2 2.a
(x,, un)
W
Similarly, we have using Lemma 15 for any & that
GD2
(xe(xes u.) (M,((M)) <
GD,,, WRI + 8hG
T
Using this display, we decompose the regret of the algorithm as stated below.
E
Σ (x un)
inf MEM
Σ
T
Σ Crs(M)) - inf
(M)( + 2GD2 + WnDD.,.Whhh + 28hGDa..tt Σ
MEM
Next, we use the following regret bound on an abstract implementation of online gradient descent with delayed updates, which specialize subsequently to our setting.
23

---

Lemma 16. Consider a delayed gradient update in Online Gradient Descent, executed as
M =IIM M -npe-n
where |EV
V(( S E, ال I G. DM MAXMEM [| Additionally, if
MAxMEM
(M)) GM. then we have for any n 0 that
2hd D3
E
Σ -
2eDMI hddmin 2nh 2 G2T
Now, we invoke the regret upper bound from Lemma
16jto arrive at
c (x1, u.)
E
Σ inf MEM
(x,
)
t=1
2hd D2 M
2&D TT /hdmin 2nthi dmmi
dmin TT
+ 2GD2 n.a + n,D W h GT 2. T
Finally, we plug the value of & from Lemma 17 and e from the first part of Lemma 14 Lemma 17. The stochastic gradients produced by Algorithm 3 satisfy the following bound
[Vll S S dgD2
As evident from the definition of M, DM = 2vhxt. Setting Yd yields the result of ((T3/4) regret for (possibly) non-smooth costs.
V dmin --/4-//4
For the second part of the claim, we show an improved analogue of the second part of Lemma 14
Lemma 18. As long as c₂ L-smooth, for all M M. (M) Č.(M) s 25Lx
Using this, a manner similar to the derivation for non-smooth costs, we arrive at
T
T
E
(xt. u.)
inf MEM
Σ
Cx u
t=1
2hd DM
< 2cDMT T V /ndmi + 2n/h dmii GT +
+GD +IGD W 1 50L 500"
(d 32233) to arrive the final bound as In this case, we set (dy 1/37 1/3 d stated in the claim.
E.4 Proof of Supporting Claims
Proof of Lemma 13 the fact that = o(1).
The properties follow from Lemma in Cassel and Koren 2020 while using
Proof of Lemma 14
Using the chain rule, we note that
h
VO,(M)
Σ (iu,F((
M @ 1e-
1=1
Now, we note that the smoothed function Fi, will satisfy
Fi,s(urk) - F((uaa)) 8hGF, ICro(A)) - 8hGF
24

---

where Gp is the Lipschitz constant of F; with respect to single u. This follows, by hybrid-liih like argument smoothing one argument at time using standard smoothing results (see e.g. [Gradu et al.) 2020] Fact 3.2). We note that G can be bound by GDr, Furthermore, this smoothing preserves convexity of Fi,s and composition of linear and convex function is convex, C. also remains convex.
The gradients of the smoothed function then has the following form due to Lemma 6.7 from Hazan et al. (016)-
du Fu + )
Vu, ((,((u))))) = Bana~aa
du
(M), = BBnjanBu
Fi(uih 8nish)m Mywehie 3
1=1
Cc(M)aaa)
Rearranging, we have
d,Ca n A+11
VCr,((M)) En
Σ
nr- @ W
1=0
Now, to relate this to Em Bag [el.. we note in expression for V(,,(AM)) we bound
(x(,, u - - C.(M (n 11) via Lemma 15
Using bounds on w, n along with this
bound, we have
W
GDD
2nd And,h-W2 (
- <
6
T
5
Proof of Lemma 75 We start with triangle inequality
1x,(%; u.) ((M))) (e,(x; u,) C p + (, ( (2(" (n-
The first term is handled via Lemma 13 so we only need to bound the second term
(C((M C.(M(')
= - (c Σ
M.w.-.) - cc(E((M))
Σ Mf
==1
==1
- GDD (M hit)
(M())
2h
GD
V Wi(M hit Ww- Σ Vi(M* ... M Mt)
2h
GD
V (M (M:t hut -(M' ...M)))
< G.
V W hit (M ...M))
25

---

Now we note that each matrix Mÿ, only occurs in one term of the form A AMM,, so we can refine the bound above
- M
h
GD (
11 V
S Wr
Combining, have
GD2 1a(xx, u.) - -
2.8
+DD
T
Proof of Lemma 16 Since et convex, so is C2,5- Using this fact and the observation that M is independent of D used to construct V, due to the delayed update of gradients, we have
C,,((M)) - ((2(
(VC,,(M'), M -M")
EV M - -M*) + 2EDD MY v /hdmin
BVV,, M -M) + +|||l1/||M MM'l 2e BeDM / hdmmi E M - -M*) +
6 dmin + +2=DMM v h/dmiin
The gradient update can be rewritten
Mith Md < || - 1
11 1GGhhdmaa || 1/ M
2m
| Mr
||M+HH+ Mr h
21
2
where we use the fact that the projection operator is non-expansive, hence M++ is closer in Euclidean distance to M than M v, Telescoping this, we have for any M that
T C,.((M))) - > ECs(sr))
< 2e hdmin + 2 dmin &T + 2hd D3
E
Proof of Lemma 17 Plugging in line from Algorithm and using our bounds on the cost, we have
d
d, 2,4
R.M
8
Proof of Lemma 18 We first make note of the following characterization of idealized costs under smoothness due to Cassel and Koren 2020 (Lemma 7.2, therein).
Lemma 19 Cassel and Koren (020). If is L-smooth, then the smoothed and non-smoothed variants of the idealized costs C₁, F,, Ci, Fi, are L'smmoth, where L' = 25L 25" 2///a.
26

---

Note that C₁ Gτ, only differ in that the latter is noise-smoothed version of the former. Let
U1:h = Ei=o MW Eizo MW ... Σi= M. Using the fact the noise
Bi:h zero-mean and independent of U1:h: we create a second-order expansion using Taylor's theorem to conclude
(M) - (.(M)
-Bnin Fu + sm1.)) Fr(uis)]
Ennia -as (P + L'
< h.
27


Reviews:
[{"review_id": "1ko2LBgfoW", "reviewer": "Reviewer_MnP5", "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.", "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?", "limitations": "The authors cover the limitation of each pseudo-disturbance. They are also upfront about PD1 not performing well in RL.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The problem setting is well-motivated and clearly formulated.\n2. New concepts are nicely explained.\n3. The different choices of pseudo-disturbance make sense intuitively and are well supported for their properties in the linear case.\n4. 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.\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and thoughtful review.  We address the main points below:\n\nWeaknesses:\n\nWe acknowledge that paper would be stronger with non-uniform disturbances. We will add detailed experiments for sinusoidal disturbances and adversarial sign gradient disturbances. \n\nBenchmarking against other more state-of-the-art methods like SAC would be useful, and we will add this. We will note that our algorithm is an augmentation or modification on top of a base algorithm, so we can apply our method on top of other baselines (SAC included) as well.  We wanted to show an improvement on the base algorithm with our experiments so this is a proof of concept for now.\nWe have not completed this for the rebuttal because we did not have the time to run the appropriate hyperparameter sweeps, which are needed even for new baselines in our modified noisy environments.\n\nQuestions:\n\nBeyond our theory for linear dynamical systems, we note that crucially MF-GPC policies are non-markovian (take more than immediate state into account), which could potentially help in non-markovian environments. This point is also highlighted by our theory for linear systems. In contrast, most of the RL algorithms are designed for markovian settings.\n"}, {"review_id": "AhcxZhlElj", "reviewer": "Reviewer_4h3N", "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. ", "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.\n\n2. 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.", "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. ", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "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. \n\nThe 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.\n\nAnother 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and thoughtful review.  We address the main points below:\n\nWe note that PD2 is actually quite general, and does not require specific domain-engineered signals from the environment.  For example, in all our experiments, we use the coordinates of the state for each auxiliary reward. This suggests simple, domain-agnostic auxiliary reward signals can deliver significant utility for PD2. We acknowledge that PD3 generally requires a simulator, though it fits in the framework and can be useful when a simulator is available. We acknowledge PD1 did not perform well, despite this being our initial idea and the nicest one in theory. We suspect this is due to the PD1 estimator's high variance.  We leave improving this via variance reduction to future work\n\nRegret minimization in general online MDPs with adversarial dynamics is known to be computationally hard (Yadkori et al., 2013), so restricting the setting is necessary to make progress. We will add discussion of this in the paper. We believe our setting is still meaningful, and sheds light on general principles that apply to nonlinear settings.\n\nQuestions:\n\n1. Good question! While it’s true the Q,V functions are learned estimates, as long as the Bellman (backup) equation holds, this works.  Generally, one can increase the number of gradient-based update steps for the critic per episode to make sure this error is small. We will add a short discussion of this to the paper.\n\n2. We were a bit imprecise when describing this in the paper and will clarify in the paper. We use the same architecture for critic networks but with a wider final layer (since the output is no longer a scalar) to produce values for each auxiliary reward. We are not reusing the representations of the original critic.\n\nLimitations:\n\nWe disagree that we did not discuss limitations of our methods. We discuss limitations of each signal in section 3.4 as is attested by Reviewer MnP5.  We agree that theory being restricted to linear dynamical systems is a limitation, though we never claim provable guarantees beyond this setting.\n\n[1] Yasin Abbasi Yadkori, Peter L Bartlett, Varun Kanade, Yevgeny Seldin, and Csaba Szepesvári. Online learning in markov decision processes with adversarially chosen transition probability distributions. Advances in neural information processing systems, 26, 2013.\n"}, {"review_id": "SgocXlj2FG", "reviewer": "Reviewer_ijfz", "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.", "questions": "- TD-Error: (See above)\n- Why does PD2 not improve the performance in noisy walker and only marginally in noisy ant? \n- 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).\n- Code: You provided code for the LDS experiments. Why not also for the robotics environments?", "limitations": "The authors did not dicsuss the limitations of their approach.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "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.\n- The ideas are formally justified and the derivations appear to be mostly correct. For LDS, the authors provide convergence proofs of their method.\n- 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.\n- 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. \n- 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\n$$c(x_t, u_t) + \\gamma V_\\pi(x_{t+1}) - V_\\pi(x_t).$$\nFrom the definition of $Q$ and $V$ and $\\mathbf{\\hat w_t}$, we can derive\n$$\n\\begin{align*} \n&\\gamma V_\\pi(f(x_t, u) + w_t) - (Q_\\pi(x_t, u) - c(x_t, u)) \\\\\n&=\\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)) \\\\\n&= \\gamma (V_\\pi(\\hat x_{t+1}) -  \\mathbb E_{x_{t+1}}[V_\\pi(x_{t+1})]),\n\\end{align*}\n$$\nwhich 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.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and thoughtful review.  We address the main points below:\n\nWeaknesses:\n\nOur contribution is mostly conceptual and theoretical, thus we focused on methods with provable guarantees. Using a learned model to compute disturbances could be interesting, but we don’t see how to develop theory based upon such a learned model at this time, especially if it is nonlinear. \nPD3 indeed performs best from our methods, but having a simulator is common in many applications, thus we think our method can be potentially practical. \n\nSorry for the confusion regarding PD1: what we mean in “TD error” is the update/error in expected SARSA (Sutton and Barto, 2018), which derives from TD error. We recognize that typically TD error is defined on state value functions (instead of state-action ones). We will clarify this in the final version. Briefly, our \"TD error\" is designed so that it is zero in expectation in absence of disturbances, thus deviations of it (on average) signal presence of unmodeled disturbances. A central result we point is that the expected value of its gradients can be used to recover the disturbances for linear systems.\n\nWe are happy to increase font sizes as you suggest. \n\nQuestions:\n\nPD2: We are not sure why PD2 does not improve performance of noisy walker and only marginally in noisy ant. This is an interesting question for future investigation. \n\n\nGradient formula:  We can explain this in more depth in the paper. The gradient term is not in (1) and (2) because we use sampling to estimate this gradient.  We are using a single point zeroth order gradient estimator (See equation (1) in  https://arxiv.org/pdf/2006.06224.pdf ). In our case, with quadratic value functions there is no smoothing error as can be seen in the proof in Appendix D.1 of the supplement.\n\nCode: We could not release the code for the larger scale experiments because these were implemented and tested within a proprietary benchmarking suite and there are restrictions on release. We plan to implement the experiments in open source and release. More importantly, we are very happy to release the algorithm's code itself very soon.  \n\nLimitations:\n\nWe disagree that we did not discuss limitations of our methods. We discuss limitations of each signal in section 3.4 as is attested by Reviewer MnP5.  We agree that theory being restricted to linear dynamical systems is a limitation, though we never claim provable guarantees beyond this setting.\n\nRichard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.\n\n"}]

Author rebuttal:
**Please see attached pdf file.**

Dear reviewers, we thank you for your time and effort in reviewing our paper! 
The main weakness jointly pointed by the reviewers is lack of experimentation with more varied noise patterns, as opposed to stochastic noise. 

We attach below in pdf format two experiments that show faster training for PD2 with:
1. sinusoidal disturbances
2. adversarial sign gradient attack disturbances (similar to [this](https://arxiv.org/pdf/1412.6572.pdf))

We will expand on these at the earliest chance of revision. 

More detailed responses are addressed below to each reviewer separately. 

Thanks again, we hope this will alleviate your concerns. 

Meta-review: The paper addresses model-free RL when there are additive disturbances in the dynamic model, with the key idea to introduce a correction term that is derived from estimates of the process noise. All the reviewers are in favor of accepting the paper – the main criticism being empirical evaluation and lack of clarity/discussion on limitation of the method.

During the discussion phase the reviewers raised many questions that were satisfactorily answered by the authors. Moreover, the authors also shared additional experimental results with varied nose patterns – these experiments are in-line with the reviewers ask. Also, the authors point out an additional contribution (a better regret that shows effectiveness in higher dimensional state spaces) that they did not explicitly focus on in the original submission.

My recommendation is accept, and I encourage authors to both include the new experimental results as well as the novel theoretical insight. Additionally, a discussion of limitation of the method will be beneficial to the research community.
Decision: Accept (poster)