Stochastic Linear Bandits with Parameter Noise

Technische Samenvatting: Stochastische Lineaire Bandieten met Parameterruis

Probleemdefinitie
Dit werk onderzoekt het model van stochastische lineaire bandieten met parameterruis. In deze setting interacteert een leerder met een omgeving over een tijds horizon $T$ door acties $a_t$ te selecteren uit een actieverzameling $\mathcal{A} \subseteq \mathbb{R}^d$. In tegenstelling tot het standaard model met additieve ruis, waarbij de beloning $X_t = a_t^\top \theta^\star + \eta_t$ is (met een vaste $\theta^\star$ en ruis $\eta_t$), veronderstelt het model met parameterruis dat de beloning wordt gegeven door $X_t = a_t^\top \theta_t$, waarbij $\theta_t$ i.i.d. wordt bemonsterd uit een vaste, onbekende verdeling $\nu$ met gemiddelde $\theta^\star$ en covariantiematrix $\Sigma$.

Het artikel benadrukt een fundamenteel onderscheid: in het model met parameterruis kan de leerder de variantie van de beloning beïnvloeden. Specifiek geldt $\text{Var}(X_t) = a_t^\top \Sigma a_t$, terwijl in het model met additieve ruis de variantie uitsluitend door de omgeving wordt bepaald. De auteurs merken op dat het model met parameterruis een verzwakking is van het model van adversariele lineaire bandieten (waarbij $\theta_t$ door een tegenstander wordt gekozen), maar dat het unieke structurele eigenschappen bezit die in bepaalde geometrische settings mogelijk strakkere regret-grenzen toelaten dan het model met additieve ruis.

Methodologie en Algoritmen
De auteurs stellen twee algoritmen voor die zijn toegespitst op verschillende geometrieën van de actieverzameling:

1. VASE (Variance Aware Optimal Design Successive Elimination):

   • Doel: Algemene eindige actieverzamelingen (en oneindige verzamelingen via overdekkingsargumenten).
   • Methode: Een opeenvolgende eliminatie-algoritme dat gebruikmaakt van variantie-informatie. In elke fase berekent het een G-optimale ontwerp $\pi_\ell$ om acties te selecteren. Het schat expliciet de variantie van acties in de drager van het ontwerp met behulp van een stopregel-algoritme (SR).
   • Kerninnovatie: Het algoritme gebruikt geschatte varianties op twee manieren: om het aantal benodigde steekproeven voor exploratie te verminderen en als gewichten in een gewogen kleinste-kwadraten-schatter. Deze weging zorgt ervoor dat de covariantie van de schatter gecontroleerd blijft, zelfs met minder steekproeven, wat leidt tot regret-grenzen die afhankelijk zijn van de variantie.

2. VALEE (Variance Aware Linear Explore-Exploit):

   • Doel: $\ell_p$-eenheidsballen waar $p \in (1, 2]$ (en hun duale normen $q \ge 2$).
   • Methode: Een eenvoudig explore-exploit-algoritme.
     • Exploratie: Het algoritme speelt standaardbasisvectoren $e_i$. Het schat de gemiddelde vector $\theta^\star$ coördinaatgewijs met behulp van de Median-of-Means (MoM)-techniek. Als de covariantiematrix $\Sigma$ onbekend is, schat het eerst de varianties van de basisvectoren.
     • Exploitatie: Zodra de schattingsfout voldoende klein is ten opzichte van de variantie en de tijds horizon, kiest het algoritme een actie $\hat{a}$ die is afgeleid van de geschatte gemiddelde $\hat{\theta}$, specifiek $\hat{a}_i = \text{sign}(\hat{\theta}_i)|\hat{\theta}_i|^{q-1} / \|\hat{\theta}\|_q^{q-1}$.
   • Kerninnovatie: De analyse maakt gebruik van de geometrie van de $\ell_p$-bal en de structuur van de parameterruis. De auteurs tonen aan dat het exploreren van basisvectoren een schattingsfout oplevert die evenredig is met $\sqrt{\sigma^2(e_i)}$, wat strakker is dan de standaard $\epsilon$-grens in modellen met additieve ruis. Dit stelt het algoritme in staat optimale regret-grenzen te bereiken die afhankelijk zijn van de variantiestructuur van de beloningsverdeling.

