Quando si affrontano i problemi multi-armed bandit, i metodi tradizionali come epsilon-greedy e UCB stimano i valori delle azioni per decidere quale azione intraprendere. Tuttavia, i gradient bandits adottano un approccio diverso: apprendono le preferenze per le azioni invece di stimarne i valori. Queste preferenze vengono aggiornate nel tempo utilizzando la stochastic gradient ascent.

Preferenze

Invece di mantenere le stime dei valori delle azioni $Q(a)$, i gradient bandits mantengono i valori di preferenza $H(a)$ per ogni azione $a$. Queste preferenze vengono aggiornate utilizzando un approccio di stochastic gradient ascent per massimizzare le ricompense attese. La probabilità di ciascuna azione viene calcolata tramite una funzione softmax:

dove:

• $H_t(a)$ è la preferenza per l'azione $a$ al tempo $t$;
• $P(A_t = a)$ è la probabilità di selezionare l'azione $a$ al tempo $t$;
• Il denominatore garantisce che la somma delle probabilità sia pari a 1.

La softmax è una funzione fondamentale nel ML, comunemente utilizzata per convertire elenchi di numeri reali in elenchi di probabilità. Questa funzione rappresenta un'approssimazione continua della funzione $\argmax$, consentendo un'esplorazione naturale assegnando una probabilità non nulla anche alle azioni con preferenza inferiore.

Regola di aggiornamento

Dopo aver selezionato un'azione $A_t$ al tempo $t$, i valori di preferenza vengono aggiornati secondo la seguente regola:

dove:

• $\alpha$ è il passo di aggiornamento;
• $R_t$ è la ricompensa ricevuta;
• $\bar R_t$ è la ricompensa media osservata fino ad ora.

Intuizione

Ad ogni passo temporale, tutte le preferenze vengono leggermente modificate. La variazione dipende principalmente dalla ricompensa ricevuta e dalla ricompensa media, e può essere spiegata così:

• Se la ricompensa ricevuta è superiore alla media, l'azione selezionata diventa più preferita e le altre azioni diventano meno preferite;
• Se la ricompensa ricevuta è inferiore alla media, la preferenza per l'azione selezionata diminuisce, mentre le preferenze per le altre azioni aumentano, favorendo l'esplorazione.

Codice di esempio

def softmax(x):
  """Simple softmax implementation"""
  return np.exp(x) / np.sum(np.exp(x))

class GradientBanditsAgent:
  def __init__(self, n_actions, alpha):
    """Initialize an agent"""
    self.n_actions = n_actions # Number of available actions
    self.alpha = alpha # alpha
    self.H = np.zeros(n_actions) # Preferences
    self.reward_avg = 0 # Average reward
    self.t = 0 # Time step counter

  def select_action(self):
    """Select an action according to the gradient bandits strategy"""
    # Compute probabilities from preferences with softmax
    probs = softmax(self.H)
    # Choose an action according to the probabilities
    return np.random.choice(self.n_actions, p=probs)

  def update(self, action, reward):
    """Update preferences"""
    # Increase the time step counter
    self.t += 1
    # Update the average reward
    self.reward_avg += reward / self.t

    # Compute probabilities from preferences with softmax
    probs = softmax(self.H) # Getting action probabilities from preferences

    # Update preference values using stochastic gradient ascent
    self.H -= self.alpha * (reward - self.reward_avg) * probs
    self.H[action] += self.alpha * (reward - self.reward_avg)

Informazioni aggiuntive

I gradient bandits presentano diverse proprietà interessanti:

• Relatività delle preferenze: i valori assoluti delle preferenze delle azioni non influenzano il processo di selezione — contano solo le differenze relative. Spostare tutte le preferenze dello stesso valore costante (ad esempio, aggiungendo 100) produce la stessa distribuzione di probabilità;
• Effetto della baseline nella regola di aggiornamento: sebbene la formula di aggiornamento includa tipicamente la ricompensa media come baseline, questo valore può essere sostituito con qualsiasi costante indipendente dall'azione scelta. La baseline influenza la velocità di convergenza ma non modifica la soluzione ottimale;
• Impatto della dimensione del passo: la dimensione del passo deve essere regolata in base al compito. Un valore più piccolo garantisce un apprendimento più stabile, mentre un valore maggiore accelera il processo di apprendimento.

Sommario

I banditi a gradiente offrono un potente alternativa agli algoritmi bandit tradizionali sfruttando l'apprendimento basato sulle preferenze. La loro caratteristica più interessante è la capacità di bilanciare in modo naturale esplorazione e sfruttamento.