Error bounds and dynamics of bootstrapping in actor-critic reinforcement learning
Authors: Ahmed J Zerouali
Douglas Blair Tweed
Venue: Accepted by TMLR ()

Abstract: Actor-critic algorithms such as DDPG, TD3, and SAC, which are built on Silver's deterministic policy gradient theorem, are among the most successful reinforcement-learning methods, but their mathematical basis is not entirely clear. In particular, the critic networks in these algorithms learn to estimate action-value functions by a “bootstrapping” technique based on Bellman error, and it is unclear why this approach works so well in practice, given that Bellman error is only very loosely related to value error, i.e. to the inaccuracy of the action-value estimate. Here we show that policy training in this class of actor-critic methods depends not on the accuracy of the critic's action-value estimate but on how well the critic estimates the gradient of the action-value, which is better assessed using what we call difference error. We show that this difference error is closely related to the Bellman error — a finding which helps to explain why Bellman-based bootstrapping leads to good policies. Further, we show that value error and difference error show different dynamics along on-policy trajectories through state-action space: value error is a low-pass anticausal (i.e., backward-in-time) filter of Bellman error, and therefore accumulates along trajectories, whereas difference error is a high-pass filter of Bellman error. It follows that techniques which reduce the high-frequency Fourier components of the Bellman error may improve policy training even if they increase the actual size of the Bellman errors. These findings help to explain certain aspects of actor-critic methods that are otherwise theoretically puzzling, such as the use of policy (as distinct from exploratory) noise, and they suggest other measures that may improve these methods.

Published in Transactions on Machine Learning Research (11/2023)
Error bounds and dynamics of bootstrapping in actor-critic reinforcement learning
Ahmed J. Zerouali
abmedd.erooaliimmall..cc uttooooooooooooooooooooooooom
Deportment of Physiology University of Toronto
Douglas B. Tweed
twoed. Seareddoogglls@uuoooonoo.
Deportment Physiology University of Toronto
Reviewed on OpenReview: https: // openreview. net/ net/forum? id= (d-CCJHJfSnY
Abstract
Actor-critic algorithms such DDPG, TD3, and SAC, which are built Silver's de- lerministic policy gradient theorem, are among the most successful reinforcement-lermiing methods, but their mathematical basis is not entirely clear. In particular, the critic net- works in these algorithms learn to estimate action-value functions by a "bootstrapping" technique based on Bellman error, and it is unclear why this approach works so well in practice, given that Bellman error is only very loosely related value error, i.e. to the inaccuracy of the action-valuc estimate. Here we show that policy training in this class of actor-critic methods depends not on the accuracy of the critic's action-value estimate but on how well the critic estimates the gradient of the action-value which is better assessed using what we call difference error. We show that this difference error is closely related lo the Bellman error finding which helps to explain why Bellman-based bootstrapping leads to good policies. Further, we show that value error and difference error show different dynamics along on-policy trajectories through state-action space: value error is a low-pass anticausal (i.c., bickward-in-time) filter of Bellman error, and therefore accumulates along trajectories, whereas difference error high-pass filter of Bellman error. Tt follows that techniques which reduce the high-frequency Fourier components of the Bellman error may improve policy training even if they increase the actual size of the Bellman errors. These findings help to explain certain aspects of actor-critic methods that are otherwise theo- retically puzzling, such as the use of policy (as distinct from exploratory) noise, and they suggest other measures that may improve these methods.
1 Introduction
Actor-critic methods (Witten 1977), (Barto et al. 1983 are a class of reinforcement-learning algorithms that work well in many applications, especially in continuous control tasks, where a simulated animal or robot learns a motor behavior, such as hopping, walking, or running, based on information from sensors in its body. Recent examples of these methods are DDPG (Lillicrap et al. 2015) and several algorithms that were developed from it, including TD3 (Fujimoto al., 2018) and SAC (Haarnoja al. 2018p. These latter two methods in particular have been very successful, matching or outperforming all rivals several benchmark tasks in OpenAI Gym and DeepMind Control Suite. But despite their success, these algorithms are not yet fully understood mathematically. In particular, there are open questions regarding the "bootstrapping" technique that is central to their operation, and which consists of using Bellman error to train a function approximator the critic to estimate the action-value function.
The central problem we will address paradox concerning this use of the Bellman error. As argued by Fujimoto et al. 2002 among others (Lillicrap et al.] 2015), FFujimoto et al.] 2018), Bellman error is

---

