Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicality

Technisches Zusammenfassung: Follow-the-Perturbed-Leader für entkoppelte Banditen

Problemstellung
Dieser Beitrag adressiert das Problem der entkoppelten Multi-Armed-Bandits (MAB), ein Szenario, in dem der Lernende in jeder Runde $t$ zwei unterschiedliche Arme auswählt: einen Arm $i_t$ zur Ausbeutung (der den Verlust $\ell_{t, i_t}$ verursacht, ohne ihn zu beobachten) und einen Arm $j_t$ zur Exploration (der den Verlust $\ell_{t, j_t}$ beobachtet, ohne ihn zu verursachen). Dieser Rahmen modelliert Szenarien wie Ultra-Breitband-Kommunikationssysteme (Erfassung eines Kanals, der sich vom Übertragungskanal unterscheidet) und den Sim-to-Real-Transfer in der Robotik. Das Ziel besteht darin, das Pseudo-Regret zu minimieren, definiert als die Differenz zwischen dem kumulativen Verlust, der durch die Ausbeutungswahl des Lernenden entsteht, und dem kumulativen Verlust des besten festen Arms im Nachhinein.

Der Beitrag zielt auf Best-of-Both-Worlds (BOBW)-Garantien ab, mit dem Ziel, Folgendes zu erreichen:

1. Optimales Regret von $O(\sqrt{KT})$ im adversariellen Regime (wo Verluste durch einen adaptiven Gegner bestimmt werden).
2. Nahezu optimales, zeitunabhängiges Regret von $O(K/\Delta_{\min})$ im stochastisch eingeschränkten adversariellen (SCA) Regime (das das standardmäßige stochastische Setting einschließt), wobei $\Delta_{\min}$ die minimale Suboptimalitätslücke ist.

Methodik
Die Autoren schlagen eine neue Strategie vor, die auf dem Follow-the-Perturbed-Leader (FTPL)-Rahmenwerk basiert und speziell entwickelt wurde, um die rechnerischen Engpässe bestehender BOBW-Strategien in entkoppelten Settings zu überwinden.

• Ausbeutungsstrategie: Der Lernende wählt den Ausbeutungsarm $i_t$ durch Minimierung einer gestörten kumulativen Verlustschätzung aus:
  $$i_t = \arg\min_{i \in [K]} \left\{ \hat{L}_{t,i} - \frac{r_{t,i}}{\eta_t} \right\}$$
  wobei $\hat{L}_{t,i}$ die geschätzte kumulative Verlustsumme ist, $\eta_t$ die Lernrate und $r_{t,i}$ i.i.d. zufällige Störungen sind, die aus einer Pareto-Verteilung $P_\alpha$ mit Formparameter $\alpha > 1$ gezogen werden. Diese Art der Störung entspricht der $\beta$-Tsallis-INF-Strategie (mit $\alpha = 1/(1-\beta)$), die für das Erreichen von BOBW-Garantien bekannt ist.

• Explorationsstrategie (Schlüsselinnovation): Bei standardmäßigen FTPL-Banditalgorithmen erfordert die Konstruktion eines unverzerrten, gewichteten (IW) Verlustschätzers typischerweise die Kenntnis der exakten Wahrscheinlichkeit $w_{t,i}$, mit der Arm $i$ ausgewählt wird. Bei entkoppelten Banditen muss die Explorationswahrscheinlichkeit $p_{t,i}$ basierend auf $w_{t,i}$ festgelegt werden. FTPL liefert jedoch (im Gegensatz zu FTRL) keinen geschlossenen Ausdruck für $w_{t,i}$, und die Schätzung des vollständigen Vektors mittels geometrischer Resampling-Verfahren ist rechnerisch teuer ($O(K^2)$ oder höher).
  Um dies zu lösen, führen die Autoren eine Surrogatwahrscheinlichkeit $q_{t,i}$ ein, die direkt aus den aktuellen Verlustschätzungen berechnet werden kann, ohne Resampling oder konvexe Optimierung:
  $$q_{t,i} = \left( \frac{1}{1 + \eta_t \hat{L}_{t,i}} \wedge \frac{1}{\sigma_{t,i}^{1/\alpha}} \right)^{\frac{\alpha+1}{2}}$$
  wobei $\sigma_{t,i}$ der Rang von $\hat{L}_{t,i}$ unter allen Armen ist. Der Explorationsarm $j_t$ wird dann gemäß der normalisierten Verteilung $p_{t,i} = q_{t,i} / \sum_j q_{t,j}$ ausgewählt. Dieser Ansatz vermeidet die Notwendigkeit expliziter $w_{t,i}$-Werte, während die theoretischen Eigenschaften, die für BOBW-Garantien erforderlich sind, erhalten bleiben.

