📊 statistics

Q-MMR: Off-Policy Evaluation via Recursive Reweighting and Moment Matching

This paper introduces Q-MMR, a novel off-policy evaluation framework for finite-horizon MDPs that learns inductive scalar weights via recursive moment matching to achieve dimension-free finite-sample guarantees under the realizability of the target Q-function, while offering new theoretical insights into coverage and connections to existing methods like importance sampling.

Original authors: Xiang Li, Nan Jiang

Published 2026-05-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Xiang Li, Nan Jiang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to figure out how good a new strategy (let's call it the "Target Policy") would be at winning a game. However, you don't have any data from playing the game with that new strategy. Instead, you only have a stack of old game logs recorded by a different, perhaps clumsy, player (the "Behavior Policy").

Your goal is Off-Policy Evaluation (OPE): Estimate the score of the new strategy using only the old logs.

The Problem: The "Apples vs. Oranges" Mismatch

The old logs are full of mistakes the clumsy player made. If you just average the scores from the old logs, you'll get the wrong answer because the new strategy plays differently.

Usually, statisticians try to fix this by "reweighting" the data. They say, "Okay, this specific move in the old log is rare for the clumsy player but common for the new strategy, so let's count it 10 times." Or, "This move is common for the clumsy player but the new strategy never does it, so let's ignore it."

The tricky part is: How do you calculate the right weights?

If you try to calculate the exact probability ratio (Importance Sampling), the numbers can get huge and unstable, like trying to balance a house of cards in a hurricane.
If you use complex math to approximate the value of the game (Fitted-Q Evaluation), traditional theories say you need a massive amount of data, and the complexity of your math model makes the error bound worse and worse.

The Solution: Q-MMR (The "Top-Down" Reweighting)

The paper introduces a new method called Q-MMR. Think of it as a "Top-Down" approach to fixing the data.

Instead of trying to guess the perfect weight for every single move all at once, Q-MMR builds the weights step-by-step, from the beginning of the game to the end.

The Analogy: The "Moment Matching" Game
Imagine you are trying to make a crowd of people (the old data) look and act exactly like a different crowd (the new strategy).

The Goal: You want the average behavior of your weighted old crowd to match the new crowd's behavior.
The Judge: You have a "Judge" (a function class) who can spot the difference between the two crowds.
The Process:
- At the start of the game, the weights are simple (everyone counts as 1).
- As you move to the next step, you adjust the weights of the current moves so that, when the Judge looks at them, they can't tell the difference between the "weighted old moves" and what the "new strategy" would have done.
- You do this recursively. You fix the weights for step 1, then use those to fix step 2, and so on.

The paper calls this Moment Matching. You are matching the "moments" (statistical averages) of the data to the target policy, but you do it in a way that is very forgiving.

The Big Surprise: "Dimension-Free" Guarantees

Here is the most exciting part of the paper.

In the past, if you used complex math models (like neural networks) to solve this, the theory said: "The more complex your model is, the more data you need, and the higher your error will be." It was like saying, "The more ingredients you add to a soup, the more likely it is to taste bad unless you have a huge pot."

Q-MMR breaks this rule.
The authors prove that even if you use a very complex model to find these weights, the error does not depend on the complexity of the model.

The Metaphor: Imagine you are trying to hit a target with a bow and arrow. Old theories said, "The more complicated your bow is, the harder it is to hit the target." Q-MMR says, "Actually, as long as the target exists (a concept called Realizability), you can hit it with the same precision, regardless of how fancy your bow is."

This is a huge deal because it means we can use powerful, complex AI models without worrying that the math will break down due to their complexity.

Why It Works: The "Fixed Design" Trick

The paper uses a clever mathematical trick borrowed from simple linear regression (like drawing a straight line through dots).

Usually, when analyzing complex AI, we have to worry about the "statistical dimension" (how many ways the model can wiggle).
Q-MMR treats the data points as "fixed" and only looks at the randomness of the rewards. This allows them to skip the messy parts of the math that usually cause the error to explode.

The "Coverage" Insight

The paper also sheds light on a concept called Coverage.

Old View: To evaluate a new strategy, the old data must cover every single move the new strategy might make.
New View (from this paper): You don't need to cover every move. You only need to cover the specific "directions" that matter for the math to work. It's like saying you don't need to know the weather in every city on Earth to predict the weather in your town; you just need to know the weather patterns that actually influence your town.

Summary

Q-MMR is a new way to evaluate a robot's (or game player's) potential performance using old, imperfect data.

