Technische Samenvatting: Een gezamenlijk efficiënt en optimaal algoritme voor heteroskedastische gegeneraliseerde lineaire bandits met adversariële corrupties

1. Probleemstelling

Het artikel behandelt het probleem van heteroskedastische gegeneraliseerde lineaire bandits (GLBs) in aanwezigheid van adversariële corrupties. Deze setting verenigt drie uitdagende aspecten van sequentiële besluitvorming:

1. Gegeneraliseerde Lineaire Modellen (GLMs): De verwachte beloning voor een arm $x_t \in \mathbb{R}^d$ volgt een GLM, $E[r_t|x_t; \theta^\star] = \mu(\langle x_t, \theta^\star \rangle)$, waarbij $\mu$ een bekende inverse linkfunctie is en $\theta^\star$ een onbekende parameter. Dit raamwerk omvat logistische, Poisson en Gaussische lineaire bandits.
2. Heteroskedasticiteit: De variantie van de beloning is niet constant maar varieert tussen armen en tijdstappen. Specifiek is $\text{Var}[r_t|x_t, \tau_t; \theta^\star] = g(\tau_t) \dot{\mu}(\langle x_t, \theta^\star \rangle)$, waarbij $g(\tau_t)$ een dispersieparameter is die exogeen tijdsvariërend kan zijn (bijv. in Gaussische bandits) of endogeen bepaald kan worden door de keuze van de arm (bijv. in logistische/Poisson bandits).
3. Adversariële Corrupties: Een adaptieve tegenstander (adversary) manipuleert de geobserveerde beloning op elk tijdstip $t$ door een corruptie $c_t$ toe te voegen, zodanig dat de leerder $\tilde{r}_t = r_t + c_t$ observeert. De tegenstander opereert onder een totale budgetbeperking $\sum_{t=1}^T |c_t| \le C$.

Het doel is om de cumulatieve pseudo-regret te minimaliseren, gedefinieerd als het verschil tussen de verwachte beloning van de optimale arm en de gekozen arm over $T$ rondes.

2. Methodologie: HCW-GLB-OMD

De auteurs stellen HCW-GLB-OMD (Hessian-Confidence Weighted GLB-OMD) voor, een algoritme dat ontworpen is om zowel computationeel efficiënt als statistisch optimaal te zijn. Het algoritme integreert twee primaire componenten:

A. Online Mirror Descent (OMD) Schatter

In tegenstelling tot eerdere benaderingen die vertrouwen op gebatchte Maximum Likelihood Estimation (MLE), wat een mismatch in de tijdindex creëert tussen lokale gewichten en globale schattingen, gebruikt HCW-GLB-OMD een online OMD-schatter. De parameterupdate op tijdstip $t$ wordt gedefinieerd als:
$$\theta_{t+1} \leftarrow \arg \min_{\theta \in \Theta} \left[ \langle \nabla \tilde{\ell}_t(\theta_t), \theta - \theta_t \rangle + \frac{1}{2} \|\theta - \theta_t\|^2_{\nabla^2 \tilde{\ell}_t(\theta_t)} + \frac{1}{2\eta} \|\theta - \theta_t\|^2_{H_t} \right]$$
waarbij $\tilde{\ell}_t$ een gewogen negatieve log-likelihood is. Deze online benadering zorgt ervoor dat de schatter, de arm en de gewichten op hetzelfde lokale tijdstip zijn uitgelijnd, wat een rigoureuze analyse van de impact van corruptie faciliteert.

B. Hessian-gebaseerde Vertrouwensgewichten

Om robuustheid tegen corrupties te bereiken, wijst het algoritme een vertrouwensgewicht $w_t$ toe aan elke observatie op basis van de lokale Hessian (kromming) van de linkfunctie en de dispersieparameter:
$$w_t = \min \left\{ 1, \frac{\alpha g(\tau_t)}{\|x_t\|_{H_t^{-1}}} \right\}$$
Hierbij kwantificeert $\|x_t\|_{H_t^{-1}}$ de onzekerheid in de richting van $x_t$.

• Mechanisme: Als een armrichting zeer onzeker is (grote norm in de inverse Hessian) relatief aan de dispersie, wordt het gewicht $w_t$ verlaagd ($<1$). Dit vermindert de weging van observaties uit richtingen die kwetsbaar zijn voor adversariële manipulatie.
• Kromingsbewustzijn: In tegen tegenstelling tot lineaire banditmethoden die een designmatrix gebruiken, gebruikt deze methode de Hessian $\nabla^2 \tilde{\ell}_t$, die de lokale helling $\dot{\mu}$ incorporeert. Dit stelt het algoritme in staat om zich aan te passen aan de specifieke geometrie van de GLM (bijv. de verzadiging in logistische bandits).

C. Corruptie-robuuste Vertrouwenssequenties

De auteurs construeren een vertrouwensset $C_t(\delta)$ die zowel de schattingsfout als de adversariële corruptie rekening houdt. De straal van deze set bevat een additieve term proportioneel aan het corruptiebudget $C$:
$$C_t(\delta) \equiv \{ \theta \in \Theta : \|\theta - \theta_t\|_{H_t} \le \beta_t(\delta) + 2\eta\alpha C \}$$
Het bewijs van deze sequentie berust op een supermartingaal-argument toegepast op een gewogen likelihood ratio, waarbij gebruik wordt gemaakt van de concave eigenschap van de mapping $x \mapsto x^{w_t}$ om gevallen waar $w_t < 1$ af te handelen.

