Lookahead identification in adversarial bandits: accuracy and memory bounds

Deze paper introduceert lookahead-identificatie in adversariele banditproblemen, waarbij wordt aangetoond dat het mogelijk is om met beperkte geheugeneisen een arm te selecteren die in een toekomstig tijdsvenster bijna optimaal presteert, ondanks het gebrek aan informatie over de toekomst.

De kern

Stel je voor dat je een gokker bent in een casino met duizenden gokkasten (de "arms" of armen). Je hebt een tijdslimiet: je mag maar een beperkt aantal keer spelen voordat je moet stoppen.

In de wereld van de kunstmatige intelligentie (AI) zijn er twee hoofdtaken die zo'n gokker kan doen:

1. Verlies minimaliseren (Regret Minimization): Probeer gedurende het hele spel zo veel mogelijk geld te winnen, door slim te wisselen tussen de kasten.
2. De beste kast vinden (Best-Arm Identification): Stop het spel op een bepaald moment en zeg: "Ik wed dat deze ene kast in de toekomst het meeste geld gaat uitkeren."

Dit paper, geschreven door Nataly Brukhim en collega's, kijkt naar een heel lastige versie van deze situatie: het "vijandige" casino.

Het Probleem: Een bedrieger in het casino

In een normaal casino werken de kasten eerlijk: als een kast vaak uitkeert, zal hij dat waarschijnlijk ook in de toekomst doen. Maar in een vijandig casino (adversarial setting) is er een bedrieger die de uitkomsten manipuleert.

• Vandaag geeft Kast A veel geld.
• Morgen geeft Kast B veel geld.
• Overmorgen geeft Kast C veel geld.

De bedrieger kijkt naar wat jij doet en past zich aan. In zo'n wereld is het bijna onmogelijk om te zeggen: "Kast A was gisteren de beste, dus hij is morgen ook de beste." De geschiedenis zegt je niets over de toekomst.

De Oplossing: "Kijk vooruit" (Lookahead)

De auteurs vragen zich af: Is het überhaupt mogelijk om iets zinnigs te zeggen over de toekomst in zo'n chaotisch casino?

Ze introduceren een nieuw idee: Lookahead Identification.
In plaats van te proberen de beste kast nu te vinden, mag je zeggen: "Ik kies een toekomstig tijdvenster (bijvoorbeeld de volgende 100 beurten) en ik wed dat deze kast in dat specifieke venster het beste zal presteren."

Het is alsof je zegt: "Ik weet niet wat er morgen gebeurt, maar ik wed dat Kast X de komende maand de beste is."

De Resultaten in Gewone Taal

1. Het is mogelijk, maar niet perfect

Het paper toont aan dat je wel een goede gok kunt doen, zelfs tegen een slimme bedrieger. Je kunt een kast kiezen die binnen een klein beetje (epsilon) van de beste kast ligt.

• De analogie: Het is alsof je in een stormachtige zee probeert te raden welke golf de hoogste zal zijn. Je kunt niet 100% zeker zijn, maar je kunt wel een redelijke gok doen die beter is dan willekeurig kiezen.

2. Het geheugenprobleem (De "Notitieblok"-test)

Hier wordt het interessant. Om deze gok te doen, moet je informatie onthouden.

• De harde waarheid: In het ergste geval heb je een groot notitieblok nodig. Je moet de prestaties van alle kasten onthouden om een goede voorspelling te doen. Als je 1000 kasten hebt, moet je ongeveer 1000 stukjes informatie bijhouden. Dit kost veel "geheugen" (memory).
• De verrassing: Als je echter een beetje geluk hebt (of als de situatie "spaarzaam" is, wat betekent dat maar een paar kasten echt goed zijn en de rest waardeloos is), dan heb je slechts een klein post-itje nodig. Je kunt dan met heel weinig geheugen toch een goede gok doen.

3. Het grote verschil: Winnen vs. Voorspellen

Dit is misschien wel het coolste deel van het paper. Ze vergelijken het met twee verschillende doelen:

• Doel A: De beste kast vinden voor de toekomst (Lookahead). Dit is heel zwaar. Je hebt veel geheugen nodig (zoals een groot notitieblok) om dit goed te doen.
• Doel B: Zoveel mogelijk geld winnen tijdens het spel (Regret Minimization). Dit is verrassend makkelijk! Je kunt hier een slimme strategie voor bedenken die werkt met heel weinig geheugen (een post-itje), zelfs in een vijandig casino.

De metafoor:
Stel je voor dat je een voorspeller bent en een speler.