It learns a set of weights for the data points, one by one, from start to finish.
It ensures the weighted data "looks like" the new strategy to a mathematical judge.
Crucially, it proves that this method works well even with very complex models, without the error getting worse as the model gets more complex.
It provides a built-in "confidence score" (uncertainty quantification) that you can calculate directly from the data.

In short, it's a smarter, more robust way to say, "Based on what we saw the clumsy player do, here is exactly how well the new pro player would have done."

Technical Summary: Q-MMR: Off-Policy Evaluation via Recursive Reweighting and Moment Matching

1. Problem Statement

The paper addresses Off-Policy Evaluation (OPE) in finite-horizon Markov Decision Processes (MDPs). The goal is to estimate the expected return $J(\pi)$ of a target policy $\pi$ using a dataset collected from a behavior policy $\pi_D$ . The setting involves General Function Approximation (GFA), where a function class $\mathcal{F}$ is used to model the target policy's Q-function, $Q^\pi$ .

The authors identify two primary theoretical gaps in existing OPE literature:

Dimension Dependence: Standard analyses for GFA (e.g., Fitted-Q Evaluation, FQE) typically yield error bounds that depend on the statistical complexity of the function class (e.g., $\log |\mathcal{F}|$ or covering numbers). This dependence is often loose, particularly in on-policy settings where Monte-Carlo estimates are dimension-free.
Inconsistency with Linear/Tabular Analyses: Refined, dimension-free guarantees exist for linear and tabular settings (often under realizability alone), but these results do not naturally extend to general function classes. Furthermore, linear analyses often rely on weaker conditions (realizability) compared to the Bellman-completeness assumptions required for general GFA analyses.

2. Methodology: Q-MMR

The authors propose Q-MMR (Q-function-based Moment-Matched Reweighting), a novel algorithmic framework that learns a set of scalar weights, one for each data point, inductively in a top-down manner.

Algorithm Overview

Given $n$ i.i.d. trajectories and a function class $\mathcal{F} = \{\mathcal{F}_h\}_{h=1}^H$ :

Initialization: Set weights $w^{(i)}_0 \equiv 1$ for all data points $i$ (since the initial state-action pair is fixed).
Recursive Reweighting: For each time step $h = 1$ to $H$ , the algorithm learns a weight vector $w^{[n]}_h = \{w^{(i)}_h\}_{i=1}^n$ by solving a minimax optimization problem:
$\hat{w}^{[n]}_h = \arg\min_{w^{[n]}_h} \sup_{f \in \mathcal{F}_h} \left| \frac{1}{n} \sum_{i=1}^n w^{(i)}_h f(s^{(i)}_h, a^{(i)}_h) - \frac{1}{n} \sum_{i=1}^n \hat{w}^{(i)}_{h-1} f(s^{(i)}_h, \pi) \right|$
This objective minimizes the discrepancy (via an Integral Probability Metric) between the reweighted distribution of the current state-action pairs and the reweighted distribution of the next state under the target policy.
Estimation: The final estimate of the return is the reweighted sum of rewards:
$\hat{J}(\pi) = \frac{1}{n} \sum_{i=1}^n \sum_{h=1}^H w^{(i)}_h r^{(i)}_h$

Key Design Choices

Non-Parametric Weights: Unlike Marginalized Importance Sampling (MIS) methods that learn a parametric function for weights, Q-MMR learns a distinct scalar for each data point.
Least 2nd-Moment Principle: Since the minimizer of the matching loss is generally not unique, the algorithm selects the solution with the minimum empirical 2nd moment ( $\|w^{[n]}_h\|_{[n]}$ ) to control variance.
Top-Down Induction: The weights are computed level-by-level from $h=0$ to $H$ , relying on the weights from the previous step.

3. Key Contributions and Theoretical Results

A. Dimension-Free Finite-Sample Guarantee

