Når man arbejder med multi-armed banditter, estimerer traditionelle metoder som epsilon-greedy og UCB aktionsværdier for at afgøre, hvilken handling der skal vælges. Gradient banditter anvender dog en anden tilgang — de lærer præferencer for handlinger i stedet for at estimere deres værdier. Disse præferencer justeres over tid ved hjælp af stokastisk gradientopstigning.

Præferencer

I stedet for at opretholde aktionsværdiestimater $Q(a)$, opretholder gradient banditter præferenceværdier $H(a)$ for hver handling $a$. Disse præferencer opdateres ved hjælp af en stokastisk gradientopstigningsmetode for at maksimere forventede belønninger. Sandsynligheden for hver handling beregnes ved hjælp af en softmax-funktion:

hvor:

• $H_t(a)$ er præferencen for handling $a$ på tidspunkt $t$;
• $P(A_t = a)$ er sandsynligheden for at vælge handling $a$ på tidspunkt $t$;
• Nævneren sikrer, at sandsynlighederne summerer til 1.

Softmax er en central funktion i ML, ofte brugt til at konvertere lister af reelle tal til lister af sandsynligheder. Denne funktion fungerer som en glat tilnærmelse til $\argmax$-funktionen, hvilket muliggør naturlig udforskning ved at give handlinger med lavere præference en ikke-nul sandsynlighed for at blive valgt.

Opdateringsregel

Efter valg af en handling $A_t$ på tidspunkt $t$ opdateres præferenceværdierne ved hjælp af følgende regel:

hvor:

• $\alpha$ er skridtstørrelsen;
• $R_t$ er modtaget belønning;
• $\bar R_t$ er gennemsnitlig belønning observeret indtil nu.

Intuition

Ved hvert tidssteg justeres alle præferencer en smule. Justeringen afhænger hovedsageligt af modtaget belønning og gennemsnitlig belønning, og kan forklares således:

• Hvis modtaget belønning er højere end gennemsnittet, bliver den valgte handling mere foretrukken, og andre handlinger bliver mindre foretrukne;
• Hvis modtaget belønning er lavere end gennemsnittet, falder præferencen for den valgte handling, mens præferencerne for de andre handlinger stiger, hvilket fremmer udforskning.

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)

Yderligere information

Gradient banditter har flere interessante egenskaber:

• Præference-relativitet: De absolutte værdier af handlingspræferencer påvirker ikke udvælgelsesprocessen — kun deres relative forskelle har betydning. Hvis alle præferencer forskydes med den samme konstant (f.eks. ved at lægge 100 til), resulterer det i den samme sandsynlighedsfordeling;
• Effekten af baseline i opdateringsreglen: Selvom opdateringsformlen typisk inkluderer den gennemsnitlige belønning som baseline, kan denne værdi erstattes med en hvilken som helst konstant, der er uafhængig af den valgte handling. Baseline påvirker konvergenshastigheden, men ændrer ikke den optimale løsning;
• Indflydelse af skridtlængde: Skridtlængden bør tilpasses den aktuelle opgave. En mindre skridtlængde sikrer mere stabil indlæring, mens en større værdi fremskynder indlæringsprocessen.

Resumé

Gradient banditter tilbyder et kraftfuldt alternativ til traditionelle bandit-algoritmer ved at udnytte præferencebaseret læring. Deres mest interessante egenskab er evnen til naturligt at balancere udforskning og udnyttelse.