Online Prediction of Stochastic Sequences with High Probability Regret Bounds

1. Il Problema

Il paper affronta il classico problema della predizione universale di sequenze stocastiche con un orizzonte temporale finito $T$ noto all'apprendista (learner).

• Scenario: Un processo stocastico $(Z_t)_{t=1}^T$ genera una sequenza di osservazioni secondo una distribuzione di probabilità congiunta $P$ sconosciuta. L'apprendista deve prevedere $Z_t$ basandosi sulle osservazioni passate $Z_1, \dots, Z_{t-1}$, subendo una perdita $\ell(B_t, Z_t)$.
• Obiettivo: Minimizzare il rimpianto (regret), definito come la differenza cumulativa tra la perdita subita dall'apprendista e quella che avrebbe subito una strategia ottimale che conosce $P$ a priori.
• Gap nella letteratura: Esistono risultati consolidati (es. Merhav & Feder, 1998) che forniscono limiti sul rimpianto in valore atteso ($\mathbb{E}[\Delta]$). Tuttavia, per applicazioni critiche dove l'affidabilità è fondamentale (es. controllo del traffico aereo, guida autonoma, diagnosi medica), è necessario sapere che il rimpianto è piccolo con alta probabilità (high probability), non solo in media. Il paper si pone la domanda: è possibile derivare limiti di rimpianto che tendono a zero con alta probabilità per questo scenario specifico?

2. Metodologia e Formulazione del Problema

Gli autori introducono un approccio basato sul problema della "predizione disallineata" (mismatched prediction) come passo intermedio fondamentale.

• Predizione Disallineata: Invece di assumere che l'apprendista conosca $P$, si assume che l'apprendista utilizzi una distribuzione di riferimento $Q$ (che può essere diversa da $P$) per calcolare le sue previsioni ottimali. La strategia dell'apprendista $b_t$ è ottimizzata rispetto a $Q$, mentre i dati reali sono generati da $P$.
• Metriche di Divergenza: L'analisi si basa sulla relazione tra $P$ e $Q$ misurata tramite:
  • Distanza variazionale istantanea e attesa ($V_T$).
  • Divergenza di Kullback-Leibler (KL) istantanea e attesa ($D_T$).
• Strumenti Matematici:
  • Vengono identificate supermartingale appropriate per applicare la disuguaglianza di Azuma-Hoeffding, ottenendo così limiti di concentrazione.
  • Viene utilizzata la disuguaglianza di Markov per trasformare i limiti che coinvolgono variabili casuali (distanza istantanea) in limiti deterministici basati sui valori attesi ($V_T$ o $D(P||Q)$).
  • Viene dimostrato un risultato di impossibilità per stabilire i limiti inferiori teorici sulla dipendenza dalla probabilità di errore $\delta$.

3. Contributi Chiave

Il paper offre tre contributi principali:

1. Limiti di Rimpianto ad Alta Probabilità (Teorema 4):
   Gli autori derivano nuovi limiti per il rimpianto medio per round $\Delta$ che valgono con probabilità almeno $1-\delta$.

   • Per un alfabeto numerabile, il limite di convergenza è dell'ordine di $O(T^{-1/2} \delta^{-1/2})$.
   • Questo completa i risultati esistenti in valore atteso (che sono dell'ordine $O(T^{-1/2})$), fornendo una garanzia di robustezza contro le fluttuazioni casuali.

2. Risultato di Impossibilità (Teorema 5):
   Viene dimostrato che non è possibile migliorare significativamente l'esponente di $\delta$ nel limite (ovvero, non si può passare da $1/\delta$ o $1/\sqrt{\delta}$ a una dipendenza logaritmica come $\log(1/\delta)$) senza fare assunzioni aggiuntive sul processo. Questo prova che la dipendenza polinomiale da $\delta$ è intrinseca al problema generale.

3. Generalità delle Assunzioni:
   A differenza di lavori precedenti che richiedevano spazi finiti, questo approccio utilizza assunzioni tecniche più miti, permettendo di trattare spazi misurabili generali e processi non necessariamente indipendenti e identicamente distribuiti (i.i.d.).

4. Risultati Principali

• Teorema 2 (Versione ad alta probabilità del Teorema 1 di Merhav & Feder):
  Se lo spazio degli stati $Z$ è numerabile, esiste una strategia universale tale che per ogni $\delta \in (0, 1)$:
  $$P\left(\Delta < O\left(\frac{1}{\sqrt{T\delta}}\right)\right) \geq 1 - \delta$$
  Questo si applica a tutte le distribuzioni $P$ calcolabili.

• Convergenza in Scenari Specifici (Tabella 1):
  Applicando i risultati al problema universale (dove $Q$ è una miscela di distribuzioni parametriche $P_\theta$), si ottengono tassi di convergenza specifici:

  • Alfabeto numerabile (Hutter, 2003): $O(T^{-1/2}\delta^{-1/2})$.
  • Processi i.i.d. (Clarke & Barron, 1990): $O((T/\log T)^{-1/2}\delta^{-1/2})$.
  • Catene di Markov a memoria finita (Atteson, 1999): $O((T/\log T)^{-1/2}\delta^{-1/2})$.

• Esperimenti Numerici:
  Gli autori hanno simulato una catena di Markov con memoria $m=3$ e 2 stati. I risultati mostrano che, mentre il rimpianto medio tende a zero rapidamente, i quantili (che rappresentano l'osservazione empirica dei limiti ad alta probabilità) convergono più lentamente, confermando la teoria secondo cui la garanzia ad alta probabilità richiede un fattore aggiuntivo rispetto alla media.

5. Significato e Implicazioni

• Affidabilità Pratica: Il passaggio dai limiti in valore atteso a quelli ad alta probabilità è cruciale per applicazioni reali dove un singolo evento di "mancata previsione" catastrofica (outlier) è inaccettabile.
• Teoria dell'Apprendimento Online: Il lavoro chiarisce i limiti fondamentali della predizione stocastica, dimostrando che il "prezzo" per ottenere garanzie probabilistiche forti è un peggioramento del fattore di scala legato alla probabilità di errore ($\delta$), che non può essere evitato in generale.
• Flessibilità: La metodologia permette di incorporare conoscenze a priori (tramite la scelta di $Q$ e della misura $w$) senza alterare il tasso di convergenza asintotico, influenzando solo le costanti nascoste.

In sintesi, il paper stabilisce che è possibile ottenere garanzie di rimpianto che tendono a zero con alta probabilità per sequenze stocastiche generali, ma che questo comporta un costo inevitabile nella dipendenza dalla probabilità di errore, un risultato che definisce i confini teorici per futuri algoritmi di predizione robusta.