The primary theoretical contribution is Theorem 1, which provides a data-dependent finite-sample bound for the OPE error. Under the standard Realizability Assumption ( $Q^\pi \in \mathcal{F}$ ), with probability at least $1-\delta$ :
$|\hat{J}(\pi) - J(\pi)| \leq \sum_{h=1}^H \hat{L}_h(\hat{w}^{[n]}_h; \hat{w}^{[n]}_{h-1}) + \sum_{h=0}^H \epsilon^{\text{stat}}_h$
where:

$\hat{L}_h$ is the empirical matching loss achieved by the algorithm.
$\epsilon^{\text{stat}}_h \propto \| \hat{w}^{[n]}_h \|_{[n]} \sqrt{\frac{\log(1/\delta)}{n}}$ .

Significance:

Dimension-Free: The bound does not explicitly depend on the statistical complexity of $\mathcal{F}$ (e.g., no $\log |\mathcal{F}|$ term) in the leading order. This is achieved by avoiding union bounds over the function class and instead relying on concentration arguments specific to the realized weights.
WYSIWYG (What You See Is What You Get): The bound is directly computable from the data, as it depends on the observed matching loss and the 2nd moment of the learned weights.
Weaker Assumptions: The guarantee holds under Realizability alone, without requiring the stronger Bellman-completeness assumption typically needed for GFA.

B. Connection to Existing Methods

The paper establishes that Q-MMR unifies and recovers known results in special cases:

Linear and Tabular Settings: When specialized to linear function classes (with invertible sample covariance) or tabular settings, Q-MMR coincides with Linear FQE and Tabular FQE (or model-based certainty-equivalence), respectively.
Recovery of Fine-Grained Bounds: In these special cases, the Q-MMR analysis recovers the dimension-free, $O(1/\sqrt{n})$ rates found in prior linear/tabular literature (e.g., Duan et al., 2020; Yin and Wang, 2021), bridging the gap between general and linear analyses.
Monte-Carlo and Importance Sampling: In on-policy settings, setting weights to 1 recovers the Monte-Carlo estimator. With specific modifications, it can also recover step-wise importance sampling.

C. Insights into Coverage

The paper provides a deeper theoretical understanding of coverage in offline RL:

Weight Magnitude as Coverage: The term $\|w^{[n]}_h\|_{[n]}$ (and its population counterpart $\|w^\star_h\|_{2, d_D}$ ) acts as an empirical coverage parameter.
Nature of Coverage: Through further analysis (Section 4), the authors show that the "coverage" required is not merely the coverage of the target policy's feature occupancy $E_{d^\pi}[\phi]$ , but rather the coverage of a vector defined by a specific linear dynamical system (analogous to $\psi_h$ in linear analyses).
Bellman Completeness: Under Bellman completeness, the population weights $w^\star_h$ perfectly recover the target distribution $d^\pi_h$ , and the stability term controlling weight blow-up is bounded by 1. Without completeness, the stability depends on the operator norm of projected transition operators, which can lead to exponential weight growth if the system is unstable.

4. Significance and Claims

The paper claims to provide a unified theoretical framework that resolves the tension between general function approximation and linear/tabular analyses in OPE.

Unification: It demonstrates that the "dimension-free" properties observed in linear/tabular settings are not artifacts of linearity but can be achieved in general settings under realizability, provided one uses a moment-matching approach with non-parametric weights.
Novelty of Analysis: The analysis is described as "starkly simple," avoiding complex union bounds over the function class. It leverages the telescoping nature of the Bellman equation and the specific structure of the moment-matching objective.
Practical Implications: The data-dependent bound offers a built-in mechanism for uncertainty quantification, as the error bound is computable from the dataset without needing to know the true complexity of the function class.

The authors note limitations, including the requirement for i.i.d. trajectory data (which breaks down in adaptive collection) and the greedy, local nature of the weight optimization (which does not explicitly account for downstream effects, though this is a trade-off to avoid double-sampling issues found in other MIS methods).

In summary, Q-MMR offers a theoretically rigorous, dimension-free approach to OPE that generalizes the favorable properties of linear methods to general function classes while relying only on realizability.