An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction

Technische Samenvatting: Een Verbeterd Algoritme voor Adversariële Lineaire Contextuele Bandieten via Reductie

Probleemdefinitie

Het artikel behandelt het adversariële lineaire contextuele bandiet-probleem. In deze setting kiest een onwetende (oblivious) tegenstander een sequentie van verborgen verliesvectoren $\theta_t \in \mathbb{R}^d$ voordat de interactie begint. In elke ronde $t$ wordt een actieset $A_t \subset \mathbb{R}^d$ i.i.d. getrokken uit een vaste maar onbekende distributie $\mathcal{D}$ en onthuld aan de leerder. De leerder moet een actie $a_t \in A_t$ selecteren en incasseert een verlies $\ell_t$ met verwachting $\mathbb{E}[\ell_t] = a_t^\top \theta_t$. Het doel is om de regret te minimaliseren ten opzichte van het beste vaste beleid $\pi$, waarbij een beleid elke geobserveerde actieset $A$ naar een punt in de convexe huls $\text{conv}(A)$ mapt.

Deze setting generaliseert klassieke lineaire bandieten door toe te staan dat de actiesets (contexten) stochastisch over de tijd variëren, terwijl de verliezen adversarieel blijven. Een cruciale uitdaging is dat de distributie $\mathcal{D}$ onbekend is, en de leerder heeft geen toegang tot een simulator die gratis monsters uit $\mathcal{D}$ kan genereren. Bovendien kan het aantal mogelijke acties $K$ exponentieel groot zijn in de dimensie $d$ (bijv. in combinatorische problemen zoals kortste paden), waardoor algoritmen met een complexiteit die polynomiaal is in $K$ onhaalbaar zijn.

Methodologie

De kernbijdrage is een computationeel efficiënte reductie die het probleem van de adversariële lineaire contextuele bandiet transformeert naar een misspecificatie-robuust adversarieel lineair bandiet-probleem met een vaste actieset.

1. Reductie naar vaste actiesets:
   De auteurs definiëren een mapping $\Psi(\pi) = \mathbb{E}_{A \sim \mathcal{D}}[\pi(A)]$, die een beleid $\pi$ mapt naar zijn gemiddelde actie. Omdat $\mathcal{D}$ onbekend is, kan de ware verzameling van gemiddelde acties $\Omega = \{\Psi(\pi) \mid \pi \in \Pi\}$ niet direct worden geraadpleegd. In plaats daarvan construeert het algoritme een empirische benadering $\hat{\Omega}$ met behulp van $N$ i.i.d. monsters van actiesets getrokken uit $\mathcal{D}$.

   • $\hat{\Omega}$ wordt gedefinieerd als de Minkowski-som van de convexe hullen van de gesamplede actiesets: $\hat{\Omega} = \frac{1}{N} \sum_{i=1}^N \text{conv}(A_i)$.
   • De reductie berust op het feit dat voor lineaire classificatiebeleid het verschil tussen het verwachte verlies op de ware distributie en de empirische distributie klein is (uniforme convergentie), mits $N$ voldoende groot is.

2. Omgaan met discrepantie via misspecificatie-robuustheid:
   Omdat de leerder opereert op $\hat{\Omega}$ in plaats van $\Omega$, is de feedback die door het onderliggende lineaire bandiet-algoritme wordt ontvangen "misspecificeerd". Specifiek verschilt het geobserveerde verwachte verlies door het lineaire bandiet-algoritme van het ware verwachte verlies met een begrensde foutterm $\epsilon$.

   • De auteurs maken gebruik van een $\alpha$-misspecificatie-robuust adversarieel lineair bandiet-algoritme als black box. Dit algoritme garandeert een lage regret, zelfs wanneer de feedback voldoet aan $|\mathbb{E}[c_t] - \langle y_t, \theta_t \rangle| \le \epsilon$.
   • Om een punt $y_t \in \hat{\Omega}$ uit te voeren die door het lineaire bandiet-algoritme wordt gesuggereerd, gebruikt de leerder een Frank-Wolfe-gebaseerde decompositie (Algoritme 2) om $y_t$ uit te drukken als een convexe combinatie van punten op de rand van $\hat{\Omega}$. Deze randpunten komen overeen met lineaire classificatiebeleid $\pi_\phi$, die uitgevoerd kunnen worden met een lineaire optimalisatie-orakel voor de individuele actiesets $A_t$.

