Title: IMPORTANCE RESAMPLING FOR OFF-POLICY POLICY EVALUATION Anonymous authors Paper under double-blind review

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.

1. INTRODUCTION:

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. 1Weighted 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 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.

2. BACKGROUND:

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 c t+1 def = c(S t , A t , S t+1 ) and γ t+1 def = γ(S t , A t , S t+1 ), with values V (s) def = E π [c t+1 + γ t+1 c t+2 + γ t+1 γ t+2 c t+3 + . . . |S t = s] = E π ∞ i=1 i-1 j=0 γ t+j c t+i |S t = 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 θ ∈ R d 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 S t = s, for stepsize α t ∈ R + and TD-error δ t def = C t+1 + γ t+1 V θ (S t+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 S t = 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)|S t = s] = α t ∇ θ V θ (s)E µ [ρ t δ t |S t = s]

and we have

E µ [ρ t δ t |S t = s] = a∈A µ(a|s)E [ρ t δ t |S t = s, A t = a] = a∈A µ(a|s) π(a|s) µ(a|s) E [δ t |S t = s, A t = a] = a∈A π(a|s)E [δ t |S t = s, A t = a] = E π [δ t |S t = 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 {(s i , a i , s i+1 , c i+1 , ρ i )} n i=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.

3. RESAMPLING STRATEGIES FOR OFF-POLICY POLICY EVALUATION:

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, {(s i , a i , s i+1 , c i+1 , ρ i )} t i=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 t j sampled from the buffer, let ∆ tj be the on-policy update for that transition. For example, for TD, ∆ tj = δ tj ∇ θ V θ (s tj ). 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 =

1 n n i=1 ρ i , IR: α t 1 k k j=1 ∆ tj BC-IR: α t ρt 1 k 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 X i = (S i , A i , S i+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.

3.1. BIAS OF IR:

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/n 2 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 X IR def = 1 k k j=1 ∆ ij for transitions i 1 , . . . , i k sampled randomly from the buffer proportionally to ρ i . Let X WIS * def = n i=1 ρi n j=1 ρj ∆ i be the batch WIS estimator of the update, with ρ i def = π(A i |S i )/µ(A i |S i ). Then, E[X IR ] = E[X WIS * ],

and so the bias of X IR is proportional to

Bias(X IR ) = E[X IR ] -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( 1 n 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[X:

IR ] = E [E[X IR |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[X WIS * ] because E[∆ ij |B] = n i=1 ρ i n j=1 ρ j ∆ i

This bias of X IR 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

X BC def = ρ k k j=1 ∆ ij for ρ = 1 n n j=1 ρ j , is unbiased: E[X BC ] = E π [∆].

Proof.

BC ] = 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 = 1 n n i=1 E π(A i |S i ) µ(A i |S i ) ∆ i = 1 n n i=1 E d µ (S i )π(A i |S i )P(S i+1 |S i , A i ) d µ (S i )µ(A i |S i )P(S i+1 |S i , A i ) ∆ i = 1 n n i=1 E π [∆] = E π [∆] .

3.2. CONSISTENCY OF IR:

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 B i = {X i-n+1 , ..., X i } 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 B i . Define the sliding-window estimator

X t def = 1 t t i=1 X (i) BC . Assume there exists a c > 0 such that Var(X (i) BC ) ≤ c ∀i. Then, as t → ∞, X t converges in probability to E π [∆]. Proof. Notice first that X (i) BC is random because B i is random and because transitions are sampled from B i . Therefore, given B i , X (i)

BC is independent of other random variables B j and X (j) BC for j = i. Now, using Corollary 3.1.1, we can show that BC-IR is unbiased for a sliding window

E[X t ] = E 1 t t i=1 X (i) BC = 1 t t i=1 E[E[X (i) BC |B i ]] = E π [∆] . Next, we show that lim |i-j|→∞ Cov(X (i) BC , X (j) BC ) = 0. For |i -j| ≥ m, B i and B j are inde- pendent, because they are disjoint sets of i.i.d. random variables. Correspondingly, X (i) BC is in- dependent 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 |B i , B j ) + Cov(E[X (i) BC |B i ], E[X (j) BC |B j ]) = 0. The first term is zero because X (i) BC is independent of X (j)

BC given B i , and the second term is zero because B i and B j 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 X t to get the desired result.

3.3. VARIANCE AND EFFECTIVE SAMPLE SIZE:

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. X WIS * 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 to X WIS * , 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 X IR relative to X WIS * using the law of total covariance:

V(X IR ) = V [E[X IR |B]] + E [V[X IR |B]] = V [X WIS * ] + E [V[X IR |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[X IR |B]] = E ( 1

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[X IR |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 X BC = 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 X BC , because it depends on the properties of the update vector ∆ ij itself. However, the key difference between them is that X BC 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 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.

( n i=1 ρi) 2 n i=1 ρ 2 i (

4. EXPERIMENTS:

In this section, we present results for predictions made with difficult polices in three domains. We compare IR and BC-IR2 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.

4.1. SETTINGS:

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 . 

Buffer Size Buffer Size:

Figure 2 : left and center Buffer size study for the random walk markov chain and four rooms domain respectively. We select the best settings for each buffersize and report the average RMSVE right Four rooms domain learning rate sensitivities parameter study.

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 a det ∈ [-1, +1] and take an action with probability defined by a Gaussian a N (a det , 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.

4.2. RESULTS:

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 . 5Another 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 .99], optimal learning rates from above parameter study center Four rooms environment n = 10000, b = 32 with optimal settings from below parameter studies. We report 70% confidence bands for ease of comparison. right Torcs racing car simulator learning curves of RMSRE calculated over a pre-collected evaluation set. α BC-IR = 1e -4 , α IR = 1e -4 , α IS = 1e -6 selected from a parameter study using RMSProp and the NVIDIA network designed for self-driving cars (Bojarski et al., 2016) 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.

5. CONCLUSIONS:

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) 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. 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. 

B.5 SAMPLING ACCORDING TO INTERMEDIATE POLICIES:

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. 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 .

Learning Rates (10 -2 ) We show the consistency of the IR estimator with n → ∞ for convenience, but our approach closely follows that of (Smith et al., 1992) .

0.1 100 ||⇡ ⇡sample|| 2 2 < l a t e x i t s h a 1 _ b a s e 6 4 = " k / 5 s E V X 3 Z o i r h l 8 G G r P R P L Y 7 v O c = " > A A A C H n i c b V D L S g M x F M 3 4 t r 6 q L t 0 E i + D G M l M U X

M g h Y I G C p R w n h l g a S y h F V 8 f D e u t G z B W a H W G v Q w 6 K b t U I h G c o Z O i 8 l 4 Y a 9 m 1 v d Q d R b 8 f Z o L u U L d H R Z h o j U o j W H E L 1 L I 0 k z D o 9 y 9 q U W 0 Q l S t + 1 R + B / i X B m F T I G C d R + S 3 s a p 6 n o J B L Z m 0 7 8 D P s F M y g 4 O 7 a U p h b y B i / Z p f Q d l S x F G y n G N k b 0 C 2 n d G m i j V s K 6 U j 9 P l G w 1 A 4 d u M 6 U 4 Z X 9 X R u K / 9 X a O S Y H n U K o L E d Q / O u h J J c U N R 1 m R b v C A E f Z c 4 R x I 9 x f K b 9 i h n F 0 i Z Z c C M F v

M g h Y I G C p R w n h l g a S y h F V 8 f D e u t G z B W a H W G v Q w 6 K b t U I h G c o Z O i 8 l 4 Y a 9 m 1 v d Q d R b 8 f Z o L u U L d H R Z h o j U o j W H E L 1 L I 0 k z D o 9 y 9 q U W 0 Q l S t + 1 R + B / i X B m F T I G C d R + S 3 s a p 6 n o J B L Z m 0 7 8 D P s F M y g 4 O 7 a U p h b y B i / Z p f Q d l S x F G y n G N k b 0 C 2 n d G m i j V s K 6 U j 9 P l G w 1 A 4 d u M 6 U 4 Z X 9 X R u K / 9 X a O S Y H n U K o L E d Q / O u h J J c U N R 1 m R b v C A E f Z c 4 R x I 9 x f K b 9 i h n F 0 i Z Z c C M F v

M g h Y I G C p R w n h l g a S y h F V 8 f D e u t G z B W a H W G v Q w 6 K b t U I h G c o Z O i 8 l 4 Y a 9 m 1 v d Q d R b 8 f Z o L u U L d H R Z h o j U o j W H E L 1 L I 0 k z D o 9 y 9 q U W 0 Q l S t + 1 R + B / i X B m F T I G C d R + S 3 s a p 6 n o J B L Z m 0 7 8 D P s F M y g 4 O 7 a U p h b y B i / Z p f Q d l S x F G y n G N k b 0 C 2 n d G m i j V s K 6 U j 9 P l G w 1 A 4 d u M 6 U 4 Z X 9 X R u K / 9 X a O S Y H n U K o L E d Q / O u h J J c U N R 1 m R b v C A E f Z c 4 R x I 9 x f K b 9 i h n F 0 i Z Z c C M F v

M g h Y I G C p R w n h l g a S y h F V 8 f D e u t G z B W a H W G v Q w 6 K b t U I h G c o Z O i 8 l 4 Y a 9 m 1 v d Q d R b 8 f Z o L u U L d H R Z h o j U o j W H E L 1 L I 0 k z D o 9 y 9 q U W 0 Q l S t + 1 R + B / i X B m F T I G C d R + S 3 s a p 6 n o J B L Z m 0 7 8 D P s F M y g 4 O 7 a U p h b y B i / Z p f Q d l S x F G y n G N k b 0 C 2 n d G m i j V s K 6 U j 9 P l G w 1 A 4 d u M 6 U 4 Z X 9 X R u K / 9 X a O S Y H n U K o L E d Q / O u h J J c U N R 1 m R b v C A E f Z c 4 R x I 9 x f K b 9 i h n F 0 i Z Z c C M F v y 3 9 J s 1 Y N / G

E V X 3 Z o i r h l 8 G G r P R P L Y 7 v O c = " > A A A C H n i c b V D L S g M x F M 3 4 t r 6 q L t 0 E i + D G M l M U X R b d u F S w r d C p Q y a 9 o 8 F M M i R 3 h D r t l 7 j x V 9 y 4 U E R w p X 9 j W r v w d S D J 4 d x 7 k 5 w T Z 1 J Y 9 P 0 P b 2 J y a n p m d m 6 + t L C 4 t L x S X l 1 r W p 0 b D g 2 u p T b n M b M g h Y I G C p R w n h l g a S y h F V 8 f D e u t G z B W a H W G v Q w 6 K b t U I h G c o Z O i 8 l 4 Y a 9 m 1 v d Q d R b 8 f Z o L u U L d H R Z h o j U o j W H E L 1 L I 0 k z D o 9 y 9 q U W 0 Q l S t + 1 R + B / i X B m F T I G C d R + S 3 s a p 6 n o J B L Z m 0 7 8 D P s F M y g 4 O 7 a U p h b y B i / Z p f Q d l S x F G y n G N k b 0 C 2 n d G m i j V s K 6 U j 9 P l G w 1 A 4 d u M 6 U 4 Z X 9 X R u K / 9 X a O S Y H n U K o L E d Q / O u h J J c U N R 1 m R b v C A E f Z c 4 R x I 9 x f K b 9 i h n F 0 i Z Z c C M F v y 3 9 J s 1 Y N / G p w u l u p H 4 7 j m C M b Z J N s k 4 D s k z o 5 J i e k Q T i 5 I w / k i T x 7 9 9 6 j 9 + K 9 f r V O e O O Z d f I D 3 v s n G Y + j r g = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " k / 5 s E V X 3 Z o i r h l 8 G G r P R P L Y 7 v O c = " > A A A C H n i c b V D L S g M x F M 3 4 t r 6 q L t 0 E i + D G M l M U X R b d u F S w r d C p Q y a 9 o 8 F M M i R 3 h D r t l 7 j x V 9 y 4 U E R w p X 9 j W r v w d S D J 4 d x 7 k 5 w T Z 1 J Y 9 P 0 P b 2 J y a n p m d m 6 + t L C 4 t L x S X l 1 r W p 0 b D g 2 u p T b n M b M g h Y I G C p R w n h l g a S y h F V 8 f D e u t G z B W a H W G v Q w 6 K b t U I h G c o Z O i 8 l 4 Y a 9 m 1 v d Q d R b 8 f Z o L u U L d H R Z h o j U o j W H E L 1 L I 0 k z D o 9 y 9 q U W 0 Q l S t + 1 R + B / i X B m F T I G C d R + S 3 s a p 6 n o J B L Z m 0 7 8 D P s F M y g 4 O 7 a U p h b y B i / Z p f Q d l S x F G y n G N k b 0 C 2 n d G m i j V s K 6 U j 9 P l G w 1 A 4 d u M 6 U 4 Z X 9 X R u K / 9 X a O S Y H n U K o L E d Q / O u h J J c U N R 1 m R b v C A E f Z c 4 R x I 9 x f K b 9 i h n F 0 i Z Z c C M F v y 3 9 J s 1 Y N / G p w u l u p H 4 7 j m C M b Z J N s k 4 D s k z o 5 J i e k Q T i 5 I w / k i T x 7 9 9 6 j 9 + K 9 f r V O e O O Z d f I D 3 v s n G Y + j r g = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " k / 5 s E V X 3 Z o i r h l 8 G G r P R P L Y 7 v O c = " > A A A C H n i c b V D L S g M x F M 3 4 t r 6 q L t 0 E i + D G M l M U X R b d u F S w r d C p Q y a 9 o 8 F M M i R 3 h D r t l 7 j x V 9 y 4 U E R w p X 9 j W r v w d S D J 4 d x 7 k 5 w T Z 1 J Y 9 P 0 P b 2 J y a n p m d m 6 + t L C 4 t L x S X l 1 r W p 0 b D g 2 u p T b n M b M g h Y I G C p R w n h l g a S y h F V 8 f D e u t G z B W a H W G v Q w 6 K b t U I h G c o Z O i 8 l 4 Y a 9 m 1 v d Q d R b 8 f Z o L u U L d H R Z h o j U o j W H E L 1 L I 0 k z D o 9 y 9 q U W 0 Q l S t + 1 R + B / i X B m F T I G C d R + S 3 s a p 6 n o J B L Z m 0 7 8 D P s F M y g 4 O 7 a U p h b y B i / Z p f Q d l S x F G y n G N k b 0 C 2 n d G m i j V s K 6 U j 9 P l G w 1 A 4 d u M 6 U 4 Z X 9 X R u K / 9 X a O S Y H n U K o L E d Q / O u h J J c U N R 1 m R b v C A E f Z c 4 R x I 9 x f K b 9 i h n F 0 i Z Z c C M F v

Theorem C.1. Let B = {x 1 , x 2 , ..., x n } 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 x i 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 = x i ]1{x i ≤ a} = n -1 n i=1 ρ i 1{x i ≤ a} n -1 n i=1 ρ i n→∞ ----→ E q [ρ(x)1{x ≤ a}] E q [ρ(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.

C.2 CHANGING BEHAVIOUR POLICIES:

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 {x i } n i=1 be a dataset where each x i is sampled from P i independently. Then, the weighted importance sampling estimator μ = n i=1 ρi n j=1 ρj g(x i ) is consistent for E f [g(X)] where g(.) is a function of interest and ρ i = q(xi) pi(xi) .

Proof. First, we rewrite μ = and let Y i = ρ i g(x i ).

Next, we find the expectations of Y i and ρ i .

E pi [Y i ] = q(x) p i (x) g(x)p i (x)dx = E q [g(X)] E pi [ρ i ] = q(x) p i (x) p i (x)dx = q(x)dx = 1

Finally, since all Y i and all ρ i have the same expectation and are independent, we apply the law of large numbers to obtain that μ =

EQUATION

:

There 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.

k 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.

While 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.

Due to computational complexity we only test WIS-Optimal in the markov chain.

We forgo evaluating any variants of the WIS update in the Torcs race car simulator based on the performance in the simpler domains.

Additional results in the Mountain Car Domain using a three layer neural network can be found in the appendix.

Figures and Tables:

Figure 1: Learning rate sensitivity study in the Random Walk Markov Chain with buffer size n = 15000, batch size b = 16 For simplicity we write the policies as follows: µ = [µ(left|•), µ(right| ). left µ = [0.5, 0.5], π = [0.1, 0.9], center µ = [0.9, 0.1], π = [0.1, 0.9], right µ = [0.99, 0.01], π = [0.01, 0.99]. Additional results using V-Trace and Sarsa can be found in the appendix B.1

Figure 3: left Markov Chain Random Walk with n = 15000, b = 16, µ = [0.99, 0.01], π = [0.01, 0.99], optimal learning rates from above parameter study center Four rooms environment n = 10000, b = 32 with optimal settings from below parameter studies. We report 70% confidence bands for ease of comparison. right Torcs racing car simulator learning curves of RMSRE calculated over a pre-collected evaluation set. α BC-IR = 1e -4 , α IR = 1e -4 , α IS = 1e -6 selected from a parameter study using RMSProp and the NVIDIA network designed for self-driving cars(Bojarski et al., 2016)

, which prioritizes training examples according to the temporal difference error w i = |δ 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).

Figure 5: Baird's Star Problem.

Figure 7: Mountain Car: Mini-batch Gradient Descent with constant learning rate π = [0, 0, 1.0], |B| = 50000, Left = 0.1, Right = 0.5

Figure 8: Mountain Car: Mini-batch Gradient Descent with Adam Optimizer. x-axis: learning rates, y-axis: RMSVE π = [0, 0, 1.0], |B| = 50000, Left = 0.1, Right = 0.5

R b d u F S w r d C p Q y a 9 o 8 F M M i R 3 h D r t l 7 j x V 9 y 4 U E R w p X 9 j W r v w d S D J 4 d x 7 k 5 w T Z 1 J Y 9 P 0 P b 2 J y a n p m d m 6 + t L C 4 t L x S X l 1 r W p 0 b D g 2 u p T b n M b

y 3 9 J s 1 Y N / G p w u l u p H 4 7 j m C M b Z J N s k 4 D s k z o 5 J i e k Q T i 5 I w / k i T x 7 9 9 6 j 9+ K 9 f r V O e O O Z d f I D 3 v s n G Y + j r g = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " k / 5 s E V X 3 Z o i r h l 8 G G r P R P L Y 7 v O c = " > A A A C H n i c b V D L S g M x F M 3 4 t r 6 q L t 0 E i + D G M l M U X R b d u F S w r d C p Q y a 9 o 8 F M M i R 3 h D r t l 7 j x V 9 y 4 U E Rw p X 9 j W r v w d S D J 4 d x 7 k 5 w T Z 1 J Y 9 P 0 P b 2 J y a n p m d m 6 + t L C 4 t L x S X l 1 r W p 0 b D g 2 u p T b n M b

y 3 9 J s 1 Y N / G p w u l u p H 4 7 j m C M b Z J N s k 4 D s k z o 5 J i e k Q T i 5 I w / k i T x 7 9 9 6 j 9+ K 9 f r V O e O O Z d f I D 3 v s n G Y + j r g = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " k / 5 s E V X 3 Z o i r h l 8 G G r P R P L Y 7 v O c = " > A A A C H n i c b V D L S g M x F M 3 4 t r 6 q L t 0 E i + D G M l M U X R b d u F S w r d C p Q y a 9 o 8 F M M i R 3 h D r t l 7 j x V 9 y 4 U E Rw p X 9 j W r v w d S D J 4 d x 7 k 5 w T Z 1 J Y 9 P 0 P b 2 J y a n p m d m 6 + t L C 4 t L x S X l 1 r W p 0 b D g 2 u p T b n M b

y 3 9 J s 1 Y N / G p w u l u p H 4 7 j m C M b Z J N s k 4 D s k z o 5 J i e k Q T i 5 I w / k i T x 7 9 9 6 j 9+ K 9 f r V O e O O Z d f I D 3 v s n G Y + j r g = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " k / 5 s E V X 3 Z o i r h l 8 G G r P R P L Y 7 v O c = " > A A A C H n i c b V D L S g M x F M 3 4 t r 6 q L t 0 E i + D G M l M U X R b d u F S w r d C p Q y a 9 o 8 F M M i R 3 h D r t l 7 j x V 9 y 4 U E Rw p X 9 j W r v w d S D J 4 d x 7 k 5 w T Z 1 J Y 9 P 0 P b 2 J y a n p m d m 6 + t L C 4 t L x S X l 1 r W p 0 b D g 2 u p T b n M b

p w u l u p H 4 7 j m C M b Z J N s k 4 D s k z o 5 J i e k Q T i 5 I w / k i T x 7 9 9 6 j 9 + K 9 f r V O e O O Z d f I D 3 v s n G Y + j r g = = < / l a t e x i t > t e x i t s h a 1 _ b a s e 6 4 = " k / 5 s

Figure 10: Intermediate sampling policies in a random walk markov chain. (left) π = [0.1, 0.9], µ = [0.9, 0.1], (right) π = [0.01, 0.99], µ = [0.99, 0.01]

Peer review (iclr2019):
 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. On the overall I think this paper presents an interesting idea of IR for off-policy learning. In particular it hinges on designing the sampling strategy in replay buffer to handle the distribution discrepancy problem in off-policy RL. Through this simple off-policy estimator, the authors are able to show improvements when compared with other state-of-the-art off-policy methods such as IS and WIS, which are both known to have high-variance issues. The authors also provided bias and consistency analysis of these estimators, which are reasonable theoretical contributions. The major theoretical question/concern that I have is in terms the variance comparisons between IR and IS/WIS. While I see some discussions in Sec 3.3, is there a concrete result showing that IR estimator has lower variance when compared to IS and WIS (even under certain technical assumptions)? This is an important missing piece for IR, as the original motivation of not using IS/WIS estimators is because of their issues on variance. In terms of experiment, while the authors have done a reasonably good job evaluating IR on several domains based on the MSE of policy evaluation, to make it more complete can the authors also show the efficiency of IR when compared to state-of-the-art algorithms such as V-trace, ABQ or Re-Trace (which are cited in the introduction section)?