# Scaling Marginalized Importance Sampling to High-Dimensional State-Spaces via State Abstraction

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 57 references that are in the map.
- First posted on arXiv 14 Dec 2022.

## Builds on (most cited first, 30 of 33)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [D4RL: Datasets for Deep Data-Driven Reinforcement Learning](https://mlsanity.com/paper/2004.07219/) (2020)
- [Learning Invariant Representations for Reinforcement Learning without Reconstruction](https://mlsanity.com/paper/2006.10742/) (2020)
- [Doubly Robust Off-policy Value Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1511.03722/) (2015)
- [Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1604.00923/) (2016)
- [DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections](https://mlsanity.com/paper/1906.04733/) (2019)
- [Batch Policy Learning under Constraints](https://mlsanity.com/paper/1903.08738/) (2019)
- [Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation](https://mlsanity.com/paper/1810.12429/) (2018)
- [DeepMDP: Learning Continuous Latent Space Models for Representation Learning](https://mlsanity.com/paper/1906.02736/) (2019)
- [Minimax Weight and Q-Function Learning for Off-Policy Evaluation](https://mlsanity.com/paper/1910.12809/) (2019)
- [Scalable methods for computing state similarity in deterministic Markov Decision Processes](https://mlsanity.com/paper/1911.09291/) (2019)
- [Offline Reinforcement Learning with Realizability and Single-policy Concentrability](https://mlsanity.com/paper/2202.04634/) (2022)
- [GenDICE: Generalized Offline Estimation of Stationary Values](https://mlsanity.com/paper/2002.09072/) (2020)
- [Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1911.06854/) (2019)
- [Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling](https://mlsanity.com/paper/1906.03393/) (2019)
- [Hyperparameter Selection for Offline Reinforcement Learning](https://mlsanity.com/paper/2007.09055/) (2020)
- [Benchmarks for Deep Off-Policy Evaluation](https://mlsanity.com/paper/2103.16596/) (2021)
- [Off-Policy Evaluation via the Regularized Lagrangian](https://mlsanity.com/paper/2007.03438/) (2020)
- [GradientDICE: Rethinking Generalized Offline Estimation of Stationary Values](https://mlsanity.com/paper/2001.11113/) (2020)
- [Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism](https://mlsanity.com/paper/2203.05804/) (2022)
- [Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learning](https://mlsanity.com/paper/2001.10742/) (2020)
- [Consistent On-Line Off-Policy Evaluation](https://mlsanity.com/paper/1702.07121/) (2017)
- [Off-Policy Deep Reinforcement Learning by Bootstrapping the Covariate Shift](https://mlsanity.com/paper/1901.09455/) (2019)
- [Instabilities of Offline RL with Pre-Trained Neural Representation](https://mlsanity.com/paper/2103.04947/) (2021)
- [Understanding the Curse of Horizon in Off-Policy Evaluation via Conditional Importance Sampling](https://mlsanity.com/paper/1910.06508/) (2019)
- [Importance Sampling Policy Evaluation with an Estimated Behavior Policy](https://mlsanity.com/paper/1806.01347/) (2018)
- [Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gaps](https://mlsanity.com/paper/2203.13935/) (2022)
- [Autoregressive Dynamics Models for Offline Policy Evaluation and Optimization](https://mlsanity.com/paper/2104.13877/) (2021)
- [A Theory of Abstraction in Reinforcement Learning](https://mlsanity.com/paper/2203.00397/) (2022)

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

- [State-Action Similarity-Based Representations for Off-Policy Evaluation](https://mlsanity.com/paper/2310.18409/) (2023)
- [Off-policy Evaluation with Deeply-abstracted States](https://mlsanity.com/paper/2406.19531/) (2024)
- [Abstract Reward Processes: Leveraging State Abstraction for Consistent Off-Policy Evaluation](https://mlsanity.com/paper/2410.02172/) (2024)
- [Concept-driven Off Policy Evaluation](https://mlsanity.com/paper/2411.19395/) (2024)
- [Quotient DAGs for Off-Policy Evaluation:Forward-Flow Importance Sampling and Exact Slate Propensities](https://mlsanity.com/paper/2605.29500/) (2026)
- [Stable Offline Value Function Learning with Bisimulation-based Representations](https://mlsanity.com/paper/2410.01643/) (2024)
- [Where to Intervene: Action Selection in Deep Reinforcement Learning](https://mlsanity.com/paper/2507.04187/) (2025)

## Abstract (arXiv)

We consider the problem of off-policy evaluation (OPE) in reinforcement learning (RL), where the goal is to estimate the performance of an evaluation policy, πe, using a fixed dataset, D, collected by one or more policies that may be different from πe. Current OPE algorithms may produce poor OPE estimates under policy distribution shift i.e., when the probability of a particular state-action pair occurring under πe is very different from the probability of that same pair occurring in D (Voloshin et al. 2021, Fu et al. 2021). In this work, we propose to improve the accuracy of OPE estimators by projecting the high-dimensional state-space into a low-dimensional state-space using concepts from the state abstraction literature. Specifically, we consider marginalized importance sampling (MIS) OPE algorithms which compute state-action distribution correction ratios to produce their OPE estimate. In the original ground state-space, these ratios may have high variance which may lead to high variance OPE. However, we prove that in the lower-dimensional abstract state-space the ratios can have lower variance resulting in lower variance OPE. We then highlight the challenges that arise when estimating the abstract ratios from data, identify sufficient conditions to overcome these issues, and present a minimax optimization problem whose solution yields these abstract ratios. Finally, our empirical evaluation on difficult, high-dimensional state-space OPE tasks shows that the abstract ratios can make MIS OPE estimators achieve lower mean-squared error and more robust to hyperparameter tuning than the ground ratios.