Contextual Bandits for Resource-Constrained Devices using Probabilistic Learning

Technischer Überblick: Kontextuelle Banditen für ressourcenbeschränkte Geräte mittels probabilistischem Lernen

Problemstellung
Kontextuelle Banditen (CB) sind grundlegend für die sequenzielle Online-Entscheidungsfindung in adaptiven Diensten wie personalisierten Empfehlungen und Edge-Computing. Der direkte Einsatz von CB-Agenten auf ressourcenbeschränkten Geräten (z. B. Mobilgeräte, Wearables, Luftfahrzeuge) stellt jedoch erhebliche Herausforderungen dar. Standardlineare CB-Algorithmen sind zwar effektiv, erfordern jedoch die Pflege von Kovarianzmatrizen, die quadratisch mit der Kontextdimensionalität skalieren ($O(Nd^2)$ Speicherbedarf), und beinhalten rechenintensive lineare Algebra-Operationen ($O(d^3)$ Komplexität), was sie für Geräte mit strengen Speicher-, Rechen- und Energiebeschränkungen ungeeignet macht.

Neuere Arbeiten führten Hyperdimensionale Kontextuelle Banditen (HD-CB) ein, die Hyperdimensionales Rechnen (HDC) nutzen, um CB-Probleme in hochdimensionalen Räumen mittels leichtgewichtiger Vektoroperationen zu lösen. Obwohl HD-CB lineare Zeitkomplexität und verbesserte Skalierbarkeit bietet, stützt sich die Standardimplementierung auf akkumulationsbasierte Updates, bei denen die Komponenten der Aktionsvektoren unbegrenzt anwachsen. Dies erfordert hochpräzise numerische Typen (z. B. 32-Bit-Gleitkommazahlen), um Überläufe zu verhindern, wodurch die Gewinne bei der Speichereffizienz zunichte gemacht werden. Eine vorherige Variante mit niedriger Präzision, HD-CBBIN, behandelte Überläufe durch periodisches Binarisieren von Vektoren und Zurücksetzen von Zählern. Diese deterministische Binarisierung verwirft jedoch angesammelte Magnitudeninformationen, was zu Leistungseinbußen führt, insbesondere in lauten oder datenarmen Regimen.

Methodik: Probabilistisches HD-CB (HD-CBPROB)
Dieser Beitrag stellt HD-CBPROB vor, eine Variante von HD-CB mit niedriger Präzision, die deterministische Akkumulation durch eine probabilistische Update-Regel ersetzt. Die Kerninnovation besteht darin, das Lernen durch Design zu begrenzen, anstatt durch periodische Resets.

1. Begrenzte Ganzzahl-Komponenten: Anstatt den Vektorkomponenten zu erlauben, unbegrenzt zu wachsen, beschränkt HD-CBPROB jede Komponente auf einen vordefinierten Ganzzahlbereich $[-\kappa, +\kappa]$. Dies ermöglicht die Verwendung von Ganzzahl-Zählern mit niedriger Präzision und Sättigung (z. B. 2, 3 oder 4 Bits).
2. Probabilistische Update-Regel: Um das Lernen innerhalb dieser engen Grenzen ohne Informationsverlust zu ermöglichen, ersetzt der Algorithmus den magnitudenbasierten Update durch einen frequenzbasierten Update. Zu jedem Zeitpunkt $t$ wird nur eine zufällige Teilmenge der Vektorkomponenten basierend auf einer zeitlich abklingenden Wahrscheinlichkeit $\alpha_t$ aktualisiert.
   • Die Update-Wahrscheinlichkeit ist definiert als $\alpha_t = \alpha_0 \max(0, 1 - \frac{t-1}{T})$.
   • Für jede Komponente $i$ wird ein zufälliger Wert $m_{t,i} \sim U(0, 1)$ abgetastet. Ein Update erfolgt nur, wenn $m_{t,i} \leq \alpha_t$.
   • Wenn ein Update stattfindet, wird die Komponente um $\pm 1$ inkrementiert oder dekrementiert (basierend auf der Bindung der Kontext- und Belohnungs-Hypervektoren) und anschließend auf den Bereich $[-\kappa, +\kappa]$ geklemmt.
3. Mechanismus: Dieser Ansatz implementiert effektiv einen „sättigenden Zufallsprozess". Durch die Kontrolle der Häufigkeit von Updates anstelle der Magnitude gespeicherter Werte behält der Agent historische Informationen auch bei Komponenten mit niedriger Präzision mit hoher Genauigkeit bei. Dies eliminiert die Notwendigkeit für Hilfszähler und periodische Binarisierungsschritte, die von HD-CBBIN erforderlich sind.

