Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Oppiskele Ylärajan Luottamusalgoritmi | Moniaseinen Bandiittiongelma
Johdatus Vahvistusoppimiseen
course content

Kurssisisältö

Johdatus Vahvistusoppimiseen

Johdatus Vahvistusoppimiseen

1. RL:n Ydinteoria
2. Moniaseinen Bandiittiongelma
3. Dynaaminen Ohjelmointi
4. Monte Carlo -Menetelmät
5. Aikaisen Eron Oppiminen

book
Ylärajan Luottamusalgoritmi

Upper confidence bound (UCB) -algoritmi on suosittu ja tehokas lähestymistapa multi-armed bandit -ongelman ratkaisemiseen. Sillä on vahvat matemaattiset takuut nopeasta konvergenssista, mikä tehostaa tutkimusprosessia.

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 logiikan mukaan olisi mahdollista, UCB-algoritmi vaatii jokaisen toiminnon kokeilemista jokaisessa tilassa vähintään kerran.

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

Miten se toimii

UCB-algoritmi tasapainottaa tutkimisen ja hyödyntämisen antamalla luottamusvälin jokaisen toiminnon arvioidulle arvolle ja valitsemalla toiminnon, jolla on korkein yläraja. Tämä lähestymistapa varmistaa, että epävarmoja palkkioita sisältäviä toimintoja tutkitaan, mutta suosii toimintoja, jotka vaikuttavat optimaalisilta.

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

At=arg maxa(Qt(a)+clntNt(a))A_t = \argmax_a\Biggl(Q_t(a) + c \sqrt\frac{\ln t}{N_t(a)}\Biggr)

missä:

  • Qt(a)Q_t(a) on toiminnon aa arvioitu tuotto ajanhetkellä tt;
  • Nt(a)N_t(a) on niiden kertojen määrä, jolloin toimintoa aa on valittu ajanhetkeen tt mennessä;
  • c>0c > 0 on säädettävä parametri, joka ohjaa tutkimisen ja hyödyntämisen tasapainoa, vastaavasti kuin ε\varepsilon ε\varepsilon-ahne-algoritmissa;
  • ln\ln on luonnollinen logaritmifunktio;
  • arg max\argmax on sen argumentin (tässä tapauksessa aa) arvo, joka maksimoi lausekkeen.

Intuitio

arg max\argmax valitsee toiminnon, joka maksimoi kahden osan summan: arvioitu toimintojen arvo ja luottamusväli. Luottamusväli skaalataan kertoimella cc, missä suuremmat arvot tekevät välistä leveämmän, eli agentti on epävarmempi toiminnon arvosta, mikä kannustaa tutkimiseen.

Luottamusvälin koko riippuu kahdesta tekijästä:

  1. Aika: ajan kuluessa agentti on epävarmempi 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ätietoja

UCB-algoritmi sisältää tutkimismekanismin, jonka tehokas toiminta edellyttää cc-hyperparametrin huolellista säätämistä. Optimaalinen cc-arvo vaihtelee ongelmakohtaisesti. Tässä yleisiä ohjeita:

  • Suuri palkkioiden varianssi: suurempi cc-arvo varmistaa riittävän tutkimisen;
  • Vakaa palkkio: pienempi cc-arvo mahdollistaa algoritmin nopean keskittymisen optimaaliseen toimintaan;
  • Yleinen oletusarvo: tyypillinen lähtökohta on c=1c = 1, mutta paras tulos edellyttää usein kokeellista säätöä.

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 samalla kun minimoi katumuksen.

question mark

Miten UCB-algoritmi käsittelee tutkimisen ja hyödyntämisen välistä tasapainoa?

Select the correct answer

Oliko kaikki selvää?

Miten voimme parantaa sitä?

Kiitos palautteestasi!

Osio 2. Luku 4

Kysy tekoälyä

expand

Kysy tekoälyä

ChatGPT

Kysy mitä tahansa tai kokeile jotakin ehdotetuista kysymyksistä aloittaaksesi keskustelumme

course content

Kurssisisältö

Johdatus Vahvistusoppimiseen

Johdatus Vahvistusoppimiseen

1. RL:n Ydinteoria
2. Moniaseinen Bandiittiongelma
3. Dynaaminen Ohjelmointi
4. Monte Carlo -Menetelmät
5. Aikaisen Eron Oppiminen

book
Ylärajan Luottamusalgoritmi

Upper confidence bound (UCB) -algoritmi on suosittu ja tehokas lähestymistapa multi-armed bandit -ongelman ratkaisemiseen. Sillä on vahvat matemaattiset takuut nopeasta konvergenssista, mikä tehostaa tutkimusprosessia.

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 logiikan mukaan olisi mahdollista, UCB-algoritmi vaatii jokaisen toiminnon kokeilemista jokaisessa tilassa vähintään kerran.

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

Miten se toimii

UCB-algoritmi tasapainottaa tutkimisen ja hyödyntämisen antamalla luottamusvälin jokaisen toiminnon arvioidulle arvolle ja valitsemalla toiminnon, jolla on korkein yläraja. Tämä lähestymistapa varmistaa, että epävarmoja palkkioita sisältäviä toimintoja tutkitaan, mutta suosii toimintoja, jotka vaikuttavat optimaalisilta.

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

At=arg maxa(Qt(a)+clntNt(a))A_t = \argmax_a\Biggl(Q_t(a) + c \sqrt\frac{\ln t}{N_t(a)}\Biggr)

missä:

  • Qt(a)Q_t(a) on toiminnon aa arvioitu tuotto ajanhetkellä tt;
  • Nt(a)N_t(a) on niiden kertojen määrä, jolloin toimintoa aa on valittu ajanhetkeen tt mennessä;
  • c>0c > 0 on säädettävä parametri, joka ohjaa tutkimisen ja hyödyntämisen tasapainoa, vastaavasti kuin ε\varepsilon ε\varepsilon-ahne-algoritmissa;
  • ln\ln on luonnollinen logaritmifunktio;
  • arg max\argmax on sen argumentin (tässä tapauksessa aa) arvo, joka maksimoi lausekkeen.

Intuitio

arg max\argmax valitsee toiminnon, joka maksimoi kahden osan summan: arvioitu toimintojen arvo ja luottamusväli. Luottamusväli skaalataan kertoimella cc, missä suuremmat arvot tekevät välistä leveämmän, eli agentti on epävarmempi toiminnon arvosta, mikä kannustaa tutkimiseen.

Luottamusvälin koko riippuu kahdesta tekijästä:

  1. Aika: ajan kuluessa agentti on epävarmempi 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ätietoja

UCB-algoritmi sisältää tutkimismekanismin, jonka tehokas toiminta edellyttää cc-hyperparametrin huolellista säätämistä. Optimaalinen cc-arvo vaihtelee ongelmakohtaisesti. Tässä yleisiä ohjeita:

  • Suuri palkkioiden varianssi: suurempi cc-arvo varmistaa riittävän tutkimisen;
  • Vakaa palkkio: pienempi cc-arvo mahdollistaa algoritmin nopean keskittymisen optimaaliseen toimintaan;
  • Yleinen oletusarvo: tyypillinen lähtökohta on c=1c = 1, mutta paras tulos edellyttää usein kokeellista säätöä.

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 samalla kun minimoi katumuksen.

question mark

Miten UCB-algoritmi käsittelee tutkimisen ja hyödyntämisen välistä tasapainoa?

Select the correct answer

Oliko kaikki selvää?

Miten voimme parantaa sitä?

Kiitos palautteestasi!

Osio 2. Luku 4
some-alt