3. Belangrijkste Bijdragen en Resultaten

A. Regret Upper Bound

Het artikel stelt een regret upper bound vast voor HCW-GLB-OMD onder de aanname dat de linkfunctie $\mu$ zelf-concordant is (Aanname 3). Met een waarschijnlijkheid van ten minste $1-\delta$, is de regret begrensd door:
$$\text{Reg}(T) \lesssim \log d \left( \sqrt{\sum_{t=1}^T g(\tau_t) \dot{\mu}_{t,\star}} + d^2 g_{\max} \kappa + d(g_{\max} + \kappa)C \right)$$
Waarbij:

• $\dot{\mu}_{t,\star} = \dot{\mu}(\langle x_{t,\star}, \theta^\star \rangle)$ is de helling van de linkfunctie bij de optimale arm.
• $g_{\max} = \max_t g(\tau_t)$ is de maximale dispersie.
• $\kappa = (\min_{x,\theta} \dot{\mu}(\langle x, \theta \rangle))^{-1}$ is de krommingsparameter.
• $C$ is het totale corruptiebudget.

Betekenis van de Bound:

• Instance-Wise Optimaliteit: De leidende term $\sqrt{\sum g(\tau_t) \dot{\mu}_{t,\star}}$ hangt af van de werkelijke helling bij de optimale arm, in plaats van de worst-case kromming $\kappa$. Dit komt overeen met de minimax lower bound voor corruptievrije GLBs.
• Corruptie-robuustheid: De corruptieterm schaalt lineair met $C$ (specifiek $d(g_{\max} + \kappa)C$), wat minimax optimaal is tot een krommingsfactor $\kappa$.
• Unificatie: De bound herstelt simultaan de state-of-the-art resultaten voor heteroskedastische lineaire bandits, logistische bandits en Poisson bandits.

B. Unified Regret Lower Bound

De auteurs bewijzen een unificerende lower bound voor elke zelf-concordante heteroskedastische GLB met adversariële corrupties:
$$\Omega \left( d \sqrt{\sum_{t=1}^T g(\tau_t) \dot{\mu}_{t,\star}} + dC \right)$$
Deze lower bound:

• Omvat bestaande probleem-specifieke lower bounds voor logistische bandits, heteroskedastische lineaire bandits en gecorrumpeerde lineaire bandits.
• Bevestigt dat de leidende term van het algoritme instance-wise minimax optimaal is.
• Demonstreert dat de corruptieterm $dC$ onvermijdelijk is, hoewel de upper bound momenteel een extra $\kappa$-factor bevat in de corruptieterm ($d\kappa C$).

C. Computationele Efficiëntie

Een cruciale bijdrage is de efficiëntie van het algoritme. Door een online OMD-update en recursieve Hessian-updates te gebruiken, bereikt HCW-GLB-OMD een $O(1)$ ruimte- en tijdcomplexiteit per iteratie. Dit staat in contrast met eerdere corruptie-robuuste algoritmen voor GLMs (bijv. CR-Eluder-UCB, GAdaOFUL) die vaak een $O(t)$ complexiteit vereisen vanwege batch-verwerking of complexe vertrouwensset-constructies.

4. Betekenis en Claims

Het artikel claimt het eerste gezamenlijk efficiënte en optimale algoritme te bieden voor heteroskedastische GLBs onder adversariële corrupties. De primaire betekenis ligt in:

1. Het overbruggen van de kloof: Het lost de trade-off op tussen computationele efficiëntie en statistische optimaliteit in gecorrumpeerde GLBs. Eerdere werken bereikten ofwel optimaliteit met hoge computationele kosten, ofwel efficiëntie met suboptimale regret bounds (vaak schalend met de worst-case kromming $\kappa$).
2. Instance-Wise Optimaliteit: Het algoritme bereikt regret bounds die zich aanpassen aan de specifieke moeilijkheidsgraad van de instantie (via $\dot{\mu}_{t,\star}$) in plaats van te vertrouwen op worst-case aannames, zelfs in aanwezigheid van corrupties.
3. Verenigd Raamwerk: Het biedt een enkel theoretisch raamwerk dat een breed spectrum aan bandit-problemen dekt (lineair, logistisch, Poisson, heteroskedastisch) zonder dat er probleem-specifieke algoritmische modificaties nodig zijn.

De auteurs merken op dat er een resterende kloof is: de corruptieterm in de upper bound schaalt met $d\kappa C$, terwijl de lower bound $dC$ is. Zij vermoeden dat de $\kappa$-factor in de corruptieterm een artefact is van de analyse en dat een $O(dC)$ bound haalbaar is, maar dit blijft een openstaand probleem. Daarnaast gaat de huidige analyse ervan uit dat de dispersieparameter $\tau_t$ bekend is bij de leerder; het afhandelen van een onbekende $\tau_t$ wordt geïdentificeerd als een toekomstige richting.