Year: 2018

Abstract:
Importance sampling is a common approach to off-policy learning in reinforcement learning. While it is consistent and unbiased, it can result in high variance updates to the parameters for the value function. Weighted importance sampling (WIS) has been explored to reduce variance for off-policy policy evaluation, but only for linear value function approximation. In this work, we explore a resampling strategy to reduce variance, rather than a reweighting strategy. We propose Importance Resampling (IR) for off-policy learning, that resamples experience from the replay buffer and applies a standard on-policy update. The approach avoids using importance sampling ratios directly in the update, instead correcting the distribution over transitions before the update. We characterize the bias and consistency of the our estimator, particularly compared to WIS. We then demonstrate in several toy domains that IR has improved sample efficiency and parameter sensitivity, as compared to several baseline WIS estimators and to IS. We conclude with a demonstration showing IR improves over IS for learning a value function from images in a racing car simulator.

heading: 1 INTRODUCTION
text: An important component of many learning systems is learning value functions for many policies. Some examples of such systems are the Horde architecture composed of General Value Functions (GVFs) (Sutton et al., 2011; Modayil et al., 2014), systems that use options (Sutton et al., 1999; Schaul et al., 2015a), predictive representation approaches (Sutton et al., 2005; Schaul and Ring, 2013; Silver et al., 2017) and systems with auxiliary tasks (Jaderberg et al., 2017). For each target policy, the value function returns the expected return from a state, and can provide useful information about (long-term) outcomes under different behaviors. Off-policy learning is critical for learning many value functions with different policies at scale, because it enables data to be generated from one behavior policy to update the values for each target policy in parallel.
The typical strategy for off-policy learning is to use importance sampling (IS). For a given state s, with action a selected according to behaviour µ, the importance sampling ratio is the ratio between the probability of the action under the target policy π and the behaviour: π(a|s)µ(a|s) . The update is multiplied by this ratio, adjusting the action probabilities so that the expectation of the update is as if the actions were sampled according to the target policy π. Though the IS estimator is unbiased and consistent (Kahn and Marshall, 1953; Rubinstein and Kroese, 2016), it can suffer from high or even infinite variance due to large magnitude IS ratios, in theory (Andradottir et al., 1995) and in practice (Precup et al., 2001; Mahmood et al., 2014; 2017).
There have been some attempts to modify policy evaluation algorithms to mitigate this variance.1 Weighted IS (WIS) algorithms have been introduced (Precup et al., 2001; Mahmood et al., 2014; Mahmood and Sutton, 2015), which normalize each update by the sample average of the ratios. These algorithms did improve learning over standard IS strategies, but are not straightforward to extend to nonlinear function approximation. In the offline setting, a reweighting scheme, called importance sampling with unequal support (Thomas and Brunskill, 2017), was introduced to account
1There is substantial literature on variance reduction for another area called off-policy policy evaluation, but which estimates only a single number or value for a policy (e.g., see (Thomas and Brunskill, 2016)). The resulting algorithms differ substantially, and are not easily applicable for learning the value function.
for samples where the ratio is zero, in some cases significantly reducing variance. Another strategy has been to use rescaling or truncation of IS ratios, such as in V-trace (Espeholt et al., 2018). Several other methods have introduced bias similarly for algorithms with eligibility traces by truncating or scaling IS ratios to maintain stability of the eligibility trace vector, including Tree-Backup (Precup et al., 2000), Retrace (Munos et al., 2016) and ABQ (Mahmood et al., 2017). Truncation of IS-ratios in V-trace can incur significant bias, and this additional truncation parameter does need to be tuned.
An alternative to reweighting updates is to instead correct the distribution before updating the estimator using weighted bootstrap sampling: resampling a new set of data from the previously generated samples (Smith et al., 1992; Arulampalam et al., 2002). Consider a setting where a buffer of data is stored, generated by a behavior policy. Samples for policy π can be obtained by resampling from this buffer, proportionally to π(a|s)µ(a|s) for state-action pairs (s, a) in the buffer. In the sampling literature, this strategy has been proposed under the name Sampling Importance Resampling (SIR) (Rubin, 1988; Smith et al., 1992; Gordon et al., 1993), and has been particularly successful for Sequential Monte Carlo sampling (Gordon et al., 1993; Skare et al., 2003). Such resampling strategies have also been popular in classification, with over-sampling or under-sampling typically being preferred to weighted (cost-sensitive) updates (Lopez et al., 2013).
Such a resampling strategy, however, has yet to be proposed for policy evaluation, though there are several potential benefits. By correcting the distribution before updating, standard on-policy updates can be used, without needing to modify or re-derive with IS ratios. This simplifies application of different optimizers, such as those with momentum terms. Another benefit is that the magnitude of the updates will vary less—because updates are not multiplied by very small or very large importance sampling ratios—potentially reducing variance of stochastic updates and simplifying stepsize selection. Resampling should have larger benefits for learning approaches, as compared to averaging or numerical integration problems, because updates accumulate in the weight vector and change the optimization trajectory of the weights. For example, very large importance sampling ratios could destabilize the weights. Such a problem does not occur for resampling, as instead the same transition will simply be resampled multiple times, spreading out the large magnitude update across multiple updates. On the other extreme, with small ratios, IS will waste updates on transitions with very small IS ratios. Resampling, therefore, should have better sample efficiency. Two important questions, therefore, are if these hypothesized advantages manifest in practice in off-policy learning, and how SIR can be extended for use in policy evaluation.
In this work, we investigate the use of SIR for online off-policy policy evaluation. We first introduce Importance Resampling (IR), which uses an SIR strategy to sample transitions from a buffer of (recent) transitions. These sampled transitions are then used for on-policy updates. We show that IR, with a sliding-window buffer, is a consistent estimator of the one-step on-policy updates, with the same bias as WIS. We then empirically investigate IR on three toy domains and a racing car simulation learning from images. We find that IR is more sample efficient—learning more quickly in terms of number of updates—and has reduced sensitivity in terms of learning rate parameters, for both fixed parameters and within the RMSProp optimizer.

