Learning What to Recommend: Minimax Optimal Simple Regret in Logistic Bandits

Problemformulierung
Diese Arbeit untersucht stochastische logistische Banditen unter dem Simple-Regret-Ziel. In diesem Setting interagiert ein Lernender über $T$ Runden mit einer Umgebung, wählt Aktionen $A_t$ aus einer Menge $\mathcal{A}$ aus und beobachtet Bernoulli-Belohnungen $X_t$ mit dem Erwartungswert $\mu(\phi(A_t)^\top \theta^*)$, wobei $\mu$ die Sigmoid-Funktion ist, $\phi$ eine bekannte Merkmalsabbildung und $\theta^*$ ein unbekannter Parameter in $\mathbb{R}^d$. Im Gegensatz zum kumulativen Regret, bei dem das Ziel darin besteht, die Summe der Belohnungen während der Exploration zu maximieren, bewertet das Simple-Regret-Ziel den Lernenden ausschließlich anhand der Qualität einer einzigen finalen Empfehlung $\hat{a}$ nach $T$ Runden. Das Regret ist definiert als die Differenz zwischen dem erwarteten Belohnungswert der optimalen Aktion und dem erwarteten Belohnungswert der empfohlenen Aktion.

Eine kritische Herausforderung bei logistischen Banditen ist die nicht einheitliche Informativität von Aktionen. Aufgrund der Sigmoid-Verknüpfung liefern Aktionen in „gesättigten" Bereichen (wo der mittlere Belohnungswert nahe 0 oder 1 liegt) nahezu deterministische Belohnungen, bieten aber wenig Information über den Parameter $\theta^*$. Umgekehrt sind Aktionen nahe dem Ursprung (wo die Sigmoid-Funktion am steilsten ist) hochinformativ, können jedoch geringere unmittelbare Belohnungen liefern. Dies erzeugt eine Geometrie, bei der die Aktionen, die für die unmittelbare Belohnung am besten sind (Exploitation), sich von denen unterscheiden, die am besten zur Identifizierung der optimalen Aktion geeignet sind (Exploration).

Methodik
Die Autoren schlagen zwei krümmungsbewusste Algorithmen vor, die die lokale Geometrie der Sigmoid-Funktion ausnutzen:

1. MULOG (Max-Uncertainty-Log): Ein deterministischer reiner Explorationsalgorithmus.

   • Mechanismus: MULOG erhält eine Konfidenzmenge $W_t$ für $\theta^*$ und konstruiert eine krümmungsgewichtete Designmatrix $L_t$. Der Unsicherheitswert für eine Aktion $a$ und einen Parameter $\theta$ ist definiert als $U(a, \theta, L_t) = \sqrt{\dot{\mu}(\phi(a)^\top \theta)} \|\phi(a)\|_{L_t^{-1}}$, wobei $\dot{\mu}$ die Ableitung der Sigmoid-Funktion ist (repräsentiert die lokale Krümmung).
   • Auswahl: In jeder Runde wählt der Algorithmus das Aktions-Parameter-Paar $(A_t, \theta_t)$ aus, das diesen Unsicherheitswert maximiert.
   • Terminierung: Nach $T$ Runden gibt es die Aktion zurück, die bezüglich eines aus der finalen Konfidenzmenge gesampelten Parametervektors gierig ist.
   • Optimierung: Für endliche Aktionsmengen reduziert sich der Auswahlschritt auf das Lösen einer endlichen Sammlung konvexer Optimierungsprobleme.

2. THATS (Try Hard Thompson Sampling): Eine randomisierte, rechnerisch leichtere Alternative.

   • Mechanismus: Anstatt das exakte Maximum der Unsicherheit zu lösen, sampelt THATS eine Richtung $\tilde{\theta}_t$ aus einer zentrierten Gauß-Verteilung mit der Kovarianz $L_t^{-1}$.
   • Auswahl: Es wählt die Aktion aus, die den randomisierten Unsicherheitswert $\sqrt{\dot{\mu}(\phi(a)^\top \bar{\theta}_t)} |\phi(a)^\top \tilde{\theta}_t|$ maximiert, wobei $\bar{\theta}_t$ eine eingeschränkte Maximum-Likelihood-Schätzung ist.
   • Abwägung: Dieser Ansatz vermeidet die für MULOG erforderliche konvexe Optimierung, verursacht jedoch statistische Kosten, was zu einer etwas lockereren Regret-Schranke führt.

Hauptbeiträge

