mlsanityData to 7 Oct 2026

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

arXiv 2212.09900 ↗First posted 19 Dec 2022cs.LG math.ST stat.MEcited by 32

Not on the map. Why?

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.

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

Builds on

36 of 88 references.

References · 36

  1. 2017A Tutorial on Thompson Samplingcited by 420
  2. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  3. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  4. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
  5. 2016Recommendations as Treatments: Debiasing Learning and Evaluationcited by 246
  6. 2018Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimationcited by 226
  7. 2019AlgaeDICE: Policy Gradient from Arbitrary Experiencecited by 187
  8. 2020Estimating means of bounded random variables by bettingcited by 164
  9. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 160
  10. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
  11. 2016Variance-based regularization with convex objectivescited by 153
  12. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
24 more
  1. 2020GenDICE: Generalized Offline Estimation of Stationary Valuescited by 122
  2. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 122
  3. 2021OptiDICE: Offline Policy Optimization via Stationary Distribution Correction Estimationcited by 121
  4. 2019Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Samplingcited by 118
  5. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
  6. 2016Off-policy evaluation for slate recommendationcited by 102
  7. 2020The Importance of Pessimism in Fixed-Dataset Policy Optimizationcited by 99
  8. 2019Confidence Intervals for Policy Evaluation in Adaptive Experimentscited by 95
  9. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 84
  10. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  11. 2018Offline Multi-Action Policy Learning: Generalization and Optimizationcited by 64
  12. 2021Sensitivity Analysis of Individual Treatment Effects: A Robust Conformal Inference Approachcited by 62
  13. 2017Balanced Policy Evaluation and Learningcited by 51
  14. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41
  15. 2020Confident Off-Policy Evaluation and Selection through Self-Normalized Importance Weightingcited by 38
  16. 2015Residual Weighted Learning for Estimating Individualized Treatment Rulescited by 37
  17. 2022Anytime-valid off-policy inference for contextual banditscited by 37
  18. 2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gapscited by 34
  19. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangiancited by 29
  20. 2021Policy Learning with Adaptively Collected Datacited by 21
  21. 2022Conformalized survival analysis with adaptive cutoffscited by 17
  22. 2016The Econometrics of Randomized Experimentscited by 14
  23. 2021Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learningcited by 10
  24. 2022Upper bounds on the Natarajan dimensions of some function classescited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 12; 2024: 9; 2025: 7; 2026: 4.

32 papers.

Sort:

By area:

  1. 2024Applied Causal Inference Powered by ML and AIcited by 30
  2. 2024Dual Active Learning for Reinforcement Learning from Human Feedbackcited by 19
  3. 2023Importance-Weighted Offline Learning Done Rightcited by 15
  4. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 14
  5. 2023Oracle-Efficient Pessimism: Offline Policy Optimization in Contextual Banditscited by 14
  6. 2023Proportional Response: Contextual Bandits for Simple and Cumulative Regret Minimizationcited by 7
  7. 2023Positivity-free Policy Learning with Observational Datacited by 6
  8. 2023Individualized Policy Evaluation and Learning under Clustered Network Interferencecited by 6
  9. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyondcited by 6
  10. 2024Combining Experimental and Historical Data for Policy Evaluationcited by 6
  11. 2025Joint Value Estimation and Bidding in Repeated First-Price Auctionscited by 6
  12. 2023Efficient and robust transfer learning of optimal individualized treatment regimes with right-censored survival datacited by 5
20 more
  1. 2024Distributionally Robust Policy Learning under Concept Driftscited by 5
  2. 2023Bayesian Safe Policy Learning with Chance Constrained Optimization: Application to Military Security Assessment during the Vietnam Warcited by 4
  3. 2025Balancing optimism and pessimism in offline-to-online learningcited by 4
  4. 2024Robust Offline Policy Learning with Observational Data from Multiple Sourcescited by 3
  5. 2024Off-policy estimation with adaptively collected data: the power of online learningcited by 3
  6. 2025Improved Offline Contextual Bandits with Second-Order Bounds: Betting and Freezingcited by 3
  7. 2023Pessimistic Off-Policy Multi-Objective Optimizationcited by 2
  8. 2023Rethinking Model-based, Policy-based, and Value-based Reinforcement Learning via the Lens of Representation Complexitycited by 2
  9. 2025Statistical and Algorithmic Foundations of Reinforcement Learningcited by 2
  10. 2024SaVeR: Optimal Data Collection Strategy for Safe Policy Evaluation in Tabular MDPcited by 1
  11. 2023Federated Offline Policy Learningcited by 0
  12. 2023Offline Policy Evaluation for Reinforcement Learning with Adaptively Collected Datacited by 0
  13. 2024Pessimistic Causal Reinforcement Learning with Mediators for Confounded Offline Datacited by 0
  14. 2025Clustered KL-barycenter design for policy evaluationcited by 0
  15. 2025DOLCE: Decomposing Off-Policy Evaluation/Learning into Lagged and Current Effectscited by 0
  16. 2025Fast Best-in-Class Regret for Contextual Banditscited by 0
  17. 2026Pessimistic Risk-Aware Policy Learning in Contextual Banditscited by 0
  18. 2026Wasserstein Policy Learning for Distributional Outcomescited by 0
  19. 2026From Unsupervised Subgroups to Hypothetical State-Intervention Policies: An Evaluation of Selected Subgrouping Methods in Observational Health Datacited by 0
  20. 2026Observational Policy Ranking for SMB Financial Guidance from Multi-Action Accounting Logscited by 0