Data-Efficient Policy Evaluation Through Behavior Policy Search

Josiah P. HannaYash ChandakPhilip S. ThomasMartha WhitePeter StoneScott Niekum

article2024JMLR53 citations

Develops algorithms that search for an optimal data-collection behavior policy to evaluate reinforcement learning policies with lower variance and mean squared error than standard on-policy rollouts.

Listen

Accurately evaluating decision-making policies before live deployment is a vital challenge across high-stakes domains such as healthcare, automated marketing, and robotics. The standard industry practice, known as on-policy evaluation, directly executes the target policy in the environment to observe outcomes. However, this approach is often data-ineﬃcient and suﬀers from high variance—meaning it requires large, costly sample sizes to produce stable performance estimates. While using an alternate data-collection strategy (off-policy evaluation) has historically been viewed as higher variance, the article demonstrates that intentionally choosing a different data-collection policy can significantly reduce evaluation error.

The article's main objective is to formalize the behavior policy search problem and demonstrate that actively searching for and deploying an optimized data-collection policy yields lower mean squared error than standard on-policy evaluation, without sacrificing statistical unbiasedness.

The authors evaluated their approach through formal mathematical proofs alongside empirical simulations spanning discrete environments and complex continuous control benchmarks, including Cart Pole, Acrobot, and Hopper. The analysis derived the theoretical form of a minimal-variance data-collection policy and introduced two practical optimization algorithms: Behavior Policy Gradient on the Variance (which directly minimizes estimator variance via gradient descent) and Behavior Policy Gradient on the Kullback-Leibler Divergence (which minimizes the divergence between the current data-collection policy and the theoretical optimum). The framework was evaluated across tabular and continuous domains, parameter sensitivity sweeps, and combinations with predictive model control variates.

The investigation produced four central findings. First, despite data points being collected sequentially across changing data-collection policies, the resulting estimates remain strictly unbiased, statistically consistent, and uncorrelated. Second, both proposed search algorithms consistently reduced estimation error compared to standard on-policy Monte Carlo roll-outs, lowering mean squared error by up to an order of magnitude across both discrete and continuous domains. Third, the potential for error reduction is highest when the target policy has high variance or when critical high-reward outcomes are rare under normal execution; actively sampling those rare, high-impact paths dramatically reduces total estimation variance. Finally, combining behavior policy search with predictive environment models (doubly robust estimation) achieved an additional 56.9% error reduction over standard model-assisted baselines.

These results demonstrate that organizations can achieve substantially more reliable policy evaluations using fewer physical or simulated trials, directly mitigating the costs and risks of deploying poorly evaluated strategies. This finding challenges the conventional belief that on-policy data collection is always superior when feasible. Instead, deliberately steering exploration toward rare, high-magnitude scenarios yields faster convergence and greater precision.

Decision-makers and engineering teams should adopt behavior policy search in environments where on-policy outcomes exhibit high variance or rare high-impact events, provided the operational platform permits minor computational overhead during data collection. When applying these methods, teams should utilize gradient baselines to stabilize learning rates and consider incorporating model-based control variates when environment models are available. Further engineering exploration should examine extensions to multi-policy evaluation and safe exploration constraints.

Confidence in these findings is supported by theoretical convergence proofs and consistent performance across diverse benchmark tasks. However, practitioners should note key limitations: the methods require careful step-size tuning to avoid unstable optimization steps, and behavior policy search yields minimal benefit if policy outcomes are near-deterministic or if variance originates entirely from uncontrollable environmental dynamics rather than the policy's actions.

Alberta Machine Intelligence Institute Sony Corporation University of Alberta University of Massachusetts Amherst University of Texas at Austin University of Wisconsin Madison mdp mean square error policy evaluation data-efficient policy evaluation behavior policy search unbiased off-policy policy evaluation

arXiv: 1706.03469

Paper: Policy Gradient Methods for Reinforcement Learning with Function Approximation, Richard S. Sutton et al. (1999). The policy-gradient theorem provides the foundation for understanding how the source optimizes a behavior policy by following gradients of its evaluation variance.

Paper: Additive Control Variates Dominate Self-Normalisation in Off-Policy Evaluation, Olivier Jeunen et al. (2026). It continues the source’s effort to reduce off-policy evaluation error by deriving additive control-variate estimators that can improve on standard variance-reduction approaches.

Cover for Data-Efficient Policy Evaluation Through Behavior Policy Search