Hauptbeiträge

1. Erste FTPL-basierte BOBW-Strategie für entkoppelte Banditen: Der Beitrag stellt die erste Strategie vor, die BOBW-Garantien in entkoppelten Banditen erreicht, ohne konvexe Optimierungsprobleme zu lösen (wie sie bei FTRL-basierten Ansätzen wie Decoupled-Tsallis-INF erforderlich sind) oder Resampling-Verfahren einzusetzen (die typischerweise für die FTPL-Wahrscheinlichkeitsschätzung benötigt werden).
2. Rechnerische Effizienz: Durch den Ersatz der Berechnung des vollständigen Wahrscheinlichkeitsvektors durch die effizient berechenbare Surrogatgröße $q_{t,i}$ reduziert die vorgeschlagene Strategie die Komplexität pro Schritt. Während das Sortieren der Verlustschätzungen $O(K \log K)$ erfordert, stellen die Autoren fest, dass eine optimierte Implementierung $O(K)$-Updates durch inkrementelles Verfolgen von Rangänderungen erreichen kann. Dies steht im Gegensatz zu FTRL-Strategien, die in jedem Schritt iterative konvexe Optimierung (z. B. Newton-Verfahren) erfordern.
3. Theoretische Garantien:
   • Adversarielles Regime: Die Strategie erreicht eine Regret-Schranke von $O(\sqrt{KT})$, die der bekannten unteren Schranke für entkoppelte Banditen entspricht.
   • Stochastisches/SCA-Regime: Die Strategie erreicht eine Regret-Schranke von $O(K/\Delta_{\min})$ (spezifisch $O(\sqrt{K/\Delta_{\min}} \sum_{i \neq i^*} 1/\Delta_i + K/\Delta_{\min})$ für $\alpha=3$), die nahezu optimal ist und die zeitabhängigen Schranken standardmäßiger stochastischer Banditen verbessert.

Ergebnisse

• Theoretisch: Der Beitrag liefert rigorose Beweise (durch Zerlegung des Regrets in Stabilitäts- und Strafterme), die zeigen, dass die Surrogatwahrscheinlichkeit $q_{t,i}$ der wahren Ausbeutungswahrscheinlichkeit hinreichend nahe ist, um die notwendigen Regret-Schranken aufrechtzuerhalten.
• Empirisch: Experimente mit synthetischen Daten (sowohl adversarielle als auch stochastische Regime) und einer realen Simulation unter Verwendung des MovieLens-100K-Datensatzes zeigen, dass die vorgeschlagene FTPL-Strategie:
  • Im Vergleich zu bestehenden BOBW-Strategien (Decoupled-Tsallis-INF/FTRL und EXP3) ein geringeres kumulatives Regret erreicht.
  • Eine überlegene rechnerische Effizienz demonstriert. Im adversariellen Regime läuft die vorgeschlagene Strategie signifikant schneller als FTRL-basierte Baselines. Für $K=64$ wurde ein Laufzeitverhältnis von FTRL zu FTPL von etwa dem 1363-fachen beobachtet.
  • Sich effektiv mit der Anzahl der Arme $K$ skaliert und Robustheit über verschiedene Lückengrößen $\Delta$ hinweg beibehält.

Bedeutung und Behauptungen
Der Beitrag behauptet, dass sein Hauptbeitrag die Lücke zwischen der theoretischen Optimalität von FTRL-basierten BOBW-Strategien und der rechnerischen Effizienz von FTPL im Kontext entkoppelter Banditen schließt. Durch die Eliminierung der Notwendigkeit für konvexe Optimierung und Resampling ermöglicht die vorgeschlagene Methode, dass FTPL seine Effizienzvorteile voll ausschöpfen kann, ohne die Regret-Leistung zu beeinträchtigen. Die Autoren schlagen vor, dass die Technik der Verwendung effizient berechenbarer Surrogatwahrscheinlichkeiten anstelle exakter Wahrscheinlichkeitsvektoren auf andere algorithmische Rahmenwerke (wie die Prod-Familie) jenseits von FTPL anwendbar sein könnte und potenziell eine verbesserte rechnerische Effizienz in breiteren Bandit-Settings ermöglicht. Die Arbeit wird durch praktische Anwendungen in Kommunikationssystemen und Robotik motiviert, wo die Rechenlatenz pro Schritt kritisch ist.