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 yleensä 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$ 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 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 arvio $k$:nnen palkkion arvosta, $Q_k$, ja todellinen $k$:s palkkio, $R_k$, virhe voidaan mitata näiden arvojen erotuksena. Seuraava arvio voidaan tämän jälkeen 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 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 initialisointi

Koulutusprosessin alussa toimintojen arvoarviot voivat vaihdella merkittävästi, mikä saattaa 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 on motivoitunut tutkimaan jokaista toimintoa useita kertoja ennen parhaan vaihtoehdon valitsemista. Tämä tekniikka on tehokkaimmillaan, kun sitä käytetään yhdessä vakionopeuksisen päivityksen kanssa.