🤖 machine learning

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

Dit artikel introduceert een quotient-DAG-raamwerk en het Forward-DP-algoritme om nuisance-variatie te elimineren en exacte berekening van ongeordende slate-propensiteiten mogelijk te maken voor efficiënte off-policy-evaluatie in autoregressieve aanbevelingssystemen.

Oorspronkelijke auteurs: Ziwen Xie, Shaowen Xiang, Hongyu He, Dianbo Liu

Gepubliceerd 2026-05-29

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Ziwen Xie, Shaowen Xiang, Hongyu He, Dianbo Liu

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een chef-kok bent die probeert te beoordelen hoe goed een nieuw recept (het Doelbeleid) zou zijn, maar je kunt het niet echt koken in je eigen keuken omdat het te duur of riskant is. In plaats daarvan heb je een notitieboek vol met recepten die in het verleden door een andere chef (het Gedragsbeleid) zijn bereid. Je doel is om te schatten hoe lekker het nieuwe recept zou zijn, uitsluitend op basis van dat oude notitieboek. Dit is het kernprobleem van Off-Policy Evaluation (OPE).

Het Probleem: Het Tellen van de Foute Dingen

Meestal bekijk je, om het nieuwe recept te beoordelen, elke enkele stap die de oude chef heeft genomen. Je zegt: "Oké, ze voegden zout toe, dan peper, dan knoflook." Je berekent een score op basis van die exacte volgorde.

Maar hier zit de adder onder het gras: soms verandert de volgorde waarin je ingrediënten toevoegt de smaak van het eindgerecht niet echt.

Het Scenario: Stel je een "plaat" voor met items (zoals een afspeellijst van 5 nummers of een dienblad met 5 voorgerechten). De klant geeft alleen om welke 5 items op het dienblad liggen, niet om de volgorde waarin de chef ze daar heeft gelegd.
De Fout: Het oude notitieboek legt de volgorde vast (Nummer A, dan B, dan C...). Als je je score berekent op basis van die specifieke volgorde, behandel je de "volgorde" als belangrijk. Maar aangezien de klant er geen waarde aan hecht, voeg je "ruis" toe aan je berekening.
Het Resultaat: Deze ruis zorgt voor een enorme hoeveelheid verwarring (variantie). Het is alsof je probeert het gewicht van een koffer te raden door elk afzonderlijk sokje erin apart te wegen, in plaats van gewoon de hele koffer te wegen. Je krijgt heel verschillende antwoorden, afhankelijk van hoe je de sokjes hebt geteld.

Bovendien is het berekenen van de "ware" kans op het krijgen van een specifieke groep van 5 items (zonder rekening te houden met de volgorde) een wiskundige nachtmerrie. Als je 5 items hebt, zijn er 120 verschillende manieren (5 faculteit) waarop ze hadden kunnen worden gekozen. Deze wiskunde voor elke enkele vermelding in je notitieboek te doen, is computationeel onmogelijk voor grote groepen.

De Oplossing: De "Quotient DAG" (De Groeperingskaart)

De auteurs stellen een slimme nieuwe manier voor om naar de data te kijken. In plaats van naar elke enkele route te kijken die de chef heeft genomen, suggereren ze om alle routes die leiden tot hetzelfde resultaat te groeperen.

De Analogie: Stel je een enorme boom voor waar elke tak een andere volgorde van het toevoegen van ingrediënten vertegenwoordigt.
- Oude Manier: Je loopt elke enkele tak af, meet het gewicht en probeert ze te middelen.
- Nieuwe Manier (Quotient DAG): Je beseft dat alle takken die eindigen met hetzelfde setje ingrediënten eigenlijk hetzelfde "knooppunt" zijn op je kaart. Je vouwt al die takken samen tot één enkel punt.
- De Kaart: Dit creëert een "Directed Acyclic Graph" (DAG)—een kaart waar je alleen om het setje items geeft dat tot nu toe is gekozen, niet om de volgorde.

