오프라인 평가를 위한 몫 그래프(Quotient DAGs): 순방향 흐름 중요 샘플링 및 정확한 슬레이트 확률

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

오프라인 평가는 온라인 테스트가 비용이 많이 들거나 위험한 경우, 즉 추천 시스템이나 의료 분야에서처럼, 다른 행동 정책으로 수집된 데이터를 사용하여 목표 정책의 성능을 추정하는 데 중요한 역할을 합니다. 일반적인 중요 샘플링은 기록된 모든 경로에 가중치를 부여하지만, 평가 대상이 무시하는 생성 과정의 세부 사항까지 의미 있는 것으로 취급할 수 있습니다. 예를 들어, 자기 회귀(autoregressive) 슬레이트 추천 시스템은 정렬된 항목 시퀀스를 생성하지만, 보상과 하위 추정기는 비정렬된 슬레이트에만 의존합니다. 이는 불필요한 분산을 유발하고 계산상의 격차를 만듭니다. 왜냐하면 정확한 비정렬 슬레이트 확률을 얻으려면 모든 생성 순서를 합산해야 하기 때문입니다. 본 논문에서는 평가에 동일하게 기여하는 이력을 병합하고, 병합된 그래프에서 목표 정책에서 행동 정책으로의 순방향 흐름 비율을 사용하여 가중치를 할당하는 '몫-DAG' 관점을 도입합니다. 집합-충분한 다음 항목 인터페이스를 사용하는 슬레이트 추천 시스템에서 이는 Forward-DP라는 부분-DAG 동적 프로그래밍 방식을 통해, 팩토리얼 열거 없이 정확한 비정렬 확률을 계산할 수 있도록 합니다. 이러한 확률 기본 요소는 컨텍스트에 따라 달라지는 자기 회귀 슬레이트 로거에 대한 실용적인 확률 기반 평가 및 모델 선택을 가능하게 합니다.

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.