Pure Exploration Beyond Reward Feedback: The Role of Post-Action Context

Technische Zusammenfassung: Reine Exploration jenseits von Belohnungsrückmeldung: Die Rolle des Post-Action-Kontexts

Problemformulierung
Dieser Artikel führt eine neue Variante des Problems der Best-Arm-Identifikation (BAI) im Setting mit festem Konfidenzniveau für stochastische Multi-Armed-Bandits (MAB) ein. In diesem Setting, bezeichnet als „BAI mit Post-Action-Kontext", wählt der Lerner eine Aktion (Arm) $X$ aus und beobachtet nicht nur die Belohnung $Y$, sondern auch einen intermediären Post-Action-Kontext $Z$. Der Kontext $Z$ wird als Folge der gewählten Aktion generiert, was dieses Problem von standardmäßigen kontextuellen Bandits unterscheidet, bei denen der Kontext vor der Aktion vorliegt.

Die Autoren analysieren zwei strukturelle Regime, die durch die kausale Beziehung zwischen Aktion, Kontext und Belohnung definiert sind:

1. Separator-Kontext: Die Belohnung $Y$ hängt ausschließlich vom Kontext $Z$ ab, wodurch $X$ und $Y$ bedingt unabhängig gegeben $Z$ sind ($P(Y|X, Z) = P(Y|Z)$). In diesem Fall wird die Verteilung der Belohnung vollständig durch den beobachteten Kontext bestimmt.
2. Nicht-Separator-Kontext: Die Belohnung $Y$ hängt sowohl von der Aktion $X$ als auch vom Kontext $Z$ ab ($P(Y|X, Z) \neq P(Y|Z)$). Hier liefert der Kontext zusätzliche Informationen, ist jedoch keine hinreichende Statistik für die Belohnung.

Das Ziel besteht darin, den Arm mit der höchsten erwarteten Belohnung mit einer Fehlerwahrscheinlichkeit von höchstens $\delta$ zu identifizieren, wobei die Stichprobenkomplexität (die Anzahl der erforderlichen Runden) minimiert werden soll.

Methodik und Algorithmen
Der Artikel leitet instanzabhängige untere Schranken für die Stichprobenkomplexität für beide Settings her und schlägt Algorithmen vor, die diese Schranken asymptotisch erreichen.

• Separator-Setting:

  • Untere Schranke: Die Autoren leiten eine untere Schranke her, die von den Häufigkeiten der beobachteten Kontexte abhängt und nicht von den Häufigkeiten der gezogenen Arme. Dies liegt daran, dass im Separator-Setting jede Beobachtung eines spezifischen Kontexts $Z=j$ Informationen über die mittlere Belohnung dieses Kontexts liefert, unabhängig davon, welcher Arm ihn erzeugt hat.
  • Algorithmus (STS): Der vorgeschlagene „Separator Track and Stop" (STS)-Algorithmus verwendet eine neuartige Abtastregel namens G-tracking. Im Gegensatz zu traditionellen Methoden, die optimale Häufigkeiten des Ziehens von Armen verfolgen, verfolgt G-tracking die optimalen Häufigkeiten der Beobachtung von Kontexten. Es behandelt das Problem als eine aktive Off-Policy-Lernaufgabe, bei der der Lerner eine Verteilung über Arme auswählt, um eine Zielverteilung über Kontexte zu erreichen. Der Algorithmus löst ein konvexes Optimierungsproblem, um die optimalen Kontexthäufigkeiten zu finden, und verwendet eine geometrische Projektion, um die nächste Armverteilung auszuwählen, wodurch sichergestellt wird, dass die beobachteten Kontexthäufigkeiten gegen das optimale Ziel konvergieren.

• Nicht-Separator-Setting:

  • Untere Schranke: Die hergeleitete untere Schranke berücksichtigt die gemeinsame Verteilung von Aktionen und Kontexten.
  • Algorithmus (NSTS): Der „Non-Separator Track and Stop" (NSTS)-Algorithmus erweitert das klassische Track-and-Stop-Framework. Er setzt D-tracking ein, um die optimalen Anteile des Ziehens spezifischer Arme zu schätzen und zu verfolgen, wobei die gemeinsamen Informationen von Aktionen und ihren resultierenden Kontexten genutzt werden, um die Schätzungen der mittleren Belohnungen zu verfeinern.