Abstract

We consider the task of evaluating a policy for a Markov decision process (MDP). The standard unbiased technique for evaluating a policy is to deploy the policy and observe its performance. We show that the data collected from deploying a different policy, commonly called the behavior policy, can be used to produce unbiased estimates with lower mean squared error than this standard technique. We derive an analytic expression for a minimal variance behavior policy – a behavior policy that minimizes the mean squared error of the resulting estimates. Because this expression depends on terms that are unknown in practice, we propose a novel policy evaluation sub-problem, behavior policy search: searching for a behavior policy that reduces mean squared error. We present two behavior policy search algorithms and empirically demonstrate their effectiveness in lowering the mean squared error of policy performance estimates.1

Topics

mdp mean square error policy evaluation

Keywords

data-efficient policy evaluation behavior policy search unbiased off-policy policy evaluation minimal-variance behavior policy importance sampling linear-softmax policy reinforcement learning Markov decision processes

1. Introduction
2. Background
2.1 Notation
2.2 Batch Policy Evaluation
2.3 Monte Carlo Batch Policy Evaluation
2.4 Importance Sampling Policy Evaluation
3. Related Work
3.1 Adaptive Importance Sampling
3.2 Variance Reduction for Policy Evaluation
4. The Behavior Policy Search Problem
4.1 Motivating Off-Policy Sampling for Lower Variance Importance Sampling
4.2 The Behavior Policy Search Problem
4.3 Statistical Properties of Behavior Policy Search Estimates
5. Behavior Policy Gradient on the Variance
6. Behavior Policy Gradient on the KL-Divergence
7. Interpreting BPG-V and BPG-KL Updates
8. Behavior Policy Search for Importance Sampling Extensions
8.1 Baselined Importance Sampling
8.2 Doubly Robust and Per-Decision Importance Sampling
8.3 Weighted Importance Sampling
9. Empirical Study
9.1 Empirical Set-up
9.2 Main Results
9.2.1 Grid World
9.2.2 Control Tasks
9.3 Control Variate Extension Results
9.4 Rareness of Event Study
10. Discussion
When to Perform Behavior Policy Search?
11. Future Work
11.1 Evaluating Multiple Evaluation Policies
11.2 Behavior Policy Search for Value Function Learning
11.3 Behavior Policy Search for Policy Improvement
11.4 Theoretical Variance Reduction
12. Conclusion
Acknowledgments
References
Appendix A. Statistical Properties of Behavior Policy Search Estimates
Appendix B. Behavior Policy Gradient of the Variance
B.1 MSE Gradient for an Unbiased Off-Policy Policy Evaluation Method
B.2 Behavior Policy Gradient of the Variance
B.3 MSE Gradient for the Doubly Robust Estimator
Appendix C. Convergence of BPG-V
Appendix D. Convexity of Variance Objective
Appendix E. Minimal-Variance Behavior Policy
Appendix F. Behavior Policy Gradient of the KL
Appendix G. Convergence of BPG-KL
Appendix H. Convexity of KL-Divergence Objective

Knowls

