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 regolate nel tempo utilizzando l'ascesa stocastica del gradiente.

Preferenze

Invece di mantenere le stime dei valori delle azioni $Q(a)$, i gradient bandits mantengono i valori di preferenza $H(a)$ per ciascuna azione $a$. Queste preferenze vengono aggiornate utilizzando un approccio di ascesa stocastica del gradiente 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 alle azioni con preferenza inferiore una probabilità diversa da zero di essere selezionate.

Regola di aggiornamento

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

dove:

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

Intuizione

A 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, mentre 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 da 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 uno più grande accelera il processo di apprendimento.

Sommario

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