Explaining Off-Policy Actor-Critic From A Bias-Variance Perspective
Authors: Ting-Han Fan
Peter Ramadge
Venue: ICLR 2022 Submitted (2022)

Abstract: Off-policy Actor-Critic algorithms have demonstrated phenomenal experimental performance but still require better explanations. To this end, we show its policy evaluation error on the distribution of transitions decomposes into: a Bellman error, a bias from policy mismatch, and a variance term from sampling. By comparing the magnitude of bias and variance, we explain the success of the Emphasizing Recent Experience sampling and 1/age weighted sampling. Both sampling strategies yield smaller bias and variance and are hence preferable to uniform sampling.

Under review as a conference paper at ICLR 2022
EXPLAINING OFF-POLICY ACTOR-CRITIC FROM A BIAS- PERSPECTIVE
Anonymous authors Paper under double-blind review
ABSTRACT
Off-policy Actor-Critic algorithms have demonstrated phenomenal experimental performance but still require better explanations. To this end, we show its policy evaluation error on the distribution of transitions decomposes into: a Bellman er- ror, a bias from policy mismatch, and a variance term from sampling. By compar- ing the magnitude of bias and variance, we explain the success of the Emphasizing Recent Experience sampling and 1/age weighted sampling. Both sampling strate- gies yield smaller bias and variance and are hence preferable to uniform sampling.
INTRODUCTION
A practical reinforcement learning (RL) algorithm is often in an actor-critic setting Lin Precup et al.] 2000) where the policy (actor) generates actions and the Q/value function (critic) evaluates the policy's s performance. Under this setting, off-policy RL uses transitions sampled from a replay buffer to perform Q function updates, yielding new policy æ. Then, finite-length trajectory under π is added to the buffer, and the process repeats. Notice that sampling from a replay buffer an offline operation and that the growth of replay buffer is an online operation. This implies off- off-policy actor-critic RL lies between offline RL (Yu et al., 2020:; Levine et al. 2020) and on- policy RL (Schulman al. 2015 2017). From bias-variance perspective, offline RL experiences large policy mismatch bias but low sampling variance, while on- on-policy RL has a low bias but high variance. Hence, with a careful choice of the sampling from its replay buffer, off-policy actor-critic RL may achieve a better bias virianariance trade-off. This is the direction we explore this work.
1992
To reduce policy mismatch bias, off- off-policy RL. employs importance sampling with the weight given by the probability ratio of the current to behavior policy (the policy that samples the trajectories) (Precup et al. 2000; Xie et al. 2019 Schmitt et al. 2020). However, because the behavior policy is can either estimate the probability ratio from the data (Lazic al.) 2020 Yang et al., 2020 Sinha et al. 2020) or use other reasonable quantities, such as the Bellman error (Schaul al. (0166). as the sampling weight. Even using naive uniform sampling from the replay buffer, some off-policy actor-critic algorithms can achieve a nontrivial performance (Haarnoja al. 2018 Fujimoto al., 2018). These observations suggest we need better understand the success of off-policy actor-critic algorithms, especially in practical situations where a fixed behavior policy is unavailable.
usually not given practice,
Our contributions are as follows. To understand the actor-critic setting without a fixed behavior policy, we construct non-stationary policy that generates the averaged occupancy measure. We use this policy reference and show the policy evaluation error in an off- off-policy actor-critic setting decomposes into the Bellman error, the policy mismatch bias, and the variance from sampling. Since supervised learning during the Q function update only controls the Bellman error, we need careful sampling strategies to mitigate bias and variance. We show that the 1/age weighting or its variants like the Emphasizing Recent Experience (ERE) strategy (Wang & Ross 2019) are preferable because both their biases and variances are smaller than that of uniform weighting.
To ensure the applicability of our explanation to practical off-policy actor-critic algorithms, we adopt weak but verifiable assumptions such as Lipschitz Q functions, bounded rewards, and a bounded ac- tion space. We avoid strong assumptions such fixed well-explored behavior policy, concentra- tion coefficients, bounded probability ratios (e.g., ratios of current to behavior policy), and tabular or linear function approximation. Hence analysis is more applicable to practical settings. In

---

Under review as a conference paper at ICLR 2022
addition, analysis suggests that 1/age-based samplings (e.g.. ERE, ERE. apx, 1/age) have advan- tages in bias and variance. Our experiments verify that SAC (Haarnoja et al. 2018) with 1/age-based samplings outperform the prior work. Thus, our results not only provide theoretical foundations for practical off-policy actor-critic RI. algorithms but also achieve better performances.
2
PRELIMINARIES
2.1 REINFORCEMENT LEARNING
Consider infinite-horizon Markov Decision Process (MDP) (S, A, T, 7) where S, A are finiteddimensional continuous state and action spaces, r(s,a) is a deterministic reward function, y (0, 1) the discount factor, and T"(s'ss,a a) is the state transition density; i.e. the density of the next state s' given the current state and action (s, a). Given an initial state distribution the objective RL is to find a policy that maximizes the d-discounted cumulative reward when the actions along the trajectory follow æ.
oc Σ
(r) ~ po. a x-16b),, 8841 T(-18s, (i))
max ((x) = max
(I)
Let pi(s|po, n, T) be the state distribution under क at trajectory step i. Define the normalized state occupancy measure by
Pro (s)
pelss n, T).
(2)
Ideally, the maximization in is achieved using a parameterized policy xe and policy gradient updates with (Sutton et 1999 Silver al., 2014):
V V (Te) (1 -) (3.0)~038 ( log (T(als)) as)
(3)
Here P7o (s, a) Po (a)))( is given in (2) and QTe is the Q function under policy ne:
Σ > (r)) az) =, au a, a (-11s)), 8:11 T(+ss; as)
(s, 0)
(4)
Off-policy RL estimates Q" by approximating the solution of the Bellman fixed -oint equation: (B (B*)")(s,a)) r(s, a) + (Tsss(()) Q") d') Q" (s.
It is well-known that Q" is the unique fixed point of the Bellman operator D=, Hence if (B" (), a) = a)s, then Q may be a "good" estimate of Q". In the next subsection. we will see that an off-policy actor-critic algorithm encourages this to hold for the replay buffer.
2.2 OFF-POLICY ACTOR-CRITIC ALGORITHIM
We study off-policy actor-critic algorithm of the form shown in Alg. In line 2, for episode index e, ne samples one trajectory of length L. The transitions in this trajectory are then added to the replay buffer. Since the policies for different episodes in the replay buffer are generally inconsistent with the current policy. Notice the trajectory is simply collected by π². not perturbed version of (e.g., gaussian corrupted version of pr*).
distinct, the collection of transitions
Line is supervised learning that minimizes the Bellman making (B" (),s a) Q(s, a) for (s in the replay buffer. When this holds, we will prove that the "distance" between Q and Q=" become smaller over the replay buffer. This is crucial step for line 4 to be truly useful. line 4, Q=" is replaced by Q, and the policy is updated accordingly.
of Q using gradient descents,
In practice, line 3 is replaced by mini-batch updates (Fujimoto al. 2018 Haarnoja et al., 2018 where the summation of ((2)) is approximated by sum the mini-batches. In section 5.2 we show that a weifohte-weigtted mini-batch sampling biases learning towards older samples; this motivates the need for countermeasure.
2

---

Under review as a conference paper at ICLR 2022
Algorithm Off-poolicy Actor-critic Algorithm
Require: Parameterized policy ग" = ne, and Q function estimate Qs. Learning rate a. for episode e 1,2, ... do
2: Sample a length-L trajectory {(5 = with initial distribution (o(s) and policy #" (als).
Evaluate the Bellman enror as J(Qs) E/o (Qo(s). (B= (0) a))) and
update Qo Φ Ø a a v
4: Approximate Eq. 3 as VoJ(To) = (1 - (-7)- ( (Vo log (o a)] and up-
date as P--1 = le + a (TT))
5: end for
Note that Alg. D seems to be inconsistent in the horizon because the Q function, Eq. (4). is defined in the infinite horizon but the trajectories are finite-length. In Corollary L we will address this inconsistency by approximating the Q function using finite-length trajectories.
2.3 THE CONSTRUCTION OF OUR BEHAIIIR POLICY
Although Alg. [ doesn't have fixed behavior policy, in Lemma construct non-stationary policy that generates the averaged occupancy measure at every step. This describes the averaged- over-episode behavior at every trajectory step i of the historical trajectory {(s,, af) 1,1=0 We
1.N.N
hence define be our behavior policy and use
reference when analyzing Alg.
The construction is as follows. Denote the state distribution at trajectory step in episode e as (f(s) Pe(s) π², T)) By Eq. (2). Poo is the state occupancy measure generated by (Pu, πh, T)) Intuitively, 0%v describes the discounted state distribution starting at trajectory step 0 in episode e.
More generally, define P% the state occupancy measure generated by (pf, nT, ().. Then, P describes the discounted state distribution starting trajectory step in episode
P (8) (1 7)
(((s
(5)
Behavior policy through averaging. Since Alg. considers trajectories from all episodes, the average-over-episodes distribution e()) N Ee Po will be of interest. Namely, g(9) is the average of all occupancy measures starting at step i. To describe the average-over-epioode behavior at step want policy that generates ( and Eq. (5) helps construct such policy. Concretely, let p.. म. (als) be the averaged state distribution and the averaged policy at step i, respectively.
N
(als) (s)
(0) (S)
Po (s), 2 (s)(s), Palss)
(6)
P (s) ΣN
Lemma shows x! in Eq. c is notion of behavior policy in the sense that (P,, mP. T) generates
i.e, generates the averaged occupancy measures when the initial state follows P,. Since T. describes the averaged discounted behavior starting at step i, we define to be our behavior policy. This is key to analyzing the policy evaluation error in Alg.
a. Lemma 1. Let Pp: (s) be the normalized state occupancy measure generated by (P., (G,x,,)),
T). Then Po. (s) a.e. and hence from Eq. (6) NN IN 0% (a)m = P (8)=² (als) a.e.
( (s)
RELATED WORK
There two main approaches to off-policy RL: importance sampling (IS) (Tokdar & Kass 2010) and regression-basee baaees approach. IS has a low bias but high variance, while the opposite holds for the regression-based approach. Below, we briefly review these techniques.
3

---

Under review as a conference paper at ICLR 2022
Importance Sampling. Standard IS uses behavior policy to form importance weight from the probability ratio of the current to the behavior policy. For fully accessible behavior policy, exam- ples of this approach include: the naive IS weight (Precup et al. 2000), importance weight clipping (Schmitt et al. 2020) and the marginalized importance weight (Xie et al. 2019 Yin & Wang 2020) can use the density ratio of the occupancy measures of the current to the behavior policies (Liu et al. 2018). This is estimated using a maximum entropy ap- proach (Lazic et al. 2020), Lagrangian approach (Yang et al., 2020), or a variational approach (Sinha et al. (020). A distinct approach emphasizes experience without considering probability ratios. Examples include emphasizing samples with a higher TD error (Schaul et al.) 2016: Horgan et al. 2018), emphasizing recent experience (Wang & Ross| (219) or updating the policy towards the past and discarding distant experience (Novati & Koumoutsakos 2019). It is also shown that IS on replay buffer is equivalent to weighting on loss functions (Fjjimoto et al. 2020).
Yin et al.] )) Alternatively,
Regression-based. A regression- -based approach can achieve strong experimental results using proper exploration and function approximation (Fujimoto et al.) 2018 Haarnoja al. 2018 It also admits strong theoretical results such as generalization error using a concentration coefficient (Le eet al. 2019), policy evaluation error using bounded probability ratios (Agarwal et al. [Chap 5.1], minimax optimal bound under linear function approximation Duan et al. (2020), confidence bounds constructed by kernel Bellman loss Feng et al. (2020). However, these settings require fixed behavior policy and bounded probability ratios, which rarely hold in practice. We hence con- struct a non-stationary behavior policy to avoid this issue.
Combined. Prior work also suggests that combining IS and the regression-based yields robust results (Dudik et al.) 2011 Jiang & Li 2016 Thomas & Brunskill 2016 Kallus & Uehara
2020
It is also common to consider some refined contractions to improve stability. Examples inc uuclude n-
step Q-learning (Hessel et al.) 2018). Retrace (Munos et al. 2016), Peng's Q (Kozuno et al.
2021
and other correction techniques (Harutyunyan et al.) 2016 lang et al. 2020
Rowland et al.
2020).
4 POLICY EVALUATION ERROR OF OFF-POLICY ACTOR-CRITIE ALGORITTMS
Let Q", QT" be the Q function of the optimal policy and N, respectively. Let Q be the estimated
Q function. The performance error QQ Q" decomposes into IQ - Q" I IQ - Q- |. The first term 1 Q is the policy evaluation error and is the focus in the off-policy evaluation literature (Duan et al. 2020). The second term is the policy's 's optimality gap and to bound this term currently requires strong assumptions such as tabular or linear MDPs (Jin et al. 2018 2020). In off off-policy actor-critic setting, the policy evaluation error has not been analyzed adequately since most analysis requires fixed behavior policy. This is the focus of our analysis.
Suppose we are given the trajectories sampled in the past episodes (the replay buffer). We ana- lyze the policy evaluation error over the expected distribution of transitions. We express this error in terms of the Bellman error of Q the bias term in I-Wasserstein distance between the policies ,T.,,=?), and the variance term in the number of trajectories N. Note n.." is the behavior policy at trajectory step defined in Eq. (6). The use of I-Wasserstein distance (Villani 2008) makes the re- sults applicable to both stochastic and deterministic policies. Since supervised learning only makes the Bellman error small, we need good sampling strategies to mitigate the bias and variance terms. We hence investigate sampling techniques from bias- perspective in the next section.
4.1 PROBLEM SETUP
Notation. In episode e, a length-L trajectory {(5), ( following policy Th is sampled (Alg. 1 line 2). Then, Q is fitted over the replay buffer (line 3). Because the error of Q at step i depends on the states sampled at steps +, the importance of these samples (s, a) depends on the trajectory step i. Also, due to the discount factor, the importance of step j >> i is discounted by د relative to step Hence, we will use a Bellman error and policy mismatch error that reflects the dependency on the trajectory step and the discount factor. For f S A + R and discounted operator over the replay buffer in N episodes:
g: S + IR, define an averaging-discounted
N T-1
T-1 (1--))**)) 9($))
f(.)) & + - f(S). and Ef &
4