De Magische Truc: Forward-Flow Importance Sampling

Zodra je deze vereenvoudigde kaart hebt, moet je weten hoe waarschijnlijk het is dat de nieuwe chef een specifiek "setje" bereikt in vergelijking met de oude chef.

De Oude Manier: Je zou de kansen van alle 120 verschillende volgorde moeten optellen om het antwoord te krijgen.
De Nieuwe Manier (Forward-DP): De auteurs hebben een methode bedacht genaamd Forward-DP (Dynamic Programming). Denk hierbij aan een slimme rekenmachine die het antwoord stap voor stap opbouwt.
- Het begint met een leeg dienblad (kans 1).
- Het vraagt: "Als ik 1 item heb, wat is de kans dat ik een 2e toevoeg?"
- Het vraagt: "Als ik 2 items heb, wat is de kans dat ik een 3e toevoeg?"
- Het blijft de kans op het hele setje opbouwen zonder ooit alle 120 volgorde te hoeven opsommen.

Deze methode is exact (het raadt niet) en snel. In plaats van jaren te duren om te berekenen (faculteit-tijd), duurt het een beheersbare hoeveelheid tijd (exponentieel in de grootte van het dienblad, maar polynomiaal in de grootte van het menu).

Waarom Dit Belangrijk Is

Minder Ruis: Door de irrelevante "volgorde"-details te negeren, wordt de wiskunde veel schoner. De schattingen zijn nauwkeuriger en stabieler.
Uitvoerbaarheid: Het maakt het mogelijk om complexe aanbevelingssystemen te evalueren (zoals "toon me 10 films") die eerder te moeilijk waren om exact te berekenen.
Real-World Test: De auteurs hebben dit getest op:
- Medische Data: Het simuleren van behandelingen voor sepsis (bloedvergiftiging). Hun methode gaf veel nauwkeurigere voorspellingen van patiëntuitkomsten dan oudere methoden.
- Aanbevelingsdata: Het gebruik van een dataset genaamd KuaiRec (video-aanbevelingen). Ze lieten zien dat hun methode in seconden de "ware" kans kon berekenen dat een groep video's werd aanbevolen, terwijl de oude manier dagen zou duren of onmogelijk zou zijn.

Samenvatting

Het paper introduceert een manier om te stoppen met het over-analyseren van het "hoe" (de volgorde van acties) en zich te focussen op het "wat" (het uiteindelijke setje items). Door equivalente routes samen te groeperen en een slimme, stap-voor-stap berekeningsmethode (Forward-DP) te gebruiken, kunnen ze nieuwe strategieën veel nauwkeuriger en efficiënter evalueren, vooral in gebieden zoals gezondheidszorg en aanbevelingsmachines waar het testen van nieuwe ideeën in het echt te gevaarlijk of duur is.

Technische Samenvatting: Quotiënt-DAG's voor Off-Policy Evaluatie

Probleemstelling

Off-policy evaluatie (OPE) schat de prestaties van een doelpolitiek $\pi$ met behulp van data die is verzameld door een gedragspolitiek $\beta$ . Standaard importance sampling (IS) herweegt gelogde trajecten op basis van het product van de verhoudingen tussen de kans op een actie onder de doelpolitiek en de gedragspolitiek. Deze aanpak behandelt echter vaak details van het generatieproces als betekenisvol, zelfs wanneer het evaluatiedoel deze details negeert.

Een primair voorbeeld van dit probleem doet zich voor bij slate-recommendatie, waarbij moderne generators vaak slates (sets van items) autoregressief construeren en per-stap-kansen blootleggen langs een specifieke volgorde. De beloning en downstream-schatters zijn echter vaak alleen afhankelijk van de ongesorteerde slate. Standaard traject-IS kent een waarschijnlijkheidsverhouding toe aan een specifiek geordend pad, wat een "joint-propensity gap" creëert: de logger legt een ordingswaarschijnlijkheid bloot, terwijl de schatter de totale waarschijnlijkheid van de ongesorteerde slate vereist. Het berekenen van deze exacte ongesorteerde propensity vereist doorgaans het sommeren over alle $K!$ generatieordes, wat computationeel onuitvoerbaar is voor matige slate-groottes. Bovendien introduceert het behandelen van de volgorde als significant onnodige variantie wanneer de beloning invariant is ten opzichte van de generatievolgorde.

