Når man arbeider med multi-armede banditter, estimerer tradisjonelle metoder som epsilon-greedy og UCB aksjonsverdier for å avgjøre hvilken handling som skal velges. Gradientbanditter benytter derimot en annen tilnærming — de lærer preferanser for handlinger i stedet for å estimere verdiene deres. Disse preferansene justeres over tid ved hjelp av stokastisk gradientopphøyelse.

Preferanser

I stedet for å opprettholde aksjonsverdiestimater $Q(a)$, opprettholder gradientbanditter preferanseverdier $H(a)$ for hver handling $a$. Disse preferansene oppdateres ved hjelp av en stokastisk gradientopphøyelse-tilnærming for å maksimere forventet belønning. Sannsynligheten for hver handling beregnes ved hjelp av en softmax-funksjon:

hvor:

• $H_t(a)$ er preferansen for handling $a$ på tidspunkt $t$;
• $P(A_t = a)$ er sannsynligheten for å velge handling $a$ på tidspunkt $t$;
• Nevneren sikrer at sannsynlighetene summerer til 1.

Softmax er en sentral funksjon innen maskinlæring, ofte brukt for å konvertere lister av reelle tall til lister av sannsynligheter. Denne funksjonen fungerer som en glatt tilnærming til $\argmax$-funksjonen, og muliggjør naturlig utforskning ved å gi handlinger med lavere preferanse en ikke-null sjanse til å bli valgt.

Oppdateringsregel

Etter å ha valgt en handling $A_t$ ved tid $t$, oppdateres preferanseverdiene ved hjelp av følgende regel:

hvor:

• $\alpha$ er størrelsen på steget;
• $R_t$ er mottatt belønning;
• $\bar R_t$ er gjennomsnittlig belønning observert så langt.

Intuisjon

Ved hvert tidsskritt blir alle preferanser justert noe. Endringen avhenger hovedsakelig av mottatt belønning og gjennomsnittlig belønning, og kan forklares slik:

• Hvis mottatt belønning er høyere enn gjennomsnittet, blir den valgte handlingen mer foretrukket, mens andre handlinger blir mindre foretrukket;
• Hvis mottatt belønning er lavere enn gjennomsnittet, reduseres preferansen for den valgte handlingen, mens preferansene for de andre handlingene øker, noe som oppmuntrer til utforskning.

Eksempelkode

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)

Tilleggsinformasjon

Gradient banditter har flere interessante egenskaper:

• Relativitet i preferanser: De absolutte verdiene til handlingspreferansene påvirker ikke valgprosessen — kun de relative forskjellene har betydning. Å forskyve alle preferanser med samme konstant (for eksempel å legge til 100) gir samme sannsynlighetsfordeling;
• Effekten av baseline i oppdateringsregelen: Selv om oppdateringsformelen vanligvis inkluderer gjennomsnittlig belønning som baseline, kan denne verdien erstattes med en hvilken som helst konstant som er uavhengig av valgt handling. Baseline påvirker konvergenshastigheten, men endrer ikke den optimale løsningen;
• Innvirkning av steglengde: Steglengden bør tilpasses oppgaven. En mindre steglengde gir mer stabil læring, mens en større verdi gir raskere læringsprosess.

Sammendrag

Gradientbanditter gir et kraftig alternativ til tradisjonelle bandittalgoritmer ved å utnytte preferansebasert læring. Deres mest interessante egenskap er evnen til å balansere utforskning og utnyttelse på en naturlig måte.