Vid hantering av multi-armed banditer uppskattar traditionella metoder som epsilon-girig och UCB aktionsvärden för att avgöra vilken åtgärd som ska väljas. 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 aktionsvärdesuppskattningar $Q(a)$, underhåller gradientbanditer preferensvärden $H(a)$ för varje åtgärd $a$. Dessa preferenser uppdateras med en stokastisk gradientuppstigningsmetod för att maximera förväntad belöning. Sannolikheten för varje åtgärd beräknas med 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 central 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 mottagen belöning;
• $\bar R_t$ är genomsnittlig belöning observerad hittills.

Intuition

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

• Om mottagen belöning är högre än genomsnittet, blir den valda åtgärden mer föredragen och övriga åtgärder blir mindre föredragna;
• Om mottagen 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 spelar roll. 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 vilken konstant som helst som är oberoende av vald åtgärd. Baslinjen påverkar konvergenshastigheten men ändrar inte den optimala lösningen;
• Steglängdens påverkan: 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 utnyttja preferensbaserat lärande. Deras mest intressanta egenskap är förmågan att på ett naturligt sätt balansera utforskning och exploatering.