Methodologie

Het artikel introduceert een Quotiënt-DAG-visie om deze problemen aan te pakken. De kernidee is om de rolloutboom van geschiedenisvoorvoegsels te quotiënteren via een equivalentierelatie die toereikend is voor het evaluatiedoel.

Quotiënt-DAG en Voorwaartse Stroom:
- De rolloutboom wordt samengevoegd door geschiedenisvoorvoegsels die equivalent zijn voor het evaluatiedoel te samenvoegen (bijvoorbeeld voorvoegsels die dezelfde set van geselecteerde items bevatten, ongeacht de volgorde).
- Dit vormt een gelaagde Gerichte Acyclische Grafiek (DAG) waarbij knopen equivalentieklassen (quotiënttoestanden) vertegenwoordigen.
- In plaats van te wegen op basis van de verhouding van een enkel gerealiseerd pad, kent de methode gewichten toe met behulp van de voorwaartse-stroomverhouding $F_\pi(z)/F_\beta(z)$ , waarbij $F_\mu(z)$ de waarschijnlijkheidsmassa is die knoop $z$ bereikt onder politiek $\mu$ .
- Deze aanpak generaliseert bestaande methoden: per-decision IS, gemarginaliseerde IS en bekende-abstraktie MIS zijn speciale gevallen die overeenkomen met verschillende keuzes van equivalentierelaties.
Forward-Flow Importance Sampling (FF-IS):
- Voor algemene OPE met een eindige horizon vervangt de schatter de verhouding van het bemonsterde voorvoegsel in Per-Decision IS (PDIS) door de quotiënt-waarschijnlijkheidsverhouding.
- Theoretische analyse toont aan dat voor terminal quotiënt-meetbare returns deze weging de "within-class"-mismatch tussen doel en gedrag verwijdert, en een exacte uitdrukking voor de variantiegap biedt die de reductie in onnodige variantie kwantificeert.
Forward-DP voor Slate OPE:
- Het artikel specialiseert dit kader voor autoregressieve slate-generatie onder een set-toereikende interface (Definitie 1). Een politiek is set-toereikend als de kans op het selecteren van het volgende item alleen afhangt van de context en de set van reeds geselecteerde items, niet van hun volgorde.
- Onder set-toereikendheid komt de permutatiequotiënt overeen met een subset-DAG, waarbij knopen subsets van de catalogus zijn en randen niet-geselecteerde items toevoegen.
- Forward-DP Algoritme: Een dynamisch programmeringsalgoritme berekent de exacte ongesorteerde slate-propensity $F_\mu(S|x)$ $F_{μ} (S ∣ x)$ door te sommeren over subsets in plaats van permutaties.
  - Complexiteit: $O((M + K) \cdot 2^K)$ , waarbij $M$ de catalogusgrootte is en $K$ de slate-grootte. Dit vermijdt de $K!$ enumeratie.
  - Optimaliteit: Het artikel bewijst dat elke deterministische algoritme dat exacte ongesorteerde propensities berekent voor set-toereikende politieke in het ergste geval elke eigentlijke subset van de slate moet bevragen, waardoor Forward-DP als query-optimaal wordt vastgesteld tot op constante factoren.

Belangrijkste Bijdragen

