Robust On-Policy Sampling for Data-Efficient Policy Evaluation in Reinforcement Learning
Authors: Rujie Zhong
Duohan Zhang
Lukas Schäfer
Stefano V Albrecht
Josiah P. Hanna
Venue: NeurIPS 2022 Accept (2022)
Keywords: Reinforcement Learning
policy evaluation
on-policy
data collection

Abstract: Reinforcement learning (RL) algorithms are often categorized as either on-policy or off-policy  depending on whether they use data from a target policy of interest or from a different behavior policy. In this paper, we study a subtle distinction between on-policy data and on-policy sampling in the context of the RL sub-problem of policy evaluation. We observe that on-policy sampling may fail to match the expected distribution of on-policy data after observing only a finite number of trajectories and this failure hinders data-efficient policy evaluation. Towards improved data-efficiency, we show how non-i.i.d., off-policy sampling can produce data that more closely matches the expected on-policy data distribution and consequently increases the accuracy of the Monte Carlo estimator for policy evaluation. We introduce a method called Robust On-Policy Sampling and demonstrate theoretically and empirically that it produces data that converges faster to the expected on-policy distribution compared to on-policy sampling. Empirically, we show that this faster convergence leads to lower mean squared error policy value estimates.

Robust On-Policy Sampling for Data-Efficient Policy
Evaluation in Reinforcement Learning
Rujie Zhong', Duohan Z Lukas Schäfer', Stefano V. Albrecht', Josiah P. Hanna
School of Informatics, University of Edinburgh
2 Statistics Department, University of Wisconsin Madison
3 Computer Sciences Department, University of Wisconsin Madison Correspondence to (dzhang357,jphan jphannah @ @wisccedu
Abstract
Reinforcement learning (RL) algorithms are often categorized as either on-policy or off-policy depending on whether they use data from a target policy of interest from different behavior policy. In this paper, tween on-policy data and on-policy sampling in the context of the RL sub-problem of policy evaluation. We observe that on-policy sampling may fail to match the expected distribution of on- on-policy data after observing only a finite number of tra- jectories and this failure hinders data-efficient policy evaluation. Towards improved data-efficiency, we show how non-i.i.d., off-policy sampling can produce data that closely matches the expected on-policy data distribution and consequently increases the accuracy of the Monte Carlo estimator for policy evaluation. We in- troduce a method called Robust On-Policy Sampling and demonstrate theoretically and empirically that it produces data that converges faster to the expected on-policy distribution compared to on-policy sampling. Empirically, we show that this faster convergence leads to lower mean squared eттоr policy value estimates.
study subtle distinction be-
Introduction
Reinforcement learning (RL.) algorithms are often categorized using the dichotomy of on-policy versus off-policy. On-policy algorithms learn about particular target policy using data collected by behaving according to the target policy. Off-policy algorithms use data collected by behaving according to different behavior policy. We study subtle distinction between on-policy data versus on-policy sampling as a step towards more data-efficient RL algorithms. To better understand this distinction, consider simple example. In this example, a certain target policy repeatedly visits state in which takes action A with probability 0.2 and action B with probability 0.8. Under on-policy sampling, after five visits to this state, might actually observe action A 2 times and action B 3 times instead of the expected and 4 times. Alternatively, we could collect data off-policy by deterministically tracking the expected target policy action proportions; doing results in observing the exact expected action frequencies. Though the latter case uses off-policy sampling, it produces data that is arguably more on-policy than the data produced by on-policy sampling.
In this paper, we study the distinction between on-policy sampling and on-policy data in the context of the RL sub-problem of policy evaluation Zinkevich al. [006]. In policy evaluation, we are given an evaluation policy and asked to estimate the expected return that would be accrued when running the evaluation policy task of interest. This problem is important for high confidence deployment of RL-trained policies. RL applications, such as robotics, data-efficient policy evaluation is of the desire the most accurate estimate with minimal collected data. While much research has gone into how to most efficiently use a set of already collected data, i.e., the off-policy policy evaluation problem [Tiang and 2016 Thomas and Brunskill 2016 an implicit assumption
utmost importance
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

in the RL community is that on-policy data is preferred to off-policy data when available. When data can be collected on-policy, we can use the Monte Carlo estimator which computes a mean return estimate using trajectories sampled i.i.d. by running the evaluation policy. In the limit, with infinite trajectories, the empirical proportion of each trajectory will converge to its true probability under the evaluation policy and the estimate will converge to the true expected return. However, for any finite sample-size, the empirical proportion of each trajectory will likely fail to match the true probability and the estimate will have error. Such sampling error is an inevitable feature of i.i.d. sampling. The probability of each new trajectory is unaffected by the trajectories occurring in the past and thus the only way to ensure the empirical distribution matches the true probability is to sample large enough data set. That is, it is only in the limit that on on-policy sampling produces exactly on on-policy data.
The observations made so far raise the question: "can non-i..d., offlpo trajectory sampling cause the empirical distribution of trajectories to converge to the expected on-policy distribution faster?" We answer this question affirmatively by introducing a method that adapts the data collecting behavior policy to consider what data has already been collected when selecting future actions. We call this method Robust On-Policy Sampling (ROS since the empirical distribution of data it produces converges faster to the expected on-policy trajectory distribution compared to standard on-policy sampling. We give a theoretical result supporting this claim and then confirm our theory with policy evaluation experiments in finite and continuous-valuee state- and action-space domains showing 1) ROS reduces sampling error in finite datasets and 2) consequently lowers the MSE of policy value estimates compared to i..dd on- on- polpoicy sampling.
Our paper contributes to the field of RI. on two fronts. On one front, we introduce practical method for data collection and demonstrate empirically that it leads to more accurate policy evaluation compared to on-policy sampling. Simultaneously, our work examines nuance in the on-policy versus off-policy dichotomy. A better understanding of this nuance opens up the possibility of designing new data collection procedures to improve the data efficiency of any RL algorithm that relies upon on-policy data.
2 Related Work
Data collection is a fundamental part of the RL problem. The most widely studied data collection problem is the question of how an agent should explore its environment to learn an optimal pol- icy [Schäfer et al. 2022 Ostrovski et al. 2017 Tang al. 2017]. In contrast to these approaches, our work focuses on the question of how an agent should collect data to evaluate a fixed policy. When given a choice of how to collect data for policy evaluation, on-policy data collection is generally preferable to off-policy data collection [Sutton and Barto 1998]. Notable exceptions are adaptive
importance sampling (AIS) methods (oosterhuis and de Rijke 2020 Hanna et al. 2017 Ciosek and
Whiteson 2017 [Buchard et al. 2016 Frank et al., 2008 and quasi-Monts Carlo methods [Arold
et al. 2022] Both these AIS methods and the Quasi-Monte Carlo method of Armold et al. [222]] lower variance in estimates computed with future samples while our method lowers the total error in the estimate computed from both past and future samples.
In one of our experiments, we consider a setting where we already have some data (collected off- policy) and must decide how to collect additional data for policy evaluation. This problem has been previously studied in the bandit literature (Tucker and Joachims, 2022) or when there are only finite number of policies that could be ran [Konyushova et al. [02T]] These prior works also show that on-policy data collection is a sub-optimal choice. They differ from (and are complementary to) our work in that they still use i.i.d. sampling for data collection whereas we show how non-independent sampling can be used to produce data that more closely matches desired distribution.
The method we introduce in this paper is motivated by the idea of decreasing sampling error in all collected data. Previous work has considered how sampling error can be reduced after data collection by re- re-weighting the obtained samples. For example. [aanaa et al. (202T) show how importance sampling with an estimated behavior policy can lower sampling error and lead to more accurate policy evaluation. Similar methods have also been studied for policy evaluation in multi-armed bandits [Narita et al.] 2019 Li et al. 2015) and works assume data is available a priori and ignore the question of how to collect it when unavailable.
learning (Pavse et al. 2020]. These prior
We provide an soun-s implementation of ROS and all experimental data at /tttps://githut com/ uoe- httptt///roouuusooooooyccc. dotloeeocy_daaaccoleeittoooo

---

Finally, the idea of adapting the sampling distribution, (i.e., behavior policy) has analogs outside of policy evaluation in Markov decision processes. O'Haggan [987] identifies flaws with i.i.d. sampling for Monte Carlo estimation that motivate taking past samples into account. Rasmussen and Ghahramani 2003] use Gaussian processes to represent uncertainty in an expectation be evaluated and use this uncertainty to guide future sample generation. Concurrent to this work, Mukherjee et al. [022]] introduced an uncertainty aware method for data collection in policy evaluation that can be seen an adaptation of these ideas to the RL.
Preliminaries
In this section, we introduce notation, formalize the policy evaluation problem, and introduce the Monte Carlo estimator for policy evaluation.
3.1 Notation
We assume the environment is finite-horizon, episodic Markov decision process (MDP) with state S, action A, transition function, P: A x X [0, 1]. reward function R S x + R. discount factor maximum horizon 1, and initial state distribution do [Puterman 2014). We assume that and A are finite though our empirical analysis considers both settings. We assume that the transition and reward functions are unknown. A policy, : S x A + [0, 1]. is function mapping states and actions to probabilities. We use [[aas)) = (ss, a) denote the conditional probability of action given state and P(s'|s, [s, a) := P(s, s') to denote the conditional probability of state s given state and action a. Since we assume a finite-horizon, we assume the state definition implicitly includes temporal information (Agarwal et al. 2022
Let h == (50, do, To,
01-1, T(-1) be trajectory and g(h) 1-11 yrr be the dis- counted return of h. Any policy induces a distribution over trajectories, Pr(h|/). We define the value of policy, v(x), the expected discounted return when sampling a trajectory by following policy x: t(τ) == [[g H ~ x En Pr(h T (h) where H a random variable representing trajectory and H denotes sampling H by running π in the given environment.
3.2 Policy Evaluation
In the policy evaluation problem, we given evaluation policy, Te- for which we would like to estimate ((Te). Conceptually, algorithms for policy evaluation involve two steps: collecting data (or receiving previously collected data) and computing collected by running a policy which we call the behavior policy. If the behavior policy is the same the evaluation policy data collection is on-policy; otherwise it is off-policy. Whether on-policy or off-policy, we assume the data collection process produces a set of trajectories, write D to denote collecting these trajectories by running policy и. The final value estimate is then computed by policy evaluation estimator (PE) that maps the set of trajectories to scalar-valued estimate of vf o(Ta). Following earlier work in policy evaluation (e.g.. [Thomas and Brunskil] 2016
estimate from that data. We assume that data
== {H, ) ) and
Jiang and Li 2016 ), we set our goal to be policy evaluation with low mean squared error (MSE):
MSE PE = E (((PE()) - v(Te)) -o(me)
D~mB
where is the behavior policy that is run collect D and PF is generic policy evaluation estimator.
3.3 Monte Carlo Policy Evaluation
Perhaps the most fundamental, model-free policy evaluation method is the Monte- Carlo (MC) estimator. Given data set, D, of n trajectories, the Monte Carlo estimate, MC(D), is the mean return over D:
MC(D) (H,, Pr(()))g()),,
where Pr(h D) denotes the empirical probability of h. i.c. how often h appears in D.
3

---

If trajectories in D are collected i.... by running (i.e., on-policy sampling). the Monte Carlo estimator unbiased and consistent assuming g(h) is bounded [Sen and Singer 1993]. However, this method can have high variance as on-policy sampling may require many trajectories for the empirical trajectory distribution Pr(h] P)) to accurately approximate Pr(A|(t)) me)) Since on-policy
sampling collects each trajectory i.i.d., it relies on the law of large numbers for an accurate weighting on each possible return. We call error between Pr(h[[) and Pr(h (T) sampling error.
Pata-Conditioned Monte Carlo Estimates
In this section, motivate how estimator that uses on-policy data can benefit from off-policy sampling. Specifically, we consider the Monte Carlo estimator and suppose that we have already collected data set, D1, of trajectories. We wish to collect an additional set of trajectories, D2. and compute the Monte Carlo estimate with the set D1UD2. Note that D1 is fixed set (the trajectories already observed) while D2 is random variable (the trajectories yet to be observed). How should D2 be collected for minimal MSE policy evaluation with the Monte Carlo estimator? Our analysis in this section suggests that i.i.d. sampling of trajectories with n. may be sub-optimal choice.
In this setting, the Monte Carlo estimator using Dj U D2 can be written as:
RD22
MC(D; U2)
g(h))))))))))))
9(1,),
fixed value
random variable
where rDD and r.D, are the number of trajectories in D1 and D2, respectively and n nD, + Da We refer to 3 as the data-conditioned Monte Carlo estimator.
Viewing the Monte Carlo estimator as a sum between fixed quantity and random quantity changes how we view the statistical properties of the estimator. For instance, while the Monte Carlo estimator known to be unbiased under on-policy sampling, its data-conditioned estimate is biased as shown in the following proposition.
Proposition The data conditioned Monte Carlo estimator is biased under on-policy sampling of D2 unless MC(D;) = v(TTe) or D1 = O. That is:
E MC(D.UL U D2)
D2 te * v(Te).
Proof. See Appendix A
Remark 1. Proposition L holds even Df was collected under on-policy sampling as well. When Dj was collected under on- on-policy sampling then the Monte Carlo estimator is unbiased considering all possible realizations of D2. However, once the trajectories in DD are fixed, it no longer matters what others values they could have taken.
Can we reduce the bias of the data-conditioned Monte Carlo estimator by collecting D2 with policy that different than ne? We conclude this section with an example showing that we can. Consider one-step MDP with one state, and two actions, do and a,. The return following an is 2 and the return following a1 is 4. The evaluation policy is TT (a (s) = Th [s] = 0.5. Suppose that, after sampling 3 trajectories, DD contains two of {8, ao, 2} and one occurrence of {s, 01 4). Note that action ag is over-sampled relative to its true probability in s and a1 is sampled If we collect an additional trajectory with ne the expected value of the Monte Carlo estimate is: { + 2 + 4 + (ao) + 4T (a1)) = 11 2.75. The true value, v(Te) = 3 and thus, conditioned on prior data, the Monte Carlo estimate is biased in expectation
4
shown in Proposition I If instead we choose the behavior policy such that ne (az) = 1 then neither action is over- or under-samplee and the expected value of the Monte Carlo estimate is the exact true value: ] + 4 4 4) 12 = 3.
This example highlights that adapting the behavior policy to consider previously collected data can lower the expected finite-sample error of policy evaluation. In the next section, we introduce an adaptive data collection method that adjusts the behavior policy based on what data has already been observed so as to lower the MSE of a Monte Carlo estimate using all observed data.

