Upper confidence bound (UCB)-algoritmen er en populær og effektiv metode for å løse multi-armed bandit-problemet. Den har sterke matematiske garantier for rask konvergens, og optimaliserer utforskningsprosessen.

Til tross for sin effektivitet i å løse MAB-problemet, har UCB-algoritmen noen merkbare begrensninger som begrenser dens anvendelse innenfor bredere forsterkende læring:

• Antakelse om stasjonære belønninger: UCB-algoritmen antar at belønningsfordelingene ikke endrer seg over tid;
• Begrensninger på tilstands- og handlingsrom: for å kunne velge handlinger etter en viss logikk, krever UCB-algoritmen at hver handling prøves minst én gang i hver tilstand.

Mens den første begrensningen kan håndteres ved å modifisere algoritmen noe, forblir den andre begrensningen en betydelig utfordring i mange praktiske anvendelser.

Hvordan det fungerer

UCB-algoritmen balanserer utforskning og utnyttelse ved å tildele et konfidensintervall til hver handlings estimerte verdi og velge handlingen med høyest øvre grense. Denne tilnærmingen sikrer at handlinger med usikre belønninger blir utforsket, samtidig som handlinger som ser ut til å være optimale foretrekkes.

Stegene i UCB-algoritmen er identiske med stegene i epsilon-grådig algoritme, bortsett fra steget for valg av handling. UCB-algoritmen velger en handling $A_t$ på tidspunkt $t$ ved å bruke følgende formel:

hvor:

• $Q_t(a)$ er estimert belønning for handling $a$ ved tid $t$;
• $N_t(a)$ er antall ganger handling $a$ har blitt valgt frem til tid $t$;
• $c > 0$ er en justerbar parameter som styrer balansen mellom utforskning og utnyttelse, tilsvarende $\varepsilon$ i $\varepsilon$-grådig algoritme;
• $\ln$ er den naturlige logaritmefunksjonen;
• $\argmax$ er verdien av et argument ($a$, i dette tilfellet) som maksimerer uttrykket.

Intuisjon

$\argmax$ velger handlingen som maksimerer summen av to deler: estimert handlingsverdi og et konfidensintervall. Konfidensintervallet skaleres med en faktor $c$, hvor høyere verdier gjør intervallet bredere, noe som betyr at agenten er mindre sikker på handlingens verdi, og dette oppmuntrer til utforskning.

Størrelsen på dette konfidensintervallet avhenger av to faktorer:

1. Tid: etter hvert som mer tid går, blir agenten mindre sikker på handlingens verdi;
2. Handlingsfrekvens: jo oftere en handling velges, desto sikrere blir agenten på dens verdi.

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]

Tilleggsinformasjon

UCB-algoritmen inkluderer en mekanisme for utforskning, som krever nøye justering av $c$-hyperparameteren for å fungere effektivt. Den optimale verdien for $c$ varierer avhengig av det spesifikke problemet. Her er noen generelle retningslinjer:

• Høy varians i belønninger: en større $c$-verdi sikrer tilstrekkelig utforskning;
• Stabile belønninger: en mindre $c$-verdi gjør at algoritmen raskt kan fokusere på den optimale handlingen;
• Vanlig standardverdi: et typisk utgangspunkt er $c = 1$, men det krever ofte eksperimentell justering for best resultat.

Oppsummering

UCB-algoritmen er en kraftig og velbegrunnet metode for å balansere utforskning og utnyttelse i multi-armede bandittproblemer. Ved å velge handlinger basert på både estimerte belønninger og usikkerhet, sikrer den effektiv læring samtidig som angeren minimeres.