Exploiting Similarities in A/B Testing with Off-Policy Estimation

Technische Samenvatting: Het exploiteren van gelijkenissen in A/B-testen met Off-Policy Schatting

Probleemstelling
A/B-testen is het standaardprotocol voor het meten van de prestatiewinst van een nieuw beslissingssysteem ($\pi_A$) ten opzichte van een baseline ($\pi_B$). Traditioneel wordt dit uitgevoerd met een verschil-in-gemiddelden-schatter, die beide systemen als black boxes behandelt. Hoewel deze schatter onbevooroordeeld is, is hij statistisch suboptimaal omdat hij mogelijke structurele gelijkenissen tussen de beleidsregels negeert. In moderne online toepassingen (bijv. advertenties, aanbevelingen) zijn beslissingssystemen vaak stochastisch en delen ze een significante structuur, wat betekent dat ze vergelijkbare "propensities" hebben om specifieke beslissingen te nemen. Het artikel betoogt dat wanneer beleidsregels overlappen, de klassieke schatter lijdt onder onnodige variantie, terwijl standaard off-policy schattingsmethoden (OPE), die vertrouwen op importance weighting, vaak te bevooroordeeld of instabiel zijn om A/B-testen direct te kunnen vervangen.

Methodologie
De auteurs stellen een familie van A/B-testschatters voor die technieken voor off-policy schatting gebruikt om de overlap tussen $\pi_A$ en $\pi_B$ te exploiteren zonder het standaard experimentele protocol te wijzigen.

1. Framework: Het probleem wordt gemodelleerd binnen een uitgebreid non-Markov Decision Process (NMDP) framework waar gebruikers interageren met het systeem over trajecten $\tau$. Het doel is om de verbetering $I(\pi_A, \pi_B) = V(\pi_A) - V(\pi_B)$ te schatten.
2. Constructie van de schatter: De voorgestelde schatter $\hat{I}_f$ combineert twee componenten:
   • Een $f$-geregulariseerde Inverse Propensity Scoring (IPS) term gebruikmakend van data van het baseline-beleid ($D_B$).
   • Een bias-correctieterm gebruikmakend van data van het doel-beleid ($D_A$).
   • De functie $f: \mathbb{R}_+ \to \mathbb{R}$ transformeert de importance weights $w(\tau) = \pi_{target}(\tau) / \pi_{source}(\tau)$.
3. Theoretische Voorwaarden:
   • Onbevooroordeeldheid: De schatter is onbevooroordeeld als $f(0) = -1$. Deze voorwaarde zorgt ervoor dat wanneer beleidsregels een disjuncte ondersteuning hebben (geen overlap), de schatter van nature terugkeert naar de standaard verschil-in-gemiddelden-schatter.
   • Variantiereductie: Om variantie te verminderen, definiëren de auteurs een variantie-surrogaat $S_f$. Ze leiden voorwaarden af voor $f$ (specifiek $f(1)=0$ en grenzen aan $f(x)$) die garanderen dat de variantie lager is dan die van de verschil-in-gemiddelden-schatter wanneer de beleidsregels vergelijkbaar zijn.
4. Optimale Transformaties:
   • Surrogaat-Optimaal ($f^*_{n_r}$): De auteurs leiden een gesloten vorm functie af $f^*_{n_r}(x) = \frac{x-1}{n_r x + 1}$ (waarbij $n_r = n_A/n_B$) die de variantie-surrogaat minimaliseert. Deze schatter herweegt effectief de data van beide populaties om rekening te houden met de steekproefonbalans.
   • Misspecificatie-bewust ($f^*_{\lambda, \Delta}$): In het besef dat propensities vaak uit data worden geschat in plaats van bekend te zijn, introduceren de auteurs een regularisatieparameter $\lambda$ om bias en variantie te balanceren onder propensity misspecificatie. Dit levert een robuuste schatter op die geleidelijk degradeert naar de verschil-in-gemiddelden-schatter naarmate de misspecificatie toeneemt.

Belangrijkste Bijdragen

