Technische Zusammenfassung: Design einer Protokollierungsrichtlinie für Off-Policy-Evaluation

Problemstellung

Die Off-Policy-Evaluation (OPE) ist ein entscheidender Mechanismus zur Schätzung des Wertes einer Zielbehandlungsrichtlinie (z. B. eines neuen Empfehlungssystems) unter Verwendung von Daten, die von einer anderen „Protokollierungsrichtlinie" (logging policy) gesammelt wurden. Obwohl OPE Experimente mit hohem Risiko ohne Live-Einsatz ermöglicht, hängt ihre Genauigkeit stark von der Protokollierungsrichtlinie ab, die zur Generierung der Daten verwendet wird. Die bestehende Literatur betrachtet die Protokollierungsrichtlinie oft als feste, möglicherweise unbekannte Verhaltensrichtlinie und konzentriert sich stattdessen auf die Verbesserung von Schätzern (z. B. Inverse Propensity Weighting, Doubly Robust). In der Praxis beeinflusst die Wahl der Protokollierungsrichtlinie jedoch die Verzerrung (Bias) und Varianz von OPE-Schätzungen dramatisch, insbesondere in Regimen mit endlichen Stichproben, großen Aktionsräumen und spärlichen Belohnungen.

Das zentrale Problem besteht darin, wie die Protokollierungsrichtlinie (insbesondere die Aktionsneigungen $\pi_l(a|x)$) zu gestalten ist, um den mittleren quadratischen Fehler (MSE) einer Inverse Propensity Weighting (IPW)-Schätzung für eine gegebene Zielrichtlinie $\pi_t$ zu minimieren. Dieses Design muss einen fundamentalen Tradeoff zwischen Belohnung und Abdeckung bewältigen: Die Konzentration der Wahrscheinlichkeitsmasse auf Aktionen mit hoher Belohnung reduziert die Varianz aus der Realisierung der Belohnung, während die Sicherstellung einer Abdeckung über Aktionen hinweg, die die Zielrichtlinie auswählen könnte, notwendig ist, um Verzerrungen und Varianzen zu kontrollieren, die aus dem Aktions-Sampling entstehen.

Methodik

Die Autoren fassen das Problem im Rahmen eines kontextuellen Bandit-Settings (Markov-Entscheidungsprozess ohne Übergangsdynamik) zusammen, in dem Kontexte $X$ aus einer Verteilung $p_X$ eintreffen und Aktionen $A$ von einer Protokollierungsrichtlinie $\pi_l$ ausgewählt werden. Die Belohnung $R$ ist binär und wird aus $Bernoulli(\mu(a, x))$ gezogen.

1. Zielfunktion

Das primäre Ziel ist die Minimierung des MSE des IPW-Schätzers $\hat{V}_{IPW}(\pi_t | \pi_l)$:
$$MSE = E[(\hat{V}_{IPW} - V(\pi_t))^2] = Bias^2 + Variance$$
Die Autoren leiten die Bias-Varianz-Zerlegung explizit als Funktion der Protokollierungsrichtlinie $\pi_l$ her. Sie stellen fest, dass zwar eine Überlappung (Sicherstellung, dass $\pi_l(a|x) > 0$ für alle $a$, bei denen $\pi_t(a|x) > 0$) die Verzerrung eliminiert, dies jedoch nicht notwendigerweise den MSE minimiert, insbesondere wenn die Stichprobengrößen klein sind.

2. Informationsregime

Der Artikel analysiert optimale Protokollierungsrichtlinien über ein Spektrum von Informationsbeschränkungen hinweg, kategorisiert nach dem Wissen über die Zielrichtlinie ($\pi_t$) und die Belohnungsverteilung ($\mu$):

• Unbekanntes $\pi_t$ und unbekanntes $\mu$: In Abwesenheit von Informationen ist die minimax-optimale Strategie die uniforme Randomisierung. Dies entspricht der Intuition, dass eine uninformative Prior-Verteilung optimal ist, wenn der Schätzwert unbekannt ist.
• Bekanntes $\mu$, unbekanntes $\pi_t$: Die optimale Richtlinie weist Masse proportional zu $\frac{\mu(a,x)}{c + \mu(a,x)^2}$ zu, priorisiert dabei Aktionen mit hoher Belohnung und wahrt gleichzeitig einen Sicherheitsabstand.
• Unbekanntes $\mu$, bekanntes $\pi_t$: Die optimale Strategie besteht darin, Daten direkt unter der Zielrichtlinie $\pi_t$ selbst zu protokollieren.
• Bekanntes $\pi_t$ und bekanntes $\mu$: Dies ist der ideale Fall. Die optimale Protokollierungsrichtlinie folgt einer Neyman-Allokation, die auf die Zielrichtlinie ausgerichtet ist:
  $$\pi_l^*(a|x) \propto \pi_t(a|x)\sqrt{\mu(a,x)}$$
  Diese Lösung gewichtet Aktionen durch das Produkt aus der Masse der Zielrichtlinie und der Quadratwurzel der Belohnungswahrscheinlichkeit.

3. Mittlere Settings und praktische Einschränkungen

In Anerkennung dessen, dass perfekte Informationen selten verfügbar sind, erweitert der Artikel das Framework auf mittlere Settings:

