🤖 machine learning

Quotient DAGs for Off-Policy Evaluation:Forward-Flow Importance Sampling and Exact Slate Propensities

This paper introduces a quotient-DAG framework and the Forward-DP algorithm to eliminate nuisance variance and enable exact computation of unordered slate propensities for efficient off-policy evaluation in autoregressive recommendation systems.

Original authors: Ziwen Xie, Shaowen Xiang, Hongyu He, Dianbo Liu

Published 2026-05-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ziwen Xie, Shaowen Xiang, Hongyu He, Dianbo Liu

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 chef trying to judge how good a new recipe (the Target Policy) would be, but you can't actually cook it in your own kitchen because it's too expensive or risky. Instead, you have a notebook full of recipes cooked by a different chef (the Behavior Policy) in the past. Your goal is to estimate how delicious the new recipe would be using only that old notebook. This is the core problem of Off-Policy Evaluation (OPE).

The Problem: Counting the Wrong Things

Usually, to judge the new recipe, you look at every single step the old chef took. You say, "Okay, they added salt, then pepper, then garlic." You calculate a score based on that exact sequence.

But here's the catch: sometimes the order in which you add ingredients doesn't actually change the taste of the final dish.

The Scenario: Imagine a "slate" of items (like a playlist of 5 songs or a tray of 5 appetizers). The customer only cares about which 5 items are on the tray, not the order the chef placed them there.
The Mistake: The old notebook records the order (Song A, then B, then C...). If you calculate your score based on that specific order, you are treating the "order" as important. But since the customer doesn't care, you are adding "noise" to your calculation.
The Result: This noise creates a huge amount of confusion (variance). It's like trying to guess the weight of a suitcase by weighing every single sock inside it individually, rather than just weighing the suitcase as a whole. You get a lot of different answers depending on how you counted the socks.

Furthermore, calculating the "true" probability of getting a specific group of 5 items (ignoring order) is a mathematical nightmare. If you have 5 items, there are 120 different ways (5 factorial) they could have been picked. Doing this math for every single entry in your notebook is computationally impossible for large groups.

The Solution: The "Quotient DAG" (The Grouping Map)

The authors propose a clever new way to look at the data. Instead of looking at every single path the chef took, they suggest grouping all the paths that lead to the same result.

The Analogy: Imagine a giant tree where every branch represents a different order of adding ingredients.
- Old Way: You walk down every single branch, measure the weight, and try to average them.
- New Way (Quotient DAG): You realize that all branches that end up with the same set of ingredients are actually the same "node" in your map. You collapse all those branches into a single point.
- The Map: This creates a "Directed Acyclic Graph" (DAG)—a map where you only care about the set of items picked so far, not the order.

The Magic Trick: Forward-Flow Importance Sampling

Once you have this simplified map, you need to know how likely the new chef is to reach a specific "set" compared to the old chef.

The Old Way: You'd have to sum up the probabilities of all 120 different orders to get the answer.
The New Way (Forward-DP): The authors invented a method called Forward-DP (Dynamic Programming). Think of this as a smart calculator that builds the answer step-by-step.
- It starts with an empty tray (probability 1).
- It asks: "If I have 1 item, what's the chance of adding a 2nd?"
- It asks: "If I have 2 items, what's the chance of adding a 3rd?"
- It keeps building up the probability of the entire set without ever needing to list out all 120 orders.