Knowl 1 — Behavior policy search for unbiased batch policy evaluation
definition
Let $\pi_e=\pi_{\theta_e}$ be a fixed evaluation policy in a finite-horizon episodic MDP, and let $v(\pi_e)$ be its expected discounted return. At iteration $i$ , behavior policy search (BPS) chooses a behavior policy $\pi_{\theta_i}$ using previously collected data, samples a trajectory $H_i\sim\pi_{\theta_i}$ , and computes an unbiased off-policy estimate $X_i=\operatorname{OPE}(\pi_e,H_i,\pi_{\theta_i})$ . The estimate after $n$ trajectories is the average $\overline X_n=n^{-1}\sum_{i=1}^{n}X_i$ . The initial behavior policy is the evaluation policy, $\theta_0=\theta_e$ . A BPS solution is a behavior policy whose off-policy estimate has lower mean squared error (MSE) than the on-policy estimate; for unbiased estimators, this is equivalent to lower variance. The algorithms in the paper optimize the current estimate’s accuracy, rather than accounting for how a behavior-policy choice may affect the quality of later choices.
Knowl 2 — Sufficient condition for a minimal-variance behavior policy
theoretical result
In a finite-horizon MDP, let $h=(s_0,a_0,r_0,\ldots,s_{l-1},a_{l-1},r_{l-1})$ be a trajectory, let $g(h)=\sum_{t=0}^{l-1}\gamma^t r_t$ be its discounted return, and define $w_\pi(h)=\prod_{t=0}^{l-1}\pi(a_t\mid s_t)$ for policy $\pi$ . Suppose the evaluation policy $\pi_e$ has nonzero probability of generating at least one trajectory with nonzero return. If a policy $\pi_b^*$ satisfies
$w_{\pi_b^*}(h)=\frac{|g(h)|w_{\pi_e}(h)}{\mathbb{E}[|g(H)|\mid H\sim\pi_e]}\qquad\text{for every trajectory }h,$
then $\pi_b^*$ minimizes the variance of the ordinary importance-sampling return among behavior policies. Equivalently, the target trajectory distribution assigns probability proportional to $\Pr(H=h\mid\pi_e)|g(h)|$ . This condition is sufficient; a Markov policy in a restricted parameterized family need not be able to realize the required trajectory distribution.
Knowl 3 — BPG-V minimizes importance-sampling variance directly
algorithm
Let $\pi_e$ be the evaluation policy, $\pi_\theta$ a differentiable behavior policy, and $H$ a trajectory sampled under $\pi_\theta$ . Write its discounted return as $g(H)=\sum_{t=0}^{l-1}\gamma^tR_t$ , its importance-sampling return as $I(H,\theta)=g(H)\prod_{t=0}^{l-1}\frac{\pi_e(A_t\mid S_t)}{\pi_\theta(A_t\mid S_t)}$ , and its policy score as $S_\theta(H)=\sum_{t=0}^{l-1}\nabla_\theta\log\pi_\theta(A_t\mid S_t)$ . Under the paper’s support and differentiability assumptions, the gradient of the single-trajectory importance-sampling MSE is
$\nabla_\theta\operatorname{MSE}[I(H,\theta)]=-\mathbb{E}_{H\sim\pi_\theta}[I(H,\theta)^2S_\theta(H)].$
BPG-V estimates this gradient with batches and takes a stochastic gradient-descent step. Because the gradient has a negative sign, the parameter update adds the estimated squared importance-sampled return times the score. The algorithm begins with $\theta_0=\theta_e$ and reports the mean importance-sampling estimate over all collected trajectories.
Input: Evaluation parameters $\theta_e$ , batch size $k$ , step sizes $\alpha_i$ , and number of updates $n$
Initialize $\theta_0 \leftarrow \theta_e$ and an empty trajectory data set $D$
For $i=0,\ldots,n-1$
    Sample $k$ trajectories $H_{i,j}\sim\pi_{\theta_i}$ , for $j=1,\ldots,k$
    Add the $k$ trajectories and their behavior-policy parameters to $D$
    For each trajectory compute $I_{i,j}=g(H_{i,j})\prod_t\pi_e(A_t\mid S_t)/\pi_{\theta_i}(A_t\mid S_t)$
    For each trajectory compute $S_{i,j}=\sum_t\nabla_\theta\log\pi_{\theta_i}(A_t\mid S_t)$
    Update $\theta_{i+1}\leftarrow\theta_i+(\alpha_i/k)\sum_{j=1}^k I_{i,j}^2S_{i,j}$
