Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Oppiskele Gradienttinen Bandiittialgoritmi | 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
Gradienttinen Bandiittialgoritmi

Moniasemaisten bandiittien yhteydessä perinteiset menetelmät, kuten epsilon-ahne ja UCB, arvioivat toimintojen arvoja päättääkseen, mitä toimintoa käyttää. Gradienttibanditit lähestyvät asiaa kuitenkin eri tavalla — ne oppivat toimintojen mieltymykset arvojen arvioimisen sijaan. Näitä mieltymyksiä säädetään ajan myötä käyttäen stokastista gradienttinousua.

Mieltymykset

Sen sijaan, että ylläpidettäisiin toimintojen arviota Q(a)Q(a), gradienttibanditit ylläpitävät mieltymysarvoja H(a)H(a) jokaiselle toiminnolle aa. Näitä mieltymyksiä päivitetään stokastisen gradienttinousun avulla odotettujen palkkioiden maksimoimiseksi. Jokaisen toiminnon todennäköisyys lasketaan softmax-funktion avulla:

P(At=a)=eHt(a)b=1neHt(b)=πt(a)P(A_t = a) = \frac{e^{H_t(a)}}{\sum_{b=1}^n e^{H_t(b)}} = \pi_t(a)

missä:

  • Ht(a)H_t(a) on toiminnon aa mieltymys ajanhetkellä tt;
  • P(At=a)P(A_t = a) on todennäköisyys valita toiminto aa ajanhetkellä tt;
  • Nimittäjä varmistaa, että todennäköisyydet summautuvat yhteen.

Softmax on keskeinen funktio koneoppimisessa, ja sitä käytetään yleisesti muuttamaan reaalilukujen listoja todennäköisyyksien listoiksi. Tämä funktio toimii pehmeänä approksimaationa arg max\argmax-funktiolle, mahdollistaen luontevan tutkimisen antamalla matalamman mieltymyksen toiminnoille ei-nolla todennäköisyyden tulla valituksi.

Päivityssääntö

Kun toiminto AtA_t valitaan ajanhetkellä tt, preferenssiarvot päivitetään seuraavan säännön mukaisesti:

Ht+1(At)Ht(At)+α(RtRˉt)(1π(At))Ht+1(a)Ht(a)α(RtRˉt)π(a)aAt\begin{aligned} &H_{t+1}(A_t) \gets H_t(A_t) + \alpha (R_t - \bar R_t)(1 - \pi(A_t))\\ &H_{t+1}(a) \gets H_t(a) - \alpha (R_t - \bar R_t)\pi(a) \qquad \forall a \ne A_t \end{aligned}

missä:

  • α\alpha on askelkokonaisuus;
  • RtR_t on saatu palkkio;
  • Rˉt\bar R_t on tähän mennessä havaittu keskimääräinen palkkio.

Intuitio

Jokaisella aikavälillä kaikkia preferenssejä siirretään hieman. Siirto riippuu pääasiassa saatu palkkio ja keskimääräinen palkkio -arvoista, ja se voidaan selittää seuraavasti:

  • Jos saatu palkkio on suurempi kuin keskimääräinen, valitusta toiminnosta tulee suositumpi ja muiden toimintojen suosio vähenee;
  • Jos saatu palkkio on pienempi kuin keskimääräinen, valitun toiminnon preferenssi vähenee, kun taas muiden toimintojen preferenssit kasvavat, mikä kannustaa tutkimiseen.

Esimerkkikoodi

def softmax(x):
  """Simple softmax implementation"""
  return np.exp(x) / np.sum(np.exp(x))

class GradientBanditsAgent:
  def __init__(self, n_actions, alpha):
    """Initialize an agent"""
    self.n_actions = n_actions # Number of available actions
    self.alpha = alpha # alpha
    self.H = np.zeros(n_actions) # Preferences
    self.reward_avg = 0 # Average reward
    self.t = 0 # Time step counter

  def select_action(self):
    """Select an action according to the gradient bandits strategy"""
    # Compute probabilities from preferences with softmax
    probs = softmax(self.H)
    # Choose an action according to the probabilities
    return np.random.choice(self.n_actions, p=probs)

  def update(self, action, reward):
    """Update preferences"""
    # Increase the time step counter
    self.t += 1
    # Update the average reward
    self.reward_avg += reward / self.t

    # Compute probabilities from preferences with softmax
    probs = softmax(self.H) # Getting action probabilities from preferences

    # Update preference values using stochastic gradient ascent
    self.H -= self.alpha * (reward - self.reward_avg) * probs
    self.H[action] += self.alpha * (reward - self.reward_avg)