This method is exact (it doesn't guess) and fast. Instead of taking years to calculate (factorial time), it takes a manageable amount of time (exponential in the size of the tray, but polynomial in the size of the menu).

Why This Matters

Less Noise: By ignoring the irrelevant "order" details, the math becomes much cleaner. The estimates are more accurate and stable.
Feasibility: It makes it possible to evaluate complex recommendation systems (like "show me 10 movies") that were previously too hard to calculate exactly.
Real-World Test: The authors tested this on:
- Medical Data: Simulating treatments for sepsis (blood infection). Their method gave much more accurate predictions of patient outcomes than older methods.
- Recommendation Data: Using a dataset called KuaiRec (video recommendations). They showed that their method could calculate the "true" probability of a group of videos being recommended in seconds, whereas the old way would take days or be impossible.

Summary

The paper introduces a way to stop over-analyzing the "how" (the order of actions) and focus on the "what" (the final set of items). By grouping equivalent paths together and using a smart, step-by-step calculation method (Forward-DP), they can evaluate new strategies much more accurately and efficiently, especially in fields like healthcare and recommendation engines where testing new ideas in real life is too dangerous or expensive.

Technical Summary: Quotient DAGs for Off-Policy Evaluation

Problem Statement

Off-policy evaluation (OPE) estimates the performance of a target policy $\pi$ using data collected by a behavior policy $\beta$ . Standard importance sampling (IS) reweights logged trajectories by the product of target-to-behavior action-probability ratios. However, this approach often treats details of the generation process as meaningful even when the evaluation target ignores them.

A primary instance of this issue arises in slate recommendation, where modern generators often construct slates (sets of items) autoregressively, exposing per-step probabilities along a specific ordering. Yet, the reward and downstream estimators often depend only on the unordered slate. Standard trajectory IS assigns a likelihood ratio to a specific ordered path, creating a "joint-propensity gap": the logger exposes an ordering probability, while the estimator requires the total probability of the unordered slate. Computing this exact unordered propensity typically requires summing over all $K!$ generation orders, which is computationally intractable for moderate slate sizes. Furthermore, treating the ordering as significant introduces nuisance variance when the reward is invariant to the generation order.

Methodology

The paper introduces a Quotient-DAG view to address these issues. The core idea is to quotient the rollout tree of history prefixes by an equivalence relation sufficient for the evaluation target.

Quotient DAG and Forward Flow:
- The rollout tree is collapsed by merging history prefixes that are equivalent for the evaluation target (e.g., prefixes containing the same set of picked items, regardless of order).
- This forms a layered Directed Acyclic Graph (DAG) where nodes represent equivalence classes (quotient states).
- Instead of weighting by the ratio of a single realized path, the method assigns weights using the forward-flow ratio $F_\pi(z)/F_\beta(z)$ , where $F_\mu(z)$ is the probability mass reaching node $z$ under policy $\mu$ .
- This approach generalizes existing methods: per-decision IS, marginalized IS, and known-abstraction MIS are special cases corresponding to different choices of equivalence relations.
Forward-Flow Importance Sampling (FF-IS):
- For general finite-horizon OPE, the estimator replaces the sampled prefix ratio in Per-Decision IS (PDIS) with the quotient likelihood ratio.
- Theoretical analysis shows that for terminal quotient-measurable returns, this weighting removes the "within-class" target-behavior mismatch, providing an exact variance gap expression that quantifies the reduction in nuisance variance.
Forward-DP for Slate OPE:
- The paper specializes this framework to autoregressive slate generation under a set-sufficient interface (Definition 1). A policy is set-sufficient if the probability of selecting the next item depends only on the context and the set of already picked items, not their order.
- Under set-sufficiency, the permutation quotient corresponds to a subset DAG, where nodes are subsets of the catalog and edges append unpicked items.
- Forward-DP Algorithm: A dynamic programming algorithm computes the exact unordered slate propensity $F_\mu(S|x)$ $F_{μ} (S ∣ x)$ by summing over subsets rather than permutations.
  - Complexity: $O((M + K) \cdot 2^K)$ , where $M$ is the catalog size and $K$ is the slate size. This avoids the $K!$ enumeration.
  - Optimality: The paper proves that any deterministic algorithm computing exact unordered propensities for set-sufficient policies must query every proper subset of the slate in the worst case, establishing Forward-DP as query-optimal up to constant factors.

Key Contributions

Theoretical Framework: A unified quotient-DAG view for OPE that derives exact likelihood ratios as forward-flow ratios on a coarser sample space.
Algorithmic Innovation: The Forward-DP algorithm, which computes exact unordered slate propensities for context-dependent, set-sufficient autoregressive loggers in time polynomial in the catalog size and exponential in the slate size (fixed-parameter tractable in $K$ ).
Variance Reduction: A formal proof that quotient weighting removes the variance component arising from irrelevant generation orders (ordering-nuisance variance), particularly when rewards are invariant to the slate's generation sequence.
Primitives for Slate OPE: The introduction of Forward-DP as a primitive enabling exact propensity-based evaluation and model selection for transformer-based slate recommenders, closing the gap for context-dependent loggers where fixed-score Plackett-Luce formulas do not apply.

Experimental Results

The authors evaluate the method on finite-horizon MDP benchmarks and slate recommendation tasks:

Finite-Horizon MDPs (Sepsis & ICU-Sepsis):
- Forward-Flow IS (FF-IS) significantly reduces Root Mean Square Error (RMSE) compared to standard trajectory IS and other baselines (e.g., DualDICE, GenDICE).
- On the Sepsis benchmark, FF-WIS reduced RMSE from 0.291 (WIS) to 0.0568.
- These gains were achieved using only logged trajectories without fitting a transition model.
KuaiRec Slate Experiments:
- Computational Efficiency: Forward-DP computes exact propensities orders of magnitude faster than $K!$ enumeration. For $K=8$ , enumeration took ~97,108 seconds, while Forward-DP took ~8.94 seconds. For $K=12$ , enumeration is infeasible, while Forward-DP completes in ~13.7 seconds.
- Downstream OPE: Estimators using Forward-DP weights (FF-OIS, FF-DR) consistently outperformed their trajectory-weighted counterparts (OIS, DR) across all slate sizes ( $K \in \{4, 6, 8\}$ ) in terms of RMSE.
- Model Selection: In off-policy model selection among autoregressive transformer recommenders, estimators utilizing Forward-DP (e.g., Tree-DR, DP-OPCB-DR) achieved superior Top-1 accuracy, Spearman correlation, and lower regret compared to trajectory-based methods.

Significance and Claims

The paper claims that the proposed framework provides a Rao–Blackwellization of per-decision IS. By quotienting the rollout tree under sufficient equivalence relations, the method eliminates nuisance variance associated with irrelevant history details (such as generation order in slate recommendation).

Specifically for slate recommendation, the paper asserts that Forward-DP supplies the missing OPE primitive for context-dependent autoregressive loggers. Unlike previous methods that rely on fixed-score assumptions (where item scores do not change with the partial slate) or Monte Carlo approximations, Forward-DP handles the case where the next-item softmax depends on the partial slate, computing the exact joint propensity without factorial enumeration. This enables practical, exact propensity-based evaluation and model selection for modern transformer-based recommenders.

The authors note limitations, including the requirement for the set-sufficiency assumption (which may require canonicalizing the picked set in deployment) and the exponential scaling with slate size $K$ , though they argue this is practical for typical slate sizes ( $K \le 10$ ) where $K!$ is intractable.