Belangrijkste Resultaten
Het artikel stelt zowel bovengrenzen als ondergrenzen vast en toont aan dat de voorgestelde algoritmen minimax optimaal zijn (tot op logaritmische factoren) voor specifieke settings.

• Algemene Eindige Actieverzamelingen ($K$ acties):

  • Bovengrens: VASE bereikt een regret van $\tilde{O}(d^2 + \sqrt{dT \log(K/\delta) M_\sigma})$, waarbij $M_\sigma$ een variantie-afhankelijke grootheid is die begrensd is door $\max_a \sigma^2(a)$.
  • Ondergrens: Een ondergrens van $\tilde{\Omega}(d\sqrt{T \sigma^2_{\max}})$ wordt bewezen, wat aantoont dat de bovengrens strak is tot op logaritmische factoren wanneer $\log(K) \approx d$.

• $\ell_p$-Eenheidsballen ($p \le 2$):

  • Bekende Covariantie: VALEE bereikt een regret van $\tilde{O}(d + \sqrt{dT \sigma^2_q})$, waarbij $\sigma^2_q = (\sum \Sigma_{ii}^{q/2})^{2/q}$. Dit wordt bewezen optimaal via een overeenkomende ondergrens van $\tilde{\Omega}(\sqrt{dT \sigma^2_q})$.
  • Onbekende Covariantie: VALEE lijdt een extra additieve term, wat resulteert in een regret van $\tilde{O}(\sqrt{dT \sigma^2_q} + d^{2/3 + 2/3q} T^{1/3})$. De auteurs merken op dat deze additieve term voortkomt uit de fase van variantieschatting.

• $\ell_p$-Eenheidsballen ($p > 2$):

  • Het artikel biedt een ondergrens van $\tilde{\Omega}(d\sqrt{T \sigma^2_{\max}})$, die overeenkomt met de bekende ondergrenzen voor het adversariele setting in deze geometrieën.

Betekenis en Claims
Het artikel claimt een "curieus geval" op te lossen met betrekking tot lineaire bandieten, waarbij het model met additieve ruis vaak slechtere regret-grenzen ($d\sqrt{T}$) oplevert dan het adversariele model ($\sqrt{dT}$) voor specifieke actieverzamelingen zoals de $\ell_2$-eenheidsbal. De auteurs tonen aan dat het model met parameterruis beter aansluit bij de intuïtie dat stochastische modellen makkelijker zouden moeten zijn dan adversariele modellen.

• Strakkere Grenzen: Voor $\ell_p$-ballen met $p \le 2$ staat het model met parameterruis regret-grenzen toe van de orde $\sqrt{dT \sigma^2_q}$, wat aanzienlijk kleiner kan zijn dan de voor additieve ruismodellen typische $d\sqrt{T}$-grens wanneer de variantie klein is.
• Structureel Voordeel: De resultaten benadrukken dat de lineariteit van de realisatie (niet alleen de verwachting) en het vermogen van de leerder om de variantie te beïnvloeden cruciaal zijn voor het bereiken van deze verbeterde grenzen.
• Eenvoud: Verrassend genoeg is de optimale regret voor $\ell_p$-ballen ($p \le 2$) haalbaar met een zeer eenvoudig explore-exploit-algoritme (VALEE), in tegenstelling tot de complexe optimale ontwerp-algoritmen die vaak vereist zijn in settings met additieve ruis.

De auteurs concluderen dat hoewel hun resultaten voor $p \le 2$ optimaal zijn (tot op logaritmen) wanneer de covariantie bekend is, het geval met onbekende covariantie een open gat laat (de $T^{1/3}$-term) dat toekomstig werk kan adresseren. Zij laten ook het ontwerp van een algoritme dat de ondergrens voor $p > 2$ benadert, als een open vraag.