# The Optimal Approximation Factors in Misspecified Off-Policy Value Function Estimation

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 43 references that are in the map.
- First posted on arXiv 25 Jul 2023.

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

- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation](https://mlsanity.com/paper/1810.12429/) (2018)
- [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)
- [Representation Learning for Online and Offline RL in Low-rank MDPs](https://mlsanity.com/paper/2110.04652/) (2021)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [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)
- [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)
- [Optimal policy evaluation using kernel-based temporal difference methods](https://mlsanity.com/paper/2109.12002/) (2021)
- [Optimal oracle inequalities for solving projected fixed-point equations](https://mlsanity.com/paper/2012.05299/) (2020)
- [Beyond the Return: Off-policy Function Estimation under User-specified Error-measuring Distributions](https://mlsanity.com/paper/2210.15543/) (2022)

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

- [Model Selection for Off-policy Evaluation: New Algorithms and Experimental Protocol](https://mlsanity.com/paper/2502.08021/) (2025)
- [Mitigating Covariate Shift in Misspecified Regression with Applications to Reinforcement Learning](https://mlsanity.com/paper/2401.12216/) (2024)
- [A Unifying View of Coverage in Linear Off-Policy Evaluation](https://mlsanity.com/paper/2601.19030/) (2026)

## Abstract (arXiv)

Theoretical guarantees in reinforcement learning (RL) are known to suffer multiplicative blow-up factors with respect to the misspecification error of function approximation. Yet, the nature of such approximation factors -- especially their optimal form in a given learning problem -- is poorly understood. In this paper we study this question in linear off-policy value function estimation, where many open questions remain. We study the approximation factor in a broad spectrum of settings, such as with the weighted L2-norm (where the weighting is the offline state distribution), the L_∞ norm, the presence vs. absence of state aliasing, and full vs. partial coverage of the state space. We establish the optimal asymptotic approximation factors (up to constants) for all of these settings. In particular, our bounds identify two instance-dependent factors for the L2(μ) norm and only one for the L_∞ norm, which are shown to dictate the hardness of off-policy evaluation under misspecification.