Return $\theta_n$ and the mean importance-sampling return over all trajectories in $D$
Knowl 4 — BPG-KL searches toward the minimum-variance trajectory distribution
algorithm
Let $\pi_e$ be the evaluation policy and $\pi_\theta$ a behavior policy. The minimum-variance target trajectory distribution has probability $q^*(h)=\Pr(H=h\mid\pi_e)|g(h)|/\mathbb{E}[|g(H)|\mid H\sim\pi_e]$ , where $g(h)$ is the discounted return. BPG-KL adjusts the behavior policy to reduce $D_{\mathrm{KL}}(q^*\,\|\,\Pr(H\mid\pi_\theta))$ . Defining $I(H,\theta)=g(H)\prod_{t=0}^{l-1}\pi_e(A_t\mid S_t)/\pi_\theta(A_t\mid S_t)$ and $S_\theta(H)=\sum_{t=0}^{l-1}\nabla_\theta\log\pi_\theta(A_t\mid S_t)$ , an expression proportional to the KL gradient is
$-\mathbb{E}_{H\sim\pi_\theta}[|I(H,\theta)|S_\theta(H)].$
Thus BPG-KL initializes at $\theta_e$ , collects batches of $k$ trajectories under the current behavior policy, and updates $\theta$ by adding a step-size times the batch average of $|I|S_\theta$ . It returns the importance-sampling mean over all collected trajectories. The target distribution may not be representable by the behavior-policy family; consequently, minimizing this KL objective does not by itself guarantee that the resulting behavior policy has lower importance-sampling variance than on-policy sampling.
Knowl 5 — Adaptive behavior policies preserve guarantees without independent, identically distributed samples
theoretical result
Suppose each off-policy estimate $X_i=\operatorname{OPE}(\pi_e,H_i,\pi_{\theta_i})$ is unbiased for $v(\pi_e)$ for every fixed behavior policy and is bounded in a common interval of width $C$ . The behavior policy for the next sample may be selected adaptively from past data. Then the average $\overline X_n=n^{-1}\sum_{i=1}^nX_i$ remains unbiased, and estimates from distinct iterations are pairwise uncorrelated even though they need not be independent or identically distributed. The average converges in probability to $v(\pi_e)$ ; moreover, for $\delta\in(0,1]$ ,
$\Pr\!\left(|\overline X_n-v(\pi_e)|>C\sqrt{\frac{\ln(2/\delta)}{2n}}\right)\leq\delta.$
For ordinary importance sampling, bounded rewards and a uniformly bounded evaluation-to-behavior action-probability ratio ensure bounded estimates under the paper’s support assumption. The concentration bound depends on the range of the estimates, which may grow under off-policy sampling; it can therefore be looser than the on-policy bound even when behavior search lowers variance and MSE.
Knowl 6 — Convergence and convexity under linear-softmax policies
theoretical result
For BPG-V and BPG-KL, assume the evaluation policy’s action probabilities are supported by every behavior policy and use stochastic-gradient step sizes $\alpha_i$ satisfying $\sum_{i=0}^{\infty}\alpha_i=\infty$ and $\sum_{i=0}^{\infty}\alpha_i^2<\infty$ . Under the paper’s differentiability and boundedness assumptions, BPG-V’s importance-sampling MSE objective and BPG-KL’s trajectory-distribution KL objective each converge to a finite value, and the corresponding objective gradient tends to zero.

If the behavior policy is linear-softmax, with finite action set $\mathcal A$ , state features $\phi(s)$ , and action parameters $\theta_a$ , so that $\pi_\theta(a\mid s)=\exp(\theta_a^\top\phi(s))/\sum_{b\in\mathcal A}\exp(\theta_b^\top\phi(s))$ , both objectives are convex in $\theta$ . Under the stated convergence conditions, the resulting minima are global within that policy family. Since $\pi_e$ is in the optimized family, the global BPG-V minimum has no greater importance-sampling variance than on-policy sampling. For BPG-KL, a global minimum means the closest representable trajectory distribution in KL, not necessarily a minimum-variance behavior policy.
Knowl 7 — Behavior-policy search extends to unbiased estimators with baselines and control variates
model/method
The behavior-policy gradient approach can be applied beyond ordinary importance sampling when the off-policy estimator is unbiased and its dependence on the behavior-policy parameters is included in the gradient. For a differentiable unbiased estimator $O(H,\theta)$ , the MSE gradient has the form $\mathbb{E}_{H\sim\pi_\theta}[O(H,\theta)^2\nabla_\theta\log\Pr(H\mid\pi_\theta)+\nabla_\theta O(H,\theta)^2]$ ; the second term accounts for explicit dependence of the estimator on $\theta$ .

For a constant baseline $b$ , ordinary importance sampling can estimate $v(\pi_e)$ as $b+g(H)\prod_t[\pi_e(A_t\mid S_t)/\pi_\theta(A_t\mid S_t)]-b\prod_t[\pi_e(A_t\mid S_t)/\pi_\theta(A_t\mid S_t)]$ . It remains unbiased, and the baseline can reduce off-policy variance when it is close to $v(\pi_e)$ . The paper also derives behavior-policy gradients for per-decision importance sampling and the doubly robust (DR) estimator. DR uses approximate target-policy state- and action-value functions as a control variate; its gradient must account for dependence and covariance among its time-indexed terms. A minimal-variance behavior-policy characterization for DR is not established in the paper.
Knowl 8 — BPG-V and BPG-KL reduce policy-evaluation MSE across tabular and continuous-control tasks
empirical result
The main comparison evaluated BPG-V and BPG-KL against on-policy Monte Carlo (MC). In the tabular Grid World, batches contained 100 trajectories and results averaged 100 trials of 1,000 iterations. The evaluation policies were an early, partially trained policy $\pi_1$ and a converged policy $\pi_2$ . For $\pi_1$ , both search methods reduced MSE by up to an order of magnitude relative to MC; for $\pi_2$ , the improvement was more modest. In a final comparison using 100 trajectories from the learned behavior policy, MSE was lower than 100-trajectory on-policy MC by 73.52% (BPG-V) and 77.78% (BPG-KL) for $\pi_1$ , and by 64.6% (BPG-V) and 46.28% (BPG-KL) for $\pi_2$ . The two methods performed similarly overall.

