Contextual Bandits for Resource-Constrained Devices using Probabilistic Learning

Riepilogo Tecnico: Bandit Contestuali per Dispositivi a Risorse Limitate mediante Apprendimento Probabilistico

Enunciato del Problema
I bandit contestuali (CB) sono fondamentali per la decisione sequenziale online nei servizi adattivi, come le raccomandazioni personalizzate e il calcolo periferico (edge computing). Tuttavia, distribuire agenti CB direttamente su dispositivi a risorse limitate (ad esempio, dispositivi mobili, indossabili, aerei) presenta sfide significative. Gli algoritmi CB lineari standard, sebbene efficaci, richiedono il mantenimento di matrici di covarianza che scalano quadraticamente con la dimensionalità del contesto ($O(Nd^2)$ di memoria) e coinvolgono operazioni di algebra lineare computazionalmente costose ($O(d^3)$ di complessità), rendendoli inadatti per dispositivi con vincoli rigorosi di memoria, calcolo ed energia.

Lavori recenti hanno introdotto i Bandit Contestuali Iperdimensionali (HD-CB), che sfruttano il Calcolo Iperdimensionale (HDC) per risolvere problemi CB in spazi ad alta dimensionalità utilizzando operazioni vettoriali leggere. Sebbene HD-CB offra una complessità temporale lineare e una migliore scalabilità, la sua implementazione standard si basa su aggiornamenti basati sull'accumulo, dove i componenti del vettore di azione crescono indefinitamente. Ciò richiede tipi numerici ad alta precisione (ad esempio, float a 32 bit) per prevenire l'overflow, annullando i guadagni di efficienza della memoria. Una precedente variante a bassa precisione, HD-CBBIN, ha affrontato l'overflow binarizzando periodicamente i vettori e resettando i contatori. Tuttavia, questa binarizzazione deterministica scarta le informazioni di magnitudine accumulate, portando a un degrado delle prestazioni, specialmente in regimi rumorosi o con scarsità di dati.

Metodologia: HD-CB Probabilistico (HD-CBPROB)
Questo articolo propone HD-CBPROB, una variante a bassa precisione di HD-CB che sostituisce l'accumulo deterministico con una regola di aggiornamento probabilistico. L'innovazione centrale è delimitare l'apprendimento per progettazione piuttosto che attraverso reset periodici.

1. Componenti Intere Delimitate: Invece di permettere ai componenti del vettore di crescere indefinitamente, HD-CBPROB vincola ogni componente a un intervallo intero predefinito $[-\kappa, +\kappa]$. Ciò consente l'uso di contatori interi saturi a bassa precisione (ad esempio, 2, 3 o 4 bit).
2. Regola di Aggiornamento Probabilistica: Per abilitare l'apprendimento entro questi limiti stretti senza perdere informazioni, l'algoritmo sostituisce l'aggiornamento basato sulla magnitudine con un aggiornamento basato sulla frequenza. Ad ogni passo temporale $t$, viene aggiornato solo un sottoinsieme casuale dei componenti del vettore in base a una probabilità che decade nel tempo $\alpha_t$.
   • La probabilità di aggiornamento è definita come $\alpha_t = \alpha_0 \max(0, 1 - \frac{t-1}{T})$.
   • Per ogni componente $i$, viene campionata un valore casuale $m_{t,i} \sim U(0, 1)$. Un aggiornamento avviene solo se $m_{t,i} \leq \alpha_t$.
   • Quando avviene un aggiornamento, il componente viene incrementato o decrementato di $\pm 1$ (in base al vincolo dei vettori iperdimensionali del contesto e della ricompensa) e poi limitato all'intervallo $[-\kappa, +\kappa]$.
3. Meccanismo: Questo approccio implementa efficacemente una "passeggiata casuale saturante". Controllando la frequenza degli aggiornamenti piuttosto che la magnitudine dei valori memorizzati, l'agente mantiene le informazioni storiche con alta fedeltà anche in componenti a bassa precisione. Ciò elimina la necessità di contatori ausiliari e passaggi di binarizzazione periodica richiesti da HD-CBBIN.

