mlsanityData to 14 Oct 2026

Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processes

arXiv 2205.13589 ↗First posted 26 May 2022cs.LG cs.AI math.STcited by 26

On the map: Offline RL and imitation learning from data → Offline RL algorithms

Abstract (arXiv)

We study offline reinforcement learning (RL) in partially observable Markov decision processes. In particular, we aim to learn an optimal policy from a dataset collected by a behavior policy which possibly depends on the latent state. Such a dataset is confounded in the sense that the latent state simultaneously affects the action and the observation, which is prohibitive for existing offline RL algorithms. To this end, we propose the underlineProxy variable underlinePessimistic underlinePolicy underlineOptimization (textttP3O) algorithm, which addresses the confounding bias and the distributional shift between the optimal and behavior policies in the context of general function approximation. At the core of textttP3O is a coupled sequence of pessimistic confidence regions constructed via proximal causal inference, which is formulated as minimax estimation. Under a partial coverage assumption on the confounded dataset, we prove that textttP3O achieves a n-1/2-suboptimality, where n is the number of trajectories in the dataset. To our best knowledge, textttP3O is the first provably efficient offline RL algorithm for POMDPs with a confounded dataset.

Key facts. Cited by 26 papers in the map (data through 14 Oct 2026). Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data. Builds on 50 of its 103 references that are in the map. First posted on arXiv 26 May 2022.

Builds on

50 of 103 references.

Closest ancestors · 17

Same direction, newest first

  1. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism11 Mar
  2. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability9 Feb
  3. 2021Proximal Reinforcement Learning: Efficient Off-Policy Evaluation in Partially Observed Markov Decision Processes28 Oct
  4. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimism17 Oct
  5. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning19 Aug
  6. 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
  7. 2021Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning25 Mar
  8. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism22 Mar
  9. 2021COMBO: Conservative Offline Model-Based Policy Optimization16 Feb
  10. 2021Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency5 Feb
  11. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec
  12. 2020Provably Good Batch Reinforcement Learning Without Great Exploration16 Jul
5 more
  1. 2020Conservative Q-Learning for Offline Reinforcement Learning8 Jun
  2. 2020MOReL : Model-Based Offline Reinforcement Learning12 May
  3. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May
  4. 2020Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison9 Mar
  5. 2020Confounding-Robust Policy Evaluation in Infinite-Horizon Reinforcement Learning11 Feb

Other references · 33

  1. 2014Fully Convolutional Networks for Semantic Segmentationcited by 4,859
  2. 2019Scalability in Perception for Autonomous Driving: Waymo Open Datasetcited by 2,451
  3. 2021Offline Reinforcement Learning as One Big Sequence Modeling Problemcited by 644
  4. 2019Object Detection in 20 Years: A Surveycited by 531
  5. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 311
  6. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 287
  7. 2019Orthogonal Statistical Learningcited by 151
  8. 2016Identifying Causal Effects With Proxy Variables of an Unmeasured Confoundercited by 139
  9. 2019Counterfactual Off-Policy Evaluation with Gumbel-Max Structural Causal Modelscited by 117
  10. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  11. 2020The Importance of Pessimism in Fixed-Dataset Policy Optimizationcited by 99
  12. 2020An Introduction to Proximal Causal Learningcited by 95