heading: 2 BACKGROUND
text: We consider the problem of learning General Value Functions (GVFs) (Sutton et al., 2011). The agent interacts in an environment defined by a set of states S, a set of actions A and Markov transition dynamics, with probability P(s′|s, a) of transitions to state s′ when taking action a in state s. A GVF is defined for policy π : S×A→ [0, 1], cumulant c : S×A×S→R and continuation function γ : S×A×S → [0, 1], with ct+1 def = c(St, At, St+1) and γt+1 def = γ(St, At, St+1), with values
V (s) def = Eπ [ct+1 + γt+1ct+2 + γt+1γt+2ct+3 + . . . |St = s] = Eπ [ ∞∑ i=1 ( i−1∏ j=0 γt+j ) ct+i|St = s ] .
The operator Eπ indicates the actions are selected according to policy π for the expectation. GVFs encompass standard definitions of value functions, where the cumulant is a reward and the continuation function is a constant. Otherwise, they specify a broader set of value functions, that enable predictions about discounted sums of others signals into the future, when following a target policy π. These values are typically estimated using parametric function approximation, with parameters θ ∈ Rd defining approximate values Vθ(s).
In off-policy learning, transitions are sampled according to behaviour policy, rather than the target policy. To get an unbiased sample of an update to the parameters, the action probabilities need to be adjusted. Consider on-policy temporal difference (TD) learning, with update αtδt∇θVθ(s) for a given St = s, for stepsize αt ∈ R+ and TD-error δt def = Ct+1 +γt+1Vθ(St+1)−Vθ(s). If actions are instead sampled according to a behaviour policy µ : S × A → [0, 1], then we can use importance sampling (IS) to modify the update, giving the off-policy TD update αtρtδt∇θVθ(s) for IS ratio ρt
def = π(At|St)µ(At|St) . Given state St = s, if µ(a|s) > 0 when π(a|s) > 0, then the expected value of these
two updates are equal. To see why, notice that
Eµ [αtρtδt∇θVθ(s)|St = s] = αt∇θVθ(s)Eµ [ρtδt|St = s]
and we have Eµ [ρtδt|St = s] = ∑ a∈A µ(a|s)E [ρtδt|St = s,At = a] = ∑ a∈A µ(a|s)π(a|s) µ(a|s) E [δt|St = s,At = a]
= ∑ a∈A π(a|s)E [δt|St = s,At = a] = Eπ [δt|St = s] .
Other on-policy updates can also be modified with IS ratios to adjust these action probabilities.
Though unbiased, IS can be high-variance, and so weighted IS ratios are typically preferred. For a batch consisting of transitions {(si, ai, si+1, ci+1, ρi)}ni=1, batch WIS uses a normalized estimate for the update. For example, an offline batch WIS TD algorithm would use update αt
ρtδt∇θVθ(s)∑n i=1 ρi
. When learning online, an efficient WIS update is less straightforward, and has resulted in algorithms specialized to the tabular setting (Precup et al., 2001) or linear functions (Mahmood et al., 2014; Mahmood and Sutton, 2015). We nonetheless use WIS as baseline, in the experiments and theory.

