Faster Deep Reinforcement Learning with Slower Online Network
Authors: Kavosh Asadi
Rasool Fakoor
Omer Gottesman
Taesup Kim
Michael Littman
Alex Smola
Venue: NeurIPS 2022 Accept (2022)

Abstract: Deep reinforcement learning algorithms often use two networks for value function optimization: an online network, and a target network that tracks the online network with some delay. Using two separate networks enables the agent to hedge against issues that arise when performing bootstrapping. In this paper we endow two popular deep reinforcement learning algorithms, namely DQN and Rainbow, with updates that incentivize the online network to remain in the proximity of the target network. This improves the robustness of deep reinforcement learning in presence of noisy updates. The resultant agents, called DQN Pro and Rainbow Pro, exhibit significant performance improvements over their original counterparts on the Atari benchmark demonstrating the effectiveness of this simple idea in deep reinforcement learning. The code for our paper is available here: Github.com/amazon-research/fast-rl-with-slow-updates.

Faster Deep Reinforcement Learning with Slower Online Network
Kavosh Asadi Amazon Web Services
Rasool Fakoor Amazon Web Services
Omer Gottesman Brown University
Taesup Kim Scoul National University
Michael L. Littman Brown University
Alexander J. Smola Amazon Web Services
Abstract
Deep reinforcement learning algorithms often use two networks for value fune- tion optimization: an online network, and a target network that tracks the online network with some delay. Using two separate networks enables the agent hedge against issues that arise when performing bootstrapping. In this paper we endow two popular deep reinforcement learning algorithms, namely DQN and Rainbow, with updates that incentivize the online network to remain in the prox- imity of the target network. This improves the robustness of deep reinforcement learning in presence of noisy updates. The resultant agents, called DQN Pro and Rainbow Pro, exhibit significant performance improvements over their original counterparts on the Atari benchmark demonstrating the effectiveness of this simple idea in deep reinforcement learning. The code for our paper is available here: Github.
Introduction
An important competency of reinforcement-lemming (RL) agents is learning in environments with large state spaces like those found in robotics (Kober et al. 2013), dialog systems @Williams et al. 2017). and games (Tesauro 1994; Silver (017). Recent breakthroughs in deep RI. have demonstrated that simple approaches such as Q-learning (Watkins & Dayan [992) can surpass
human-level performance in challenging environments when equipped with deep neural networks for
function approximation (Mnih et al. 2013).
Two components of gradient-based deep RL agent its objective function and optimization procedure. The optimization procedure takes estimates of the gradient of the objective with respect to network parameters and updates the parameters accordingly. In DQN (Mmih et al. 2015), for example, the objective function is the empirical expectation of the temporal difference (TD) error (Sutton)
1988) on buffered set of environmental interactions (Lin 1992). and variants of stochastic gradient descent are employed to best minimize this objective function.
A fundamental difficulty in this context stems from the use of bootstrapping. Here, bootstrapping refers to the dependence the target of updates on the parameters of the neural network, which is itself continuously updated during training. Employing bootstrapping in RL stands in contrast to pneervised-leamiing techniques and Monte-Carlo RL (Sutton & Barto 2018), where the target of our gradient updates does not depend the parameters of the neural network.
Mnih et al. (0155) proposed a simple approach to hedging against issues that arise when using bootstrapping, namely to use a largel network in value-function optimization. The target network updated periodically, and tracks the online network with some delay. While this modification
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

constituted a major step towards combating misbehavior in Q-learning (Lee & He 2019 Kim et al.
2019
Zhang et al. 202T. optimization instability still prevalent van Hasselt al., 2018).
Our primary contribution is to endow DQN and Rainbow (Hessel et al. 2018 with term that ensures the parameters of the ontine-network component remain in the proximity of the parameters of the target network. Our theoretical and empirical results show that our simple proximal updates can remarkably increase robustness to noise without incurring additional computational or memory costs. In particular, we present comprehensive experiments on the Atari benchmark (Bellemare et al.) 2013) where proximal updates yield significant improvements, thus revealing the benefits of using this simple technique for deep RL.
2 Background and Notation
RL is the study of the interaction between an environment and an agent that learns to maximize reward through experience. The Markov Decision Process (Puterman) 1994), or MDP, is used math- ematically define the RI. problem. An MDP is specified by the tuple (S, A, R. P. 7) where S is the of states and A is the set of actions. The functions R. S x A -> IR and p S A x S [0, 1] denote the reward and transition dynamics of the MDP. Finally, discounting factor ry is used to formalize the intuition that short-term rewards are more valuable than those received later.
The goal in the RL problem to learn a policy, a mapping from states to a probability distribution over actions, S (AA), that obtains high sums of future discounted rewards. An important concept in RL is the state value function. Formally, denotes the expected discounted sum of future policy in state (s) E
rewards when committing the Bellman operator 7 as follows:
- Ro|So 8, T We define
(T) = Σ raa (R(s,)) + Σ P(s,,, 8')(8))
aEA
s'ES
which we can write compactly Txu = R + pP where (s)=
([als) [lee and [PmD] (s) E.EA T(a 8) EvesP(s, a, s s's) We also denote: (TT)"u TT.
72 compositions
Notice that o. is the unique fixed- of (T*)" for all natural numbers meaning that at (T")" for all n. Define v* as the optimal value of a state, namely: v (s) == max, v (s), and n policy that achieves (s) for all states. We define the Bellman Optimality Operator T
[To] = max R(s, a) + PTP(s,,,'')(( aEA
s'ES
whose fixed point v*. These operators are the heart of many planning and RL algorithms including Value Iteration (Bellman 1957) and Policy Iteration HHwwrd 1960).
3 Proximal Bellman Operator
In this section, we introduce a new class of Bellman operators that ensure that the next iterate in planning and RL remain in the vicinity of the previous iterate. To this end, we define the Bregman Divergence generated by a convex function f:
Dy(e', v) : f(0')
(VS()), -
Examples include the 4p norm generated by f(v) - 1 ||0 and the Mahalanobis Distance generated by f(c) = (v. Qu) for a positive semi-definite matrix Q-
We now define the Proximal Bellman Operator (TE,))":
(T "o arg min I| / (7T)" 0l D))
(I)
where e E (0, oc). Intuitively, this operator encourages the next iterate to the proximity of the previous iterate, while also having small difference relative to the point recommended by the

---

original Bellman Operator. The parameter could, therefore, be thought of as knob that controls the degree of gravitation towards the previous iterate.
Our goal is to understand the behavior of Proximal Bellman Operator when used in conjunction with
the Modified Policy Iteration (MPI) algorithm (Puterman 1994 Scherrer al. 2013). Define Gr
as the greedy policy with respect to v. At a certain iteration k, Proximal Modified Policy Iteration
(PMPI) proceeds as follows:
Tkk f GUK-1,
<- (o--)
(3)
The pair of updates above generalize existing algorithms, Notably, with c + oo and general n we get MPI, with - and n 1 the algorithm reduces to Value Iteration, and with c - oc and n 00 we have a reduction to Policy Iteration. For finite c. the two extremes of n, namely n = 1 and n = oc, could be thought of as the proximal versions of Value Iteration and Policy Iteration, respectively.
To analyze this approach, it is first natural to ask if each iteration of PMPI could be thought of as contraction so we can get sound and convergent behavior in planning and learning. For > 1, Scherrer et al. (2015) constructed a contrived MDP demonstrating that one iteration of MPI can unfortunately expand. As PMPI is just a generalization of MPI, the same example from SSchererr et al. 2013) shows that PMPI can expand. In the case of n 1, we can rewrite the pair of equations 2 and in single update as follows: Up f- Th When + 0o, standard proofss can be employed to show that the operator is contraction (Littman & Szepesvári 1996). We now show that To. contraction for finite values of See our appendix for proofs.
Theorem 1. The Proximal Bellman Optimality Operator Tē. is contraction with fixed point v².
Therefore, we get convergent behavior when using Te,, in planning and RL. The addition of the proximal term is fortunately not changing the fixed point, thus not negatively affecting the final solution. This could be thought of form of regularization that vanishes in the limit; the algorithm converges to vt even without decaying 1/c.
Going back to the general sekas & Tiitsiklis 1996, Scherrer et al. 2015), we study error propagation in PMPI in presence of additive noise where we get a noisy sample of the original Bellman Operator (7 3" 0 + eg. The
case, we cannot show contraction, but following previous work (Bert-
noise can stem from a variety of reasons, such as approximation or estimation error. For simplicity,
we restrict the analysis to (v', v) l|o' 2112. so we rewrite update B as:
Uk f arg min 1/00 ((T=.)" Ux- - Ex) 112 ll Uk 111
which can further be simplified to:
Uk
(T " UK-- + Buk +(1 B)EK:
where 3 = I=ce This operator is a generalization of the operator proposed by Smirnova & Dohmatob (2020) who focused on the case of n = 1. To build some intuition, notice that the update is multiplyngg error én by a term that is smaller than one, thus better hedging against large noise. While the update may slow progress when there is no noise, is entirely conceivable that for large enough values of ex. it is better
non-zero B3 values. In the following theorem we formalize this intuition. Our result leans on the theory provided by Scherrer et al. (015) and could be thought of as a generalization of their theorem for non-zero values.
Theorem 2. Consider the PMPI algorithm specified by:
Th Get Uk-1
(4)
Uk f- (T (T
p + -3)e
(5)
Define the Bellman residual by == Uk TFst2 Upe and error terms By : (I --pFpk and
yk == 7 Pm" 6k. After k steps:
Th x0 (T (Tg Tx+1 Uk Una
3

---

where dR S 7ppx dx-1 ((1 -)yk-1 - 3bb-1) +11 Σラ=1 (y +
S - ( P +3)1 (T- - 37)bk=1 + (1 -3) + 6
by (11
The bound provides intuition as to how the proximal Bellman Operator can accelerate convergence in the presence of high noise. For simplicity, we will only analyze the effect of the noise term, and ignore the e' term. We first look at the Bellman residual, bg- Given the Bellman residual in iteration 1, 1, the only influence of the noise term eg on by is through the (1 - ( r), term, and we see that by decreases linearly with larger B.
The analysis of sk is slightly more involved but follows similar logic. The bound for 8y can be decomposed into a term proportional to b and term proportional to 36,-1, where both are multiplied with positive semi-definite matrices. Since b itself linearly decreases with 3, we conclude that larger 3 decreases the bound quadratically.
ΣØ= j= Pm ybg-1 The effect of 3 on the bound for dg is more complex. The terms Byk-1 and > 11-
introduce a linear decrease of the bound on dk with 3, while the term 3(1 ΣØ= (T 66k-1
introduces quadratic dependence whose curvature depends on / E (y y. This complex dependence on / highlights the trade-off between noise reduction and magnitude of updates. To understand this trade-off better, we examine two extreme cases for the magnitude on the noise. When the noise is very large, we may set 3 1, equivalent to infinitely strong proximal term. is easy to see that for 8 = 1, the values of dę and remain unchanged, which is preferable to the increase they would suffer the presence of very large noise. On the other extreme, when no noise is present, the Fa and yı: terms in Theorem 2 vanish, and the bounds on de and 8ę can be minimized by setting = 0, i.e. without noise the proximal term should not be used and the original Bellman update performed. Intermediate noise magnitudes thus require value of /3 that balances the noise reduction and update size.
Deep Q-Network with Proximal Updates
We now endow DQN-style algorithms with proximal updates. Let (s, a, of interaction. Define the following objective function:
n,, s') denote buffered tuple
h(0, w) == E(s.ar.'') 7 max Q(s: (1
(6)
a
Our proximal update is defined follows:
1 25 ||w well
W++1 < arg min h(w,, w) +
This algorithm closely resembles the standard proximal-poing algorithm (Rockafellar 1976 Parikh & Boyd| 2014) with the important caveat that the function h is taking two vectors input. At each iteration, we hold the first input constant while optimizing over the second input.
In the optimization literature, the proximal-point algorithm is well-studied in contexts where an analytical solution to 7 available. With deep learning no closed-form solution exists, so we approximately solve 7 by taking fixed number of descent steps using stochastic gra- dients. Specifically, starting each iteration with w = Wt, we perform multiple w updates w tw-a V2h(W,, w) + _ (w- wr)). We end the iteration by setting Wt+1 w. To make a connection to standard deep RL, the online weights w could be thought of as the weights we maintain in the interim to solve 7 due to lack of a closed-form solution. Also, what is commonly referred to as the target network could better be thought as just the previous iterate in the above moximal-poin algorithm.
(a/a) (1-(aa)) w + (a/2) w. -a-aa V22h(wr w. Notice the intuitively appealing form: we first compute convex combination of w: and w, based on the syper-parametery a and 2, then add the gradient term to arrive at the next iterate of w. If we and w are close, the convex combination is close to w itself and so this DON with proximal update
Observe that the update can be written as: w + (1

---

(DQN Pro) would behave similarly to the original DQN. However, when strays too far from wa taking the convex combination ensures that w gravitates towards the previous iterate wy- The gradient signal from minimizing the squared TD error 6 should then be strong enough to cancel this default gravitation towards wt. The update includes standard DQN as special case when - oc. The pseudo-code for DQN is presented in the Appendix. The difference between DQN and DQN Pro is minimal (shown gray), and corresponds with a few lines of code our implementation.
Experiments
In this section, we empirically investigate the effectiveness of proximal updates in planning and reinforeement-leammigg algorithms. We begin by conducting experiments with PMPI in the context of approximate planning, and then move to large-scale RL experiments Atari.
5.1 PMPI Experiments
We now focus understanding the empirical impact of adding the proximal term on the performance of approximate PMPI. To this end, we use the pair of update equations:
T
< Gek-1 <- (1- (1-B) +x) + 81k-1-
For this experiment, we chose the toy 8 8 Frozen Lake environment from Open AT Gym (Brockman et al. 2016), where the transition and reward model of the environment is available the planner. Using a small environment allows us to understand the impact of the proximal term in the simplest and most clear setting. Note also that we arranged the experiment that the policy greedification step GUA-1 Vk is error-free, so we can solely focus on the interplay between the proximal term and the error caused by imperfect policy evaluation.
We applied 100 iterations of PMPI, then measured the quality of the resultant policy π == T100 as defined by the distance between its true value and that of the optimal policy, namely || V llog: We repeated the experiment with different magnitudes error, as well as different values of the parameter.
0.35
0.40
5.00....000..0002
0.30
Unifom 6. 00..01...c0.11
Unformt- 005.0 805)
Unform--0 w.o.s.s.coo. (o5))
Inform-- 01.0 01)
0.25
Unffemi-0.0. (00mmi-0.010.000 0.01.0..1)
0.25
Unferm--..0s 05,0
Unifornt
||V
ViIl-
IIV
0.20
0.30
0.05
0.00
0.00
0.00
0.25
0.50
0.30
0.55
0.00
0.25
0.30
0.70
0.95
Figure I: Performance approximate PMPI has a U-shaped dependence on the parameter / = T+a Results are averaged over 30 random seeds with n (left) and = (right).
From Figure M is clear that the final performance exhibits U-shape with respect to the parameter 3. It is also noticable that the best best-performing 3 is shifting to the right side (larger values) as we increase the magnitude of noise. This trend makes sense, and is consistent with what is predicted by Theorem 2: As the noise level rises, we have more incentive to use larger (but not too large) B values hedge against it.
5.2 Atari Experiments
In this section, we evaluate the proximal (or Pro) agents relative to their original DQN-style counter- parts on the Atari benchmark (Bellemare et al. 2013), and show that endowing the agent with the proximal term can lead into significant improvements in the interim as well as in the final performance. We next investigate the utility of our proposed proximal term through further experiments. Please see the Appendix for complete description of our experimental pipeline.
5

---

5.2.1 Setup
We used 55 Atari games (Bellemare et al. 2013) to conduct our experimental evaluations. Following Machado (2018) and Castro (2018), we used sticky actions to inject stochasticity into the otherwise deterministic Atari emulator.
Our training and evaluation protocols and the hyper-parameter settings follow those of the Dopamine baseline (Castro et al., 2018). To report performance, we measured the undiscounted sum of rewards obtained by the learned policy during evaluation. We further report the learning curve for all experiments averaged across 5 random seeds. We reiterate that we used the exact same hyper-parameters for all agents ensure sound comparison.
Astortx
Amidar
0.1
022
BeamRider
Breakout
Gopher
Asterix
Qbert
Amidar
Breakout
Figure 2: A minimal dyper-parameee tuning for in DQN Pro (left) and Rainbow Pro (right).
Our Pro agents have single additional hyper- ayper-parameter č. We did minimal random search on games to tune č Figure 2 visualizes the performance of Pro agents as function of č. In light of this result, we
0.2 for DQN Pro and 0.05 for Rainbow Pro. We used these values of all 55 games, and note that performed no further arper-parameter tuning at all.
5.2.2 Results
The first question is whether endowing the DQN agent with the proximal term can yield significant improvements over the original DQN. Figure (top) shows a comparison between DQN and DQN
Pro in terms the final performance. particular, following standard practice (Wang et al. 2016
Dabney et al. 2018 van Seijen al. 2019, for each game we compute:
ScoreDoN Pm ScoreDQN
max ScorepoN Score Scoreganko
Bars shown in red indicate the games in which we observed better final performance for DQN Pro relative to DQN, and bars in blue indicate the opposite. The height of a bar denotes the magnitude of this improvement for the corresponding benchmark; notice that the y-axis is scaled logarithmically. We took human and random scores from previous work (Nair et al. 2015 Dabney al. (018). clear that DQN Pro dramatically improves upon DQN. We defer to the Appendix for full learning curves on all games tested.
Can we fruitfully combine the proximal term with some of the existing algorithmic improvements DQN? To answer this question, we build the Rainbow algorithm of Hessel al. (2018) who successfully combined numerous important algorithmic ideas in the value- based RL literature. We present this result Figure 3 (bottom). Observe that the overall trend is for Rainbow Pro yield large performance improvements over Rainbow.
Additionally, measured the performance of agents relative human players. To this end, and again following previous work (Wang et al.] 2016 Dabney et al. 2018 van Seijen et al. 2019), for each agent compute the human-normalized score:
Score ScoreRandom
Score ScoreRamiom
In Figure (left), we show the median of this score for all agents, which Wang et al. (2016) and Hessel al. (0018) argued sensible quantity to track. We also show per-game learning curves with standard error in the Appendix.

---

200%
10%
10%
0%
0%
10%
10%
jurroy
Carbical
Pera
Alen
dowiro
Chopre rocorntte
Aateoads
Solers
Crucy
Nithommn
Fruitite
thouree
drasta
Kough Kenghwtert
Fahingbwiy
Attutt
video
aamusiied
Sta Stanburne
Span manninuuus
Vise Tearhii
Mumo Mume Noceme
Ouner
Mantrr Coniraaaaiin
3000%
3000%
100%
100%
10%
0%
10%
10%
50%
50%
Andee
tansiron
Bowkng
Chepprreenn of
Coll
yprute
Contral
booing
Queer
20tpun
Oocher
Spactevnder
Hon
Figure 3: Final gain for DQN Pro over DQN (top), and Rainbow Pro over Rainbow (bottom), averaged over 5 seeds. DQN Pro and Rainbow Pro significantly outperform their original counterparts.
We make two key observations from this figure. First, the very basic DQN Pro agent is capable of achieving human-level performance (1.0 on the y-axis) after 120 million frames. Second, the Rainbow Pro agent achieves 220 percent nurmaieordalized score after only 120 million frames.
5.2.3 Additional Experiments
Our purpose in endowing the agent with the proximal term to keep the online network in the vicinity of the target network, so it would be natural to ask this desirable property can manifest itself in practice when using the proximal term. In Figure 4 answer this question affirmatively by plotting the magnitude of the update to the target network during synchronization. Notice that we periodically synchronize online and target networks, so the proximity of the online and target network should manifest itself in a low distance between two consecutive target networks. Indeed, the results demonstrate the success of the proximal term terms of obtaining the desired proximity of online and target networks.
While using the proximal term leads to significant improvements, may still wonder if the advan- tage of DQN Pro over DQN is merely stemming from a poorly-chosen period typer-parameted in the original DQN, as opposed to truly more stable optimization in DQN Pro. To refute this hypothesis, we ran DQN with various settings of the period hyper-parameter {2000, 4000, 8000, 12000). This included the default value of the hyper-parameter (8000) from the original paper (Mnih al. 2013), but also covered a wider set of settings.
Additionally, tried an alternative update strategy for the target network, referred to as Polyak averaging, which was popularized in the context of continuous-action RL (Lillicrap et al. 2015): 0 Tw + (1 8. For this update strategy, too, tried different settings of the hyper-parameed namely (0.05, 0.005, 0.0005), which includes the value 0.005 used numerous papers (Lillicrap
al. 2015 Fujimoto al., 2018 Asadi al. 202T).
Figure presents a comparison between DQN Pro and DQN with periodic and Polyak target updates for various syper-parameter settings of period and It is clear that DQN Pro is consistently
7

---

2.5
Deanfider
Rainbow
human-normalized median
Rainbow
2.0
DQN Pro
DQN
1.5
Gogeer
1.0
122
0.5
0.0
Tea Baaiing Fromes Boo
Training Frames (Million)
Figure 4: (left): Human-normalized median performance for DQN, Rainbow, DQN Pro, and Rainbow Pro on 55 Atari games. Results are averaged over independent seeds. Our agents, Rainbow Pro (yellow) and DQN Pro (red) outperform their original counterparts Rainbow (green) and DQN (blue). (right): Using the proximal term reduces the magnitude of target network updates.
Beandhider
WicardOWWrr
BearsFiderr
WiarstWWrr
500C
1:00
+000
+000
Anstage Reriure
3000
1000
1000
1000
Training Frammss (illice)
Traliing Framnes (ViBoo))
Tralsing Frames (VBllo))
Trakning Frames (Viloo))
1.000
10000
0000
0512
DON Pre
DON Pro
DGN aettor 1904
DCh perloc
22
Figure 5: A comparison between DQN Pro and DQN with periodic (left) and Polyak (right) updates.
outperforming the two alternatives regardless of the specific values of period and T, thus clearly demonstrating that the improvement is stemming from more stable optimization procedure leading better interplay between the two networks.
Finally, an alternative approach to ensuring lower distance between the online and the target network is to anneal the step size based on the number of updates performed the online network since the last online-target synchronization. In this case we performed this experiment in 4 games where knew proximal updates provide improvements based
DQN Pro versus DQN resulst in Figure 3 In this case we linearly decreased the step size from the original DQN learning rate a to a' where we tuned a' using random search. Annealing indeed improves DQN, but DQN Pro outperforms the improved version of DQN. Our intuition is that Pro agents only perform small updates when the target network is far from the online network, but naively decaying the learning rate can harm progress when the two networks are in vicinity of each other.
Discussion
In our experience using proximal updates in the parameter space were far superior than proximal updates in the value space. We believe this is because the parameter-space definition can enforce the proximity globally, while in the value space one can only hope obtain proximity locally and
batch of samples. One may hope to use natural gradients to enforce value-space proximity more principled way, but doing usually requires significantly more computational resources Knight &

---

Name ThinGame
Zarzon
BattleZone
Assauft
1/990
20000
2000
12:00
Accensp Resion
Averago Rettern
.00000
Aeerog 8000
19400
33000
DOKtro
5000
500
DON deciy
Training Frames
100
Training (Miliio))
120
Training Fromes (Willon))
120
Training Fromes (Milioo))
122
Figure 6: Learning-rate decay does not bridge the gap between DQN and DQN Pro.
This is in contrast to our proximal updates which add negligible computational cost in the simple form of taking a dimension weighted average of two weight vectors.
Lernr 2018).
In addition, for a smooth (Lipschitz) Q function, performing parameter-space regularization guaran- tees function-space regularization. Concretely: Vs, Va [Q(s a; 0) - ((,, a; 0') < L 0'll where L is the Lipschitz constant of Q. Moreover, deep networks are Lipschitz (Neyshaurr et al. 2015 Asadi et al. 2018). because they are constructed using compositions of Lipschitz functions (such as ReLU, convolutions, etc) and that composition of Lipschitz functions is Lipschitz. So performing value-space updates may be an overkill. Lipschitz property of deep networks has successfully been leveraged in other contexts, such as in generative adversarial training Arjovsky et al. (2017).
A key selling point of our result is simplicity, because simple results easy understand, implement, and reproduce. We obtained significant performance improvements by adding just a few lines of codes to the publicly available implementations of DQN and Rainbow Castro et al. (018).
7 Related Work
The introduction of proximal operators could be traced back to the seminal work of Moreau (196
1965). Martinet (1970) and Rockafellar (1976), and the use of the proximal operators has since expanded into many areas of science such as signal processing (Combettes & Pesquet 2009).
statistics and machine learning (Beck & Tehoulle 2009 Polson et 2015) Reddi et 2015 and
convex optimization (Parikh & Boyd 2014 Bertsekas
2011b
In the context of RL, Mahadevan et al. off-policy algorithms with linear function approximation. One intriguing characteristic of their work is that they perform updates in primal-dual space, a property that was leveraged in sample complexity analysis (Liu et al. 2020) for the proximal counterparts of the gradient cemporal-differenen algorithm (Sutton et al.] (2008) Proximal operators also have appeared in the deep RL literature. For instance, instance,,Fakoor et al. (2020b) used proximal operators for meta learning, and Maggipinto et al. (2020) improved TD3 (Fjimoto et al. 2018) by employing a stochastic proximal poxiital-point point interpretation.
(2014) introduced proximal theory for deriving convergent
The effect of the proximal term in our work reminiscent of the use of trust regions in
algorithms (Schulman al. 2015 2017, Wang al. 2019 Fakoor et al. 2020a Tomar et al.) 202T). However, three factors differentiate our work: we define the proximal term using the value function, not the policy, we enforce the proximal term in the parameter space, as opposed to the function space, and we use the target network as the previous iterate in our proximal definition.
8 Conclusion and Future work
We showed clear advantage for using proximal terms to perform slower but more effective updates in approximate planning and reinforcement learning. Our results demonstrated that proximal updates lead to more robustness with respect to noise. Several improvements to proximal methods exist, such as the acceleration algorithm (Nesterov) 1983 Li & Lin 2015). as well as using other proximal terms (Combettes & Pesquet 2009). J, which we leave for future work.
Acknowledgment
We thank Lihong Li, Pratik Chaudhari, and Shoham Sabach for their valuable insights in different stages of this work.

---

References
Arjovsky, M., Chintala, S., and Bottou, L. Wasserstein generative adversarial networks. In ICML, 2017.
Asadi et al. Lipschitz continuity in model-based reinforcement learning. In ICML, 2018.
Asadi, K., Parikh, N., Parr, R. E., Konidaris, G. D., and Littman, M. L. Deep radial-basis value functions for continuous control. AAAI Conference on Artificial Intelligence, 2021.
Beck, A. and Teboulle, M. A fast iterative shrinkage-threshoolinng algorithm for linear inverse problems, SIAM Journal on Imaging Sciences, 2009.
Bellemare, M. G., Naddaf, Y., Veness, J., and Bowling, M. The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 2013.
Bellman, R. E. Dynamic Programming. 1957.
Bertsekas, D. P. Incremental gradient, subgradient, and proximal methods for convex optimization: survey. Optimization for Machine Learning. 201
Bertsekas, D. P. Incremental proximal methods for large scale convex optimization. Mathematical Programming, 2011b.
Bertsekas, D. and Tsitsiklis, N. Neuro-dynamic programming. Athena Scientific, 1996.
Brockman, G., Cheung, V., Pettersson, L.,, Schneider, J., Schulman, J., Tang, J., and Zaremba, W. Openai gym, 2016.
Castro, P. S., Moitra, S., Gelada, C., Kumar, S., and Bellemare, M. G. Dopamine: A Research Framework for Deep Reinforcement Learning. 2018.
Combettes, P. L. and Pesquet, J.-C. Proximal Splitting Methods in Signal Processing. Fixed-point algorithms for inverse problems in science and engineering, 2009.
Dabney, W., Ostrovski, G., Silver, D., and Munos, R. Implicit quantile networks for distributional reinforcement learning. In International conference machine learning, pp. (096-1105, PMLR, 2018.
Fakoor, R., Chaudhari, P., and Smola, A. J. P3O: Policy-on policy-off policy optimization. In Conference on Uncertainty Artificial Intelligence, 2020a.
Fakoor, R., Chaudhari, P., Soatto, S., and Smola, A. J. Meta Meta-Q-learning. In International Conference on Learning Representations, 2020b.
Fujimoto, S., Hoof, H., and Meger, D. Addressing function approximation error in actor-critic methods. In International Conference Machine Learning. 2018
Hessel, M., Modayil, J., van Hasselt, H., Schaul, T., Ostrovski, G., Dabney, W., Horgan, D., Piot, B., Azar, M., and Silver, D. Rainbow: Combining improvements in deep reinforcement learning. In AAAI Conference on Artificial Intelligence, 2018.
Howard, R. A. Dynamic programming and markov processes. 1960.
Kim, S., Asadi, K., Littman, M., and Konidaris, G. Deepmellow: removing the need for target network in deep qelaarning. In International Joint Conference on Artificial Intelligence. 2019.
Kingma, D. and Ba, J. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
Knight, E. and Lemner, O. Natural gradient deep gelaarning. arXiv preprint arXiv: mtt.1183300488 2018.
Kober, J., Bagnell, J. A., and Peters, J. Reinforcement learning in roboties: survey. International Journal of Robotics Research, 2013.
10

---

Lee, D. and He, N. Target-based temporal-differene difference learning. In International Conference on Machine Learning, 2019.
Li, H. and Lin, Z. Accelerated proximal gradient methods for nonconvex programming. Advances in neural information processing systems, 2015.
Lillicrap, T. P., Hunt, J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D. Continuous control with deep reinforcement learning. In International Conference on Learning Representations, 2015.
Lin, L.JJ. Self-improving reactive agents based on reinforcement learning, planning and teaching. Machine learning. 1992.
Littman, M. L. and Szepesvári, C. A generalized reinforcement-leamme model: Convergence and applications. In ICML, volume 96, pp. 310-318. Citeseer, 1996.
Liu, B., Liu, J., Ghavamzadch, M., Mahadevan, S., and Petrik, M. Finite-sample samile analysis of proximal gradient TD algorithms. In Conference on Uncertainty in Artificial Intelligence, 2020.
Machado, M. C., Bellemare, M. G., Talvitie, E.. Veness, J., Hausknecht, M.. and Bowling, M. Revisiting the arcade learning cavironment: Evaluation protocols and open problems for general agents. Journal of Artificial Intelligence Research, 2018.
Maggipinto, M.. Susto, G. A., and Chaudhari, Proximal deterministic policy gradient. In International Conference on Intelligent Robots and Systems, 2020.
Mahadevan, S., Liu, B., Thomas, P., Dabney, W., Giguere, S., Jacek, N., Gemp, I., and Liu, J. Proximal Reinforcement Learning: A New Theory of Sequential Decision Making in Primal-Dual Spaces. arXiv, 2014.
Martinet, B. Regularisation, d'inéquations variationelles par approximations succesives. Revue Francaise d' d'informatique et de Recherche operationelle, 1970.
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Ried- miller, M., Fidjeland, A. K., Ostrovski, G., et al. Human-level control through deep reinforcement learning. Nature, 2015.
Moreau, J. Fonctions convexes duales et points proximaux dans un espace hilbertien. Comptes rendus hebdomadaires des séances de l'Acaéémie des sciences, 1962.
Moreau, J. Proximité dualité dans un espace hilbertien. Bulletin de Société Mathématique de France, 1965.
Nair, A., Srinivasan, P., Blackwell, S., Alcicek, C., Fearon, R., De Maria, A., Panneershelvam, V., Suleyman, M., Beattie, C., Petersen, S., et al. Massively parallel methods for deep reinforcement learning. arXiv preprint N0XY::1507.042966 2015.
Nesterov, A method for unconstrained convex minimization problem with the rate of convergence (1/k* 2). In Doklady an USSR, 1983.
Neyshabur al. Norm-based capacity control in neural networks. In COLT, 2015.
Parikh, N. and Boyd, proximal algorithms. Foundations and Trends in optimization, 2014.
Polson, N. G., Scott, J. G., and Willard, B. Proximal algorithms in statistics and machine learning. Statistical Science, 2015.
Puterman, M. L. Markov Decision Processes: Discrete Stochastic Dynamic Programming. 1994.
Reddi, S., Poczos, B., and Smola, A. Doubly robust covariate shift correction. AAAI Conference Artificial Intelligence, 2015.
Rockafellar, R. T. Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 1976.

---

Scherrer, B.. Ghavamzadeh, M., Gabillon, V., Lesner, B., and Geist, M. Approximate modified policy iteration and its application to the game of tetris. J. Mach. Learn. Res., 16:1629-1676, 2015.
Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P. Trust region policy optimization. In International conference machine learning, 2015.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. Proximal policy optimization algorithms. arXiv, 2017.
Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., al. Mastering the game of go without human knowledge. Nature, 2017.
Smimova, and Dohmatob, E. On the convergence of smooth regularized approximate value iteration schemes. Advances in Neural Information Processing Systems, 33, 2020.
Sutton, R. S. Learning to predict by the methods of temporal differences. Machine learning, 1988.
Sutton, R. S. and Barto, A. G. Reinforcement learning: An introduction. 2018.
Sutton, R. S., Szepesvári, C., and Maei, H. R. A convergent O(n) temporal-difference algorithm for off-policy learning with linear function approximation. In Advances in Neural Information Processing Systems, 2008.
Tesauro, gammon, a self-teaching backgammon program, achieves master-level play. Neural computation, 1994.
Tomar, M., Shani, L., Efroni, Y., and Ghavamzadeh, M. Mirror descent policy optimization, 2021.
van Hasselt, H., Doron, Y., Strub, F., Hessel, M., Sonnerat, N., and Modayil, J. Deep reinforcement learning and the deadly triad. arXiv, 2018.
van Seijen, H., Fatemi, M., and Tavakoli, A. Using logarithmic mapping to enable lower discount factors in reinforcement learning. Advances in Neural Information Processing Systems, 2019.
Wang, Y., He, H., Tan, X., and Gan, Y. Trust region-guidee proximal policy optimization. In Advances in Neural Information Processing Systems, 2019.
Wang, Z., Schaul, T., Hessel, M., Hasselt, H., Lanctot, M., and Freitas, N. Dueling network architectures for deep reinforcement learning. In International conference on machine learning, pp. 1995-2003. PMLR, 2016.
Watkins, C. and Dayan, P. Q-learning, Machine learning, 1992.
Williams, J. D., Asadi, K., and Zweig, G. Hybrid code networks: practical and efficient end-to-end dialog control with supervised and reinforcement learning. In Association for Computational Linguisties, 2017.
Zhang, S., Yao, H., and Whiteson, Breaking the deadly triad with target network. arXiv, 2021.
12


Reviews:
[{"review_id": "uEBXVy0QF9h", "reviewer": "Reviewer_Pjai", "summary": "The paper addresses the foundamental problem of Bellman operator in RL. The authors proposed a proximal Bellman operator that updates that incentivize the online network to remain in the vicinity of the target network. Theoretical analysis and toy task results suggested that the proximal Bellman Operator can accelerate convergence in the presence of high noise in value function approximation. Then the proximal value update is implemented on DQN and Rainbow agents and showed performance gain in many Atari games.", "questions": "Questions:\n1. I understand $\\alpha$ as the learning rate same as the orginal algorithm, is this correct?\n2. While the experiments are based on Atari which are mostly deterministic environments,  I wonder whether the proposed PMPI works even better in noisy environments. May the author provide some insights?\n3. Fig. 1, is $\\epsilon$ equal to $\\epsilon_k$ ?\n\nSuggestions:\n\n- Fig.2 and 5 are not that friendly to color-blind readers. Some efforts could be made to improved the plots.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "[Strength]\n1. The work tackles a generally interested problem in deep RL about target value network.\n2. The paper is basically well-written and easy to follow.\n3. Both theoretical analysis and experimental results are well-presented\n4. The proposed method is simple and effective.\n\n[Weakness]\n1. A new hyperparameter $\\tilde{c}$ is introduced and need be to tunned to achieve best performance.\n2. It is unclear that how can proposed PMPI generalize to continuous action case.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "fCrr-YgjPm4", "reviewer": "Reviewer_Djgd", "summary": "In this paper, the authors propose to improve reinforcement learning robustness by essentially adding a regularization term to the Q updates, so that the weight of the online Q network will stay closer to the weight of the target Q network. \nThe authors provide both theoretical and empirical results and show that when the proposed method is added to DQN and Rainbow baselines, it improves performance quite significantly on Atari tasks. ", "questions": "- My main question is: How is the proposed method fundamentally different from the alternatives? Why is it that it can achieve good performance improvement while others fail? (I also mentioned this in the previous section). In the current version of the paper, I don't quite find a very clear and comprehensive explanation for this. ", "limitations": "I saw the authors indicate they have discussed the limitations of the work, but I did not seem to find where the discussion is, maybe I missed it? Would be great if you can point it out for me. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- the simplicity of the method: as the authors discussed, the proposed method is quite simple and effective. And the simplicity brings a number of benefits. \n- clean presentation and adequate technical details: the authors did a very good job presenting the method and also the many technical details, overall, the results seem to be reliable. \n- interesting ablations: very important ablations to show that the effect of the proposed method is not the same as alternatives such as polyak averaging and learning rate decay. \n- theoretical support: the theoretical results are good. \n- significant results: although the proposed method did not improve on all tasks, but overall, the results show significant improvement in performance, and seems to be reliable results given the ablation provided and the discussion on hyperparameters. \n\nWeaknesses:\n- the novelty of the idea: the idea to make network weight stay close to the weight of an older version of the same network is not new. However, it would seem that this particular simple design will have a similar effect to changing polyak or learning rate decay, but the authors show that this is not the case and those ablations are very interesting. So probably should not be considered a major weakness. \n- would love to see some more discussion on how exactly the proposed regularization can have superior effect compared to alternatives such as using polyak and smaller learning rates. Currently, there are empirical results that indicate the effects are very different, but why? For example, if we use polyak instead, will it perhaps... always produce a much larger shift in network weights or maybe the output Q values? I think it will be great if the authors can dig deeper and provide a hypothesis on what is the fundamental difference here that allowed the proposed method to achieve much stronger performance than alternative regularizations. \n- would love to see some additional analysis on environments where the proposed method did not do well, in these cases, is it because the Q networks are now updated much slower (due to the fact that a consistent hyperparameter is selected for all environments)? Then for example, will increasing the learning rate in these environments recover the performance? Not a major point but would be good to see how that works. \n- would be great if we can see results also for tasks with continuous action spaces, such as MuJoCo, where there seems to be a larger problem with bootstrapping. But I understand this might be significant extra work. \n\n\nvery minor typos:\n- line 195 xCan\n\nSummary:\nOverall, I like this work, it is presented in a very clean fashion, with adequate details and good results. My current major concern is probably on the lack of explanation on how maintaining vicinity in the weight parameter space will give a very different effect compared to alternative methods? I am willing to increase my score if the rebuttal can address my concern. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "AnU4kxxK9GY", "reviewer": "Reviewer_Gkox", "summary": "The authors consider the class of deep reinforcement learning algorithms that are based on an online network that is updated at every interaction and a target network that is updated periodically. This technique, in general, ensures that the slower moving target network stabilizes the learning. \n\nThe paper proposes a type of regularization which keeps the online network in the proximity of the target network (this technique is referred to as the \"slowing down\" in the title of the paper).\n\nThe paper considers the DQN and Rainbow algorithms, and modifies them with the proposed approach. Experiments on the OpenAI Gym Atari game benchmarks show a significant improvement compared to the baseline algorithms. Experiments show that the performance improvement generated by technique depends on the level of noise in the reward function of the RL process.\n", "questions": "The paper provides sufficient information to make an informed opinion. \n", "limitations": "The paper adequately addresses the limitations of the work. The theoretical nature of the paper does not raise issues of negative societal impact. ", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ The paper is written very clearly. \n+ Whenever feasible, theoretical motivations of the approach are given. \n+ The paper clearly points out the parts where the current level of understanding does not allow for theoretical proofs.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept