Ved håndtering av multi-armed banditter estimerer tradisjonelle metoder som epsilon-greedy og UCB aksjonsverdier for å avgjøre hvilken handling som skal velges. Gradientbanditter benytter imidlertid 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øyning.

Preferanser

I stedet for å opprettholde aksjonsverdiestimater $Q(a)$, opprettholder gradientbanditter preferanseverdier $H(a)$ for hver handling $a$. Disse preferansene oppdateres ved hjelp av en tilnærming basert på stokastisk gradientopphøyning 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$ ved tidsskritt $t$;
• $P(A_t = a)$ er sannsynligheten for å velge handling $a$ ved tidsskritt $t$;
• Nevneren sikrer at sannsynlighetene summerer til 1.

Softmax er en sentral funksjon i maskinlæring, ofte brukt til å konvertere lister av reelle tall til lister av sannsynligheter. Denne funksjonen fungerer som en jevn 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 å bruke 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. Justeringen 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:

• Preferanserelativitet: 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 å benytte preferansebasert læring. Deres mest interessante egenskap er evnen til å balansere utforskning og utnyttelse på en naturlig måte.