Year: 2021

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.

heading: 1 INTRODUCTION
text: A practical reinforcement learning (RL) algorithm is often in an actor-critic setting (Lin, 1992; Precup et al., 2000) where the policy (actor) generates actions and the Q/value function (critic) evaluates the policy’s performance. Under this setting, off-policy RL uses transitions sampled from a replay buffer to perform Q function updates, yielding a new policy π. Then, a finite-length trajectory under π is added to the buffer, and the process repeats. Notice that sampling from a replay buffer is an offline operation and that the growth of replay buffer is an online operation. This implies off-policy actor-critic RL lies between offline RL (Yu et al., 2020; Levine et al., 2020) and onpolicy RL (Schulman et al., 2015; 2017). From a bias-variance perspective, offline RL experiences large policy mismatch bias but low sampling variance, while 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-variance trade-off. This is the direction we explore this work.
To reduce policy mismatch bias, 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 usually not given in practice, one can either estimate the probability ratio from the data (Lazic et al., 2020; Yang et al., 2020; Sinha et al., 2020) or use other reasonable quantities, such as the Bellman error (Schaul et al., 2016), as the sampling weight. Even using a naive uniform sampling from the replay buffer, some off-policy actor-critic algorithms can achieve a nontrivial performance (Haarnoja et al., 2018; Fujimoto et al., 2018). These observations suggest we need to better understand the success of off-policy actor-critic algorithms, especially in practical situations where a fixed behavior policy is unavailable.
Our contributions are as follows. To understand the actor-critic setting without a fixed behavior policy, we construct a non-stationary policy that generates the averaged occupancy measure. We use this policy as a reference and show the policy evaluation error in an 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 action space. We avoid strong assumptions such as a fixed well-explored behavior policy, concentration coefficients, bounded probability ratios (e.g., ratios of current to behavior policy), and tabular or linear function approximation. Hence our analysis is more applicable to practical settings. In
addition, our analysis suggests that 1/age-based samplings (e.g., ERE, ERE apx, 1/age) have advantages 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 RL algorithms but also achieve better performances.

heading: 2 PRELIMINARIES