heading: 3 RESAMPLING STRATEGIES FOR OFF-POLICY POLICY EVALUATION
text: In this section, we introduce resampling, as an alternative to importance sampling for off-policy learning. We first introduce the algorithm, Importance Resampling (IR). We then prove consistency and characterize the bias. We conclude with a discussion about its variance properties.
Importance Resampling requires access to a buffer of samples, from which we can resample. Replaying experience from a buffer was introduced as a biologically plausible mechanism to reuse old experience (Lin, 1992; 1993), and has since become common for improving sample efficiency, particularly for control (Mnih et al., 2015; Schaul et al., 2015b). In the simplest case—which we assume here—the buffer is a sliding window of the most recent n samples, {(si, ai, si+1, ci+1, ρi)}ti=t−n, at time step t > n. These samples are generated by taking actions according to behaviour µ, and so the tuples are generated with probability dµ(s)µ(a|s)P(s′|s, a), where dµ : S → [0, 1] is the stationary distribution for policy µ. The goal is to obtain samples instead according to dµ(s)π(a|s)P(s′|s, a), as if we had taken actions according to policy π from state s ∼ dµ. This assumption—that states are still sampled from dµ—underlies most off-policy learning algorithms; very few attempt to use IS to adjust probabilities dµ to dπ (Precup et al., 2001).
The IR algorithm is simple: resample a mini-batch of size k on each step t from the buffer of size n, proportionally to ρi in the buffer. Standard on-policy updates, such as on-policy TD or on-policy gradient TD, are then used on this resample. The key difference to IS and WIS is that the sampling distribution itself is corrected (see Theorem C.1), before the update, whereas IS and WIS correct the update itself. This small difference, however, can have larger ramifications practically, particularly with updates that accumulate in the parameters.
We consider two variants of IR: with and without bias correction. For point tj sampled from the buffer, let ∆tj be the on-policy update for that transition. For example, for TD, ∆tj = δtj∇θVθ(stj ). The first step for either variant is to sample a mini-batch of size k from the buffer, proportionally to ρi, as described above. The standard IR update simply uses a mini-batch, whereas Bias-Corrected IR (BC-IR) pre-multiplies with the average ratio in the buffer ρ̄t = 1n ∑n i=1 ρi,
IR: αt 1k k∑ j=1 ∆tj BC-IR: αtρ̄t 1k k∑ j=1 ∆tj .
BC-IR negates bias introduced by the average ratio in the buffer deviating significantly from the true mean. For reasonably large buffers, ρ̄t will be close to 1 making IR and BC-IR have nearidentical updates. In practice, we find the two variants of IR perform similarly. Nonetheless, they do have different theoretical properties, particularly for small buffer sizes n, so we characterize both. Though BC-IR has better bias properties, IR is simpler—not requiring any modification to the updates—which may be more important than the small amount of bias introduced by the IR without bias correction. For this reason, we advocate for and analyze both variants.
Across all results, we make the following assumption. Assumption 1. Transition tuples Xi = (Si, Ai, Si+1) are sampled i.i.d. according to the distribution p(x = (s, a, s′)) = dµ(s)µ(a|s)P(s′|s, a), for i = 1, 2, 3, . . ..
To distinguish expectations under p(x) = dµ(s)µ(a|s)P(s′|s, a) and q(x) = dµ(s)π(a|s)P(s′|s, a), we overload the notation from above, using operators Eµ and Eπ respectively. To reduce clutter, we will typically write E to mean Eµ, because most expectations are under the sampling distribution.

heading: 3.1 BIAS OF IR
text: We first show that IR is biased, and that its bias is actually equal to batch WIS (in Theorem 3.1). This bias is small for reasonably large n, because it is proportional to 1/n. In terms of mean-squared error, composed of squared bias and variance, this term is 1/n2 and is relatively negligible compared to the variance. Nonetheless, for smaller buffers, such bias could have an impact. We show that with a simple modification, in BC-IR, we obtain an unbiased estimate of the update (Corollary 3.1.1). Theorem 3.1. [Bias for a fixed buffer of size n] Assume a buffer B of n transitions is sampled i.i.d., according to dµ(s)µ(a|s)P(s′|s, a). Let XIR def = 1k ∑k j=1 ∆ij for transitions i1, . . . , ik sampled
randomly from the buffer proportionally to ρi. Let XWIS∗ def = ∑n i=1 ρi∑n j=1 ρj ∆i be the batch WIS estimator of the update, with ρi def = π(Ai|Si)/µ(Ai|Si). Then, E[XIR] = E[XWIS∗], and so the bias of XIR is proportional to
Bias(XIR) = E[XIR]− Eπ[∆] ∝ 1
n (Eπ[∆]σ2ρ − σρ,∆σρσ∆)
where Eπ[∆] is the expected update across all transitions, with actions from S taken by the target policy π; σ2ρ = Var( 1 n ∑n j=1 ρj); σ 2 ∆ = Var( 1 n ∑n i=1 ρi∆i); and covariance σ(ρ,∆) =
Cov( 1n ∑n j=1 ρj , 1 n ∑n i=1 ρi∆i).
Proof. Notice first that when we weight with ρi, this is equivalent to weighting with dµ(Si)π(Ai|Si)P(Si+1|Si,Ai) dµ(Si)µ(Ai|Si)P(Si+1|Si,Ai) , and so we are applying the correct IS ratio for the transition.
E[XIR] = E [E[XIR|B]] = E [ E [ 1 k k∑ j=1 ∆ij |B ]] = E [ 1 k k∑ j=1 E[∆ij |B] ]
= E [ n∑ i=1 ρi∑n j=1 ρj ∆i ] = E[XWIS∗] . because E[∆ij |B] = n∑ i=1 ρi∑n j=1 ρj ∆i
This bias ofXIR is therefore the same as batch WIS, which is characterized in (Owen, 2013, Section 2.7), completing the proof.
This bias of IR will be small for reasonably large n, both because it is proportional to 1/n and because larger n will result in lower variance of the average ratios and average update for the buffer. In particular, as n grows, these variances decay proportionally to n.
Corollary 3.1.1. Bias-corrected IR, with estimator XBC def = ρ̄k ∑k j=1 ∆ij for ρ̄ = 1 n ∑n j=1 ρj , is unbiased: E[XBC] = Eπ[∆].