On Cart Pole Swing Up, Acrobot, Cart Pole, and Hopper, the experiments used batches of 500 trajectories, 200 behavior-policy updates, and averages over 100 trials. Both BPG methods reduced MSE faster than MC and showed similar performance, including on tasks with continuous states or actions. An additional rare-event Grid World experiment found larger variance improvements when the evaluation policy rarely selected a high-reward terminal action; improvement diminished as the event became common and the initial on-policy variance fell.
Knowl 9 — Combining BPG-V with a model-based control variate can further lower MSE
empirical result
The paper compared doubly robust behavior-policy gradient search (DR-BPG) with an on-policy doubly robust estimator, called the advantage-sum estimator (ASE), in a stochastic $10\times10$ Grid World. The agent moved in its intended direction with probability $0.9$ and otherwise moved left or right with equal probability. Models were either updated using all collected trajectories or estimated from the first 10 iterations and then held fixed; behavior search with the fixed model began at iteration 10. With the fixed model, DR-BPG had the lowest MSE among the compared methods. Using the final learned behavior policy and 100 trajectories, DR-BPG reduced MSE by 56.9% relative to ASE with the same model. When the model was continually updated, DR-BPG was competitive with ASE but not statistically significantly better. The authors note that changing the model changes the variance objective and leaves convergence without the fixed-objective guarantee.
Knowl 10 — Estimator choice and optimization settings constrain practical gains
limitation
Behavior-policy search does not guarantee improvement at every update: noisy gradient estimates or a poorly chosen step size can move to a higher-variance behavior policy, and the paper’s Grid World step-size ablation showed possible divergence at very large step sizes ( $\alpha=5$ or $10$ ). The method also adds computation, relies on the support condition needed for importance sampling, and is studied for finite-horizon episodic, fully observable environments. The authors recommend it especially when on-policy return variance is expected to be high; little improvement may be available when the evaluation policy is deterministic or near-uniform, or when variance is largely environmental rather than action-dependent.

Optimizing behavior for ordinary importance sampling can also hurt a different estimator. In a two-arm bandit with rewards 100 and 1 and evaluation probability $\theta_e=0.1$ of selecting the high-reward arm, the minimum-variance behavior parameter for ordinary importance sampling is approximately $\theta_b^*=0.917$ . With datasets of 50 samples averaged over 500 repetitions, weighted/self-normalized importance sampling MSE rose for $\theta>0.5$ even as ordinary importance-sampling MSE continued to fall. The best behavior-policy search strategy for weighted importance sampling is left open.

Coverage note — Proofs and derivations, full parameter-ablation curves, and secondary plot details are omitted because they support the stated results but do not add separate load-bearing contributions beyond the guarantees and empirical findings captured here.

References

