Technische Samenvatting: Bijna-Optimale Regret in Adversariale Kernel Bandits

1. Probleemformulering

Het artikel behandelt het adversariale kernel bandit-probleem, een generalisatie van adversariale lineaire bandits waarbij de verliesfuncties behoren tot een Reproducing Kernel Hilbert Space (RKHS).

• Situatie: In elke ronde $t \in [T]$ kiest een leerder een actie $x_t$ uit een eindige actieset $\mathcal{X} \subset \mathbb{R}^d$. Tegelijkertijd kiest een oblivieuze adversary een vector $w_t$ in de RKHS $\mathcal{H}$.
• Verlies: De leerder lijdt een verlies $\ell_t(x_t) = \langle \Phi(x_t), w_t \rangle_{\mathcal{H}}$, waarbij $\Phi: \mathcal{X} \to \mathcal{H}$ de kenmerkafbeelding is die geassocieerd is met een symmetrische positief-definiete kernel $K$.
• Feedback: De leerder observeert slechts het scalaire verlies $\ell_t(x_t)$, niet de vector $w_t$ of de volledige verliesfunctie.
• Doel: Minimaliseer de verwachte regret $R_T$ tegen de beste vaste actie $x^*$ op basis van achterafkennis:
  $$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]$$
• Aannames: De adversary is begrensd ($\|w_t\|_{\mathcal{H}} \le B$), en de kernel is begrensd ($K(x,x) \le 1$). Cruciaal is dat, in tegenstelling tot eerdere werken van Chatterji et al. [2019], de adversary niet beperkt is tot rang-een verliezen (d.w.z. $w_t$ hoeft niet van de vorm $\Phi(z_t)$ te zijn); $w_t$ kan elk element van $\mathcal{H}$ zijn met een begrensde norm.

2. Methodologie en Algorithmus

De auteurs stellen een algoritme voor gebaseerd op Exponentiële Gewichten (Exp2), aangepast voor oneindig-dimensionale kenmerkruimten. De kernuitdaging is dat standaard belang-gewogen schatters in lineaire bandits onbegrensd worden wanneer de kenmerkafbeelding ligt in een oneindig-dimensionale RKHS, als gevolg van verdwijnende eigenwaarden van de covariantie-operator.

Om dit te overwinnen, introduceren de auteurs twee belangrijke modificaties:

1. Geregulariseerde Belang-Gewogen Schatter:
   In plaats van de empirische covariantie-operator $\Sigma_t = \mathbb{E}_{x \sim p_t}[\Phi(x)\Phi(x)^\top]$ te inverteren, gebruikt het algoritme een ridge-geregulariseerde versie $\Sigma_t^\lambda = \Sigma_t + \lambda I_{\mathcal{H}}$. De schatter wordt gedefinieerd als:
   $$\hat{w}_t = y_t (\Sigma_t^\lambda)^{-1} \Phi(x_t)$$
   Deze regularisatie zorgt ervoor dat de schatter begrensd blijft, zelfs wanneer $\Sigma_t$ eigenwaarden dicht bij nul heeft. Dit introduceert echter een systematische bias: $\mathbb{E}[\hat{w}_t | \mathcal{F}_{t-1}] = (\Sigma_t^\lambda)^{-1}\Sigma_t w_t \neq w_t$.

2. Expliciete Bias-Correctie Term:
   Om de regularisatie-bias te compenseren, construeert het algoritme een gecorrigeerde verliesproxy $\hat{\ell}_t(x)$:
   $$\hat{\ell}_t(x) = \langle \hat{w}_t, \Phi(x) \rangle_{\mathcal{H}} - c_t(x)$$
   waarbij de correctieterm $c_t(x) = B\sqrt{\lambda} \|\Phi(x)\|_{(\Sigma_t^\lambda)^{-1}}$ is.

   • Mechanisme: De correctieterm is direct afgeleid uit de gesloten-vorm bias-expressie. Het fungeert als een puntsgewijze bovengrens voor de bias, zodat de verwachte verliesproxy het ware verlies onderschat voor de comparator (de beste vaste actie). Deze structurele keuze zorgt ervoor dat het residu aan de comparator-zijde in de regret-decompositie niet-positief is, waardoor alleen een beheersbaar residu aan de leerder-zijde overblijft.

3. Verkenningstrategie:
   Het algoritme onderhoudt een verdeling $p_t$ die een mengsel is van de huidige exponentiële-gewichtenverdeling $q_t$ en een vaste verdelingsverdeling $\nu_G$. De verdelingsverdeling wordt gekozen via een geregulariseerd G-optimale ontwerp om te waarborgen dat de effectieve dimensie gecontroleerd blijft.

