Technische Zusammenfassung: Nahezu optimale Regret bei adversarischen Kernel-Bandits

1. Problemformulierung

Die Arbeit behandelt das Problem der adversarischen Kernel-Bandits, eine Verallgemeinerung adversarischer linearer Bandits, bei der die Verlustfunktionen zu einem Reproducing Kernel Hilbert Space (RKHS) gehören.

• Setting: In jeder Runde $t \in [T]$ wählt ein Lernender eine Aktion $x_t$ aus einer endlichen Aktionsmenge $\mathcal{X} \subset \mathbb{R}^d$. Gleichzeitig wählt ein oblivious (nicht-adaptiver) Gegner einen Vektor $w_t$ im RKHS $\mathcal{H}$.
• Verlust: Der Lernende erleidet einen Verlust $\ell_t(x_t) = \langle \Phi(x_t), w_t \rangle_{\mathcal{H}}$, wobei $\Phi: \mathcal{X} \to \mathcal{H}$ die Merkmalsabbildung ist, die zu einem symmetrischen positiv definiten Kernel $K$ gehört.
• Rückmeldung: Der Lernende beobachtet nur den skalaren Verlust $\ell_t(x_t)$, nicht den Vektor $w_t$ oder die vollständige Verlustfunktion.
• Ziel: Minimierung des erwarteten Regrets $R_T$ gegenüber der besten festen Aktion $x^*$ im Nachhinein:
  $$R_T = \mathbb{E}\left[ \sum_{t=1}^T \langle \Phi(x_t), w_t \rangle_{\mathcal{H}} - \sum_{t=1}^T \langle \Phi(x^*), w_t \rangle_{\mathcal{H}} \right]$$
• Annahmen: Der Gegner ist beschränkt ($\|w_t\|_{\mathcal{H}} \le B$), und der Kernel ist beschränkt ($K(x,x) \le 1$). Im Gegensatz zu früheren Arbeiten von Chatterji et al. [2019] ist der Gegner nicht auf verluste vom Rang eins beschränkt (d. h., $w_t$ muss nicht die Form $\Phi(z_t)$ haben); $w_t$ kann ein beliebiges Element von $\mathcal{H}$ mit beschränkter Norm sein.

2. Methodik und Algorithmus

Die Autoren schlagen einen Algorithmus vor, der auf Exponentiellen Gewichten (Exp2) basiert und für unendlichdimensionale Merkmalsräume angepasst wurde. Die zentrale Herausforderung besteht darin, dass standardmäßige gewichtete Schätzer in linearen Bandits unbeschränkt werden, wenn die Merkmalsabbildung in einem unendlichdimensionalen RKHS liegt, was auf verschwindende Eigenwerte des Kovarianzoperators zurückzuführen ist.

Um dies zu überwinden, führen die Autoren zwei wesentliche Modifikationen ein:

1. Regularisierter gewichteter Schätzer:
   Anstatt den empirischen Kovarianzoperator $\Sigma_t = \mathbb{E}_{x \sim p_t}[\Phi(x)\Phi(x)^\top]$ zu invertieren, verwendet der Algorithmus eine ridge-regularisierte Version $\Sigma_t^\lambda = \Sigma_t + \lambda I_{\mathcal{H}}$. Der Schätzer ist definiert als:
   $$\hat{w}_t = y_t (\Sigma_t^\lambda)^{-1} \Phi(x_t)$$
   Diese Regularisierung stellt sicher, dass der Schätzer auch dann beschränkt bleibt, wenn $\Sigma_t$ Eigenwerte nahe Null aufweist. Dies führt jedoch zu einer systematischen Verzerrung: $\mathbb{E}[\hat{w}_t | \mathcal{F}_{t-1}] = (\Sigma_t^\lambda)^{-1}\Sigma_t w_t \neq w_t$.

2. Expliziter Bias-Korrekturterm:
   Um die durch die Regularisierung verursachte Verzerrung auszugleichen, konstruiert der Algorithmus einen korrigierten Verlust-Proxy $\hat{\ell}_t(x)$:
   $$\hat{\ell}_t(x) = \langle \hat{w}_t, \Phi(x) \rangle_{\mathcal{H}} - c_t(x)$$
   wobei der Korrekturterm $c_t(x) = B\sqrt{\lambda} \|\Phi(x)\|_{(\Sigma_t^\lambda)^{-1}}$ ist.

   • Mechanismus: Der Korrekturterm wird direkt aus dem geschlossenen Ausdruck für die Verzerrung abgeleitet. Er wirkt als punktweise obere Schranke für die Verzerrung und stellt sicher, dass der erwartete Verlust-Proxy den wahren Verlust für den Vergleichswert (die beste feste Aktion) unterschätzt. Diese strukturelle Wahl gewährleistet, dass der Residuum auf der Seite des Vergleichswerts in der Regret-Zerlegung nicht-positiv ist, sodass nur ein kontrollierbares Residuum auf der Seite des Lernenden verbleibt.

3. Explorationsstrategie:
   Der Algorithmus hält eine Verteilung $p_t$ vor, die eine Mischung aus der aktuellen Verteilung der exponentiellen Gewichte $q_t$ und einer festen Explorationsverteilung $\nu_G$ ist. Die Explorationsverteilung wird über ein regularisiertes G-optimal-Design gewählt, um die effektive Dimension kontrolliert zu halten.