• Minimax-Untere Schranke: Die Arbeit etabliert eine untere Minimax-Schranke erster Ordnung der Größenordnung $\Omega\left(\frac{d}{\sqrt{\kappa^* T}}\right)$, wobei $\kappa^*$ die inverse Steigung der Sigmoid-Funktion an der optimalen Aktion ist (d. h. $\kappa^* = 1/\dot{\mu}(\phi(a^*)^\top \theta^*)$).
  • Unterschiedlicher Härte-Mechanismus: Im Gegensatz zu unteren Schranken für kumulatives Regret (z. B. Abeille et al., 2021), die auf den Kosten von Information beruhen (den Lernenden zwingend, nahezu optimale Arme zu spielen), wird diese untere Schranke aus einer Konstruktion eines „verschobenen gesättigten Hyperwürfels" abgeleitet. In dieser Konstruktion werden sowohl statistische Information als auch Wertempfindlichkeit durch dieselbe lokale Krümmung in einem gesättigten Bereich kontrolliert. Dies zeigt, dass das Problem auch dann schwierig bleibt, wenn die Freiheit besteht, rein nach Information zu sampeln, falls die optimale Aktion in einem flachen Bereich der Sigmoid-Funktion liegt.
• Optimale Algorithmen:
  • MULOG erreicht eine obere Schranke für das Simple Regret von $\tilde{O}\left(\frac{d}{\sqrt{\kappa^* T}}\right)$ und entspricht damit der unteren Schranke bis auf logarithmische Faktoren. Dies ist die erste direkte Garantie für reine Exploration bei logistischen Banditen, die eine instanzweise Minimax-Optimalität erreicht.
  • THATS erreicht eine Schranke von $\tilde{O}\left(\frac{d^{3/2}}{\sqrt{\kappa^* T}}\right)$. Der zusätzliche Faktor $\sqrt{d}$ ergibt sich aus der Verwendung einer geometrieagnostischen randomisierten Approximation der Richtung maximaler Unsicherheit.
• Geometrische Einsicht: Die Autoren zeigen, dass die Worst-Case-Geometrie (verschobene gesättigte Instanzen) nicht der einzige Fall ist. Sie belegen, dass „informative, aber belohnungsarme Aktionen" (Sonden) in der Aktionsmenge existieren können. Diese Aktionen liegen im Bereich hoher Krümmung der Sigmoid-Funktion und liefern signifikante Informationen über die optimale Richtung, obwohl sie einen niedrigen erwarteten Belohnungswert aufweisen.

Ergebnisse

• Theoretisch: Die abgeleiteten Schranken bestätigen, dass die Schwierigkeit des logistischen Simple Regret durch die Krümmung an der optimalen Aktion bestimmt wird. Die Algorithmen steuern die Unsicherheit in den krümmungsgewichteten Merkmalsrichtungen erfolgreich.
• Empirisch: Experimente sowohl an „schwierigen" Geometrien (verschobene gesättigte Hyperwürfel) als auch an „einfachen" Geometrien (mit hinzugefügten informativen Sondearmen) stützen die theoretischen Befunde:
  • Bei schwierigen Instanzen performen MULOG und THATS wie von den Minimax-Schranken vorhergesagt.
  • Bei einfachen Instanzen mit Sondearmen übertreffen reine Explorationsmethoden (MULOG und THATS) kumulative-Regret-Baselines (wie Cumulative Thompson Sampling und Online-to-Batch-Konvertierungen) deutlich. Die reinen Explorationsmethoden sampeln aktiv die belohnungsarmen, hochinformativen Sonden, was die Anzahl der Runden drastisch reduziert, die benötigt werden, um einen niedrigen Simple-Regret-Schwellenwert zu erreichen.
  • Kumulative-Regret-Methoden versagen darin, diese Sonden effektiv auszunutzen, da ihre Online-to-Batch-Konvertierung die Aufnahme belohnungsarmer Aktionen in die Verteilung der finalen Empfehlung bestraft.

Bedeutung
Die Arbeit behauptet, dass reine Exploration bei logistischen Banditen eine von kumulativen Regret-Problemen unterschiedliche Geometrie aufweist. Der Hauptbeitrag besteht darin, zu identifizieren, dass die lokale Krümmung an der optimalen Aktion ($\kappa^*$) der bestimmende Faktor für die Minimax-Rate erster Ordnung ist. Durch die Entwicklung von Algorithmen, die diese Krümmung explizit berücksichtigen, erreichen die Autoren im Worst-Case eine Minimax-optimale Performance. Darüber hinaus hebt die Arbeit eine praktische Implikation hervor: In Szenarien wie A/B-Tests oder der Datensammlung für Belohnungsmodelle kann das aktive Aufspüren von „informativen, aber belohnungsarmen" Aktionen die Identifizierung der besten finalen Politik erheblich beschleunigen – ein Verhalten, das Standardalgorithmen für kumulatives Regret strukturell nicht aufweisen können. Die Ergebnisse dienen als Ausgangspunkt für eine schärfere Theorie der entscheidungsorientierten Exploration in nichtlinearen Banditen.