Prior Diffusiveness and Regret in the Linear-Gaussian Bandit

Probleemstelling
Het artikel behandelt het linear-Gaussische banditprobleem, een sequentieel besluitvormingssetting waarbij een speler acties $A_t \in \mathcal{A} \subset \mathbb{R}^d$ selecteert om cumulatieve beloningen te maximaliseren. De beloning op tijdstip $t$ wordt gegenereerd door $R_{t+1} = \theta_\star^\top A_t + W_{t+1}$, waarbij $\theta_\star$ een onbekende parametervector is en $W_{t+1}$ i.i.d. Gaussische ruis is met variantie $\sigma^2$. Het doel is om de Bayesiaanse regret te minimaliseren, gedefinieerd als het verwachte verschil tussen de beloning van de optimale actie en de gekozen actie over een horizon $T$, uitgaande van een priorverdeling $\rho$ op $\theta_\star$. Specifiek richten de auteurs zich op het geval waarbij $\theta_\star \sim \mathcal{N}(\mu_0, \Sigma_0)$ en de actieset een geschaalde $\ell_2$-bal is met straal $r$.

Methodologie
De auteurs analyseren Thompson sampling, een posterior sampling-algoritme dat een parameterinschatting $\hat{\theta}_t$ trekt uit de posteriorverdeling gegeven de historie $H_t$ en de actie selecteert die de verwachte beloning onder $\hat{\theta}_t$ maximaliseert.

Om de regret-bounds af te leiden, maken de auteurs gebruik van een decompositie van de instantane regret in twee termen:

1. Term (I): De regret die wordt geleden wanneer de gesamplede parameter $\hat{\theta}_t$ dicht bij de ware parameter $\theta_\star$ ligt (binnen een met hoge waarschijnlijkheid optredende gebeurtenis gedefinieerd door de posterior precisie-matrix).
2. Term (II): De regret die wordt geleden wanneer de gesamplede parameter ver van de ware parameter verwijderd is.

De kern van de technische innovatie ligt in de analyse van Term (I). De auteurs introduceren een gegeneraliseerde elliptische potentielemma (Lemma 3). In tegenstelling tot standaard elliptische potentielemma's die gebruikt worden in de literatuur over lineaire bandits (bijv. Abeille & Lazaric, 2017; Dani et al., 2008), die doorgaans vereisen dat de initiële precisie-matrix niet nul is (bijv. $V_0 \succeq I$) en kwadratische fouten begrenzen, stelt dit nieuwe lemma het volgende mogelijk:

• Het staat toe dat de initiële precisie-matrix $V_0$ willekeurig klein is (of zelfs nul in het limiet), wat diffuse priors accommodeert.
• Het introduceert een flexibele exponent $p \in [0, 1]$ in de sommatie van normen.
• Het scheidt expliciet de grens in een logaritmische determinantterm (die de informatiewinst op de lange termijn vastlegt) en een trace-term met betrekking tot de initiële precisie-matrix (die de initiële "burn-in" kosten vastlegt).

De analyse van Term (II) berust op standaard concentratie-ongelijkheden voor Gaussische verdelingen om de waarschijnlijkheid van grote afwijkingen tussen $\hat{\theta}_t$ en $\theta_\star$ te begrenzen.

Belangrijkste Bijdragen en Resultaten
De primaire bijdrage is een nieuwe Bayesiaanse regret-bound voor Thompson sampling in de linear-Gaussische setting die de prior-afhankelijke "burn-in" term ontkoppelt van de minimax regret-rate.

1. Verbeterde Regret Bound: De auteurs bewijzen dat Thompson sampling een regret bereikt van:
   $$\text{Reg}(T) = \tilde{O}\left( \sigma d \sqrt{T} + d r \sqrt{\text{Tr}(\Sigma_0)} \right)$$
   Hierbij vertegenwoordigt $\sigma d \sqrt{T}$ de asymptotische minimax-rate, terwijl $d r \sqrt{\text{Tr}(\Sigma_0)}$ de initiële kosten vertegenwoordigt voor het reduceren van de onzekerheid van de schaal van de prior naar de schaal van de ruis.

2. Ontkoppeling van Termen: Eerdere bounds (bijv. Kalkanli & Özgür, 2020) vertoonden een multiplicatieve afhankelijkheid, zoals $\tilde{O}(d \sqrt{T(\sigma^2 + r^2 \text{Tr}(\Sigma_0))})$, waarbij de diffusiviteit van de prior $\sqrt{\text{Tr}(\Sigma_0)}$ de gehele minimax-rate schaalde. Het nieuwe resultaat laat zien dat, tot aan de logaritmische factoren, de diffusiviteit van de prior slechts een additieve constante toevoegt aan de regret, onafhankelijk van de tijdshorizon $T$.

3. Lower Bounds: Het artikel stelt een ondergrens vast voor elke policy in deze setting, waarmee wordt aangetoond dat de burn-in term $d r \sqrt{\text{Tr}(\Sigma_0)}$ onvermijdelijk is voor Gaussische priors. Dit bevestigt dat de additieve structuur van de bovengrens nauwkeurig is (tot aan logaritmische factoren) en dat de diffusiviteit van de prior niet volledig uit de regret geëlimineerd kan worden.

4. Generalisatie: De auteurs merken op dat hun resultaten kunnen worden uitgebreid naar sterk log-concaaf priors en ruisverdelingen, niet strikt beperkt tot het Gaussische geval.

Betekenis
Het artikel beweert dat zijn resultaten een onnauwkeurigheid in bestaande regret-bounds voor Thompson sampling oplossen. Door te bewijzen dat de prior-afhankelijke term additief is in plaats van multiplicatief, verheldert het werk de rol van de diffusiviteit van de prior: het fungeert als een eenmalige "burn-in" kostenpost die nodig is om de onzekerheid te reduceren tot het niveau van de observatieruis, waarna de prestaties van het algoritme uitsluitend worden bepaald door de variantie van de ruis $\sigma$ en de dimensie $d$. Dit biedt een preciezere karakterisering van de efficiëntie van het algoritme, met name in regimes waar de prior zeer diffuus is (grote $\text{Tr}(\Sigma_0)$), door aan te tonen dat dergelijke diffusiviteit de asymptotische convergentierate niet permanent verslechtert. De introductie van het gegeneraliseerde elliptische potentielemma wordt gepresenteerd als een instrument dat een flexibelere analyse mogelijk maakt van stochastische optimalisatieproblemen waarbij de initiële onzekerheid onbegrensd kan zijn.