Offline-to-Online Learning in Linear Bandits

Technische Samenvatting: Offline-to-Online Learning in Lineaire Bandieten

Probleemstelling
Dit artikel behandelt het probleem van offline-to-online learning binnen de context van de stochastische lineaire bandit. In dit scenario selecteert een leerling sequentieel acties uit een verzameling $\mathcal{A} \subset \mathbb{R}^d$ om de cumulatieve beloningen over een horizon $n$ te maximaliseren, terwijl er toegang is tot een vooraf bestaande offline dataset $\mathcal{D}$. De offline data wordt verzameld via een vast, niet-adaptief ontwerp (deterministische actie-aantallen) en volgt een lineair beloningsmodel met subgaussische ruis.

De kernuitdaging ligt in de afweging tussen twee concurrerende doelstellingen:

1. Online Regret ($R_n$): Het minimaliseren van regret ten opzijde van de optimale actie $\mu^*$. Standaard online algoritmen (bijv. LinUCB) vertrouwen op optimisme om te exploreren, bereiken sublineaire regret, maar kunnen mogelijk hoge initiële regret ervaren als de offline data wordt genegeerd.
2. Offline Regret ($R_n^{off}$): Het minimaliseren van regret ten opzijde van de gemiddelde beloning van de offline dataset ($\mu_{off}$). Standaard offline algoritmen (bijv. LinLCB) vertrouwen op pessimisme om de bekende data te exploiteren, wat zorgt voor prestaties die dicht bij $\mu_{off}$ liggen, maar faalt in exploratie, wat leidt tot lineaire regret als de offline data suboptimal is of als de horizon lang is.

Bestaand werk heeft deze regimes grotendeels apart behandeld of gefocust op multi-armed bandits (MAB), waarbij de regret schaalt met het aantal acties. Dit artikel probeert de kloof te overbruggen in gestructureerde (lineaire) omgevingen, waar de regret zou moeten schalen met de dimensie $d$ in plaats van de grootte van de actieruimte.

Methodologie: Het LinOtO Algoritme
De auteurs stellen LinOtO (Linear Offline-to-Online) voor, een algoritme dat dynamisch de balans tussen exploratie en exploitatie beheert door een exploratiebudget te beheren. Het algoritme werkt door te schakelen tussen twee strategieën op basis van een betrouwbaarheidsset $C_t$ die is geconstrueerd uit zowel offline als online data:

1. Betrouwbaarheidssets: Het algoritme onderhoudt een kleinste-kwadraten-schatter $\hat{\theta}_t$ en een betrouwbaarheidselipsoïde $C_t$ rond de ware parameter $\theta^*$. De straal van deze set incorporeert onzekerheid van zowel de offline data ($\beta_{off}$) als de online interacties ($\beta_t$).
2. Optimistische vs. Pessimistische Acties:
   • UCB Actie ($U_t$): De actie die de Upper Confidence Bound binnen $C_t$ maximaliseert. Dit bevordert exploratie en vermindert $R_n$, maar brengt het risico met zich mee dat $R_n^{off}$ toeneemt.
   • LCB Actie ($L_t$): De actie die de Lower Confidence Bound maximaliseert (specifiek het maximum van de minimale betrouwbaarheidsgrenzen over de tijd). Dit bevordert de exploitatie van de offline data, wat $R_n^{off}$ vermindert, maar potentieel $R_n$ verhoogt.
3. Budgetmechanisme:
   • Het algoritme definieert een veilige baseline-beloning $r_b$, afgeleid van een ondergrens op de beloning van een specifieke "veilige" actie $L_{off}$ (de LCB-actie berekend uitsluitend op basis van offline data). Proposition 2 garandeert dat $L_{off}$ met hoge waarschijnlijkheid dicht bij $\mu_{off}$ ligt.
   • Een exploratiebudget $B(t)$ wordt bijgehouden, wat de cumulatieve excessieve beloning van het algoritme boven de baseline $r_b$ vertegenwoordigt.
   • Beslissingsregel: Als $B(t) > 0$, selecteert het algoritme de optimistische actie $U_t$ (exploratie). Als $B(t) \le 0$, selecteert het de pessimistische actie $L_t$ (exploitatie) om budget te accumuleren.
   • Dit mechanisme zorgt ervoor dat het algoritme alleen exploreert wanneer het het recht heeft "verdiend" door veilig te blijven ten opzichte van de offline baseline.