3. Hauptbeiträge

• Algorithmenentwurf: Ein prinzipieller Algorithmus, der exponentielle Gewichte mit einem regularisierten Schätzer und einem expliziten Bias-Korrekturterm kombiniert. Dieser Ansatz vermeidet die restriktive Annahme eines Gegners mit Verlusten vom Rang eins, die von Chatterji et al. [2019] gefordert wurde.
• Regret-Analyse via Effektiver Dimension: Die Autoren leiten eine Regret-Schranke her, die von der effektiven Dimension $d^*(\lambda)$ des Kernels abhängt, definiert als:
  $$d^*(\lambda) = \max_{\nu \in \Delta(\mathcal{X})} \text{Tr}\left( (\Sigma(\nu) + \lambda I_{\mathcal{H}})^{-1} \Sigma(\nu) \right)$$
• Entfernung der Rang-eins-Annahme: Das Framework erlaubt beliebige beschränkte RKHS-Verluste und erweitert die Anwendbarkeit erheblich im Vergleich zu früheren Arbeiten, die auf projektionsbasierten Schätzern beruhten, die Rang-eins-Beschränkungen erforderten.

4. Hauptergebnisse

Die Arbeit etabliert eine Regret-Schranke der Form:
$$R_T = \tilde{O}\left( B \sqrt{T d^*(\lambda) \log |\mathcal{X}|} \right)$$
wobei $d^*(\lambda)$ die Komplexität des Kernels erfasst. Diese Rate entspricht den bekannten optimalen Raten für das stochastische Kernel-Bandit-Problem (bis auf logarithmische Faktoren).

Spezifische Kernel-Raten:

• Matérn$(\nu, d)$-Kernel: Für einen Matérn-Kernel mit Glattheit $\nu$ auf $\mathbb{R}^d$ ergibt die effektive Dimension eine Regret-Schranke von:
  $$R_T = \tilde{O}\left( T^{\frac{\nu+d}{2\nu+d}} \right)$$
  Dies verbessert die bisher beste bekannte Rate von $\tilde{O}(T^{\frac{2\nu+d}{4\nu}})$ von Chatterji et al. [2019] und entspricht der unteren Schranke aus paralleler Arbeit [Iwazaki, 2026] bis auf logarithmische Faktoren. Bemerkenswert ist, dass die vorherige Rate nicht einmal sublinear war, wenn $\nu < d/2$, während die neue Schranke immer sublinear ist.
• Quadratisch Exponentieller (SE) Kernel: Die Schranke stellt die nahezu optimale $\tilde{O}(\sqrt{T})$-Rate wieder her und entspricht Chatterji et al. [2019], jedoch ohne die Rang-eins-Beschränkung.
• Allgemeine Eigenwertabnahme:
  • Polynomiale Abnahme ($\mu_j \le C j^{-\beta}$): Erzielt $R_T = \tilde{O}(T^{\frac{\beta+1}{2\beta}})$.
  • Exponentielle Abnahme ($\mu_j \le C e^{-\beta j}$): Erzielt $R_T = \tilde{O}(\sqrt{T})$.

5. Bedeutung und Behauptungen

Die Arbeit behauptet, die Lücke zwischen der Leistung adversarischer und stochastischer Kernel-Bandits zu schließen. Insbesondere:

• Optimalität: Die abgeleiteten Raten entsprechen den optimalen Raten, die für stochastische Kernel-Bandits bekannt sind (z. B. via SupKernelUCB oder Methoden der bayesschen Optimierung), bis auf logarithmische Faktoren.
• Theoretischer Fortschritt: Durch die Entfernung der Annahme eines Gegners mit Verlusten vom Rang eins gelten die Ergebnisse für eine allgemeinere und realistischere Klasse adversarischer Umgebungen, in denen die Verlustfunktion ein beliebiges beschränktes Element des RKHS ist.
• Vergleich mit früheren Arbeiten: Die Arbeit verbessert Chatterji et al. [2019] für Matérn-Kernel und allgemeine polynomiale Abnahme und liefert engere Schranken, die unter Bedingungen, unter denen die vorherigen Schranken nicht sublinear waren, sublinear in $T$ sind.
• Parallele Arbeit: Die Autoren erkennen unabhängige parallele Arbeit von Iwazaki [2026] an, die ähnliche Ergebnisse mit einem eng verwandten Ansatz (exponentielle Gewichte mit regularisierten Schätzern und Bias-Korrektur) erzielt. Die Arbeit weist geringfügige Unterschiede im Problemsetup auf (z. B. oblivious vs. adaptiver Gegner, spezifische Komplexitätsmaße), behauptet jedoch, dass die Kernbeiträge in Bezug auf Algorithmen und Analyse im Wesentlichen äquivalent sind.

Die Arbeit kommt zu dem Schluss, dass die vorgeschlagene Methode eine nahezu optimale Lösung für das Problem der adversarischen Kernel-Bandits bietet und die Herausforderungen unendlichdimensionaler Merkmalsräume effektiv durch Regularisierung und explizite Bias-Korrektur bewältigt.