1.A. Agarwal, N. Jiang, S. M. Kakade, and W. Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, 2019.
2.T. I. Ahamed, V. S. Borkar, and S. Juneja. Adaptive importance sampling technique for Markov chains using stochastic approximation. Operations Research, 54(3):489–504, 2006.
3.O. D. Akyildiz and J. Míguez. Convergence rates for optimised adaptive importance samplers. Statistics and Computing, 31:1–17, 2021.
4.T. Archibald, K. McKinnon, and L. Thomas. On the generation of markov decision processes. Journal of the Operational Research Society, 46(3):354–361, 1995.
5.S. M. R. Arnold, P. L’Ecuyer, L. Chen, Y.-f. Chen, and F. Sha. Policy Learning and Evaluation with Randomized Quasi-Monte Carlo. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), 2022.
6.K. D. Asis, J. F. Hernandez-Garcia, G. Z. Holland, and R. S. Sutton. Multi-step reinforcement learning: A unifying algorithm, 2017.
7.K. Azuma. Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, Second Series, 19(3):357–367, 1967.
8.M. Bastani. Model-free intelligent diabetes management using machine learning. Master’s thesis, Department of Computing Science, University of Alberta, 2014.
9.D. P. Bertsekas and J. N. Tsitsiklis. Gradient convergence in gradient methods with errors. SIAM Journal on Optimization, 10:627–642, 2000.
10.G. Bouchard, T. Trouillon, J. Perez, and A. Gaidon. Online learning to sample. arXiv preprint arXiv:1506.09016, 2016.
11.S. Boyd, S. P. Boyd, and L. Vandenberghe. Convex optimization. Cambridge university press, 2004.
12.G. Brockman, V. Cheung, L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba. OpenAI gym. arXiv preprint arXiv:1606.01540, 2016.
13.K. Ciosek and S. Whiteson. OFFER: Off-environment reinforcement learning. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), 2017.
14.N. Corrado and J. P. Hanna. On-Policy Policy Gradient Reinforcement Learning Without On-Policy Sampling. Arxiv Pre-Print, 2023.
15.E. Coumans and Y. Bai. Pybullet, a python module for physics simulation for games, robotics, and machine learning. http://pybullet.org, 2016–2019.
16.P. Y. Desai and P. W. Glynn. Simulation in optimization and optimization in simulation: A Markov chain perspective on adaptive Monte Carlo algorithms. In Proceedings of the 33rd conference on Winter simulation, pages 379–384. IEEE Computer Society, 2001.
17.Y. Duan, X. Chen, R. Houthooft, J. Schulman, and P. Abbeel. Benchmarking deep reinforcement learning for continuous control. In Proceedings of the 33rd International Conference on Machine Learning, 2016.
18.J. Frank, S. Mannor, and D. Precup. Reinforcement learning in the presence of rare events. In Proceedings of the 25th International Conference on Machine Learning, pages 336–343. ACM, 2008.
19.C. Gelada and M. G. Bellemare. Off-policy deep reinforcement learning by bootstrapping the covariate shift. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3647–3655, 2019.
20.Z. D. Guo, P. S. Thomas, and E. Brunskill. Using options and covariance testing for long horizon off-policy policy evaluation. In Proceedings of the 31st Conference on Advances in Neural Information Processing Systems (NeurIPS), 2017.
21.A. Hallak and S. Mannor. Consistent on-line off-policy evaluation. In Proceedings of the 34th International Conference on Machine Learning, pages 1372–1383, 2017.
22.J. Hammersley and D. Handscomb. Monte Carlo methods. Ltd., London, page 40, 1964.
23.J. P. Hanna, P. Thomas, P. Stone, and S. Niekum. Data-efficient policy evaluation through behavior policy search. In Proceedings of the 34th International Conference on Machine Learning (ICML), 2017.
24.J. P. Hanna, S. Niekum, and P. Stone. Importance sampling in reinforcement learning with an estimated behavior policy. Machine Learning, pages 1–51, 2021.
25.N. Jiang and L. Li. Doubly robust off-policy evaluation for reinforcement learning. In Proceedings of the 33rd International Conference on Machine Learning (ICML), 2016.
26.S. Kakade. A natural policy gradient. In Proceedings of the 14th Conference on Advances in Neural Information Processing Systems (NeurIPS), volume 14, pages 1531–1538, 2001.
27.M. Kearns and S. Singh. Near-optimal reinforcement learning in polynomial time. Machine Learning, 49(2-3):209–232, 2002.
28.C. Lemieux. Control variates. Wiley StatsRef: Statistics Reference Online, pages 1–8, 2014.
29.T. P. Lillicrap, J. J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, and D. Wierstra. Continuous control with deep reinforcement learning. CoRR, abs/1509.02971, 2015.
30.Q. Liu, L. Li, Z. Tang, and D. Zhou. Breaking the curse of horizon: Infinite-horizon off-policy estimation. In Advances in Neural Information Processing Systems (NeurIPS), volume 31, pages 5356–5366, 2018.
31.S. Liu and S. Zhang. Improving Monte Carlo Evaluation with Offline Data. In Proceedings of the International Conference on Machine Learning (ICML), 2024.
32.A. R. Mahmood, H. P. van Hasselt, and R. S. Sutton. Weighted importance sampling for off-policy learning with linear function approximation. In Advances in Neural Information Processing Systems, pages 3014–3022, 2014.
33.S. Mukherjee, J. P. Hanna, and R. Nowak. ReVar: Strengthening Policy Evaluation via Reduced Variance Sampling. In Proceedings of the 38th International Conference on Uncertainty in Artificial Intelligence (UAI), 2022.
34.S. Mukherjee, J. P. Hanna, and R. Nowak. SaVeR: Optimal Data Collection Strategy for Safe Policy Evaluation in Tabular MDP. In Proceedings of the International Conference on Machine Learning (ICML), 2024a.
35.S. Mukherjee, Q. Xie, J. P. Hanna, and R. Nowak. SPEED: Experimental Design for Policy Evaluation in Linear Heteroscedastic Bandits. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), 2024b.
36.M. Mutný, T. Janik, and A. Krause. Active Exploration via Experiment Design in Markov Chains. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), 2023.
37.A. B. Owen. Monte Carlo theory, methods and examples. 2013.
38.J. Peters and S. Schaal. Natural actor-critic. Neurocomputing, 71(7-9):1180–1190, 2008.
39.B. Piot, M. Geist, and O. Pietquin. Difference of convex functions programming for reinforcement learning. Advances in Neural Information Processing Systems, 27, 2014.
40.T. Popoviciu. Sur les équations algébriques ayant toutes leurs racines réelles. Mathematica, 9:129–145, 1935.
41.D. Precup, R. S. Sutton, and S. Singh. Eligibility traces for off-policy policy evaluation. In Proceedings of the 17th International Conference on Machine Learning (ICML), pages 759–766, 2000.
42.M. L. Puterman. Markov decision processes: Discrete stochastic dynamic programming. John Wiley & Sons, 2014.
43.H. Robbins and S. Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400–407, 1951.
44.R. Y. Rubinstein and D. P. Kroese. Simulation and the Monte Carlo method, volume 10. John Wiley & Sons, 2016.
45.J. Schulman, S. Levine, P. Moritz, M. Jordan, and P. Abbeel. Trust region policy optimization. In Proceedings of the 32nd International Conference on Machine Learning (ICML), 2015.
46.J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
47.P. K. Sen and J. M. Singer. Large Sample Methods in Statistics: An Introduction with Applications. Chapman & Hall, 1993.
48.S. P. Singh and R. S. Sutton. Reinforcement learning with replacing eligibility traces. Machine Learning, 22(1-3):123–158, 1996.
49.A. L. Strehl, L. Li, and M. L. Littman. Reinforcement learning in finite MDPs: PAC analysis. Journal of Machine Learning Research, 10:2413–2444, 2009.
50.R. S. Sutton. Learning to predict by the methods of temporal differences. Machine Learning, 3(1):9–44, 1988.
51.R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT Press, 2018.
52.R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour. Policy gradient methods for reinforcement learning with function approximation. In Proceedings of the 13th Conference on Advances in Neural Information Processing Systems (NeurIPS), 2000.
53.R. S. Sutton, J. Modayil, M. Delp, T. Degris, P. M. Pilarski, A. White, and D. Precup. Horde: A scalable real-time architecture for learning knowledge from unsupervised sensorimotor interaction. In The 10th International Conference on Autonomous Agents and Multiagent Systems-Volume 2, pages 761–768, 2011.
54.A. Swaminathan and T. Joachims. The self-normalized estimator for counterfactual learning. In Proceedings of the 29th Conference on Advances in Neural Information Processing Systems (NeurIPS), pages 3231–3239, 2015.
55.G. Theocharous, P. S. Thomas, and M. Ghavamzadeh. Personalized ad recommendation systems for life-time value optimization with guarantees. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), pages 1806–1812, 2015.
56.P. S. Thomas. Safe reinforcement learning. PhD thesis, University of Massachusetts Libraries, 2015.
57.P. S. Thomas and E. Brunskill. Data-efficient off-policy policy evaluation for reinforcement learning. In Proceedings of the 33rd International Conference on Machine Learning (ICML), 2016.
58.P. S. Thomas and E. Brunskill. Importance sampling with unequal support. In Thirty-first AAAI conference on artificial intelligence, 2017.
59.P. S. Thomas, G. Theocharous, and M. Ghavamzadeh. High confidence off-policy evaluation. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2015a.
60.P. S. Thomas, G. Theocharous, and M. Ghavamzadeh. High confidence policy improvement. In Proceedings of the 32nd International Conference on Machine Learning (ICML), 2015b.
61.J. Veness, M. Lanctot, and M. Bowling. Variance reduction in Monte-Carlo tree search. In Proceedings of the 24th Conference on Advances in Neural Information Processing Systems (NeurIPS), pages 1836–1844, 2011.
62.R. Wan, B. Kveton, and R. Song. Safe Exploration for Efficient Policy Evaluation and Comparison. In Proceedings of the International Conference on Machine Learning (ICML), 2022.
63.M. White and M. Bowling. Learning a value analysis tool for agent evaluation. In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI), pages 1976–1981, 2009.
64.R. J. Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning, 8(3-4):229–256, 1992.
65.M. Yang, O. Nachum, B. Dai, L. Li, and D. Schuurmans. Off-policy evaluation via the regularized lagrangian. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, 2020.
66.R. Zhong, D. Zhang, L. Schäfer, S. V. Albrecht, and J. P. Hanna. Robust On-Policy Sampling for Data-Efficient Policy Evaluation in Reinforcement Learning. In Proceedings of Neural and Information Processing Systems (NeurIPS), 2022.
67.M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pages 928–936, 2003.
68.M. Zinkevich, M. Bowling, N. Bard, M. Kan, and D. Billings. Optimal unbiased estimators for evaluating agent performance. In Proceedings of the 21st National Conference on Artificial Intelligence (AAAI), pages 573–578, 2006.

