mlsanityData to 14 Oct 2026

Variance-Aware Off-Policy Evaluation with Linear Function Approximation

arXiv 2106.11960 ↗First posted 22 Jun 2021cs.LG math.OC stat.MLcited by 34

Not on the map. Why?

Abstract (arXiv)

We study the off-policy evaluation (OPE) problem in reinforcement learning with linear function approximation, which aims to estimate the value function of a target policy based on the offline data collected by a behavior policy. We propose to incorporate the variance information of the value function to improve the sample efficiency of OPE. More specifically, for time-inhomogeneous episodic linear Markov decision processes (MDPs), we propose an algorithm, VA-OPE, which uses the estimated variance of the value function to reweight the Bellman residual in Fitted Q-Iteration. We show that our algorithm achieves a tighter error bound than the best-known result. We also provide a fine-grained characterization of the distribution shift between the behavior policy and the target policy. Extensive numerical experiments corroborate our theory.

Key facts. Cited by 34 papers in the map (data through 14 Oct 2026). Builds on 32 of its 65 references that are in the map. First posted on arXiv 22 Jun 2021.

Builds on

32 of 65 references.

References · 32

  1. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,920
  2. 2019Stabilizing Off-Policy Q-Learning via Bootstrapping Error Reductioncited by 840
  3. 2020MOReL : Model-Based Offline Reinforcement Learningcited by 590
  4. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  5. 2020Is Pessimism Provably Efficient for Offline RL?cited by 364
  6. 2015Doubly Robust Off-policy Value Evaluation for Reinforcement Learningcited by 339
  7. 2016Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learningcited by 286
  8. 2019DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Correctionscited by 254
  9. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  10. 2018Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimationcited by 227
  11. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  12. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
20 more
  1. 2019AlgaeDICE: Policy Gradient from Arbitrary Experiencecited by 188
  2. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  3. 2018More Robust Doubly Robust Off-policy Evaluationcited by 141
  4. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  5. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  6. 2020GenDICE: Generalized Offline Estimation of Stationary Valuescited by 122
  7. 2020Minimax-Optimal Off-Policy Evaluation with Linear Function Approximationcited by 120
  8. 2019Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Samplingcited by 119
  9. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  10. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  11. 2019Efficiently Breaking the Curse of Horizon in Off-Policy Evaluation with Double Reinforcement Learningcited by 75
  12. 2020CoinDICE: Off-Policy Confidence Interval Estimationcited by 64
  13. 2020Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learningcited by 60
  14. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  15. 2020A Unifying View of Optimism in Episodic Reinforcement Learningcited by 52
  16. 2019Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimationcited by 48
  17. 2021Instabilities of Offline RL with Pre-Trained Neural Representationcited by 38
  18. 2018Deep Reinforcement Learning for Vision-Based Robotic Grasping: A Simulated Comparative Evaluation of Off-Policy Methodscited by 33
  19. 2020Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learningcited by 26
  20. 2021Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithmcited by 10

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 2; 2022: 13; 2023: 8; 2024: 5; 2025: 4; 2026: 2.

34 papers.

Sort:

By area:

  1. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 65
  2. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 55
  3. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  4. 2022Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processescited by 26
  5. 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
  6. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximationcited by 22
  7. 2022Offline Reinforcement Learning with Differential Privacycited by 20
  8. 2021Accelerated and instance-optimal policy evaluation with linear function approximationcited by 18
  9. 2022Off-Policy Fitted Q-Evaluation with Differentiable Function Approximators: Z-Estimation and Inference Theorycited by 18
  10. 2024Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learningcited by 18
  11. 2022Learn to Match with No Regret: Reinforcement Learning in Markov Matching Marketscited by 16
  12. 2022Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximationcited by 13
22 more
  1. 2022Sample Complexity of Nonparametric Off-Policy Evaluation on Low-Dimensional Manifolds using Deep Networkscited by 12
  2. 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficientcited by 12
  3. 2023Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximationcited by 9
  4. 2023Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learningcited by 9
  5. 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewardscited by 8
  6. 2023Robust Offline Reinforcement learning with Heavy-Tailed Rewardscited by 7
  7. 2024Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learningcited by 6
  8. 2024Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPscited by 6
  9. 2023Finding Regularized Competitive Equilibria of Heterogeneous Agent Macroeconomic Models with Reinforcement Learningcited by 4
  10. 2023Regularization and Variance-Weighted Regression Achieves Minimax Optimality in Linear MDPs: Theory and Practicecited by 4
  11. 2023VIPeR: Provably Efficient Algorithm for Offline RL with Neural Function Approximationcited by 3
  12. 2023Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximationcited by 3
  13. 2026Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrabilitycited by 3
  14. 2022Cascaded Gaps: Towards Gap-Dependent Regret for Risk-Sensitive Reinforcement Learningcited by 2
  15. 2026Multiscale replay: A robust algorithm for stochastic variational inequalities with a Markovian buffercited by 2
  16. 2024Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Pathcited by 1
  17. 2025Reweighting Improves Conditional Risk Boundscited by 1
  18. 2022Statistical Estimation of Confounded Linear MDPs: An Instrumental Variable Approachcited by 0
  19. 2024Is Offline Decision Making Possible with Only Few Samples? Reliable Decisions in Data-Starved Bandits via Trust Region Enhancementcited by 0
  20. 2025Towards Optimal Differentially Private Regret Bounds in Linear MDPscited by 0
  21. 2025Functional Critics Are Essential for Actor-Critic: From Off-Policy Stability to Efficient Explorationcited by 0
  22. 2025Generalized Fitted Q-Iteration with Clustered Datacited by 0