• De voorspeller die wil zeggen "Welke kast wint de komende week?" moet alles onthouden. Hij heeft een zware rugzak vol notities nodig.
• De speler die gewoon wil winnen terwijl hij speelt, kan heel slim zijn met een heel klein notitieblok. Hij hoeft niet alles te onthouden, hij hoeft alleen maar slim te reageren op wat er nu gebeurt.

Waarom is dit belangrijk?

Vroeger dachten wetenschappers dat als je in een vijandige omgeving werkt, je ofwel heel veel geheugen nodig hebt, ofwel dat je niets zinnigs kunt zeggen.

Dit paper laat zien dat:

1. Je wel iets zinnigs kunt zeggen over de toekomst, zelfs zonder vertrouwen in de geschiedenis.
2. Er een groot verschil is tussen het voorspellen van de toekomst en het spelen om te winnen. Je kunt heel goed spelen met weinig geheugen, maar om de toekomst te voorspellen heb je vaak meer geheugen nodig (tenzij de situatie simpel is).

Kortom: In een chaotische wereld kun je slimme voorspellingen doen, maar je moet wel weten hoeveel "ruimte" in je hoofd je daarvoor nodig hebt. Soms volstaat een post-itje, soms heb je een hele bibliotheek nodig.

Technische samenvatting

1. Probleemdefinitie en Context

Het artikel onderzoekt een variant van het Multi-Armed Bandit (MAB) probleem in een adversariale omgeving (waarbij beloningen niet stochastisch zijn, maar door een tegenstander kunnen worden gekozen). Traditioneel worden twee hoofddoelen in MAB onderscheiden:

1. Regret-minimalisatie: Het minimaliseren van het verschil tussen de cumulatieve beloning van de algoritme en die van de beste arm in hindsight.
2. Best-Arm Identification (BAI): Het identificeren van de arm met de hoogste verwachte beloning.

Het probleem: In adversariale settings is klassieke BAI zinloos. Omdat de tegenstander de beloningen dynamisch kan aanpassen, geeft de beste prestatie in het verleden geen enkele garantie voor de toekomst. Het is onmogelijk om een arm te vinden die "altijd" het beste zal presteren.

De oplossing: De auteurs introduceren Lookahead BAI. Het doel is niet om de beste arm voor het verleden te vinden, maar om een arm te selecteren die binnen een toekomstig tijdsvenster (prediction window) bijna optimaal presteert.

• De leerling kiest een starttijd $t_0$ en een venstergrootte $w$.
• De leerling moet een arm $\hat{i}$ kiezen zodat de gemiddelde beloning over het venster $[t_0, t_0+w]$ binnen $\epsilon$ ligt van de optimale arm voor dat specifieke venster.
• De leerling werkt onder een geheugenbeperking ($\sigma$ bits).

2. Methodologie en Algoritmen

De auteurs analyseren zowel de haalbaarheid van nauwkeurige identificatie als de kosten in termen van geheugen. Ze presenteren drie kernalgoritmen:

A. Algoritme 1: Lookahead BAI (Algemeen)

Dit algoritme werkt zonder extra aannames over de data, maar vereist veel geheugen.

• Methode: Het algoritme kiest willekeurig een venstergrootte $w$ en een starttijd $t_0$ gebaseerd op een binaire boom-structuur (geïnspireerd door Drucker, 2013).
• Exploratie: Tijdens het venster $[t_0-w, t_0]$ wordt willekeurig een arm gekozen om een schatting te maken van de gemiddelde beloning.
• Selectie: De arm met de hoogste geschatte cumulatieve beloning in het venster wordt gekozen als voorspelling voor het volgende venster.
• Geheugen: Vereist $\Omega(K)$ bits om de sommen van alle $K$ armen bij te houden.

B. Algoritme 2: Lookahead BAI voor Sparsere Instancies

Dit algoritme is ontworpen voor situaties waar de beloningen "lokaal spaars" zijn (d.w.z. slechts een paar armen hebben significante beloningen in een venster).

• Voorwaarde: De instancier is $\phi$-spaars, wat betekent dat de verhouding tussen de som van de kwadraten van de beloningen en het kwadraat van de maximale beloning klein is ($\|\bar{n}\|_2^2 / n_1^2 \leq \phi$).
• Methode: Het gebruikt een CountSketch datastructuur (Charikar et al., 2004) in plaats van volledige sommen bij te houden.
• Voordeel: Dit reduceert het geheugengebruik drastisch tot polylogaritmisch in $K$ en $T$, terwijl de nauwkeurigheid behouden blijft.

C. Algoritme 3: Regret-minimalisatie met Beperkt Geheugen