---

5 Robust On-Policy Data Collection
In this section, we introduce a method that adapts the data-collecting behavior policy online to minimize sampling error in the data used by the Monte Carlo estimator. Specifically, let Dj denote all trajectories observed up to time-step t of the current trajectory (including the partial current trajectory). At time-step error, i.e. divergence between Pr(h) xe) and Pr(h D.). Our method can be run starting with D, = 0 or already containing trajectories in setting like that described in the preceding section.
method sets the behavior policy as to reduce the current sampling
To reduce sampling error when collecting future trajectories, we want to adjust the behavior policy to increase the probability of under-sampled trajectories, i.e., h for which Pr(h][2,) < Pr(h/TT mT). Unfor- tunately, the trajectory distributions are unknown because the transition function, P. is also unknown. Instead, we will increase the probability of under-sampled actions. Let TD S x A - [o, 1] denote the empirical policy which gives the proportion of times that each action was taken in each state in D,. If (alls) < (a(als), then has appeared less often in the data than it would in expectation under T.. Thus, we should increase the probability of a in s for future data collection.
When the state and action spaces are finite, TD can be computed exactly as the maximum likelihood policy under D;:
TD == arg max ((T).
((T) = Σ log π (ar [s
(4)
RED: d'm0
where the argmax taken with respect to all policies. In larger MDPS, we require function approxi- mation which may make TD hard to compute and update online new data is collected. Fortunately, with an additional assumption we can determine the direction to adjust action probabilities without explicitly computing wD This assumption is that n. belongs to a class of differentiable, parameterized policies and is parameterized by vector 0 E Rd This assumption is mild for many RL applications as it permits tabular, linear, and neural network policy representations. We use 0. represent the parameter values for Te. We show in the next subsection that the gradient of the log-likelihood at O.. VoL(mo))o=o)) can be used to make sampling-error- error-reducing changes to the behavior policy.
5.1 Robust On-Policy Sampling
Our primary algorithmic contribution Robust On-Policy Sampling (ROS) reduces sampling error by adapting the behavior policy with single step of gradient descent on the log-likelihooe each time-step. From here on, we use VoL to denote the gradient of the log-likelihood evaluated at O.- Observe that V provides a direction to adjust 0, to increase the probability of actions that were over-sampled relative to their probability under Re- Thus, Vo provides direction to adjust Oe to decrease the probability of over-sampled actions for which (aass)) > Te (a)s). With this insight, ROS is able adapt 0. so that TD tracks मe without computing Tp. At each time-step, ROS computes V C with all state- pairs previously observed and then changes the evaluation policy parameters with single step of gradient descent that umder-sample actions have greater probability than they would have under Te-
Pseudocode for ROS is given in Algorithm| I ROS first computes VoL with previously collected trajectories if any are provided (Line 4). ROS then collects n additional trajectories by interacting with the given MDP (Lines 6-14). For each action selection, ROS sets the behavior policy parameters (Lines and 10). It then computes Ve log (A|s))) (Lines 11 and 12). Finally, the chosen action is executed in the environment, reward
as 0. - a V VeL(m))) VoL(To)le received, and the agent moves to the next state (Line 13). Importantly, note that updating V C requires per-timestep computation that is linear in the number of policy parameters and remains constant as the size of D grows.
(e=0, and updates
5.2 ROS Convergence
This section develops our theoretical understanding of ROS. Due to space constraints, we defer all proofs to Appendix B First, we show that ROS converges to the expected state visitation frequencies under ne- Second, we show that, for a fixed state, (-(+ss) converges to (-ls)) faster under ROS compared to on-policy sampling. Finally, we introduce upper bound on the squared error between
5

---

Algorithm Robust On-Policy Sampling.
1: Input: Evaluation policy with parameters P., step size a, previously collected trajectories to
used for policy evaluation, D1 (possibly empty), number of trajectories to collect, ?.
2: Output: Data set of trajectories.
3: & < number of state-action tuples in D)
4: VoL < x (s,a)ED Vo log (ala)))
5: D <- D1
6: for <i< n do
7:
so dg
8:
for 0 I < do
9:
0, + 0. Vo
10:
+ A A~ (-
11:
VoL + k VoCC x+ V 1olo
ktI
12:
*+ k+1
8141 P(-|s), at), + R(s
14:
end for
D {S0, ao, Po. 8-11 a1-1, (1-1))
16: end for
Return D
Monte Carlo estimate and v(Te) terms of sampling error which shows how ROS's faster convergence affects the MSE of policy evaluation. These results use the following assumption:
The discrete state-space of the MDP has directed acyclic graph (DAG) structure. Specifically, states in S can be partitioned into disjoint sets S, indexed by episode step. The transition function is such that P(s'|s,, a) >> 0 implies that s St and s' E ES++1-
Assumption 1.
Note that Assumption M is mild any time-step part of the state (as we have already assumed in Section 3.I.
MDP can be made DAG by including the current
Assumption 2. ROS uses a step-size of a + oo and the behavior policy is parameterized as a softmax function, i.e., To (als) e...,, where for each state, 8, and action, a, we have a parameter 0z.a- As we formally show in Appendix B this assumption implies that ROS always takes the most under-sampled action in each state.
We also introduce the notation of d', (s) as the probability of visiting state at episode time t while following policy x and d', (s) as the empirical frequency of visitations to state episode time after observing trajectories.
Theorem 1. Under Assumptions 1 and 2 and ROS action selection, d',(s) converges to d (s) with probability for all E S and < <.
lim (s) ds))s,, vs E stttk n=+00
Theorem 2. Let be a particular state that is visited m times during data collection and assume that [A| 2. Under Assumption 2 (= (=)(s((-)))]
(2) under ROS sampling while Op( ( under on-policy sampling, where O, denotes stochastic boundedness.
Theorem 3. Assume Vs E S,a E A that R(s, a) S Ruax- The squared error in the Monte Carlo estimate using D can be upper-bounded by:
(u(me) MC(D))
22 R2 / 2D (dhlld4.) + 2Es [Daa m (-()).
Remark 2. The second term in the bound in Theorem is the KL-divergence between and Te which Theorem tells us will decrease faster under ROS action selection. The first term the KL-divergence between the empirical and true state distributions which depends both on sampling

---

Sampling error
8P
Sampling error
10
805
10"3
10
1
10-1
10-4
0FD+8PG
10-1
10
10'
10"
10
10"
Timesteps
Timesteps
Without initial data
(b) With initial data
Figure 1: Sampling error (KL) curves of data collection in the GridWorld domain. Each strategy is followed to collect data with 23T steps, and all results are averaged over 200 trials with shading indicating one standard error intervals. Figures ((a) and [(b] show the sampling error curves of data collection without and with initial data, respectively. Axes in these figures are log-scaled.
error in action selection as well as sampling error in the transition and initial state distributions. While the former decreases faster under ROS, the latter will decrease the same for both ROS and on-policy sampling. Hence, the theoretical faster rate of ROS for reducing sampling error in action selection may be muted by high environment stochasticity. The experimental results given in Figure 12(a) complement this theoretical observation.
Empirical Study
We next conduct empirical study of ROS in policy evaluation problems. Our primary goal is to answer the following questions:
Does ROS reduce sampling error compared to on-policy sampling?
2. Does ROS lower policy evaluation MSE when starting with and without off-policy data?
We conduct policy evaluation experiments in four domains covering discrete and continuous state and action spaces: multi-armed bandit problem (Sutton and Barto 1998). Gridworld [Thomas and Brunskill 2016), CartPole, and Continuous CartPole [Brockman et al. 2016 Since these domains widely used, we defer their descriptions Appendix C Our primary baseline for comparison is on-policy sampling (OS) of i.i.d. trajectories with the Monte Carlo estimator used to compute the final policy value estimate (denoted OS-MC). We also compare BPG which finds minimum variance behavior policy for the ordinary importance sampling (OIS) policy value estimator (Hanna et al. 2017] (denoted BPG-OIS), We provide full experimental details concerning how Tee and ((TT)) were determined in Appendix C2
6.1 Policy Evaluation without Initial Data
We first run experiments in a setting without initial data, in which all data is collected from scratch, Letting T denote the average length a trajectory, in each domain, we collect a total of 213T environment steps with each method and compute metrics every 2 2 2 trajectories. Note that we specify the number of environment steps rather than number of trajectories in our empirical results. For Bandit T = 1, for GridWorld T = 7.43, CartPole = 48.48, and for CanPPleeContiuonn settings for all experiments
= 49.56. The
presented in Appendix
We first verify that ROS reduces sampling error compared to on-policy sampling. We measure sampling error with the KL-divergence (KL) between тe and parametric maximum likelihood estimate of TD from the observe data. In Appendix D we give complete definition of the measure as well as an alternative measure that leads to qualitatively similar results. Due to space constraints, we only show this result for the GridWorld domain (Figure [(a];: results for other domains are qualitatively the same and can be found in Appendix D.I. Figure I(a] shows that with ROS sampling error decreases faster than os. Unsurprisingly, BPG increases sampling error
an off-policy method which adapts the behavior policy away from ne. These results answer our first empirical
7

---

Meain Squared Enror
2o1
10"
10-1
10"4
10"9
10"
10-1
10-1
10
Timestops
Timastops
Bandit
GridWorld
(c) CartPole
(d) CariPoleContinoous
OS-MC
BPC-OIS
BOSAMC
Figure 2: Mean squared error (MSE) of policy evaluation in the without initial data setting. Policy evaluation conducted on the data collected from each strategy, and these curves show the MSE of the estimates (lower is better). The vertical axis gives MSE and the horizontal axis is the amount of environment steps taken (both are log-scaled). Shading indicates one standard error.
(Mean Squared Enror
20
10
10"
15t
20-4
10
30
10"
10
10-
10
Timesteps
Timestaps
Timesteps
Timesttps
(a) Bandit
(b) GridWorld
(c) CartPole
(d) CariPolCContinuous
OS-MI
107D-D51-MC
1GPD-B7G)--5
10PD-505)-E
Figure 3: Mean squared error (MSE) of policy evaluation in the with initial data setting. Policy evaluation is conducted on the data collected from each strategy and a small set of initial data collected off off-policy. Axes and confidence intervals are the same as in Figure
question and confirm our theoretical claim that non-i.i.d. off-policy sampling can cause the empirical distribution of data to converge the expected on-policy distribution faster.
Ultimately, this paper focuses on reducing sampling error for lower MSE policy evaluation. Figure 2 shows that ROS lowers MSE compared to both OS and BPG across all domains These results address our second empirical question and support the claim that reducing sampling error decreases the MSE of the Monte Carlo estimator for policy evaluation.
6.2 Policy Evaluation with Initial Data
Our next set of experiments considers a setting with initial data, in which set of 100 trajectories are already available and we wish
these trajectories our policy value estimate. These trajectories are collected via i.i.d. off-colicy sampling with behavior policy that is slightly different than πe. This setting is intended represent setting where π. has just been updated from an older policy and we would like to still use the off- off-policy data already collected from the older policy combined with the data to be collected. In addition to the off-policy data (OPD), we collect an additional 213T steps of environment interaction with each method. We do not count the initial 100 trajectories towards the total collected data.
For ROS, we use the OPD to initialize C.C. We expect to that ROS will collect data to combine with the OPD such that the aggregate data set looks as it had been collected with Te to begin with. We compare ROS to the following baseline methods. (OPD OS)-MC collects additional data with os and uses the Monte Carlo estimator with the total data-set. (OPD + OS)-(WIS + MC) uses weighted importance sampling (WIS) compute estimate from the OPD combines the estimate with Monte Carlo estimate using on- on-policy data. (OPD BPG)-OIS collects additional data with BPG and uses ordinary importance sampling the estimator with all data. Finally, (oS MC) replaces the 100
Numeric values for the final MSE of each method can be found in Appendix F We also report median and interquartile ranges of the error of each method in Appendix G

---

initial trajectories with trajectories from oS, then collects the remaining data with OS and uses the Monte Carlo estimator. In the case of (oS MC). the 100 initial trajectories are counted towards the total data collected.
Figure [(b) shows that sampling error decreases fastest for ROS as the additional data is collected. For policy evaluation, we show MSE for varying amounts of data in Figure D and provide numerical values for the final MSE in Appendix
We observe that the initial data provides an immediate reduction in MSE at the expense of injecting bias into the estimates. (OPD+OS)-MC struggles to reduce this bias while (OPD+ROS)-MC is able to through data collection. Overall, this result highlights that ROS can collect udditional data that reduces sampling eπror in the aggregate data set and produce lower MSE estimates compared to other data collection methods. Intuitively. OS requires many more samples to dilute the bias brought on by using OPD in the Monte Carlo estimator, while ROS is able to correct the empirical off-po aff-policy distribution to the expected on-policy distribution and use the Monte Carlo estimator without any off-policy corrections.
The comparison OS-MC demonstrates the potential of ROS for correcting an off-policy empirical distribution to the expected on-policy distribution. As noted above, OS-MC has 100 fewer trajectories than the other baselines. However even when including the initial 100 off-policy trajectories in the data total for all methods - ROS eventually obtains lower MSE compared to OS-MC. In this sense, ROS has taken an initially biased dataset and collected the right trajectories to make it look as-if the evaluation policy had collected all trajectories in the first place.
6.3 Sensitivity Study
Finally, we evaluate the sensitivity of ROS to hyper- parameter, environment, and policy settings. ROS requires setting step size, a, which controls how much ROS updates the behavior policy away from Te. We show MSE curves for ROS with different step size a on GridWorld and CartPole Figures I (a = 0 corresponds to OS). Figure 4aa) shows that, in GridWorld, ROS with any tested step-size produces lower MSE policy evaluation than OS for any data set size. As it collects more data, ROS with larger enables lower MSF because the norm of V decreases as sampling error decreases, and thus a larger a is required to make significant updates. A larger a value is also in line with our thcoretical results which prescribe a (1000) diverges and the second largest (a = 100) requires many steps before it improves upon os. Thus, in domains with continuous state-spaces, more conservative values may be preferred.
30. However, in CartPole, (Figure 4b).. ROS with the largest tested
Our final set of experiments considers how the stochasticity of domain and entropy of Th affect the relative improvement that ROS offers. In this sub sub-section, we study these settings in the Bandit domain for its simplicty; similar experimental results in choose a 1000 for the following experiments.
can be found in Appendix We
To study domain stochasticity, we first create variants of the Bandit environment by multiplying either the mean or scale of the reward distribution of each action by varying factor. In each experimental trial, we use ROS to collect 10007 steps for the Monte Carlo estimator and compute the relative MSE compared to the Monte Carlo estimator using OS with the same number of steps. Figure 4[c shows that as the factor on the mean increases, ROS provides a greater reduction in MSE as even small amounts of sampling error translate into large MSE when the reward means are large. On the other hand, as the scale factor increases, the MSF is dominated by reward noise and the relative benefit of reducing sampling error disappears.
We also evaluate the relative improvement of ROS as a function of the entropy of Te. For Te, we use e-greedy policies which select the optimal action in state with probability 1 1- and otherwise select an action uniformly at random. Relative improvement in MSE is shown in Figure [ For all c, ROS improves upon the MSE of os. The improvement is generally larger for more stochastic Te when sampling error in action selection will be highest.
7 Discussion and Future Work
This work has shown that off-policy non-i.i.d. sampling can produce data sets that more closely approximate the on-policy data distribution than on-policy i.i.d. sampling. We considered the problem of policy evaluation and showed that more closely approximating the on-policy data distribution leads to more data efficient policy evaluation across several domains. As far as we know, ROS is the first

---

Moan Squared Error
Mean Squared Eror
109
0.7
Relative MSE
Relative MSE
0.3
PC
20
emtrre Vg MP"
0.4
105 1EK0-MM
605c 300
10 10
10 Timesteps
10 10
10 Timesteps
10
10
64
0.2
0.4
0.5
Factors
Epsilon
(a) GridWorld
(b) CartPole
(c) Environment Noise
(d) Policy Noise
Figure 4: MSE of ROS with different step-size, a (a) and Hbb). Relative improvement of ROS in
Bandit compared to os with different stochasticity in the environment (4)) and policy (Kd)). The
relative MSE is computed the MSE of ROS divided by the MSE of OS. Results in these ligures averaged over 500 trials.
data collection method for policy evaluation that uses off- off-po sampling to produce more closely on-policy data than the data produced by on-policy sampling.
While ROS a first step towards off off-policy algorithms that produce data matching target distribution, highlight few limitations of the algorithm and our study. In our view, the main limitations of the ROS algorithm are the need to set a step-size parameter (in contrast to parameter-free on on-policy sampling) and the need to update VeL at each action step. For the former, future work should investigate robust methods for setting the step-size, particularly in settings where To generalizes across the space.. For the latter limitation, future study could consider only updating VeL the end of each episode instead of after each action choice (assuming more computation can be done between episodes). In terms of our study, for this paper chose study many different facets of ROS on a suite of simpler domains (see the appendices for additional ablations and extensions); a future study should assess the scalability of ROS with more complex function approximators. Finally, our theoretical results were conducted in the tabular setting; an important open question is at what rate ROS converges when Fe uses function approximator that must generalize across states. Beyond these minor technical limitations, our paper addresses fundamental research questions in RL and thus do not see obvious negative societal impacts that are unique this work in comparison other work in RL and policy evaluation.
While evaluated ROS for policy evaluation, the long-term importance of this work may be in exploring the distinction between on-policy sampling and on-policy data. On-policy RL algorithms require on-policy data and work suggests that adaptive off-po sampling can produce on-policy data more efficiently than on-policy sampling. In the future, we wish to study these insights for on-policy policy improvement algorithms (e.g., policy gradient methods (Willimss 1992 Schulman et al. 2017 and to extend our convergence results to non-tabular settings.
8 Conclusion
In this paper, we have introduced a novel data collection method for policy evaluation in reinforcement learning environments. Our method Robust On-Policy Sampling (ROS) considers previously collected data when selecting actions to reduce sampling error in the entire collected data set. We show both in theory and in practice that data from ROS converges faster the on-policy data distribution compared to on- on-policy sampling. Empirically, we find that faster convergence to the on on-policy data distributions lowers the MSE of policy evaluation.
Acknowledgments and Disclosure of Funding
We thank Ishan Durugkar, Brahma Pavse, Subhojyoti Mukherjee, Elliot Fosong, and Filippos Christianos for their feedback which greatly strengthened the paper. We also wish to acknowledge the anonymous reviewers for their comments and constructive criticisms. Support for this research was provided by the Office of the Vice Chancellor for Research and Graduate Education the University of Wisconsin Madison with funding from the Wisconsin Alumni Research Foundation.
10

---

References
Alckh Agarwal, Nan Jiang, Sham M. Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. 2022.
Alen Alexanderian. Some notes asymptotic theory in probability. Notes. University of Maryland, 2009.
Sébastien M. R. Arnold, Pierre L'Beuyer, Liyu Chen, Yi-fan Chen, and Fei Sha. Policy learning and evaluation with randomized quasi-monte carlo. In International Conference on Artificial Intelligence and Statistics, 2022.
Guillaume Bouchard, Théo Trouillon, Julien Perez, and Adrien Gaidon. Online learning to sample. arXiv preprint arXiv:1506.0000 2016.
Greg Brockman, Vicki Cheung. Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. OpenAl Gym. arXiv preprint arXiv: 2016.
Kamil Ciosek and Shimon Whiteson. OFFER: Off-environment reinforcement learning. In AAAI Conference on Artificial Intelligence, 2017.
Mehrdad Farajtabar, Yinlam Chow, and Mohammad Ghavamzadeh. More robust doubly robust off-policy evaluation. In International Conference on Machine Learning, 2018.
Jordan Frank. Shie Mannor, and Doina Precup. Reinforcement learning in the presence of rare events. In International Conference on Machine Learning, 2008.
Josiah P. Hanna, Philip S. Thomas, Peter Stone, and Scott Niekum. Data-efficient policy evaluation through behavior policy search. In International Conference on Machine Learning. 2017.
Josiah Hanna, Scott Niekum, and Peter Stone. Importance Sampling in Reinforcement Learning with an Estimated Behavior Policy. Machine Learning, 110(6):167--331,, May 2021.
Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array programming with NumPy. Nature, 585(7825):357-362, 2020.
Kevin Sheppard, Tyler Reddy,
Nan Jiang and Lihong Li. Doubly robust off-policy evaluation for reinforcement learning. In International Conference Machine Learning, 2016.
Ksenia Konyushova, Yutian Chen, Thomas Paine, Caglar Gulcehre, Cosmin Paduraru, Daniel J. Mankowitz, Misha Denil, and Nando de Freitas. Active offline policy selection. In Advances in Neural Information Processing Systems, 2021.
Hoang Le, Cameron Voloshin, and Yisong Yue. Batch policy learning under constraints. In Interna- tional Conference on Machine Learning, 2019.
Lihong Li, Rémi Munos, and Csaba Szepesvári. Toward minimax off-policy value estimation. In International Conference Artificial Intelligence and Statistics, 2015.
Jay Mardia, Jiantao Jiao, Ervin Tánczos, Robert Nowak, and Tsachy Weissman. Concentration inequalities for the empirical distribution of discrete distributions: beyond the method of types. Information and Inference: Journal of the IMA, 9(4):813-85L) 2019.
Subhojyoti Mukherjee, Josiah P. Hanna, and Robert Nowak. ReVar: Strengthening Policy Evalu- ation via Reduced Variance Sampling. In International Conference on Uncertainty in Artificial Intelligence (UAI), August 2022.
Yusuke Narita, Shota Yasui, and Kohei Yata. Efficient counterfactual learning from bandit feedback. In AAAI Conference on Artificial Intelligence, 2019.
Anthony O' Hagan. Monte carlo is fundamentally unsound. The Statistician, pages 247-249, 1987.

---

Harrie Oosterhuis and Maarten de Rijke. Taking the counterfactual online: Efficient and unbiased online evaluation for ranking. In International Conference on Theory of Information Retrieval, 2020.
Georg Ostrovski, Marc G. Bellemare, Aäron Oord, and Rémi Munos. Count-based exploration with neural density models. In International conference on machine learning, 2017.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems. 2019.
Brahma S. Pavse, Ishan Durugkar, Josiah P. Hanna, and Peter Stone. Reducing sampling error in batch temporal difference learning. In International Conference on Machine Learning. 2020.
Martin L. Puterman. Markov decision processes: discrete stochastic dynamic programming. John
Wiley & Sons, 2014.
Carl Edward Rasmussen and Zoubin Ghahramani. Bayesian monte carlo. In Advances in Neural Information Processing Systems, 2003.
Lukas Schäfer, Filippos Christianos, Josiah P. Hanna, and Stefano V. Albrecht. Decoupled rein- forcement learning to stabilise atrinsically-motiin motivated exploration. In International Conference on Autonomous Agents and Multiagent Systems, 2022.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 2017.
Pranab K. Sen and Julio M. Singer. Large Sample Methods in Statisties: An Introduction with Applications. Chapman & Hall, 1993.
Richard Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, 1998.
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, Xi Chen, Yan Duan, John Schulman, Filip De Turck, and Pieter Abbeel. # exploration: A study of count-based exploration for deep reinforcement learning. In Advances in neural information processing systems, 2017.
Philip S. Thomas and Emma Brunskill. Data-efficient off off-policy policy evaluation for reinforcement learning. In International Conference Machine Learning, 2016.
Aaron David Tucker and Thorsten Joachims. Variance-optimal augmentation logging for counterfac- tual evaluation in contextual bandits. arXiv preprint arXiv:2202.01721, 2022.
Ronald J. Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3):229-22 256,, 1992.
Martin Zinkevich, Michael Bowling, Nolan Bard, Morgan Kan, and Darse Billings. Optimal unbiased estimators for evaluating agent performance. In AAAI Conference Artificial Intelligence, 2006.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section i
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
Section
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
12

---

(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section
and Appendix B
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendices
and H
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material URL)? [Yes] Included in supplementary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section + and Appendices and +
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] Experiments use RL domains and algorithms that can be ran on a typical personal computer. Minimal compute resources required to reproduce any experiment in the paper.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No]
(c) Did you include any new assets either in the supplemental material or as a URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "rtdjn_jVBS4", "reviewer": "Reviewer_gCc9", "summary": "The authors propose a method of more efficient policy evaluation, that requires fewer samples from the environment relative to Monte Carlo sampling (running directly in environment), as well as an alternative baseline method BPG. The central idea of the paper is that a marginal log-likelihood loss can be treated as a gradient in the direction of executing actions that appear more often in evaluation trajectories seen so far. Therefore, the negative of the gradient can direct the policy in the direction of executing actions that have been seen less often, which causes our empirical action frequency to stay closer to the true distribution compared to sampling actions naively.\n\nThis approach is compared both assuming no existing episodes of interaction, and with episodes of interaction - if there is initial data then it is used to compute the gradient for future interactions in the environment / provide an initial set of episodes for averaging episode return.", "questions": "What do the authors see as potential paths for applying the problem to larger dimensional MDPs? It seems the core of this paper is whether we expect this to work in larger MDPs, because it is only in those MDPs where you need function approximation to work. But it is also in larger MDPs where we'd expect it to be difficult to adjust policy behavior by applying a small number of gradients to the policy.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The insight that the log-likelihood can be treated as a gradient in the direction of selecting rarer actions is interesting. I do have some concerns about the significance of the method. The method inherently relies on having the ability to sample enough on-policy trajectories to apply meaningful corrections to the current empirical distribution of episode trajectories. I would assume this requires a fairly substantial number of episodes as you try to apply the method to higher dimensional settings. It also seems like this approach becomes more data hungry as you increase the size of the existing initial data, because it will take more on-policy samples to apply the relevant corrections.\n\nThere is a theoretical justification of the approach, but the argument for it has some fairly strong cavaets - it is both based on a tabular policy, and requires using a learning rate of $\\alpha \\to \\infty$, such that ROS will always pick an action that is undersampled. This does give a sequence of random variables that strays from the true distribution less, but it's a pretty extreme argument and it's hard to see how this proof says anything about the continuous, non-tabular case with much smaller learning rates. It feels a good deal more extreme than other tabular RL proofs. Most of the time you can tell the proof will not work directly in a continuous setting, but you can see a vague throughline of how it could work assuming a nice enough function approximator. I don't see valid throughline if you need to start from assuming an infinite learning rate.\n\nAdditionally, I feel there are errors in the proof used. In the proof of Lemma 1 in Appendix B, the paper says\n\n\"The ROS update is given by $\\theta'_a = \\alpha(\\frac{\\theta}{\\alpha} - term)$. Taking the limit as $\\alpha \\to \\infty$ we see that $\\frac{\\theta}{\\alpha}$ is negligible and thus the parameter is $\\theta'_a = \\alpha(term)$\"\n\nI don't see why this step is justified, it relies on $\\lim_{\\alpha\\to\\infty} \\alpha \\cdot \\frac{\\theta}{\\alpha} = 0$, which is definitely not correct, we cannot cancel this term to 0 if it's getting multiplied by a term going to infinity.\n\nIn the proof of Theorem 2, the authors could also be clearer on why $Q_m$ can be treated as O(1) (because the n-th derivative of the KL-divergence at a fixed point $\\pi_e$ should still be constant with respect to number of data points $m$). In general it would have also been nicer if size of action space $|A|$ was in the bounds in some way, because this does matter to the convergence rate if we wished to apply this method to different MDPs.\n\n(I suspect that although the proofs have holes, the general results are still correct.)\n\nThe method does outperform BPG asymptotically - my concern is that by the time the asymptotics show up, you are already collecting enough on-policy episodes to make the difference not very applicable. Almost all results are in discrete domains with learning rates $\\alpha = 10$ to $10^4$ and the results in the one continuous problem with reasonable learning rate (CartPoleContinuous) did not look as exciting.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "lhxWQ5g7u-k", "reviewer": "Reviewer_cwVN", "summary": "The authors identify a deficiency in on-policy data collection for policy evaluation; when data are sampled i.i.d., new samples do not take into consideration the possible bias of the previous samples. The authors propose adaptive, *off-policy* sampling as a means to actively correct for this bias in a feedback-based manner. Because computing the exact policy for the bias correction is not feasible when using function approximation, the authors propose Robust On-policy Sampling (ROS), which iteratively perturbs a stochastic policy via gradient ascent to iteratively approximate the required sampling policy. The authors prove some convergence results for their method and demonstrate that it can reduce the expected mean squared error (MSE) for policy evaluation in several low-dimensional control tasks.", "questions": "1. Is there a possible relationship between the theoretical KL divergence bound in Theorem 2 and the expected, empirical MSE? I understand that, intuitively, a lower KL divergence would generally lead to a lower MSE in practice, but as it stands now, Theorem 2 seems to be relatively disconnected from the empirical results of the paper. I would be willing to raise my score if the authors can strengthen the connection between theory and practice here (e.g., possibly by relaxing/removing Assumption 1).\n1. More of a suggestion than a question: Do you think an adaptive gradient method (e.g., RMSProp, Adam) might help mitigate some of the hyperparameter sensitivity observed in Section 6.3?\n", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- The authors consider an interesting and relevant problem for on-policy evaluation: Given a batch of previously collected (possibly biased) on-policy data, what *off-policy* sampling strategy should be employed to produce better estimates of the *on-policy* expected returns under the target policy $\\pi$? As the paper correctly points out, simply sampling more i.i.d. data using the target policy is a suboptimal strategy.\n- The proposed algorithm ROS is an intuitive solution to the above problem. Given that some actions may be underrepresented in the past, it makes sense that their probabilities should be slightly increased in the future. Using gradient ascent on a stochastic policy is an elegant way to do this without requiring the explicit calculation of an analytical solution, which is crucial for non-tabular environments.\n- The empirical performance of the proposed method appears to be favorable when compared to a variety of baselines, although I am not familiar enough with the related work to determine the relative strengths of the baselines.\n- Overall, the paper is very well written.\n\n**Weaknesses**\n- Some of the theoretical results are somewhat weak:\n  - Proposition 1, which states that pooling two i.i.d. datasets together is biased unless the first dataset is unbiased, seems obvious and unnecessary; of course, if the first dataset's mean is wrong, then it would require an infinite amount of additional sampling to counteract its bias.\n  - Assumption 1 (the MDP is a directed acyclic graph) is a very strong assumption that I think would rarely be satisfied in practice.\n  - Theorem 1 establishes the consistency of the ROS estimator. However, the i.i.d. on-policy estimator (which the paper claims is inferior) is also a consistent estimator! I find this confusing, because the main thesis of the paper is that a consistent estimator (i.e., i.i.d. on-policy sampling) is, alone, not sufficient for good performance with finite trajectories. Having consistency/convergence as a theorem therefore seems to overstate its importance; perhaps it would be better as a lemma to Theorem 2?\n- I was a bit disappointed to see that the main convergence result (Theorem 2) provides a stochastic bound on the KL divergence between the maximum-likelihood policy $\\pi_D$ and the true policy $\\pi$, rather than the policy-evaluation MSE. As far as I understood, the authors’ claim in the abstract/introduction is that ROS should lead to lower MSE. Although this is shown empirically, which is great, the paper would be much stronger if the theory also supported this claim. In my opinion, it is not as interesting that ROS is able to estimate the policy $\\pi$ with high accuracy, but more so that, by doing this, it can achieve more-accurate estimates of $V^\\pi$ or $Q^\\pi$.\n- The tested environments are relatively small, comprising a bandit, gridworld, and two cartpole variations. I think adding at least one high-dimensional environment – even if it were just one Atari game or the like – would make the experiments much more convincing. At present, it is hard to gauge how scalable the results are, even though the ROS algorithm itself looks scalable.\n\n**Minor Edits**\n- Line 122: “is ran” $\\rightarrow$ “is run.”\n- Line 176: “can be ran” $\\rightarrow$ “can be run.”\n- Line 191: Should it be $\\theta \\in \\mathbb{R}^d$, not $\\theta \\subseteq \\mathbb{R}^d$?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MAhVDoVyXE5", "reviewer": "Reviewer_cYQz", "summary": "In this work, authors attempt to improve sample efficiency as well as accuracy of Monte-Carlo policy evaluation by an interplay between on-policy and off-policy data collection. The key idea being on-policy sampling may not guarantee exact policy state-action visitiation distribution in finite interactions. This could be corrected by doing off-policy sampling while tracking the visitation distribution to ensure on-policy state-action density distribution. To elaborate, they collect some data using on-policy sampling, thereafter, they create a new behavior policy with higher likelihood of under-sampled actions. \n\nTheir method of “Robust On-policy Sampling (ROS)”  covers larger MDPs by assuming parametrized and differential behavior policy representation. This policy is adjusted via gradient descent to increase probabilities for low-sampled actions. \n", "questions": "I would recommend authors to evaluate their method over  Atari or Gym-based mujoco environments. This might show significant improvement in optimal policy convergence in those cases which are generally sample inefficient.\n\nAlso, can your work be adopted to deterministic parameterized policies?", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: Authors attempt to improve Monte-Carlo accuracy and sample efficiency in a novel way. They do have classic baselines as well enough coverage of related work.\n\nQuality: Yes, the proposal is technically reasonable. They also provide theoretical analysis and show experimental results in simpler environments to build their case. Authors did show sensitivity of their method to step-size(hyper-parameter)\n\nClarity: Yes, the paper is well written and requires minor corrections only\n\n- PE notation is not defined in eq. (1) \n- MC notation is also not defined in eq. (2)\n\nSignificance: Authors open up an interesting problem space and the suggested ideas could be borrowed by others. However, the experiments done by authors are in simpler environments, where significant improvements are only found in Gridworld environment with discrete space. This dilutes the practical importance of the method.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "8Ifj9HhnNG", "reviewer": "Reviewer_C33h", "summary": "The paper proposes using non-i.i.d. off-policy sampling to improve the efficiency of on-policy RL algorithms.\nSpecifically, it suggests using a behaviour policy that takes into account past actions to choose future actions to cause the observed data to more closely match the on-policy distribution than simply relying on the law of large numbers.\nThe paper then presents theoretical and empirical support for the proposed approach.", "questions": "1. The definition of a policy is that of a Markov policy, but the paper proposes using a behaviour policy that takes into account more information than just the current state/features.\n1. Why does ROS only take into account immediate sampling error, and not sampling error in future states via TD-like bootstrapping? Is it unlikely to make a big difference for the extra complication? Could this drag the behaviour policy further away from the on-policy state distribution?\n1. The figures are very small, and some of the colours are quite similar. I would suggest making the figures larger, possibly by using a shared Y axis. Also consider changing the colours, bolding the lines, and/or using arrows and labels instead of a legend to reduce the reliance on colour to tell which algorithm is which.\n1. In Figure 2, how is the policy evaluated? Monte Carlo?\n1. Would ROS work with a changing target policy?\n\n### Minor suggestions:\n- line 33: \"upmost\" should be \"utmost\"", "limitations": "Yes, the paper adequately addressed the limitations and societal impact of the proposed algorithm.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Originality\nTo the best of my knowledge, the proposed algorithm and contributions are new.\n\n### Quality\nThe paper seems very well-done. I don't have any complaints about quality.\n\n### Clarity\nThe paper is written very clearly, with intuitive examples provided to communicate important points to the reader. I was pleasantly surprised by how readable the paper is.\n\n### Significance\nThe proposed strategy tackles an important problem: the poor sample efficiency of on-policy algorithms. It also seems very general, and therefore could be quite significant.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept