Active Context Selection Improves Simple Regret in Contextual Bandits

Technische Zusammenfassung: Aktive Kontextauswahl verbessert den einfachen Regret in kontextuellen Banditen

Problemformulierung
Dieser Artikel untersucht das Problem des kontextuellen Multi-Armed-Bandits innerhalb eines endlichen Kontextrums, wobei Kontexte distincte Subpopulationen (z. B. demografische Gruppen) repräsentieren. Das Lernziel wird durch den kontextgewichteten einfachen Regret definiert: Nach einem festen experimentellen Budget $T$ muss der Lernende für jede Subpopulation eine einzelne beste Behandlung empfehlen. Die Leistungsmetrik ist die erwartete Lücke zwischen der optimalen und der empfohlenen Behandlung, gewichtet mit dem Populationsverteilungsvektor $p$ über die $k$ Subpopulationen.

Die Studie unterscheidet zwischen zwei Stichprobenregimen:

1. Passive Stichprobennahme: Kontexte werden zufällig gemäß der festen Verteilung $p$ offenbart, und der Lernende wählt nur die Behandlung.
2. Aktive Stichprobennahme: Der Lernende kann für jede Runde sowohl die Subpopulation (den Kontext) als auch die Behandlung aktiv wählen.

Die Analyse geht von einem Worst-Case-Szenario bezüglich der Belohnungsverteilungen aus, bleibt jedoch instanzabhängig hinsichtlich der Kontextverteilung $p$. Der Artikel konzentriert sich auf das „datenreiche" Regime, in dem der Horizont $T$ deutlich größer ist als die Anzahl der Behandlungen $n$, der Kontexte $k$ und der Kehrwert der minimalen Kontextwahrscheinlichkeit.

Methodik und theoretischer Rahmen

• Optimaler Zuweisungsplan bei bekanntem $p$:
  Wenn die Subpopulationsverteilung $p$ bekannt ist, charakterisieren die Autoren die optimale Zuweisung des experimentellen Budgets. Sie beweisen, dass für das Worst-Case-Kriterium des einfachen Regrets verlaufsfreie Strategien (bei denen die Kontextauswahl nur von $p$ und nicht von der beobachteten Historie abhängt) ausreichen, um die Minimax-Rate zu erreichen.

  • Passive Rate: Unter passiver Stichprobennahme skaliert der Regret als $\Theta(\sqrt{\frac{n}{T}} \|p\|_{1/2})$.
  • Aktive Rate: Unter aktiver Stichprobennahme weist die optimale Strategie Proben der Subpopulation $j$ mit einer Wahrscheinlichkeit proportional zu $p_j^{2/3}$ zu. Dies erreicht eine Regret-Rate von $\Theta(\sqrt{\frac{n}{T}} \|p\|_{2/3})$.
  • Die Lücke: Der Verbesserungsfaktor der aktiven gegenüber der passiven Stichprobennahme wird durch das Verhältnis $R(p) = \|p\|_{1/2} / \|p\|_{2/3}$ charakterisiert. Die Autoren zeigen, dass dieser Abstand bei stark nicht-uniformen Verteilungen bis zu $\Theta(k^{1/4})$ betragen kann. Die optimale aktive Zuweisung verschiebt die Stichprobenwahrscheinlichkeiten hin zu einer gleichmäßigeren Verteilung im Vergleich zu $p$, wodurch die Exploration in kleineren Subpopulationen erhöht wird.

• Budgetierte Interventionen:
  Der Artikel erweitert die Analyse auf Szenarien, in denen aktive Stichprobennahme kostspielig ist, sodass der Lernende die Subpopulation nur in einem $\alpha$-Anteil der Runden wählen kann. Die Autoren formulieren ein restringiertes Optimierungsproblem zur Minimierung des Regrets unter der Bedingung, dass die Zuweisung $q$ die Bedingung $q_j \geq (1-\alpha)p_j$ erfüllen muss. Sie leiten eine Schwellenwertstruktur für die optimale Zuweisung ab: Subpopulationen mit großem $p_j$ können bei ihrer passiven Zuweisung verbleiben, wenn das Budget nicht ausreicht, um sie zu verbessern, während andere in Richtung des Anteils $p_j^{2/3}$ gesteigert werden. Sie identifizieren ein minimales Budget $\alpha_{\min}(p)$, das erforderlich ist, um die vollständig aktive optimale Rate wiederherzustellen.

