Introduction
In reinforcement learning (RL), theoretical guarantees often rely on the "realizability" assumption—the premise that the true value function of a policy resides perfectly within a chosen function class. In practice, however, models are almost always misspecified. When the function class (such as a linear model) cannot perfectly represent the value function, estimation errors can experience significant multiplicative blow-up. This phenomenon is particularly critical in Off-Policy Evaluation (OPE), where an agent estimates the value of a target policy using data generated by a different behavior policy.
This paper establishes the fundamental limits of this error magnification. By identifying instance-dependent approximation factors, the authors determine the best possible performance any estimator can achieve under misspecification and demonstrate that the classic Least Squares Temporal Difference (LSTD) algorithm is often as effective as any possible estimator.
Theoretical Framework
The research focuses on linear off-policy value function estimation within infinite-horizon discounted Markov Reward Processes (MRPs). The authors analyze the "approximation factor"—the ratio between the error of a specific algorithm and the best possible approximation error achievable within the given function class.
The study evaluates these factors across two primary metrics:
- Weighted $L_2(\mu)$ norm: Measuring error on states according to their frequency in the observed data distribution (the behavior policy).
- $L_\infty$ norm: Measuring the worst-case error across all possible states in the state space.
Methodology
To derive these limits, the authors utilize a combination of exact error decomposition and lower-bound constructions:
- LSTD Analysis: The authors provide a new error decomposition for the population-level LSTD algorithm, identifying the specific mathematical properties of an RL instance that drive error.
- Lower Bound Construction: To prove that their identified factors are indeed optimal, the authors construct "hard" synthetic MRP instances (typically involving 2 to 5 states). These instances demonstrate that two different environments can produce identical data but possess different true value functions, making them indistinguishable to any learner and setting a floor on achievable error.
- Comparative Estimators: Beyond LSTD, the authors investigate model-based estimators, particularly in scenarios where the data distribution provides full support over the state space.
Key Insights and Results
The Two Failure Modes of LSTD
For the $L_2(\mu)$ norm, the research identifies two distinct factors that contribute to error blow-up:
- Pushforward Coverage ($\|\Pi_\mu P\|_\mu$): This factor quantifies the risk of states in the data distribution transitioning to states that are poorly represented in the data.
- Feature Geometry ($\sigma_{min}$): A condition number representing the geometric relationship between the feature space and the transitions.
A significant finding is that LSTD is fundamentally robust: if LSTD diverges on a specific problem, the authors prove that any other estimator would also face an infinite approximation factor in that same setting.
The $L_\infty$ Surprise
Counter-intuitively, the $L_\infty$ norm—often considered a more stringent requirement—depends only on the feature geometry factor ($\sigma_{min}(A)$). The authors explain that because a small $L_\infty$ error is a much stronger constraint, it inherently accounts for the "pushforward" issues that must be explicitly tracked in the $L_2$ case.
Model-Based Superiority in Full Support
In scenarios where every state is visited at least once (full support), the authors find that model-based estimators using state abstractions can outperform LSTD. Specifically, they can achieve an approximation factor of $2/(1-\gamma)$, which remains independent of the feature geometry—a significant advantage in regimes where the geometry is poorly conditioned.
Summary of Optimal Factors
The paper concludes that the optimal asymptotic approximation factors ($\alpha^\star$) are:
- In $L_2(\mu)$: LSTD is optimal up to constants, with error scaling based on the ratio of pushforward coverage to the minimum singular value of the transition-adjusted feature matrix.
- In $L_\infty$: The optimal factor is approximately $1 + \frac{1+\gamma}{\sigma_{min}(A)}$.
- Full Support: The factor becomes $1/(2(1-\gamma))$ for aliased states and exactly $1$ for non-aliased states.
Conclusion and Future Directions
While this work provides a definitive map of the limits of linear off-policy evaluation, several avenues for future research remain. The current results are specific to linear function approximation; extending these optimal factors to non-linear models, such as deep neural networks, is a significant open challenge. Additionally, while this paper addresses the evaluation of a fixed policy, the "control" problem—finding the optimal policy—introduces further complexities and hardness results that warrant future investigation under similar misspecification frameworks.
Summary updated