Hauptbeiträge

• Algorithmische Innovation: Einführung einer probabilistischen Update-Regel für HD-CB, die die Verwendung von Ganzzahl-Komponenten mit niedriger Präzision und Sättigung ohne periodischen Informationsverlust ermöglicht.
• Ressourceneffizienz: Die Methode reduziert den Speicherbedarf, indem sie die Notwendigkeit für Hilfszähler und separate binarisierte Kopien von Vektoren eliminiert, die bei vorherigen Varianten mit niedriger Präzision erforderlich waren. Sie reduziert auch die Rechenkosten, da die erwartete Anzahl von Updates aufgrund der abklingenden Wahrscheinlichkeit $\alpha_t$ im Laufe der Zeit abnimmt.
• Leistungserhaltung: Der Ansatz bewahrt die Ranking-Qualität von Aktionen, indem er Magnitudeninformationen durch die Update-Häufigkeit erhält und so die mit harter Binarisierung verbundenen Verschlechterungen vermeidet.

Experimentelle Ergebnisse
Die Autoren evaluierten HD-CBPROB mittels Off-Policy-Evaluation auf standardisierten synthetischen CB-Benchmarks über die Open Bandit Pipeline (OBP) und verglichen es mit:

1. LinEPS: Standardlinearer CB (Basislinie).
2. HD-CBREAL: HD-CB mit reellen Werten.
3. HD-CBBIN: Binarisiertes HD-CB mit periodischen Resets.
4. HD-CBPROB: Der vorgeschlagene probabilistische Ansatz.

Wichtige Erkenntnisse umfassen:

• Überlegenheit gegenüber binarisierten Varianten: HD-CBPROB übertrifft HD-CBBIN bei gleichen Präzisionsniveaus konsistent in allen getesteten Konfigurationen (variierende Kontextdimensionalität $d$ und Anzahl der Aktionen $N$). Insbesondere verbesserte eine 3-Bit-HD-CBPROB-Implementierung die kumulativen Belohnungen um etwa 5,8 % gegenüber einer 3-Bit-HD-CBBIN-Implementierung.
• Annäherung an die Leistung mit reellen Werten: Eine 3-Bit-HD-CBPROB-Konfiguration (mit Sättigungsschwelle $\kappa=3$) erreichte eine Leistung, die der Basislinie HD-CBREAL mit reellen Werten nahekommt, mit einer durchschnittlichen Lücke von nur 2,5 %.
• Abnehmende Erträge bei höherer Präzision: Die Erhöhung der Präzision von 3 auf 4 Bits ergab für HD-CBPROB abnehmende oder leicht negative Erträge, was darauf hindeutet, dass 3 Bits ausreichen, um die Aktionsqualität in diesen synthetischen Einstellungen zu erfassen.
• Speichereffizienz: HD-CBPROB benötigt bei gleicher Bitbreite strikt weniger Speicher als HD-CBBIN, da es keine Hilfsmechanismen (Zähler und temporäre binarisierte Kopien) erfordert. Im Gegensatz zu linearen CB bleibt der Speicherbedarf in Bezug auf die Kontextdimensionalität konstant.

Bedeutung und Behauptungen
Der Beitrag behauptet, dass probabilistisches HD-CB den Kompromiss zwischen Speicherbedarf und Informationsverlust auflöst, der früheren hyperdimensionalen Ansätzen innewohnt. Durch den Wechsel von magnitudenbasierter Akkumulation zu frequenzbasierten probabilistischen Updates ermöglicht die Methode den Einsatz adaptiver, autonomer Agenten auf Geräten mit engen Budgets für Leistung, Speicher und Rechenkapazität. Die Autoren positionieren HD-CBPROB als eine überzeugende Alternative für Edge-Intelligenz, die einen Weg bietet, nahezu optimale Entscheidungsleistung bei deutlich reduziertem Ressourcenbedarf im Vergleich sowohl zu Standard-Linearalgorithmen als auch zu bestehenden hyperdimensionalen Varianten mit niedriger Präzision zu erreichen.

Von den Autoren identifizierte zukünftige Arbeiten umfassen die Evaluierung des Ansatzes auf realen, protokollierten Bandit-Datensätzen, Tests unter komplexeren Belohnungsverteilungen sowie die Gewinnung direkter Latenz- und Energiemessungen auf eingebetteter Hardware zur Untermauerung der Behauptungen zum Edge-Einsatz.