• Unbekanntes $p$ (Der EETC-Algorithmus):
  Wenn $p$ unbekannt ist, kann eine vollständig aktive Strategie die $p^{2/3}$-Regel nicht einfach übernehmen. Die Autoren schlagen den Explore-Explore-Then-Commit (EETC)-Algorithmus vor, der drei Phasen ausbalanciert:

  1. Initiale passive Exploration: Der Lernende agiert passiv, um $p$ zu schätzen.
  2. Fortgesetzte passive Stichprobennahme: Der Lernende fährt mit passiver Stichprobennahme fort, bis das verbleibende Budget ausreicht, um die optimale aktive Zuweisung basierend auf der aktuellen Schätzung umzusetzen.
  3. Commitment: Der Lernende wechselt zur aktiven Stichprobennahme unter Verwendung der geschätzten Verteilung, um die verbleibenden Runden zu zuweisen.
     Die theoretische Analyse zeigt, dass EETC für große Horizonte dieselbe einfache Regret-Rate wie die optimale vollständig aktive Strategie mit bekanntem $p$ erreicht, bis auf konstante Faktoren.

Hauptergebnisse und Experimente

• Theoretische Garantien: Der Artikel etabliert enge Regret-Raten sowohl für bekanntes als auch für unbekanntes $p$. Er beweist, dass die aktive Kontextauswahl die passive Stichprobennahme strikt verbessert, wobei das Ausmaß der Verbesserung von der Heterogenität der Kontextverteilung abhängt.
• Synthetische Experimente: Experimente mit synthetischen Daten bestätigen, dass sich die Regret-Lücke zwischen passiven und aktiven Strategien mit zunehmender Anzahl der Subpopulationen $k$ vergrößert, was mit der theoretischen Schranke von $\Theta(k^{1/4})$ übereinstimmt. Es wird gezeigt, dass der EETC-Algorithmus die Leistung des Orakels (bekanntes-$p$) aktiven Strategie eng nachahmt.
• Realwelt-Daten (MovieLens): Die Autoren bewerteten ihre Methoden am MovieLens-1M-Datensatz, wobei Filmempfehlungen als Behandlungen und demografische Gruppen als Subpopulationen behandelt wurden. Die Ergebnisse zeigen, dass passive Strategien den höchsten Regret aufweisen. Sowohl die bekannte-$p$-aktive Strategie als auch EETC übertreffen die passive Baseline signifikant, wobei EETC mit zunehmendem Horizont die Leistung der Orakel-aktiven Strategie annähert.

Bedeutung und Behauptungen
Der Artikel behauptet, den spezifischen Wert der aktiven Auswahl von Subpopulationen im experimentellen Design und beim Policy-Learning zu quantifizieren. Sein primärer Beitrag besteht darin zu demonstrieren, dass aktive Subpopulationsauswahl die Leistung gegenüber passiver Stichprobennahme immer verbessert, wobei der Gewinn beträchtlich ist, wenn die Populationsverteilung verzerrt ist.

Die Autoren betonen, dass ihre Arbeit die Lücke zwischen standardmäßigen kontextuellen Banditen (bei denen Kontexte umweltbedingt sind) und experimentellem Design (bei dem der Experimentator die Stichprobe kontrolliert) schließt. Durch die Charakterisierung der optimalen Zuweisungsregel ($q_j \propto p_j^{2/3}$) und die Bereitstellung eines Algorithmus (EETC), der sich an unbekannte Verteilungen anpasst, ohne asymptotische Optimalität zu opfern, bietet der Artikel einen rigorosen Rahmen für die effiziente Ressourcenallokation in heterogenen Populationen. Die Arbeit legt nahe, dass in Szenarien, in denen gezielte Rekrutierung oder kontrollierte Stichprobennahme machbar ist, die Ignorierung der Fähigkeit, Kontexte auszuwählen, zu suboptimalen Behandlungsempfehlungen führt.