Inizializzazione ottimistica con algoritmi Greedy

L’inizializzazione ottimistica è una strategia semplice ma efficace per migliorare le prestazioni degli algoritmi greedy nei problemi di multi-armed bandit. L’idea consiste nell’assegnare inizialmente valori elevati alla funzione di valore delle azioni \( Q(a) \), inducendo l’agente a esplorare maggiormente in assenza di conoscenze pregresse.

L’aggiornamento del valore stimato dell’azione avviene tramite una valutazione incrementale di tipo Monte Carlo:

\( \hat{Q}_t(a_t) = \hat{Q}_{t-1} + \frac{1}{N_t(a_t)} ( r_t - \hat{Q}_{t-1} ) \)

dove:

• \( r_t \) è la ricompensa osservata al tempo \( t \);
• \( N_t(a_t) \) rappresenta il numero di volte in cui l’azione \( a_t \) è stata selezionata fino a quel momento;
• l’inizializzazione parte da \( N(a) > 0 \) per garantire una media ben definita.

Questa impostazione incoraggia naturalmente l’esplorazione iniziale, poiché le azioni non ancora testate mantengono un valore elevato e quindi una maggiore probabilità di essere scelte. Se il valore di inizializzazione è calibrato con attenzione, l’algoritmo può raggiungere un buon equilibrio tra esplorazione e sfruttamento, ottenendo prestazioni competitive anche rispetto a strategie più complesse. Diversamente NON garantisce la convergenza a Q*.

Infine, l’approccio si presta a essere valutato secondo nuove metriche di confronto tra algoritmi, che considerano non solo la ricompensa media, ma anche la rapidità di convergenza verso politiche efficaci.

 

Gli algoritmi Probably Approximately Correct (PAC) rappresentano un approccio teorico per analizzare e limitare gli errori commessi da algoritmi di reinforcement learning. Essi si basano sull’idea di garantire che, per la maggior parte dei passi temporali, l’azione scelta sia quasi ottimale, con un alto livello di confidenza.

In modo più formale, un algoritmo PAC prevede che:

• ad ogni passo temporale venga scelta un’azione \( a \);
• il valore dell’azione sia \( \varepsilon \)-ottimale, cioè \( Q(a) \ge Q(a^*) - \varepsilon \);
• questa condizione si verifichi con probabilità almeno \( 1 - \delta \);
• e ciò valga eccetto al più un numero polinomiale di passi temporali

I vincoli PAC risultano polinomiali nei parametri principali del problema, come il numero di azioni, \( \varepsilon \), \( \delta \) e altri fattori legati alla complessità dell’ambiente. Molti algoritmi PAC si fondano su strategie di ottimismo o sul Thompson sampling, due approcci che promuovono un bilanciamento tra esplorazione e sfruttamento.

In particolare, alcuni algoritmi PAC basati sull’ottimismo inizializzano semplicemente tutti i valori delle azioni con un valore elevato, coerente con le specificità del problema, per incentivare una fase iniziale di esplorazione più ampia.

Il confronto tra gli algoritmi greedy e l’inizializzazione ottimistica nei problemi di multi-armed bandit evidenzia come le diverse strategie influenzino il comportamento del regret cumulativo, ovvero la perdita dovuta a scelte subottimali nel tempo.

• Greedy: produce un regret totale lineare, poiché tende a sfruttare eccessivamente le azioni inizialmente più promettenti senza sufficiente esplorazione.
• Costante \( \varepsilon \)-greedy: mantiene un regret lineare, in quanto la probabilità costante di esplorazione non diminuisce con l’esperienza.
• Decrescente \( \varepsilon \)-greedy: può ottenere un regret sublineare se il tasso di decadimento di \( \varepsilon \) è scelto correttamente, ma questo richiede la conoscenza preliminare dei gaps tra le azioni, che di norma sono ignoti.
• Inizializzazione ottimistica: garantisce un regret sublineare se i valori iniziali vengono impostati in modo sufficientemente ottimistico; altrimenti, il comportamento resta lineare come nei metodi greedy.

In sintesi, le strategie che incoraggiano l’esplorazione — tramite valori iniziali elevati o parametri \( \varepsilon \) decrescenti — tendono a ottenere risultati più efficienti nel lungo periodo, riducendo la crescita del regret rispetto ai metodi puramente deterministici.

