Lorsqu'on traite des bandits à plusieurs bras, les méthodes traditionnelles telles que epsilon-greedy et UCB estiment les valeurs d'action pour décider quelle action entreprendre. Cependant, les bandits à gradient adoptent une approche différente — ils apprennent des préférences pour les actions au lieu d'estimer leurs valeurs. Ces préférences sont ajustées au fil du temps à l'aide de l'ascension du gradient stochastique.

Préférences

Au lieu de maintenir des estimations de valeur d'action $Q(a)$, les bandits à gradient maintiennent des valeurs de préférence $H(a)$ pour chaque action $a$. Ces préférences sont mises à jour en utilisant une approche d'ascension du gradient stochastique afin de maximiser les récompenses attendues. La probabilité de chaque action est calculée à l'aide d'une fonction softmax :

où :

• $H_t(a)$ est la préférence pour l'action $a$ à l'instant $t$ ;
• $P(A_t = a)$ est la probabilité de sélectionner l'action $a$ à l'instant $t$ ;
• Le dénominateur garantit que la somme des probabilités est égale à 1.

La fonction softmax est une fonction essentielle en apprentissage automatique, couramment utilisée pour convertir des listes de nombres réels en listes de probabilités. Cette fonction sert d'approximation lisse à la fonction $\argmax$, permettant une exploration naturelle en donnant aux actions de moindre préférence une probabilité non nulle d'être sélectionnées.

Règle de mise à jour

Après avoir sélectionné une action $A_t$ au temps $t$, les valeurs de préférence sont mises à jour selon la règle suivante :

où :

• $\alpha$ est le pas d'apprentissage ;
• $R_t$ est la récompense reçue ;
• $\bar R_t$ est la récompense moyenne observée jusqu'à présent.

Intuition

À chaque étape temporelle, toutes les préférences sont légèrement modifiées. Le changement dépend principalement de la récompense reçue et de la récompense moyenne, et peut s'expliquer ainsi :

• Si la récompense reçue est supérieure à la moyenne, l'action sélectionnée devient plus préférée, tandis que les autres actions deviennent moins préférées ;
• Si la récompense reçue est inférieure à la moyenne, la préférence pour l'action sélectionnée diminue, tandis que les préférences pour les autres actions augmentent, favorisant ainsi l'exploration.

Exemple de code

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)

Informations supplémentaires

Les bandits à gradient possèdent plusieurs propriétés intéressantes :

• Relativité des préférences : les valeurs absolues des préférences d'action n'affectent pas le processus de sélection d'action — seules leurs différences relatives comptent. Déplacer toutes les préférences d'une même constante (par exemple, ajouter 100) aboutit à la même distribution de probabilités ;
• Effet de la base dans la règle de mise à jour : bien que la formule de mise à jour inclue généralement la récompense moyenne comme base, cette valeur peut être remplacée par n'importe quelle constante indépendante de l'action choisie. La base influence la vitesse de convergence mais ne modifie pas la solution optimale ;
• Impact du taux d'apprentissage : le taux d'apprentissage doit être ajusté en fonction de la tâche. Une valeur plus faible assure un apprentissage plus stable, tandis qu'une valeur plus élevée accélère le processus d'apprentissage.

Résumé

Les bandits à gradient offrent une alternative puissante aux algorithmes de bandit traditionnels en exploitant l'apprentissage basé sur les préférences. Leur caractéristique la plus intéressante est leur capacité à équilibrer naturellement l'exploration et l'exploitation.