• Verteilung über Zielrichtlinien: Wenn das exakte Ziel unbekannt ist, aber eine Verteilung $Pr(\pi_t)$ bekannt ist, zielt die optimale Protokollierungsrichtlinie auf ein „zweites Moment-Pseudoziel" $\tilde{\pi}_t(a|x) = \sqrt{E[\pi_t(a|x)^2]}$ ab.
• Verrauschte Belohnungsschätzungen: Wenn $\mu$ über ein Modell $\hat{\mu}$ mit Rauschen geschätzt wird, führt das direkte Einsetzen von $\hat{\mu}$ zu einer Aufblähung der Varianz. Die Autoren schlagen eine posteriore Schrumpfung vor, bei der verrauschte Schätzungen auf einen kontextspezifischen Mittelwert hin geschrumpft werden. Unter einer gaußschen hierarchischen Prior-Verteilung wird das optimale Schrumpfungsgewicht hergeleitet, was zu einer „empirischen Bayes"-Interpretation führt, bei der der Schrumpfungsparameter aus zurückgehaltenen Daten geschätzt wird.
• Soft-Greedy-Klassen: Für Settings, in denen theoretische Optima aufgrund technischer oder organisatorischer Einschränkungen nicht machbar sind, schlägt der Artikel drei Richtlinienklassen vor, die durch einen „Gierigkeits"-Parameter indiziert sind: Top-k, Softmax und Power-normalisiert. Diese Klassen interpolieren zwischen uniformer Randomisierung und deterministischer gieriger Auswahl und ermöglichen es Unternehmen, den Tradeoff zwischen Belohnung und Abdeckung über einen einzigen Hyperparameter auszugleichen.

Hauptergebnisse

1. Optimalität modifizierter Protokollierung: Im Fall, dass sowohl $\pi_t$ als auch $\mu$ bekannt sind, liefert die optimale Protokollierungsrichtlinie $\pi_l^*$ (Neyman-Allokation) einen niedrigeren MSE für die IPW-Schätzung als das direkte Ausführen der Zielrichtlinie $\pi_t$ (On-Policy-Evaluation). Darüber hinaus sammelt $\pi_l^*$ während der Protokollierungsphase eine höhere erwartete Belohnung als $\pi_t$ selbst. Dies zeigt, dass eine optimierte OPE gleichzeitig die statistische Präzision und die Benutzererfahrung im Vergleich zu Live-A/B-Tests verbessern kann.
2. Tradeoff zwischen Belohnung und Abdeckung: Der Artikel formalisiert, dass die optimale Protokollierung selten identisch mit der Zielrichtlinie ist. Selbst wenn die Zielrichtlinie bekannt ist, muss die Protokollierungsrichtlinie das Sampling von Aktionen mit hoher Belohnung (zur Reduzierung der Belohnungsvarianz) gegen das Sampling von Aktionen, die die Zielrichtlinie auswählt (zur Reduzierung der Sampling-Varianz), abwägen.
3. Auswirkung von Rauschen: Die Verwendung verrauschter Belohnungsvorhersagen ohne Schrumpfung führt zu suboptimalen Protokollierungsrichtlinien, die schlechter abschneiden können als die uniforme Randomisierung. Die posteriore Schrumpfung mildert dieses Risiko erheblich und ermöglicht es oft, dass optimierte Protokollierung auch bei unvollkommenen Belohnungsmodellen besser abschneidet als On-Policy-Evaluation.
4. Leistung von Heuristiken: Simulationen zeigen, dass einfache „soft-greedy"-Richtlinien (insbesondere Top-k und Power-normalisiert) den MSE des theoretischen Optimums annähern können. In Regimen mit kleinen Stichproben kann das gezielte Abschneiden des Aktionsunterstützungsbereichs (Induzierung einer leichten Verzerrung) den gesamten MSE im Vergleich zu Richtlinien, die eine strikte Überlappung erzwingen, reduzieren.

Bedeutung und Beiträge

Der Artikel behauptet, ein vereinheitlichendes Framework für das Design von Protokollierungsrichtlinien zu liefern, das über ad-hoc-Heuristiken oder reine Sicherheitsbeschränkungen hinausgeht. Seine Bedeutung liegt in:

• Theoretische Fundierung: Er verbindet das Design von Protokollierungsrichtlinien mit klassischen Problemen des optimalen Versuchsdesigns (Neyman-Allokation) und Importance Sampling und liefert handhabbare optimale Lösungen unter verschiedenen Informationsbeschränkungen.
• Handlungsanleitungen: Er bietet konkrete Strategien für Unternehmen bei der Auswahl unter Kandidatensystemen, insbesondere wenn die Zielrichtlinie unbekannt ist oder Belohnungsschätzungen verrauscht sind. Die vorgeschlagenen Schrumpfungsmethoden und soft-greedy-Klassen bieten praktische Werkzeuge für die Implementierung.
• Doppelter Nutzen: Er hinterfragt die Vorstellung, dass die Datenerhebung zur Evaluation die Benutzererfahrung opfern muss. Die Ergebnisse zeigen, dass theoretisch optimale Protokollierungsrichtlinien sowohl präzisere Offline-Evaluationen als auch höhere unmittelbare Belohnungen als die bewerteten Richtlinien liefern können.
• Klärung von Tradeoffs: Durch die explizite Charakterisierung des Tradeoffs zwischen Belohnung und Abdeckung sowie der Bias-Varianz-Zerlegung im Kontext des Protokollierungsdesigns klärt der Artikel, wann und warum verschiedene Protokollierungsstrategien (z. B. uniform vs. gierig vs. Neyman) angemessen sind.

Die Autoren kommen zu dem Schluss, dass ihre theoretischen Ergebnisse zwar auf Annahmen beruhen (wie die Verwendung von IPW und schwacher Überlappung), sie jedoch eine prinzipielle Grundlage für Unternehmen bieten, um ihre Bemühungen zur Offline-Experimentierung zu verbessern und konservative Ausweichstrategien wie die uniforme Randomisierung durch datengesteuerte, theoretisch optimierte Protokollierungsstrategien zu ersetzen.