# Variance-Aware Off-Policy Evaluation with Linear Function Approximation

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

## 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 (most cited first, 30 of 32)

- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [Stabilizing Off-Policy Q-Learning via Bootstrapping Error Reduction](https://mlsanity.com/paper/1906.00949/) (2019)
- [MOReL : Model-Based Offline Reinforcement Learning](https://mlsanity.com/paper/2005.05951/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Doubly Robust Off-policy Value Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1511.03722/) (2015)
- [Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1604.00923/) (2016)
- [DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections](https://mlsanity.com/paper/1906.04733/) (2019)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation](https://mlsanity.com/paper/1810.12429/) (2018)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [AlgaeDICE: Policy Gradient from Arbitrary Experience](https://mlsanity.com/paper/1912.02074/) (2019)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [More Robust Doubly Robust Off-policy Evaluation](https://mlsanity.com/paper/1802.03493/) (2018)
- [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [GenDICE: Generalized Offline Estimation of Stationary Values](https://mlsanity.com/paper/2002.09072/) (2020)
- [Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation](https://mlsanity.com/paper/2002.09516/) (2020)
- [Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling](https://mlsanity.com/paper/1906.03393/) (2019)
- [Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping](https://mlsanity.com/paper/2006.13165/) (2020)
- [Logarithmic Regret for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2011.11566/) (2020)
- [Efficiently Breaking the Curse of Horizon in Off-Policy Evaluation with Double Reinforcement Learning](https://mlsanity.com/paper/1909.05850/) (2019)
- [CoinDICE: Off-Policy Confidence Interval Estimation](https://mlsanity.com/paper/2010.11652/) (2020)
- [Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learning](https://mlsanity.com/paper/2001.10742/) (2020)
- [Near-Optimal Offline Reinforcement Learning via Double Variance Reduction](https://mlsanity.com/paper/2102.01748/) (2021)
- [A Unifying View of Optimism in Episodic Reinforcement Learning](https://mlsanity.com/paper/2007.01891/) (2020)
- [Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimation](https://mlsanity.com/paper/1910.07186/) (2019)
- [Instabilities of Offline RL with Pre-Trained Neural Representation](https://mlsanity.com/paper/2103.04947/) (2021)
- [Deep Reinforcement Learning for Vision-Based Robotic Grasping: A Simulated Comparative Evaluation of Off-Policy Methods](https://mlsanity.com/paper/1802.10264/) (2018)

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

- [Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism](https://mlsanity.com/paper/2203.05804/) (2022)
- [Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game](https://mlsanity.com/paper/2205.15512/) (2022)
- [Provable Benefit of Multitask Representation Learning in Reinforcement Learning](https://mlsanity.com/paper/2206.05900/) (2022)
- [Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processes](https://mlsanity.com/paper/2205.13589/) (2022)
- [Learning Stochastic Shortest Path with Linear Function Approximation](https://mlsanity.com/paper/2110.12727/) (2021)
- [On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2211.13208/) (2022)
- [Offline Reinforcement Learning with Differential Privacy](https://mlsanity.com/paper/2206.00810/) (2022)
- [Accelerated and instance-optimal policy evaluation with linear function approximation](https://mlsanity.com/paper/2112.13109/) (2021)
- [Off-Policy Fitted Q-Evaluation with Differentiable Function Approximators: Z-Estimation and Inference Theory](https://mlsanity.com/paper/2202.04970/) (2022)
- [Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learning](https://mlsanity.com/paper/2403.09621/) (2024)
- [Learn to Match with No Regret: Reinforcement Learning in Markov Matching Markets](https://mlsanity.com/paper/2203.03684/) (2022)
- [Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2210.00701/) (2022)
- [Sample Complexity of Nonparametric Off-Policy Evaluation on Low-Dimensional Manifolds using Deep Networks](https://mlsanity.com/paper/2206.02887/) (2022)
- [Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficient](https://mlsanity.com/paper/2210.00750/) (2022)
- [Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation](https://mlsanity.com/paper/2305.06446/) (2023)
- [Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learning](https://mlsanity.com/paper/2310.01380/) (2023)
- [Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewards](https://mlsanity.com/paper/2303.05606/) (2023)
- [Robust Offline Reinforcement learning with Heavy-Tailed Rewards](https://mlsanity.com/paper/2310.18715/) (2023)
- [Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learning](https://mlsanity.com/paper/2407.07631/) (2024)
- [Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPs](https://mlsanity.com/paper/2408.04526/) (2024)
- [Finding Regularized Competitive Equilibria of Heterogeneous Agent Macroeconomic Models with Reinforcement Learning](https://mlsanity.com/paper/2303.04833/) (2023)
- [Regularization and Variance-Weighted Regression Achieves Minimax Optimality in Linear MDPs: Theory and Practice](https://mlsanity.com/paper/2305.13185/) (2023)
- [VIPeR: Provably Efficient Algorithm for Offline RL with Neural Function Approximation](https://mlsanity.com/paper/2302.12780/) (2023)
- [Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2310.18919/) (2023)
- [Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability](https://mlsanity.com/paper/2605.09214/) (2026)
- [Cascaded Gaps: Towards Gap-Dependent Regret for Risk-Sensitive Reinforcement Learning](https://mlsanity.com/paper/2203.03110/) (2022)
- [Multiscale replay: A robust algorithm for stochastic variational inequalities with a Markovian buffer](https://mlsanity.com/paper/2601.01502/) (2026)
- [Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path](https://mlsanity.com/paper/2402.08998/) (2024)
- [Reweighting Improves Conditional Risk Bounds](https://mlsanity.com/paper/2501.02353/) (2025)
- [Statistical Estimation of Confounded Linear MDPs: An Instrumental Variable Approach](https://mlsanity.com/paper/2209.05186/) (2022)

## 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.