heading: Proof.
text: E[XBC] = E [ ρ̄ k k∑ j=1 E[∆ij |B] ] = E [ ρ̄ n∑ i=1 ρi∑n j=1 ρj ∆i ] = E [ 1 n n∑ i=1 ρi∆i ] = 1n n∑ i=1 E [π(Ai|Si) µ(Ai|Si) ∆i ] = 1n
n∑ i=1 E [dµ(Si)π(Ai|Si)P(Si+1|Si, Ai) dµ(Si)µ(Ai|Si)P(Si+1|Si, Ai) ∆i ] = 1n n∑ i=1 Eπ [∆] = Eπ [∆] .

heading: 3.2 CONSISTENCY OF IR
text: Consistency of IR in terms of an increasing buffer, with n → ∞, is a relatively straightforward extension on results for SIR, with or without bias correction (see Theorem C.1 in Appendix C). More interesting is consistency in terms of increasing interactions with the environment, t → ∞, with a fixed length buffer, as will be the case in practice. IR, without bias correction, is asymptotically biased in this case; in fact, its asymptotic bias is the one characterized above for a fixed length buffer in Theorem 3.1. This asymptotic bias, though, is proportional to 1/n, which is negligible for typical buffer sizes. BC-IR, on the other hand, is consistent, even with a sliding window, as we show in the following theorem.
Theorem 3.2. Let Bi = {Xi−n+1, ..., Xi} be the buffer of the most recent n transitions sampled by time i, i.i.d. as specified in Assumption 1. Let X(i)BC be the bias-corrected IR estimator, with k samples from buffer Bi. Define the sliding-window estimator Xt def = 1t ∑t i=1X (i) BC. Assume there exists a c > 0 such that Var(X(i)BC) ≤ c ∀i. Then, as t→∞, Xt converges in probability to Eπ[∆].
Proof. Notice first that X(i)BC is random because Bi is random and because transitions are sampled fromBi. Therefore, givenBi,X (i) BC is independent of other random variablesBj andX (j) BC for j 6= i.
Now, using Corollary 3.1.1, we can show that BC-IR is unbiased for a sliding window
E[Xt] = E [1 t t∑ i=1 X (i) BC ] = 1 t t∑ i=1 E[E[X(i)BC|Bi]] = Eπ [∆] .
Next, we show that lim|i−j|→∞ Cov(X (i) BC, X (j) BC) = 0. For |i − j| ≥ m, Bi and Bj are independent, because they are disjoint sets of i.i.d. random variables. Correspondingly, X(i)BC is independent of X(j)BC. Explicitly, using the law of total covariance, we get that Cov(X (i) BC, X (j) BC) = Cov(X (i) BC, X (j) BC|Bi, Bj) + Cov(E[X (i) BC|Bi],E[X (j) BC|Bj ]) = 0. The first term is zero because X (i) BC is independent of X(j)BC given Bi, and the second term is zero because Bi and Bj are independent. Therefore, lim|i−j|→∞ Cov(X (i) BC, X (j) BC) = 0.
Using the assumption on the variance, we can apply Lemma C.3 to Xt to get the desired result.

