# Policy learning "without" overlap: Pessimism and generalized empirical Bernstein's inequality

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

## Key facts

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

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

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Bellman-consistent Pessimism for Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06926/) (2021)
- [Recommendations as Treatments: Debiasing Learning and Evaluation](https://mlsanity.com/paper/1602.05352/) (2016)
- [Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation](https://mlsanity.com/paper/1810.12429/) (2018)
- [AlgaeDICE: Policy Gradient from Arbitrary Experience](https://mlsanity.com/paper/1912.02074/) (2019)
- [Estimating means of bounded random variables by betting](https://mlsanity.com/paper/2010.09686/) (2020)
- [Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage](https://mlsanity.com/paper/2107.06226/) (2021)
- [Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning](https://mlsanity.com/paper/2106.04895/) (2021)
- [Variance-based regularization with convex objectives](https://mlsanity.com/paper/1610.02581/) (2016)
- [Minimax Weight and Q-Function Learning for Off-Policy Evaluation](https://mlsanity.com/paper/1910.12809/) (2019)
- [Offline Reinforcement Learning with Realizability and Single-policy Concentrability](https://mlsanity.com/paper/2202.04634/) (2022)
- [GenDICE: Generalized Offline Estimation of Stationary Values](https://mlsanity.com/paper/2002.09072/) (2020)
- [OptiDICE: Offline Policy Optimization via Stationary Distribution Correction Estimation](https://mlsanity.com/paper/2106.10783/) (2021)
- [Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling](https://mlsanity.com/paper/1906.03393/) (2019)
- [Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning](https://mlsanity.com/paper/2108.08812/) (2021)
- [Off-policy evaluation for slate recommendation](https://mlsanity.com/paper/1605.04812/) (2016)
- [The Importance of Pessimism in Fixed-Dataset Policy Optimization](https://mlsanity.com/paper/2009.06799/) (2020)
- [Confidence Intervals for Policy Evaluation in Adaptive Experiments](https://mlsanity.com/paper/1911.02768/) (2019)
- [Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity](https://mlsanity.com/paper/2202.13890/) (2022)
- [Towards Instance-Optimal Offline Reinforcement Learning with Pessimism](https://mlsanity.com/paper/2110.08695/) (2021)
- [Offline Multi-Action Policy Learning: Generalization and Optimization](https://mlsanity.com/paper/1810.04778/) (2018)
- [Sensitivity Analysis of Individual Treatment Effects: A Robust Conformal Inference Approach](https://mlsanity.com/paper/2111.12161/) (2021)
- [Balanced Policy Evaluation and Learning](https://mlsanity.com/paper/1705.07384/) (2017)
- [The Efficacy of Pessimism in Asynchronous Q-Learning](https://mlsanity.com/paper/2203.07368/) (2022)
- [Residual Weighted Learning for Estimating Individualized Treatment Rules](https://mlsanity.com/paper/1508.03179/) (2015)
- [Confident Off-Policy Evaluation and Selection through Self-Normalized Importance Weighting](https://mlsanity.com/paper/2006.10460/) (2020)
- [Anytime-valid off-policy inference for contextual bandits](https://mlsanity.com/paper/2210.10768/) (2022)
- [Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gaps](https://mlsanity.com/paper/2203.13935/) (2022)

## Built on by (most cited first, 30 of 32)

- [Applied Causal Inference Powered by ML and AI](https://mlsanity.com/paper/2403.02467/) (2024)
- [Dual Active Learning for Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2410.02504/) (2024)
- [Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learning](https://mlsanity.com/paper/2304.07278/) (2023)
- [Oracle-Efficient Pessimism: Offline Policy Optimization in Contextual Bandits](https://mlsanity.com/paper/2306.07923/) (2023)
- [Importance-Weighted Offline Learning Done Right](https://mlsanity.com/paper/2309.15771/) (2023)
- [Proportional Response: Contextual Bandits for Simple and Cumulative Regret Minimization](https://mlsanity.com/paper/2307.02108/) (2023)
- [Positivity-free Policy Learning with Observational Data](https://mlsanity.com/paper/2310.06969/) (2023)
- [Individualized Policy Evaluation and Learning under Clustered Network Interference](https://mlsanity.com/paper/2311.02467/) (2023)
- [On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond](https://mlsanity.com/paper/2401.03301/) (2024)
- [Combining Experimental and Historical Data for Policy Evaluation](https://mlsanity.com/paper/2406.00317/) (2024)
- [Distributionally Robust Policy Learning under Concept Drifts](https://mlsanity.com/paper/2412.14297/) (2024)
- [Balancing optimism and pessimism in offline-to-online learning](https://mlsanity.com/paper/2502.08259/) (2025)
- [Joint Value Estimation and Bidding in Repeated First-Price Auctions](https://mlsanity.com/paper/2502.17292/) (2025)
- [Efficient and robust transfer learning of optimal individualized treatment regimes with right-censored survival data](https://mlsanity.com/paper/2301.05491/) (2023)
- [Bayesian Safe Policy Learning with Chance Constrained Optimization: Application to Military Security Assessment during the Vietnam War](https://mlsanity.com/paper/2307.08840/) (2023)
- [Improved Offline Contextual Bandits with Second-Order Bounds: Betting and Freezing](https://mlsanity.com/paper/2502.10826/) (2025)
- [SaVeR: Optimal Data Collection Strategy for Safe Policy Evaluation in Tabular MDP](https://mlsanity.com/paper/2406.02165/) (2024)
- [Robust Offline Policy Learning with Observational Data from Multiple Sources](https://mlsanity.com/paper/2410.08537/) (2024)
- [Off-policy estimation with adaptively collected data: the power of online learning](https://mlsanity.com/paper/2411.12786/) (2024)
- [Pessimistic Off-Policy Multi-Objective Optimization](https://mlsanity.com/paper/2310.18617/) (2023)
- [Rethinking Model-based, Policy-based, and Value-based Reinforcement Learning via the Lens of Representation Complexity](https://mlsanity.com/paper/2312.17248/) (2023)
- [Statistical and Algorithmic Foundations of Reinforcement Learning](https://mlsanity.com/paper/2507.14444/) (2025)
- [Federated Offline Policy Learning](https://mlsanity.com/paper/2305.12407/) (2023)
- [Offline Policy Evaluation for Reinforcement Learning with Adaptively Collected Data](https://mlsanity.com/paper/2306.14063/) (2023)
- [Pessimistic Causal Reinforcement Learning with Mediators for Confounded Offline Data](https://mlsanity.com/paper/2403.11841/) (2024)
- [Clustered KL-barycenter design for policy evaluation](https://mlsanity.com/paper/2503.02735/) (2025)
- [DOLCE: Decomposing Off-Policy Evaluation/Learning into Lagged and Current Effects](https://mlsanity.com/paper/2505.00961/) (2025)
- [Fast Best-in-Class Regret for Contextual Bandits](https://mlsanity.com/paper/2510.15483/) (2025)
- [Pessimistic Risk-Aware Policy Learning in Contextual Bandits](https://mlsanity.com/paper/2605.15620/) (2026)
- [Wasserstein Policy Learning for Distributional Outcomes](https://mlsanity.com/paper/2606.19117/) (2026)

## Abstract (arXiv)

This paper studies offline policy learning, which aims at utilizing observations collected a priori (from either fixed or adaptively evolving behavior policies) to learn an optimal individualized decision rule that achieves the best overall outcomes for a given population. Existing policy learning methods rely on a uniform overlap assumption, i.e., the propensities of exploring all actions for all individual characteristics must be lower bounded. As one has no control over the data collection process, this assumption can be unrealistic in many situations, especially when the behavior policies are allowed to evolve over time with diminishing propensities for certain actions. In this paper, we propose Pessimistic Policy Learning (PPL), a new algorithm that optimizes lower confidence bounds (LCBs) -- instead of point estimates -- of the policy values. The LCBs are constructed using knowledge of the behavior policies for collecting the offline data. Without assuming any uniform overlap condition, we establish a data-dependent upper bound for the suboptimality of our algorithm, which only depends on (i) the overlap for the optimal policy, and (ii) the complexity of the policy class we optimize over. As an implication, for adaptively collected data, we ensure efficient policy learning as long as the propensities for optimal actions are lower bounded over time, while those for suboptimal ones are allowed to diminish arbitrarily fast. In our theoretical analysis, we develop a new self-normalized type concentration inequality for inverse-propensity-weighting estimators, generalizing the well-known empirical Bernstein's inequality to unbounded and non-i.i.d. data. We complement our theory with an efficient optimization algorithm via Majorization-Minimization and policy tree search, as well as extensive simulation studies and real-world applications that demonstrate the efficacy of PPL.