Om te laten zien dat het geheugenprobleem specifiek is voor BAI en niet voor alle adversariale bandit taken, presenteren ze een algoritme voor regret-minimalisatie.

• Methode: Het deelt de tijd in blokken in en gebruikt een bestaand "expert"-algoritme met beperkt geheugen (van Peng en Rubinstein, 2023).
• Techniek: Door een combinatie van exploitatie (volgen van de expert) en willekeurige exploratie binnen blokken, wordt een schatting van de verliezen gemaakt die voldoende is voor het expert-algoritme om te updaten.
• Resultaat: Het bereikt sublineaire regret met slechts polylogaritmisch geheugen.

3. Belangrijkste Resultaten en Theorema's

De auteurs leveren zowel boven- als ondergrenzen voor nauwkeurigheid ($\epsilon$) en geheugen ($\sigma$):

| Taak | Scenario | Nauwkeurigheid ($\epsilon$) | Geheugen ($\sigma$) | Opmerking |
| :--- | :--- | :--- | :--- :--- |
| Lookahead BAI | Algemeen | $O(1/\sqrt{\log T})$ | $\Omega(K)$ bits | Theorema 2 & 8 |
| Lookahead BAI | Spars (Lokaal) | $O(1/\sqrt{\log T})$ | $\tilde{O}(1)$ bits | Theorema 14 |
| Regret Min. | Beperkt Geheugen | - | $\tilde{O}(1)$ bits | Regret: $\tilde{O}(T^{2/3}K^{1/3})$ (Theorema 17) |

Kernbevindingen:

1. Haalbaarheid: Identificatie is mogelijk in adversariale settings, maar met een foutmarge van $O(1/\sqrt{\log T})$. Een lagere foutmarge is onmogelijk (ondergrens $\Omega(1/\log T)$).
2. Geheugenvereiste voor BAI: Voor algemene adversariale bandits is $\Omega(K)$ bits geheugen noodzakelijk om een niet-triviale nauwkeurigheid te garanderen. Dit is een harde ondergrens bewezen via een reductie naar het Set-Disjointness probleem.
3. Sparsiteit: Als de data lokaal spaars is, kan dezelfde nauwkeurigheid worden bereikt met slechts polylogaritmisch geheugen.
4. Scheiding tussen BAI en Regret: Er is een scherpe scheiding tussen de twee taken.
   • BAI vereist veel geheugen ($\Omega(K)$) in het ergste geval.
   • Regret-minimalisatie kan worden opgelost met zeer weinig geheugen (polylogaritmisch), zelfs in adversariale settings. Dit is een verrassend resultaat, aangezien men zou denken dat beide taken vergelijkbare geheugeneisen hebben.

4. Bijdrage en Significantie

De paper levert een fundamentele bijdrage aan het begrip van de interactie tussen voorspelling, adversariale omgevingen en geheugenbeperkingen:

• Eerste positieve resultaten voor adversariale BAI: Voorheen werd aangenomen dat BAI in adversariale settings onmogelijk was. Dit paper toont aan dat het wel mogelijk is, mits men kijkt naar een toekomstig venster (lookahead) en accepteert dat de foutmarge logaritmisch is.
• Geheugen-accuraatheid trade-off: De auteurs karakteriseren precies hoeveel geheugen nodig is. Ze tonen aan dat het "geheugenprobleem" inherent is aan de identificatietaken in het ergste geval, maar dat dit opgelost kan worden onder realistische aannames (sparsiteit).
• Fundamentele scheiding: Het meest opvallende resultaat is de demonstratie dat regret-minimalisatie en best-arm identification fundamenteel verschillende geheugeneisen hebben in bandit settings. Waar BAI veel geheugen nodig heeft, kan regret worden geminimaliseerd met weinig geheugen. Dit weerlegt de intuïtie dat beide taken even zwaar zijn in termen van informatieverwerking.
• Verbetering van bestaande werk: De resultaten voor regret-minimalisatie met beperkt geheugen verbeteren eerdere resultaten (zoals die van Xu en Zhao, 2021) aanzienlijk in zowel de regret-grens als de geheugengrens.

Conclusie:
Het werk toont aan dat hoewel het voorspellen van de toekomst in een volledig vijandige omgeving beperkt is door de beschikbare informatie (en dus een logaritmische foutmarge heeft), het beheersen van de geheugeneisen mogelijk is door slimme algoritmen te gebruiken die inspelen op de structuur van de data (sparsiteit) of door de doelstelling te verschuiven van identificatie naar regret-minimalisatie.