heading: 3.3 VARIANCE AND EFFECTIVE SAMPLE SIZE
text: In this section, we provide some intuition on the variance properties of the discussed off-policy estimators. Similarly to bias, we can characterize the variance of the IR estimator relative to batch WIS. XWIS∗ is able to use a batch update on all the data in the buffer, which should result in a lowvariance estimate but is an unrealistic algorithm to use in practice. Instead, it provides a benchmark, where the goal is to obtain similar variance toXWIS∗, but within realistic computational restrictions. Because of the clear relationship between IR and WIS, as used in Theorem 3.1, we can easily characterize the variance of XIR relative to XWIS∗ using the law of total covariance:
V(XIR) = V [E[XIR|B]] + E [V[XIR|B]] = V [XWIS∗] + E [V[XIR|B]]
where the variability is due to having randomly sampled buffers B and random sampling from B. The second term corresponds to the noise introduced by sampling a mini-batch of k transitions from the buffer B, instead of using the entire buffer like WIS. For more insight, we can expand this second term, E [V[XIR|B]] = E [ ( 1k ∑k j=1 ∆ij − 1 n ∑n i=1 ∆i) 2|B ] , where we consider the variance independently for each element of ∆i and so apply the square element-wise. The variability is not due to IS ratios, and instead arises from variability in the updates themselves. Therefore, the variance of IR corresponds to the variance of WIS, with some additional variance due to this variability around the average update in the buffer.
This variance contrasts the variance of the corresponding mini-batch IS estimator:
V (
1 k k∑ j=1 ρij∆ij ) = E [( 1 k k∑ j=1 ρij∆ij − Eπ[∆] )2]
For large importance sampling ratios, this mini-batch can deviate significantly around the mean update. Further, this deviation around the mean update is across all transitions, unlike E [V[XIR|B]] which reflects the expected deviation for a buffer of size n. The IS estimator is unbiased, as opposed to IR and WIS which both introduce some bias. A more fair comparison is to BC-IR, which is unbiased, with variance
V ( XBC ) = E [( ρ̄ k k∑ j=1 ∆ij − Eπ[∆] )2]
It is difficult to state generally that the variability of the IS estimator will be greater than XBC, because it depends on the properties of the update vector ∆ij itself. However, the key difference between them is that XBC multiplies all the updates by the averaged ratio, whereas IS includes individual (potentially high magnitude) ratios inside the sum.
Finally, the variance of IR will be affected by what is known as the effective sample size. For data with several high magnitude ratios, and many small ratios, the IS estimator will likely suffer from high-variance updates. IR, however, will not be completely robust to this setting either: it will prevent high magnitude updates, but will be sampling from an effectively smaller dataset. This effective size is smaller because IR will repeatedly sample the same transitions, and potentially never sample some of the transitions with small IS ratios. With less data, we typically incur more variance.
One common estimator of effective sample size is ( ∑n i=1 ρi)
2∑n i=1 ρ 2 i
(Kong et al., 1994; Martino et al., 2017). This estimate lies between 1 and n. When the effective sample size is low, this indicates that most of the probability is concentrated on a few samples, which could be problematic. An important next step is to better understand theoretically the implications of effective sample size. Here, we now turn to experiments to gain more insight into the relative efficacy of IR to IS, in settings including such skewed ratios.

heading: 4 EXPERIMENTS
text: In this section, we present results for predictions made with difficult polices in three domains. We compare IR and BC-IR 2 to an importance sampling approach using uniformly sampled experiences from the replay buffer (ER+IS), and three variants of weighted importance sampling (WIS). The three variants of WIS considered are WIS-Batch, WIS-Buffer, and WIS-Optimal discussed further in the appendix3 4. For tabular domains, we don’t average over the mini-batch updates, although doing so won’t change results significantly. We report parameter studies and learning curves, excluding buffer size studies, on a single buffer size shared between all the methods. Although results from other buffer sizes (not shown here) have similar conclusions. We show 95% confidence intervals on all results unless otherwise specified.

