Quotient DAGs for Off-Policy Evaluation:Forward-Flow Importance Sampling and Exact Slate Propensities
This work addresses the variance and computational bottleneck in off-policy evaluation for slate recommendation, a problem critical for practitioners using autoregressive loggers in high-stakes domains like recommendation and healthcare.
The authors propose a quotient-DAG framework for off-policy evaluation that computes exact slate propensities without factorial enumeration, reducing variance and computational cost. In slate recommendation, their Forward-DP method achieves exact unordered propensities, enabling practical evaluation and model selection for autoregressive slate loggers.
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.