# On the Optimality of Batch Policy Optimization Algorithms

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 37 references that are in the map.
- First posted on arXiv 6 Apr 2021.

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

- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [Conservative Q-Learning for Offline Reinforcement Learning](https://mlsanity.com/paper/2006.04779/) (2020)
- [Off-Policy Deep Reinforcement Learning without Exploration](https://mlsanity.com/paper/1812.02900/) (2018)
- [Stabilizing Off-Policy Q-Learning via Bootstrapping Error Reduction](https://mlsanity.com/paper/1906.00949/) (2019)
- [Behavior Regularized Offline Reinforcement Learning](https://mlsanity.com/paper/1911.11361/) (2019)
- [MOPO: Model-based Offline Policy Optimization](https://mlsanity.com/paper/2005.13239/) (2020)
- [MOReL : Model-Based Offline Reinforcement Learning](https://mlsanity.com/paper/2005.05951/) (2020)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Way Off-Policy Batch Deep Reinforcement Learning of Implicit Human Preferences in Dialog](https://mlsanity.com/paper/1907.00456/) (2019)
- [Keep Doing What Worked: Behavioral Modelling Priors for Offline Reinforcement Learning](https://mlsanity.com/paper/2002.08396/) (2020)
- [Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach](https://mlsanity.com/paper/1610.03425/) (2016)
- [The Importance of Pessimism in Fixed-Dataset Policy Optimization](https://mlsanity.com/paper/2009.06799/) (2020)
- [Provably Good Batch Reinforcement Learning Without Great Exploration](https://mlsanity.com/paper/2007.08202/) (2020)
- [CoinDICE: Off-Policy Confidence Interval Estimation](https://mlsanity.com/paper/2010.11652/) (2020)
- [Near-Optimal Offline Reinforcement Learning via Double Variance Reduction](https://mlsanity.com/paper/2102.01748/) (2021)
- [Distributional Robustness and Regularization in Reinforcement Learning](https://mlsanity.com/paper/2003.02894/) (2020)
- [From Data to Decisions: Distributionally Robust Optimization is Optimal](https://mlsanity.com/paper/1704.04118/) (2017)
- [Distributionally Robust Counterpart in Markov Decision Processes](https://mlsanity.com/paper/1501.07418/) (2015)
- [Recovering Best Statistical Guarantees via the Empirical Divergence-based Distributionally Robust Optimization](https://mlsanity.com/paper/1605.09349/) (2016)
- [Distributionally Robust Counterfactual Risk Minimization](https://mlsanity.com/paper/1906.06211/) (2019)
- [Distributionally Robust Optimization for Sequential Decision Making](https://mlsanity.com/paper/1801.04745/) (2018)
- [Empirical Likelihood for Contextual Bandits](https://mlsanity.com/paper/1906.03323/) (2019)

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

- [Supervised Pretraining Can Learn In-Context Reinforcement Learning](https://mlsanity.com/paper/2306.14892/) (2023)
- [Towards Instance-Optimal Offline Reinforcement Learning with Pessimism](https://mlsanity.com/paper/2110.08695/) (2021)
- [Value-Incentivized Preference Optimization: A Unified Approach to Online and Offline RLHF](https://mlsanity.com/paper/2405.19320/) (2024)
- [Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism](https://mlsanity.com/paper/2203.05804/) (2022)
- [The In-Sample Softmax for Offline Reinforcement Learning](https://mlsanity.com/paper/2302.14372/) (2023)
- [Adversarial Model for Offline Reinforcement Learning](https://mlsanity.com/paper/2302.11048/) (2023)
- [Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptotics](https://mlsanity.com/paper/2105.03863/) (2021)
- [Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization](https://mlsanity.com/paper/2111.13807/) (2021)
- [Pessimism for Offline Linear Contextual Bandits using ℓp Confidence Sets](https://mlsanity.com/paper/2205.10671/) (2022)
- [Offline Primal-Dual Reinforcement Learning for Linear MDPs](https://mlsanity.com/paper/2305.12944/) (2023)
- [Importance-Weighted Offline Learning Done Right](https://mlsanity.com/paper/2309.15771/) (2023)
- [Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings](https://mlsanity.com/paper/2105.06029/) (2021)
- [Model Selection in Batch Policy Optimization](https://mlsanity.com/paper/2112.12320/) (2021)
- [Fast and Regret Optimal Best Arm Identification: Fundamental Limits and Low-Complexity Algorithms](https://mlsanity.com/paper/2309.00591/) (2023)
- [Offline Reinforcement Learning in Large State Spaces: Algorithms and Guarantees](https://mlsanity.com/paper/2510.04088/) (2025)
- [ARMOR: A Model-based Framework for Improving Arbitrary Baseline Policies with Offline Data](https://mlsanity.com/paper/2211.04538/) (2022)
- [Optimal Best-Arm Identification in Bandits with Access to Offline Data](https://mlsanity.com/paper/2306.09048/) (2023)
- [Balancing optimism and pessimism in offline-to-online learning](https://mlsanity.com/paper/2502.08259/) (2025)
- [Model-based Offline Reinforcement Learning with Local Misspecification](https://mlsanity.com/paper/2301.11426/) (2023)
- [Online Learning with Off-Policy Feedback](https://mlsanity.com/paper/2207.08956/) (2022)
- [VIPeR: Provably Efficient Algorithm for Offline RL with Neural Function Approximation](https://mlsanity.com/paper/2302.12780/) (2023)
- [The Curse of Passive Data Collection in Batch Reinforcement Learning](https://mlsanity.com/paper/2106.09973/) (2021)
- [In-Context Reinforcement Learning From Suboptimal Historical Data](https://mlsanity.com/paper/2601.20116/) (2026)
- [NeuroSep-CP-LCB: A Deep Learning-based Contextual Multi-armed Bandit Algorithm with Uncertainty Quantification for Early Sepsis Prediction](https://mlsanity.com/paper/2503.16708/) (2025)
- [Bayesian Regret Minimization in Offline Bandits](https://mlsanity.com/paper/2306.01237/) (2023)
- [Offline Clustering of Preference Learning with Active-data Augmentation](https://mlsanity.com/paper/2510.26301/) (2025)
- [Unlearning Offline Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/2605.00638/) (2026)
- [Offline-to-Online Learning in Linear Bandits](https://mlsanity.com/paper/2606.04305/) (2026)

## Abstract (arXiv)

Batch policy optimization considers leveraging existing data for policy construction before interacting with an environment. Although interest in this problem has grown significantly in recent years, its theoretical foundations remain under-developed. To advance the understanding of this problem, we provide three results that characterize the limits and possibilities of batch policy optimization in the finite-armed stochastic bandit setting. First, we introduce a class of confidence-adjusted index algorithms that unifies optimistic and pessimistic principles in a common framework, which enables a general analysis. For this family, we show that any confidence-adjusted index algorithm is minimax optimal, whether it be optimistic, pessimistic or neutral. Our analysis reveals that instance-dependent optimality, commonly used to establish optimality of on-line stochastic bandit algorithms, cannot be achieved by any algorithm in the batch setting. In particular, for any algorithm that performs optimally in some environment, there exists another environment where the same algorithm suffers arbitrarily larger regret. Therefore, to establish a framework for distinguishing algorithms, we introduce a new weighted-minimax criterion that considers the inherent difficulty of optimal value prediction. We demonstrate how this criterion can be used to justify commonly used pessimistic principles for batch policy optimization.