Approccio Bayesiano

L’inferenza bayesiana fornisce un quadro probabilistico per aggiornare la conoscenza sui parametri ignoti di un modello, come nel caso dei problemi di multi-armed bandit. Secondo la visione bayesiana, si parte da una distribuzione prior che rappresenta la conoscenza iniziale (o l’incertezza) sui parametri sconosciuti, in questo caso la distribuzione delle ricompense associati a ciascun braccio.

Quando vengono raccolte nuove osservazioni, cioè dati sulle ricompense ottenuti, l’incertezza sui parametri viene aggiornata applicando la regola di Bayes. Per esempio, se il premio del braccio \( i \) dipende da un parametro \( \phi_i \), e la distribuzione a priori di tale parametro è \( p(\phi_i) \), allora, dopo aver scelto il braccio e osservato un premio \( r_{i1} \), si può aggiornare la stima di \( \phi_i \) secondo:

\( p(\phi_i \mid r_{i1}) = \frac{p(r_{i1} \mid \phi_i)p(\phi_i)}{p(r_{i1})} = \frac{p(r_{i1} \mid \phi_i)p(\phi_i)}{\int_{\phi_i} p(r_{i1} \mid \phi_i)p(\phi_i)d\phi_i} \)

Questo meccanismo consente di combinare in modo coerente le informazioni precedenti (il prior) con le nuove evidenze sperimentali (i dati osservati), ottenendo una distribuzione posterior che riflette la conoscenza aggiornata sul parametro.

In generale il calcolo di questo aggiornamento può essere complesso senza informazioni sulla struttura della distribuzione a priori e dei dati, in qualche caso può essere sviluppato analiticamente.

Se la rappresentazione parametrica delle distribuzioni a priori e posteriori è la stessa, si definiscono coniugate. 

Probability matching e Thompson Sampling

Il probability matching è una strategia di decisione nei problemi di multi-armed bandit basata su un’interpretazione probabilistica delle azioni ottimali. Si assume di avere una distribuzione parametrica delle ricompense per ciascun braccio, e la scelta dell’azione avviene proporzionalmente alla probabilità che essa sia effettivamente quella ottimale.

Formalmente, la politica può essere espressa come:

\( \pi(a \mid h_t) = \mathbb{P}[Q(a) > Q(a'), \, \forall a' \ne a \mid h_t] \)

Questo approccio risulta spesso ottimistico di fronte all’incertezza: le azioni meno esplorate, per le quali si dispone di meno informazioni, possono avere una probabilità maggiore di essere considerate ottimali, incentivando così l’esplorazione.

Tuttavia, calcolare analiticamente la probabilità che un’azione sia ottimale a partire dalla distribuzione posterior può essere complesso. Sorprendentemente, esiste però un metodo semplice e pratico che implementa efficacemente il probability matching: il Thompson Sampling, che campiona le azioni in base alle loro distribuzioni di probabilità a posteriori, bilanciando in modo naturale esplorazione e sfruttamento.

Il Thompson Sampling è una strategia bayesiana di esplorazione per i problemi di multi-armed bandit, che implementa in modo naturale il principio del probability matching. L’idea di base è quella di mantenere una distribuzione di probabilità sui possibili valori delle ricompense per ciascun braccio, aggiornata dinamicamente in base alle osservazioni raccolte.

L’algoritmo procede come segue:

• Si inizializza una distribuzione prior per ogni braccio \( a \), indicata come \( p(\mathcal{R}_a) \).
• Ad ogni iterazione:
  • Per ciascun braccio si campiona una distribuzione dei premi \( \mathcal{R}_a \) dal posterior.
  • Si calcola la funzione di valore d’azione \( Q(a) = \mathbb{E}[\mathcal{R}_a] \).
  • Si seleziona l’azione ottimale \( a_t = \arg\max_{a \in \mathcal{A}} Q(a) \).
  • Si osserva il premio \( r \) corrispondente.
  • Si aggiorna la distribuzione posterior \( p(\mathcal{R}_a) \) utilizzando la regola di Bayes.

Il Thompson Sampling bilancia automaticamente esplorazione e sfruttamento: le azioni con alta incertezza vengono esplorate più spesso, ma col tempo la politica converge verso quella ottimale man mano che la conoscenza sui premi diventa più accurata.