Hauptbeiträge

1. Problemdefinition: Formalisierung von BAI mit Post-Action-Kontext, Unterscheidung zwischen Separator- und Nicht-Separator-Struktur-Regimen.
2. Theoretische Schranken: Herleitung instanzabhängiger unterer Schranken für die Stichprobenkomplexität für beide Regime. Es wird gezeigt, dass die Separator-Schranke strikt enger ist als Schranken, die durch Ignorieren des Kontexts abgeleitet wurden.
3. Algorithmusdesign:
   • Einführung von G-tracking, einer Abtastregel, die im Separator-Setting direkt die Häufigkeiten der Kontextbeobachtung optimiert und dabei die Geometrie des Kontextrraums ausnutzt.
   • Erweiterung des Track-and-Stop-Frameworks auf das Nicht-Separator-Setting (NSTS).
4. Suboptimalitätsanalyse: Theoretischer und empirischer Nachweis, dass Algorithmen, die Post-Action-Kontext ignorieren (wie standardmäßiges Track-and-Stop), strikt suboptimal sind. Im Separator-Setting kann das Ignorieren des Kontexts zu willkürlich großen Erhöhungen der Stichprobenkomplexität führen, selbst wenn die Belohnungslücken klein sind, da die bedingte Unabhängigkeitsstruktur nicht genutzt wird.
5. Reduktionsanalyse: Der Artikel analysiert die Reduktion des Separator-Problems auf lineare Bandits und zeigt, dass solche Reduktionen die untere Schranke für die Stichprobenkomplexität im Vergleich zum vorgeschlagenen direkten Ansatz erhöhen.

Ergebnisse

• Theoretisch: Die vorgeschlagenen Algorithmen (STS und NSTS) werden als $\delta$-korrekt bewiesen und erreichen asymptotische Optimalität, wobei sie die hergeleiteten unteren Schranken für $\delta \to 0$ erreichen.
• Empirisch: Experimente mit synthetischen Daten und realen Daten (KuaiSAR-Empfehlungsprotokolle) zeigen signifikante Leistungssteigerungen.
  • Im Separator-Setting übertrifft STS die Baselines (Track-and-Stop und Lazy Track-and-Stop) drastisch, die oft versagen, innerhalb angemessener Zeithorizonte zu stoppen.
  • Im Nicht-Separator-Setting reduziert NSTS die erforderliche Anzahl an Stichproben im Vergleich zu Track-and-Stop, das Kontextinformationen ignoriert, erheblich.
  • Verlaufsplots bestätigen, dass STS gegen die optimalen Kontexthäufigkeiten konvergiert, während die Baselines versagen, sich mit der optimalen Strategie in Einklang zu bringen.

Bedeutung und Behauptungen
Der Artikel behauptet, dass die Nutzung von Post-Action-Kontext die optimale Strategie für reine Exploration grundlegend verändert. Die Autoren betonen, dass in Szenarien, in denen intermediäre Beobachtungen (Mediatoren) verfügbar sind, deren Ignorieren zu erheblicher Ineffizienz führt. Insbesondere ermöglicht im Separator-Setting die Fähigkeit, Informationen über verschiedene Arme zu poolen, die denselben Kontext erzeugen, eine viel schnellere Identifikation des besten Arms. Die Arbeit hebt hervor, dass standardmäßige BAI-Algorithmen nicht nur suboptimal sind, sondern in diesen strukturierten Umgebungen willkürlich ineffizient sein können. Der Artikel schließt, dass zukünftige Arbeiten den Fall adressieren könnten, in dem die Kontextwahrscheinlichkeitsmatrix unbekannt ist, wobei dies nicht-konvexe Herausforderungen einführt, die die Entwicklung effizienter Algorithmen erschweren.