# K-Nearest-Neighbor Resampling for Off-Policy Evaluation in Stochastic Control

arXiv: https://arxiv.org/abs/2306.04836 · HTML: https://mlsanity.com/paper/2306.04836/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 74 references that are in the map.
- First posted on arXiv 7 Jun 2023.

## Builds on (most cited first, 23 of 23)

- [Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1604.00923/) (2016)
- [DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections](https://mlsanity.com/paper/1906.04733/) (2019)
- [Batch Policy Learning under Constraints](https://mlsanity.com/paper/1903.08738/) (2019)
- [Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage](https://mlsanity.com/paper/2107.06226/) (2021)
- [The Surprising Effectiveness of Representation Learning for Visual Imitation](https://mlsanity.com/paper/2112.01511/) (2021)
- [A Tour of Reinforcement Learning: The View from Continuous Control](https://mlsanity.com/paper/1806.09460/) (2018)
- [Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1911.06854/) (2019)
- [A Review of Off-Policy Evaluation in Reinforcement Learning](https://mlsanity.com/paper/2212.06355/) (2022)
- [Information Theoretic Model Predictive Control: Theory and Applications to Autonomous Driving](https://mlsanity.com/paper/1707.02342/) (2017)
- [Benchmarks for Deep Off-Policy Evaluation](https://mlsanity.com/paper/2103.16596/) (2021)
- [Approximate Nearest Neighbor Search on High Dimensional Data --- Experiments, Analyses, and Improvement (v1.0)](https://mlsanity.com/paper/1610.02455/) (2016)
- [Bootstrapping Fitted Q-Evaluation for Off-Policy Inference](https://mlsanity.com/paper/2102.03607/) (2021)
- [A Kernel Loss for Solving the Bellman Equation](https://mlsanity.com/paper/1905.10506/) (2019)
- [Offline Reinforcement Learning with Pseudometric Learning](https://mlsanity.com/paper/2103.01948/) (2021)
- [Importance Resampling for Off-policy Prediction](https://mlsanity.com/paper/1906.04328/) (2019)
- [Large-Scale Retrieval for Reinforcement Learning](https://mlsanity.com/paper/2206.05314/) (2022)
- [ORL: Reinforcement Learning Benchmarks for Online Stochastic Optimization Problems](https://mlsanity.com/paper/1911.10641/) (2019)
- [Representation Balancing MDPs for Off-Policy Policy Evaluation](https://mlsanity.com/paper/1805.09044/) (2018)
- [Multi-step Off-policy Learning Without Importance Sampling Ratios](https://mlsanity.com/paper/1702.03006/) (2017)
- [Combining Parametric and Nonparametric Models for Off-Policy Evaluation](https://mlsanity.com/paper/1905.05787/) (2019)
- [Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency](https://mlsanity.com/paper/2301.06240/) (2023)
- [State Estimation for the Individual and the Population in Mean Field Control with Application to Demand Dispatch](https://mlsanity.com/paper/1504.00088/) (2015)
- [Associative Memory Based Experience Replay for Deep Reinforcement Learning](https://mlsanity.com/paper/2207.07791/) (2022)

## Built on by (most cited first, 2 of 2)

- [Learning conditional distributions on continuous spaces](https://mlsanity.com/paper/2406.09375/) (2024)
- [Limit Order Book Simulation and Trade Evaluation with K-Nearest-Neighbor Resampling](https://mlsanity.com/paper/2409.06514/) (2024)

## Abstract (arXiv)

In this paper, we propose a novel K-nearest neighbor resampling procedure for estimating the performance of a policy from historical data containing realized episodes of a decision process generated under a different policy. We provide statistical consistency results under weak conditions. In particular, we avoid the common assumption of identically and independently distributed transitions and rewards. Instead, our analysis allows for the sampling of entire episodes, as is common practice in most applications. To establish the consistency in this setting, we generalize Stone's Theorem, a well-known result in nonparametric statistics on local averaging, to include episodic data and the counterfactual estimation underlying off-policy evaluation (OPE). By focusing on feedback policies that depend deterministically on the current state in environments with continuous state-action spaces and system-inherent stochasticity effected by chosen actions, and relying on trajectory simulation similar to Monte Carlo methods, the proposed method is particularly well suited for stochastic control environments. Compared to other OPE methods, our algorithm does not require optimization, can be efficiently implemented via tree-based nearest neighbor search and parallelization, and does not explicitly assume a parametric model for the environment's dynamics. Numerical experiments demonstrate the effectiveness of the algorithm compared to existing baselines in a variety of stochastic control settings, including a linear quadratic regulator, trade execution in limit order books, and online stochastic bin packing.