Upper confidence bound (UCB) algoritmen er en populær og effektiv metode til at løse multi-armed bandit-problemet. Den har stærke matematiske garantier for hurtig konvergens og optimerer udforskningsprocessen.

På trods af dens effektivitet i løsning af MAB-problemet har UCB-algoritmen nogle bemærkelsesværdige begrænsninger, der indskrænker dens anvendelse i bredere reinforcement learning:

• Antagelse om stationære belønninger: UCB-algoritmen antager, at belønningsfordelinger ikke ændrer sig over tid;
• Begrænsninger på tilstands- og handlingsrum: For overhovedet at kunne vælge handlinger efter en bestemt logik kræver UCB-algoritmen, at hver handling prøves mindst én gang i hver tilstand.

Mens den første begrænsning kan håndteres ved mindre ændringer af algoritmen, forbliver den anden begrænsning en væsentlig udfordring i mange praktiske anvendelser.

Sådan fungerer det

UCB-algoritmen balancerer udforskning og udnyttelse ved at tildele et konfidensinterval til hver handlings estimerede værdi og vælge den handling med højeste øvre grænse. Denne tilgang sikrer, at handlinger med usikre belønninger udforskes, samtidig med at handlinger, der ser ud til at være optimale, foretrækkes.

Trinnene i UCB-algoritmen er identiske med trinnene i epsilon-grådig algoritmen, bortset fra trinnet med valg af handling. UCB-algoritmen vælger en handling $A_t$ på tidspunkt $t$ ved hjælp af følgende formel:

hvor:

• $Q_t(a)$ er den estimerede belønning for handling $a$ på tidspunkt $t$;
• $N_t(a)$ er antallet af gange handling $a$ er blevet valgt indtil tidspunkt $t$;
• $c > 0$ er en justerbar parameter, der styrer balancen mellem udforskning og udnyttelse, svarende til $\varepsilon$ i $\varepsilon$-grådig algoritmen;
• $\ln$ er den naturlige logaritmefunktion;
• $\argmax$ er værdien af et argument ($a$ i dette tilfælde), der maksimerer udtrykket.

Intuition

$\argmax$ vælger den handling, der maksimerer summen af to dele: den estimerede handlingsværdi og et konfidensinterval. Konfidensintervallet skaleres med en faktor $c$, hvor større værdier gør intervallet bredere, hvilket betyder, at agenten er mindre sikker på handlingens værdi, hvilket fremmer udforskning.

Størrelsen af dette konfidensinterval afhænger af to faktorer:

1. Tid: efterhånden som tiden går, bliver agenten mindre sikker på handlingens værdi;
2. Handlingsfrekvens: jo oftere en handling vælges, desto mere sikker bliver agenten på dens værdi.

Eksempelkode

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]

Yderligere information

UCB-algoritmen indeholder en mekanisme til udforskning, som kræver omhyggelig justering af $c$-hyperparameteren for at fungere effektivt. Den optimale $c$-værdi varierer afhængigt af det specifikke problem. Her er nogle generelle retningslinjer:

• Høj varians i belønninger: en større $c$-værdi sikrer tilstrækkelig udforskning;
• Stabile belønninger: en mindre $c$-værdi gør det muligt for algoritmen hurtigt at fokusere på den optimale handling;
• Almindelig standardværdi: et typisk udgangspunkt er $c = 1$, men det kræver ofte eksperimentel justering for bedste resultater.

Resumé

UCB-algoritmen er en effektiv og veldokumenteret metode til at balancere udforskning og udnyttelse i multi-armed bandit-problemer. Ved at vælge handlinger baseret på både estimerede belønninger og usikkerhed sikrer den effektiv læring, samtidig med at fortrydelse minimeres.