Het upper confidence bound (UCB) algoritme is een populair en effectief benadering voor het oplossen van het multi-armed bandit probleem. Het biedt sterke wiskundige garanties voor snelle convergentie en optimaliseert het exploratieproces.

Ondanks de effectiviteit bij het oplossen van het MAB-probleem, kent het UCB-algoritme enkele opmerkelijke beperkingen die de toepassing ervan binnen bredere reinforcement learning beperken:

• Aanname van stationaire beloningen: het UCB-algoritme gaat ervan uit dat beloningsverdelingen niet veranderen in de tijd;
• Beperkingen op toestands- en actieruimtes: om acties volgens een bepaalde logica te kunnen kiezen, vereist het UCB-algoritme dat elke actie in elke toestand minstens één keer wordt geprobeerd.

Hoewel de eerste beperking kan worden aangepakt door het algoritme licht aan te passen, blijft de tweede beperking een significante uitdaging in veel praktische toepassingen.

Werking

Het UCB-algoritme balanceert exploratie en exploitatie door aan elke actie een betrouwbaarheidsinterval toe te kennen voor de geschatte waarde en de actie te selecteren met de hoogste bovengrens. Deze aanpak zorgt ervoor dat acties met onzekere beloningen worden onderzocht, terwijl de voorkeur wordt gegeven aan acties die optimaal lijken te zijn.

De stappen van het UCB-algoritme zijn identiek aan de stappen van het epsilon-greedy algoritme, met uitzondering van de stap voor het kiezen van een actie. Het UCB-algoritme selecteert een actie $A_t$ op tijdstip $t$ met behulp van de volgende formule:

waarbij:

• $Q_t(a)$ de geschatte beloning is van actie $a$ op tijdstip $t$;
• $N_t(a)$ het aantal keren is dat actie $a$ is geselecteerd tot tijdstip $t$;
• $c > 0$ een instelbare parameter is die de balans tussen exploratie en exploitatie regelt, vergelijkbaar met $\varepsilon$ in het $\varepsilon$-greedy algoritme;
• $\ln$ de natuurlijke logaritmefunctie is;
• $\argmax$ de waarde is van een argument ($a$, in dit geval) die de uitdrukking maximaliseert.

Intuïtie

$\argmax$ kiest de actie die de som van twee delen maximaliseert: de geschatte actiewaarde en een betrouwbaarheidsinterval. Het betrouwbaarheidsinterval wordt geschaald met een factor $c$, waarbij hogere waarden het interval breder maken. Dit betekent dat de agent minder zeker is over de waarde van de actie, wat exploratie stimuleert.

De grootte van dit betrouwbaarheidsinterval hangt af van twee factoren:

1. Tijd: naarmate er meer tijd verstrijkt, wordt de agent minder zeker van de waarde van de actie;
2. Actiefrequentie: hoe vaker een actie wordt gekozen, des te zekerder de agent wordt over de waarde ervan.

Voorbeeldcode

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]

Aanvullende Informatie

Het UCB-algoritme bevat een mechanisme voor exploratie, waarvoor zorgvuldige afstemming van de $c$-hyperparameter noodzakelijk is om effectief te functioneren. De optimale waarde van $c$ verschilt per specifiek probleem. Enkele algemene richtlijnen:

• Hoge variantie in beloningen: een grotere $c$-waarde zorgt voor voldoende exploratie;
• Stabiele beloningen: een kleinere $c$-waarde stelt het algoritme in staat snel te focussen op de optimale actie;
• Gebruikelijke standaardwaarde: een typisch startpunt is $c = 1$, maar vaak is experimentele afstemming nodig voor het beste resultaat.

Samenvatting

Het UCB-algoritme is een krachtig en goed onderbouwd methode voor het balanceren van exploratie en exploitatie in multi-armed bandit problemen. Door acties te selecteren op basis van zowel geschatte beloningen als onzekerheid, zorgt het voor efficiënt leren terwijl spijt wordt geminimaliseerd.