Belangrijkste Bijdragen

1. Algoritme Ontwerp: Het artikel presenteert LinOtO, het eerste algoritme dat specifiek is ontworpen voor de offline-to-online lineaire bandit setting die tegelijkertijd UCB en LCB strategieën balanceert via een budget-gebaseerd schakelmechanisme.
2. Theoretische Garanties: De auteurs stellen hoge-waarschijnlijkheid regret-bounds vast voor beide metrieken:
   • Online Regret ($R_n$): Theorem 1 toont aan dat LinOtO sublineaire regret bereikt ten opzichte van de optimale actie. De bound bestaat uit een term die afhankelijk is van de horizon $n$ (vergelijkbaar met LinUCB) en een additieve constante die afhankelijk is van de kwaliteit van de offline data. Als de offline data de ruimte goed dekt, verbetert de bound.
   • Offline Regret ($R_n^{off}$): Theorem 2 demonstreert dat de regret ten opzichte van de offline referentie lineair met $n$ schaalt, maar afneemt als $O(1/\sqrt{m})$ met het aantal offline samples $m$. Dit komt overeen met de prestaties van een puur offline (pessimistische) oplossing.
3. Pareto Tradeoff Analyse: De analyse onthult een instelbare tradeoff die wordt gecontroleerd door een parameter $\alpha$. Het verhogen van $\alpha$ bevoordeelt de online prestaties (dichter bij LinUCB), terwijl het verlagen van $\alpha$ de offline prestaties bevoordeelt (dichter bij LinLCB).

Experimentele Resultaten
Empirische evaluaties op synthetische lineaire bandit-taken (dimensie $d=20$, $|A|=100$) laten het volgende zien:

• Horizon Gevoeligheid: Voor korte horizonten volgt LinOtO de conservatieve LinLCB baseline. Voor lange horizonten gaat het over naar exploratie en bereikt het sublineaire regret vergelijkbaar met LinUCB.
• Kwaliteit van de Offline Data:
  • Wanneer de offline dataset de optimale actie uitsluit, wijkt LinOtO succesvol af van de suboptimale offline prior om te exploreren, en presteert uiteindelijk beter dan LinLCB (dat lineaire regret lijdt) en nadert het de LinUCB-prestaties naarmate de offline datagrootte $m$ toeneemt.
  • Wanneer de offline dataset de optimale actie bevat, convergeert LinOtO snel en presteert het vergelijkbaar met LinUCB en LinLCB.
• Robuustheid: Het algoritme presteert consistent tussen de extremen van pure exploratie (LinUCB) en pure exploitatie (LinLCB), en past zich aan de parameters van het probleem aan.

Betekenis en Claims
Het artikel claimt dat LinOtO effectief de "slecht begrepen" offline-to-online tradeoff in gestructureerde omgevingen oplost. In tegen tegenstelling tot eerder werk in MAB-settings (bijv. Sentenac et al., 2025), maakt deze aanpak gebruik van de lineaire structuur om te zorgen dat de regret schaalt met dimensie $d$ in plaats van het aantal acties, wat het schaalbaar maakt voor hoog-dimensionale problemen.

De auteurs merken bescheiden op dat hun framework momenteel fixed-design offline data veronderstelt en geen rekening houdt met distributieverschuivingen tussen offline en online data of adaptieve logging-policies. Zij identificeren het aanpakken van deze beperkingen, samen met het uitbreiden van het framework naar niet-lineaire settings, als belangrijke richtingen voor toekomstig onderzoek. Het werk draagt bij aan de bredere literatuur over het benutten van voorkennis (hints, offline data) om exploratie-exploitatie tradeoffs in online learning te sturen.