Theoretisch Kader: Een unificerende quotiënt-DAG-visie voor OPE die exacte waarschijnlijkheidsverhoudingen afleidt als voorwaartse-stroomverhoudingen op een grover steekproefruimte.
Algoritmische Innovatie: Het Forward-DP algoritme, dat exacte ongesorteerde slate-propensities berekent voor contextafhankelijke, set-toereikende autoregressieve loggers in tijd die polynomiel is in de catalogusgrootte en exponentieel in de slate-grootte (vast-parameter tractabel in $K$ ).
Variantiereductie: Een formeel bewijs dat quotiëntweging de variantiecomponent verwijdert die voortkomt uit irrelevante generatieordes (ordings-nuisance variantie), met name wanneer beloningen invariant zijn ten opzichte van de generatiesequentie van de slate.
Primitieven voor Slate OPE: De introductie van Forward-DP als een primitief dat exacte propensity-gebaseerde evaluatie en modelselectie mogelijk maakt voor transformer-gebaseerde slate-recommenders, waardoor de kloof wordt gedicht voor contextafhankelijke loggers waarvoor vaste-score Plackett-Luce-formules niet van toepassing zijn.

Experimentele Resultaten

De auteurs evalueren de methode op benchmarks voor MDP's met een eindige horizon en taken voor slate-recommendatie:

MDP's met Eindige Horizon (Sepsis & ICU-Sepsis):
- Forward-Flow IS (FF-IS) vermindert de Root Mean Square Error (RMSE) aanzienlijk in vergelijking met standaard traject-IS en andere baselines (zoals DualDICE, GenDICE).
- Op de Sepsis-benchmark verlaagde FF-WIS de RMSE van 0,291 (WIS) naar 0,0568.
- Deze winsten werden behaald met alleen gelogde trajecten, zonder het aanpassen van een overgangsmodel.
KuaiRec Slate Experimenten:
- Berekenings-efficiëntie: Forward-DP berekent exacte propensiteiten met een orde van grootte sneller dan $K!$ enumeratie. Voor $K=8$ duurde enumeratie ~97.108 seconden, terwijl Forward-DP ~8,94 seconden nodig had. Voor $K=12$ is enumeratie onuitvoerbaar, terwijl Forward-DP in ~13,7 seconden wordt voltooid.
- Downstream OPE: Schatters die Forward-DP-gewichten gebruiken (FF-OIS, FF-DR) presteerden consistent beter dan hun tegenhangers met traject-gewichten (OIS, DR) voor alle slate-groottes ( $K \in \{4, 6, 8\}$ ) in termen van RMSE.
- Modelselectie: Bij off-policy modelselectie tussen autoregressieve transformer-recommenders bereikten schatters die Forward-DP gebruiken (bijv. Tree-DR, DP-OPCB-DR) superieure Top-1-accuraatheid, Spearman-correlatie en lagere regret in vergelijking met op trajecten gebaseerde methoden.

Betekenis en Claims

Het artikel beweert dat het voorgestelde kader een Rao–Blackwellisering van per-decision IS biedt. Door de rolloutboom te quotiënteren onder toereikende equivalentierelaties, elimineert de methode onnodige variantie die geassocieerd is met irrelevante geschiedenisdetails (zoals generatievolgorde bij slate-recommendatie).

Specifiek voor slate-recommendatie stelt het artikel dat Forward-DP de ontbrekende OPE-primitief levert voor contextafhankelijke autoregressieve loggers. In tegenstelling tot eerdere methoden die vertrouwen op vaste-score-aannames (waarbij item-scores niet veranderen met de partiële slate) of Monte Carlo-benaderingen, behandelt Forward-DP het geval waarbij de next-item softmax afhankelijk is van de partiële slate, en berekent het de exacte gezamenlijke propensity zonder factoriële enumeratie. Dit maakt praktische, exacte propensity-gebaseerde evaluatie en modelselectie mogelijk voor moderne transformer-gebaseerde recommenders.

De auteurs merken beperkingen op, waaronder de vereiste van de set-toereikendheidsaanneming (die kan vereisen dat de geselecteerde set in de implementatie wordt genormaliseerd) en de exponentiële schaling met de slate-grootte $K$ , hoewel zij betogen dat dit praktisch is voor typische slate-groottes ( $K \le 10$ ) waar $K!$ onuitvoerbaar is.