Contextual Bandits for Resource-Constrained Devices using Probabilistic Learning

Technische Samenvatting: Contextuele Bandieten voor Middelenbeperkte Apparaten met Probabilistisch Leren

Probleemstelling
Contextuele bandieten (CB) zijn fundamenteel voor online sequentiële besluitvorming in adaptieve diensten zoals gepersonaliseerde aanbevelingen en edge computing. Het rechtstreeks implementeren van CB-agenten op middelenbeperkte apparaten (bijvoorbeeld mobiele telefoons, wearables, luchtvaartapparaten) vormt echter aanzienlijke uitdagingen. Standaard lineaire CB-algoritmen zijn weliswaar effectief, maar vereisen het bijhouden van covariantiematrices die kwadratisch schalen met de contextdimensie ($O(Nd^2)$ geheugen) en omvatten rekenkundig kostbare lineair-algebra-operaties ($O(d^3)$ complexiteit), waardoor ze ongeschikt zijn voor apparaten met strikte geheugen-, reken- en energiebeperkingen.

Recent werk introduceerde Hyperdimensionale Contextuele Bandieten (HD-CB), die Hyperdimensionaal Leren (HDC) benutten om CB-problemen in hoogdimensionale ruimten op te lossen met behulp van lichtgewicht vectoroperaties. Hoewel HD-CB lineaire tijdscomplexiteit biedt en de schaalbaarheid verbetert, vertrouwt de standaardimplementatie op accumulatie-gedreven updates waarbij actievectorcomponenten onbeperkt groeien. Dit vereist numerieke typen met hoge precisie (bijvoorbeeld 32-bits floats) om overloop te voorkomen, waardoor de winst in geheugenefficiëntie teniet wordt gedaan. Een eerdere variant met lage precisie, HD-CBBIN, loste overloop op door vectoren periodiek te binariseren en tellers te resetten. Deze deterministische binarisatie gooit echter opgehoopte magnitude-informatie weg, wat leidt tot prestatiedegradatie, met name in ruisige regimes of bij gebrek aan data.

Methodologie: Probabilistische HD-CB (HD-CBPROB)
Dit artikel stelt HD-CBPROB voor, een variant met lage precisie van HD-CB die deterministische accumulatie vervangt door een probabilistische updateregel. De kerninnovatie bestaat uit het begrenzen van het leren door ontwerp in plaats van via periodieke resets.

1. Beperkte Integer-componenten: In plaats van vectorcomponenten onbeperkt te laten groeien, beperkt HD-CBPROB elke component tot een vooraf gedefinieerd integerbereik $[-\kappa, +\kappa]$. Dit maakt het gebruik mogelijk van low-precision verzadigde integer-tellers (bijvoorbeeld 2, 3 of 4 bits).
2. Probabilistische Updateregel: Om leren binnen deze strakke grenzen mogelijk te maken zonder informatie te verliezen, vervangt het algoritme de update op basis van magnitude door een update op basis van frequentie. Op elk tijdstip $t$ wordt slechts een willekeurige subset van vectorcomponenten bijgewerkt op basis van een tijdsafhankelijke waarschijnlijkheid $\alpha_t$.
   • De updatekans wordt gedefinieerd als $\alpha_t = \alpha_0 \max(0, 1 - \frac{t-1}{T})$.
   • Voor elke component $i$ wordt een willekeurige waarde $m_{t,i} \sim U(0, 1)$ getrokken. Een update vindt alleen plaats als $m_{t,i} \leq \alpha_t$.
   • Wanneer een update plaatsvindt, wordt de component met $\pm 1$ verhoogd of verlaagd (gebaseerd op de binding van de context- en beloning-hypervectoren) en vervolgens afgekapt tot het bereik $[-\kappa, +\kappa]$.
3. Mechanisme: Deze aanpak implementeert effectief een "verzadigende willekeurige wandeling". Door de frequentie van updates te controleren in plaats van de magnitude van opgeslagen waarden, behoudt de agent historische informatie met hoge fideliteit, zelfs in componenten met lage precisie. Dit elimineert de noodzaak van hulptellers en periodieke binarisatiestappen die vereist zijn door HD-CBBIN.