21 more
  1. 2020Minimax Estimation of Conditional Moment Modelscited by 83
  2. 2019Off-Policy Evaluation in Partially Observable Environmentscited by 66
  3. 2020Sample-Efficient Reinforcement Learning of Undercomplete POMDPscited by 66
  4. 2020Semiparametric proximal causal inferencecited by 59
  5. 2020Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RLcited by 55
  6. 2021Proximal Causal Learning with Kernels: Two-Stage Estimation and Moment Restrictioncited by 55
  7. 2021Causal Inference Under Unmeasured Confounding With Negative Controls: A Minimax Learning Approachcited by 44
  8. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 42
  9. 2020Off-policy Evaluation in Infinite-Horizon Reinforcement Learning with Latent Confounderscited by 41
  10. 2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
  11. 2016A PAC RL Algorithm for Episodic POMDPscited by 37
  12. 2021TF-Blender: Temporal Feature Blender for Video Object Detectioncited by 37
  13. 2018A confounding bridge approach for double negative control inference on causal effectscited by 36
  14. 2020Adversarial Estimation of Riesz Representerscited by 35
  15. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
  16. 2020Dynamic Causal Effects Evaluation in A/B Testing with a Reinforcement Learning Frameworkcited by 29
  17. 2020Kernel Methods for Unobserved Confounding: Negative Controls, Proxies, and Instrumentscited by 28
  18. 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
  19. 2021Sublinear Regret for Learning POMDPscited by 19
  20. 2021Online Learning for Unknown Partially Observable MDPscited by 17
  21. 2022Learn to Match with No Regret: Reinforcement Learning in Markov Matching Marketscited by 16

Built on by

Cited by year

Citing papers per year: 2022: 7; 2023: 7; 2024: 5; 2025: 7.

26 papers.

Sort:

By area:

  1. 2024Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizercited by 109
  2. 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
  3. 2022Future-Dependent Value-Based Off-Policy Evaluation in POMDPscited by 21
  4. 2023Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Explorationcited by 20
  5. 2022Offline Reinforcement Learning with Instrumental Variables in Confounded Markov Decision Processescited by 19
  6. 2022Offline Policy Evaluation and Optimization under Confoundingcited by 12
  7. 2024On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluationcited by 10
  8. 2022Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instrumentscited by 9
  9. 2023Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximationcited by 9
  10. 2023Delphic Offline Reinforcement Learning under Nonidentifiable Hidden Confoundingcited by 7
  11. 2025Confounding Robust Deep Reinforcement Learning: A Causal Approachcited by 7
  12. 2023A Policy Gradient Method for Confounded POMDPscited by 6
14 more
  1. 2023Provably Efficient UCB-type Algorithms For Learning Predictive State Representationscited by 6
  2. 2025Automatic Reward Shaping from Confounded Offline Datacited by 6
  3. 2024A Natural Extension To Online Algorithms For Hybrid RL With Limited Coveragecited by 5
  4. 2024Two-way Deconfounder for Off-policy Evaluation in Causal Reinforcement Learningcited by 5
  5. 2025Counterfactually Fair Reinforcement Learning via Sequential Data Preprocessingcited by 5
  6. 2023Finding Regularized Competitive Equilibria of Heterogeneous Agent Macroeconomic Models with Reinforcement Learningcited by 4
  7. 2025Learning an Optimal Assortment Policy under Observational Datacited by 4
  8. 2022Blessing from Human-AI Interaction: Super Reinforcement Learning in Confounded Environmentscited by 3
  9. 2025Reinforcement Learning with Continuous Actions Under Unmeasured Confoundingcited by 3
  10. 2025Grounded by Experience: Generative Healthcare Prediction Augmented with Hierarchical Agentic Retrievalcited by 1
  11. 2022Statistical Estimation of Confounded Linear MDPs: An Instrumental Variable Approachcited by 0
  12. 2022Offline Reinforcement Learning for Human-Guided Human-Machine Interaction with Private Informationcited by 0
  13. 2024Pessimistic Causal Reinforcement Learning with Mediators for Confounded Offline Datacited by 0
  14. 2025The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportabilitycited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2022State-Aware Proximal Pessimistic Algorithms for Offline Reinforcement Learning
  2. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity
  3. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage
  4. 2025Semi-pessimistic Reinforcement Learning
  5. 2022Model-Based Offline Reinforcement Learning with Pessimism-Modulated Dynamics Belief
  6. 2026Pessimistic Auxiliary Policy for Offline Reinforcement Learning
  7. 2026Generalization in offline RL: The structure is more important than the amount of pessimism
  8. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangian