# A Complete Characterization of Linear Estimators for Offline Policy Evaluation

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 64 references that are in the map.
- First posted on arXiv 8 Mar 2022.

## Builds on (most cited first, 29 of 29)

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation](https://mlsanity.com/paper/1810.12429/) (2018)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Minimax Weight and Q-Function Learning for Off-Policy Evaluation](https://mlsanity.com/paper/1910.12809/) (2019)
- [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019)
- [What are the Statistical Limits of Offline RL with Linear Function Approximation?](https://mlsanity.com/paper/2010.11895/) (2020)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Offline Reinforcement Learning with Realizability and Single-policy Concentrability](https://mlsanity.com/paper/2202.04634/) (2022)
- [Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation](https://mlsanity.com/paper/2002.09516/) (2020)
- [Batch Value-function Approximation with Only Realizability](https://mlsanity.com/paper/2008.04990/) (2020)
- [Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions](https://mlsanity.com/paper/2010.01374/) (2020)
- [Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation](https://mlsanity.com/paper/2111.10919/) (2021)
- [Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learning](https://mlsanity.com/paper/2001.10742/) (2020)
- [Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms](https://mlsanity.com/paper/2006.08916/) (2020)
- [Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL](https://mlsanity.com/paper/2012.08005/) (2020)
- [An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap](https://mlsanity.com/paper/2103.12690/) (2021)
- [Instabilities of Offline RL with Pre-Trained Neural Representation](https://mlsanity.com/paper/2103.04947/) (2021)
- [Optimal and instance-dependent guarantees for Markovian linear stochastic approximation](https://mlsanity.com/paper/2112.12770/) (2021)
- [Least-Squares Temporal Difference Learning for the Linear Quadratic Regulator](https://mlsanity.com/paper/1712.08642/) (2017)
- [A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Setting](https://mlsanity.com/paper/2011.01075/) (2020)
- [Stabilizing Dynamical Systems via Policy Gradient Methods](https://mlsanity.com/paper/2110.06418/) (2021)
- [Optimal policy evaluation using kernel-based temporal difference methods](https://mlsanity.com/paper/2109.12002/) (2021)
- [Accelerated and instance-optimal policy evaluation with linear function approximation](https://mlsanity.com/paper/2112.13109/) (2021)
- [Comments on the Du-Kakade-Wang-Yang Lower Bounds](https://mlsanity.com/paper/1911.07910/) (2019)
- [Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond](https://mlsanity.com/paper/1912.11071/) (2019)
- [Optimal oracle inequalities for solving projected fixed-point equations](https://mlsanity.com/paper/2012.05299/) (2020)

## Built on by (most cited first, 7 of 7)

- [On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluation](https://mlsanity.com/paper/2402.14703/) (2024)
- [Offline Reinforcement Learning in Large State Spaces: Algorithms and Guarantees](https://mlsanity.com/paper/2510.04088/) (2025)
- [Model Selection for Off-policy Evaluation: New Algorithms and Experimental Protocol](https://mlsanity.com/paper/2502.08021/) (2025)
- [A Unifying View of Coverage in Linear Off-Policy Evaluation](https://mlsanity.com/paper/2601.19030/) (2026)
- [Generalized Fitted Q-Iteration with Clustered Data](https://mlsanity.com/paper/2510.03912/) (2025)
- [Q-MMR: Off-Policy Evaluation via Recursive Reweighting and Moment Matching](https://mlsanity.com/paper/2605.06474/) (2026)
- [A Distribution Mapping Approach to Counterfactually Fair Reinforcement Learning](https://mlsanity.com/paper/2608.08743/) (2026)

## Abstract (arXiv)

Offline policy evaluation is a fundamental statistical problem in reinforcement learning that involves estimating the value function of some decision-making policy given data collected by a potentially different policy. In order to tackle problems with complex, high-dimensional observations, there has been significant interest from theoreticians and practitioners alike in understanding the possibility of function approximation in reinforcement learning. Despite significant study, a sharp characterization of when we might expect offline policy evaluation to be tractable, even in the simplest setting of linear function approximation, has so far remained elusive, with a surprising number of strong negative results recently appearing in the literature. In this work, we identify simple control-theoretic and linear-algebraic conditions that are necessary and sufficient for classical methods, in particular Fitted Q-iteration (FQI) and least squares temporal difference learning (LSTD), to succeed at offline policy evaluation. Using this characterization, we establish a precise hierarchy of regimes under which these estimators succeed. We prove that LSTD works under strictly weaker conditions than FQI. Furthermore, we establish that if a problem is not solvable via LSTD, then it cannot be solved by a broad class of linear estimators, even in the limit of infinite data. Taken together, our results provide a complete picture of the behavior of linear estimators for offline policy evaluation, unify previously disparate analyses of canonical algorithms, and provide significantly sharper notions of the underlying statistical complexity of offline policy evaluation.