Sintesi Tecnica: Flickering Multi-Armed Bandits

1. Formulazione del Problema

Il documento introduce il framework Flickering Multi-Armed Bandit (FMAB) per affrontare il processo decisionale sequenziale in ambienti in cui la disponibilità delle azioni è dinamica, ristretta e dipendente dallo stato corrente dell'agente. A differenza dei classici problemi Multi-Armed Bandit (MAB), che assumono l'accesso illimitato a un insieme fisso di braccia, il FMAB modella scenari in cui un agente può selezionare solo un sottoinsieme di braccia definito dal suo attuale posizionamento in un grafo che evolve stocasticamente.

Vincoli Core:

• Accessibilità Locale: In ogni round $t$, l'agente si trova nell'arm $a_{t-1}$. L'insieme delle braccia disponibili $L_t(a_{t-1})$ è limitato al vicinato di $a_{t-1}$ nel grafo corrente $G_t$, includendo l'arm stesso.
• Evoluzione Stocastica: Il grafo $G_t$ evolve nel tempo. L'agente non può saltare arbitrariamente a qualsiasi arm; deve navigare attraverso la struttura del grafo per raggiungere braccia non visitate o promettenti.
• Doppia Sfida: L'agente affronta una tensione tra l'acquisizione di informazioni statistiche (esplorare le braccia per identificare quella ottimale) e l'overhead di navigazione fisica (il costo di movimento attraverso il grafo per raggiungere tali braccia).

Modelli di Grafo:
Gli autori formalizzano l'evoluzione della disponibilità delle azioni attraverso due processi di grafo casuale primari:

1. i.i.d. Erdős–Rényi (ER): In ogni round, un nuovo grafo viene campionato indipendentemente. Gli archi esistono con probabilità $p$ (omogenea) o probabilità specifiche per ogni arco $p_{ij}$ (eterogenea).
2. Edge-Markovian: Il grafo evolve dallo stato precedente. Gli archi appaiono con probabilità $\alpha$ e scompaiono con probabilità $\beta$. Questo modella una connettività "appiccicosa" (sticky) dove la topologia cambia gradualmente invece di resettarsi completamente.

L'obiettivo è minimizzare il regret cumulativo $R(T) = \sum_{t=1}^T (\mu(a^*) - r_t(a_t))$, dove $a^*$ è l'arm ottimale, soggetto a questi vincoli di movimento locale.

2. Metodologia

La soluzione proposta è un Algoritmo a Due Fasi che utilizza un Lazy Random Walk per l'esplorazione.

Fase I: Identificazione della Miglior Arm (Esplorazione)

• Policy: L'agente esegue un lazy random walk. In ogni step, dato l'arm corrente $a_{t-1}$ e il grafo realizzato $G_t$, l'agente seleziona l'arm successivo $a_t$ uniformemente a caso dall'insieme disponibile $L_t(a_{t-1})$.
• Durata: Questa fase dura per un tempo predeterminato $T_0$.
• Obiettivo: Raccogliere campioni sufficienti da tutte le braccia per stimare accuratamente le loro ricompense medie $\hat{\mu}(a)$.
• Terminazione: Al termine della Fase I, l'agente identifica l'arm candidato ottimale $\hat{a}^* = \arg\max_a \hat{\mu}(a)$.

Fase II: Navigazione e Impegno (Sfruttamento)

• Policy: L'agente continua il lazy random walk finché non raggiunge con successo l'obiettivo identificato $\hat{a}^*$.
• Impegno (Commitment): Una volta che l'agente approda su $\hat{a}^*$, si impegna su questa arm per tutti i round successivi. Poiché l'agente può sempre rimanere alla propria arm (self-loop), esso rimane su $\hat{a}^*$ indefinitamente.

Tecniche di Analisi Teorica

L'analisi unisce le tecniche spettrali per catene di Markov evolutive con le disuguaglianze di concentrazione per grafi tempo-varianti:

• Per Grafi i.i.d. ER:
  • Caso Omogeneo: Il kernel di transizione atteso è simmetrico e doppiamente stocastico, producendo una distribuzione stazionaria uniforme. Gli autori utilizzano un argomento di rigenerazione per dimostrare che il walk si mescola efficientemente.
  • Caso Eterogeneo: Il kernel non è simmetrico. Gli autori impiegano un argomento di tipicità uniforme, dimostrando che le proprietà del grafo realizzato (gradi, tagli) si concentrano nettamente attorno ai loro valori attesi, permettendo limiti uniformi sul gap spettrale e sulla distribuzione stazionaria.
• Per Grafi Edge-Markovian:
  • L'analisi affronta l'accoppiamento tra il walk dell'agente e l'evoluzione del grafo.
  • Viene stabilita una condizione di "Due Velocità" (Two Speeds): il grafo deve evolvere abbastanza lentamente (condizione di stickiness $\beta \le O(1/n)$) rispetto alla velocità di miscelazione del random walk.
  • L'algoritmo richiede un periodo di burn-in ($T_{burn}$) affinché il processo del grafo raggiunga la sua distribuzione stazionaria prima che inizi la fase standard di esplorazione.