heading: 2.1 REINFORCEMENT LEARNING
text: Consider an infinite-horizon Markov Decision Process (MDP) 〈S, A, T, r, γ〉, where S, A are finite-dimensional continuous state and action spaces, r(s, a) is a deterministic reward function, γ ∈ (0, 1) is the discount factor, and T (s′|s, 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 ρ0, the objective of RL is to find a policy π that maximizes the γ-discounted cumulative reward when the actions along the trajectory follow π:
max π J(π) = max π
E [ ∞∑ i=0 γir(si, ai) ∣∣∣s0 ∼ ρ0, ai ∼ π(·|si), si+1 ∼ T (·|si, ai)] . (1)
Let ρi(s|ρ0, π, T ) be the state distribution under π at trajectory step i. Define the normalized state occupancy measure by
ρπρ0(s) , (1− γ) ∞∑ i=0 γiρi(s|ρ0, π, T ). (2)
Ideally, the maximization in (1) is achieved using a parameterized policy πθ and policy gradient updates with (Sutton et al., 1999; Silver et al., 2014):
∇θJ(πθ) = (1− γ)−1E(s,a)∼ρπθρ0 [(∇θ log πθ(a|s))Q πθ (s, a)]. (3)
Here ρπθρ0 (s, a) = ρ πθ ρ0 (s)πθ(a|s) is given in (2), and Q πθ is the Q function under policy πθ:
Qπ(s, a) = E [ ∞∑ i=0 γir(si, ai) ∣∣∣s0 = s, a0 = a, ai ∼ π(·|si), si+1 ∼ T (·|si, ai)] . (4)
Off-policy RL estimates Qπ by approximating the solution of the Bellman fixed-point equation:
(BπQπ)(s, a) = r(s, a) + γEs′∼T (·|s,a), a′∼π(a|s)Qπ(s′, a′) = Qπ(s, a). It is well-known that Qπ is the unique fixed point of the Bellman operator Bπ . Hence if (BπQ̂)(s, a) ≈ Q̂(s, a), 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.

heading: 2.2 OFF-POLICY ACTOR-CRITIC ALGORITHM
text: We study an off-policy actor-critic algorithm of the form shown in Alg. 1. In line 2, for episode index e, πe samples one trajectory of length L. The transitions in this trajectory are then added to the replay buffer. Since the policies for different episodes are distinct, the collection of transitions in the replay buffer are generally inconsistent with the current policy. Notice the trajectory is simply collected by πe, not a perturbed version of πe (e.g., gaussian corrupted version of pie).
Line 3 is a supervised learning that minimizes the Bellman error of Q̂ using gradient descents, making (BπeQ̂)(s, a) ≈ Q̂(s, a) for (s, a) in the replay buffer. When this holds, we will prove that the “distance” between Q̂ and Qπ e
become smaller over the replay buffer. This is a crucial step for line 4 to be truly useful. In line 4, Qπ e is replaced by Q̂, and the policy is updated accordingly.
In practice, line 3 is replaced by mini-batch updates (Fujimoto et al., 2018; Haarnoja et al., 2018) where the summation of J(Q̂φ) is approximated by a sum over the mini-batches. In section 5.2, we show that a uniform-weighted mini-batch sampling biases learning towards older samples; this motivates the need for a countermeasure.
Algorithm 1 Off-policy Actor-critic Algorithm
Require: Parameterized policy πe = πθe and Q function estimate Q̂φ. Learning rate α. 1: for episode e = 1, 2, ... do 2: Sample a length-L trajectory {(sei , aei )} L−1 i=0 with initial distribution ρ0(s) and policy π e(a|s).
3: Evaluate the Bellman error as J(Q̂φ) = ∑e j=1 ∑L−1 i=0 ( Q̂φ(s j i , a j i )− (Bπ e Q̂φ)(s j i , a j i ) )2
and update Q̂φ as φ← φ− α∇φJ(Q̂φ).
4: Approximate Eq. (3) as ∇θĴ(πθ) = (1 − γ)−1E(s,a)∼ρπθρ0 [(∇θ log πθ(a|s))Q̂(s, a)] and update as θe+1 = θe + α∇θĴ(πθ). 5: end for
Note that Alg. 1 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 1, we will address this inconsistency by approximating the Q function using finite-length trajectories.

heading: 2.3 THE CONSTRUCTION OF OUR BEHAVIOR POLICY
text: Although Alg. 1 doesn’t have a fixed behavior policy, in Lemma 1, we construct a non-stationary policy that generates the averaged occupancy measure at every step. This describes the averagedover-episode behavior at every trajectory step i of the historical trajectory {(sei , aei )} L−1,N i,e=0,1. We hence define it to be our behavior policy and use it as a reference when analyzing Alg. 1.
The construction is as follows. Denote the state distribution at trajectory step i in episode e as ρei (s) = ρi(s|ρ0, πe, T ). By Eq. (2), ρπ e ρ0 is the state occupancy measure generated by (ρ0, π e, T ). Intuitively, ρπ e
ρ0 describes the discounted state distribution starting at trajectory step 0 in episode e.
More generally, define ρπ e
ρei as the state occupancy measure generated by (ρei , π
e, T ). Then, ρπ e
ρei describes the discounted state distribution starting at trajectory step i in episode e.
ρπ e
ρei (s) , (1− γ) ∞∑ j=i γj−iρej(s) (5)
Behavior policy through averaging. Since Alg. 1 considers trajectories from all episodes, the average-over-episodes distribution %(i) = N−1 ∑ e ρ πe ρei will be of interest. Namely, %(i) is the average of all occupancy measures starting at step i. To describe the average-over-episodes behavior at step i, we want a policy that generates %(i), and Eq. (5) helps construct such a policy. Concretely, let ρi, π D i (a|s) be the averaged state distribution and the averaged policy at step i, respectively.
%(i)(s) , N−1 N∑ e=1 ρπ e ρei (s), ρi(s) , N −1 N∑ e=1 ρei (s), π D i (a|s) ,
∑N e=1 π
e(a|s)ρπeρei (s)∑N e=1 ρ πe ρei (s) . (6)
Lemma 1 shows πDi in Eq. (6) is a notion of behavior policy in the sense that (ρi, π D i , T ) generates %(i); i.e., πDi generates the averaged occupancy measures when the initial state follows ρi. Since π D i describes the averaged discounted behavior starting at step i, we define it to be our behavior policy. This is a key to analyzing the policy evaluation error in Alg. 1.
Lemma 1. Let ρπ D i
ρi (s) be the normalized state occupancy measure generated by (ρi, π D i , T ). Then
%(i)(s) = ρ πDi ρi (s) a.e. and hence from Eq. (6), N−1 ∑N e=1 ρ πe ρei (s)πe(a|s) = ρπ D i ρi (s)πDi (a|s) a.e.

heading: 3 RELATED WORK
text: There are two main approaches to off-policy RL: importance sampling (IS) (Tokdar & Kass, 2010) and regression-based approach. IS has a low bias but high variance, while the opposite holds for the regression-based approach. Below, we briefly review these techniques.
Importance Sampling. Standard IS uses behavior policy to form an importance weight from the probability ratio of the current to the behavior policy. For a fully accessible behavior policy, examples 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; Yin et al., 2021). Alternatively, one 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 approach (Lazic et al., 2020), a Lagrangian approach (Yang et al., 2020), or a variational approach (Sinha et al., 2020). 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, 2019) 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 (Fujimoto et al., 2020).
Regression-based. A regression-based approach can achieve strong experimental results using proper exploration and function approximation (Fujimoto et al., 2018; Haarnoja et al., 2018). It also admits strong theoretical results such as generalization error using a concentration coefficient (Le et al., 2019), policy evaluation error using bounded probability ratios (Agarwal et al., 2019)[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 a fixed behavior policy and bounded probability ratios, which rarely hold in practice. We hence construct a non-stationary behavior policy to avoid this issue.
Combined. Prior work also suggests that combining IS and the regression-based yields robust results (Dudı́k 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 include nstep 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; Tang et al., 2020; Rowland et al., 2020).

heading: 4 POLICY EVALUATION ERROR OF OFF-POLICY ACTOR-CRITIC ALGORITHMS
text: Let Q∗, Qπ N
be the Q function of the optimal policy and πN , respectively. Let Q̂ be the estimated Q function. The performance error |Q̂−Q∗| decomposes into |Q̂−QπN |+ |QπN −Q∗|. The first term |Q̂−QπN | 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 optimality gap and to bound this term currently requires strong assumptions such as tabular or linear MDPs (Jin et al., 2018; 2020). In an off-policy actor-critic setting, the policy evaluation error has not been analyzed adequately since most analysis requires a 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 analyze 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 1-Wasserstein distance between the policies (πN , πDi ), and the variance term in the number of trajectories N . Note π D i is the behavior policy at trajectory step i defined in Eq. (6). The use of 1-Wasserstein distance (Villani, 2008) makes the results 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 a bias-variance perspective in the next section.

heading: 4.1 PROBLEM SETUP
text: Notation. In episode e, a length-L trajectory {(sei , aei )} L−1 i=0 following policy π e 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 i, i+ 1, . . . , 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 γj−i relative to step i. Hence, we will use a Bellman error and a policy mismatch error that reflects the dependency on the trajectory step and the discount factor. For f : S × A → R and g : S → R, define an averaging-discounted operator over the replay buffer in N episodes:
ẼLi f(·, ·) , 1
N N∑ e=1 L−1∑ j=i (1− γ)γj−if(sej , aej) and ẼLi g(·) , 1 N N∑ e=1 L−1∑ j=i (1− γ)γj−ig(sej)
Using ẼLi , the Bellman error of Q̂ and the distance between the policies (π N , πDi ) on the replay buffer are written as
i,L Q̂ = ẼLi ∣∣∣Q̂(·, ·)− (BπN Q̂)(·, ·)∣∣∣, W i,L1 = Ẽ L i W1(π N ||πDi )(·). (7)
W1(π N ||πDi )(s) = W1(πN (·|s)||πDi (·|s)) is the 1-Wasserstein distance between two policies at state s, which can be viewed as a function of (s, a). Both the Bellman error i,L Q̂ and the policy mismatch error W i,L1 depend on trajectory step i and are both discounted by γ.
Assumptions. We now relate the Bellman error and the policy mismatch error defined in Eq. (7) to the policy evaluation error |Q̂−QπN |. First, to control the error of Q̂ by policy mismatch error in W1 distance, we assume that for every state, Q̂ and Qπ N
are LA-Lipschitz 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 on the Q functions and apply a concentration inequality. Because Alg. 1 only samples one trajectory in each episode, higherorder quantities (e.g., variance) is unavailable. This motivates us to use first-order quantities (e.g., a uniform bound on the Q functions) and apply Hoeffding’s inequality. Hence, we assume that Q̂(s, a) and Qπ N
(s, a) are bounded in the interval [0, rmax/(1 − γ)] and that the action space is bounded with the diameter diamA. A justification of these assumptions is provided in Appendix A.2.

heading: 4.2 POLICY EVALUATION ERROR
text: Observe that the Q function, Eq. (4), 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 i up to a constant error, we need samples at least to step i+ Ω((1− γ)−1). Hence, we first prove the main theorem with i = 0 and L =∞. Then, we generalize the result to i ≥ 0 and finite L in Corollary 1. Theorem 1. Let N be the number of episodes. For f : S × A → R, define the operator Ẽ∞0 f , 1 N ∑N e=1 ∑∞ i=0(1 − γ)γif(sei , aei ). Denote the policy mismatch error and the Bellman error as W 0,∞1 = Ẽ ∞ 0 W1(π N ||πD0 )(·) and 0,∞ Q̂ = Ẽ∞0 |Q̂(·, ·)− (Bπ N Q̂)(·, ·)|, respectively. Assume
(1) For each s ∈ S, Q̂(s, a) and QπN (s, a) are LA-Lipschitz in a.
(2) Q̂(s, a) and Qπ N (s, a) are bounded and take values in [0, rmax/(1− γ)].
(3) The action space is bounded with diameter diamA <∞.
Then, with probability at least 1− δ, E(s0,a0)∼ρ0(s)πD0 (a|s) ∣∣∣Q̂(s0, a0)−QπN (s0, a0)∣∣∣
≤ r max
1− γ
√ 1
2N log
2 δ + ( rmax (1− γ)2 + 2LAdiamA 1− γ )√ 2 N log 2 δ + 1 1− γ ( 0,∞ Q̂ + 2LAW 0,∞ 1 ) .
Theorem 1 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 in the number of episodesN . On the other hand, W 0,∞1 is the “policy mismatch bias” w.r.t. πN . Because the behavior policy πD0 is a mixture of the historical policies {πe}Ne=1, Eq. (6), we expect it to increase in N until πN begins to converge.
Theorem 1 only indicates the difference between Q̂ andQπ N
at i = 0 and infinite-length trajectories. We can generalize it to i ≥ 0 and finite-length trajectories as follows. Recall from Eq. (6) and Lemma 1, the average state distribution at the i-th step, ρi, and the behavior policy at the i-th step,
πDi , generate the average state occupancy measure, i.e., ρ πDi ρi = N−1 ∑N e=1 ρ πe ρei a.e. Therefore, by restricting attention to the states sampled at time steps i, i + 1, . . . the “initial state distribution” and the behavior policy become ρi and π D i , which generalizes Theorem 1 from i = 0 to i ≥ 0. In addition, due to γ-discounting, we may use length-L trajectories to approximate infinite-length ones, provided that L ≥ i+ Ω((1− γ)−1). These observations lead to the following corollary. Corollary 1. Fix assumptions (1) (2) (3) of Theorem 1. Rewrite the policy mismatch error and the Bellman error as W i,L1 = Ẽ L i W1(π N ||πDi )(·) and i,L Q̂ = ẼLi |Q̂(·, ·)− (Bπ N
Q̂)(·, ·)|, respectively. Note ẼLi is defined in Eq. (7). Then, with probability at least 1− δ,
E(si,ai)∼ρi(s)πDi (a|s) ∣∣∣Q̂(si, ai)−QπN (si, ai)∣∣∣ ≤
rmax
1− γ
√ 1
2N log
2 δ + ( rmax (1− γ)2 + 2LAdiamA 1− γ )(√ 2 N log 2 δ + γL−i ) + 1 1− γ ( i,L Q̂ + 2LAW i,L 1 ) .
Moreover, if i ≤ L − log log γ with 0 < < 1 and the constants are normalized as LA = c/(1 − γ), i,L Q̂ = ξi,L Q̂ /(1− γ), then, with probability at least 1− δ,
E(si,ai)∼ρi(s)πDi (a|s) ∣∣∣Q̂(si, ai)−QπN (si, ai)∣∣∣
≤Õ ( 1 (1− γ)2 ( (rmax + c · diamA)(1/ √ N + ) + ξi,L Q̂ + c ·W i,L1 )) ,
where Õ(·) is a variant of O(·) that ignores logarithmic factors.
Note that if i = 0 and L = ∞, Corollary 1 is identical to Theorem 1. Because the Bellman error of Q̂ and the bias of the policy are both evaluated using the averaging-discounted operator ẼLi , Corollary 1 implies the difference of Q̂ and Qπ N
at trajectory step i 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 ≥ i.
Normalization. Although the first conclusion in Corollary 1 gives a bound on the error of Q̂, the constants may implicitly depend on the expected horizon (1−γ)−1.Hence its interpretation requires care. For instance, LA, the Lipschitz constant of the Q 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 a few trajectory steps, so the Lipschitzness of Qπ in actions is sublinear in (1 − γ)−1. On the other hand, if the policy π fails to correct a disturbance δ, due to error propagation, the error δ propagates to every future step, leading to a linear error dependency to the horizon O(δH). Therefore, the Lipschitzness of Qπ in actions can be as large as O((1 − γ)−1). In addition to LA, the Bellman error i,LQ̂ should scale linearly in (1 − γ) −1 because the Q function represents the discounted cumulative reward, Eq. (4), which scales linearly in (1 − γ)−1. These observations suggest that i,L
Q̂ and LA in Corollary 1 are either linear in the
horizon or lie between sublinear and linear. To better capture the dependency on the horizon, we normalize the constants and get the second conclusion.
Interpretation. The second conclusion shows the approximation error from infinite to finitelength trajectories is bounded by a constant for i ≤ L − log log γ Taylor ≈ L − Ω((1 − γ)−1), and will become harder to control for the higher i 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. 1 has two phases. At phase 1, 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, so the policy evaluation error becomes harder to improve and πN tends to converge.

heading: 5 PRACTICAL SAMPLING STRATEGIES
text: 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, Wang & Ross (2019) proposes to emphasize recent experience (ERE) because the recent policies are closer to 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.

heading: 5.1 EMPHASIZING RECENT EXPERIENCE
text: In Wang & Ross (2019), the authors use a length-K trajectory (K may differ across episodes) and perform K updates. In the k-th (1 ≤ k ≤ K) update, a mini-batch is sampled uniformly from the most recent ck = max(N0ηk L0 K , cmin) samples, where N0 is the current size of the replay buffer, L0 is the maximum horizon of the environment, η 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: (L0, η, cmin) = (1000, 0.996, 5000). One can see that η = 1 does a uniform weighting over the replay buffer, and the emphasis on the recent data becomes larger as η 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-uniform weighting:
wt ∝ 1 max(t, cmin, N0ηL0) − 1 N0 + 1(t ≤ cmin) cmin max
( ln
cmin N0ηL0
, 0 ) , (8)
where t is the age of a data point relative to the newest time step; i.e., w1 is the newest sample.
Note that Prop. 1 holds for η 6= 1 because it is derived from the geometric series formula: (1 − ηn)/(1 − η), which is valid when η 6= 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 η ≈ 1, Eq. (8) suggests wt is proportional to 1/(N0ηL0) − 1/N0 for all 1 ≤ t ≤ N0, which is a uniform weighting. The emphasis on the recent experience (indicated by 1(t ≤ cmin)) is also evident from Eq. (8). Precisely, the second term increases logarithmically ln 1η when η becomes smaller, so the smaller η indeed gives more weight on the recent experience.
To understand the effect of 1/age, recall from section 2.2 that in practice, Q̂ is updated using minibatch samples. Define a point (sei , a e i )’s time step as i+ 1 + L · (e− 1). Then the expected number of times in all batch samples that a point at a certain time step is selected (the expected selection number) gives the aggregate weight over the time steps. As shown in Figure. 1, 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.

heading: 5.2 POLICY EVALUATION ERROR UNDER NON-UNIFORM WEIGHTS
text: 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 1 to non-uniform weights {wi > 0} such that the policy evaluation error is bounded by three terms: Hoeffiding error Õ( √∑ i w 2 i / ∑ i wi) (weighted variance), weighted bias W i,L 1,w, and normalized weighted bellman error ξi,L Q̂,w
. Since the weighted bellman error is well-controlled by supervised learning, in the following, 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 1 shows the uniform sampling (for each sampling from the replay buffer) makes the aggregate weights (expected selection number) bias toward old samples. Because the old policies tend to be distant from the current policy, the uniform sampling induces a larger weighted bias W i,L1,w than ERE and 1/age do. As for the variance from sampling, we generalize Corollary 1’s uniform case: Õ(1/ √ N) to Corol-
lary 2’s weighted case: Õ( √∑ i w 2 i / ∑ i wi). That is, the variance under non-uniform weight is
bounded by the Hoeffding error Õ( √∑ i w 2 i / ∑ i wi) and is reduced to Õ(1/ √ N) when the weights are equal. Furthermore, one can prove that the Hoeffding error is minimized under uniform weights: Proposition 2. Let {wt > 0}Nt=1 be the weights of the data indexed by t. Then the Hoeffding error√∑N t=1 w 2 t / ∑N t=1 wt is minimized when the weights are equal: wt = c > 0, ∀ t.
Therefore, the variance from sampling is large under non-uniform aggregate weights and is minimized by uniform aggregate weights. Since the uniform sampling leads to more non-uniform aggregate 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.

heading: 5.3 EXPERIMENTAL VERIFICATION
text: Since we’ve established a 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 samplings 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, a 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 MuJoCo continuous-control environments (Todorov et al., 2012): Humanoid, Ant, Walker2d, HalfCheetah, and Hopper. All tasks have a maximum horizon of 1000 and are trained using a Pytorch Soft-Actor-Critic (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 perspective.
Most hyper-parameters of the SAC algorithm are the same as that in Tandon (2018) except for the batch size, where we find a batch size of 512 tends to give more stable results. Our code is available at https://github.com/sunfex/weighted-sac. The SAC implementation and the MuJoCo environment are licensed under the MIT license and the personal student license, respectively. The experiment is run on a server with an Intel i7-6850K CPU and Nvidia GTX 1080 Ti GPUs.
In Figure 2, 1/age-based samplings (ERE, ERE apx, 1/age) perform better than the uniform weighting 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, so Eq. (8) is indeed a good approximation of the ERE strategy. This also explains the implicit connection between ERE and 1/age weighting strategies: ERE is almost equivalent to ERE apx and 1/age is the main factor in ERE apx, so ERE and 1/age
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 1). Table 1 shows the SAC with 1/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.

heading: 6 CONCLUSION
text: 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 a successful off-policy actor-critic algorithm should have a careful sampling strategy that controls its bias and variance. Motivated by the empirical success of Emphasizing Recent Experience (ERE), we prove that ERE is a variant of the 1/age weighting. We then explain that 1/age-based samplings (e.g., ERE, ERE apx, 1/age) have smaller bias and variance and are preferable over uniform sampling. Our experiments verify that soft actorcritic with 1/age-based samplings outperforms the prior work. We hence conclude that a simple but careful design in the sampling of off-policy actor-critic RL can lead to better performances.

heading: 7 ETHICS STATEMENT
text: 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 are abundant while new samples 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 challenges of delegating important decisions to a machine, and data privacy issues (e.g., recommendation agents). These implications apply to most control and RL studies and are not associated with any specific work.

heading: 8 REPRODUCIBILITY STATEMENT
text: To ensure reproducibility of the experiments, we’ve provided hyper-parameters in Appendix A.1 and the source code at an anonymous Github page https://github.com/sunfex/ weighted-sac. Discussions on the assumptions are in section 4.1 and justifications are in Appendix A.2. A complete proof of the theorems and lemmas can be found in Appendix.

heading: A APPENDIX
text: A.1 HYPER-PARAMETERS
To train the SAC agents, we use deep neural networks to parameterize the policy and Q functions. Both networks consist of dense layers with the same widths. Table 2 presents the suggested hyperparameters. As mentioned in the experiment section, the hyper-parameters are similar as the implementation in Tandon (2018).
A.2 JUSTIFICATION OF ASSUMPTIONS
In section 4.1, we introduce three main assumptions in this work. Below is a validation for each.
Environment Hopper HalfCheetah Walker2D Ant Humanoid Temperature 0.2 0.2 0.2 0.2 0.05
A.3 THE CONSTRUCTION OF OUR BEHAVIOR POLICY
We first discuss some important relations between state occupancy measures and Bellman flow operator. Similar results about Fact 1 and 2 be found in Liu et al. (2018)[Lemma 3]. Definition 1 (Bellman flow operator). The Bellman flow operatorBρ0,π,T (·) generated by (ρ0, π, T ) with discount factor γ is defined as
Bρ0,π,T (ρ)(s) , (1− γ)ρ0(s) + γ ∫ T (s|s′, a′)π(a′|s′)ρ(s′)ds′da′.
Fact 1. Bρ0,π,T is a γ-contraction w.r.t. total variational distance.
Proof. Let p1(s), p2(s) be the density functions of some state distributions.
DTV (Bρ0,π,T (p1)||Bρ0,π,T (p2)) = 1
2 ∫ ∣∣Bρ0,π,T (p1(s))−Bρ0,π,T (p2(s))∣∣ds = 1
2
∫ γ ∣∣∣ ∫ T (s|s′, a′)π(a′|s′)(p1(s′)− p2(s′))ds′da′∣∣∣ds
≤ γ 2
∫ T (s|s′, a′)π(a′|s′) ∣∣p1(s′)− p2(s′)∣∣ds′da′ds = γ
2 ∫ ∣∣p1(s′)− p2(s′)∣∣ds′ = γDTV (p1||p2). Fact 2. The normalized state occupancy measure ρπρ0 generated by (ρ0, π, T ) with discount factor γ is a fixed point of Bρ0,π,T ; i.e., Bρ0,π,T (ρ π ρ0)(s) = ρ π ρ0(s).
Proof.
ρπρ0(s) =(1− γ) ∞∑ i=0 γifi(s|ρ0, π, T )
=(1− γ)f0(s|ρ0, π, T ) + γ(1− γ) ∞∑ i=0 γifi+1(s|ρ0, π, T )
=(1− γ)ρ0(s) + γ(1− γ) ∞∑ i=0 γi ∫ T (s|s′, a′)π(a′|s′)fi(s′|ρ0, π, T )ds′da′
=(1− γ)ρ0(s) + γ ∫ T (s|s′, a′)π(a′|s′)(1− γ) ∞∑ i=0 γifi(s ′|ρ0, π, T )ds′da′
=(1− γ)ρ0(s) + γ ∫ T (s|s′, a′)π(a′|s′)ρπρ0(s ′)ds′da′ = Bρ0,π,T (ρ π ρ0)(s).
Thus, the Bellman flow operator is useful to analyze the state occupancy measures, and we have the following lemma to construct the behavior policy πDi . Lemma 1. Let ρei (s) the state distribution at trajectory step i in episode e. Let ρπ e
ρei (s) be the normalized occupancy measure starting at trajectory step i in episode e. Then 1N ∑N e=1 ρ πe ρei (s) = ρ πDi ρi (s) a.e., where ρπ D i ρi is the normalized state occupancy measure is generated by (ρi, π D i , T ).
Moreover, we have 1N ∑N e=1 ρ πe ρei (s)πe(a|s) = ρπ D i ρi (s)πDi (a|s) a.e.
Proof. Precisely, ρei (s) = ρi(s|ρ0, πe, T ) is the state distribution at trajectory step i following the laws of (ρ0, πe, T ). Since ρπ e
ρei is the normalized occupancy measure generated by (ρei , π e, T ), each ρπ e
ρei is the fixed-point of the Bellman flow equation:
ρπ e
ρei (s) = (1− γ)ρei (s) + γ
∫ T (s|s′, a′)πe(a′|s′)ρπ e
ρei (s′)ds′da′, ∀ e ∈ [1, ..., N ].
This implies the average normalized occupancy measure is the fixed point of the Bellman flow equation characterized by (ρi, π D i , T ):
1
N N∑ e=1 ρπ e ρei (s) = 1 N N∑ e=1 [ (1− γ)ρei (s) + γ ∫ T (s|s′, a′)πe(a′|s′)ρπ e ρei (s′)ds′da′ ]
= (1− γ)ρi(s) + γ ∫ T (s|s′, a′) 1
N N∑ e=1 [ πe(a′|s′)ρπ e ρei (s′) ] ds′da′
= (1− γ)ρi(s) + γ ∫ T (s|s′, a′) ∑N e=1 π e(a′|s′)ρπeρei (s ′)∑N
e=1 ρ πe ρei (s′)
∑N e=1 ρ πe ρei (s′)
N ds′da′
= (1− γ)ρi(s) + γ ∫ T (s|s′, a′)πDi (a′|s′) 1
N N∑ e=1 ρπ e ρei (s′)ds′da′,
where πDi (a|s) , ∑N e=1 π e(a|s)ρπ e ρe i (s)∑N
e=1 ρ πe
ρe i (s)
is the average behavior policy at step i. Since the Bellman flow
operator is a γ-contraction in TV distance and hence has a unique fixed point in TV distance, denoted as ρπ D i
ρi (s), we arrive at 1N ∑N e=1 ρ πe ρei (s) = ρ πDi ρi
(s) almost everywhere. Also, by construction, we have
1
N N∑ e=1 ρπ e ρei (s)πe(a|s) = ρπ D i ρi (s)πDi (a|s) a.e.
A.4 POLICY EVALUATION ERROR
Lemma 2. If Q(s, a) is LA-Lipschitz in a for any s, then, for any state distribution ρ, Es∼ρ ∣∣∣Ea∼π1(·|s)Q(s, a)− Ea∼π2(·|s)Q(s, a)∣∣∣ ≤ LAEs∼ρW1(π1(·|s)||π2(·|s)).
Proof. For any fixed s, we have Ea∼π1(·|s)Q(s, a)− Ea∼π2(·|s)Q(s, a) = LA [ Ea∼π1(·|s) Q(s, a)
LA − Ea∼π2(·|s)
Q(s, a)
LA ] ≤LA
[ sup ‖f‖Lip≤1 Ea∼π1(·|s)f(a)− Ea∼π2(·|s)f(a) ] = LAW1(π1(·|s)||π2(·|s)),
where the second line follows from Kantorovich-Rubinstein duality (Villani, 2008). Since the 1- Wasserstein distance W1 is symmetric, we can interchange the roles of π1 and π2, yielding∣∣∣Ea∼π1(·|s)Q(s, a)− Ea∼π2(·|s)Q(s, a)∣∣∣ ≤ LAW1(π1(·|s)||π2(·|s)). Taking the expectation Es∼ρ on both sides completes the proof.
Lemma 3. If Qπ(s, a) is LA-Lipschitz in a for any s, then E(s0,a0)∼ρ̂0(s)πD0 (a|s) ∣∣∣QπD0 (s0, a0)−Qπ(s0, a0)∣∣∣ ≤ LA 1− γ E s∼ρ
πD0 ρ̂0
W1(π D 0 (·|s)||π(·|s)).
Proof. For any (s, a), we have
|Qπ D 0 (s, a)−Qπ(s, a)| =γ ∣∣∣Es′∼T (·|s,a)EπD0 QπD0 (s′, πD0 (s′))− EπQπ(s′, π(s′))∣∣∣
≤γEs′∼T (·|s,a) ∣∣∣EπD0 ,πQπD0 (s′, πD0 (s′))−Qπ(s′, πD0 (s′)) +Qπ(s′, πD0 (s′))−Qπ(s′, π(s′))∣∣∣
≤γEs′∼T (·|s,a) (∣∣∣EπD0 QπD0 (s′, πD0 (s′))−Qπ(s′, πD0 (s′))∣∣∣+ ∣∣∣EπD0 ,πQπ(s′, πD0 (s′))−Qπ(s′, π(s′))∣∣∣)
≤γEs′∼T (·|s,a) ( EπD0 ∣∣∣QπD0 (s′, πD0 (s′))−Qπ(s′, πD0 (s′))∣∣∣+ LAW1(πD0 (·|s′)||π(·|s′))), where the last line follows from Lemma 2. Let ρπ
D 0 i be the state distribution at step i following the
laws of (ρ̂0, πD0 , T ). Take expectation over ρ̂0 and expand the recursive relation. We arrive at
E(s0,a0)∼ρ̂0(s)πD0 (a|s) ∣∣∣QπD0 (s0, a0)−Qπ(s0, a0)∣∣∣ ≤ LA ∞∑
i=1
γiE si∼ρ πD0 i W1(π D 0 (·|si)||π(·|si))
= LA
1− γ E s∼ρ
πD0 ρ̂0
W1(π D 0 (·|s)||π(·|s))− LAEs∼ρ̂W1(πD0 (·|s)||π(·|s))
≤ LA 1− γ E s∼ρ
πD0 ρ̂0
W1(π D 0 (·|s)||π(·|s)),
where the second line follows from ρπ D 0
ρ̂0 = (1− γ) ∑∞ i=0 γ iρ πD0 i .
Lemma 4. If Q(s, a) is LA-Lipschitz in a for any s, then E(s0,a0)∼ρ̂0(s)πD0 (a|s) ∣∣∣Q(s0, a0)−QπD0 (s0, a0)∣∣∣
≤ E (s,a)∼ρ πD0 ρ̂0 (s)πD0 (a|s) ∣∣∣Q(s, a)− BπQ(s, a)∣∣∣+ LAW1(π(·|s)||πD0 (·|s)) 1− γ .
Proof. For any (s, a) ∈ S ×A, we have a recursive relation:∣∣∣Q(s, a)−QπD0 (s, a)∣∣∣ = ∣∣∣Q(s, a)− BπD0 QπD0 (s, a)∣∣∣ ≤ ∣∣∣Q(s, a)− BπD0 Q(s, a)∣∣∣+ ∣∣∣BπD0 Q(s, a)− BπD0 QπD0 (s, a)∣∣∣
= ∣∣∣Q(s, a)− BπD0 Q(s, a)∣∣∣+ γ∣∣∣Es′∼T (·|s,a),a′∼πD0 (·|s′)Q(s′, a′)−QπD0 (s′, a′)∣∣∣ ≤ ∣∣∣Q(s, a)− BπD0 Q(s, a)∣∣∣+ γEs′∼T (·|s,a),a′∼πD0 (·|s′)∣∣∣Q(s′, a′)−QπD0 (s′, a′)∣∣∣
Expand the recursive relation. We have E(s0,a0)∼ρ̂0(s)πD0 (a|s) ∣∣∣Q(s0, a0)−QπD0 (s0, a0)∣∣∣
≤Es0∼ρ̂0Ea0∼πD0 (·|s0) ∣∣∣Q(s0, a0)− BπD0 Q(s0, a0)∣∣∣
+ Es0∼ρ̂0 ∞∑ i=1 γiEa0,s1,a1,...,si−1,ai−1Esi∼T (·|si−1,ai−1),ai∼πD0 (·|si) ∣∣∣Q(si, ai)− BπD0 Q(si, ai)∣∣∣
=Es0∼ρ̂0 ∞∑ i=0 γiEa0,s1,a1,...,si,ai∼T,πD0 ∣∣∣Q(si, ai)− BπD0 Q(si, ai)∣∣∣
= 1
1− γ E (s,a)∼ρ
πD0 ρ̂0 (s)πD0 (a|s) ∣∣∣Q(s, a)− BπD0 Q(s, a)∣∣∣. (9)
The last line uses a fact for the normalized occupancy measure :
E ρ πD0 ρ̂0
= (1− γ) [ Es0∼ρ̂0Ea0∼πD0 (·|s0) + ∞∑ i=1 γiEs0∼ρ̂0Ea0∼πD0 (·|s0)...Esi∼T (·|si−1,ai−1),ai∼πD0 (·|si) ] .
We are almost done once the BπD0 in Eq. (9) is replaced by Bπ . Note that
E (s,a)∼ρ
πD0 ρ̂0 (s)πD0 (a|s) ∣∣∣Q(s, a)− BπD0 Q(s, a)∣∣∣ ≤E
(s,a)∼ρ πD0 ρ̂0 (s)πD0 (a|s) ∣∣∣Q(s, a)− BπQ(s, a)∣∣∣+ ∣∣∣BπQ(s, a)− BπD0 Q(s, a)∣∣∣ =E
(s,a)∼ρ πD0 ρ̂0 (s)πD0 (a|s) ∣∣∣Q(s, a)− BπQ(s, a)∣∣∣+ γ∣∣∣Es′∼T (·|s,a)Eπ,πD0 Q(s′, π(s′))−Q(s′, πD0 (s′))∣∣∣ Lem. 2 ≤ E
(s,a)∼ρ πD0 ρ̂0 (s)πD0 (a|s) [∣∣∣Q(s, a)− BπQ(s, a)∣∣∣+ γLAEs′∼T (·|s,a)W1(π(·|s′)||πD0 ·|s′)] =E
(s,a)∼ρ πD0 ρ̂0 (s)πD0 (a|s) ∣∣∣Q(s, a)− BπQ(s, a)∣∣∣ + LAE
s∼ρ πD0 ρ̂0
W1(π(·|s)||πD0 (·|s))− (1− γ)LAEs∼ρ̂0W1(π(·|s)||πD0 (·|s))
≤E (s,a)∼ρ
πD0 ρ̂0 (s)πD0 (a|s) ∣∣∣Q(s, a)− BπQ(s, a)∣∣∣+ LAW1(π(·|s)||πD0 (·|s)). (10)
The second-last line follows from that the distribution of s′ is ρπ D 0
ρ̂0,1 (s′) = ∫ sa T (s′|s, a)ρπ D 0 ρ̂0 (s, a),
which satisfies the identity
ρ πD0 ρ̂0 (s′) = (1− γ)ρ̂0(s′) + γ ∫ T (s′|s, a)ρπ D 0 ρ̂0 (s, a)dsda = (1− γ)ρ̂0(s′) + γρ πD0 ρ̂0,1 (s′).
Combining Eq. (9) and Eq. (10), the result follows.
Lemma 5. Let 0 ≤ f(s, a) ≤ ∆ be a bounded function for (s, a) ∈ S × A. Let Ẽ∞0 be the averaging-discounted operator with infinite-length trajectories in N episodes; i.e., Ẽ∞0 f =
1 N ∑N e=1 ∑∞ i=0(1− γ)γif(sei , aei ). Then, with probability greather than 1− δ,(
Ẽ∞0 − E ρ πD0 ρ̂0 (s)πD0 (a|s)
) f ≤ ∆ √ 2
N log
1 δ .
Proof. Let δse0(s) be the delta measure at the initial state in episode e. Because the empirical distribution ρ̂0 is composed of the realization of the trajectories’s initial states, we know ρ̂0 = 1 N ∑N e=1 δse0 . Then, Lemma 1 implies ρ πD0 ρ̂0
is an average of the normalized occupancy measures in N episodes.
ρ πD0 ρ̂0 (s)πD0 (a|s) a.e. = 1
N N∑ e=1 ρπ e δse0 (s)πe(a|s)
def. of ρπ e
δse0= 1
N N∑ e=1 ∞∑ i=0 (1− γ)γiρei (s|δse0 , π e, T )πe(a|s),
(11)
where ρei is the state density at trajectory step i in episode e. Since (s e i , a e i ) ∼ ρei (s|δse0 , π e, T )πe(a|s), we have(
Ẽ∞0 − E ρ πD0 ρ̂0 (s)πD0 (a|s)
) f = 1
N N∑ e=1 [ ∞∑ i=0 (1− γ)γif(sei , aei )− Eρπeδse0 (s)πe(a|s)f ] (11) = 1
N N∑ e=1 [ ∞∑ i=0 (1− γ)γi [ f(sei , a e i )− E[f(sei , aei )|se0] ]] = 1 N N∑ e=1 Me.
(12)
We claim that {Me}Ne=1 defined as Me = ∑∞ i=0(1− γ)γi [ f(sei , a e i )−E[f(sei , aei )|se0] ] is a martingale difference sequence. To see this, let Fe be the filtration of all randomness from episode 1 to e, with F0 being a null set. Clearly, we have Me ∈ Fe, E[Me|Fe−1] = 0 and Me ∈ [−∆,∆] since f(s, a) ∈ [0,∆] by assumption, which proves {Me}Ne=1 is a martingale difference sequence. Finally, since Me is bounded in [−∆,∆], by Azuma-Hoeffding inequality, we conclude that with probability greater than 1− δ,
Eq. (12) ≤ N−1 √∑N e=1(2∆) 2
2 log
1 δ = ∆
√ 2
N log
1 δ .
Theorem 1. Let N be the number of episodes. For f : S × A → R, define the operator Ẽ∞0 f , 1 N ∑N e=1 ∑∞ i=0(1 − γ)γif(sei , aei ). Denote the policy mismatch error and the Bellman error as W 0,∞1 = Ẽ ∞ 0 W1(π N ||πD0 )(·) and 0,∞ Q̂ = Ẽ∞0 |Q̂(·, ·)− (Bπ N Q̂)(·, ·)|, respectively. Assume
(1) For each s ∈ S, Q̂(s, a) and QπN (s, a) are LA-Lipschitz in a.
(2) Q̂(s, a) and Qπ N (s, a) are bounded and take values in [0, rmax/(1− γ)].
(3) The action space is bounded with diameter diamA <∞.
NoteW1(πN ||πDi )(s) meansW1(πN (·|s)||πDi (·|s)), which is a function of s. Then, with probability greater than 1− δ, we have
E(s0,a0)∼ρ0(s)πD0 (a|s) ∣∣∣Q̂(s0, a0)−QπN (s0, a0)∣∣∣
≤ r max
1− γ
√ 1
2N log
2 δ + ( rmax (1− γ)2 + 2LAdiamA 1− γ )√ 2 N log 2 δ + 1 1− γ ( 0,∞ Q̂ + 2LAW 0,∞ 1 ) .
Proof. The proof basically combines Lemma 3, 4 and 5. To start with, the objective is decomposed as:
E(s0,a0)∼ρ0(s)πD0 (a|s) ∣∣∣Q̂(s0, a0)−QπN (s0, a0)∣∣∣
=H1 + E(s0,a0)∼ρ̂0(s)πD0 (a|s) ∣∣∣Q̂(s0, a0)−QπN (s0, a0)∣∣∣
≤H1 + E(s,a)∼ρ̂0(s)πD0 (a|s) ∣∣∣Q̂(s0, a0)−QπD0 (s0, a0)∣∣∣+ ∣∣∣QπD0 (s0, a0)−QπN (s0, a0)∣∣∣
4, 3 ≤ H1 + 1
1− γ E (s,a)∼ρ
πD0 ρ̂0 (s)πD0 (a|s) [∣∣∣Q̂(s, a)− (BπN Q̂)(s, a)∣∣∣+ 2LAW1(πN (·|s)||πD0 (·|s))] =H1 +
H2 1− γ + 1 1− γ Ẽ∞0 [∣∣∣Q̂(·, ·)− (BπN Q̂)(·, ·)∣∣∣+ 2LAW1(πN ||πD0 )(·)] Assump. ≤ H1 +
H2 1− γ + 1 1− γ ( 0,∞ Q̂ + 2LAW 0,∞ 1 ) .
(13)
Because |Q̂(s, a)−QπN (s, a)| ∈ [0, r max 1−γ ], we know Ea∼πD0 (·|s)|Q̂(s, a)−Q πN (s, a)| ∈ [0, r max
1−γ ], too. Suppose ρ̂0 have N independent samples. By Hoeffding’s inequality, with probability ≥ 1− δ,
H1 = ( Es0∼ρ0 − Es0∼ρ̂0 ) Ea0∼πD0 (·|s0) ∣∣Q̂(s0, a0)−QπN (s0, a0)∣∣ ≤ rmax 1− γ
√ 1
2N log
1 δ . (14)
Also, let f(s, a) = ∣∣Q̂(s, a)−(BπN Q̂)(s, a)∣∣+2LAW1(πN (·|s)||πD0 (·|s)). Then f(s, a) is bounded in [0, r max
1−γ + 2LAdiamA]. Thereby, Lemma 5 implies that with probability greater than 1− δ, H2 = ( E (s,a)∼ρ
πD0 ρ̂0 (s)πD0 (a|s) − Ẽ∞0 )[∣∣∣Q̂(s, a)− (BπN Q̂)(s, a)∣∣∣+ 2LAW1(πN (·|s)||πD0 (·|s))] ≤ ( rmax
1− γ + 2LAdiamA )√ 2 N log 1
δ (15)
Combining Eq. (13), (14) and (15), a union bound implies with probability greater than 1− 2δ, E(s0,a0)∼ρ0(s)πD0 (a|s) ∣∣∣Q̂(s0, a0)−QπN (s0, a0)∣∣∣
≤ r max
1− γ
√ 1
2N log
1 δ + ( rmax (1− γ)2 + 2LAdiamA 1− γ )√ 2 N log 1 δ + 1 1− γ ( 0,∞ Q̂ + 2LAW 0,∞ 1 ) Finally, rescaling δ to δ/2 finishes the proof.
Corollary 1. Let ẼLi be the operator defined as ẼLi f = 1 N ∑N e=1 ∑L−1 j=i (1 − γ)γj−if(sej , aej). Fix assumptions (1) (2) (3) of Theorem 1. Rewrite the policy mismatch error and the Bellman error as W i,L1 = Ẽ L i W1(π N ||πDi )(·) and i,L Q̂ = ẼLi |Q̂(·, ·) − (Bπ N
Q̂)(·, ·)|, respectively, where W1(π
N ||πDi )(s) = W1(πN (·|s)||πDi (·|s)). Let ρi(s) be the average state density at trajectory step i over all N episodes. Then, with probability greater than 1− δ, we have
E(si,ai)∼ρi(s)πDi (a|s) ∣∣∣Q̂(si, ai)−QπN (si, ai)∣∣∣ ≤
rmax
1− γ
√ 1
2N log
2 δ + ( rmax (1− γ)2 + 2LAdiamA 1− γ )(√ 2 N log 2 δ + γL−i ) + 1 1− γ ( i,L Q̂ + 2LAW i,L 1 ) .
Moreover, if i ≤ L− log log γ and the constants are normalized as LA = c/(1−γ), i,L Q̂ = ξi,L Q̂ /(1−γ), then, with probability greater than 1− δ, we have
E(si,ai)∼ρi(s)πDi (a|s) ∣∣∣Q̂(si, ai)−QπN (si, ai)∣∣∣
≤Õ ( 1 (1− γ)2 ( (rmax + c · diamA)(1/ √ N + ) + ξi,L Q̂ + c ·W i,L1 ))
Proof. Notice that Theorem 1 is the situation when i = 0 and L = ∞. To push this to i ≥ 0 and L = ∞, recall that Lemma 1 defines the behavior policy πDi , the average state distribution ρi and the state occupancy measure ρ πDi ρi
at step i. Also, since the trajectories in each episode are initialized using the same initial state distribution, we have ρ0 = ρ0. Therefore, the objective of Theorem 1 is actually E(s0,a0)∼ρ0(s)πD0 (a|s) ∣∣∣Q̂(s0, a0)−QπN (s0, a0)∣∣∣. This is generalized to i ≥ 0 using substitutions: (ρ0, π D 0 , Ẽ ∞ 0 )→ (ρi, πDi , Ẽ∞i ), yielding
E(si,ai)∼ρi(s)πDi (a|s) ∣∣∣Q̂(si, ai)−QπN (si, ai)∣∣∣
≤ r max
1− γ
√ 1
2N log
2 δ + ( rmax (1− γ)2 + 2LAdiamA 1− γ )√ 2 N log 2 δ + 1 1− γ ( i,∞ Q̂ + 2LAW i,∞ 1 ) .
Finally, observe that for any bounded f :
Ẽ∞i f ≤ ẼLi f + γL−i‖f‖∞
We arrive at
E(si,ai)∼ρi(s)πDi (a|s) ∣∣∣Q̂(si, ai)−QπN (si, ai)∣∣∣
≤ r max
1− γ
√ 1
2N log
2 δ + ( rmax (1− γ)2 + 2LAdiamA 1− γ )(√ 2 N log 2 δ + γL−i ) + 1 1− γ ( i,L Q̂ + 2LAW i,L 1 ) .
As for the second conclusion, with the substitutions in the statement, we know γL−i ≤ . Hence,
E(si,ai)∼ρi(s)πDi (a|s) ∣∣∣Q̂(si, ai)−QπN (si, ai)∣∣∣
≤ r max
1− γ
√ 1
2N log
2 δ + ( rmax (1− γ)2 + 2c · diamA (1− γ)2 )(√ 2 N log 2 δ + ) + 1 (1− γ)2 ( ξi,L Q̂ + 2c ·W i,L1 )
=Õ ( 1 (1− γ)2 ( (rmax + c · diamA)(1/ √ N + ) + ξi,L Q̂ + c ·W i,L1 ))
A.5 POLICY EVALUATION ERROR UNDER NON-UNIFORM WEIGHTS
Lemma 6. Following from Lemma 1, let w = {we > 0}Ne=1 be the (unnormalized) weights for the episodes. We have for the weighted case, 1∑
e we
∑ e weρ πe ρei (s) = ρ πDi,w ρi,w (s) a.e., where
ρ πDi,w ρi,w (s) is the normalized state occupancy measure is generated by (ρi,w, π D i,w, T ). Also, 1∑ e we ∑ e weρ πe ρei (s)πe(a|s) = ρπ D i,w ρi,w (s)πDi,w(a|s) a.e.
Proof. The proof is basically a generalization of Lemma 1. Since ρπ e
ρei is the normalized occupancy
measure generated by (ρei , π e, T ), we know each ρπ
e
ρei is the fixed-point of the Bellman flow equation:
ρπ e
ρei (s) = (1− γ)ρei (s) + γ
∫ T (s|s′, a′)πe(a′|s′)ρπ e
ρei (s′)ds′da′, ∀ e ∈ [1, ..., N ].
Taking a weighted average, we get 1∑ e we ∑ e weρ πe ρei (s)
= 1∑ e we ∑ e we [ (1− γ)ρei (s) + γ ∫ T (s|s′, a′)πe(a′|s′)ρπ e ρei (s′)ds′da′ ] =(1− γ)ρi,w(s) + γ ∫ T (s|s′, a′) 1∑
e we ∑ e we [ πe(a′|s′)ρπ e ρei (s′) ] ds′da′
=(1− γ)ρi,w(s) + γ ∫ T (s|s′, a′) ∑ e weπ e(a′|s′)ρπeρei (s ′)∑
e weρ πe ρei (s′)
∑ e weρ πe
ρei (s′)∑
e we ds′da′
=(1− γ)ρi,w(s) + γ ∫ T (s|s′, a′)πDi,w(a′|s′)
1∑ e we ∑ e weρ πe ρei (s′)ds′da′,
where πDi (a|s) , ∑ e weπ e(a|s)ρπ e ρe i (s)∑
e weρ πe
ρe i (s)
is the weighted behavior policy at step i. Since the Bell-
man flow operator is a γ-contraction in TV distance and hence has a unique (up to difference in some measure zero set) fixed point, denoted as ρ πDi,w ρi,w (s), we arrive at 1∑ e we ∑ e weρ πe ρei (s) = ρ πDi,w ρi,w (s) a.e. Finally, by definition of πDi,w(a|s), we conclude that 1∑ e we ∑ e weρ πe ρei (s)πe(a|s) = ρ πDi,w ρi,w (s)πDi,w(a|s) a.e.
Theorem 2. Let w = {we > 0}Ne=1 be the (unnormalized) weights for the episodes. Let Ẽ∞0,w be the operator defined as Ẽ∞0,wf = 1∑ e we ∑N e=1 ∑∞ i=0(1 − γ)γiwef(sei , aei ). Fix assumptions (1) (2) (3) of Theorem 1. Rewrite the policy mismatch error and the Bellman error as W 0,∞1,w = Ẽ ∞ 0,wW1(π N ||πD0,w)(·) and 0,∞ Q̂,w = Ẽ∞0,w|Q̂(·, ·) − (Bπ N
Q̂)(·, ·)|, respectively, where W1(π N ||πD0,w)(s) = W1(πN (·|s)||πD0,w(·|s)). With probability greater than 1− δ, we have
E(s0,a0)∼ρ0(s)πD0,w(a|s) ∣∣∣Q̂(s0, a0)−QπN (s0, a0)∣∣∣ ≤ rmax
1− γ
√ ∑ e w 2 e
2( ∑ e we) 2 log 2 δ
+ ( rmax
(1− γ)2 + 2LAdiamA 1− γ )√ 2∑e w2e ( ∑ e we) 2 log 2 δ + 1 1− γ ( 0,∞ Q̂,w + 2LAW 0,∞ 1,w ) .
Proof. The proof basically follows from Theorem 1. Decompose the objective using Lemma 3, 4 as: E(s0,a0)∼ρ0(s)πD0,w(a|s) ∣∣∣Q̂(s0, a0)−QπN (s0, a0)∣∣∣
=H1 + E(s0,a0)∼ρ̂0,w(s)πD0,w(a|s) ∣∣∣Q̂(s0, a0)−QπN (s0, a0)∣∣∣
≤H1 + E(s,a)∼ρ̂0,w(s)πD0,w(a|s) ∣∣∣Q̂(s0, a0)−QπD0,w(s0, a0)∣∣∣+ ∣∣∣QπD0,w(s0, a0)−QπN (s0, a0)∣∣∣
4, 3 ≤ H1 + 1
1− γ E (s,a)∼ρ
πD0,w ρ̂0,w (s)πD0,w(a|s) [∣∣∣Q̂(s, a)− (BπN Q̂)(s, a)∣∣∣+ 2LAW1(πN (·|s)||πD0,w(·|s))] =H1 +
H2 1− γ + 1 1− γ Ẽ∞0,w [∣∣∣Q̂(·, ·)− (BπN Q̂)(·, ·)∣∣∣+ 2LAW1(πN ||πD0,w)(·)] Assump. ≤ H1 +
H2 1− γ + 1 1− γ ( 0,∞ Q̂,w + 2LAW 0,∞ 1,w ) ,
(16) where ρ̂0,w(s) = ∑ e weδ(s−s e 0)∑
e we is the weighted empirical initial state distribution. Because
|Q̂(s, a) − QπN (s, a)| ∈ [0, r max 1−γ ], we know Ea∼πD0,w(·|s)|Q̂(s, a) − Q πN (s, a)| ∈ [0, r max 1−γ ], too.
By Hoeffding’s inequality, with probability greater than 1− δ,
H1 = ( Es0∼ρ0 − Es0∼ρ̂0,w ) Ea0∼πD0,w(·|s0) ∣∣Q̂(s0, a0)−QπN (s0, a0)∣∣ ≤ 1∑
e we
√√√√∑e (we rmax1−γ )2 2 log 1 δ = rmax 1− γ √ ∑ e w 2 e 2( ∑ e we) 2 log 1 δ .
(17)
Also, let f(s, a) = ∣∣Q̂(s, a) − (BπN Q̂)(s, a)∣∣ + 2LAW1(πN (·|s)||πD0,w(·|s)). Then f(s, a) is bounded in [0, r max
1−γ + 2LAdiamA]. Using a weighted version of Azuma-Hoeffding in Lemma 5, we have that with probability greater than 1− δ, H2 = ( E (s,a)∼ρ
πD0,w ρ̂0,w (s)πD0,w(a|s) − Ẽ∞0,w
)[∣∣∣Q̂(s, a)− (BπN Q̂)(s, a)∣∣∣+ 2LAW1(πN (·|s)||πD0,w(·|s))]
≤ ( rmax
1− γ + 2LAdiamA )√ 2∑e w2e ( ∑ e we) 2 log 1 δ
(18)
Combining Eq. (16), (17) and (18), a union bound implies with probability greater than 1− 2δ,
E(s0,a0)∼ρ0(s)πD0,w(a|s) ∣∣∣Q̂(s0, a0)−QπN (s0, a0)∣∣∣ ≤ rmax
1− γ
√ ∑ e w 2 e
2( ∑ e we) 2 log 1 δ
+ ( rmax
(1− γ)2 + 2LAdiamA 1− γ )√ 2∑e w2e ( ∑ e we) 2 log 1 δ + 1 1− γ ( 0,∞ Q̂,w + 2LAW 0,∞ 1,w ) Finally, rescaling δ to δ/2 finishes the proof.
Corollary 2. Let ẼLi,w be the operator defined as ẼLi,wf = 1∑ e we ∑ e ∑L−1 j=i (1 − γ)γj−iwef(s e j , a e j). Fix assumptions (1) (2) (3) of Theorem 1. Rewrite the policy mismatch error and the Bellman error as W i,L1,w = Ẽ L i,wW1(π N ||πDi,w)(·) and i,L Q̂,w = ẼLi,w|Q̂(·, ·) − (Bπ N
Q̂)(·, ·)|, respectively, where W1(πN ||πDi,w)(s) = W1(πN (·|s)||πDi,w(·|s)). Let ρi,w(s) be the average weighted state density at trajectory step i. Then, with probability greater than 1− δ, we have E(si,ai)∼ρi,w(s)πDi,w(a|s) ∣∣∣Q̂(si, ai)−QπN (si, ai)∣∣∣ ≤ rmax
1− γ
√ ∑ e w 2 e
2( ∑ e we) 2 log 2 δ
+ ( rmax
(1− γ)2 + 2LAdiamA 1− γ )(√ 2∑e w2e ( ∑ e we) 2 log 2 δ + γL−i ) + 1 1− γ ( i,L Q̂,w + 2LAW i,L 1,w ) .
Moreover, if i ≤ L− log log γ and the constants are normalized as LA = c/(1−γ), i,L Q̂,w = ξi,L Q̂,w /(1− γ), then, with probability greater than 1− δ, we have
E(si,ai)∼ρi,w(s)πDi,w(a|s) ∣∣∣Q̂(si, ai)−QπN (si, ai)∣∣∣
≤Õ ( 1 (1− γ)2 ( (rmax + c · diamA) (√ ( ∑ e w2e)/( ∑ e we)2 + ) + ξi,L Q̂,w + c ·W i,L1,w ))
Proof. Observe that for any bounded f :
Ẽ∞i,wf ≤ ẼLi,wf + γL−i‖f‖∞
Thus, we can start from Theorem 2 and prove with the same argument in Corollary 1.
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 wt:
wt ∝ 1 1− ηL0/K ( 1 max(t, cmin, N0ηL0) − 1 N0 ) + 1(t ≤ cmin)K cmin max ( 1− ln cmin/N0 L0 ln η , 0 ) ,
where t is the age of a data point relative to the newest time step; i.e., w0 is the newest sample. N0 is the size of the experience replay. L0 = 1000 is the maximum horizon of the environment. K is the length of the recent trajectory. η ≈ 0.996 is the decay parameter. cmin ≈ 5000 is the minimum coverage of the sampling. Moreover, the ERE strategy can be approximated (by Taylor Approximation) as
wt ∝ 1 max(t, cmin, N0ηL0) − 1 N0 + 1(t ≤ cmin) cmin max
( ln
cmin N0ηL0
, 0 )
Proof. Recall that Wang & Ross (2019) assume a situation of doing K updates in each episode. In the kth update, the data is sampled uniformly from the most recent ck = max(N0ηk L0 K , cmin) points.
To compute the aggregrated weight wt over these K updates, observe that a data point of age t is in the most recent ck points if ck ≥ t and that the weight in each uniform sample is 1/ck. Therefore, wt should be proportional to
wt ∝ ∑
k: 1≤k≤K, ck≥t
1
ck . (19)
Because ck is designed to be lower bounded by cmin, we shall discuss Eq. (19) by cases.
(1) When t > cmin, we know ck > cmin because ck ≥ t is a constraint in the sum. This means ck = N0η
kL0/K and hence ck ≥ t is equivalent to k ≤ ln tN0 / ln η L0/K . Eq. (19) becomes
∑ k: 1≤k≤K,
ck≥t
1
ck =
min(K, ln tN0 / ln ηL0/K)∑
k=1
1
N0 η−L0k/K
(∗) =
min(K, ln tN0 / ln ξ)∑
k=1
1
N0 ξ−k
=  ξ −1 N0 1−ξ − logξ t N0 1−ξ−1 = 1/t−1/N0 1−ηL0/K if K > ln t N0 / ln ηL0/K ξ−1
N0
1−ξ−K 1−ξ−1 = η−L0/N0−1/N0 1−ηL0/K if K ≤ ln t N0 / ln ηL0/K
=
{ 1/t−1/N0 1−ηL0/K if t > N0η L0
1/(N0η L0 )−1/N0
1−ηL0/K if t ≤ N0η L0
= 1 1− ηL0/K ( 1 max(t, N0ηL0) − 1 N0 ) where (*) is a substitution: ξ = ηL0/K .
(2) When t ≤ cmin, we know ck ≥ t for all k because ck ≥ cmin by definition. Eq. (19) becomes ∑
k: 1≤k≤K, ck≥t
1
ck = K∑ k=1 1 ck
(∗) =
min(K, ln cmin N0 / ln ξ)∑ k=1 1 N0 ξ−k + max(K − ln cmin N0 / ln ξ, 0) 1 cmin
(∗∗) =
1 1− ηL0/K ( 1 max(cmin, N0ηL0) − 1 N0 ) + max(K −K ln cmin/N0 L0 ln η , 0) 1 cmin
= 1 1− ηL0/K ( 1 max(cmin, N0ηL0) − 1 N0 ) + K cmin max ( 1− ln cmin/N0 L0 ln η , 0 ) ,
where (*) does a substitution: ξ = ηL0/K and split the sum. (**) reuses the analysis in case (1).
Combining cases (1) and (2), we arrive at the first conclusion. As for the approximation, since η ≈ 0.996, let η = 1− κ. We have
1− ηL0/K = 1− (1− κ)L0/K ≈ 1− 1 + κL0/K = κ L0 K ≈ −L0 K ln(1− κ) = −L0 K ln η
Thus the first term in the conclusion of Prop. 1 is proportional to K. The second term is also proportional to K. Since wt is only made to be proportional to the RHS and both terms on the RHS become proportional to K, we can remove K on the RHS:
wt ∝ 1
−L0 ln η ( 1 max(t, cmin, N0ηL0) − 1 N0 ) + 1(t ≤ cmin) cmin max ( 1− ln cmin/N0 L0 ln η , 0 )
Finally, because 0 < η < 1, −L0 ln η is a positive number, the above expression can be further simplified by timing −L0 ln η on the RHS, yielding the result. Proposition 2. Let {wt > 0}Nt=1 be the weights of the data indexed by t. Then the Hoeffding error√∑N t=1 w 2 t / ∑N t=1 wt is minimized when the weights are equal: wt = c > 0, ∀ t.
Proof. Let w = [w1, ..., wN ]> be the weight vector and f(w) = √ w>w/(1>w) be the Hoeffding error. Observe that f(w) is of the form:
f(w) = ‖w‖/(1>w) = ‖w/(1>w)‖,
where ‖w‖ = √ w>w is the 2-norm of w. Thereby, let z = w/(1>w) be the normalized vector. That f(w) is minimized is equivalent to that g(z) = ‖z‖ is minimized for 1>z = 1. By the lagrange multiplier, this happens when
∇g = z ‖z‖ = λ1, for some λ ∈ R.
This can be achieved by zt = c for some c > 0. Therefore, we know f is minimized when
zt = wt 1>w = c for some c.
Since 1>w does not depend on t, we conclude that the minimizer happens at wt = c > 0, ∀t.

Review summaries:
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.  

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.  

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.