Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Impara Algoritmo dei Banditi a Gradiente | Problema del Multi-Armed Bandit
Introduzione al Reinforcement Learning
course content

Contenuti del Corso

Introduzione al Reinforcement Learning

Introduzione al Reinforcement Learning

1. Teoria Fondamentale dell'RL
2. Problema del Multi-Armed Bandit
3. Programmazione Dinamica
4. Metodi Monte Carlo
5. Apprendimento a Differenza Temporale

book
Algoritmo dei Banditi a Gradiente

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 la stochastic gradient ascent.

Preferenze

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

P(At=a)=eHt(a)b=1neHt(b)=πt(a)P(A_t = a) = \frac{e^{H_t(a)}}{\sum_{b=1}^n e^{H_t(b)}} = \pi_t(a)

dove:

  • Ht(a)H_t(a) è la preferenza per l'azione aa al tempo tt;
  • P(At=a)P(A_t = a) è la probabilità di selezionare l'azione aa al tempo tt;
  • 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 arg max\argmax, consentendo una esplorazione naturale dando alle azioni con preferenza inferiore una probabilità diversa da zero di essere selezionate.

Regola di aggiornamento

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

Ht+1(At)Ht(At)+α(RtRˉt)(1π(At))Ht+1(a)Ht(a)α(RtRˉt)π(a)aAt\begin{aligned} &H_{t+1}(A_t) \gets H_t(A_t) + \alpha (R_t - \bar R_t)(1 - \pi(A_t))\\ &H_{t+1}(a) \gets H_t(a) - \alpha (R_t - \bar R_t)\pi(a) \qquad \forall a \ne A_t \end{aligned}

dove:

  • α\alpha è la dimensione del passo;
  • RtR_t è la ricompensa ricevuta;
  • Rˉt\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 dell'azione selezionata diminuisce, mentre le preferenze delle 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 del 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. Il 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 una valida alternativa 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.

question mark

Qual è il principale vantaggio nell’utilizzo dei banditi a gradiente rispetto agli algoritmi bandit tradizionali?

Select the correct answer

Tutto è chiaro?

Come possiamo migliorarlo?

Grazie per i tuoi commenti!

Sezione 2. Capitolo 5

Chieda ad AI

expand

Chieda ad AI

ChatGPT

Chieda pure quello che desidera o provi una delle domande suggerite per iniziare la nostra conversazione

course content

Contenuti del Corso

Introduzione al Reinforcement Learning

Introduzione al Reinforcement Learning

1. Teoria Fondamentale dell'RL
2. Problema del Multi-Armed Bandit
3. Programmazione Dinamica
4. Metodi Monte Carlo
5. Apprendimento a Differenza Temporale

book
Algoritmo dei Banditi a Gradiente

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 la stochastic gradient ascent.

Preferenze

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

P(At=a)=eHt(a)b=1neHt(b)=πt(a)P(A_t = a) = \frac{e^{H_t(a)}}{\sum_{b=1}^n e^{H_t(b)}} = \pi_t(a)

dove:

  • Ht(a)H_t(a) è la preferenza per l'azione aa al tempo tt;
  • P(At=a)P(A_t = a) è la probabilità di selezionare l'azione aa al tempo tt;
  • 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 arg max\argmax, consentendo una esplorazione naturale dando alle azioni con preferenza inferiore una probabilità diversa da zero di essere selezionate.

Regola di aggiornamento

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

Ht+1(At)Ht(At)+α(RtRˉt)(1π(At))Ht+1(a)Ht(a)α(RtRˉt)π(a)aAt\begin{aligned} &H_{t+1}(A_t) \gets H_t(A_t) + \alpha (R_t - \bar R_t)(1 - \pi(A_t))\\ &H_{t+1}(a) \gets H_t(a) - \alpha (R_t - \bar R_t)\pi(a) \qquad \forall a \ne A_t \end{aligned}

dove:

  • α\alpha è la dimensione del passo;
  • RtR_t è la ricompensa ricevuta;
  • Rˉt\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 dell'azione selezionata diminuisce, mentre le preferenze delle 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 del 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. Il 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 una valida alternativa 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.

question mark

Qual è il principale vantaggio nell’utilizzo dei banditi a gradiente rispetto agli algoritmi bandit tradizionali?

Select the correct answer

Tutto è chiaro?

Come possiamo migliorarlo?

Grazie per i tuoi commenti!

Sezione 2. Capitolo 5
some-alt