# Near-optimal Policy Identification in Active Reinforcement Learning

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 64 references that are in the map.
- First posted on arXiv 19 Dec 2022.

## Builds on (most cited first, 30 of 31)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [First return, then explore](https://mlsanity.com/paper/2004.12919/) (2020)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Benchmarking Model-Based Reinforcement Learning](https://mlsanity.com/paper/1907.02057/) (2019)
- [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Model-Based Active Exploration](https://mlsanity.com/paper/1810.12162/) (2018)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Tuning Hyperparameters without Grad Students: Scalable and Robust Bayesian Optimisation with Dragonfly](https://mlsanity.com/paper/1903.06694/) (2019)
- [Distributionally Robust Bayesian Optimization](https://mlsanity.com/paper/2002.09038/) (2020)
- [Symmetry-Aware Actor-Critic for 3D Molecular Design](https://mlsanity.com/paper/2011.12747/) (2020)
- [Misspecified Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2111.05008/) (2021)
- [Reinforcement Learning for Molecular Design Guided by Quantum Mechanics](https://mlsanity.com/paper/2002.07717/) (2020)
- [Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information](https://mlsanity.com/paper/2104.09460/) (2021)
- [Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2206.11489/) (2022)
- [Kernel-Based Reinforcement Learning: A Finite-Time Analysis](https://mlsanity.com/paper/2004.05599/) (2020)
- [Efficient Local Planning with Linear Function Approximation](https://mlsanity.com/paper/2108.05533/) (2021)
- [Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model](https://mlsanity.com/paper/2105.14016/) (2021)
- [Efficient Planning in Large MDPs with Weak Linear Function Approximation](https://mlsanity.com/paper/2007.06184/) (2020)
- [An Experimental Design Perspective on Model-Based Reinforcement Learning](https://mlsanity.com/paper/2112.05244/) (2021)
- [Exploration via Planning for Information about the Optimal Trajectory](https://mlsanity.com/paper/2210.04642/) (2022)

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

- [Active Preference Optimization for Sample Efficient RLHF](https://mlsanity.com/paper/2402.10500/) (2024)
- [Sample Efficient Preference Alignment in LLMs via Active Exploration](https://mlsanity.com/paper/2312.00267/) (2023)
- [Distributionally Robust Model-based Reinforcement Learning with Large State Spaces](https://mlsanity.com/paper/2309.02236/) (2023)
- [Kernelized Offline Contextual Dueling Bandits](https://mlsanity.com/paper/2307.11288/) (2023)
- [Multitask Learning with No Regret: from Improved Confidence Bounds to Active Learning](https://mlsanity.com/paper/2308.01744/) (2023)
- [RewardUQ: A Unified Framework for Uncertainty-Aware Reward Models](https://mlsanity.com/paper/2602.24040/) (2026)
- [Offline Clustering of Preference Learning with Active-data Augmentation](https://mlsanity.com/paper/2510.26301/) (2025)

## Abstract (arXiv)

Many real-world reinforcement learning tasks require control of complex dynamical systems that involve both costly data acquisition processes and large state spaces. In cases where the transition dynamics can be readily evaluated at specified states (e.g., via a simulator), agents can operate in what is often referred to as planning with a generative model. We propose the AE-LSVI algorithm for best-policy identification, a novel variant of the kernelized least-squares value iteration (LSVI) algorithm that combines optimism with pessimism for active exploration (AE). AE-LSVI provably identifies a near-optimal policy uniformly over an entire state space and achieves polynomial sample complexity guarantees that are independent of the number of states. When specialized to the recently introduced offline contextual Bayesian optimization setting, our algorithm achieves improved sample complexity bounds. Experimentally, we demonstrate that AE-LSVI outperforms other RL algorithms in a variety of environments when robustness to the initial state is required.