Gradientbanditalgoritm

Vid arbete med 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 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 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 och används ofta 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 stegstorlek;
• $R_t$ är mottagen belöning;
• $\bar R_t$ är genomsnittlig belöning observerad hittills.

Intuition

Vid varje tidsteg justeras alla preferenser något. Förändringen beror främst 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 andra å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 andra å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:

• Relativitet i preferenser: de absoluta värdena för handlingspreferenser påverkar inte urvalsprocessen — endast deras relativa skillnader är viktiga. Om alla preferenser förskjuts med samma konstant (t.ex. genom att addera 100) fås 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 handling. Baslinjen påverkar konvergenshastigheten men ändrar inte den optimala lösningen;
• Steglängdens påverkan: steglängden bör justeras utifrån uppgiften. En mindre steglängd ger stabilare inlärning, medan ett större värde snabbar upp 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.