Contributi Chiave

• Innovazione Algoritmica: Introduzione di una regola di aggiornamento probabilistica per HD-CB che abilita l'uso di componenti intere sature a bassa precisione senza perdita periodica di informazioni.
• Efficienza delle Risorse: Il metodo riduce l'ingombro di memoria eliminando la necessità di contatori ausiliari e copie separate binarizzate dei vettori richiesti dalle precedenti varianti a bassa precisione. Riduce anche il costo computazionale poiché il numero atteso di aggiornamenti diminuisce nel tempo a causa della probabilità decrescente $\alpha_t$.
• Preservazione delle Prestazioni: L'approccio mantiene la qualità di ordinamento delle azioni preservando le informazioni di magnitudine attraverso la frequenza di aggiornamento, evitando il degrado associato alla binarizzazione rigida.

Risultati Sperimentali
Gli autori hanno valutato HD-CBPROB utilizzando la valutazione off-policy su benchmark sintetici CB standardizzati tramite la Open Bandit Pipeline (OBP), confrontandolo con:

1. LinEPS: CB lineare standard (baseline).
2. HD-CBREAL: HD-CB a valori reali.
3. HD-CBBIN: HD-CB binarizzato con reset periodici.
4. HD-CBPROB: La variante probabilistica proposta.

Le scoperte chiave includono:

• Superiorità rispetto alle Varianti Binarizzate: HD-CBPROB supera costantemente HD-CBBIN a livelli di precisione uguali in tutte le configurazioni testate (variando la dimensionalità del contesto $d$ e il numero di azioni $N$). Nello specifico, un'implementazione HD-CBPROB a 3 bit ha migliorato le ricompense cumulative di circa il 5,8% rispetto a un'implementazione HD-CBBIN a 3 bit.
• Avvicinamento alle Prestazioni a Valori Reali: Una configurazione HD-CBPROB a 3 bit (con soglia di saturazione $\kappa=3$) ha raggiunto prestazioni vicine alla baseline HD-CBREAL a valori reali, con un divario medio di soli 2,5%.
• Rendimenti Decrescenti sulla Precisione: L'aumento della precisione da 3 a 4 bit ha prodotto rendimenti decrescenti o leggermente negativi per HD-CBPROB, suggerendo che 3 bit sono sufficienti per catturare la qualità delle azioni in questi ambienti sintetici.
• Efficienza della Memoria: HD-CBPROB richiede rigorosamente meno memoria di HD-CBBIN alla stessa larghezza di bit perché non richiede meccanismi ausiliari (contatori e copie temporanee binarizzate). A differenza del CB lineare, il suo ingombro di memoria rimane costante rispetto alla dimensionalità del contesto.

Significato e Affermazioni
L'articolo afferma che l'HD-CB probabilistico risolve il compromesso tra ingombro di memoria e perdita di informazioni intrinseco nei precedenti approcci iperdimensionali. Spostandosi dall'accumulo basato sulla magnitudine agli aggiornamenti probabilistici basati sulla frequenza, il metodo abilita la distribuzione di agenti adattivi e autonomi su dispositivi con budget rigorosi di potenza, memoria e calcolo. Gli autori posizionano HD-CBPROB come un'alternativa convincente per l'intelligenza periferica (edge intelligence), offrendo un modo per raggiungere prestazioni decisionali quasi ottimali con requisiti di risorse significativamente ridotti rispetto sia agli algoritmi lineari standard che alle varianti iperdimensionali a bassa precisione esistenti.

I lavori futuri identificati dagli autori includono la valutazione dell'approccio su dataset reali di bandit registrati, test sotto distribuzioni di ricompensa più complesse e l'ottenimento di misurazioni dirette di latenza ed energia su hardware incorporato per sostenere le affermazioni relative alla distribuzione periferica.