Lisätietoja

Gradienttibanditeilla on useita mielenkiintoisia ominaisuuksia:

  • Preferenssien suhteellisuus: toimintojen preferenssien absoluuttisilla arvoilla ei ole vaikutusta toimintojen valintaan — vain niiden suhteellisilla eroilla on merkitystä. Kaikkien preferenssien siirtäminen samalla vakiolla (esim. lisäämällä 100) johtaa samaan todennäköisyysjakaumaan;
  • Vertailuarvon vaikutus päivityssäännössä: vaikka päivityskaavassa käytetään yleensä keskimääräistä palkkiota vertailuarvona, tämän arvon voi korvata millä tahansa vakiolla, joka ei riipu valitusta toiminnosta. Vertailuarvo vaikuttaa oppimisen nopeuteen, mutta ei muuta optimaalista ratkaisua;
  • Askelkoon vaikutus: askelkoon arvo kannattaa säätää tehtävän mukaan. Pienempi askelkoko takaa vakaamman oppimisen, kun taas suurempi arvo nopeuttaa oppimisprosessia.

Yhteenveto

Gradienttibanditit tarjoavat tehokkaan vaihtoehdon perinteisille bandittialgoritmeille hyödyntämällä preferenssipohjaista oppimista. Niiden merkittävin ominaisuus on kyky tasapainottaa luonnollisesti tutkimista ja hyväksikäyttöä.

question mark

Mikä on gradienttibandittien tärkein etu perinteisiin bandittialgoritmeihin verrattuna?

Select the correct answer

Oliko kaikki selvää?

Miten voimme parantaa sitä?

Kiitos palautteestasi!

Osio 2. Luku 5

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
Gradienttinen Bandiittialgoritmi

Moniasemaisten bandiittien yhteydessä perinteiset menetelmät, kuten epsilon-ahne ja UCB, arvioivat toimintojen arvoja päättääkseen, mitä toimintoa käyttää. Gradienttibanditit lähestyvät asiaa kuitenkin eri tavalla — ne oppivat toimintojen mieltymykset arvojen arvioimisen sijaan. Näitä mieltymyksiä säädetään ajan myötä käyttäen stokastista gradienttinousua.

Mieltymykset

Sen sijaan, että ylläpidettäisiin toimintojen arviota Q(a)Q(a), gradienttibanditit ylläpitävät mieltymysarvoja H(a)H(a) jokaiselle toiminnolle aa. Näitä mieltymyksiä päivitetään stokastisen gradienttinousun avulla odotettujen palkkioiden maksimoimiseksi. Jokaisen toiminnon todennäköisyys lasketaan softmax-funktion avulla:

P(At=a)=eHt(a)b=1neHt(b)=πt(a)P(A_t = a) = \frac{e^{H_t(a)}}{\sum_{b=1}^n e^{H_t(b)}} = \pi_t(a)

missä:

  • Ht(a)H_t(a) on toiminnon aa mieltymys ajanhetkellä tt;
  • P(At=a)P(A_t = a) on todennäköisyys valita toiminto aa ajanhetkellä tt;
  • Nimittäjä varmistaa, että todennäköisyydet summautuvat yhteen.

Softmax on keskeinen funktio koneoppimisessa, ja sitä käytetään yleisesti muuttamaan reaalilukujen listoja todennäköisyyksien listoiksi. Tämä funktio toimii pehmeänä approksimaationa arg max\argmax-funktiolle, mahdollistaen luontevan tutkimisen antamalla matalamman mieltymyksen toiminnoille ei-nolla todennäköisyyden tulla valituksi.

Päivityssääntö

Kun toiminto AtA_t valitaan ajanhetkellä tt, preferenssiarvot päivitetään seuraavan säännön mukaisesti:

