TL;DR
This paper introduces a novel "Tabular-MIS" estimator for off-policy evaluation in reinforcement learning that achieves the theoretically optimal (Cramer-Rao) lower bound for mean-squared error, overcoming a previous $H$-factor inefficiency. They also provide a data-splitting variant that offers high-probability error bounds, making it more practical for real-world applications.
What Problem Does This Paper Address?
In reinforcement learning (RL), off-policy evaluation (OPE) is crucial for assessing the performance of a new policy using data collected by a different, "logging" policy. Traditional importance sampling (IS) methods for OPE suffer from a significant drawback: their estimation error can grow exponentially with the time horizon ($H$) of the RL problem. This "curse of horizon" limits their applicability. While marginalized importance sampling (MIS) has shown promise in mitigating this, existing MIS methods still had an estimation error that was a factor of $H$ worse than the theoretical best possible (Cramer-Rao lower bound). This paper aims to close this gap, achieving the optimal asymptotic efficiency for OPE in tabular settings.
Methods
The core contribution is a modified MIS estimator, termed Tabular-MIS (TMIS). Unlike previous methods that might struggle with finite sample guarantees or require explicit knowledge of the logging policy, TMIS leverages the tabular setting (finite states and actions) to achieve better performance. A key technique involves a "fictitious" estimator that bridges the gap between the observed data and the true value function, allowing for theoretical analysis. The paper also introduces a data-splitting TMIS variant. This approach partitions the available data into multiple folds, computes TMIS on each fold, and then averages the results. This technique is crucial for deriving high-probability error bounds, as it allows for the application of standard concentration inequalities.
Datasets
Not discussed in the paper. The experiments use a simulated time-varying, non-mixing tabular MDP environment.
Key Insights and Ideas
- Breaking the $H$-factor inefficiency: The paper demonstrates that by carefully modifying MIS, it's possible to achieve the optimal $O(H^2/n)$ MSE bound, matching the Cramer-Rao lower bound, which was previously thought to be unattainable for MIS in this setting.
- Tabular setting is key: The finite state and action spaces in tabular MDPs are exploited to construct more efficient estimators, going beyond simple importance weighting.
- Data splitting for high-probability guarantees: The introduction of data splitting is a significant practical contribution, enabling the derivation of high-probability error bounds which are essential for reliable decision-making in real-world applications.
- Logging policy-free implementation: The proposed TMIS estimator can be implemented without knowing the exact behavior policy, making it more practical when such information is unavailable or unreliable.
Key Results
- The proposed Tabular-MIS (TMIS) estimator achieves an asymptotic mean-squared error (MSE) that matches the Cramer-Rao lower bound, specifically $O(H^2/n)$, for tabular MDPs with finite state and action spaces. This is a significant improvement over prior MIS methods that had an $O(H^3/n)$ bound.
- A data-splitting TMIS estimator is introduced, which provides high-probability error bounds of $O(\sqrt{H^2SA/n})$. This is the first IS-based OPE estimator to achieve such guarantees.
- The paper shows that TMIS is asymptotically, locally, uniformly minimax optimal, meaning it's optimal for every problem instance.
- Empirical results on a simulated non-stationary MDP show that TMIS outperforms the State-MIS estimator in terms of relative RMSE, especially as the horizon $H$ increases.
Limitations and Future Work
- Tabular setting: The current work is limited to tabular MDPs. Generalizing these techniques to function approximation settings (e.g., deep RL) remains an open challenge.
- Infinite action spaces: The paper's achievement of the Cramer-Rao bound relies on the action space being finite. The problem of achieving optimal OPE in settings with infinite action spaces is still open.
- Model-based assumption: The TMIS estimator, by estimating transition dynamics, can be seen as a model-based approach. While it achieves model-free performance guarantees, further exploration of purely model-free methods with similar efficiency is warranted.
- Future work: The authors suggest resolving the open problems mentioned above and generalizing the techniques to more practical settings.
Summary updated