Sintesi Tecnica: Apprendimento in Bandit Markoviani con Stati Non Osservabili ed Epoche Decisionali Vincolate

1. Definizione del Problema

Questo articolo affronta il problema della minimizzazione del regret nei bandit markoviani sotto due vincoli specifici:

1. Stati Non Osservabili: Il controllore non osserva lo stato interno dei bracci (catene di Markov). L'unico feedback disponibile è la ricompensa generata dal braccio attivato. Ciò corrisponde a un setting di "feedback bandit completo" dove lo spazio degli stati è nascosto.
2. Epoche Decisionali Vincolate: Il controllore non può cambiare braccio arbitrariamente ad ogni passo temporale. Invece, il cambio è consentito solo in specifiche epoche decisionali ($\tau_i$), che sono tempi di arresto determinati dal flusso di ricompense. Nello specifico, il controllore deve rimanere impegnato su un braccio finché non viene ricevuto un segnale specifico (ad esempio, una ricompensa non nulla).

I bracci sono modellati come Processi Decisionali di Markov (MDP) in cui le dinamiche di transizione dipendono dal fatto che l'arm sia attivo o passivo. Il sistema evolve in modo tale che i bracci non attivati continuino a transire secondo i loro kernel passivi ($p^0_a$), mentre i bracci attivati transiscono secondo i kernel attivi ($p^1_a$).

2. Framework di Apprendimento e Benchmark

Gli autori limitano la loro analisi a un benchmark di "pure regret" (regret puro).

• Politiche Pure: Una politica è definita "pura" se seleziona un singolo braccio dall'inizio alla fine dell'orizzonte di apprendimento senza mai cambiarlo.
• Definizione di Regret: Il regret è la differenza tra la ricompensa cumulativa dell'algoritmo di apprendimento e la ricompensa cumulativa della migliore politica pura (il braccio con il guadagno asintotico più elevato).

Motivazione per le Politiche Pure:
Sebbene le politiche pure siano generalmente sub-ottimali per i "restless bandits" (dove i bracci non attivati evolvono), gli autori introducono una classe di bandit chiamati self-degrading restless bandits. In questi casi, se un braccio viene lasciato inattivo, il suo bias atteso (una misura della deviazione dalla media della ricompensa) tende a diminuire o a rimanere costante rispetto alle osservazioni del controllore. Il documento dimostra che per i self-degrading bandits, le politiche pure sono asintoticamente ottimali. Questa classe generalizza i "rested bandits" (dove i bracci inattivi si congelano) e include esempi restless non banali come i canali Gilbert-Elliott non-preemptivi e i modelli Nerlove-Arrow.

3. Metodologia: UCB-NOM

L'articolo propone UCB-NOM (Upper Confidence Bound per Non-Observable Markovian bandits), un algoritmo ottimista ispirato al principio UCB.

Componenti Chiave di UCB-NOM:

1. Stimatore del Guadagno Empirico: L'algoritmo stima il guadagno ($g_a$) di un braccio $a$ mediando le ricompense raccolte quando quel braccio era attivo.
2. Costruzione dell'Indice Ottimista: Per gestire la non-osservabilità degli stati e i vincoli, l'algoritmo costruisce un limite superiore ottimistico $\tilde{g}_a(t)$ per il vero guadagno. Questo indice include:
   • La media empirica della ricompensa.
   • Un bonus di esplorazione (intervallo di confidenza) che tiene conto di:
     • Il numero di pull ($N_a(t)$).
     • Il numero di volte in cui l'algoritmo è passato al braccio $a$ (costo di switch).
     • Lo span del bias ($sp(b_a)$) della catena di Markov del braccio, che quantifica la massima deviazione della funzione di bias.
3. Tecnica del Raddoppio (Doubling Trick): Per soddisfare la proprietà di "cambio raro" richiesta dalle garanzie teoriche, l'algoritmo utilizza una tecnica di raddoppio. Una volta selezionato un braccio, questo viene giocato finché il numero delle sue visite non raddoppia. Ciò assicura che il numero di cambi cresca logaritmicamente con il numero di pull.

Sfide Teoriche Affrontate:

• Non-osservabilità: A differenza di lavori precedenti (ad es. RCA di Tekin & Liu) che si basano sull'osservazione degli stati per innescare cicli di rigenerazione, UCB-NOM non può usare la rigenerazione; invece, limita l'errore utilizzando lo span del bias e il numero di switch.
• Epoche Decisionali Vincolate: L'algoritmo deve tenere conto del ritardo tra le epoche decisionali. L'analisi assume un limite ($C_\tau$) sul tempo atteso fino alla successiva epoca decisionale.

4. Risultati Chiave e Garanzie Teoriche

A. Limiti Inferiori (Impossibilità del Regret Logaritmico)

Il documento stabilisce che, senza una conoscenza preventiva della struttura del bandit, il regret logaritmico ($O(\log T)$) è irraggiungibile per algoritmi consistenti e a cambi rari.

• Teorema 4: Per qualsiasi algoritmo consistente e a cambi rari, il regret atteso scala come $\omega(\log T)$ (super-logaritmico). Ciò è dimostrato costruendo modelli alternativi che sono indistinguibili dal modello reale tramite le sole ricompense, ma che hanno bracci ottimali differenti, costringendo l'algoritmo a estrarre eccessivamente bracci sub-ottimali per distinguerli.

B. Prestazioni di UCB-NOM (Caso Generale)

• Teorema 6: UCB-NOM raggiunge un limite di regret di $O(f(T)^2 \log T)$, dove $f(T)$ è una funzione "proxy dello span" che diverge all'infinito.
• Significato: Scegliendo un $f(T)$ che diverge arbitrariamente lentamente, UCB-NOM può avvicinarsi arbitrariamente al regime ideale logaritmico, eguagliando efficacemente il limite inferiore super-logaritmico.

C. Prestazioni con Conoscenza Preventiva (Bias Span Limitato)

Se l'algoritmo riceve un limite superiore noto $D$ sullo span del bias di tutti i bracci (e sul ritardo dell'epoca decisionale), le prestazioni migliorano significativamente.

• Teorema 8 (Instance-Dependent): Con un proxy dello span fisso $f \equiv D$, UCB-NOM raggiunge un regret instance-dependent di $O(\log T)$.
• Teorema 9 (Worst-Case): Sotto lo stesso assunto di bias span limitato, l'algoritmo raggiunge un regret worst-case di $O(\sqrt{T \log T})$.

D. Tuning e Parametri di Confidenza

Il documento analizza la scelta del parametro di confidenza $\delta(t)$. Suggerisce che essere "sotto-ottimisti" (scegliendo un $\delta(t)$ più piccolo per allargare gli intervalli di confidenza) è preferibile nei contesti markoviani rispetto ai bandit stocastici. Questo perché il rumore negli stimatori markoviani può essere maggiore della varianza della ricompensa suggerita dallo span del bias, richiedendo bonus di esplorazione più ampi per mantenere la proprietà ottimistica.

5. Significato e Contributi

L'articolo rivendica i seguenti contributi:

1. Formulazione del Problema: Formalizza un setting di apprendimento che combina stati non osservabili ed epoche decisionali endogene vincolate, motivato dalle reti di comunicazione (ad es. scheduling di canali non-preemptivi).
2. Self-Degrading Bandits: Identifica e definisce una classe di restless bandits in cui le politiche pure sono ottimali, giustificando l'uso del pure regret come benchmark.
3. Limiti Fondamentali: Dimostra che la non-osservabilità degli stati combinata con le epoche decisionali vincolate impedisce intrinsecamente il regret logaritmico nel caso generale, stabilendo un limite inferiore super-logaritmico.
4. Design dell'Algoritmo: Introduce UCB-NOM, un algoritmo che raggiunge un regret quasi-ottimale senza l'osservazione dello stato. Crucialmente, i limiti del regret non dipendono dal numero di stati ($|S_a|$) delle catene di Markov sottostanti, ma piuttosto dallo span del bias.
5. Approfondimenti Strutturali: Dimostra che con una semplice conoscenza preventiva (un limite sullo span del bias), è possibile recuperare le classiche garanzie di regret logaritmico dei bandit stocastici, suggerendo che la non-osservabilità degli stati è un "leggero inconveniente" nei setting self-degrading, purché siano noti i limiti strutturali.

Gli autori concludono che, sebbene il setting sia più complesso dei normali bandit stocastici, il framework e l'algoritmo proposto forniscono garanzie teoriche robuste senza richiedere le tecniche complesse tipicamente associate ai POMDP (Partially Observable Markov Decision Processes), a patto di aderire al benchmark del pure regret.