Citation

MLA

Hanna, J. P., et al. “Data-Efficient Policy Evaluation Through Behavior Policy Search”. Journal of Machine Learning Research, vol. 25, no. 313, 2024, pp. 1–8, https://www.jmlr.org/papers/v25/21-0346.html.

APA

Hanna, J. P., Chandak, Y., Thomas, P. S., White, M., Stone, P., & Niekum, S. (2024). Data-Efficient Policy Evaluation Through Behavior Policy Search. Journal of Machine Learning Research, 25(313), 1–58. https://www.jmlr.org/papers/v25/21-0346.html

Chicago

Hanna, J. P., Y. Chandak, P. S. Thomas, M. White, P. Stone, and S. Niekum. 2024. “Data-Efficient Policy Evaluation Through Behavior Policy Search”. Journal of Machine Learning Research 25 (313): 1–58. https://www.jmlr.org/papers/v25/21-0346.html.

Harvard

Hanna, J.P. et al. (2024) “Data-Efficient Policy Evaluation Through Behavior Policy Search”, Journal of Machine Learning Research, 25(313), pp. 1–58. Available at: https://www.jmlr.org/papers/v25/21-0346.html.

Vancouver

1. Hanna JP, Chandak Y, Thomas PS, White M, Stone P, Niekum S (2024) Data-Efficient Policy Evaluation Through Behavior Policy Search. Journal of Machine Learning Research 25:1–58

