Bij het werken met multi-armed bandits schatten traditionele methoden zoals epsilon-greedy en UCB actie-waarden om te bepalen welke actie genomen moet worden. Gradient bandits hanteren echter een andere benadering — zij leren voorkeuren voor acties in plaats van hun waarden te schatten. Deze voorkeuren worden in de loop van de tijd aangepast met behulp van stochastische gradient ascent.

Voorkeuren

In plaats van het bijhouden van actie-waarde schattingen $Q(a)$, houden gradient bandits voorkeurswaarden $H(a)$ bij voor elke actie $a$. Deze voorkeuren worden bijgewerkt met een stochastische gradient ascent-benadering om de verwachte beloningen te maximaliseren. De kans op het kiezen van een actie wordt berekend met een softmax-functie:

waarbij:

• $H_t(a)$ de voorkeur is voor actie $a$ op tijdstip $t$;
• $P(A_t = a)$ de kans is om actie $a$ te selecteren op tijdstip $t$;
• De noemer zorgt ervoor dat de kansen optellen tot 1.

Softmax is een essentiële functie in ML, vaak gebruikt om lijsten van reële getallen om te zetten in lijsten van kansen. Deze functie fungeert als een vloeiende benadering van de $\argmax$-functie, waardoor natuurlijke exploratie mogelijk wordt door acties met een lagere voorkeur een niet-nul kans te geven om geselecteerd te worden.

Update-regel

Na het selecteren van een actie $A_t$ op tijdstip $t$, worden de voorkeurwaarden bijgewerkt volgens de volgende regel:

waarbij:

• $\alpha$ de stapgrootte is;
• $R_t$ de ontvangen beloning is;
• $\bar R_t$ het gemiddelde van de tot nu toe waargenomen beloningen is.

Intuïtie

Bij elke tijdstap worden alle voorkeuren enigszins aangepast. De aanpassing hangt voornamelijk af van de ontvangen beloning en het gemiddelde van de beloningen, en kan als volgt worden uitgelegd:

• Als de ontvangen beloning hoger is dan het gemiddelde, wordt de geselecteerde actie meer geprefereerd en worden andere acties minder geprefereerd;
• Als de ontvangen beloning lager is dan het gemiddelde, neemt de voorkeur voor de geselecteerde actie af, terwijl de voorkeuren voor andere acties toenemen, wat exploratie stimuleert.

Voorbeeldcode

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)

Aanvullende informatie

Gradient bandits hebben verschillende interessante eigenschappen:

• Relativiteit van voorkeuren: de absolute waarden van actievoorkeuren beïnvloeden het selectieproces van acties niet — alleen hun relatieve verschillen zijn van belang. Het verschuiven van alle voorkeuren met dezelfde constante (bijvoorbeeld 100 optellen) resulteert in dezelfde kansverdeling;
• Effect van de baseline in de update-regel: hoewel de updateformule doorgaans het gemiddelde van de beloning als baseline bevat, kan deze waarde worden vervangen door een willekeurige constante die onafhankelijk is van de gekozen actie. De baseline beïnvloedt de snelheid van convergentie, maar verandert de optimale oplossing niet;
• Invloed van de stapgrootte: de stapgrootte dient te worden afgestemd op de betreffende taak. Een kleinere stapgrootte zorgt voor stabieler leren, terwijl een grotere waarde het leerproces versnelt.

Samenvatting

Gradient bandieten bieden een krachtig alternatief voor traditionele bandietalgoritmen door gebruik te maken van voorkeursgebaseerd leren. Hun meest opvallende kenmerk is het vermogen om op natuurlijke wijze exploratie en exploitatie in balans te brengen.