Quotient DAGs for Off-Policy Evaluation: Forward-Flow Importance Sampling and Exact Slate Propensities
Ziwen Xie, Shaowen Xiang, Hongyu He, Dianbo Liu · 2026
Read Quotient DAGs for Off-Policy Evaluation: Forward-Flow Importance Sampling and Exact Slate Propensities by Ziwen Xie, Shaowen Xiang, Hongyu He, Dianbo Liu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-29500.txt.
Introduction
Ziwen Xie and three colleagues reframe off-policy evaluation with quotient DAGs, merging runs the review cannot tell apart. Importance sampling reweights runs but counts build details even when rewards ignore them. An autoregressive slate recommender orders items while only the unordered slate matters. That mismatch adds nuisance variance and makes exact slate probabilities costly. Their quotient-DAG view assigns weights with target-side forward-flow ratios over the merged graph, for usable reviews and model choice. A subset-DAG dynamic program finds exact propensities without factorial counting.
Catalog record
| CREATOR | Ziwen Xie, Shaowen Xiang, Hongyu He, Dianbo Liu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 94590 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.29500
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Quotient DAGs for Off-Policy Evaluation: Forward-Flow Importance Sampling and Exact Slate Propensities Ziwen Xie, Shaowen Xiang, Hongyu He, Dianbo Liu Abstract Off-policy evaluation estimates how a target policy would perform using data collected by a different behavior policy, which is crucial when online testing is costly or risky, such as in recommendation or healthcare. Standard importance sampling reweights each logged trajectory, but it can treat details of the generation process as meaningful even when the evaluation target ignores them: for example, an autoregressive slate recommender may generate an ordered sequence of items while the reward and downstream estimator depend only on the unordered slate. This creates nuisance variance and a computational gap, since exact unordered slate propensities require summing over all generation orders. We introduce a quotient-DAG view that merges histories equivalent for evaluation and assigns weights using target-to-behavior forward-flow ratios on the merged graph. For slate recommendation under a set-sufficient next-item interface, this yields Forward-DP, a subset-DAG dynamic program that computes exact unordered propensities without factorial enumeration. The resulting propensity primitive enables practical propensity-based evaluation and model selection for context-dependent autoregressive slate loggers. 1 Introduction Reinforcement learning is widely used for sequential decision policies in recommendation, clinical treatment, and public-sector resource allocation. In many such settings, deploying a new policy directly is expensive or unsafe: a candidate sepsis-treatment protocol, for instance, cannot be tested on ICU patients merely to see whether it improves outcomes. Off-policy evaluation (OPE) addresses this problem by estimating the value of a target policy from data logged under a different behavior policy. Importance sampling (IS), the canonical unbiased OPE estimator, reweights each logged trajectory by a product of target-to-behavior action-probability ratios, but these products can vary by orders of magnitude as horizon and policy mismatch grow. Figure 1: From trajectory IS to quotient-DAG weighting. (a) Trajectory IS assigns a likelihood ratio to each realized path. (b) The rollout tree shares prefixes but still represents distinct history-prefix nodes, even with repeated state labels. (c) A quotient DAG merges evaluation-equivalent prefixes into multi-parent nodes such as z_{4} . The quotient likelihood ratio is the forward-flow ratio F_{\pi}(z)/F_{\beta}(z) , not any single path ratio. This work starts from the observation, illustrated in Figure 1 , that the rollout tree can be a finer representation than the evaluation problem requires. A logged trajectory is one path through the tree, and trajectory IS assigns a likelihood ratio to that particular path. Yet the tree may contain history prefixes that are equivalent for the relevant continuation or evaluation target. We quotient the rollout tree by such an equivalence relation, collapsing equivalent prefixes into nodes of a layered directed acyclic graph (DAG). On this quotient DAG, the probability mass reaching a node under each policy defines its forward flow, and the appropriate likelihood ratio is the target-to-behavior flow ratio F_{\pi}(z)/F_{\beta}(z) . Per-decision IS, marginalized IS, and known-abstraction MIS are special cases of this construction, corresponding to different choices of equivalence relation. Our main concrete instantiation is slate recommendation, where modern slate generators often construct slates autoregressively, exposing per-step probabilities along one realized ordering. Yet slate rewards and propensity-consuming slate-OPE estimators may depend only on the unordered slate. This creates a joint-propensity gap: the logger exposes an ordering probability, while the estimator requires the total probability of the unordered slate. Computing this quantity exactly requires summing over all generation orders, and fixed-score Plackett–Luce expressions no longer apply once the next-item softmax depends on the partial slate. In this paper, we formulate the quotient-space likelihood ratio as a forward-flow ratio and use it to construct forward-flow IS estimators. For terminal quotient-measurable returns, this gives an exact variance-gap expression that identifies the within-class likelihood-ratio variation removed by quotient weighting. For autoregressive slate generation, when the per-step distribution depends only on the context and the set of items already picked, forward flow on the subset DAG computes the exact unordered slate propensity in time polynomial in the catalog size and exponential in the slate size. This closes the joint-propensity computational gap for context-dependent set-sufficient loggers. We evaluate the resulting estimators on finite-horizon MDP benchmarks and use KuaiRec slate experiments to test the Forward-DP propensity primitive in downstream OPE and model selection. 2 Problem setup Off-policy evaluation. We consider off-policy evaluation (OPE) of a target policy \pi from data logged under a behavior policy \beta . The environment is a finite-horizon MDP \mathcal{M}=(\mathcal{S},\mathcal{A},P,R,d_{0},\gamma,H) . A trajectory \tau=(s_{1},a_{1},r_{1},\ldots,s_{H},a_{H},r_{H}) is generated by s_{1}\sim d_{0} , a_{t}\sim\pi(\cdot\mid s_{t}) , r_{t}\sim R(s_{t},a_{t}) , and s_{t+1}\sim P(\cdot\mid s_{t},a_{t}) for t<H . The discounted return is J(\tau)=\sum_{t=1}^{H}\gamma^{t-1}r_{t} , and the policy value is V(\pi)=\mathbb{E}_{\pi}[J(\tau)] . Given logged trajectories \mathcal{D}=\{\tau^{(i)}\}_{i=1}^{N}\sim\beta , define the per-step ratio \rho_{t}(\tau)=\pi(a_{t}\mid s_{t})/\beta(a_{t}\mid s_{t}) and \rho_{1:t}(\tau)=\prod_{t^{\prime}=1}^{t}\rho_{t^{\prime}}(\tau) . The trajectory-level importance sampling estimator is \widehat{V}_{\mathrm{IS}}(\pi)=\frac{1}{N}\sum_{i=1}^{N}\rho_{1:H}(\tau^{(i)})J(\tau^{(i)}), (1) which is unbiased under the standard support condition that the target trajectory distribution is absolutely continuous with respect to the behavior trajectory distribution ( 21 ) . The self-normalized variant \widehat{V}_{\mathrm{WIS}}(\pi)=\sum_{i}w_{i}J(\tau^{(i)})/\sum_{i}w_{i} with w_{i}=\rho_{1:H}(\tau^{(i)}) trades finite-sample unbiasedness for typically lower variance ( 15 ) . Slate OPE. The slate setting is a contextual combinatorial bandit at the evaluation level. A context x\sim p_{\mathcal{X}} is observed, a candidate pool [M]=\{1,\ldots,M\} is available, and the policy selects a size- K slate S\subseteq[M] with |S|=K . We assume the evaluation reward is a set function r(x,S) , invariant to the generation order of the slate. The value of a slate policy is V(\pi)=\mathbb{E}_{x\sim p_{\mathcal{X}},\,S\sim\pi(\cdot\mid x)}[r(x,S)]. Although evaluation is slate-level, the logger may generate S autoregressively as an ordered sequence \sigma=(\sigma_{1},\ldots,\sigma_{K}) with S=\{\sigma_{1},\ldots,\sigma_{K}\} . Let h_{<t}=(\sigma_{1},\ldots,\sigma_{t-1}) be the ordered prefix and S_{<t}=\{\sigma_{1},\ldots,\sigma_{t-1}\} the picked set. For a slate policy \mu\in\{\beta,\pi\} , \mu(\sigma\mid x)=\prod_{t=1}^{K}\mu(\sigma_{t}\mid x,h_{<t}). (2) Definition 1 (Set-sufficient slate policy) . A slate policy \mu is set-sufficient if, for every context x , step t , item a , and any two ordered prefixes h_{<t} and h^{\prime}_{<t} with the same picked set S_{<t} , \mu(a\mid x,h_{<t})=\mu(a\mid x,h^{\prime}_{<t})\qquad\text{for all }a\notin S_{<t}. (3) We write this common value as \mu(a\mid x,S_{<t}) . Our exact subset-DAG construction assumes that the behavior policy \beta and every target policy under evaluation are set-sufficient. Under set-sufficiency, an autoregressive Plackett–Luce policy can be written as \mu_{\theta}(a\mid x,S_{<t})=\frac{\exp\!\left(\ell_{\theta}(a;\mathrm{prompt}(x,S_{<t}))/T_{\mathrm{temp}}\right)}{\sum_{a^{\prime}\notin S_{<t}}\exp\!\left(\ell_{\theta}(a^{\prime};\mathrm{prompt}(x,S_{<t}))/T_{\mathrm{temp}}\right)}, (4) where \mathrm{prompt}(x,S_{<t}) is the model’s input encoding of the context x together with the picked set S_{<t} , \ell_{\theta}(a;\cdot) is the model’s logit for item a , and T_{\mathrm{temp}}>0 is the sampling temperature. Scope of set-sufficiency. Set-sufficiency is imposed on the slate-generation interface, not on the architecture alone. It holds for score-then-mask deployments in which a model scores the remaining candidates and previously selected items affect future choices only through the exclusion mask; this is the canonical slate-generation lift adopted in practice for SASRec, BERT4Rec, and NeuralPGRank-style neural rankers ( 8 ; 26 ; 5 ) . For prompt-based LLM rerankers, we enforce the same interface by presenting the picked set in a canonical order (§ 4.3 ). Models that autoregressively condition on the emitted order of previous items fall outside this assumption unless their prefix representation is canonicalized, which changes the deployed policy by removing ordering information ( 6 ; 2 ; 27 ) . The induced unordered-slate propensity is \mu(S\mid x)=\sum_{\sigma\in\mathrm{perm}(S)}\mu(\sigma\mid x), (5) a sum over all K! orderings of S . Slate-OPE estimators assume access