3. Belangrijkste Bijdragen

• Algoritmeontwerp: Een principieel algoritme dat exponentiële gewichten combineert met een geregulariseerde schatter en een expliciete bias-correctieterm. Deze aanpak vermijdt de restrictieve rang-een adversary-aanname die vereist was door Chatterji et al. [2019].
• Regret-analyse via Effectieve Dimensie: De auteurs leiden een regretgrens af die afhankelijk is van de effectieve dimensie $d^*(\lambda)$ van de kernel, gedefinieerd als:
  $$d^*(\lambda) = \max_{\nu \in \Delta(\mathcal{X})} \text{Tr}\left( (\Sigma(\nu) + \lambda I_{\mathcal{H}})^{-1} \Sigma(\nu) \right)$$
• Verwijdering van Rang-Een Aannames: Het kader staat willekeurige begrensde RKHS-verliezen toe, wat de toepasbaarheid aanzienlijk verbreedt in vergelijking met eerdere werken die leunden op projectie-gebaseerde schatters die rang-een beperkingen vereisten.

4. Hoofdresultaten

Het artikel stelt een regretgrens vast van de vorm:
$$R_T = \tilde{O}\left( B \sqrt{T d^*(\lambda) \log |\mathcal{X}|} \right)$$
waarbij $d^*(\lambda)$ de complexiteit van de kernel vastlegt. Deze snelheid komt overeen met de bekende optimale snelheden voor het stochastische kernel bandit-probleem (tot op logaritmische factoren).

Specifieke Kernel-snelheden:

• Matérn$(\nu, d)$ Kernel: Voor een Matérn-kernel met gladheid $\nu$ op $\mathbb{R}^d$, levert de effectieve dimensie een regretgrens op van:
  $$R_T = \tilde{O}\left( T^{\frac{\nu+d}{2\nu+d}} \right)$$
  Dit verbetert de eerdere beste bekende snelheid van $\tilde{O}(T^{\frac{2\nu+d}{4\nu}})$ door Chatterji et al. [2019] en komt overeen met de ondergrens uit gelijktijdig werk [Iwazaki, 2026] tot op logaritmische factoren. Opmerkelijk is dat de eerdere snelheid niet eens sublineair was wanneer $\nu < d/2$, terwijl de nieuwe grens altijd sublineair is.
• Kwadratische Exponentiële (SE) Kernel: De grens herstelt de bijna-optimale $\tilde{O}(\sqrt{T})$ snelheid, overeenkomend met Chatterji et al. [2019] maar zonder de rang-een beperking.
• Algemene Eigenwaarde-afname:
  • Polynoom Afname ($\mu_j \le C j^{-\beta}$): Bereikt $R_T = \tilde{O}(T^{\frac{\beta+1}{2\beta}})$.
  • Exponentiële Afname ($\mu_j \le C e^{-\beta j}$): Bereikt $R_T = \tilde{O}(\sqrt{T})$.

5. Betekenis en Beweringen

Het artikel beweert de kloof te dichten tussen de prestaties van adversariale en stochastische kernel bandits. Specifiek:

• Optimaliteit: De afgeleide snelheden komen overeen met de optimale snelheden die bekend zijn voor stochastische kernel bandits (bijvoorbeeld via SupKernelUCB of methoden voor Bayesiaanse optimalisatie) tot op logaritmische factoren.
• Theoretische Vooruitgang: Door de rang-een adversary-aanname te verwijderen, zijn de resultaten van toepassing op een meer algemene en realistische klasse van adversariale omgevingen waarbij de verliesfunctie een willekeurig begrensd element van de RKHS is.
• Vergelijking met Eerdere Werken: Het werk verbetert Chatterji et al. [2019] voor Matérn-kernels en algemene polynoom-afname, en biedt strakkere grenzen die sublineair zijn in $T$ onder omstandigheden waar de eerdere grenzen dat niet waren.
• Gelijktijdig Werk: De auteurs erkennen onafhankelijk gelijktijdig werk van Iwazaki [2026] dat vergelijkbare resultaten bereikt met een nauw verwante aanpak (exponentiële gewichten met geregulariseerde schatters en bias-correctie). Het artikel merkt kleine verschillen op in de probleemopzet (bijvoorbeeld oblivieuze versus adaptieve adversary, specifieke complexiteitsmaten), maar stelt dat de kern-algoritmische en analytische bijdragen in wezen equivalent zijn.

Het artikel concludeert dat de voorgestelde methode een bijna-optimale oplossing biedt voor het adversariale kernel bandit-probleem, en effectief omgaat met de uitdagingen van oneindig-dimensionale kenmerkruimten door middel van regularisatie en expliciete bias-correctie.