BibTeX

@article{JMLR:v25:21-0346,
  author  = {Josiah P. Hanna and Yash Chandak and Philip S. Thomas and Martha White and Peter Stone and Scott Niekum},
  title   = {Data-Efficient Policy Evaluation Through Behavior Policy Search},
  journal = {Journal of Machine Learning Research},
  year    = {2024},
  volume  = {25},
  number  = {313},
  pages   = {1--58},
  url     = {http://jmlr.org/papers/v25/21-0346.html}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Data-Efficient Policy Evaluation Through Behavior Policy Search

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Behavior policy search for unbiased batch policy evaluation

Knowl 2 — Sufficient condition for a minimal-variance behavior policy

Knowl 3 — BPG-V minimizes importance-sampling variance directly

Knowl 4 — BPG-KL searches toward the minimum-variance trajectory distribution

Knowl 5 — Adaptive behavior policies preserve guarantees without independent, identically distributed samples

Knowl 6 — Convergence and convexity under linear-softmax policies

Knowl 7 — Behavior-policy search extends to unbiased estimators with baselines and control variates

Knowl 8 — BPG-V and BPG-KL reduce policy-evaluation MSE across tabular and continuous-control tasks

Knowl 9 — Combining BPG-V with a model-based control variate can further lower MSE

Knowl 10 — Estimator choice and optimization settings constrain practical gains

References

Citation

BibTeX

Access the Paper