Ht+1(At)Ht(At)+α(RtRˉt)(1π(At))Ht+1(a)Ht(a)α(RtRˉt)π(a)aAt\begin{aligned} &H_{t+1}(A_t) \gets H_t(A_t) + \alpha (R_t - \bar R_t)(1 - \pi(A_t))\\ &H_{t+1}(a) \gets H_t(a) - \alpha (R_t - \bar R_t)\pi(a) \qquad \forall a \ne A_t \end{aligned}

missä:

  • α\alpha on askelkokonaisuus;
  • RtR_t on saatu palkkio;
  • Rˉt\bar R_t on tähän mennessä havaittu keskimääräinen palkkio.

Intuitio

Jokaisella aikavälillä kaikkia preferenssejä siirretään hieman. Siirto riippuu pääasiassa saatu palkkio ja keskimääräinen palkkio -arvoista, ja se voidaan selittää seuraavasti:

  • Jos saatu palkkio on suurempi kuin keskimääräinen, valitusta toiminnosta tulee suositumpi ja muiden toimintojen suosio vähenee;
  • Jos saatu palkkio on pienempi kuin keskimääräinen, valitun toiminnon preferenssi vähenee, kun taas muiden toimintojen preferenssit kasvavat, mikä kannustaa tutkimiseen.

Esimerkkikoodi

def softmax(x):
  """Simple softmax implementation"""
  return np.exp(x) / np.sum(np.exp(x))

class GradientBanditsAgent:
  def __init__(self, n_actions, alpha):
    """Initialize an agent"""
    self.n_actions = n_actions # Number of available actions
    self.alpha = alpha # alpha
    self.H = np.zeros(n_actions) # Preferences
    self.reward_avg = 0 # Average reward
    self.t = 0 # Time step counter

  def select_action(self):
    """Select an action according to the gradient bandits strategy"""
    # Compute probabilities from preferences with softmax
    probs = softmax(self.H)
    # Choose an action according to the probabilities
    return np.random.choice(self.n_actions, p=probs)

  def update(self, action, reward):
    """Update preferences"""
    # Increase the time step counter
    self.t += 1
    # Update the average reward
    self.reward_avg += reward / self.t

    # Compute probabilities from preferences with softmax
    probs = softmax(self.H) # Getting action probabilities from preferences

    # Update preference values using stochastic gradient ascent
    self.H -= self.alpha * (reward - self.reward_avg) * probs
    self.H[action] += self.alpha * (reward - self.reward_avg)

Lisätietoja

Gradienttibanditeilla on useita mielenkiintoisia ominaisuuksia:

  • Preferenssien suhteellisuus: toimintojen preferenssien absoluuttisilla arvoilla ei ole vaikutusta toimintojen valintaan — vain niiden suhteellisilla eroilla on merkitystä. Kaikkien preferenssien siirtäminen samalla vakiolla (esim. lisäämällä 100) johtaa samaan todennäköisyysjakaumaan;
  • Vertailuarvon vaikutus päivityssäännössä: vaikka päivityskaavassa käytetään yleensä keskimääräistä palkkiota vertailuarvona, tämän arvon voi korvata millä tahansa vakiolla, joka ei riipu valitusta toiminnosta. Vertailuarvo vaikuttaa oppimisen nopeuteen, mutta ei muuta optimaalista ratkaisua;
  • Askelkoon vaikutus: askelkoon arvo kannattaa säätää tehtävän mukaan. Pienempi askelkoko takaa vakaamman oppimisen, kun taas suurempi arvo nopeuttaa oppimisprosessia.

Yhteenveto

Gradienttibanditit tarjoavat tehokkaan vaihtoehdon perinteisille bandittialgoritmeille hyödyntämällä preferenssipohjaista oppimista. Niiden merkittävin ominaisuus on kyky tasapainottaa luonnollisesti tutkimista ja hyväksikäyttöä.

question mark

Mikä on gradienttibandittien tärkein etu perinteisiin bandittialgoritmeihin verrattuna?

Select the correct answer

Oliko kaikki selvää?

Miten voimme parantaa sitä?

Kiitos palautteestasi!

Osio 2. Luku 5
some-alt