Upper confidence bound (UCB)-algoritmen är en populär och effektiv metod för att lösa multi-armed bandit-problemet. Den har starka matematiska garantier för snabb konvergens och optimerar utforskningsprocessen.

Trots sin effektivitet vid lösning av MAB-problemet har UCB-algoritmen vissa anmärkningsvärda begränsningar som begränsar dess användning inom bredare förstärkningsinlärning:

• Antagande om stationära belöningar: UCB-algoritmen antar att belöningsfördelningarna inte förändras över tid;
• Begränsningar i tillstånds- och handlingsutrymmen: för att ens börja välja handlingar enligt någon logik kräver UCB-algoritmen att varje handling i varje tillstånd prövas minst en gång.

Medan den första begränsningen kan hanteras genom att modifiera algoritmen något, kvarstår den andra begränsningen som en betydande utmaning i många praktiska tillämpningar.

Så fungerar det

UCB-algoritmen balanserar utforskning och exploatering genom att tilldela ett konfidensintervall till varje handlings uppskattade värde och väljer den handling med högst övre gräns. Detta tillvägagångssätt säkerställer att handlingar med osäkra belöningar utforskas samtidigt som handlingar som verkar vara optimala prioriteras.

Stegen i UCB-algoritmen är identiska med stegen i epsilon-girig algoritm, förutom steget för val av handling. UCB-algoritmen väljer en handling $A_t$ vid tidpunkt $t$ med hjälp av följande formel:

Där:

• $Q_t(a)$ är den uppskattade belöningen för handling $a$ vid tidpunkt $t$;
• $N_t(a)$ är antalet gånger handling $a$ har valts fram till tidpunkt $t$;
• $c > 0$ är en justerbar parameter som styr balansen mellan utforskning och exploatering, liknande $\varepsilon$ i $\varepsilon$-girig algoritm;
• $\ln$ är den naturliga logaritmfunktionen;
• $\argmax$ är det värde på argumentet ($a$ i detta fall) som maximerar uttrycket.

Intuition

$\argmax$ väljer den handling som maximerar summan av två delar: det uppskattade handlingsvärdet och ett konfidensintervall. Konfidensintervallet skalas med en faktor $c$, där större värden gör intervallet bredare, vilket innebär att agenten är mindre säker på handlingens värde, vilket uppmuntrar utforskning.

Storleken på detta konfidensintervall beror på två faktorer:

1. Tid: ju mer tid som går, desto mindre säker blir agenten på handlingens värde;
2. Handlingsfrekvens: ju oftare en handling väljs, desto säkrare blir agenten på dess värde.

Exempelkod

class UpperConfidenceBoundAgent:
  def __init__(self, n_actions, confidence):
    """Initialize an agent"""
    self.n_actions = n_actions # Number of available actions
    self.confidence = confidence # c
    self.Q = np.zeros(self.n_actions) # Estimated action values
    self.N = np.zeros(self.n_actions) # Action selection counters
    self.t = 0 # Time step counter

  def select_action(self):
    """Select an action according to the upper confidence bound strategy"""
    # Increase the time step counter
    self.t += 1

    # Each action should be taken at least once
    for action in range(self.n_actions):
      if self.N[action] == 0:
        return action

    # Return the action with highest upper confidence bound
    return np.argmax(self.Q + self.confidence * np.sqrt(np.log(self.t) / self.N))

  def update(self, action, reward):
    """Update the values using sample average estimate"""
    # Increasing the action selection counter
    self.N[action] += 1
    # Updating the estimated action value
    self.Q[action] += (reward - self.Q[action]) / self.N[action]

Ytterligare information

UCB-algoritmen innehåller en mekanism för utforskning, vilket kräver noggrann justering av hyperparametern $c$ för att fungera effektivt. Det optimala värdet på $c$ varierar beroende på det specifika problemet. Här är några allmänna riktlinjer:

• Hög varians i belöningar: ett större $c$-värde säkerställer tillräcklig utforskning;
• Stabila belöningar: ett mindre $c$-värde gör att algoritmen snabbt kan fokusera på den optimala åtgärden;
• Vanlig standard: en typisk startpunkt är $c = 1$, men det krävs ofta experimentell justering för bästa resultat.

Sammanfattning

UCB-algoritmen är en kraftfull och välgrundad metod för att balansera utforskning och exploatering i multi-armed bandit-problem. Genom att välja åtgärder baserat på både uppskattade belöningar och osäkerhet möjliggör den effektiv inlärning samtidigt som ångern minimeras.