Ylärajan Luottamusalgoritmi

Upper confidence bound (UCB) -algoritmi on suosittu ja tehokas menetelmä multi-armed bandit -ongelman ratkaisemiseen. Sillä on vahvat matemaattiset takeet nopeasta konvergenssista, mikä tehostaa eksploraatioprosessia.

Vaikka UCB-algoritmi on tehokas MAB-ongelman ratkaisussa, sillä on joitakin huomattavia rajoituksia, jotka rajoittavat sen soveltamista laajemmassa vahvistusoppimisessa:

• Oletus stationaarisista palkkioista: UCB-algoritmi olettaa, että palkkioiden jakaumat eivät muutu ajan myötä;
• Rajoitukset tila- ja toimintatiloissa: jotta toimintojen valinta jonkin logiikan mukaan olisi mahdollista, UCB-algoritmi vaatii, että jokaista toimintoa kokeillaan jokaisessa tilassa vähintään kerran.

Vaikka ensimmäiseen rajoitukseen voidaan puuttua muokkaamalla algoritmia hieman, toinen rajoitus on edelleen merkittävä haaste monissa käytännön sovelluksissa.

Miten se toimii

UCB-algoritmi tasapainottaa eksploraation ja eksploitaation antamalla luottamusvälin jokaisen toiminnon arvioidulle arvolle ja valitsemalla toiminnon, jolla on korkein yläraja. Tämä lähestymistapa varmistaa, että epävarmat palkkiot tulevat tutkituiksi samalla kun suositaan toimintoja, jotka vaikuttavat optimaalisilta.

UCB-algoritmin vaiheet ovat identtiset epsilon-ahne-algoritmin vaiheiden kanssa, lukuun ottamatta toiminnon valitsemista. UCB-algoritmi valitsee toiminnon $A_t$ ajanhetkellä $t$ seuraavalla kaavalla:

missä:

• $Q_t(a)$ on toiminnon $a$ arvioitu tuotto ajanhetkellä $t$;
• $N_t(a)$ on niiden kertojen määrä, jolloin toimintoa $a$ on valittu ajanhetkeen $t$ mennessä;
• $c > 0$ on säädettävä parametri, joka ohjaa tutkimisen ja hyväksikäytön tasapainoa, samoin kuin $\varepsilon$ $\varepsilon$-ahne-algoritmissa;
• $\ln$ on luonnollinen logaritmifunktio;
• $\argmax$ on sen argumentin ($a$ tässä tapauksessa) arvo, joka maksimoi lausekkeen.

Intuitio

$\argmax$ valitsee toiminnon, joka maksimoi kahden osan summan: arvioitu toimintopalkkio ja luottamusväli. Luottamusväli skaalataan kertoimella $c$, jossa suuremmat arvot tekevät välistä leveämmän, mikä tarkoittaa, että agentti on epävarmempi toiminnon arvosta, mikä kannustaa tutkimiseen.

Tämän luottamusvälin koko riippuu kahdesta tekijästä:

1. Aika: mitä enemmän aikaa kuluu, sitä epävarmempi agentti on toiminnon arvosta;
2. Toiminnon valintatiheys: mitä useammin toimintoa valitaan, sitä varmempi agentti on sen arvosta.

Esimerkkikoodi

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]

Lisätietoa

UCB-algoritmi sisältää mekanismin tutkimista varten, mikä vaatii $c$-hyperparametrin huolellista säätöä toimiakseen tehokkaasti. Optimaalinen $c$-arvo vaihtelee ongelmakohtaisesti. Tässä joitakin yleisiä ohjeita:

• Suuri palkkioiden vaihtelu: suurempi $c$-arvo varmistaa riittävän tutkimisen;
• Vakaat palkkiot: pienempi $c$-arvo mahdollistaa algoritmin keskittymisen nopeasti optimaaliseen toimintaan;
• Yleinen oletusarvo: tyypillinen aloitusarvo on $c = 1$, mutta se vaatii usein kokeellista säätöä parhaan tuloksen saavuttamiseksi.

Yhteenveto

UCB-algoritmi on tehokas ja hyvin perusteltu menetelmä tutkimisen ja hyödyntämisen tasapainottamiseen multi-armed bandit -ongelmissa. Valitsemalla toimenpiteet sekä arvioitujen tuottojen että epävarmuuden perusteella se mahdollistaa tehokkaan oppimisen ja minimoi katumuksen.