heading: 4.1 SETTINGS
text: Random Walk Markov Chain We use a typically constructed random walk Markov chain (Sutton and Barto, 2018) with 8 non-terminating states and 2 terminating, with a reward of 1 on the transition to the right-most terminal state and 0 everywhere else. The agent follows a policy µ and learns the value function according to a target policy π. We compute the root mean squared value error (RMSVE) on every training step with a value function found using dynamic programming with threshold 10−15.
2While BC-IR is included in the results and used for the simulated car experiments, we found IR and BC-IR to perform almost exactly the same with BC-IR having lower sensitivity to learning rate in some instances.
3Due to computational complexity we only test WIS-Optimal in the markov chain. 4We forgo evaluating any variants of the WIS update in the Torcs race car simulator based on the perfor-
mance in the simpler domains.
Four Rooms Environment The four rooms domain is a well known hard domain used for training options (Stolle and Precup, 2002). The behavior policy followed by the agent is equiprobable everywhere except for 25 randomly selected states which take the action down with probability 0.05 with remaining probability split equally amongst the other actions. The 25 random states are the same for all runs, but we also evaluated different states for each run (see appendix). The target policy of interest is to take the down action deterministically, inducing highly variant IS ratios. The cumulant for the value function is 1 when the agent hits a wall and 0 otherwise. The continuation function is γ = 0.9 terminating when the agent hits a wall. We calculate the RMSVE similarly to the Markov Chain.
Simulated Car Domain We use the TORCs race car simulator to perform scaling experiments using neural networks. We set up the simulator to produce 64x128 cropped grayscale images. We have an underlying deterministic steering controller that produces steering actions adet ∈ [−1,+1] and take an action with probability defined by a Gaussian aN (adet, 0.1). We show a demonstration learning a single GVF with cumulant 1 when the car is near the center of the road (signal provided by Torcs), continuation function with 0.9 everywhere with terminating condition the same as the cumulant, and a target policy modeled as a gaussian N (0.15, 0.0075), which corresponds to steering left.

heading: 4.2 RESULTS
text: In each of the domains tested we see significant improvements in the range of effective learning rates. The most stark example is seen in the right plot of figure 1. Here the behaviour policy induces importance sampling ratios as high as 99 while also having very few effective samples from which to train. After 1000 training epochs only a single learning rate seemed to not diverge using ER+IS and WIS-Buffer. In this same setting, IR performs very similar to the value function trained with on policy data. We also see lower sensitivity to learning rate in the four rooms environment, rightmost figure 2. 5
Another benefit of IR is the gains in sample efficiency, and the focus on potentially rare samples following the target policy. We show this with the learning curves found in figure 3. In the random
5Additional results in the Mountain Car Domain using a three layer neural network can be found in the appendix.

heading: ER+ISIR OnPolicyWIS-Batch WIS-OptimalWIS-BufferBC-IR
text: walk and four rooms domains we see WIS-Buffer and WIS-Batch perform approximately the same as ER+IS with IR outperforming the competitors. This can be attributed to IR’s resampling scheme, where we see more samples important to training. This is especially apparent in the four rooms experiments, where we may only get a few chances to train from certain hard to reach states. The uniform sampling methods will more likely miss out on rare examples, or only see them once making learning slow. We also note that WIS-Batch is unable to learn in the hardest of settings for the Markov chain, potentially due to the bias incurred from only performing WIS on a subsample of the entire data. One interesting observation is in the Baird’s Star Problem where IR results in better weights and lower value error (see appendix).
The experiments in the Torcs domain show faster learning using a deep learning system. While the results are promising, they are not as stark as we would have expected given the prior experiments and the variance in final performance is much larger for BC-IR and IR. There are several contributing factors to learning off-policy using IR and IS that need to be considered. First by using RMSProp or other adaptive learning rate algorithms we are potentially gaining WIS like benefits, reducing the variance of the updates considerably. IR may improve performance when the behaviour and target policies cause even more variant importance ratios, but with an adaptive learning rate algorithm this becomes less problematic when using IS. More needs to be understood about the interactions between adaptive algorithms and off-policy learning with importance sampling ratios.

heading: 5 CONCLUSIONS
text: Resampling for off-policy learning has been unconsidered, to our knowledge, up until now. This may be due to a focus on learning from only the most recent experiences and throwing away transitions once used. The resampling approach is now viable because of the increased prominence of the experience replay buffer in deep reinforcement learning. Previous approaches have exploited the experience replay buffer for orthogonal purposes including Prioritized Experience Replay (Schaul et al., 2015b), which prioritizes training examples according to the temporal difference error wi = |δi| + . A possible extension to IR is to sample from an intermediate sampling distribution which eases high variant importance sampling ratios (see Appendix B.5).
In this paper we introduced a new approach to off-policy learning: resampling. We explored the theoretical implications of importance resampling, including a correction term to guarantee consistency in the moving window setting. We provided a number of empirical studies in hard off-policy learning settings outperforming the realistic competitors often by a wide margin, while also being less sensitive to learning rate in the mini-batch stochastic gradient update. We found IR to outperform IS in cases with potentially high importance sampling ratios suggesting a possible reduction in variance. Finally, we show improvements in learning rate performance for IR and BC-IR methods using deep learning within a challenging racing car simulator environment. There remains a number of both theoretical and empirical questions surrounding the benefits of the resampling approach to off-policy learning worth exploring in future work.

