Cover meets Robbins while Betting on Bounded Data: $\ln n$ Regret and Almost Sure $\ln\ln n$ Regret

Titolo: Cover incontra Robbins scommettendo su Dati Limitati: Regret $O(\ln n)$ e Regret $O(\ln \ln n)$ quasi certo

1. Il Problema

Il lavoro si concentra sul problema della scommessa sequenziale (o betting) contro una sequenza di dati $X_1, X_2, \dots$ contenuti nell'intervallo $[0, 1]$.

• Contesto: Si assume che i dati abbiano una media condizionale nota $m_0 \in (0, 1)$.
• Obiettivo: Un scommettitore deve allocare una frazione $\lambda$ della sua ricchezza corrente ad ogni passo temporale. La ricchezza $W_n(\lambda)$ cresce moltiplicativamente in base alla correttezza della scommessa rispetto alla media $m_0$.
• Metrica di Performance: Il Regret (rimpianto) è definito come la differenza tra il logaritmo della ricchezza massima ottenibile a posteriori (usando la strategia $\lambda^*$ ottimale su tutta la sequenza) e il logaritmo della ricchezza ottenuta dalla strategia mista proposta:
  $$R_n = \ln W^*_n - \ln W_n$$
• La Sfida: Esiste un trade-off noto nella letteratura:
  1. Gli algoritmi universali (come quello di Cover) garantiscono un regret worst-case di $O(\ln n)$ su tutti i percorsi, ma non migliorano su percorsi stocastici "tipici".
  2. Strategie basate su prior pesanti vicino allo zero (come quelle di Robbins) possono ottenere un regret molto migliore, $O(\ln \ln n)$, su percorsi stocastici tipici, ma rischiano un regret lineare (catastrofico) su percorsi adversariali o atipici.

Il paper si chiede se sia possibile unire i vantaggi di entrambi gli approcci: garantire un regret $O(\ln n)$ nel caso peggiore (protezione adversarial) e $O(\ln \ln n)$ su quasi tutti i percorsi stocastici, mantenendo al contempo un tasso di crescita asintotico ottimale.

2. Metodologia

Gli autori propongono una strategia di aggregazione convessa (una miscela) di due strategie classiche di scommessa:

1. Miscela Uniforme (Approccio di Cover):

   • Utilizza una distribuzione uniforme come prior su $\lambda \in [-1/m_0, 1/(1-m_0)]$.
   • Proprietà: Garantisce un regret path-wise di $O(\ln n)$ su ogni sequenza di dati, indipendentemente dalla loro natura (stocastica o adversarial). Tuttavia, su percorsi stocastici, non raggiunge il limite inferiore $O(\ln \ln n)$.

2. Miscela di Robbins Modificata:

   • Utilizza una prior specifica (modificata da Robbins) che assegna una massa significativa ai valori di $\lambda$ vicini a zero, decrescendo rapidamente per valori più grandi.
   • Proprietà: Su percorsi stocastici dove la varianza intrinsea cresce, questa strategia ottiene un regret di $O(\ln \ln n)$. Tuttavia, su percorsi dove la media si discosta significativamente da $m_0$ (o in scenari adversariali), può subire un regret lineare.

3. La Strategia Aggregata (Best-of-Both-Worlds):

   • Gli autori definiscono una nuova ricchezza $W_n$ come combinazione convessa delle due ricchezze sopra:
     $$W_n = s_0 W^{(1)}_n + (1-s_0) W^{(2)}_n$$
     dove $W^{(1)}_n$ è la miscela uniforme e $W^{(2)}_n$ è la miscela di Robbins, e $s_0 \in (0,1)$ è una costante di split.
   • L'idea chiave è che il regret della somma è limitato dal minimo dei regret delle singole componenti (più una costante additiva), permettendo di ereditare il comportamento migliore di ciascuna strategia a seconda del percorso.

3. Risultati Principali

A. Limiti di Regret Path-Wise

