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 riippumaton tilasta MAB-ongelman tilattoman luonteen 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 olemassa useita tapoja estimoida $Q(a)$ havaittujen palkkioiden perusteella. Yleisin menetelmä on otoskeskiarvoestimaatti, joka laskee toiminnon $a$ valitsemisesta ajanhetkeen $t$ mennessä saadun keskimääräisen palkkion:

missä:

• $Q_t(a)$ on toiminnon $a$ estimaatti ajanhetkellä $t$;
• $N_t(a)$ on niiden kertojen määrä, jolloin toimintoa $a$ on valittu ajanhetkeen $t$ mennessä;
• $R_i$ on palkkio, joka on saatu aina, kun toimintoa $a$ on käytetty.

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 arvioimiseen, se vaatii kaikkien aiempien palkkioiden tallentamista ja niiden summan uudelleenlaskemista jokaisella aikavälillä. 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 $k$:nnen palkkion arvio $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 on seuraavanlainen:

missä $\alpha$ on oppimisnopeutta säätelevä askelkokoparametri. Kuten aiemmassa 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 viimeaikaisia havaintoja.

Optimistinen alustaminen

Koulutusprosessin alussa toimintojen arvojen arviot 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 rajallisen kokemuksen perusteella. 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 (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 parhaan vaihtoehdon valitsemista. Tämä tekniikka on tehokkaimmillaan, kun sitä käytetään yhdessä vakioaskelkoon kanssa.