Gradienttinen Bandiittialgoritmi
Moniasemaisten bandiittien yhteydessä perinteiset menetelmät, kuten epsilon-ahne ja UCB, arvioivat toimintojen arvoja päättääkseen, mitä toimintoa suorittaa. Gradienttibanditit lähestyvät ongelmaa kuitenkin eri tavalla — ne oppivat toimintojen preferenssejä arvojen arvioimisen sijaan. Näitä preferenssejä säädetään ajan myötä käyttäen stokastista gradienttinousua.
Preferenssit
Sen sijaan, että ylläpidettäisiin toimintojen arviota Q(a), gradienttibanditit ylläpitävät preferenssiarvoja H(a) jokaiselle toiminnolle a. Näitä preferenssejä päivitetään stokastisen gradienttinousun avulla odotettujen palkkioiden maksimoimiseksi. Jokaisen toiminnon todennäköisyys lasketaan softmax-funktiolla:
P(At=a)=∑b=1neHt(b)eHt(a)=πt(a)missä:
- Ht(a) on toiminnon a preferenssi ajanhetkellä t;
- P(At=a) on todennäköisyys valita toiminto a ajanhetkellä t;
- 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 argmax-funktiolle, mahdollistaen luonnollisen tutkimisen antamalla pienemmän preferenssin toiminnoille nollasta poikkeavan mahdollisuuden tulla valituksi.
Päivityssääntö
Toiminnon At valinnan jälkeen ajanhetkellä t, preferenssiarvot päivitetään seuraavan säännön mukaisesti:
Ht+1(At)←Ht(At)+α(Rt−Rˉt)(1−π(At))Ht+1(a)←Ht(a)−α(Rt−Rˉt)π(a)∀a=Atmissä:
- α on askelkokonaisuus;
- Rt on saatu palkkio;
- Rˉt on tähän asti havaittu keskimääräinen palkkio.
Intuitio
Jokaisella ajanhetkellä kaikkia preferenssejä siirretään hieman. Muutos 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, valitun toiminnon preferenssi kasvaa, ja muiden toimintojen preferenssit vähenevät;
- 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ätietoa
Gradienttibanditeilla on useita mielenkiintoisia ominaisuuksia:
- Preferenssien suhteellisuus: toimintojen preferenssien absoluuttisilla arvoilla ei ole vaikutusta toiminnon 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 tulee 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 hyödyntämistä.
Kiitos palautteestasi!
Kysy tekoälyä
Kysy tekoälyä
Kysy mitä tahansa tai kokeile jotakin ehdotetuista kysymyksistä aloittaaksesi keskustelumme
Can you explain how the softmax function helps with exploration in gradient bandits?
What is the role of the average reward baseline in the update rule?
Can you compare gradient bandits to epsilon-greedy or UCB methods?
Awesome!
Completion rate improved to 2.7
Gradienttinen Bandiittialgoritmi
Pyyhkäise näyttääksesi valikon
Moniasemaisten bandiittien yhteydessä perinteiset menetelmät, kuten epsilon-ahne ja UCB, arvioivat toimintojen arvoja päättääkseen, mitä toimintoa suorittaa. Gradienttibanditit lähestyvät ongelmaa kuitenkin eri tavalla — ne oppivat toimintojen preferenssejä arvojen arvioimisen sijaan. Näitä preferenssejä säädetään ajan myötä käyttäen stokastista gradienttinousua.
Preferenssit
Sen sijaan, että ylläpidettäisiin toimintojen arviota Q(a), gradienttibanditit ylläpitävät preferenssiarvoja H(a) jokaiselle toiminnolle a. Näitä preferenssejä päivitetään stokastisen gradienttinousun avulla odotettujen palkkioiden maksimoimiseksi. Jokaisen toiminnon todennäköisyys lasketaan softmax-funktiolla:
P(At=a)=∑b=1neHt(b)eHt(a)=πt(a)missä:
- Ht(a) on toiminnon a preferenssi ajanhetkellä t;
- P(At=a) on todennäköisyys valita toiminto a ajanhetkellä t;
- 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 argmax-funktiolle, mahdollistaen luonnollisen tutkimisen antamalla pienemmän preferenssin toiminnoille nollasta poikkeavan mahdollisuuden tulla valituksi.
Päivityssääntö
Toiminnon At valinnan jälkeen ajanhetkellä t, preferenssiarvot päivitetään seuraavan säännön mukaisesti:
Ht+1(At)←Ht(At)+α(Rt−Rˉt)(1−π(At))Ht+1(a)←Ht(a)−α(Rt−Rˉt)π(a)∀a=Atmissä:
- α on askelkokonaisuus;
- Rt on saatu palkkio;
- Rˉt on tähän asti havaittu keskimääräinen palkkio.
Intuitio
Jokaisella ajanhetkellä kaikkia preferenssejä siirretään hieman. Muutos 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, valitun toiminnon preferenssi kasvaa, ja muiden toimintojen preferenssit vähenevät;
- 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ätietoa
Gradienttibanditeilla on useita mielenkiintoisia ominaisuuksia:
- Preferenssien suhteellisuus: toimintojen preferenssien absoluuttisilla arvoilla ei ole vaikutusta toiminnon 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 tulee 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 hyödyntämistä.
Kiitos palautteestasi!