L'algoritmo Upper Confidence Bound (UCB) è un approccio popolare ed efficace per risolvere il problema del multi-armed bandit. Presenta solide garanzie matematiche di rapida convergenza, ottimizzando il processo di esplorazione.

Nonostante la sua efficacia nella risoluzione del problema MAB, l'algoritmo UCB presenta alcune limitazioni rilevanti che ne restringono l'applicazione nell'ambito più ampio del reinforcement learning:

• Assunzione di ricompense stazionarie: l'algoritmo UCB presume che le distribuzioni delle ricompense non cambino nel tempo;
• Vincoli sugli spazi di stati e azioni: per poter iniziare a scegliere le azioni secondo una logica, l'algoritmo UCB richiede di provare ogni azione in ogni stato almeno una volta.

Mentre la prima limitazione può essere affrontata modificando leggermente l'algoritmo, la seconda limitazione rimane una sfida significativa in molte applicazioni pratiche.

Come funziona

L'algoritmo UCB bilancia esplorazione e sfruttamento assegnando un intervallo di confidenza al valore stimato di ciascuna azione e selezionando l'azione con il limite superiore più alto. Questo approccio garantisce che vengano esplorate le azioni con ricompense incerte, privilegiando allo stesso tempo le azioni che sembrano essere ottimali.

I passaggi dell'algoritmo UCB sono identici a quelli dell'algoritmo epsilon-greedy, ad eccezione del passaggio di scelta di un'azione. L'algoritmo UCB seleziona un'azione $A_t$ al passo temporale $t$ utilizzando la seguente formula:

dove:

• $Q_t(a)$ è la ricompensa stimata dell'azione $a$ al tempo $t$;
• $N_t(a)$ è il numero di volte in cui l'azione $a$ è stata selezionata fino al tempo $t$;
• $c > 0$ è un parametro regolabile che controlla l'equilibrio tra esplorazione e sfruttamento, simile a $\varepsilon$ nell'algoritmo $\varepsilon$-greedy;
• $\ln$ è la funzione logaritmo naturale;
• $\argmax$ è il valore dell'argomento ($a$, in questo caso) che massimizza l'espressione.

Intuizione

$\argmax$ sceglie l'azione che massimizza la somma di due parti: il valore stimato dell'azione e un intervallo di confidenza. L'intervallo di confidenza è scalato da un fattore $c$, dove valori maggiori rendono l'intervallo più ampio, il che significa che l'agente è meno sicuro del valore dell'azione, favorendo così l'esplorazione.

La dimensione di questo intervallo di confidenza dipende da due fattori:

1. Tempo: con il passare del tempo, l'agente diventa meno sicuro del valore dell'azione;
2. Frequenza dell'azione: più spesso un'azione viene scelta, più sicuro l'agente diventa del suo valore.

Codice di esempio

class UpperConfidenceBoundAgent:
  def __init__(self, n_actions, confidence):
    """Initialize an agent"""
    self.n_actions = n_actions # Number of available actions
    self.confidence = confidence # c
    self.Q = np.zeros(self.n_actions) # Estimated action values
    self.N = np.zeros(self.n_actions) # Action selection counters
    self.t = 0 # Time step counter

  def select_action(self):
    """Select an action according to the upper confidence bound strategy"""
    # Increase the time step counter
    self.t += 1

    # Each action should be taken at least once
    for action in range(self.n_actions):
      if self.N[action] == 0:
        return action

    # Return the action with highest upper confidence bound
    return np.argmax(self.Q + self.confidence * np.sqrt(np.log(self.t) / self.N))

  def update(self, action, reward):
    """Update the values using sample average estimate"""
    # Increasing the action selection counter
    self.N[action] += 1
    # Updating the estimated action value
    self.Q[action] += (reward - self.Q[action]) / self.N[action]

Informazioni aggiuntive

L'algoritmo UCB integra un meccanismo di esplorazione, che richiede un'attenta regolazione dell'iperparametro $c$ per funzionare in modo efficace. Il valore ottimale di $c$ varia a seconda del problema specifico. Di seguito alcune linee guida generali:

• Elevata varianza nelle ricompense: un valore $c$ più grande garantisce un'esplorazione sufficiente;
• Ricompense stabili: un valore $c$ più piccolo permette all'algoritmo di concentrarsi rapidamente sull'azione ottimale;
• Valore predefinito comune: un punto di partenza tipico è $c = 1$, ma spesso è necessario un aggiustamento sperimentale per ottenere i migliori risultati.

Riepilogo

L'algoritmo UCB è un metodo potente e ben fondato per bilanciare esplorazione ed exploitazione nei problemi multi-armed bandit. Selezionando le azioni in base sia alle ricompense stimate che all'incertezza, garantisce un apprendimento efficiente riducendo al minimo il rimpianto.