Actiewaarde is een fundamenteel concept in het MAB-probleem. Het speelt een cruciale rol in verschillende algoritmen, waaronder epsilon-greedy en upper confidence bound. Het primaire doel van een actiewaarde is het geven van een schatting van de verwachte beloning wanneer een specifieke actie wordt gekozen. Het is vergelijkbaar met een toestand-actiewaarde, maar is onafhankelijk van een toestand vanwege het toestandloze karakter van het MAB-probleem.

Definitie van actiewaarde

Formeel stelt de actiewaarde, aangeduid als $Q(a)$, de verwachte beloning voor van het kiezen van actie $a$:

waarbij:

• $R$ de ontvangen beloning is;
• $A$ de geselecteerde actie is.

Aangezien de ware beloningsverdeling doorgaans onbekend is, moeten we $Q(a)$ schatten met behulp van geobserveerde data.

Waardeschatting van Acties

Er zijn verschillende manieren om $Q(a)$ te schatten op basis van waargenomen beloningen. De meest gebruikelijke methode is de steekproefgemiddelde schatting, die de gemiddelde beloning berekent die is ontvangen door het kiezen van actie $a$ tot tijdstip $t$:

waarbij:

• $Q_t(a)$ de geschatte waarde is van actie $a$ op tijdstip $t$;
• $N_t(a)$ het aantal keren is dat actie $a$ is gekozen tot tijdstip $t$;
• $R_i$ de beloning is verkregen bij elke keer dat actie $a$ werd uitgevoerd.

Naarmate meer steekproeven worden verzameld, convergeert deze schatting naar de werkelijke verwachte beloning $Q_*(a)$, ervan uitgaande dat de beloningsverdeling stationair blijft.

Incrementele bijwerkingsregel

Hoewel de bovenstaande formule gebruikt kan worden om actie-waarden te schatten, vereist deze het opslaan van alle eerdere beloningen en het telkens opnieuw berekenen van hun som bij elke tijdstap. Met incrementele bijwerkingen is dit niet meer nodig. De formule voor incrementele bijwerkingen kan als volgt worden afgeleid:

waarbij voor een bepaalde actie:

• $Q_k$ een schatting is van de $k$-de beloning, die kan worden uitgedrukt als een gemiddelde van de eerste $k-1$ beloningen;
• $R_k$ de werkelijke $k$-de beloning is.

Intuïtie

Door de schatting van de $k$-de beloning, $Q_k$, en de werkelijke $k$-de beloning, $R_k$, te kennen, kan de fout worden gemeten als het verschil tussen deze waarden. Vervolgens kan de volgende schatting worden berekend door de vorige schatting enigszins aan te passen in de richting van de werkelijke beloning, om de fout te verkleinen.

Deze intuïtie leidt tot een andere formule, die er als volgt uitziet:

waarbij $\alpha$ een stapgrootteparameter is die de leersnelheid bepaalt. Net als in de vorige formule kan alpha $\frac1k$ zijn, wat resulteert in een steekproefgemiddelde schatting. Alternatief wordt vaak een constante $\alpha$ gebruikt, omdat dit geen extra ruimte vereist (om op te slaan hoe vaak een actie is uitgevoerd) en aanpassing aan niet-stationaire omgevingen mogelijk maakt door meer gewicht te geven aan recente observaties.

Optimistische initialisatie

Aan het begin van een trainingsproces kunnen schattingen van actie-waarden aanzienlijk variëren, wat kan leiden tot voortijdige exploitatie. Dit betekent dat de agent zijn initiële kennis te vroeg benut, waardoor suboptimale acties worden verkozen op basis van beperkte ervaring. Om dit probleem te verminderen en initiële exploratie te stimuleren, is optimistische initialisatie een eenvoudige en effectieve techniek.

Bij optimistische initialisatie worden actie-waarden op relatief hoge waarden geïnitialiseerd (bijvoorbeeld $Q_0(a) = 1$ in plaats van 0). Deze aanpak wekt de indruk dat alle acties aanvankelijk veelbelovend zijn. Hierdoor wordt de agent gestimuleerd om elke actie meerdere keren te verkennen voordat de beste keuze wordt gemaakt. Deze techniek is het meest efficiënt in combinatie met een constante stapgrootte.