Belangrijkste Bijdragen

• Algoritmische Innovatie: Introductie van een probabilistische updateregel voor HD-CB die het gebruik mogelijk maakt van low-precision, verzadigde integer-componenten zonder periodiek informatieverlies.
• Middelen-efficiëntie: De methode verkleint het geheugengebruik door de noodzaak tot hulpmiddelen en aparte gebinariseerde kopieën van vectoren, zoals vereist door eerdere varianten met lage precisie, te elimineren. Het verlaagt ook de rekentijd, aangezien het verwachte aantal updates in de loop van de tijd afneemt door de afnemende waarschijnlijkheid $\alpha_t$.
• Behoud van Prestaties: De aanpak behoudt de rangschikkingkwaliteit van acties door magnitude-informatie te behouden via updatefrequentie, waardoor de degradatie die gepaard gaat met harde binarisatie wordt vermeden.

Experimentele Resultaten
De auteurs evalueerden HD-CBPROB met behulp van off-policy evaluatie op gestandaardiseerde synthetische CB-benchmarks via de Open Bandit Pipeline (OBP), waarbij het werd vergeleken met:

1. LinEPS: Standaard lineaire CB (baseline).
2. HD-CBREAL: HD-CB met reële waarden.
3. HD-CBBIN: Gebinariseerde HD-CB met periodieke resets.
4. HD-CBPROB: De voorgestelde probabilistische variant.

Belangrijkste bevindingen zijn:

• Superioriteit boven Gebinariseerde Varianten: HD-CBPROB presteert consistent beter dan HD-CBBIN op gelijke precisieniveaus in alle geteste configuraties (variërende contextdimensie $d$ en aantal acties $N$). Specifiek verbeterde een 3-bits HD-CBPROB-implementatie de cumulatieve beloningen met ongeveer 5,8% ten opzichte van een 3-bits HD-CBBIN-implementatie.
• Benadering van Prestaties met Reële Waarden: Een 3-bits HD-CBPROB-configuratie (met verzadigingsdrempel $\kappa=3$) behaalde prestaties die dicht in de buurt kwamen van de HD-CBREAL-baseline met reële waarden, met een gemiddelde kloof van slechts 2,5%.
• Afnemende Meerwaarde van Precisie: Het verhogen van de precisie van 3 naar 4 bits leverde voor HD-CBPROB afnemende of licht negatieve meerwaarde op, wat suggereert dat 3 bits voldoende zijn om actie-kwaliteit in deze synthetische settings te vangen.
• Geheugenefficiëntie: HD-CBPROB vereist strikt minder geheugen dan HD-CBBIN bij dezelfde bitbreedte, omdat het geen hulpmiddelen vereist (tellers en tijdelijke gebinariseerde kopieën). In tegenstelling tot lineaire CB blijft het geheugengebruik constant ten opzichte van de contextdimensie.

Betekenis en Claims
Het artikel claimt dat probabilistische HD-CB de afweging tussen geheugengebruik en informatieverlies, die inherent is aan eerdere hyperdimensionale benaderingen, oplost. Door over te stappen van accumulatie op basis van magnitude naar probabilistische updates op basis van frequentie, maakt de methode de implementatie van adaptieve, autonome agenten mogelijk op apparaten met krappe budgetten voor stroom, geheugen en rekenkracht. De auteurs positioneren HD-CBPROB als een overtuigend alternatief voor edge-intelligentie, waarbij een manier wordt geboden om bijna optimale besluitvormingsprestaties te bereiken met aanzienlijk verminderde middelenvereisten in vergelijking met zowel standaard lineaire algoritmen als bestaande hyperdimensionale varianten met lage precisie.

Toekomstig werk dat door de auteurs is geïdentificeerd, omvat het evalueren van de aanpak op real-world gelogde bandietdatasets, testen onder complexere beloningsverdelingen, en het verkrijgen van directe latentie- en energiemetingen op embedded hardware om claims over implementatie aan de edge te onderbouwen.