• Nieuwe Schatterfamilie: Introductie van een flexibele familie van A/B-testschatters gebaseerd op importance weighting die expliciet de overlap tussen beleidsregels exploiteert.
• Theoretische Garanties: Bewijs dat de schatters onbevooroordeeld zijn onder specifieke voorwaarden op $f$ en tonen verbeterde concentratie-eigenschappen (lagere variantie) wanneer beleidsregels vergelijkbaar zijn.
• Robuustheid: Ontwikkeling van misspecificatie-bewuste varianten die robuust blijven wanneer propensities uit data worden geschat, waardoor de hoge variantie of bias die typisch is voor standaard OPE-methoden wordt vermeden.
• Graceful Degradation (Geleidelijke Degradatie): De schatters zijn ontworpen om automatisch terug te keren naar de standaard verschil-in-gemiddelden-schatter wanneer beleidsregels verschillend zijn (geen overlap) of wanneer misspecificatie ernstig is, wat prestatieverlies in ongunstige scenario's voorkomt.

Experimentele Resultaten
De auteurs valideren hun aanpak via drie experimentele settings:

1. Overlappende Beleidsregels & Data-onbalans: In een vereenvoudigde bandit-setting bereikten de voorgestelde schatters aanzienlijke variantiereductie (tot 27x in specifieke scenario's) wanneer de beleidsregels dicht bij elkaar lagen. De reductie was bijzonder effectief in het afhandelen van ongebalanceerde gebruikersallocaties ($n_A \neq n_B$), waar de standaard verschil-schatter moeite mee heeft.
2. Gevoeligheid voor Misspecificatie: In scenario's met geïnduceerde fouten in de propensity-schatting, vertoonden de standaard IPS en naïeve geregulariseerde schatters ($h_1$) een hoge Mean Squared Error (MSE). In contrast hiermee presteerden de voorgestelde misspecificatie-bewuste schatters consistent beter dan de verschil-in-gemiddelden-baseline, waarbij ze zelfs onder matige tot hoge niveaus van misspecificatie een lagere MSE behielden.
3. Realistische Aanbevelingsproblematiek: Door een non-Markoviaans aanbevelingsmilieu met gebruikersverveling te simuleren, testten de auteurs horizonten $T \in \{1, \dots, 32\}$. De variantie-optimale schatter ($f^*_1$) verminderde de MSE aanzienlijk voor korte tot matige horizonten. Echter, voor lange horizonten degradeerde de cumulatieve fout in de propensity-schatting de prestaties. De misspecificatie-bewuste schatter bood stabiele, bescheiden winsten over alle horizonten, en presteerde beter dan zowel de standaard verschil-schatter als andere OPE-gebaseerde benaderingen zoals DiffQ.

Betekenis en Claims
Het artikel claimt dat off-policy schattingsideeën niet louter als vervanging voor A/B-testen moeten dienen, maar als een instrument om de statistische efficiëntie van A/B-testen zelf te verbeteren. Door gebruik te maken van de bekende of geschatte propensities van de geteste systemen, kunnen beoefenaars nauwkeurigere verbeteringsschattingen verkrijgen met dezelfde steekproefomvang. De voorgestelde methode is significant omdat het:

• Geen wijzigingen vereist in het standaard A/B-test dataverzamelingprotocol.
• Robuust is tegen de praktische realiteit van geschatte propensities.
• Een "best of both worlds"-scenario biedt: het biedt aanzienlijke variantiereductie wanneer beleidsregels vergelijkbaar zijn (de veelvoorkomende casus bij iteratieve systeemupdates) terwijl het veiligheid garandeert (niet slechter dan standaard A/B-testen) wanneer zij dat niet zijn.

De auteurs concluderen dat hoewel hun aanpak het variantieprobleem bij overlappende beleidsregels aanpakt, er nog steeds uitdagingen zijn voor zeer lange horizonten waar propensity drift significant is, wat suggereert dat toekomstig werk zich moet richten op het exploiteren van sequentiële structuren en doubly robust methoden.