Learning from Local Walks on Dynamic Graphs with Bandit Feedback

Sintesi Tecnica: Apprendimento da Cammini Locali su Grafi Dinamici con Feedback Banditico

Formulazione del Problema
Questo articolo affronta il problema dei multi-armed bandit (MAB) stocastici in un contesto in cui l'apprendista è vincolato al movimento locale su un grafo dinamico. A differenza dei modelli classici di MAB dove ogni braccio è disponibile in ogni round, o dei modelli a feedback-graph dove sono disponibili osservazioni laterali, qui l'apprendista può selezionare solo il proprio nodo corrente o un suo vicino immediato in base alla connettività del grafo in quel preciso istante temporale.

• Setting: I bracci corrispondono ai vertici $A = \{1, \dots, n\}$ di un grafo non orientato tempo-variante $G_t = (A, E_t)$.
• Vincoli: Al round $t$, l'apprendista osserva solo il vicinato locale $L_t(a_{t-1})$ e deve scegliere $a_t \in L_t(a_{t-1})$. Il processo del grafo è oblivious (indipendente dalle azioni dell'apprendista).
• Sfida Centrale: Questo setting scinde l'identificazione del miglior braccio dall'exploitation. Nei bandit classici, identificare il braccio ottimale $a^\star$ permette l'immediata exploitation. In questo setting dinamico, anche dopo che $a^\star$ è stato identificato, l'apprendista potrebbe trovarsi strutturalmente isolato da esso a causa della topologia evolutiva. La apprendibilità richiede che l'ambiente fornisca costantemente percorsi navigabili, non solo che l'unione di tutti i grafi sull'orizzonte sia connessa.

Metodologia e Condizioni Strutturali
Gli autori adottano un framework explore-then-commit, separando il problema in esplorazione (raccolta di campioni) e navigazione (raggiungimento del target identificato). Per garantire la apprendibilità, introducono una condizione strutturale agnostica rispetto al processo basata sul cammino canonico (un semplice random walk dove l'apprendista resta fermo o si muove uniformemente verso un vicino).

• Common-Stationary Sliding-Window Mixing (Definizione 1): Il paper rifiuta le condizioni di connettività dell'intero orizzonte (ad esempio, l'unione di tutti i grafi essere connessa) come insufficienti, poiché non garantiscono la raggiungibilità ad arbitrarie ore di arresto. Invezione, impone una condizione sul random walk indotto:
  1. Distribuzione Stazionaria Comune: Ogni istantanea del grafo $G_t$ induce un kernel reversibile $U_t$ con una distribuzione stazionaria comune $\pi$ (ad esempio, ottenuta tramite sequenze di grado fissate).
  2. Sliding-Window Mixing: In ogni finestra temporale di lunghezza $W$, almeno una frazione $\rho$ dei round deve avere un gap spettrale $\ge \gamma$.
     Questa condizione assicura che il cammino si misceli verso $\pi$ uniformemente nel tempo, impedendo all'apprendista di rimanere intrappolato in sottografi locali indefinitamente, indipendentemente da quando termina l'esplorazione.

Algoritmi
Il paper analizza una famiglia di algoritmi che operano sotto questo regime:

1. LEX (Fixed-Budget Lazy Exploration): Utilizza il cammino canonico per l'esplorazione per un budget fisso $T_{exp}$ determinato dai parametri di mixing e dai gap di reward. Si impegna (commit) sul leader empirico e naviga usando il cammino canonico se il target non è immediatamente raggiungibile.
2. CB-LEX (Confidence-Based Stopping): Sostituisce il budget fisso con una regola di arresto dipendente dai dati. Termina quando il Lower Confidence Bound (LCB) del leader empirico domina gli Upper Confidence Bounds (UCB) di tutti gli altri bracci (non solo del secondo miglior braccio), garantendo robustezza contro il campionamento non uniforme.
3. RALEX (Reward-Aware Exploration): Introduce un kernel distorto dal reward che mescola il cammino canonico con una proposta ottimistica (softmax sui reward stimati). Fondamentalmente, mantiene un "pavimento canonico" ($\epsilon_0$) per garantire che le proprietà di mixing strutturale del cammino canonico siano preservate, garantendo la sicurezza nel caso peggiore.

Risultati Chiave e Regret Bounds
Sotto la condizione di $(W, \rho, \gamma, \pi)$-mixing, gli autori stabiliscono un regret atteso sublineare ($o(T)$) per tutti gli algoritmi proposti. I limiti di regret si decompongono in due componenti distinte:

1. Learning Regret: Scala con la difficoltà statistica (inverso dei gap $\Delta^{-2}$) e l'overhead di mixing ($\tau_0$), rappresentando il costo di identificare il miglior braccio.
2. Navigation Regret: Un costo strutturale indipendente dall'orizzonte $T$, che rappresenta il tempo atteso per raggiungere il braccio ottimale identificato dal punto di arresto.

• LEX/CB-LEX: Raggiungono un regret di ordine $O(\tau_0 \cdot \Psi \cdot \log T)$, dove $\Psi$ cattura la complessità dei gap e delle masse stazionarie.
• RALEX: Dimostra che la distorsione consapevole del reward è compatibile con un regret sublineare. Sebbene il limite del caso peggiore sia conservativo (a causa del pavimento canonico), il paper fornisce un teorema separato (Teorema 4) mostrando che se la distorsione consapevole del reward riesce ad aumentare la probabilità di visita degli armi "vicino ai colli di bottiglia", si ottiene un guadagno di performance provabile (miglioramento moltiplicativo nel termine di apprendimento).

Significato e Rivendicazioni
Il paper si pone come una caratterizzazione strutturale della apprendibilità per bandit localmente vincolati su grafi dinamici, piuttosto che come una proposta per la minimizzazione del regret quasi-ottimale su specifiche famiglie di grafi (come i grafi completi).

• Invarianza rispetto allo shift: Il contributo primario è la condizione di mixing a finestra scorrevole e invariante rispetto allo shift. Ciò assicura che le assunzioni strutturali richieste per la navigazione valgano anche dopo il tempo di arresto casuale dell'esplorazione, un requisito che le condizioni sull'intero orizzonte non soddisfano.
• Decoupling (Disaccoppiamento): Il lavoro separa esplicitamente il costo statistico dell'apprendimento dal costo strutturale della navigazione, fornendo un framework teorico pulito per ambienti dinamici.
• Agnosticismo rispetto al processo: A differenza del lavoro precedente che si basa su specifici processi di grafi (ad esempio, Erdős–Rényi i.i.d. o edge-Markovian), questo paper fornisce un teorema che vale per qualsiasi sequenza di grafi che soddisfi la condizione di mixing centrata sul cammino.
• Sicurezza vs Guadagno: L'analisi di RALEX distingue tra un "teorema di sicurezza" (che garantisce un regret sublineare con qualsiasi parametro di distorsione) e un "teorema di guadagno" (che certifica il miglioramento delle performance sotto specifiche condizioni sulla proposta consapevole del reward).

Gli autori concludono che il loro lavoro stabilisce un "regime positivo" in cui il cammino canonico intrinseco è sufficiente per l'apprendimento, offrendo una base per estensioni future a kernel più complessi come i cammini di tipo Metropolis.