3. Algoritmische componenten:

   • Algoritme 1: Het hoofdframework dat interageert met de omgeving, de suggestie van het lineaire bandiet deelt in een mengeling van lineaire beleid, en de resulterende loss terugvoert naar het lineaire bandiet-algoritme.
   • Algoritme 3 (Misspecificatie-Robuuste Continue Exponential Weights): Een specifieke instantiatie van het robuuste lineaire bandiet-algoritme. Het past de afgeknipte (clipped) continue exponential weights methode (Ito et al., 2020) aan door een "bonusterm" $b_t$ aan de loss-estimator toe te voegen. Deze bonus stimuleert exploratie en compenseert de regret-overhead veroorzaakt door misspecificatie.
   • Doubling Trick: Om de onbekende optimale steekproefomvang $N$ af te handelen, gebruikt het algoritme een doubling trick, waarbij het proces bij rondes $2, 4, 8, \dots$ wordt herstart en alle geaccumuleerde context-monsters gebruikt om $\hat{\Omega}$ te verfijnen.

Belangrijkste Bijdragen

• Orakel-efficiënt Algoritme: Het artikel presenteert het eerste algoritme voor adversariële lineaire contextuele bandieten met stochastische actiesets dat regret-bounds bereikt die onafhankelijk zijn van het aantal acties $K$ in zijn computationele complexiteit. Het vereist enkel een lineair optimalisatie-orakel voor de individuele actiesets in elke ronde.
• Combinatorische Toepasbaarheid: De methode is de eerste die $\text{poly}(d)\sqrt{T}$ regret in polynomiale tijd bereikt voor combinatorische bandieten met stochastische actiesets en adversariële verliezen. Eerdere algoritmen vereisten ofwel semi-bandit feedback, ofwel hadden een computationele complexiteit die polynomiaal schaalt met $K$ (wat exponentieel is in $d$ voor veel problemen).
• Nieuwe Reductie: Het werk vestigt een polynomiale-tijd reductie van adversariële lineaire contextuele bandieten naar misspecificatie-robuuste lineaire bandieten. In tegenstelling tot eerdere reducties (bijv. Hanna et al., 2023) die zich richtten op stochastische settings of geen polynomiale-tijd implementaties hadden, opereert deze reductie onder adversariële verliezen en is deze computationeel efficiënt.

Resultaten

Het algoritme bereikt de volgende regret-bounds (logaritmische factoren genegeerd):

• Zonder Simulator: $\tilde{O}(\min\{d^2\sqrt{T}, \sqrt{d^3 T \log K}\})$.
  • Dit lost een openstaande vraag van Liu et al. (2023) op over de vraag of $\text{poly}(d)\sqrt{T}$ regret in polynomiale tijd haalbaar is zonder afhankelijk te zijn van $K$.
  • De computationele complexiteit is $\text{poly}(d, T)$ plus $\text{poly}(d, T)$ oproepen aan het lineaire optimalisatie-orakel.
• Met Simulator: Indien de leerder toegang heeft tot een simulator die gratis contexten kan genereren, verbetert de regret-bound naar $\tilde{O}(d\sqrt{L^*})$, waarbij $L^*$ het cumulatieve verlies is van het beste beleid. Dit is een first-order bound die zich aanpast aan de moeilijkheidsgraad van de probleeminstantie.

Betekenis en Claims

De auteurs stellen dat dit werk een algemeen framework biedt dat de toepasbaarheid van adversariële lineaire contextuele bandieten aanzienlijk vergroot voor problemen met exponentieel grote actieruimtes (bijv. kortste pad, flow, bipartite matching) zonder kennis van de contextdistributie of een simulator te vereisen.

Het artikel merkt expliciet op dat hoewel de bound $\tilde{O}(d^2\sqrt{T})$ een verbetering is ten opzichte van eerdere polynomiale-tijd resultaten die afhankelijk zijn van $K$, het nog steeds een open vraag is of de bijna-optimale $\tilde{O}(d\sqrt{T})$ bound zonder simulator in polynomiale tijd bereikt kan worden. De auteurs benadrukken ook dat hun aanpak de onrealistische aanname van log-concaaf context-distributies verwijdert die nodig is door sommige eerdere werken (Olkhovskaya et al., 2023) wanneer deze naar specifieke formuleringen worden gespecialiseerd. Ten slotte suggereren zij dat het reductie-framework ook toepasbaar kan zijn op andere settings, zoals lineaire MDP's met vaste transities en adversariële verliezen.