Published in Transactions on Machine Learning Research (11/2023)
not closely related to the accuracy of the critic it can be small even when the critic gives a very poor approximation to the true action-value. Nonetheless, critics trained to minimize the squared Bellman error do turn out well, in the sense that they can be used to train good policies. The purpose of this paper is to present mathematical results that partially resolve this paradox, and also help explain other aspects of actor-critic methods that are otherwise puzzling from a theoretical viewpoint.
The remainder of this paper is organized follows. In section 2 we briefly review actor-critic methods, specify which algorithms we will focus on, and formulate the precise questions that we address in this paper. In section we present main contributions:
(a) We argue that the pointwise accuracy or value error of the critic, which has been the focus of previous analyses, is not particularly good index of its ability to train policies. We introduce more relevant measure called the difference error, which evaluates the directional derivative of the critic's estimates along trajectories, and we relate this new mcasure to both the Bellman and value errors.
(b) We show that the difference error and the value error are complementary filters of the Bellman error.
(c) We establish a bound on the discrete Fourier coefficients of the Bellman error, which explains how the dynamics bootstrapping are governed by the regularity of the state dynamics, the policy, the rewards and the critic.
And in section we summarize our results and comment on how they could be built upon in future work.
2 Background
2.1
Reinforcement learning
The mathernatical setting is reinforcement-leariing problems where time advances in discrete steps. Let S S Rd and A S R2 denote the state space and the action space respectively. At each time t, the agent receives information about the current state s; of its environment (and we will focus on the case where that information is complete and accurate, or in other words where the state is fully observable). The agent then applies function μ : S - A, called the actor the policy, to choose Having made this choice, the agent gets scalar reward Te r(s,,a;) E E typically depending on both the state and action; we assume that the function S x A A R is bounded, as in most real-world applications. Time ticks forward to t 1, and the environment passes to its next state, St+1 = f(s,, az), where f is the state transition or state dynamics function. The reward and dynamics functions are deterministic, and the policy also deterministic apart from "exploratory" and "policy" noise terms, described below, that are added its outputs during training but not during testing. In recent applications, the policy is most often a deep neural network, and the aim of the reinforeement-lerniigg algorithm is to adjust the weights and biases of that network to yield an optimal policy, or in other words one that maximizes the discounted cumulative reward or value,
action, at p(st) E A.
V*(s)) A E (8r,
(2.1)
averaged across all possible starting points 8t of trajectories in state space. In this formula, y is a "discount factor" in the range (0, 1) which expresses the idea that rewards in the distant future matter less to the agent than more imminent rewards do. More generally, the final time point in the summation need not be oc, but we will assume that it is, to simplify the math. So in short, the aim is to adjust to maximize VP.
Actor-critic methods approach this problem by creating a critic, which a function approximator that is distinct from the policy network, and is trained to learn the action-value function Q" : S x A + R, which takes as input a state-action pair (s, a) and yields as output the quality of its outcome the total discounted cumulative reward that will result. from taking action in state and then choosing all subsequent actions
2

---

Published in Transactions on Machine Learning Research (11/2023)
in accordance with policy ju:
Q" a1) _ r(s), 0t)
+
Σ 7=1+1
y yd (Sr, ((s)))
(2.2)
Clearly Q* is closely related to VH, as (s, m())) (*)s,, again assuming (as we do throughout the paper) that the dynamics, reward, and policy are deterministic.
From 2.2 it follows that the action-valuc function obeys the Bellman equation (Belmann Barto 2018
1957
Sutton &
(",,,, at) = r az) + 70" ((
(2.3)
which we can write more simply as
Of rt + +
(2.4)
where we use the shorthand notation Qi Q" at), rz r(s,, ar), and Ui+1 Q" (s(+1,((544))) Note that the action a at time t is arbitrary while the action at time t + must be on policy: ac+1 p(s++1).
Usually, the critic Q S x A + R is trained by adjusting its parameters to shrink the Bellman error eB - R, given at (st, az) by
e B (1) & Q(s ar) ((s,,a)) 7Q (8++1,
(2.5)
more briefly by
B $ Q: -QQ++1,
(2.6)
with the same shorthand notation as in the previous paragraph.
What is noteworthy here is that Q is adjusted based on its own values at two time points, Qr and Q++1 a process called bootstrapping - rather than on any direct feedback about Q", the function it is trying to approximate. In effect, Q adjusted to obey more and more closely the Bellman equation (2.4). the hope that, if both Q and Q" obey that equation, then Q may resemble Q" in other ways as well. But in which respects, exactly, do need to make Q resemble Q", and what is the mathematical justification for hoping that this resemblance can be achieved by minimizing the Bellman error?
In addressing these questions, we will restrict our discussion to the large subclass of actor-critic methods that are off policy, that work with continuous state and action spaces, and that rely on the Silver et al. (2014) deterministic policy gradient (DPG) theorem - a result that mathematically justifies the procedure of improving the policy network by adjusting paramcters H" up the gradicnt calculated by the chain rule:
(Q"(s,a)
(000%
( )
(2Q"(s.) a)
@p(s)
(2.7)
80"
(s.o)=(e.u(ee)
80"
(More precisely, the DPG theorem shows that, in contimmous-control setting, 0Q/00" approximates the gradient of reasonable objective function for the policy see (Degris et al. 2012. Silver et al. 2014] [Imani et al. 2018)).
This subclass of algorithms includes many important actor-critic algorithms such as DDPG (iilicrap et al. 2015), TD3 (Fujimoto al., 2018), and SAC (Haarnoja et al. 2018), but excludes other highly successful actor-critic methods such as PPO (Schulman al.) 2017).
The justification for bootstrapping is less of problem for PPO than for off-policy DPG-based algorithms, which is why we focus on the latter class here. To clarify this point, note that PPO estimates Q" directly by summing discounted rewards along its most recent trajectory, and the critic network supplies a "bascline" or "control variate" to reduce the variance of the direct estimate. In this setup, it is well understood that even a very poor estimate of Q" can serve as a useful control variate, provided that it correlates with the true Q". In DPG-type algorithms however, the critic network Q the policy's sole source of information about Q", and so inaccurate critics are a more severe problem, and the need to justify bootstrapping is more pressing.
3

---

Published in Transactions on Machine Learning Research (11/2023)
Focusing our discussion on off-policy DPG-based contimnous-contron algorithms also motivates restriction to deterministic dynamics. In practice, the performance of these algorithms is commonly evaluated on deterministic tasks and environments such as HalfCheetah, Walker2d, Aut, Humanoid and so on in Mujoco and the OpenAI Gym/ /Gymmammmmmmmm package and the DeepMind Control Suite. On a more conceptual level, it is better to analyse the simpler, deterministic case first, and exlend the results to stochastic systems in a separate paper, as the mathematical treatment would be more involved and potentially less instructive.
2.2 Question
Why do DPG-based actor-critic methods perform so well in practice, given that they rely on an estimator of Q# that is trained using an error signal, e which is computed by bootstrapping, with no reference to Q"?
The usual justification a theorem of (Bertsekas Tsitsiklis 1996) which guarantees that if eB = 0 for all state-action pairs (s, a), then the estimator Q will be perfectly accurate, meaning that what we will call the value error zero,
(s. a Q(s, (s, =
(2.8)
for all (s,a) E Sx A.
Yet this standard rationale is not entirely reassuring, because applics only in cases where e is exactly zero throughout state-action space, whereas in practice e is never zeroed, and the best we can hope for is that it will be small enough. Worryingly in this context, it has been shown by (Fujimoto et al. 2022) that if e is not zeroed but merely bounded, then el may be very large even when e is small. Here we analyze further the relation between e" and action-value estimators in the setting of DPG-based actor-critic methods.
In the proofs that follow, we analyse the information about 0Q*/0u provided by a single sample or minibatch of Bellman errors. We make no assumptions about how the critic or policy have been trained before that batch was drawn, whether they have been trained at all. Our results hold even if the critic and policy are freshly initialized, with random parameters. Similarly, we will analyse the evolution of various error measures along infinite-duration trajectories, but we do not assume that the agent has traversed those trajectories, or any trajectories at all. The point is that, even if the agent has never had any encounter of any kind with its environment, still its critic and policy and the state dynamics and reward function together imply a continuum of infinite-duration trajectories filling the on-policy submanifold of stale-action space, and they also imply the errors that the agent would encounter it did traverse any portion of any of those paths, or if it computed Bellman and other errors based on tuples drawn from replay buffer.
3
Main results
3.1 Critics compute partial derivatives
As mentioned in the previous section, DPG-based actor-critic algorithms rely on the gradient 0Q/00u aQ/0a- 0p/00r to adjust the policy parameters 0" of μ S + A. Therefore, the critic learns Q" only in order to compute an estimate of the partial derivative /Q"/Oa. This is a key fact, because it means that during learning, the accuracy of the opprozimator Q iisself mallers less than that of the gradient estimate aQ/Oa. And therefore the value error el is a less relevant measure of the critic's quality than what we will call the difference error,
AQ (Q QQ)) (Q Q(¹) e -e = AA
(3.1)
Simply put, AQ is a better gauge than ef of the critic's gradient estimate because the gradient depends on how Q and Q" change from point to point across state-action space, not on their values at any one point. To express the same idea mathematically, we define the state-oction step Ax, (st+1 St, p(3++1) - at); and consider the first-order Taylor expansion
Q= Q++1 Au! VQ (((41)) 01Amm 12)
4

---

Published in Transactions on Machine Learning Research (11/2023)
for the approximator Q, well as similar expression for the true action-value function Q". Assuming that |m is small enough, we can write that
AQ = Act (VQ (( VQ" (1641,
A Ar! 1+41
(3.2)
QQ where 6+1 is the critic's gradient error. This equation shows that et AQ contains information about the gradient error which ef does not. Namely, AQ is approzimalely the inner product of E with the veclor Art, or in other words it approsimates the error in the directional derivative of the critic's 's estimates.
To summarize, (Fujimoto et al., 2022) and others have raised doubts about Bellman-basod learning, on the grounds that of is a poor proxy for + Our plan is to defend Bellman methods by showing that of is a very good proxy for the more relevant error mcasure e. One could of course study the relation between ef and the gradient error e, itself, or even the action- action-gradiend gradient error given by
QQ
(s, dQ da (s.
aQ"
Da (s.a),
but those relations are complicated, in part because they depend on the detailed contents of the replay buffer (see Appendix Aj. We have found it more informative to establish the relatively simple relation between the Bellman and difference errors and then, in Appendix A build on equation (3.2) to describe the relation between 2 and the gradient errors. There we will further highlight the suitability of AQQ an index of gradient error by showing that approximately linearly related the best estimate of c+1 obtained based on the information in the replay buffer.
0.0 that can be
Proposition 1. The difference error is related to the Bellman error 2.6 and the value error equation
2.8 by the
cl + 7
(1 -1)7)_m ei.
(3.3)
Proof. We subtract the right-hand side of of eQ, eB, and ei, and then simplify, to get
3.3
from the left, multiply by 7; expand based the definitions
74 + t - 7)e = =7(0++1 - Qt Qu + Q1) + (Q: - - -1 -()
= Qt rt - :::1=00
where the final equality follows from Bellman's 's equation.
With (3.3) in hand,
compare how of and e
AQ are bounded in relation to cf.
Regarding e: Fujimoto et al. (2022) have shown that if the Bellman error is bounded so that le S C' for constant C> 0, then
(3.4)
(1-7)
That is, |ee1 may be large as C/(1-7), for example 100 times larger than C if 7 0.99, which is common value used in many applications (Lillicrap et al. 2015 Fujimoto et al. 2018 Haarnoja et al. 2018
But the corresponding bound for 2Q is much better: Proposition 2. If lel1 < C, then
AQ 2C 7
(3.5)
Proof. From equations
3.3 and
3.4
le
AQ
e
+
(1 -
7)
o
<
C
(1-7)
20
7
7
7
(1 (1-7) 7)
5

---

Published in Transactions on Machine Learning Research (11/2023)
This bound is of particular importance. Again, for the concrete value ? 0.99 often used in practice, we see that | is at worst just over twice as large as the upper-bound on |eB], whereas |e can be as much as two orders of magnitude larger than |e In short, while e is a poor proxy for e it is good proxy for eAQ. And eA is the more relevant measure: in light of the discussion at the beginning of this subsection, eAQ better reflects the accuracy of the critic's gradient estimate 0Q/Ou, which is what matters for policy training. Therefore the bound (3.5) helps explain why DPG-based actor-critic learning works well in practice, as training Q to shrink e indirectly improves the approximation of aQ* /0a that is used for policy updates.
Of course, this finding does not resolve all the mathematical questions regarding actor-critic methods, and eeQ is not a perfect substitute for edoQ or evQ, as we explain in Appendix A However, more can be said once we clarify the underlying reason why e and eAQ have such different bounds, which we do in the next subsection.
3.2 of and E are complementary filters
Here show that of and e, e.9 are inversely related, in the sense that e, is low-pass filter of e whereas & AQ is a higl-pass filter of cf. Therefore it is not just the size of ef that influences ef and AQ Rather, a crucial factor is the temporal frequency of ef along the trajectories of the system, by which we mean the froquency of variation of c, with respect to t.. It follows that techniques that reduce this temporal frequency may improve the performance of actor-critic methods even if they increase eg itself.
In our discrete-time setting, a first-order linear line-invariant low-pass filter, or more simply a low-pass filter from now on, can be described by the equation
M/+1 = 03 + - 3)
(3.6)
where ze the filter's input, Ye is its output, and and | are positive constants (Oppenheim et al. 1998 Sec.3.9-11). The gain of this filter is a/8, which means that, given constant input 27 I. the filter's ' output Y will eventually converge to steady, equilibrium value of (a B)zz (In some papers, low-pass filters are defined to have a = 3, and therefore a gain of 1, in which case any non-unity scaling is applied afterwards by multiplying the filter output by the desired gain factor, but for us it will be convenient to treat the gain as an intrinsic property of the filter.)
Returning now to the Bellman equation 2.4 we can write this way:
Q r -1- 7) Qi
(3.7)
which has the same form 03.6 except that the time indices t and t + 1 have been swapped. In other words, the Bellman equation defines filter running backwards in time, or more briefly, an anticausal filter. Therefore we have:
Proposition 3. The function Qt is an anticausal low- filter of re, with a gain of 1/(1 - 7).
Similarly, 2.6 can be written
Q: = e + + (1- Q++1-
(3.8)
Subtracting 3.7 from (38 gives us:
Proposition 4. The value error ef is an anticausal low-poss filter of the Bellman error ef with constants a = 1 and B = (1 11-1) 7):
e =
Q
B [1 []]- e
(3.9)
and so we have
e
Q
(r- c.
(3.10)
7=1
Proof. We establish equation
3.10
From equation
3.9
we have
B
-e
Q
for all 2 1

---

Published in Transactions on Machine Learning Research (11/2023)
by multiplying both sides of this equality by y(r-1) and then summing over t & with & 0, 0, we get
8
20
20
E
1r-00
6
(r+1-0
Σ
(T- of
7=t
+=1+1
The gain of this filter is 1/(1 7) which in practice is usually large. For instance, if 0.99 then the gain is 100. This high-gain, low-pass filter behavior is the reason et can grow much larger than e,"
In this same discrete-time setting, a high-pass filter (Oppenheim et al. 1998 Sec.3.10) is described by the equation
Mt+ = a xx) + (1 B)ye
(3.11)
From this fact, together with the definition of AQ in (3.1,, and equation 3.10 it follows that: et
Proposition 5. The difference error g. an anticausal high-pass filter of the Bellman error ef with
1 and B 1- 9:
AQ c = (cf41 cel) - [1- -11-7)) c24
(3.12)
and so
2
= Σ ? (r-1) (-- - c
(3.13)
r=
Proof. We have
et
(Q++1 1++1) (Q: - Qt) (Qt+1 r44 7Q++2) (Qt r1 - -++++)
(Q++1 T(+1 - 7Q+4) (Q: - Fı - -Q(++) + (Qr42 - Q++1 - Qiiz + 2
(c+41 -e,²) + 7
AQ
to establish 3.12 Equation 3313 then follows by the same reasoning that of (3.10).
From this result, we know that ef shows the characteristic behavior high-pass filters (Oppenheim et al. 1998p: it ignores low-frequency events, and it responds to high-frequent events but then "forgets", its value fading to zero with the (backwards) passage of time.
So the main point of this section that, owing to their different filtering properties, of accumulates along trajectories whereas e, AQQ does not, and this is the underlying reason that the bounds on ei discovered by Fujimoto et al. 2022 are large whereas the bounds eQQ are small. Pushing this analysis further, we have:
Corollary 6. Let eB S A R be upper-bounded by C O, and suppose that there exists point (0) S x A al which
C
c 0n) 1-
Then along the trojectory starting at (s0, and following the policy sb, we have that e = 0 for all t E N.
Proof. As l < C' and the anticausal low-pass filter el has gain of 1/(1-7)) the time series e, can attain value of C/(1 ~) if and only if it reccives a strictly constant input e. - for all t E N. The vanishing AQ along the trajectory a()) (St, ( then follows from equation 3.13 of e
7

---

Published in Transactions on Machine Learning Research (11/2023)
In words, if the Fujimoto et al. bound (3.4] is tight at any point in state-action space, then the difference error vanishes everywhere along the trajectory through that point. In that sense, there is a partial trade-off between ef and e for any given bound on ef: the absolute value |e, reaches its maximum only when (e2 is minimal (i.e. 0). Another practical consequence, more clearly expressed by equation (3. (3.13). is that for any given magnitude of the Bellman error, the lower we can make the temporal frequency of variation of B the smaller |et will be. We elaborate on this point in the next subsection.
et
3.3 Controlling temporal frequency
What factors influence the temporal frequency of ef?? The standard way of analyzing frequency components of time series is to use the discrete Fourier transform, or DFT: given any finite-length real time series {an ( = (Tn. '.. IN-II. where N is a positive integer, the DFT of (rm)n=d is the N-element sequence { 1N k=0 given by (Stankovic 2015
--1
Tn exexp( (nexp((-22kkn//p i2rkn/NN) k 1).
0=
Here, the modulus [ corresponds to N times the amplitude of the component of /e of frequency 2rt/NN. Please see Appendix B for more explanations of the DFT and proof of the following bound on the frequency components of the Bellman error:
Proposition 7. Along any finäte-length segment {(su, ao), (8n, (sn,) N-1 of a trajectory, the DFT terms N-1 1eB1N-1 [e Jk=1
of the Bellman error satisfy the inequality
|efl S (N -2) 2)
{ {15A max Lip(u) (11+ Lip((r)
sin [k
+ [[1 + 2) - Qol + + - roll + + (Q2l (QwN),,
where Lip(r), Lip(Q), and Lip(u) are the Lipschitz constants of r S x A + R, S::xxx R, and μ:: S + A respectively, (s) A (s. - 8, and where I max maxs I
In simple terms, the bounds on |e_i depend on the frequency 2rk/N through the factor 2)/ (in//in(k//N) as well as on the "smoothness" of the functions r and Q across state-action space, and on the system's motion through that space, which determined by the policy μ and the state dynamics f. To put this result in context, we argued in section 3.1 that minimizing the difference error e, eAQ more important than minimizing the Q-function error < and in section 3.2. we showed that e, is a high-pass filter of et, meaning that the scale of |020 is governed by the absolute values |eEl for k near N/2 (the high-frequency components). The proposition above now explains how the choices of Q r, and will impact the upper- bounds on the |e in the sense that the less abrupíly these functions vary at local scale, the smaller | must be.
At this point, it may be helpful to visualize how some of these factors the regularity of p, and Q over S and A are interrelated and how they influence the temporal frequency of Q along an on-policy trajectory ((s,,)(s))))200) We locus on I + Q (st, ((()),, because it is one of the main variables that determines the temporal bchavior e, (We could of course have shown eB itsclf rather than Q, but plots of e :SxA-1 R and (+> B (st, (s,))(s))) are less easy to interpret.)
We will consider a very simple control system, a one-kilogram mass sliding on a horizontal frictionless rail in zero gravity. The state space C R of this system consists of the position and velocity s = (g. v) of the mass, while the action is a driving force applied to it, so that A = R. The dynamics function obtained by discretizing Newton's second law by Fuler's method, with time step ms.
the following:
Panel (A) represents a reference case. Here, for simplicity, the policy μ is linear and the reward function quadratic. Specifically, the policy's action is an applied force, expressed in newtons and given by p(s) -1(0 + 5(q - 0.3)), where q is in metres and in m/s. The reward is r(s,a) -33 x (g² + 10w2), which is bounded over the trajectories we consider in the figure.
8

---

Published in Transactions on Machine Learning Research (11/2023)
A)
B)
1000
3000
4030
C)
D)
3000
1000
2000
3000
4200
9090
Figure 3.1: Spatial factors affecting temporal frequency along state-space trajectories. Left of each panel: top is state space S (the blue plane) with one on on-policy trajectory; below is the graph of the approximator Q (the grey surface) with the projection of the same trajectory (black curve). Right of each panel: plot of t + Q (St, ((s)). (A) Low Lip(u) and Lip(r) with fine approximator Q (reference case); (B) Low Lip(u) and Lip(r) with coarse approximator Q; (C) Low Lip(u) and high Lip(r) with fine approximator Q; (D) Low Lip(r) and high Lip(μ) with fine approximator Q.
Lip(u) and Lip(r) are both low. The critic Q, consisting of 500 Gaussian filters trained by the recursive least squares method (RLS), is almost perfect fit to the true Q"(which we approximated very closely by summing discounted rewards along trajectories). The near-perfect fit. and the low Lip(r) induce a low Lip(Q), resulting in t + Q (St, p(st)) with few fluctuations.
Panel (B) depicts the situation where and are the same as in (A), but the approximator Q has only 50 filters. Its coarser approximation has a higher Lip(Q) than the reference case, and leads more fluctuations in the right-hand-side plot.
Panel (C) is a case where and Q are in (A), but r(s.a) = - -0.33 tanh(10g²)) instead of the reference quadratic. In this example, the larger Lip(r) induces larger Lip(Q") and therefore larger Lip(Q), which can be seen from the steep bumps in the graph of Q, again resulting in fluctuations in the right-ham hand plot.
Finally, Panel (D) shows a case where r and Q are (A), but the linear policy is replaced by a coarse approximation μ. In this case, not only does the trajectory fluctuate more in S because of the higher Lip(μ), but also obtain higher Lip(Q) because the rougher policy affects Q".
To summarize, Fig. 3.1 illustrates how the smoothness μ, r and Q over their domain spaces influences the temporal frequency of - Q (ss)), whose behavior carries over the Bellman error, which computed using and r.
The main lesson of Proposition and Figure 3.1 is that can shrink the high-frequency components of ef" by reducing I maxx, or by choosing simple, low-Lipschitz reward function r, or by smoothing out or Q, for instance with weight decay. As regards If |max. it usually not possible alter the function f which is determined by the state dynamics. But in some tasks it may be possible to train agent initially in

---

Published in Transactions on Machine Learning Research (11/2023)
simplified, lower-speed version of the environment it will ultimately operate in. This is sensorimotor form of curriculum learning (Bengio et al. 2009 Wang et al. 2027), and reflects the commonplace observation that humans do often begin learning a skill in a simplified or lower-speed setting, as for instance with training wheels or on a kiddic slope.
3.4 Relation to policy noise
Our focus has been on the mathematical justification for Bellman-based learning, but our temporal filtering results also shed light on another aspect of off-policy DPG-lype actor-critic methods, namely the use of "policy noise".
In many algorithms of this type, the agent stores large number of its past interactions with the environment in a "replay buffer", where the kth entry in the buffer is tuplet (sk, Og. &k) where 88 was the state at the beginning of an interaction, ag was the action taken, Th was the resulting reward, and sy was the subsequent state. The critic trains itself by drawing batches of these tuples from the buffer and for each one computing not its associated Bellman error e but a perturbed version of that error:
c (sk: (k) Tk 7Q'ht (s
(((()) + +),
(3.14)
where y is a zero-mean policy noise term (distinct from the "exploratory noise" that the agent adds to its actions when it interacts with the environment), and where Q'at designates a target network, which is close to but not identical with Q.
While the motivation behind explovatory noise is obvious, and the use of a target net has been shown to bring certain benefits (e.g. in (Fan et al.] 2020)); the use of the policy noise term in (3.14) is less clear conceptually, as its addition violates the rationale behind the learning rule. Indeed, the rationale for learning from " is the Bellman equation 2.3 but that equation holds only when the action at the subsequent state is on policy (i.e. a++1 = (( or, in the buffer, p(x(()); it fails if noise is added to sus$)) as in f3.14) And yet adding v does improve learning. Fujimoto et al. (2018), who introduced the idea of policy noise, proposed that it might help performance by smoothing the learned Q estimate. In light of our results we can add that the spatial averaging induced by v of the target value around ('a u(s')) may also be useful because it blurs out high-frequency components of Q. In other words, our findings here clarify the sense in which using equation (3.14) regularizes the critic's learning, and perhaps provide fuller explanation to why policy noise improves actor-critic performance.
4 Summary and future work
In this paper we have addressed the question, why do DPG-based actor-critic methods, which train a value- estimator Q based on the Bellman error e," perform well even though e," is not closely related to the value error ef and e, can be very large even when ef is small? The answer, we have shown, is that the accuracy of the policy's teaching signal aQ/ae depends less on the value error ef than on the difference error eA9, and AQ is closely related to c!" We have also shown that this difference error is high-pass-fill filstrie version of ef suggest ing that actor-critic performance may be improvable by laking steps to limit the high-frequency spatial components of the functions r S x A A R and Q: S x A + R, for instance by choosing tempered reward functions, and using policy noise and weight decay to temper the critic network Q. This being said, it would be interesting to build on this work to address other questions.
In the previous section, we established thcoretical results to explain how current techniques and practices improve the performance of certain actor-critic methods. An obvious question to address in future work is how such findings could be used for practical algorithm design. One line of thinking might be to develop algorithms that explicitly learn the gradient 3Q"/0a, instcad of relying on critics to estimate Q" only. Another relevant direction would be the design of methods that specifically temper the critic Q during training. For the sake of illustration, we include a brief example in Appendix that relates the use of twin critics to the smoothing of the estimator Q
On the theoretical side, the scope of the present article has been quite confined, for both mathematical convenience and readability purposes. On the one hand, we have focused on one aspect of the learning
10

---

Published in Transactions on Machine Learning Research (11/2023)
process, namely the information about gradient error that is contained in the errors ea and c computed along the paths of the current policy. A natural, though challenging, follow-up question is how much more information about 0Q* can be recovered as the policy evolves and e and eAQ are computed along an ever-changing set trajectorics.
We have also restricted our attention deterministic dynamics in this paper because of our own research interests and because of their relevance to the usual benchmarks for DPG-type algorithms. Extending the discussion to stochastic systems would obviously be relevant for applications related to stochastic optimal control, but would require heavier mathematical machinery.
Of course, many other open questions remain regarding the mathematical basis of actor-critic methods, including convergence conditions (Williams & Baird 1990), and the effects of sparse training data (Fujimolo et al. 2022
Acknowledgments
This work was supported by Mitacs through the Mitacs Accelerate Program.
References
Andrew G Barto, Richard S Sutton, and Charles W Anderson. Neuronlike adaptive elements that can solve difficult learning control problems. IEEE transactions on systems, man, and cybernetics, (5):834-846, 1983.
Richard E Bellman. Dynamic Programminng Princeton University Press, 1957.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th annual international conference on machine learning, pp. 41-48, 2009.
Dimitri Bertsekas and John N Tsitsiklis. Neuro-dynamie programming. Athena Scientific, 1996.
Thomas Degris, Martha White, and Richard S Sutton. Off-policy actor-critic. arXie preprinl arXiv: 1XXv:1205.44 2111205.48390 4839,,839998 2012.
Jianqing Fan, Zhaoran Wang, Yuchen Xie, and Zhuoran Yang. A theoretical analysis of deep q-learning. In Learning for Dynamics and Control, pp. 486 489. PMLR, 2020.
Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor-critic methods. In International conference machine learning, pp. 1587-1596. PMLR, 2018.
Scott Fujimoto, David Meger, Doina Precup, Ofir Nachum, and Shixiang Shane Gu. Why should i trust you, bellman? the bellman error a poor replacement for value error. arXie preprinl arXiv:2201.14417 2022.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International conference on machine learning, pp. 1861-1870. PMLR, 2018.
Ehsan Imani, Fric Graves, and Martha White. An off-policy policy gradient theorem using phatic weightings. In S. Bengio, Н. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Newral Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL httpps:/ppree http:////oceeenn...m... neurips httpiipp..cppppppeeeeee cc/paper filess/paper/2018/55 Bec21444d6775008t177700404141114 Paper.app..... www.eerpaapppp.............
Timothy P Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Sil- ver, and Daan Wierstra. Continuous control with deep reinforcement learning, preprint arXiv:1509.0299 2015.
Alan V. Oppenheim, Alan S. Willsky, and S. Hamid Nawab. Signals and Systems 2e. PrenticoHHll,, Inc., 1998.
11

---

Published in Transactions on Machine Learning Research (11/2023)
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimiza- tion algorithis. Xr preprinl (XXim:107.0660 00777, 2017.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deter- ministic policy gradient algorithms. In International conference on machine learning, pp. 387 395, Pmlr, 2014.
Ljubisa Stankovic. Digital signal processing: with selected topics: Adoptive systems, time-frequency analysis, sparse signal processing. CreateSpace, 2015.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Che Wang. Yanqiu Wu, Quan Vuong, and Keith Ross. Striving for simplicity and performance off off-policy drl: Output normalization and non-uniform sampling. In International Conference on Machine Learning, pp. 10070-100000 10000. PMLR, 2020.
Xin Wang, Yudong Chen, and Wenwu Zhu. survey on curriculum learning. IEEE Transaclions on Paltern Analysis and Machine Intelligence, 44(9):4555-4577 2021.
Ronald J Williams and LC Baird. A mathematical analysis of actor-critic architectures for learning opti- mal controls through incremental dynamic programming. Proceedings of the Sirth Yale Workshop on Adaptive and Learning Systems, pp. 96-101, 1990.
lan H Witten. An adaptive optimal controller for discrete-time Markov environments. Information and control, 34(4):286-25) 295, 1977.
A The gradient error and the difference error
Contimuing the discussion of section 3.1 the purpose of this appendix is to clarify the link between the difference error
AQ
(Q++1 - Q.) - (Q - Qt)) = Ac
that we study this paper, and the gradient errors:
0.Q AQ
8Q" da
6 da
(st, 0e)
(st, az)
and
QQ A VQ (8t+1, - VQ" (sL+1,
where as usual, the point (5r, 0r) E S x A has an arbitrary action, and point along on on-policy trajectory following μ4, with 8+41 = f(s)). For simplicity, we assume here that the state space and the action space are both Euclidean, specifically that Rd and RR.
E S x A is the next
Defining Ax. (8t+1 St, (1,11(1+1) at), we have the first-order Taylor expansion
Q: = Q++1 Ax! VQ (St41, (($:4))) (IAx,1)
for the approximator Q, as well as similar expression for the state-action value function Q". Assuming that |Ar,| small enough, we can write that
R Ari (VQ (5441. - VQ" ((
vQ = Aut e Ar!
(4411
0.Q a.Q)
(A.1)
where 6+1 the stale-gradient error. This equation shows that AQ is approzimalely linearly reloted to the component of TQ in the direction Ar, the point (st+1: (($+1)) S A. On its own, therefore, et AQ reflects only the component of e TQ along that single vector Art-
8,Q
12

---

Published in Transactions on Machine Learning Research (11/2023)
We can however say more if we consider the additional information provided by a replay buffer. To make analysis tractable and derive a general result, we will assume that we have an idealized replay buffer, in the sense that it is large enough that all the objects defined below make sense and all the sets are non-empty.
Suppose we have a replay buffer =
{(sk, ak rk, ( 1k) where (as is usual in practice) the transitions (sk, OK; rk, s()) are not. necessarily obtained by following the policy i only. Fixing a state E S, consider the subset of transition tuples:
B(s) {Sk, Okgy Tkes (ke) | Sb., =s i= 1, , ns C
whose next state is Let us introduce:
Az; (5%: - -(s,) okr) 20 (s) - el (((b)) - ( (k:),
with i = 1,... na. Next, let (s) be the (row) vector whose entries are the of (s),,, let (s) be the matrix whose rows are the vectors Axt, and let (s) Spang fp; [= be the linear subspace of A spanned by the "samples" Art. By equation A.I. we have that:
AQ(() s (s) e 0e (s, (())), B,
(A.2)
which shows that AQ (s) is approximately linearly related to the projection of vQ (s, p(s)) onto the subspace B,, (s) S S x A. Letting (s)+ denote the Peoor-Penrooee pseudo-inverse (s), equation (A.2) tells us that if the | are small enough, then (s) E AQ (s) is least-squares estimator for e e (s, ((s)).
Given these facts, how much information about e eQ (s, ((s)) or ea.l ((s)) can be recovered from eAQ (s, p(s))? The answer lies within the subspace (s) spanned by the Arg and therefore in the samples available in the subset B(s).
If the examples Ar; are varied enough to span the entirety of S x A, then for a given point E S, the values AQ will determine all the components of vQ (s, p())), meaning we can completely recover this vector using the difference errors. Similarly, if the Az, are such that A S Ws,,(s), then the difference errors will allow us to recover the gradient error in the action direction, namely c (s. p(s)). But these ideal cases are unrcalistic in practice, and more generally, it can be shown (though the proofs are beyond the scope of this paper) that even when the space (s) is maximal, in the sense that it contains all possible Ar compatible with the state dynamics and the policy μu, the action space A will not necessarily be included in (s), and in that case eÂQ will not mcasure how well the critic estimates the projection of aQ" /8a onto the orthogonal complement (s) CSX x A.
In summary, the difference error eQQ not a perfect index of the error in aQ" /0a/ In most cases will contain only incomplete information about eaq mixed with inessential information about the state-gradient error e,Q, as shown in A.1. But it is linearly related the best estimate of da that can be obtained given the information in the buffer, it is fairly simply related to the Bellman error eB, and it is in any case more informative than the value error el that has been the focus of previous investigations. Our aim in this paper has been to counter the claim that Bellman- based learning is suspect because e is bad surrogate for eQ, To do that, we have shown that eQQ is a more relevant error measure than el in this context, and that B is a good surrogate for eáQ
Proof of DFT bound
B.1 Discrete Fourier Transform
We start with a brief review of the Discrete Fourier Transform (DFT),, and establish a lemma that simplifies the proof of Proposition 7
13

---

Published in Transactions on Machine Learning Research (11/2023)
Recall that given any finite-length real time series {In) In-o fro, 11.... .N-1),, where N is positive whose terms are
integer, the DFT of is the N-element sequence { k== N-1
fx
eexpppiiwnm Ak 0 1),
(B.1)
where is a square root of -1, and the frequency variable wi - 2 for all == 0,... (N - 1).
N-1 the original time series (2) is recovered using the identity Stankovic Given the DFT terms (= 2015 S.c.3.1)
Σ (x)((n))))) Vn =0 0,, "....,N (N-1).
In
meaning that the quantity |&g//N represents the amplitude of the component exp(tuge) with frequency wk- Moreover, it is straightforward matter to compute that exp(+twx) exp(-iwN- for k = 1, (N-1). 1); which means that and wN- represent the same frequency of cycling but in opposite directions clockwise vs counterclockwise. Therefore the DFTT terms 24 corresponding to high frequencies are those with & close to N/2, while the terms corresponding to low frequencies are those with close to 0 or (N - 1).
Now we show the following general facts:
Lemma 8. Let { N-11 be a fimite-length discrete time-series.
The terms of ils DFT {&=]k- are given by do EN-1 on and
N-1
1- 1-exp( exp( (inwk) (In In-1)
24 =
(B.2)
rexp(-iwx
n=1
for k = 1,... (N - 1).
2. For all k: .,, (N 1), have that
(N 1) A
8x
Tmaxx
(B.3)
sin
W1 2
where Atmax A mI. Jzn xn-
+ Proof. To prove B.2 we write the terms the sequence {= 2 (Im Im 1), and using the geometric sums
1N-1 as a telescoping sum In = 20
exp( -inww) = exp(-imwa)
Σ 0=
expl- - -wnk)
N-1 exp(-inwy, (inwwnnw) = 0,
#=0
we have from B.1
that for all k = 1,... (N - 1),
N-1 N-1
4t
Σ
am Im-1)
exp(-inuue
Σ
Σ exp( (inws)) (Im xm-11)
n=1
m=1
--1
mm-1
N-1
exp( exp(-immwx)
exp((inww))
(em Fmn =
(Irm Im-1))
1 1-exp( (inp--ww))
And the case of l 0 is trivial.
14

---

Published in Transactions on Machine Learning Research (11/2023)
Next, from the identity sin(0) (exp(18) exp(-it)) /2i, it follows that for all m 0,..., , 1,
(pip--inww))
2i exp (-immw//2 /2) sin sin(mww//2 /2)
sin(mwwk
1 sin(wh
exp( iwo))
2i exp -iwk 2) sin (wx,
sin (wxk2)
The right-hand side of equation
B.2 can now be bounded as follows:
N
(N- 1) max sin(wx/2)
18x1 S
Fn Fn-1l
Pn Fn-1 sin 42
-1 NATmax
(2)
n=I,..,N -N-1)
proving equation
B33
B.2 Proof of Proposition
AQ is the result of We now burn to the Bellman error ef and the difference error AQ We have seen that e anticausal high-pass filtering of all the ef from to co. But if e is upper-bounded by C> 0, then for any finite T, we have from equation 3.13) that
T
Σ
r-
(ef+1- - + - ET+1
7=
T
<
7 --t (e - - + + +
Tmt
The term 2-T+1-1C goes to as increases, which means that values of e in the distant future have vanishing influence on e, AQ So with arbitrarily small error, we can consider long but finite time series of Bellman errors, and analyze their frequency components using the DFT terms {e) 1k=0 In this context, we derive a refinement of inequality [B.3..
Lemma 9. Suppose that W the discrete time series obtained by evaluating Lipschitz function Φ S x A + along a finile-length segment {(so, ao); (8a ((s))) N-1 of trajectory. The DFT terms N-1 then satisfy the inequality:
{dx) J
(N 2) |0al S 10h -dol sin(ww Lip(ø) /1 Lip(n)² 1 maxx
(B.4)
where Lip(ø) and Lip(μ) are the Lipschitz constants of & and μ respectively, where ff & o (s, and where |A max max,es (s)]
Proof. Applying equation B.2 to the DFT terms N=t yields:
N-1
1 exp( exx((innw)) innwk) (0n 2n-1);
22 - (6) 1o)
Σ
eexp(-iwp iww)
n=2
then modifying the proof of B.3 gives the inequality:
(N 2) max
1 < 10 dol
Øn Φn-1
sin (1nw /2)
1<=
15

---

Published in Transactions on Machine Learning Research (11/2023)
Since 8n f (1n-1; for = 2...., 1, have
An - Φn-1 = b (1 (f (8n-1, (())a11)))))))))) - (5
< Lip(ø) (8n-1, 1)) (S (8n-1, 1, (1]]) (1
x Lip(ø) /
sn-1| Lip(n) (8n (( - Sn-1
< Lip(o)v Lip(u²²
max IsASN-1
((=)1))())))) 5n-1
- Lip(o) Lip(n) max"
which completes the proof of the Lemma.
Continuing with the notation of this last Lemma, we can now establish:
Proposition Along any fonite-length segment ao), (8n, ((n))( of a trajectory, the DFT terms N-1 N-1 {eR) [k=1 of the Bellman error satisfy the inequality
[ < (N 2)
sin {152 max / + Lip(u)) [[1 L)ip((Q) + Lip(r)]}
[11 + 7) 1Q1 Qol + Ini - roll + (1Qxl + QN1).
Proof. From the definitions e Qn r 2Q and B.1 the DFT terms a of the Bellman error are given by
2h = Qx fv exp( (iiimm))@mmt ==1,.- (N - 1),
where Qx and Ps are the DFT terms of Q and respectively. For the sum on the RHS, direct computation yields
Σ exp( (www))Qn+1+ exp(lwx) (Q+-Qu+ Qu QN)
where QN -(N-1- PN-1
R 1 that
8 = (1 vexp(iwx)) Qu - Px + (exp(in))(o - QN),
(B.5)
and therefore
| S (1 1 + 1P + +(1
The incquality in the statement then follows by applying Lemma to the terms 2 and [Pa).
In summary, the inequality of Proposition relates the modulus of the DFT terms of the Bellman error to the state dynamics and the regularity of the critic Q, the reward function and the policy on the state-action space S x A. We also make the following remarks:
(a) Since IQ: Qol = Q (sI,H(s1)) Q(so, [o) and Ir, rol = |r (81, ((s))) - r(s0, an)), the term (1 1111 - Qol + Ir1 - rol in the inequality quantifies a gap incurred by transitioning from an arbitrary initial state-action (Su, ao) to the on-policy part of the trajectory {(sn, ((s)))) In the case where ag = ((s)), the inequality reduces to:
NN
1)
{150 max v1 Lip(u)² [[1 Lip(() Lip(r)] + (1Qol+ 11000+110 +Qvx))
sin
Fk 2
16

---

Published in Transactions on Machine Learning Research (11/2023)
(b) The scale of the term I obtained by following the policy n: S A.
Imax msx 1f (s, ((s))= s|| depends on the smoothness of the trajectory
(c) To clarify what the term If lmax represents, it might be useful to look an alternative definition of the state dynamics. Had we adopted the continuous-time dynamical systems notation, our state dynamics would be given by 84+1 constant | Imax would then be replaced by suPses IF (8,)
Imax
+ F (st, 04) for certain function F :S A + S. The
(d) The bounds on | are much larger for the low frequencies 2Tk/N than for the high frequencies, because sin(wx/2) = N/rk for k close to or (N - 1) (low frequency), while sin (w)/2)) = for close to N/2 (high frequency).
C On variants of TD3
In this appendix, we briefly describe a possible implication of our results, which may be worth exploring further. Many actor-critic algorithms, starting with TD3 (Fujimoto et al. 2018), use two critics (Haarnoja let al. 2018 Wang al., 2020). Each of the two critics, Q, for 1,2, has its own target, but trained based on both largets:
e, = (a(s,aa-r(ss0)) - min Q (s', 111
(s' ((s')+++
(C.1)
Fujimoto and colleagues advocated taking the minimum of the two target values, shown in [C.1 the grounds that critic outputs tend to risc in the course of learning, and so taking the minimum would help prevent Q drifting up and away from the true Q". But our results suggest that there may be value in using the twin targets to temper the Q-function, so as to reduce its figh-freyeeccy components, rather than or in addition to lowering it.
Figure C.I illustrates this idea. The blue lines in the plots learning curves for TD3 two benchmark continuous-control tasks from OpenAT Gym: Ant-v4 and HalfCheetah-v4. The orange lines are learning curves for a very slightly different algorithm, just like TD3 and with the same initializations but training the Q; based not on the lower of the two targets but on the one closer to zero, i.e. on the one whose absolute value is smaller. And the green lines are learning curves for a third version of TD3, where the Q₁ are trained based on the mean of the two targets. These latter two methods will tend to squeeze the Q function, not just from above as TD3 does, but also from below. The plots indicate that these mall--arree and mean-large methods may outperform standard TD3 on some tasks. So there may be value in investigating new ways of handling twin targets that temper Q rather than just lower it.
For each of the two lasks, we ran five trials of each of the three algorithms, all with the same five random seeds, and using the hyperparameters from the TD3 implementation at https:/ http://gihtub.com combbcccosstto www/sfujim////////////ooptttttst /DD3). Of course these results are by no means a thorough test of any algorithm. They are mercly a brief illustration of how concepts from this paper might be applied to algorithm design in the future.
17

---

Published in Transactions on Machine Learning Research (11/2023)
Ant-v4
HalfCheetah-v4
6000
15000
4000
10000
Return
Return
2000
5000
0.0
0.5
1.0
1.5
2.0
2.5
3.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
million timesteps
million timesteps
Figure C.1: Learning curves for the standard TD3 algorithm (blue) and two variants it: a small-target version (orange) that trains critics based on the smaller of two target-network outputs, and mcan-target version (green) that trains based the mean of the outputs of the target networks. The shaded regions represent the standard errors of the mean.
18


Reviews:
[{"review_id": "fXFVHcy2k8", "reviewer": "Reviewer_KAiw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths:\n- The paper is written clearly and concisely, and was very easy to understand. Thank you!\n- Proofs are written in-line, presented simply, and explained very clearly. Again, thank you, authors.\n- Sheds light on a problem that's very confusing (why deterministic AC algorithms are able to perform well with terrible critics) and under-studied.\n\n### Weaknesses:\n- The paper doesn't validate their theory with extensive empirical results, but does provide a demonstration. This isn't a dealbreaker for me, but the paper would be a lot stronger with more extensive experiments/demonstrations.\n- Details on plots and experiments are missing.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the use of Bellman Error (BE)-minimizing algorithms for learning the critic in deterministic actor-critic (AC) algorithms. Specifically, it sheds light on why BE-based critics perform well in DDPG, TD3, and SAC when they tend to not be relied on by other AC algorithms like PPO due to their high Value Error (VE). The paper shows that this is because the deterministic AC algorithms only use the critic to estimate the direction to improve the policy, a shift-invariant quantity that is not harmed as badly by the BE being a poor proxy of VE than AC algorithms that rely on critic estimates to have low VE.\n\nSpecifically, the paper:\n1. points out that deterministic AC algorithms only use the critic to estimate the direction of policy improvement (undervalued insight in my opinion).\n2. proposes the Difference Error as a more relevant measure of error for this purpose.\n3. derives a bound on the Value Error in terms of the Difference Error, and shows that it's significantly better than the corresponding bound in terms of the Bellman Error.\n4. interprets the VE as a low-pass filter of the BE and Difference Error as a high-pass filter of the BE, to show why the bounds are so different and why the VE can grow so much larger than the BE.\n5. uses the discrete Fourier transform to break the Bellman Error of a trajectory into frequency terms and bounds their magnitude in terms of several quantities.\n6. discusses possible approaches to reducing these terms, and demonstrates that two specific approaches improve performance on Ant-v4 and HalfCheetah-v4.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "### Important changes:\n- More information about the plot could be helpful for understanding it. For example, the plot of the state space is 2D, so presumably the position and velocity of the bead on the wire? All axis information would be good to include on the plots, actually.\n- More information about the experimental methodology for the plots in Figure 4.1. What hyperparameters were used for each method? Are the shaded regions confidence intervals? If so, what confidence level?\n- It would be much better to present evidence that the performance gain observed in the demonstrations is due to the changes made in the algorithms. Consider building on Section 3.3 by comparing the magnitudes of the DFT terms of the observed Bellman Errors for each of the algorithms. If the modified algorithms exhibit smaller high-frequency components than the unmodified algorithm, that would be much more convincing than simply showing a performance improvement.\n\n### Less important changes:\n#### Section 2.1\n- The reward and state transition functions are not usually defined as deterministic. This would be a big change from the usual setting, and if the analysis relies on this fact it could limit the usefulness of the paper's findings (a lot of issues in RL go away with deterministic rewards and transitions). \n- Similarly, the agent's policy is not necessarily (or even usually) deterministic. Do the authors mean that the policy is deterministic in the algorithms considered in the paper?\n- The discount factor can be 0 (then value becomes immediate reward), but not 1.\n- Much of the presentation in this section is specific to a subset of RL, and it would be better to be clear about this. E.g., $Q^\\mu(s,\\mu(s)) = V^\\mu(s)$ is only true for deterministic policies.\n- It would be good to more clearly state that the Off-Policy Deterministic Policy Gradient theorem these algorithms rely on is based on an approximation (dropping the gradient of the action value function from the derivation entirely) that is only valid in the tabular setting (see [Errata B in Degris et al. (2012)](https://arxiv.org/pdf/1205.4839.pdf)), and can be a problem when using the resulting algorithms with function approximation ([Imani, 2018](https://proceedings.neurips.cc/paper_files/paper/2018/file/3ef815416f775098fe977004015c6193-Paper.pdf)).\n\n#### Section 3.1:\n- \"This bound helps explain why DPG-based actor-critic learning works well in practice.\" It might be better to explicitly say why, as this was not clear to me at first. Is it because DPG-based AC algorithms use the BE-minimizing critic to estimate partial derivatives (that are shift-invariant), which is harmed less by the BE being a bad proxy for value error than algorithms that use the critic in ways that depend on low VE?\n\n#### Section 3.2:\n- More context/explicit explanation would be helpful for the last paragraph of 3.2. Why would we want $e^{\\Delta Q}_t$ to be small? I can infer it's because a smaller difference error means better estimates of partial derivatives which means better actor updates?", "broader_impact_concerns": "I don't see any ethical issues specific to this paper beyond those faced by the whole field.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "adNK3oPfRa", "reviewer": "Reviewer_4gdd", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Soundness\n=========\n\nThe motivation of the difference error (Eq. 3.1) is not fully convincing. As we are only interested in the accuracy of the gradient of the Q function *with respect to the action*, the error in our Q values does not need to be absolutely constant ($c$), but it suffices if it is constant in actions ($c(s)$). However, the difference error compares Q-values of two different time steps that often involve different states. Hence, if the learned Q-function differs from the true Q function only in terms of an arbitrary state value error $c(s)$, the difference Error can be large, despite resulting in the correct partial derivative wrt the action.\n\nI do not see the purpose of Proposition 2. Doesn't it just state that the loss function tends to take smaller absolute values?\n\nCorollary 6 seems to be wrong and useless. Consider a very large C, large enough to ensure that it upper-bounds the Bellman error. The corollary states that any Q function with a large value error of $\\frac{1}{\\gamma}C$ at $(s\\_0, a\\_0)$ will have zero temporal difference error at every time step. Which clearly can not be the case in general. The proof states that $e\\_{t}^{Q}$ cann only be non-zero at $(s\\_0, a\\_0)$ if the Bellman error is constant. However, this seems to assume that the Q function is trained in a certain way, which is not stated in the Corollary. Furthermore, what is the point of assuming that the Q function is trained along a single infinite trajectory (which is never the case in practice) and that this training will converge to a particular value (without providing any reason why it should converge to that value)?\nThe next paragraph argues that this leads to a partial tradeoff: When the Bellman error is constant, the Bellman difference error will be zero, and hence, the paper argues, when maximizing the Bellman error, it will be always at the upper bound $C$ and therefore constant. However, I don't think that this argumentation makes sense, because maximizing the Bellman error would in general not make it constant.\n\nThe paper argues that Proposition 7 (a bound on the Bellman-error) helps to better understand the benefit of policy noise. Whereas Fujimoto et al (2018) introduced it as a kind of regularization to smoothen the Q-function wrt the actions to reduce overfitting , the paper argues, that it should rather be understood as a method for smoothing the Q-values wrt time. However, in my opinion this motivation is less convincing than the one proposed by Fujimoto because policy noise is only very indirectly related to temporal smoothness.  \n\nAll the analysis in the paper considers the different errors when assuming a fixed trajectory. It is not clear how this relates to replay buffers consisting of many different episodes and different policies.\n\nClarity\n=======\nThe purpose of Fig. 3.1 is not clear. It shows different variation of the same simple task and the state-action values along a trajectory. I think the intention of the figure is to show that more difficult task and function approximation errors can lead to less smooth (in time) Q-values. However, four simple examples are not are not indicative of a general trend (I do agree that there should be a general tendencies to smoother Q-functions for simpler tasks, so even if the results were significant, they were hardly surprising). In terms of presentation, one needs to read a rather long paragraph in the caption to understand what the figure is showing. Adding legends would would be preferable.\n\nThe function $f$ is not sufficiently well defined. It seems to be refering to the closed-loop deterministic system dynamics for a given policy.\n\nEvaluation\n==========\nThe experimental evaluation is insufficient to undermine the claim that using Q networks with smaller absolute values outperform using the minimum Q values. The paper only shows two Mujoco environments. Furthermore, the paper contains insufficient details about the chosen hyperparameters, and the procedure for selecting them.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper argues that minimizing the Bellman error is not the ideal objective for off-policy actor critic methods, because the deterministic policy gradient only requires an approximation of the $\\frac{\\partial Q(\\mathbf{s}, \\mathbf{a})}{\\partial \\mathbf{a}}$, but not necessarily a good approximation of $Q(\\mathbf{s},\\mathbf{a})$. Instead, the paper proposed to minimize the \"difference error\" the true difference in Q values along subsequent states, and the corresponding according to the learned Q function. The paper argues that the value-error corresponds to a low-pass filter of the Bellman errors along a trajectory, whereas the proposed difference error corresponds to a high-pass filter. Based on this perspective, the paper evaluates a variation of TD3 that instead of using the minimum of both Q-networks, use the one with smaller absolute value, and shows that this procedure slightly improves learning performance on two selected Mujoco experiments.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "* The experimental evaluation needs to be significantly expanded. More different environments need to be considered, ideally with different forms of reward function (going beyond locomotion). The procedure for selecting hyperparameters, and the chosen hyperparameters need to be clearly stated.\n\n* The main insight needs to be clearly stated. \n\n* The difference error needs to be better motivated, in particular the effect of state dependent errors $c(t)$ needs to be better discussed.", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "gOBqyqrL8q", "reviewer": "Reviewer_PJ8w", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Overall the paper is well-written and is easy to understand. Good job!\n2. The problem this paper studies is very valuable and interesting.\n3. The approach that uses the Fourier analysis and high/low pass filters seems novel to me.\n\nWeaknesses:\n\n1. The main weakness is that it is unclear how the difference error ($(Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t) )- (Q_\\mu(s_{t+1}, a_{t+1}) - Q_\\mu(s_t, a_t) )$) is related to the partial derivative of the action-value error w.r.t. the action ($\\frac{\\partial Q(s_t, a_t)}{\\partial a_t} - \\frac{\\partial Q_\\mu (s_t, a_t)}{\\partial a_t}$). This is a key step that justifies the value of studying the difference error.\n\n2. I am not sure what can I learn from Proposition 7. This proposition shows that both the high-frequency and the low-frequency parts of $e_t^B$ have the same dependence on Lip(\\mu), Lip(Q), and Lip(r). Before you said, \"The practical consequence is that, for any given magnitude of Bellman errors, the lower we can make the temporal frequency of variation of $e^B_t$, the smaller $e^{\\Delta Q}_t$ will be.\" So from this proposition, I think what we can learn is that by reducing Lip(\\mu), Lip(Q), and Lip(r), the magnitude of both high- and low-frequency parts of $e^B_t$ will be smaller. Is this what readers should learn from this proposition? If it is, you should make this point clear.\n\n3. If my previous understanding is correct, I doubt if proposition 7 provides useful knowledge for algorithm design. Specifically, you said \"So the lesson of Proposition 7 and Figure 3.1 is that we can shrink the high-frequency components of $e^B_t$ by reducing ||f^{\\Delta}_\\mu|| or by choosing a simple, low-Lipschitz reward function r or by smoothing out \\mu or Q, for instance with weight decay.\" Both ||f^{\\Delta}_\\mu||, and r are determined by the problem. And they being low Lipschitz basically means that they don't vary across different state actions. Smoothing out $\\mu$ and $Q$ drives them far away from optimal policies and $Q_\\mu$. So I don't see why proposition 7 says anything useful about designing algorithms that achieve a low Bellman error.\n\n4. It appears that filters are more like providing a different way to look at the problem, rather than giving new results. For example, equation 3.9, which does not need filters, is enough to show that $e_t^Q$ can be much larger than $e_t^B$. If my understanding is correct, the authors should make this explicit. Right now, it is not clear why you want to introduce filters.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "By the deterministic policy gradient theorem, it is important that the gradient of the estimate of the action-value function is accurate. This paper starts from this fact and then makes the following contributions:\n\nThis paper introduces the difference error, which better estimates the error in the gradient of the action-value function compared to the value error, and relates the difference error to both the Bellman error and the error in the Q-function estimates. \n\nThis paper shows that the difference error and the error in the Q-function estimates are complementary filters of the Bellman error. \n\nThis paper establishes a bound on the discrete Fourier coefficients of the Bellman error, which explains how the dynamics of bootstrapping are governed by the regularity of the state dynamics, the policy, the rewards, and the Q-function estimator.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Why did you draw $t \\to Q(s_t, \\mu(s_t))$  instead of $e_t^B$ in Figure 3.1? Don't you want to illustrate Proposition 7, which concerns the DFT terms of $e_t^B$?\n\nIn Figure 3.1's caption, you said \"In panel(A), the policy is a simple linear one, and the reward function is a simple quadratic with a small Lip(r). Consequently, Lip(Qµ) is also small, and so is Lip(Q), because the critic’s estimate is accurate.\" If your critic's estimate is accurate, the Bellman error is 0, regardless of the structure of the reward setting and the policy $\\mu$. Why did you require that the reward is quadratic and the policy is linear?\n\nAgain in Figure 3.1's caption, you said \"In panel(B), the critic is less accurate and so Lip(Q) is increased, leading to high-frequency ripples in the time plot.\" I don't see how the accuracy of the critic is related to Lip Q. What if you have a Q being a constant vector?\n\nIn section 2, you need to define the state and action spaces, the reward function.\n\nYou need to justify why to consider deterministic environments and policies.\n\nIf you have infinite state and action spaces, the series in equation 2.1 may not exist.\n\nActor-critic methods do not necessarily use a critic \"network\". \n\nRight above equation 2.2, you need to say what policy $\\mu$ is.\n\nEquation 2.7, needs to write $\\frac{\\partial Q^\\mu(s, a)}{\\partial a}$. $\\frac{\\partial Q^\\mu}{\\partial a}$ does not make sense.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors improved their submission a fair bit based on the reviewer's feedback, which helped with clarity and motivation. Most of the reviewers agree that that the theoretical results are well-motivated and of interest to researchers working with actor-critic methods. I tend to agree with them, and am recommending acceptance based on the TMLR guideline to welcome "theoretical studies yielding new insight into the design and behavior of learning in intelligent systems".

Some final comments from some of the reviewers:
*  It would have been preferrable to run the experiment and compare the magnitudes of the DFT terms of the observed Bellman Errors for each of the algorithms
*  $e_t^{\Delta Q}$ contains two parts: $\frac{\delta Q}{\delta a}$ and $\frac{\delta Q}{\delta s}$, instead of $\frac{\delta Q}{\delta a}$ alone. So it is still not quite satisfying to use $e_t^{\Delta Q}$ to justify the behavior of deterministic policy gradient.
*  Equation A.1 states that the Q-Error and the gradient-error are linearly related when ignoring non-linear effects between the inputs and outputs of the Q function. The latter assumption seems problematic, as the nonlinear effects can be large in general.
*  The claim that the Bellman error is a good proxy for minimizing the difference error might need more justification.
Decision: Accept (poster)