3. Risultati Chiave

Bound del Regret

Il documento stabilisce bound di regret sublineari ad alta probabilità per entrambi i modelli di grafo.

Teorema 1 (Grafi i.i.d. ER):
Per il modello ER eterogeneo, il regret $R(T)$ soddisfa con probabilità $1-\delta$:
$$R(T) \le \underbrace{O\left(n \log(nT/\delta) + \frac{n \log(n/\delta)}{\Delta_{\min}^2}\right)}_{\text{Costo di Esplorazione}} + \underbrace{O\left(n \log(n/\delta)\right)}_{\text{Costo di Navigazione}}$$
dove $\Delta_{\min}$ è il minimo gap di sub-ottimalità. Il costo di esplorazione scala linearmente con il numero di braccia $n$, e il costo di navigazione tiene conto del tempo per raggiungere l'arm ottimale.

Teorema 3 (Grafi Edge-Markovian):
Sotto condizioni di tipicità e stickiness, il regret include un termine di burn-in aggiuntivo:
$$R(T) \le \underbrace{O\left(\frac{\log(nT/\delta)}{\alpha+\beta}\right)}_{\text{Burn-in}} + \underbrace{O\left(n \log(nT/\delta) + \frac{n \log(n/\delta)}{\Delta_{\min}^2}\right)}_{\text{Esplorazione}} + \underbrace{O\left(n \log(n/\delta)\right)}_{\text{Navigazione}}$$

Regret Atteso e Quasi-Ottimalità

Impostando la probabilità di fallimento $\delta = 1/T$, gli autori derivano il bound del regret atteso:
$$E[R(T)] = O\left(\frac{n \log(nT)}{\Delta_{\min}^2}\right)$$
Il documento dimostra che questo bound è quasi-ottimale derivando un lower bound informatico-teoretico. Il lower bound mostra che qualsiasi algoritmo deve incorrere in un tempo di identificazione di $\Omega(n \log(T)/\Delta_{\min}^2)$. L'approccio proposto a due fasi eguaglia questo lower bound fino a fattori logaritmici, dimostrando che il "costo di navigazione" non aumenta fondamentalmente la difficoltà statistica del problema oltre il requisito di identificazione.

Simulazioni

I risultati teorici sono validati attraverso:

1. Esperimenti Controllati: Le simulazioni su grafi ER i.i.d. ed Edge-Markovian confermano che il regret medio converge a zero e che il tempo di navigazione scala inversamente con la probabilità di arco $p$ (ovvero, $O(1/p)$).
2. Scenario di Risposta ai Disastri Robotica: Una simulazione di un veicolo terrestre alla ricerca di siti di relay per comunicazioni in una zona colpita da disastri. Il veicolo opera con sensori locali (nessuna mappa globale) e naviga in una rete stradale che cambia dinamicamente (Edge-Markovian). I risultati mostrano che l'algoritmo identifica con successo la posizione ottimale e vi converge, validando l'applicabilità pratica del modello FMAB.

4. Significato e Contributi

Il documento rivendica i seguenti contributi:

• Framework Novello: Introduce il modello FMAB, che è il primo a accoppiare esplicitamente i vincoli di movimento locale (navigazione) con il processo decisionale sequenziale sotto incertezza. Questo affronta una lacuna nella letteratura esistente dove i bandit "Sleeping" o "Volatile" assumono che la disponibilità sia indipendente dalle azioni dell'agente o sia globalmente nota.
• Analisi Unificata: Fornisce un'analisi del regret unificata per l'apprendimento su grafi casuali in evoluzione, gestendo sia la dinamica i.i.d. che quella Markoviana.
• Robustezza Algoritmica: La strategia di lazy random walk proposta si dimostra robusta attraverso diversi regimi di connettività (omogenei, eterogenei e tempo-correlati).
• Limiti Fondamentali: Stabilendo un lower bound corrispondente, il lavoro caratterizza il costo intrinseco dell'apprendimento sotto vincoli di movimento locale, provando che l'overhead fisico di navigazione non degrada il tasso statistico fondamentale di apprendimento (salvo fattori logaritmici).
• Rilevanza Pratica: Il lavoro unisce l'apprendimento online teorico con i vincoli fisici, offrendo una base rigorosa per applicazioni nella robotica, nella risposta ai disastri e nei sistemi di rete dove gli agenti non possono teletrasportarsi tra le opzioni.

Gli autori concludono che, sebbene l'analisi ad alta probabilità dipenda da specifici parametri del grafo, il regret atteso finale dipende solo dai parametri fondamentali del problema ($n, T, \Delta_{\min}$), suggerendo che i vincoli strutturali dell'ambiente sono gestiti efficacemente dalla strategia di esplorazione proposta.