• Teorema 3.1 (Miscela Uniforme): Conferma che la miscela uniforme ha un regret $R_n \leq \ln(1+n) + 1$ su ogni percorso. Questo implica che se la Legge dei Grandi Numeri (SLLN) viene violata su un percorso, la ricchezza $W_n$ diverge.
• Teorema 4.1 (Miscela di Robbins): Dimostra che per la miscela di Robbins, su un insieme di eventi ad alta probabilità (dove la ricchezza rimane limitata), il regret è limitato da $O(\ln \ln V_n)$, dove $V_n$ è la varianza cumulativa.
• Proposizione 5.1 (Aggregazione): Il risultato centrale. La strategia aggregata soddisfa:
  $$R_n \leq \min\{R^{(1)}_n, R^{(2)}_n\} + C$$
  Di conseguenza:
  • Su tutti i percorsi: Il regret è al massimo $O(\ln n)$ (ereditato dalla componente uniforme).
  • Su quasi tutti i percorsi stocastici (insieme di misura 1): Il regret è $O(\ln \ln n)$ (ereditato dalla componente di Robbins).
  • Questo risolve il trade-off apparente: non è necessario scegliere tra sicurezza worst-case e performance tipica.

B. Tassi di Crescita Asintotica

• Gli autori analizzano il tasso di crescita asintotica ($\liminf \frac{1}{n} \ln W_n$) e quello auto-normalizzato ($\liminf \frac{1}{V_n} \ln W_n$).
• Dimostrano che la strategia aggregata raggiunge il tasso di crescita ottimale (uguale al massimo tra le due componenti) sia nel setting a dati limitati che in quello sub-Gaussian (estendendo i risultati di lavori precedenti).
• In particolare, la miscela di Robbins da sola ha un tasso di crescita sub-ottimale su distribuzioni con media lontana da $m_0$ a causa del regret lineare; l'aggregazione risolve questo problema mantenendo il tasso ottimale.

C. Leggi dei Logaritmi Iterati (LIL) Gioco-Teoriche

• Il lavoro fornisce una versione gioco-teorica della Legge dei Logaritmi Iterati (LIL).
• Il risultato afferma: o la LIL (e la SLLN auto-normalizzata) vale su un percorso specifico, oppure la ricchezza del processo di scommessa aggregato diverge su quel percorso.
• Questo fornisce un "witness" esplicito (la ricchezza stessa) per la violazione delle leggi probabilistiche classiche, collegando la teoria del regret online con la statistica gioco-teorica (Shafer e Vovk).

4. Contributi Chiave

1. Risoluzione del Trade-off: Dimostrazione che è possibile ottenere simultaneamente un regret worst-case $O(\ln n)$ e un regret quasi certo $O(\ln \ln n)$ su dati limitati, un risultato che non era stato esplicitamente proposto o analizzato in precedenza.
2. Generalizzazione: Estensione di questi concetti al setting sub-Gaussian (confrontando con Agrawal e Ramdas [2026]), mostrando che l'aggregazione convessa funziona anche lì per ottenere il meglio di entrambi i mondi.
3. Nuovi Witness per LIL: Costruzione esplicita di un processo di ricchezza che funge da testimone per la SLLN e la LIL auto-normalizzata, fornendo limiti finiti e quantificabili.
4. Analisi dei Tassi di Crescita: Identificazione e risoluzione del trade-off tra regret path-wise e tasso di crescita asintotico, mostrando che l'aggregazione preserva l'ottimalità della crescita.

5. Significato e Implicazioni

• Teoria dell'Apprendimento Online: Il paper offre nuovi strumenti per la progettazione di algoritmi di scommessa e portafoglio che sono robusti contro dati adversariali ma altamente efficienti su dati stocastici.
• Statistica Gioco-Teorica: Rafforza il legame tra i processi di ricchezza (martingale) e le leggi fondamentali della probabilità, offrendo una visione costruttiva (attraverso la ricchezza) di teoremi limite classici.
• Praticità: La strategia proposta è semplice da implementare (una media ponderata di due prior note) ma offre garanzie teoriche molto forti, rendendola un candidato ideale per applicazioni reali in ambienti incerti.

In sintesi, il lavoro dimostra che la combinazione intelligente di strategie "conservative" (Cover) e "aggressive" (Robbins) permette di superare i limiti teorici percepiti, ottenendo adattabilità ottimale sia per dati stocastici che per dati avversariali.