Toimintoarvo on keskeinen käsite MAB-ongelmassa. Sillä on olennainen rooli useissa algoritmeissa, kuten epsilon-ahneessa ja yläluottamusraja-menetelmässä. Toimintoarvon ensisijainen tarkoitus on antaa arvio odotetusta palkkiosta, kun tietty toiminto valitaan. Se muistuttaa tila-toimintoarvoa, mutta on tilasta riippumaton MAB-ongelman tilattomuuden vuoksi.

Toimintoarvon määritelmä

Muodollisesti toimintoarvo, merkittynä $Q(a)$, edustaa odotettua palkkiota, kun valitaan toiminto $a$:

missä:

• $R$ on saatu palkkio;
• $A$ on valittu toiminto.

Koska todellinen palkkioiden jakauma on tyypillisesti tuntematon, meidän täytyy arvioida $Q(a)$ havaittujen tietojen perusteella.

Toimintoarvojen estimointi

On useita tapoja estimoida $Q(a)$ havaittujen palkkioiden perusteella. Yleisin menetelmä on otoskeskiarvoestimaatti, joka laskee toiminnon $a$ valitsemisesta ajanhetkeen $t$ mennessä saatujen palkkioiden keskiarvon:

missä:

• $Q_t(a)$ on toiminnon $a$ arvioitu arvo ajanhetkellä $t$;
• $N_t(a)$ on toiminnon $a$ valintojen lukumäärä ajanhetkeen $t$ mennessä;
• $R_i$ on palkkio, joka saatiin aina, kun toiminto $a$ valittiin.

Kun näytteitä kerätään lisää, tämä estimaatti lähestyy todellista odotettua palkkiota $Q_*(a)$ olettaen, että palkkioiden jakauma pysyy stationaarisena.

Inkrementaalinen päivityssääntö

Vaikka yllä olevaa kaavaa voidaan käyttää toimintojen arvojen arviointiin, se vaatii kaikkien aiempien palkkioiden tallentamista ja niiden summan uudelleenlaskemista jokaisella askeleella. Inkrementaalisten päivitysten avulla tämä ei ole tarpeen. Inkrementaalisen päivityksen kaava voidaan johtaa seuraavasti:

missä jollekin toiminnolle:

• $Q_k$ on arvio $k$:nnen palkkion arvosta, joka voidaan ilmaista ensimmäisten $k-1$ palkkion keskiarvona;
• $R_k$ on todellinen $k$:s palkkio.

Intuitio

Kun tiedetään arvio $k$:nnen palkkion arvosta, $Q_k$, ja todellinen $k$:s palkkio, $R_k$, virhe voidaan mitata näiden arvojen erotuksena. Seuraava arvio voidaan laskea säätämällä edellistä arviota hieman todellisen palkkion suuntaan virheen pienentämiseksi.

Tämä intuitio johtaa toiseen kaavaan, joka näyttää tältä:

missä $\alpha$ on oppimisnopeutta säätelevä askelkokoparametri. Kuten edellisessä kaavassa, alfa voi olla $\frac1k$, jolloin saadaan otoskeskiarvoarvio. Vaihtoehtoisesti käytetään usein vakioarvoista $\alpha$:aa, koska se ei vaadi lisätilaa (toiminnon suoritusmäärän tallentamiseen) ja mahdollistaa sopeutumisen ei-stationaarisiin ympäristöihin painottamalla enemmän viimeisimpiä havaintoja.

Optimistinen alustus

Koulutusprosessin alussa toimintojen arvoarviot voivat vaihdella merkittävästi, mikä voi johtaa ennenaikaiseen hyödyntämiseen. Tämä tarkoittaa, että agentti saattaa hyödyntää alkuperäistä tietämystään liian aikaisin, suosien epäoptimaalisia toimintoja perustuen rajalliseen kokemukseen. Tämän ongelman lieventämiseksi ja alkuperäisen tutkimisen edistämiseksi yksi yksinkertainen ja tehokas tekniikka on optimistinen alustaminen.

Optimistisessa alustamisessa toimintojen arvot alustetaan suhteellisen korkeiksi arvoiksi (esim. $Q_0(a) = 1$ nollan sijaan). Tämä luo vaikutelman, että kaikki toiminnot ovat aluksi lupaavia. Tämän seurauksena agentti kannustetaan tutkimaan jokaista toimintoa useita kertoja ennen kuin se päätyy parhaaseen valintaan. Tämä tekniikka on tehokkaimmillaan käytettynä yhdessä vakion askelkoon kanssa.