mlsanityData to 14 Oct 2026

Learning Bellman Complete Representations for Offline Policy Evaluation

arXiv 2207.05837 ↗First posted 12 Jul 2022cs.LG math.OC math.STcited by 17

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

Abstract (arXiv)

We study representation learning for Offline Reinforcement Learning (RL), focusing on the important task of Offline Policy Evaluation (OPE). Recent work shows that, in contrast to supervised learning, realizability of the Q-function is not enough for learning it. Two sufficient conditions for sample-efficient OPE are Bellman completeness and coverage. Prior work often assumes that representations satisfying these conditions are given, with results being mostly theoretical in nature. In this work, we propose BCRL, which directly learns from data an approximately linear Bellman complete representation with good coverage. With this learned representation, we perform OPE using Least Square Policy Evaluation (LSPE) with linear functions in our learned representation. We present an end-to-end theoretical analysis, showing that our two-stage algorithm enjoys polynomial sample complexity provided some representation in the rich class considered is linear Bellman complete. Empirically, we extensively evaluate our algorithm on challenging, image-based continuous control tasks from the Deepmind Control Suite. We show our representation enables better OPE compared to previous representation learning methods developed for off-policy RL (e.g., CURL, SPR). BCRL achieve competitive OPE error with the state-of-the-art method Fitted Q-Evaluation (FQE), and beats FQE when evaluating beyond the initial state distribution. Our ablations show that both linear Bellman complete and coverage components of our method are crucial.

Key facts. Cited by 17 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 37 of its 51 references that are in the map. First posted on arXiv 12 Jul 2022.

Builds on

37 of 51 references.

Closest ancestors · 7

Same direction, newest first

  1. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation21 Nov
  2. 2021Representation Learning for Online and Offline RL in Low-rank MDPs9 Oct
  3. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage13 Jul
  4. 2021Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RL22 Jun
  5. 2021Representation Matters: Offline Pretraining for Sequential Decision Making11 Feb
  6. 2020Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient8 Nov
  7. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?22 Oct

Other references · 30

  1. 2020A Simple Framework for Contrastive Learning of Visual Representationscited by 12,049
  2. 2018Representation Learning with Contrastive Predictive Codingcited by 7,777
  3. 2019Momentum Contrast for Unsupervised Visual Representation Learningcited by 7,513
  4. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,885
  5. 2020Bootstrap your own latent: A new approach to self-supervised Learningcited by 4,750
  6. 2015Continuous control with deep reinforcement learningcited by 3,407
  7. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  8. 2020Mastering Atari with Discrete World Modelscited by 1,007
  9. 2018DeepMind Control Suitecited by 956
  10. 2020CURL: Contrastive Unsupervised Representations for Reinforcement Learningcited by 760
  11. 2021Mastering Visual Continuous Control: Improved Data-Augmented Reinforcement Learningcited by 372
  12. 2015Doubly Robust Off-policy Value Evaluation for Reinforcement Learningcited by 339
18 more
  1. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  2. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 287
  3. 2016Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learningcited by 286
  4. 2019Improving Sample Efficiency in Model-Free Reinforcement Learning from Imagescited by 274
  5. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
  6. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  7. 2019Unsupervised State Representation Learning in Ataricited by 144
  8. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  9. 2020Minimax-Optimal Off-Policy Evaluation with Linear Function Approximationcited by 120
  10. 2021Benchmarks for Deep Off-Policy Evaluationcited by 89
  11. 2020Off-Policy Evaluation via the Regularized Lagrangiancited by 86
  12. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  13. 2020Deep Reinforcement and InfoMax Learningcited by 79
  14. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  15. 2021Provable Representation Learning for Imitation with Contrastive Fourier Featurescited by 34
  16. 2020Statistical Bootstrapping for Uncertainty Estimation in Off-Policy Evaluationcited by 28
  17. 2020A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Settingcited by 25
  18. 2021Learning Good State and Action Representations via Tensor Decompositioncited by 7

Built on by

Cited by year

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

17 papers.

Sort:

By area:

  1. 2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
  2. 2024More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learningcited by 23
  3. 2023Distributional Offline Policy Evaluation with Predictive Error Guaranteescited by 20
  4. 2022When is Realizability Sufficient for Off-Policy Reinforcement Learning?cited by 17
  5. 2025Qsharp: Provably Optimal Distributional RL for LLM Post-Trainingcited by 15
  6. 2022Oracle Inequalities for Model Selection in Offline Reinforcement Learningcited by 13
  7. 2024The Central Role of the Loss Function in Reinforcement Learningcited by 8
  8. 2023State-Action Similarity-Based Representations for Off-Policy Evaluationcited by 4
  9. 2024Off-policy Evaluation with Deeply-abstracted Statescited by 4
  10. 2024Primal-Dual Spectral Representation for Off-policy Evaluationcited by 4
  11. 2024Efficient and Sharp Off-Policy Evaluation in Robust Markov Decision Processescited by 3
  12. 2024OPERA: Automatic Offline Policy Evaluation with Re-weighted Aggregates of Multiple Estimatorscited by 3
5 more
  1. 2025Bellman Calibration for V-Learning in Offline Reinforcement Learningcited by 3
  2. 2025Fitted Q-Evaluation without Bellman Completeness via Occupancy Weightingcited by 2
  3. 2023π2vec: Policy Representations with Successor Featurescited by 1
  4. 2024Stable Offline Value Function Learning with Bisimulation-based Representationscited by 0
  5. 2025Generalized Linear Markov Decision Processcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Offline Policy Evaluation via Mixed Bellman Residuals and Adaptive Critic Representations
  2. 2026Residuals-based Offline Reinforcement Learning
  3. 2022Bellman Residual Orthogonalization for Offline Reinforcement Learning
  4. 2022Behavior Prior Representation learning for Offline Reinforcement Learning
  5. 2026Lifted Bellman Linear Programming for Offline Reinforcement Learning
  6. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism
  7. 2025Learning to Trust Bellman Updates: Selective State-Adaptive Regularization for Offline RL
  8. 2026Target-Aligned Bellman Backup for Cross-domain Offline Reinforcement Learning