Introduction
Off-Policy Evaluation (OPE) is a fundamental challenge in Reinforcement Learning (RL), particularly in domains where safety or cost constraints preclude online experimentation. The goal of OPE is to estimate the performance of a target policy $\pi$ using historical data generated by a different logging policy $\mu$. Historically, OPE has been plagued by the "Curse of Horizon," where the variance of estimators grows exponentially or high-order polynomially with the time horizon $H$.
This paper introduces Tabular-MIS (TMIS), a novel estimator for tabular Markov Decision Processes (MDPs) that achieves asymptotic efficiency. By leveraging the specific structure of tabular environments, TMIS reaches the Cramer-Rao lower bound, reducing the error scaling from the previous state-of-the-art $O(H^3/n)$ to the optimal $O(H^2/n)$.
The Curse of Horizon and Marginalized Importance Sampling
Traditional OPE methods often rely on Importance Sampling (IS), which reweights trajectories based on the likelihood ratio between the target and logging policies. In long-horizon tasks, these ratios multiply, leading to variance that explodes exponentially with $H$.
To mitigate this, Marginalized Importance Sampling (MIS) was developed. MIS focuses on state-action visitation distributions rather than full trajectories, reducing the variance growth to a polynomial factor (typically $O(H^3)$). However, theoretical analysis suggested a lower bound of $O(H^2)$ was possible for tabular settings. The gap between $H^3$ and $H^2$ remained a significant hurdle in reaching peak efficiency for tabular RL.
The Tabular-MIS (TMIS) Framework
The authors propose the TMIS estimator, which departs from previous MIS approaches by explicitly modeling the components of the MDP through a granular, component-based approach.
1. Direct Component Estimation
Instead of estimating density ratios directly, TMIS constructs empirical estimates for the transition kernel $P(s'|s, a)$ and the reward function $r(s, a)$ for every state-action pair present in the dataset.
2. Plug-in Value Estimation
Using these empirical components, the estimator reconstructs the marginalized state visitation distribution for the target policy. This "plug-in" approach allows the model to utilize the Markov property more effectively than methods that treat the environment as a black box.
3. Logging-Policy Independence
A significant advantage of TMIS is that it does not require knowledge of the logging policy $\mu$. It operates solely on the observed transitions and rewards, making it more flexible in real-world scenarios where the logging policy might be unknown or complex.
4. Split-TMIS for High-Probability Guarantees
To ensure robustness against rare, high-variance trajectories, the authors introduce Split-TMIS. This variant partitions the data into multiple folds, computes estimates on each, and averages the results. This technique allows for the derivation of high-probability error bounds, providing statistical guarantees that are essential for practical deployment.
Key Insights: Breaking the $H^3$ Barrier
The primary breakthrough of this work lies in recognizing that action observability in tabular settings is a powerful tool. Previous MIS methods often assumed a general setting that could accommodate infinite action spaces, which necessitated the use of importance weights that introduced an extra factor of $H$ into the error bound.
By explicitly accounting for the finite nature of the action space in tabular MDPs, TMIS recovers this lost efficiency. The authors prove that $H^2/n$ is the Cramer-Rao lower bound—the fundamental limit of accuracy for any unbiased estimator. TMIS is the first MIS-based estimator to achieve this limit.
Interestingly, the research also demonstrates that TMIS can outperform standard Monte Carlo estimation even in on-policy settings. By leveraging the underlying Markov structure, TMIS reduces variance more effectively than simple trajectory averaging.
Results and Empirical Evidence
The authors validated TMIS using a simulated time-varying, non-mixing tabular MDP. This synthetic environment was designed to stress-test estimators against long horizons and non-stationary dynamics.
The empirical results confirmed the theoretical predictions:
- Optimal MSE: TMIS maintained an error scaling of $O(H^2/n)$, a significant improvement over the $O(H^3/n)$ seen in prior MIS methods.
- Comparison: TMIS consistently outperformed standard IS (which failed as $H$ increased) and State-MIS (which exhibited the predicted $O(H^3)$ error growth).
- Finite-Sample Performance: The high-probability bounds were shown to hold, with error scaling at $\tilde{O}(\sqrt{H^2 SA / n})$.
Limitations and Future Work
While TMIS represents a significant step forward, it is currently limited to the tabular setting where state and action spaces are finite. Extending these efficiency gains to continuous spaces or environments requiring function approximation (such as Deep RL) remains an open challenge. Additionally, the authors acknowledge a conjecture that in infinite action spaces, the $H^3$ bound might indeed be the fundamental limit, a hypothesis that warrants further investigation.
Summary updated