---

Under review as a conference paper at ICLR 2022
Using E/, the Bellman enror of Q and the distance between the policies (T x.?) buffer are written as
the replay
8 = = Q(,-) (B=" 2)(.))
W.L W ((xp))))
( [[x;) = Wi(= (1s) (==))|== state s. which can be viewed as function of (s, a.. Both the Bellman eπror I.L and the policy Q
(-1s)) is the 1- I-Wasserstein distance between two policies at
mismatch error with depend on trajectory step and are both discounted by 7.
Assumptions. We now relate the Bellman error and the policy mismatch error defined in Eq. to the policy evaluation error Q QTn First, control the error of Q by policy mismatch error in W1 distance, we assume that for every state, Q and Q= are -i-Lsschhttz over actions. We provide reasoning for this assumption in the later discussion. Next, observe that both quantities in Eq. 7 are random with sources of randomness from initial states, policies at different episodes, and the state transitions. To control this randomness, we need assumptions a concentration inequality. Because Alg. [ only samples one trajectory in each episode, higher- order quantities (c.g., variance) unavailable. This motivates us use first-order quantities (c.g.. uniform bound on the Q functions) and apply Hoeffding's inequality. Hence, we assume that Q(ss. a) and QT (s, a) are bounded in the interval [0, rr /(1 - ->] and that the action space is bounded with the diameter diam,, justification of these assumptions is provided in Appendix A.2
the functions and apply
4.2 POLICY EVALUATION ERROR
Observe that the Q function, Eq. is defined on infinite-length trajectories while the errors, Eq. 7 are evaluated on length- L trajectories. Discounting makes it possible to approximate the Q functions using finite-length L. To approximate the Q function at trajectory step up constant error, we need samples at least to step + 2((1-) --)- and L Then, generalize the result to i and finite L in Corollary [
Hence, we first prove the main theorem with i
Theorem 1. Let N be the number of episodes. For f: S A + R. define the operator Eg f & N Σ Ei f)'' af). Denote the policy mismatch error and the Bellman error as f()
I
w E3 Wi (T (mmp)) and 0,00 = - (B*" ()(--)) respectively. Assume EQ
(1) For each S, Q1, a) and Q=" a) are L--Liscchitz in
(2) (ss a) and Q=a (8, are bounded and take values in [0, max /(1 7)]
(3) The action space is bounded with diameter diam < Sc.
Then, with probability at least 1 - 6.
E (00))a)) (als)
((s0, ao) - Q² 100""""0000 (so,ao)
max
log 2N
2
maa
2L 2L
2
log
2 +
σ 1- 7 c -2LAW1120
1
0.50
(1 72 1 1
N
Theorem expresses the error of Q as the sum of Bellman error, bias, and variance terms. To be more specific, the first two terms are understood as the "variance from sampling" because these decrease the number of episodes N. On the other hand, w:0.00 is the "policy mismatch bias" w.r.t.
N Because the behavior policy T is mixture of the historical policies [T Eq. (6). we expect it to increase in N until n begins to converge.
Theorem only indicates the difference between Q and QTa at 0 and lnfinite-length trajectories. We can generalize it to i 2 O and finite-length trajectories as follows. Recall from Eq. (6) and Lemma i the average state distribution at the i-th step, Pts and the behavior policy at the i-th step,
5

---

Under review as a conference paper at ICLR 2022
TP generate the average state occupancy measure, i.e., p. = N- -==1 Pp: a.e. Therefore, by restricting attention to the states sampled at time steps i, + 1,... the "initial state distribution" 0 to i 2 0.
and the behavior policy become P, and nh which generalizes Theorem from In addition, due to y-discounting, we may use length-L trajectories to approximate infinite-length ones, provided that L 2 i ([(1-))-)) These observations lead to the following corollary.
Corollary 1. Fix assumptions (1) (2) (3) of Theorem 7 Rewrite the policy mismatch ervor and the Bellman error as Wi' E (m))()) and 3.L éQ (2(,)) (BT Q)(,-)) respectively,
Note Et is defined in Eq. 7 Then, with probability least 1 6,
E (s, (T) ((si, ai)
- -:)- (8t,
100 (s),
max
2
pmax
2
2 2 + T (50 -11 w..".
1
2N
log +
8
71-
(V
N
log + +
Moreover, if S L
logg with 0 < < and the constants are normalized as LA c/(1 77). log
2.h c.. (11 7), then, with probability at least 1 -,,
@ cQ
Blos, [((5, ai) a;)- Qn" (st,
<0 71- (r tc. diam altmm))11/// +c) cQ
si.. + +e. w..")
where Ō() is a variant of O()) that ignores logarithmic
Note that if i 0 and L oo, Corollary I is identical to Theorem Because the Bellman error of Q and the bias of the policy are both evaluated using the averaging-discoune Corollary implies the difference of Q and Q at trajectory step mainly depends on states at trajectory steps i. Since the Q function is a discounted sum of rewards from the current step to the future, the error at step i should mainly depend on the steps 2 i.
operator E
Normalization. Although the first conclusion in Corollary gives bound the error of Q, the constants may implicitly depend on the expected horizon (1 (1-?) Hence its interpretation requires care. For instance, L,, the Lipschitz constant of the functions w.r.t. actions, is probably the most tricky constant. While it is used extensively in the prior work (Luo et al. 2019 Xiao et al. 2019 Ni et al. 2019: Yu et al. 2020), its magnitude is never properly addressed in the literature. Intuitively, if a policy π is good enough, it should quickly correct some disturbance on actions. In this case, the rewards after the disturbance only differ in few trajectory steps, so the Lipschitzness of QF in actions is sublinear in (1 - -)- On the other hand, if the policy π fails to correct a disturbance due to error propagation, the error ò propagates to every futurre step, leading a linear error dependency to the horizon O(HH). Therefore, the Lipschitzness of Q" in actions can be as large i.L should scale linearly in (1 7)
as O((1 ")) In addition to LA. the Bellman error 2 because the Q function represents the discounted cumulative reward, Eq. 4). which scales linearly in -1, These observations suggest that $ and LA in Corollary are either linear in the horizon lie between sublinear and linear. To better capture the dependency the horizon, normalize the constants and get the second conclusion.
Interpretation. The second conclusion shows the approximation error from infinite to finite-
I, 2(1 - -))- and will become harder to control for the higher due to the lack of samples. Besides, the variance term dominates when N is small, while the bias term dominates at large N. Therefore, one may imagine that the training of Alg. [ has two phases. At phase the variance term dominates and decreases in N, so the learning improves quickly as more trajectories are collected. At phase 2, the bias term dominates, the policy evaluation error becomes harder to improve and N tends to converge.
length trajectories is bounded by constant for i < I, loge
Taylor
R
log

---

Under review as a conference paper at ICLR 2022
5 PRACTICAL SAMPLING STRATEGIES
As previously mentioned, the supervised learning during the Q function update fails to control the bias and variance. We need careful sampling techniques during the sampling from the replay buffer to mitigate the policy evaluation error. In particular, Waan & Ross (2019) proposes to emphasize recent experience (ERE) because the recent policies are closer the latest policy. We show below that the ERE strategy is a refinement of 1/age weighting and that both methods help balance the expected selection number of each training transition (s, a). Balanced selection numbers reduce both the policy mismatch bias and sampling variance. Hence, this suggests the potential usefulness of ERE and 1/age, which we verify through experiments in the last subsection.
5.1 EMPHASIZING RECENT EXPERIENCE
In Wang & Ross 2019), the authors use length- K trajectory (K may differ across episodes) and perform K updates. In the k-th (1 S < K) update, a mini-batch is sampled uniformly from the most recent C₁ = max (No)) '2, Cmiu) samples, where No is the current size of the replay buffer, Ly is the maximum horizon the environment, 77 is the decay parameter, and Cmin is the minimum coverage of the sampling. For MuJoCo (Todorov et al.] 2012) environments, the paper suggests the values: (To, 7i Cmin) (1000, 0.996, 5000). One can see that v = 1 does a uniform weighting over the replay buffer, and the emphasis on the recent data becomes larger v becomes smaller. To see how the ERE strategy affects the mini-batch sampling, we prove the following result.
Proposition 1. ERE is approximately equivalent (Taylor Approx.) to the non tni-uniform weighting:
1(t S Cmin)
(In Cmin
Non 0),
Wt X
max(I,, Cmii, Norpa
No
+
Cmin
max
(8)
where L is the age of a data point relative the newest time step; i.e., is the newest sample.
Note that Prop. holds for 7 * 1 because it is derived from the geometric series formula: (1 /11 17). which is valid when 17 * 1. Despite this discontinuity, we may still claim that the ERE strategy performs a uniform weighting when is close to 1. This is because when y R 1, Eq. (8) suggests wy is proportional to 1/(NoyLww 1/No for all < l S No. which is uniform weighting. The emphasis on the recent experience (indicated by (1 S Cmin)) is also evident from Eq. Precisely, the second term increases logarithmically In when 17 becomes smaller, so the
smaller 7) indeed gives more weight on the recent experience.
ERE apx
Expected selection number batch
Uniform weight
Discussion. A key distinction between the orig- inal ERE and Prop. [ is that the original ERE considers the trajectory length K while Prop. [ doesn't, 't Intuitively, the disappearance of K's de- pendency results from the aggregation of all ef- fects in 1 < h < K updates. We verify that Eq. (8) tracks the original ERE well in the next subsection.
12-
1/age weight
10-
4-
Another feature of Prop. is an implicit 1/age weighting in Eq. 8 Although the original ERE 1.0 samples uniformly from the recent e points, the 0.8
0.2
0.6
Time step
le6 aggregate effect of all 1 < k < K updates appears be well approximated by a 1/age weighting.
Figure 1: Expected selection numbers (aggregate weights) over million time steps.
To understand the effect of 1/age, recall from section 2.2 that in practice, Q is updated using mini- batch samples. Define point (sf, af''s time step as i I + L- (e 1). Then the expected number of times in all batch samples that a point at certain time step is selected (the expected selection number) gives the aggregate weight over the time steps. As shown in Figure. [ 1/age weighting and ERE_apx, Eq. (8). give almost uniform expected selection numbers across time steps while uniform weighting is significantly biased toward the old samples. Therefore, 1/age weighting and its variants help balance the expected selection number.

---

Under review as a conference paper at ICLR 2022
5.2 POLICY EVALUATION ERROR UNDER VON-UNIFORM WEIGHTS
Recall the expected selection numbers are the aggregate weights over time. To understand the merit of balanced selection numbers, we develop an error analysis under non-uniform aggregate weights in the Appendix A.5] In particular, Corollary 2 generalizes Corollary D to non-uniform weights {w,; > 0} such that the policy evaluation error is bounded by three terms: Hoeffiding error ŌlVE, w / wi) (weighted variance), weighted bias Wi. and normalized weighted bellman error ei.L_ "Q.=* Since the weighted bellman error is well-controlled by supervised learning, the follow- ing, we discuss the weighted biases and variances in ERE, 1/age weighting, and uniform sampling. We conclude that the ERE and 1/age weighting are better because both of their biases and variances are smaller than that of uniform sampling.
For the bias from policy mismatch, Figure the replay buffer) makes the aggregate weights (expected selection number) bias toward old samples. Because the old policies tend be distant from the current policy, the uniform sampling induces a larger weighted bias W than ERE and 1/age do.
| shows the uniform sampling (for each sampling from
As for the variance from sampling, generalize Corollary || uniform case: Ö(I/VN) to Corol- lary weighted case: Ö( Eg / E, w.). That is, the variance under non-uniform weight is bounded by the Hoeffding error Ó O w / w;) and is reduced to ((1/v((1/)) /VV) when the weights equal. Furthermore, one can prove that the Hoeffding error is minimized under uniform weights:
Proposition 2. Let {we 0) be the weights of the data indexed by t. Then the Hoeffding error
V VE= wt/ Ei We is minimized when the weights are equal: wt = c > 0, VL
Therefore, the variance from sampling is large under non-uniform aggregate weights and is mini- mized by uniform aggregate weights. Since the uniform sampling leads to more non-uniform aggre- gate weights than ERE and 1/age weighting, its variance is also larger.
Because the ERE and 1/age weighting have balanced selection numbers (i.e., balanced aggregate weights), their biases and variance are smaller. They should perform better than uniform weighting for off-policy actor-critic RL. We will verify this in the next subsection.
5.3 EXPERIMENTAL VERIFICATION
Since we" we've established theoretical explanation for 1/age-based samplings (ERE, ERE_apx, 1/age), we will explore two main propositions from the preceding subsections: (1) Are 1/age-based sam- plings better than uniform weighting? (2) Does the approximated ERE proposed in Eq. (8) track the original ERE well? In addition, since prioritized experience replay (Schaul et al., 2016) (PER) is a popular sampling method, natural question is (3) Do 1/age-based samplings outperform PER?
We evaluate five sampling methods (ERE, ERE_apx, 1/age weighting, uniform, PER) on five MuloCo continuous-control environments (Todorov al.) 2012): Humanoid, Ant, Walker2d, HalfCheetah, and Hopper. All tasks have a maximum horizon of 1000 and are trained using Py- torch Soft-Actor- (Haarnoja et al. 2018) implementation on Github [Tandon 2018). Because the standard SAC implementation uses the uniform sampling, by comparing uniform sampling with the other four methods, we can deduce ways to boost SAC from a sampling's s perspective.
of the SAC algorithm are the same as that in Tandon 2018 except for the batch size, where we find batch size of 512 tends to give more stable results. Our code is available at athhtps:: t hub. com/ sun f ex / we ghted-sac) The SAC implementation and the Mu- JoCo environment are licensed under the MIT license and the personal student license, respectively. The experiment is run server with Intel i7-6850K CPU and Nvidia GTX 1080 Ti GPUs
Most
In Figure I/age-based samplings (ERE, ERE I/age) perform better than the uniform weight- ing does in all tasks. This verifies our preceding assertion that 1/age-based samplings are superior because their biases and variances of the estimated Q function are smaller. Moreover, ERE and ERE_apx mostly coincide with each other, Eq. (8) is indeed good approximation of the ERE strategy. This also explains the implicit connection between ERE and 1/age weighting strategies: ERE is almost equivalent ERE apx and 1/age is the main factor in ERE apx, ERE and 1/age
8

---

Under review as a conference paper at ICLR 2022
14.3
Humaruab-02
1.4.3
Antez2
1.63
xpx
ERE
1/nge weightt Uniform weight
>> & 4 to
PER
cumukttee
ERE, opp
2/50c wiight
ERE
ERE upo
blage weight
ERE
PER
0.0
0.2
0.6
0.8
1.0
0.0
0.2
0.6
1.0
0.4
0.8
1.0
step
stop
stop
104
HallChewiahv22
143
hoppet-v2
comuaattee FoW3r
1.25
0.75
Loge weight
ERE, SRE_ap
ERE apa
Alagu weight
ERE
ERE
0.25
PER
Unilorm weight
3.00
0:
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.8
1.0
stop
stop
Figure 2: ERE, ERE_apx, 1/age weighting, PER, and uniform weighting MuJoCo environments in million steps. The solid lines and shaded areas are the means and one standard deviations.
weighting should produce similar results. Finally, ERE and 1/age generally outperform PER, so the 1/age-based samplings that we study achieve nontrivial performance improvements.
Finally, we provide performance comparison with the prior work Fujimoto et al. (2020); Kozuno et al. (2021) in Table [}. Table [ shows the SAC with l/age-based samplings (ERE, ERE_apx, 1/age) outperform the prior work. This suggests 1/age-based samplings not only possess simplicity and theoretical explanations but also achieve better performances.
Methods
Hopper
HalfCheetah
Ant
Walker2D
Humanoid
SAC+ERE
3402
13591
6516
5530
7147
SAC+ERE_apx
3477
13890
6757
5460
7088
SAC+l/age
3496
14328
5950
5774
6664
TD3+LAP FFjjimooo et al.
2020
3364
10769
5593
4203
5445
TD3+PAL
Fujimoto et al.
2020
3055
10584
4662
4458
5328
TD3+Peng
Kozuno al. 2021
X
4196
3675
X
Table 1: Performance comparison on MuJoCo environments at step 1 million. The numbers are
measured from Fujimoto al. (Figur 1] and Kozuno al. (202T) 4]. The X symbol means the data are unavailable from the paper.
6 CONCLUSION
To understand off-policy actor-critic algorithms, we show the policy evaluation error on the expected distribution of transitions decomposes into the Bellman error, the bias from policy mismatch, and the variance from sampling. We use this to explain that successful off ofo-iy actor-critic algorithm should have a careful sampling strategy that controls its bias and variance. Motivated by the empir- ical success of Emphasizing Recent Experience (ERE), prove that ERE is variant of the I/age weighting. We then explain that 1/age-basee based samplings (e.g., ERE, ERE_apx, 1/age) have smaller bias and variance and are preferable critic with 1/age-base based samplings outperforms the prior work. We hence conclude that a simple but careful design in the sampling of off off-policy actor-critic RL can lead better performances.
uniform sampling. Our experiments verify that soft actor-

---

Under review as a conference paper at ICLR 2022
7 ETHICS STATEMENT
Our work explains off-policy actor-critic RL algorithms and designs simple but effective training techniques. The results apply to real domains where past trajectories abundant while new sam- ples are costly, e.g., robotics, recommender systems, and power grid management. RL algorithms may have positive economic effects by boosting efficiency and lowering risk. But inappropriate use can have negative societal impacts. These include job loss due to automation, the ethical chal- lenges of delegating important decisions to a machine, and data privacy issues (e.g., recommendation agents). These implications apply to most control and RI. studies and are not associated with any specific work.
REPRODUCIBILITY STATEMENT
To ensure reproducibility of the experiments, we've provided hyper-paramettrs Appendix A and the source code anonymous Github page https://gi com/ sunfex. we weighted-sac sac Discussions on the assumptions are in section 4.1 and justifications are in Ap- pendix A.2 A complete proof of the theorems and lemmas can be found in Appendix.
REFERENCES
Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, 2019.
Yaqi Duan, Zeyu Jia, and Mengdi Wang. Minimax-optimal off-policy evaluation with linear func- tion approximation. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 2701-2700 Virtual, 13-18 Jul 2020. PMLR.
Miroslav Dudík, John Langford, and Lihong Li. Doubly robust policy evaluation and learning. In Proceedings of the 28th International Conference on International Conference on Machine Learning. ICML' 11, pp. 1097-1104, Madison, WI, USA, 2011. Omnipress.
Yihao Feng. Tongzheng Ren, Ziyang Tang, and Qiang Liu. Accountable off off-policy evaluation with kernel Bellman statistics. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 3102-3111. PMLR, 13-18 Jul 2020.
Scott Fujimoto, Herke van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th Inter- national Conference Machine Learning, ICML 2018, Stockholmsmüssan. Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 1582-1591. PMLR, 2018.
Scott Fujimoto, David Meger, and Doina Precup. An equivalence between loss functions and uniform sampling in experience replay. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tice Lin (cds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
Yasuhiro Fujita and Shin-ichi Maeda. Clipped action policy gradient. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1597-1606. PMLR, 10-15 Jul 2018.
Ishaan Guirajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Im- proved training of wasserstein gans. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fer- gus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement leaming with stochastic actor. In Jennifer G. Dy and
10

---

Under review as a conference paper at ICLR 2022
Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 Proceedings of Machine Learning Research, pp. 1856-1865. PMLR, 2018.
Anna Harutyunyan, Marc G. Bellemare, Tom Stepleton, and Rémi Munos. Q(A) with off-policy corrections. In ALT, pp. 305-320, 2016.
Matteo Hessel, Joseph Modayil, Hado van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. Proceedings of the AAAI Conference on Artificial Intelligence, 32 (1), Apr. 2018.
Dan Horgan, John Quan, David Budden, Gabriel Barth-Maron, Matteo Hessel, Hado van Hasselt, and David Silver. Distributed prioritized experience replay. In International Conference on Learn- ing Representations, 2018.
Nan Jiang and Lihong Li. Doubly robust off- offl-y value evaluation for reinforcement learning. In Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp-
652-661, New York, New York, USA, 20-22 Jun 2016. PMLR.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is q-learning provably effi cient? In Bengio, Wallach, H. Larochelle, K. Grauman, Desa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137-2143. PMLR, 2020.
Nathan Kallus and Masatoshi Uehara. Doubly robust off-policy value and gradient estimation for deterministic policies. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 10420-10430. Curran As- sociates, Inc., 2020.
Tadashi Kozuno, Yunhao Tang, Mark Rowland, Rémi Munos, Steven Kapturowski, Will Dabney, Michal Valko, and David Abel. Revisiting peng 's q()) for modern reinforcement learning. In Ma- rina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 5794-5804. PMLR, 2021.
Nevena Lazic, Dong Yin, Mehrdad Farajtabar, Nir Levine, Dilan Gorur, Chris Harris, and Dale Schuurmans. maximum-entropy approach to off-policy evaluation in average-reward mdps. Advances in Neural Information Processing Systems, 33, 2020.
Hoang Le, Cameron Voloshin, and Yisong Yue. Batch policy learning under constraints. In Inter- national Conference on Machine Learning, pp. 3703-3712. PMLR, 2019.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tuto- rial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01644, 2020.
Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Sample complexity of asynchronous q-learning: Sharper analysis and variance reduction. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 7031-7043. Curran Associates, Inc., 2020.
Long Ji Lin. Seff-improving reactive agents based reinforcement learning, planning and teaching. Machine Learning, 8:293-321, 1992.
Qiang Liu, Lihong Li. Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinite- horizon oollccy estimation. In Advances in Neural Information Processing Systems, volume 31, pp. 5356-5366. Curran Associates, Inc., 2018

---

Under review as a conference paper at ICLR 2022
Yuping Luo, Huazhe Xu, Yuanzhi Li, Yuandong Tian, Trevor Darrell, and Tengyu Ma. Algorithmic framework for model-based deep reinforcement learning with theoretical guarantees. In Interna- tional Conference Learning Representations, 2019. URL
net//
forum? d=RJee
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. In International Conference on Learning Representations, 2018.
Remi Munos, Tom Stepleton, Anna Harutyunyan, and Mare Bellemare. Safe and efficient off-policy reinforcement learning. In D. Lee, M. Sugiyama, U. Luxburg, Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
Chengzhuo Ni, Lin F. Yang, and Mengdi Wang. Learning control in metric space with optimal regret. In 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 726-733, 2019.
Guido Novati and Petros Koumoutsakos. Remember and forget for experience replay. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 4851-4860, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
Doina Precup, Richard S. Sutton, and Satinder P. Singh. Eligibility traces for off-policy policy evaluation. In Proceedings of the Seventeenth International Conference on Machine Learning, ICML '00, pp. 759-766, San Francisco, CA, USA, 2000. Morgan Kaufmann Publishers Inc. ISBN 1558607072.
Mark Rowland, Will Dabney, and Rémi Munos. Adaptive trade-offs in off off-policy learning. In Silvia Chiappa and Roberto Calandra (eds.), The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Pulermo, Sicily, Italy], volume 108 of Proceedings of Machine Learning Research, pp. 34 44. PMLR, 2020.
Tom Schaul, John Quan, loannis Antonoglou, and David Silver. Prioritized experience replay. In ICLR, 2016.
Simon Schmitt, Matteo Hessel, and Karen Simonyan. Off-policy actor-critic with shared experience replay. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 8545- 8554, Virtual, 13-18 Jul 2020. PMLR.
John Schulman, Sergey Levine, Picter Abbcel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp- 1889-1897, Lille, France, 07-09 Jul 2015. PMLR.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms, 2017.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In Eric P. Xing and Tony Jebara (eds.), Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pp. 387-395, Bejing, China, 22 24 Jun 2014. PMLR.
Samarth Sinha, Jiaming Song, Animesh Garg, and Stefano Ermon. likelihood--ree importance weights, 2020. urXiv:2006.13169
Experience replay with
Richard S. Sutton, David McAllester, Satinder Singh, and Yishay Mansour, Policy gradient methods for reinforcement learning with function approximation. In Proceedings of the 12th International Conference on Neural Information Processing Systems, NIPS 99, pp. 1057-1063, Cambridge, MA, USA, 1999. MIT Press.
Pranjal Tandon.
Pytorch soft actor critic, tory, http::///iiiuttoooo/mm///////y//
2018.
Github
Reposi-
12

---

Under review as a conference paper at ICLR 2022
Yunhao Tang, Michal Valko, and Remi Munos. Taylor expansion policy optimization, In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learn ing, volume 119 of Proceedings of Machine Learning Research, pp. 9397-9406. PMLR, 13-18 Jul 2020.
Philip Thomas and Emma Brunskill. Data-efficient off-policy policy evaluation for reinforeement learning. In Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 2139-2148, New York, New York, USA, 20-22 Jun 2016. PMLR.
E. Todorov, T. Erez, and Y. Tassa. Mujoco: A physics engine for model- control. In 2012 JEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026-50333 Oct 2012.
Surya Tokdar and Robert Kass. Importance sampling: areview. Wiley InleeyyIteerisccpplnaanyya Reviews: Computational Statisties, 2(1):54-60, 2010.
C Villani. Optimal transport Old and new, volume 338, pp. xxii+973. 01 2008
Che Wang and Keith Ross. Boosting soft actor-critic: Emphasizing recent experience without for- getting the past, 2019. arXiv:1906.0400
Chenjun Xiao, Yifan Wu, Chen Ma, Dale Schuurmans, and Martin Müller. Learning combat compounding-ene error in model- based reinforcement learning, 2019. 191.v:1922.11206.
Tengyang Xie, Yifei Ma, and Yu-Xiang Wang. Towards optimal off-policy evaluation for rein- forcement learning with marginalized importance sampling. In Advances in Neural Information Processing Systems, volume 32, pp.
Curran Associates, Inc., 2019.
Mengjiao Yang. Ofir Nachum, Bo Dai, Lihong Li, and Dale Schuurmans. Off-policy evaluation via the regularized lagrangian. Advances Neural Information Processing Systems, 33, 2020.
Ming Yin and Yu-Xiang Wang. Asymptotically efficient off-policy evaluation for tabular reinforce- ment learning. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 3948-3958, 3958,, Online, 26-28 Aug 2020. PMLR.
Ming Yin, Yu Bai, and Yu- Yu-Xiang Wang. Near-optimal provable uniform convergence in offline policy evaluation for reinforcement learning. In Arindam Banerjee and Kenji Fukumizu (eds.), Proceedings The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 1567-1575, PMLR, 13-15 Apr 2021.
Tianhe Yu, Garrett Thomas. Lantao Yu, Stefano Ermon, James Y Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. Mopo: Model-based offline policy optimization. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances Neural Information Processing Systems, Curran Associates, Inc., 2020.
volume 33, pp. 14129 14129-1412.
A APPENDIX
A.1 HYPER-PARAMENTE PARAMETERS
To train the SAC agents, use deep neural networks parameterize the policy and functions. Both networks consist of dense layers with the same widths. presents the suggested hyper- parameters. As mentioned the experiment section, the hyper-parameters are similar as the imple- mentation in Tandon 2018).
A.2 JUSTIFICATION OF ASSUMPTIONS
In section 4.1 introduce three main assumptions in this work. Below validation for each.
13

---

Under review as a conference paper at ICLR 2022
Variable
Value
Optimizer
Adam
Learning rate
3E-4
Discount factor
0.99
Batch size
512
Model width
256
Model depth
3
Table 2: Suggested hyper-parameter, for SAC.
Environment Hopper
HalfCheetah
Walker2D
Ant
Humanoid
Temperature 0.2
0.2
0,2
0.2
0.05
Table Temperature parameters for SAC in MuloCo environments.
1. For each E S, Q(, a) and QT' (s, a) are LA-Lisschitz in a. As mentioned in the paragraph "Normalization" of section 4.2 the Lipschitzness of Q*" is sublinear linear in the horizon, which quantifies the magnitude of Q Lipschitz constant. Since Q approximates Q Q should have a similar property as long as the training error is well controlled. The practitioner can also enforce the Lipschitzness of Q using gradient penalty (Gulrajani et al, 2017) spectral normalization (Miyato al. 2018).
2. (s, a) and Q=a (s, a) are bounded and take values in [0, r /(1 - 7)]. This standard assumption in the RL literature. If the bound is violated, one can either clip, translate, or rescale to obtain new Q functions that satisfy the constraint. Note a bounded reward r(s, a)
[0, max] has implied Q E [0, max /(1 -)]]-
3. The action space is bounded with diameter diam < 0o. This a standard assumption in continuous-control environments and is usually satisfied in practice. It is also common to use clipping to ensure the bounds of the actions generated by the policy (Fujita Maeda 2018).
A.3 THE CONSTRUCTION OF OUR BEHAVIOR POLICY
We first discuss some important relations between state occupancy measures and Bellman flow op- erator. Similar results about Fact Tand Tbe found in Liu et al. [ 3J.
Definition (Bellman flow operator). The Bellman flow operator BP generated by (po, n,, T) with discount factor 7 is defined as
B (p)(s. & (1 (1-7)po(s) + T(s d') ('ssp''s)'''s da'
Fact B is a "-contraction w.z.t total variational distance.
Proof. Let (I P2(s) be the density functions of some state distributions.
Drv (Bpo (P1) po. (P2)) = 2 / B (p). - B Br
/ > fl T(sis' d'
pz(s') ds' da'
< / (')))))))7((())))))) - p2()s) Ids' do' ds
? / |m((6)) p2(5') DDr
2
Fact 2. The normalized state occupancy measure P7 generated by (po, n, T) with discount factor Y is a fixed point of B B Le., B T (3) (s).
14

---

Under review as a conference paper at ICLR 2022
Proof.
Pro
-1) (8) (s)
-2) Σ (T,
1=0
-(1 - (o)o((p x, T) + + Σ E1 (itipls))))
im
20
-(1 - -))((s))) + 711 -1)--) Ex
T(s]s', a'
(po: n,, T)ds's do'
-(1 - ()))())))))))))))))))))))))))) + + / T(sb ((sbs.")mmd) 7)
r Sil''loo v,, T)ds do'
= - ()p((s) +7 T(s]s' (')ss',a'TTT( (')'(''ss') ( (8 (s')d''dd da' = B B ( (po (s).
Thus, the Bellman flow operator is useful analyze the state occupancy measures, and we have the following lemma to construct the behavior policy T!P
Lemma 1.
Let (s) the state distribution at trajectory step i in episode e. Let P (s) be the normalized occupancy measure starting at trajectory step i in episode e. Then t Ee= P7j =
sP x (s) a.e., where P7; the normalized state occupancy measure generated by (P T). P7,
Moreover, we have N Ee 1% (8)7 Pp: = (5)m a.e.
Proof. Precisely, (f(s) = ps x-, T) is the state distribution at trajectory step following the laws (Pu, n², P% is the fixed-point of the Bellman flow equation:
,²,T), ,), Since %% is the normalized occupancy measure generated by (pt, ( each
p% = = (1- +7 T(s]s' (ollss,d))rs dd') (d' (s')ds'da Ve [J.
This implies the average normalized occupancy measure is the fixed point of the Bellman flow equation characterized by (Pes x!. T))
N (1 7)) +7 ('))s" (s')ds' da'
= (1-7)77,66) +7 / T(sls, d')
T (a'ls') (6') ds da'
= (1 ()p((s) + / T(s)s',d))
EN
De=1 n ( pp (s') Ee PT (s')
N ds' da'
EN P% (s")
(1 (s) +2 / ((s)s),a)m<(((
1 Σ ( (s')d''
where (a(as)) A EN = (s)
is the average behavior policy at step i. Since the Bellman flow
EN P7 (5)
operator is c in TV distance and hence has a unique fixed point in TV distance, denoted = as Pp (s), we arrive N >. Por (s) Pp (s) almost everywhere. Also, by construction, we have
1 N
Σ
p (8)T (als)
a2 (s)TT (a]s) a.e.
N
15

---

Under review as a conference paper at ICLR 2022
A.4 POLICY EVALUATION ERROR
Lemma 2. (fQ a) is La-Lipschitz in a for any 8, then, for any state distribution
Esup B (1) Q(s,a) (s (i
Proof. For any fixed 8, we have
Q(s,a) a) La SLA sup (a))()))) Ba (L)) |ifliosi
((s,a) Bawaz((1s))
(()) (1) La (awn(((s)
L
where the second line follows from Kantorovich- Saatorovich-Rubinstein duality (Villani 2008). Since the 1- Wasserstein distance W1 is symmetric, we can interchange the roles of πΙ T2. yielding
(a (+le (11) a) - (1a) a) s (1)))
Taking the expectation Eg-p both sides completes the proof.
Lemma 3. IfQ" is L--liscccitz in a for any 8, then
E (100)))))p(s))))8aa)))))) Q (so, an) Q" ao)
S
LA
W (-s))[
W1
1 s~Pfo
Proof. For any (s, a), we have
1QTh (s Q (s)
=7 E. Eu E. Q E..
Sy
Q" (5)) (7),) -0'(s' -1
E
(s', ( ((())))((((,,((())))))))))
E (s)))()))) --(6--00) Bag= Q² (5 Q"'(', m((s)
STBE Exp Q (s))
Q" (7))) LAWi
(1s))
where the last line follows from Lemma Let Pi be the state distribution at step following the laws of (Po. To T). Take expectation over Pu and expand the recursive relation. We arrive at
E (s00.00) (p
Q (su, ao) (su, ao) S LA
E scmp,
= W2(= (+ss)((())
TA E
W (T (-1s)
Wim
1 - y
LA
E
W (m (+1)
erup
where the second line follows from Pāo (1 - (1-7) Eie p.p
Lemma 4. ((, a) is LA Lipschitt in a for any s. then
Q(so, ao) - q (so. ao)
((eo (ale)
E o ((8,a) B3 Q( a)) + (
(s.a)-p (ola)
16

---

Under review as a conference paper at ICLR 2022
Proof. For any (s. S x A. we have recursive relation:
Q(s,a) Q" (s = Q(s.a) - B Q (s.a)
Q(..a) -B (s a) + 1 Q(s.(ss)) - R Q (s.a)
= Q(s,a) 8 Q(s a)
Q ())
< Q(s,a) 0 ( a) + (ha 0(5' - Q (s',a'))
Expand the recursive relation. We have
(000000)) Q(so, ao) Q² (so, ao) po E Bao (1))0)
Q(su, au) B Q(su, an)
+ E Bo do
E Ba.. Btt. o a(
a() R Q(s.. ai)
E E00
"l ((s), - ((s)
1=0
1 E
((s,a))B*t) (()))
1- (c,0)~p2)
(ale)
(9)
The last line uses fact for the normalized occupancy measure
= (1 77) (o E Ba (-1s0)
E of
(-18:)
PAo
We are almost done once the B in Eq. is replaced by B", Note that
E
(s) 1 8 Q(s,a)) a)
(s
oB Ao
(als)
E
-(s,a)(B - (5s(s, a) + (=((ssa)- - 8 Q(s.a)
(..0)pp (()s)
-I
8
((s,a)) - B QTQ(s a)
+ > | Q ((s)) - -66'' ( (o(')))
(.. Ag
(als)
2
((s,a) - ((s
+ + ((s a)
"I 1s')
o (x.a)~pp Ao
(als)
(((s,a) - (=((s, a)
=E
(s.))pp (clo)
LAB
8 (T( (-1s) - (1 - L. (i(
<
B (s.a)-pp
(als)
Q(s,a)) - B=Q(s
a)} (ss + [=
(10)
The second-last line follows from that the distribution of s' is P (s') = Scn ((s)(ssa)p7) (s, which satisfies the identity
Piu (s') = (1 p)p)(s')+ + / T(s'ls, a) (s, a)dsda = (1 - 77)p((s) + +yp =8
(5))
Combining Eq. 99 and Eq. I0 the result follows.
Lemma 5. Let 0 S a(s A be bounded function for (s, a) E S A. Let Eg be
the averaugng- operator with infinite-length trajectories in N episodes; ie, E f
17

---

Under review as a conference paper at ICLR 2022
N E.=EE Eio - fi ((), Then, with probability greather than 1 - 6,
E Phu (s)mg (ale)
/ S A
log
N
Proof. Let (s)(s) be the delta measure at the initial state in episode e. Because the empir- ical distribution PO composed of the realization of the trajectories's ' initial states, we know 3o
an average of the normalized occupancy mea- in - NV Σe dzg- Then, Lemma implies Pão sures in N episodes.
Poo (5) (a|s)
me
Σ ==1
(s)s
N
(11)
def. of PB
- w) pi (s x", (
1=0
where Pf is the state density at trajectory step in episode e. pi(56 T², s), we have
Since
(sf
F E
Σ >) - Bogg (orerans
Pio (e)x (al=)(al=))
N
8
Σ (1 (1-7)) () -[1(6)
M
(12)
) is martin- We claim that [ defined as M = -i= -ff((,; gale difference sequence. To see this, let F be the filtration of all randomness from episode I to e, with 5 being a null set. Clearly, we have M E Fe, E[M f(s.a) [0, A] by assumption, which proves {M*)
and M E [-A, A] since Je=1 is martingale difference sequence.
Finally, since M is bounded in A], by Azuma-Hoefiding inequality, we conclude that with probability greater than 1 Ó,
E (2A)2 2
2 N 5
Eq.
N
log 8 = 11
log
Theorem 1. Let N be the number of episodes. For f: S x A + R, define the operator Eg f A N EN Σ (1 f af). Denote the policy mismatch error and the Bellman error (B* ()(-))} respectively. Assume
W 10. = E Wi (.) and &
0.00 =
(1) For each s S, ((, a) and Q=" (s. a) are LA Lipsschhit in a.
(2) ((s, a) and Q= (s,a) are bounded and take values in [0, max /(1 - 7)]
(3) The action space is bounded with diameter diam < oc.
Note W, (л || [ss) means W, (T (=
which is a function of s. Then, with probability
greater than 1 6, we have
E
Q((0,, ao) Q (sg, (s))
max
log
2
+
max
+ 1
2L ALiam
log
2
+
1 '
1
( 0.00
+ +2L,W0000)
2N
5
(1
72
N
18

---

Under review as a conference paper at ICLR 2022
Proof.
The proof basically combines Lemma
and
To start with, the objective is decomposed
as:
B ((c0)so))pp()))(8taa)) (s5, ao)
QT (so. ao)
111 + ( ((50, ao) QT (so. ao)
<H1 + (() (ale)
(s0, ao)
Q& (so:
- -Q" (su. am) (s0, ao) + 10 1 ao)
8
1
[((0,a) (B ()() a)) (1=))
H1
E
1 y
(s,0)rupo
(o)m (a|a)
=H1 +
H2
+
1
E00
((.,)) -(B* (o()))) + (+
1 1
1
-
Assump.
H1
+ 1 1
H2
+
1
0,00 + 22AW.1120)
(13)
Because aQ( Q= (s, (s,
[0, - we know p
( a)) Q= (s,
a)) [0,
T-7
too. Suppose Po have N independent samples. By Hoeffding's 's inequality, with probability
6,
max
H1 = [E (Esorpo Eso po ) Bao so) [((s) aq) Q" (so. ao)
log
(14)
2N
3'
Also, let (s, a) a)ssa))(88) () a) WW (T (+s)) (-1s)). Then f(s a) is bounded
in 10, 1-7 + Adiama) Thereby, Lemma implies that with probability greater than 8,
|[(c,aa) (B= (s), 2 (1
H₂ = E
(B,0))=p 8 (s)a)(a))
max
+ 22
V
2 N
log
1
3
(15)
Combining Eq.
13
14 and
15
union bound implics with probability greater than - 25,
(en (o)))) (al*) (so, ao) Q²² (so, ao)
maxx
(11 (1- 2L 2L
max
2 +
_6660 0,000 +2LAWD 11 ( "000
log
+
log
2N
N
Finally, rescaling 8 to 6/2 finishes the proof.
Corollary 1. Let F.F. be the operator defined as P 1/ (1
df). Fix assumptions (1) (2) (3) of Theorem [ Rewrite the policy mismatch error and the Bellman error as Wi. E. (1 ||x,) and c. -E( (B"
Q)(--)),, respectively, where be the average state density at trajectory step i over all N episodes. Then, with probability greater than 1 - 8, we have
W1 W [IT:)) W1(=" (N=((N)-))) (+1s)][=? (-Is). Let (,())
((ss, a:) Qna (si, (st,
E (et)))))p()))
max
log + (1 (1 71
max
2L 2L
2
log + xmm)
+ +i 1- (
1 ( ib
+ 2L.W(11
2N
1-7
Moreover, ifi S L-
log and the constants are normalized as LA c/(l-7), 2/2
loge
it
5/¹¹
i.l.
2/2/10 (1-
then, with probability greater than 1 - 8. we have
E B(s.a))77 ((5)) az) Q=x (si, ai)
<ō (1- 732
1
(nmaax feax+C +c diam (L/// +c)+ E6
+ ch. +c. se.w)))
19

---

Under review as a conference paper at ICLR 2022
Proof. Notice that Theorem I is the situation when and L = co. To push this to 2 and = J0, recall that Lemma defines the behavior policy n." the average state distribution pj and the state occupancy measure Po. at step i. Also, since the trajectories each episode are initialized using the same initial state distribution, we have pa = Therefore, the objective of Theorem is actually B (e (o0)))))))))) (ala) (10, ao) - Q= (00, This generalized i using substitutions: (Pos Tp. ET) + (Tes TiP ) yielding
((s))a))D((()))((a)) ((8;: az) Q"n
(sis ail
y mmax
log
(1-
mmax
21 2I.adiamA)
2
log
2
( 1.00 "
-2LAW((00
2N
-
N
7
Finally, observe that for any bounded f:
E s E f +
We arrive at
B ((er)a)))7 (s) -QT (sis ai)
2N
log +
2
8
(11
- 7)2
p.max
+
2LAdiaaA
1 ) (v/² log σ
2 t//
i. + wT(h y à
As for the second conclusion, with the substitutions in the statement, we know / < c. Hence,
((ss,, a:) Qa (st, (si,ai) ai)
E (s)) (als)
maxx
1
2
(1 71- + 2c diam A
mmax
)(1
2
- )) + (1 (1-7)
(chb ( + 2c whi))
log
+
log
2N
(1 7)2
N
7)²
-0
(frmax c diam dia//)(I//NN +c) eih +c. +c.wii))
(1
7)2
A.5 POLICY EVALUATION ERROR UNDER NON-UNIFORM WEIGHTS
Lemma 6. Following from Lemma 7 let w {we > 0) be the (unnormalized) weights =D
for the episodes. We have for the weighted case, E. Ee (eppi (x)(()) a.C., where The Ppi,o (8) is the normalized state occupancy measure is generated by (Pr.o T.. 2hf Σ. me Ee wopf (dls) = P7,,"" (3)mf (als) a.e.
T, T). Also,
Proof. The proof is basically generalization of Lemmal Since P the normalized occupancy measure generated by (pf, n², T),, we know each p7 is the fixed-point of the Bellman flow equation:
(1- +x d') (s')d'ss (d')ds'da', da', Vee [I.
20

---

Under review as a conference paper at ICLR 2022
Taking weighted average, get
Ee We Σ (s)
Σ We (1 (1- (1-)))((0) + +7 /
(6 (ddd
E. We
-(1 () +7 / T(s]s' a')
Ee Wr I [ [T (5') ds'da'
-(1 ()) +7 / T(s)s', aa)
Ee (dl (8')
Ee Wapfi (5')
ds' da'
Ee Weppp (5')
Ee We
=(1 (s)))) +2 / T(s]s', a' ('fmml"'
Σ Wapp (s')d''d da'
Ee We
Σ. won (al 1) (s)
where n. (als)
is the weighted behavior policy step i. Since the Bell-
Σ. p (e)
man flow operator is a cccotracctoon in TV distance and hence has a unique (up to difference
(s), Th. (s). we arrive at En
in some measure zero set) fixed point, denoted Ps..
1 the E. Wapp (s) =
(s) a.e. Finally, by definition of T,, (als), conclude that Σ. we Ee WePeo (8) (als)
Pr (s)mP. a.e.
Theorem 2. Let w = (we > O) be the (unnormalized) weights for the episodes. Let Esg. be the operator defined as Fige = E.we Ee Ei=o(1 - DeJ at). Fix assump- tions (1) (2) (3) of Theorem 7 Rewrite the policy mismatch error and the Bellman error as 1, Ege W1 1 T
and 0,00
EQ,u (...)(((..)) (B=* ())(,))). respectively, where
W1 W1(T (IT. Im..)) W1 W N (-1s) (o With probability greater than 1 8, we have
E (p (a|s) ((50, an) - Q=a (50, ao)
<
max
Σ. w²
log
2 8
1
2 2(E. we)
+
max
7)2
+ 2L 2LadiamA
2 2. w we
log
2
+
1-
1
i,10
0.00
+ 2T W1,00)
1,
Proof. The proof basically follows from Theorem
Decompose the objective using Lemma 3 4
as:
B B (o (ala) Q(s0, ao) - QTm (80. ao)
(100 ao) - Q= (00""s000000000000000 aoi
=H1 + +B Be (alo)
Q(50, au) Q ao) + 10 ( (su, QT" (sa. ao)
<H1 +
(a|s)
[0(s.a) - (88** (=)))sssa)) + 2I (-|s) 2. (-18)
H1
E
P.u (alss)
1- 7 (s.a)r
H₂
F0. |Q(::)) - (88**
-(B")) (Q(.))) + (1
=H1 +
+
1 y
1 -
Assump.
Hi
H12
+
0,00 2,
+ W. 1,
1 7
1 7
(16)
where )u, = Ee ((66-50)) is the weighted empirical initial state distribution.
Because
E.
(())a)) (s))) E 10, } we know B Bawag ((())))) (((,,)() (x,a) E [0, -
too.
21

---

Under review as a conference paper at ICLR 2022
By Hoeffding's inequality, with probability greater than 1 5,
H1 (Eeoripo Bsorrpow ) (. ao) (1s0)) Q((s)
(s0 as)
Σe
We 1-7
pinax
ylax
Σ u
1 log
(17)
log
Ee We
2 We)
Also, let f(s,a) ((s (BT* (s) + 2LAWi (T, bounded in [0, pmaxx + 2L Adiama). Using a weighted version of Azuma- goeff-io in Lemma 5 we have that with probability greater than - 6,
(+ss). Then f(s,a) is
1-y
H2 = (
[1(ss,0 - -(8T" ()) + ( (m,
P. (s,a)~-Po.. p0.00 (1))),
max
2 2 w V
1
+ 2Ladiama)
log
E w
(18)
Combining Eq. 16 and
18 union bound implies with probability greater than 1 25,
max
Σ.
E
((00)0)))000)))0)m (alo)
((00: ap) x= (so, ao)
log
2
mmx
2L
2 2 w
log
1
+
1
( (
+ 222 W-0.00
(1 (1-7)3
1-7
we )2
0
7
Q.u
Finally, rescaling 5 to 5/2 finishes the proof.
Corollary 2. Let E be the operator defined as E = Ee E. Ee
( (8)) Fix assumptions (1) (2) Theorem Rewrite the policy mismatch error and the Bellman error as WiL -Et, W1 (= N (.) and T. spectively, where W1 W1 (s) W1 (T [=
Q(.,)) (B* ()(,))) re- =Et,n(((,))
q.10
Let (s)) be the average weighted state density at trajectory step i. Then, with probability greater than 1 - ò, we have
(1..a)))7 Pa) Q(,, a,) Q=" (s
S
max
Σ. w²
log
2(E. w₂)²
+ (1- 1
max
2L A
2 w² )
log
+ +
+ 1
1 1-
((
2,w
+ +2L W +2LAWAth
1,10
Moreover, if < L- logcc and the constants are normalized as LA = c/(1 (1-7)1)) 7). then, with probability greater than 1 - 8, we have
d.b
- /
Tog
&Q2w
((0,,0))0,, ((s))aa)) Q=" (st,
<ō
72 mrx + diama)
[ w Σ
we
+e) + dhl
q + w1.b))
Proof. Observe that for any bounded f:
E f < E.J.f + + fflllo
Thus, start from Theorem 2 and prove with the same argument in Corollary 1
22

---

Under review as a conference paper at ICLR 2022
A.6 PROOF OF EMPHAZING RECENT EXPERIENCE
Proposition 1. The ERE strategy in Wang & Ross 2019 is equivalent to a non-uniform sampling with weight we:
1
No )
1
1 Gmin K
max (1 In1 Cmin 0).
We 1- 1- max(t, Cmin: Nonto)
Cmin
Lo In
where t is the age of a data point relative to the newest time step; i.e. wo the newest sample.
No is the size of the experience replay. Lo 1000 is the maximum horizon of the environment. K the length of the recent trajectory. = 0.996 is the decay parameter. Cmin R 5000 is the minimum coverage of the sampling. Moreover, the ERE strategy can be approximated (by Taylor Approximation) as
X
max(t, Cmin Non No
1
+
1(t S Cmiu)
max
In
Cuuin Non
0)
Cmin
Proof. Recall that Wang & Ross (219)) assume a situation of doing updates in each episode. In the kth update, the data is sampled uniformly from the most recent eą max(NNon * 'x points.
Cmii)
To compute the aggregrated weight wy over these K updates, observe that a data point of age is in the most recent C points if c 2 t and that the weight in each uniform sample 1/ck. Therefore, wy should be proportional to
We X
Σ
(19)
Ck
ISKSK,
Because Cj is designed to be lower bounded by Cmin, we shall discuss Eq. 19 by cases.
(1) When t >> Cmins know C Cmin because C₁ 2 is constraint in the sum. This means Cs Noo and hence ca 2 is equivalent to l & In / /./I//f La/K, Eq. (19) becomes
min(K, la // /
min(K, In Ng (ng)
Σ
Σ
1 1] No
Lak/K (+)
S
Ck
No
4: ISKSK
0427
long No
1/1 1/1-1/N
if In No
In Lo/K
No
1-8
1- bo/K
1-E E--K
7 ko /No 1/No
if < In No In in
T-6-
1-17-//
1/t-1/Ng
1-1
ift > No
1
1
1/(Nog 103-1NN
if $ No
nLo/K max(t, Non
No
where (*) is a substitution: & = =
(2) When 5
Cmins we know C* 2 for all l: because ea 2 Cmin by definition. Eq.
19
becomes
Σ IECKK 22
Cx
Cs
min( K, In Squa ln
E * + max(K - In
Canin / /In 0)
No
No
Cmin
1=
1
In Cmin/No
1
+ max(K K K
0)
bo/K
max max(Cmin Cmin: Lon
No
Lo Inn
Crinn
1
max (1
In Cmin/ /No 0).
+
ko/K
max(Cmin. NonLo)
No
Cmin
Lo lu
23

---

Under review as a conference paper at ICLR 2022
where (+) does substitution: Ç 17 /// and split the sum. (**) reuses the analysis in case (1).
Combining cases (1) and (2), arrive the first conclusion. As for the approximation, since 7 Re 0.996, let 7j = - k. We have
x) Lo/K x =1 = Lo K
La In(1 R)
Lo Im
n
K
Thus the first term in the conclusion of Prop. is proportional to K. The second term is also proportional to K. Since w, only made to be proportional to the RHS and both terms on the RHS become proportional to K, remove K on the RHS:
1
1(t S Cuin)
Cminn No (1
0)
+
max
Lo in .max(t, Cmin: Norpba
No
Cmin
Lo In 1)
Finally, because < < 1, Ly In is a positive number, the above expression can be further simplified by timing - Lo in the RHS, yielding the result.
Let {we 0) be the weights of the data indexed by t. Then the Hoeffding error V E N w// E Wt minimized when the weights are equal: wt > 0, Vt.
Proposition 2.
Proof. Let w = [W].... WN] be the weight vector and f(w) = Vw" w/(l1 T w) be the Hoeffding error. Observe that fww) is of the form:
f(w) = w1l((1 T w) = 11w/(11 (((T([)))) "w)l:
where || w w is the 2-norm of Thereby, let (1 w) be the normalized vector. That I' (ww) minimized is equivalent to that g(z) ||=||| is minimized for 1. By the lagrange multiplier, this happens when
2
A1, for some À E R.
This can be achieved by 2, = c for some c > 0. Therefore, we know f is minimized when
Wt w
2t
e for some c.
Since 1 w does not depend on ł, we conclude that the minimizer happens at w, >> 0, Vt.
24


Reviews:
[{"review_id": "q_LzsG_hJJt", "reviewer": "Reviewer_b574", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper is very confusing. \n\nFirst, the title is about explaining off-policy actor critic. However, all the theories discuss only the critic error. In my opinion, the authors should focus on the policy evaluation problem with data from mixing distributions because the theory has noting to do with the actor.\n\nSecond, Algorithm 1 does not make sense to me. In Line 3, it involves the true Bellman operator, which is not available because we do not know the transition kernel. It also does not specify the function class of Q, so I'll assume the argmin is done over all possible Q function. Then shouldn't the argmin simply return the true Q function of the policy \\pi^e, because the true Q function apparently gives 0 for the objective inside the argmin? This confusion makes it hard to interpret Theorem 1. First Theorem 1 does not specify what \\hat Q it talks about, I feel it cannot be an arbitrary \\hat Q because otherwise the error shouldn't depend on N. For now I assume it's the \\hat Q generated by Line 3 in Algorithm 1. Then as discussed before, that argmin should return the true Q function, then the error should simply be 0. \n\nThird, I do not understand the motivation of this work. What do we get from the proposed decomposition? It looks it's just an understanding of ERE, which I don't think is enough for publication. Further, it would be good to explain how many seeds are used to generate the plots. For now it is hard to interpret the results.", "summary_of_the_paper": "The paper proposes to decompose the critic error into several terms to better understand off-policy actor-critic algorithms. Empirical results are provided to show how their theory can be used to explain two experience replay sampling strategies.", "summary_of_the_review": "The presentation and motivation of the work is not clear", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "b2qizkRSJ5s", "reviewer": "Reviewer_RYz4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This is a nice paper expanding our undertanding of actor-critic algorithms. Focusing on the policy evaluation error is a simple approach yielding meaningful results. The assumptions are sufficiently weak for the conclusions to apply to modern deep RL methods, a strength of this analysis. The experiments are a good addition to validate the theoretical findings and make the case more convincing. Overall, this is a great paper with concrete insights that are clearly conveyed. \n\nQuestions and comments:\n- I think the fact that the analysis is uisng continuous action spaces is neat. This seems to be a less popular choice in RL.\n\n- Algorithm 1 is set up nicely to avoid the complexity of deep RL algorithms but still retain the essence of the algorithms and allowing interesting theoretical derivations.\n\n- p.6 To clarify, why is it stated that $|\\hat{Q} - Q^{\\pi^N}|$  mainly depends on steps $\\ge i$. Is this because of the presence of $\\epsilon^{i,L}_\\hat{Q}$ and $W^{i,L}_1$?\n\n- It would have been nice to have an experiment which directly measures the policy evaluation error. This could be done in a simpler environment where policy evaluation is relatively easy e.g. LQR. This could help support the theory even further.\n\n- How are the curves in figure 1 generated? Are these obtained analytically or are simulations run to obtain then? \nIt seems like for uniform sampling, if we sample only 1 transition at each step, the expected count (aggregate weight) after $n$ steps would be $\\sum_{i=0}^n \\frac{1}{i} \\approx \\log n$. This would imply that the aggregate weight for the transition at time step $i$ would be approximate $\\log n - log i$, which seems to roughly match the shape of the curve plotted.\n\n- p.6 The detailed discussion in the \"Normalization\" paragraph is nice to tie up loose ends.\n\n- p.6-7 Some parts of the \"Interpretation\" paragraph are a bit confusing to me. In particular, I'm not following the part discussing the bias and variance terms and how they impact the optimization process. I understand that, near the beginning of learning, variance may be large relative to bias. But in phase 2, it's not clear to me what happens to the relative magnitudes. It seems like both bias and variance would be small. Also, while lower policy evaluation error leads to more accurate estimations of $Q^{\\pi^N}$, I'm finding it difficult to translate that to how fast optimization progresses. It would seem like more accurate estimates would lead to \"better\" optimization steps but, at the same time, the optimization process will naturally slow down as the iterates approach a maximum. I think this paragraph should be clarified a bit more.\n\n- Since the policy evaluation error is only one component of the total error $|\\hat{Q} - Q^*|$, what do you think about the other term $|Q^{\\pi^N} - Q^*|$? Is it not as important to assess the behaviour of the actor-critic algorithms? It seems like focusing on policy evaluation is be enough to understand the performance of actor-critic algorithms in certain cases.\n\n- Does the theory recommend any \"optimal weights\"? It would be interesting if the derived bounds could be used to develop a better sampling strategy than 1/age or ERE.\n- On a similary note, have you tried more aggressive recency weights, such as 1/age^c for c > 1? It would seem to decrease the bias even further although at some cost in the variance. Perhaps an adaptive c would be appropriate too.  \n\n- Can the developed theory be used to explain the performance of prioritized ER? \n", "summary_of_the_paper": "The paper seeks to improve our understanding of actor-critic methods in deep RL by providing an analysis of the error in estimating the value function. The main theoretical result is an error bound which depends on the Bellman error, variance from sampling and a bias term from the policy mismatch. This error bound suggests that a replay buffer sampling strategy that focuses on recent samples will have an advantage. Experiments validate this hypothesis and using weighted sampling with 1/age weights improves performance. Morover, the theory helps explain the success of the ERE algorithm which also emphasizes recent transitions. \n", "summary_of_the_review": "The paper presents a convincing analysis of replay sampling in actor-critic algorithms with theoretical results applicable to modern deep RL algorithms. I think it would be a nice addition to the literature.\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Z4kA7bbpRL", "reviewer": "Reviewer_VgPP", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Overall comments : \n\n\t1. This paper studies policy evaluation errors for off-policy actor-critic algorithms. The key argument is that the policy evaluation error for actor-critic in off-policy has not been studied well. While this is true, I would have expected some empirical analysis, to justify the theoretical claims of the off-policy critic error in the overall algorithms. For example, how does the critic evaluation error in algorithms like SAC/DDPG lead to the performance in the policy improvement step? Does poor estimation of the critic lead to errors in algorithms like SAC? I think a careful analysis of this is what is expected from a paper trying to analysue bias, variance and policy evaluation error of algorithms like SAC/DDPG etc which has strong empirical performance. \n\n\t2. Theorem 1 characterizes the effect of the policy evaluation error in the off-policy actor-critic setting. While this result is important to characterize - I am not sure if it adds too much value in the overall scheme of things. For example, it'd have been better to see how this error leads to the convergence/divergence of off-policy algorithms? Otherwise, this is similar to any Q function error, as in TD learning, with the additional terms due to the policy mismatch term W (but this theorem result is what we'd expect anyway?)\n\n\t3. Theorem 1 and the Corollary are useful to see how the overall off-policy learning error can be characterized in terms of the bias and variance. I think this result is important to exactly see the effect policy mismatch and the induced variance has in the overall learning algorithm. \n\n\t4. The experimental analysis of this paper is rather weak. The only strong result here is Theorem 1 - but it is difficult to justify the usefulness of it. In the experimental studies, I expected ablation analysis demonstrating the effect of this variance term and how the critic evaluation error influences the performance of standard off-policy actor-critic algorithms like SAC/DDPG.\n\n\t5. The paper discusses the different sampling schemes, and I thought the motivation was to see why these sampling schemes often work well in practice. However, from the context of the paper, it is not clear how this contribution is justified - I do not see any clear statements/results backing this claim?\n", "summary_of_the_paper": "This paper studies the bias variance perspective of off-policy actor-critic algorithms. The policy mismatch in off-policy learning leads to a variance issue (often due to importance sampling) while the bias is due to the mismatch of the behaviour and the target policies. This paper studies the setting where the behaviour policy is unknown. The paper studies why sampling schemes from the experience replay buffer often work well - since they lead to lower bias and variance issues than uniform sampling from the buffer.  The key contribution of this work is to provide theoretical justification, for off-policy actor-critic algorithms from a bias-variance perspective. \n", "summary_of_the_review": "I think this paper is interesting and careful studies of existing algorithms that work well in practice is required. However, this work needs more analysis (either experimentally or theoretical justifications) for it to be ready for acceptance. There is only one theory result (Theorem 1) which characterizes the off-policy actor-critic algorithms. However, this result statement is itself not novel and is derived from a vast majority of similar results in RL literature. In practice, I expected a lot more ablation studies characterizing the bias-variance trade-off. The paper perhaps has more claims than what it could demonstrate - and clearly needs more work for it to be ready for acceptance. I would encourage the authors to pick some simpler tasks and demonstrate the bias/variance analyais on some simple mdps too - instead of only showing performance curves for different sampling schemes on some standard mujoco tasks (which often is hard to interpret and not clear how these results are supporting the advertised claim)", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Lw02O7gbY7y", "reviewer": "Reviewer_e5zQ", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "========== Novelty =============\n\nThe idea of adjusting sampling probability of transitions in the replay buffer for off-policy learning is not new, and has been explored in a number of orthogonal ways as also mentioned in the current paper. This paper investigates a theoretically motivated approach for decomposing the evaluation errors and studies empirical properties of a number of other sampling methods.\n\n========== Literature reviews =============\n\nAs mentioned by the authors, off-policy evaluation learning has been categorized into importance sampling based and regression based. However, in practice, it is more common to combine the aforementioned ideas with contraction operators to carry out scalable off-policy learning when combined with function approximations. Notable examples include n-step Q-learning [1], Retrace [2], Peng's Q [3] among others [4-6]. I think they might be of direct interest if the authors' attempt is to analyze the stability of off-policy learning algorithms.\n\n[1] Hessel et al, Rainbow: combining improvements in deep RL, 2018\n[2] Munos et al, Safe and sample efficient RL, 2016\n[3] Kozuno et al, Revisiting Peng's Q lambda for modern RL, 2021\n[4] Harutyunyan et al, Q(lambda) with off-policy corrections, 2016\n[5] Tang et al, Taylor expansion policy optimization, 2020\n[6] Rowland et al, Adaptive trade-offs in off-policy learning, 2019\n\nThe author has also missed a ref [7] on connecting replay with loss functions.\n\n[7] Fujimoto et al, An equivalence between loss function and non-uniform sampling, 2021\n\n========== Detailed questions =============\n\n1. Overall, the notations are a bit confusing throughout the paper. The paper uses rho_{rho_i} to represent discounted visitation distribution rho starting from rho_i, and uses rho_i to represent the discounted visitation distribution at step i. Putting such notations together makes it quite difficult to read in general. I'd suggest simplifying the notations by e.g., getting rid of a general initial distribution but focusing on a single starting state s_0, or adopting some other ways to represent rho_{rho_i}.\n\n2. The indices e and i are also a bit counterintuitive. I'd suggest using i for the update iteration and t for the time stpe.\n\n3. Algo 1 does not necessarily reflect an exact off-policy actor-critic algorithm used in practice. In particular, the data collection policy might be a perturbed policy (e.g., epsilon-greedy or gaussian corrupted version of the target policy pi^e). I think it is worth making this clear in the presentation.\n\n4. In Eqn 6, an \"average\" behavior policy is defined using all previous policies. One question I have in mind is the utility of defining such a distribution -- though by combining all discounted visitation distribution, we can define an average policy, this policy does not necessarily induce the average discounted visitation distribution. In other words, there can be an average discounted visitation dist which cannot be realized by any Markovian / non-stationary policy. \n\n5. Based on Thm 1, it seems that the evaluation always suffers from an error that is (1/1-gamma) * W, where W is the wasserstain distance mismatch between the current policy pi^N and average policy pi^D. This observation is based on the last term of the RHS in Thm 1. Does it mean that the error is irreducible when pi^N mismatches with pi^D (i.e., W>0)? I am not quite sure if this is true in the tabular case, in which the evaluation error should vanish as more samples come in -- as long as all state-action pairs are visited, the evaluation error should decrease and vanish. It is not clear how the result in Thm 1 is consistent in this case\n\n6. Though I appreciate that the authors try to connect theory with practice, I find the jump from Sec 4 to Sec 5 to be rather abrupt. In particular, I don't see why ERE's implementation of the sampling scheme directly relates to the error bounds in Sec 4. Can we say ERE seeks to minimize the error bound?\n\nA rather important factor here is that, intuitively, it is kind of clear why putting emphasis on recent experiences makes sense -- this is because overall RL algorithms prefer on-policy data over off-policy data to be more stable. In fact, even algorithms which are off-policy by design can perform much better when using near on-policy data, such as VMPO (over MPO) and R2D2 (over DQN). Therefore, the intuition of using recent experience is already there in the literature. What can be valuable here is how detailed implementation practices seeks to optimize a theoretically justified bound. Unfortunately, it is not reflected well here.\n\n7. Fig 2 shows the difference of different algorithms. It seems that different sampling methods do not have that much of a significant difference in the performance. Overall, the empirical observations do not make a convincing case as to why methods such as ERE matter.\n", "summary_of_the_paper": "The paper studies the policy evaluation error in off-policy actor critic algorithms. The core idea is to decompose the error into three terms: bellman error, policy mismatch bias and sampling variance. Based on the decomposition, the paper justifies ERE, a recently proposed replay sampling heuristic and empirically studies the properties of a number of other sampling methods.", "summary_of_the_review": "Overall, I think the paper is lacking in a few aspects.\n\n1. Theory is not presented in a very clear way. I think the theory results are not very convincing, in that it does not reconcile with certain intuitions. However, I might be missing something here and am curious to hear what the authors say.\n\n2. Theory does not connect with practice. A major point of the paper, to my understanding, is that it entails a potentially theoretically sound framework to explain replay practices. However, I don't think the authors have established a convincing case here -- in understanding the practice, the theory here does not provide much more information than plain intuitions we already have.\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: There was some disagreement between reviewers regarding the quality of the paper. Reading the paper, I had difficulty understanding what you were trying to achieve and, similarly to reviewer VgPP, felt the experimental section to be weak. While I can appreciate that compute is expensive, it would have been relevant to design more controllable continuous environments to get cleaner results in addition to those on MuJoCo. As it is, there is a lot of noise (and Table 1 does not contain confidence intervals) which, added to the general brittleness of RL algorithms, makes the experiments lack convincing power.

I encourage the authors to take all the feedback from the authors into account and resubmit an improved version of their work to another conference.
Decision: Reject