heading: A WEIGHTED IMPORTANCE SAMPLING
text: We consider three weighted importance sampling updates as competitors to IR. N is the size of the experience replay buffer, b is the size of a single batch.
∆θ = ∑b i ρiδi∇θV (si; θ)∑b
j ρj WIS-Batch
∆θ = N ∑b i ρiδi∇θV (si; θ)∑N
j ρj WIS-Buffer
∆θ = ∑N i ρiδi∇θV (si; θ)∑N
j ρj WIS-Optimal

heading: B MORE EXPERIMENTAL RESULTS

heading: B.1 MARKOV CHAIN

heading: ER+ISIR SarsaClip = 1.0 Clip = 0.5*max Clip = 0.9*max
text: We also include results in the random walk markov chain for V-Trace and Sarsa. V-Trace exhibited the same issues as importance sampling, where we can see a clear disadvantage in the harder policies. Also, we can clearly see a bias-variance trade off in V-Trace as the clipping parameter ρ̄ became more aggressive. Sarsa makes clear gains over ER+IS (and IR in the easiest setting), but fails to learn the true value function for the hardest settings.

heading: B.2 BAIRD’S STAR PROBLEM
text: We use a well known variant of the Star Problem (Baird, 1995; Sutton et al., 2009) proposed as a counter example to the convergence of semi-gradient temporal difference learning in the off-policy setting. We train using a batch version of TDC (Sutton et al., 2009). We calculate the RMSVE for each state on every training step.

heading: B.3 FOUR ROOMS DOMAIN
text: We also sampled new random states in which to act unfavorably for every run. We found the behavior used in the experiments presented in the main text to be harder than many of the other policies sampled randomly.

heading: B.4 MOUNTAIN CAR
text: We use the standard mountain car domain described in (Sutton and Barto, 2018). To make the simulations more realistic we collect experience from behavior policy learned through Q-learning (Sutton and Barto, 2018) with a -greedy exploration strategy. We code a GVF to predict whether the agent will hit the back wall within a horizon of γ = 0.9 while following the the persistent policy accelerating forward. We use two exploration parameters = {0.1, 0.5} with maximum importance sampling ratio values at ρmax = {6, 30} respectively. We show comparisons for both a static step size SGD and with the Adam optimizer. These experiments perform as expected, except for one configuration of the behavior policy using the Adam optimizer. It is possible that the Adam optimizer is getting some benefit similar to WIS with the recency averages of updates accounting for the high variance of the update.

heading: B.5 SAMPLING ACCORDING TO INTERMEDIATE POLICIES
text: While intuitively it might seem sampling according to the target policy will produce the best value functions, when making multiple predictions with the same training network it would be more convenient to sample from the experience replay buffer with an intermediate policy. We get the benefits of less variant importance sampling ratios with the ability to use one IR buffer for multiple policies.
To combine the IR and importance sampling with a uniform experience replay we sample from the buffer according to the PMF
p(sampling di) = ρ̄i∑ j ρ̄j , ρ̄i = πsample(at|st) µ(at|st) .
We would then us off-policy temporal difference methods with the effective importance sampling ratio used as ρeffective =
π(at|st) πsample(at|st) . We show initial results for this extension in the markov chain
random walk in figure 10.

heading: C MORE THEORETICAL RESULTS

heading: C.1 CONSISTENCY OF THE IR ESTIMATOR WITH GROWING BUFFER SIZE
text: We show the consistency of the IR estimator with n→∞ for convenience, but our approach closely follows that of (Smith et al., 1992).
Theorem C.1. Let B = {x1, x2, ..., xn} be a buffer of data sampled i.i.d. according to proposal distribution p(x). Let q(x) be some distribution of interest and assume the proposal distribution samples everywhere where q(x) is non-zero. Also, let Y be a discrete random variable taking values xi with probability ∝ q(xi)p(xi) . Then, Y converges in distribution to X ∼ Q as n→∞.
Proof. Let ρi = q(xi) p(xi) . From the probability mass function of Y , we have that:
P[Y ≤ a] = n∑ i=1 P[Y = xi]1{xi ≤ a}
= n−1
∑n i=1 ρi1{xi ≤ a}
n−1 ∑n i=1 ρi
n→∞−−−−→ Eq[ρ(x)1{x ≤ a}] Eq[ρ(x)]
= 1 · ∫ a −∞ q(x) p(x)p(x)dx+ 0 · ∫∞ a q(x) p(x)p(x)dx∫∞
−∞ q(x) p(x)p(x)dx
= ∫ a −∞ q(x)dx
The above shows consistency. If we have a large enough buffer, then the importance resampling will closely approximate sampling from the target distribution Q. In particular, any expectation we want to estimate under Q can also be a well-approximated by using the defined sampling scheme.

