Vid hantering av multi-armed bandits uppskattar traditionella metoder som epsilon-girig och UCB aktionsvärden för att avgöra vilken åtgärd som ska vidtas. Gradientbanditer använder dock en annan metod — de lär sig preferenser för åtgärder istället för att uppskatta deras värden. Dessa preferenser justeras över tid med hjälp av stokastisk gradientuppstigning.

Preferenser

Istället för att underhålla uppskattningar av aktionsvärden $Q(a)$, underhåller gradientbanditer preferensvärden $H(a)$ för varje åtgärd $a$. Dessa preferenser uppdateras med en stokastisk gradientuppstigning för att maximera förväntade belöningar. Sannolikheten för varje åtgärd beräknas med hjälp av en softmax-funktion:

där:

• $H_t(a)$ är preferensen för åtgärd $a$ vid tidpunkt $t$;
• $P(A_t = a)$ är sannolikheten att välja åtgärd $a$ vid tidpunkt $t$;
• Nämnaren säkerställer att sannolikheterna summerar till 1.

Softmax är en viktig funktion inom ML, ofta använd för att omvandla listor av reella tal till listor av sannolikheter. Denna funktion fungerar som en mjuk approximation av $\argmax$-funktionen, vilket möjliggör naturlig utforskning genom att ge åtgärder med lägre preferens en icke-noll chans att väljas.

Uppdateringsregel

Efter att en åtgärd $A_t$ har valts vid tidpunkt $t$ uppdateras preferensvärdena enligt följande regel:

där:

• $\alpha$ är stegstorleken;
• $R_t$ är erhållen belöning;
• $\bar R_t$ är genomsnittlig belöning observerad hittills.

Intuition

Vid varje tidssteg justeras alla preferenser något. Förändringen beror huvudsakligen på erhållen belöning och genomsnittlig belöning, och kan förklaras så här:

• Om erhållen belöning är högre än genomsnittet blir den valda åtgärden mer föredragen, medan andra åtgärder blir mindre föredragna;
• Om erhållen belöning är lägre än genomsnittet minskar preferensen för den valda åtgärden, medan preferenserna för övriga åtgärder ökar, vilket uppmuntrar utforskning.

Exempelkod

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)

Ytterligare information

Gradientbanditer har flera intressanta egenskaper:

• Preferensrelativitet: de absoluta värdena för åtgärdspreferenser påverkar inte urvalsprocessen — endast deras relativa skillnader är avgörande. Om alla preferenser förskjuts med samma konstant (t.ex. genom att addera 100) erhålls samma sannolikhetsfördelning;
• Effekten av baslinjen i uppdateringsregeln: även om uppdateringsformeln vanligtvis inkluderar den genomsnittliga belöningen som baslinje, kan detta värde ersättas med en godtycklig konstant som är oberoende av vald åtgärd. Baslinjen påverkar konvergenshastigheten men ändrar inte den optimala lösningen;
• Påverkan av steglängden: steglängden bör justeras utifrån aktuell uppgift. En mindre steglängd ger stabilare inlärning, medan ett större värde påskyndar inlärningsprocessen.

Sammanfattning

Gradientbanditer erbjuder ett kraftfullt alternativ till traditionella banditalgoritmer genom att använda preferensbaserat lärande. Deras mest intressanta egenskap är förmågan att på ett naturligt sätt balansera utforskning och exploatering.