heading: C.2 CHANGING BEHAVIOUR POLICIES
text: We consider the importance sampling estimator under conditions of a changing policy. Theorem C.2. Let P be a target distribution with density p and {xi}ni=1 be a dataset where each xi is sampled from Pi independently. Then, the weighted importance sampling estimator µ̂ =∑n i=1 ρi∑n j=1 ρj g(xi) is consistent for Ef [g(X)] where g(.) is a function of interest and ρi = q(xi)pi(xi) .
Proof. First, we rewrite µ̂ = 1 n
∑n i=1 ρig(xi) 1 n ∑n j=1 ρj and let Yi = ρig(xi).
Next, we find the expectations of Yi and ρi.
Epi [Yi] = ∫ q(x)
pi(x) g(x)pi(x)dx
= Eq[g(X)]
Epi [ρi] = ∫ q(x)
pi(x) pi(x)dx
= ∫ q(x)dx
= 1
Finally, since all Yi and all ρi have the same expectation and are independent, we apply the law of large numbers to obtain that
µ̂ = 1 n
∑n i=1 ρig(xi)
1 n ∑n j=1 ρj n→∞−−−−→ Eq[g(X)] (1)
as desired.
Theorem C.2 implies that, even if the behaviour policy is changing over time, as long as we use an importance ratio corresponding to the policy that was used to select an action, we will retain an unbiased estimate of the expected update.

heading: C.3 CONSISTENCY UNDER A SLIDING WINDOW DATASET
text: Lemma C.3. Let Z1, ...Zn be random variables with mean µ. Suppose there exists a c > 0 such that V(Zi) ≤ c ∀i and that lim|i−j|→∞Cov(Xi, Xj) = 0. Then, as N →∞, 1N ∑N i=1 Zi converges in probability to µ. Proof. Let SN = ∑N i=1 Zi.
V(SN ) = N∑ i=1 V(Zi) + 2 N∑ i=1 N∑ j=i+1 Cov(Zi, Zj)
The first term is bounded by cN from our assumption on the variance. Now, to bound the second term.
Fix δ > 0 and choose M such that ∀|i − j| > M , |Cov(Zi, Zj)| < δ (such an M must exist since lim|i−j|→∞ Cov(Xi, Xj) = 0). Assuming that N > M , we can decompose the second term into
N∑ i=1 N∑ j=i+1 Cov(Zi, Zj) = N∑ i=1 i+M∑ j=i+1 Cov(Zi, Zj) + N∑ i=1 N∑ j=i+M+1
Cov(Zi, Zj)∣∣∣∣∣∣ N∑ i=1 N∑ j=i+1 Cov(Zi, Zj) ∣∣∣∣∣∣ ≤ N∑ i=1 i+M∑ j=i+1 |Cov(Zi, Zj)|+ N∑ i=1 N∑ j=i+M+1 |Cov(Zi, Zj)|
By the Cauchy-Schwarz inequality and our variance assumption, |Cov(Zi, Zj)| ≤ c. So, we get∣∣∣∣∣∣ N∑ i=1 N∑ j=i+1 Cov(Zi, Zj) ∣∣∣∣∣∣ ≤ N∑ i=1 i+M∑ j=i+1 c+ N∑ i=1 N∑ j=i+M+1 δ
≤ NMc+N2δ
Altogether, our upper bound is
V ( SN N ) ≤ c N + Mc N + δ
Finally, we apply Chebyshev’s inequality. For a fixed > 0,
P (∣∣∣∣SNN − µ ∣∣∣∣ > ) ≤ 1 2V ( SN N ) ≤ 1 2 ( c N + Mc N + δ
) Since we can choose δ to be arbitrarily small (say δ = 1N ), the right-hand side goes to 0 as N →∞, concluding the proof.

Review summaries:
In this work, the authors studied the technique of importance re-sampling (IR) for off-policy evaluation in RL, which tends to have low-biased (and it's unbiased in the bias-correction version) and low-variance. Different than existing methods such as importance sampling (IS) and weighted importance sampling (WIS) which correct the distribution over policy/transitions by an importance sampling ratio, in IR one stores the offline data in a buffer and re-samples the experience data (in form of state, action, & next-state) for on-policy RL updates. This approach avoids using importance sampling ratios directly, which potentially alleviate the variance issue in TD estimates. The authors further analyze the bias and consistency of IR, discuss about the variance of IR, and demonstrate the effectiveness of IR by comparing it with IS/WIS on several benchmark domains.

This paper introduces the concept of Sampling Importance Resampling (SIR) and give a simple method to adjust the off-policyness in the TD update rule of (general) value function learning, as an alternative of importance sampling. The authors argue that this resampling technique has several advantages over IS, especially on the stability with respect to step-size if we are doing optimization based the reweighted/resampled samples. In experiment section they show the sensitivity to learning rate of IR TD learning is closer to the on-policy TD learning, comparing with using IS or WIS.