La valeur d'action est un concept fondamental dans le problème du bandit manchot (MAB). Elle joue un rôle central dans divers algorithmes, notamment epsilon-greedy et la borne supérieure de confiance. L'objectif principal d'une valeur d'action est de fournir une estimation de la récompense attendue lorsqu'une action spécifique est choisie. Elle est similaire à une valeur état-action, mais elle est indépendante de l'état en raison de la nature sans état du problème MAB.

Définition de la valeur d'action

Formellement, la valeur d'action, notée $Q(a)$, représente la récompense attendue lors du choix de l'action $a$ :

où :

• $R$ est la récompense reçue ;
• $A$ est l'action sélectionnée.

Puisque la distribution réelle des récompenses est généralement inconnue, nous devons estimer $Q(a)$ à l'aide des données observées.

Estimation des valeurs d'action

Il existe plusieurs méthodes pour estimer $Q(a)$ à partir des récompenses observées. La méthode la plus courante est l'estimation par moyenne empirique, qui calcule la récompense moyenne obtenue en sélectionnant l'action $a$ jusqu'au temps $t$ :

où :

• $Q_t(a)$ est la valeur estimée de l'action $a$ à l'instant $t$ ;
• $N_t(a)$ est le nombre de fois où l'action $a$ a été choisie jusqu'au temps $t$ ;
• $R_i$ est la récompense obtenue à chaque fois que l'action $a$ a été sélectionnée.

À mesure que davantage d'échantillons sont collectés, cette estimation converge vers la véritable récompense attendue $Q_*(a)$, en supposant que la distribution des récompenses reste stationnaire.

Règle de mise à jour incrémentale

Bien que la formule ci-dessus puisse être utilisée pour estimer les valeurs d'action, elle nécessite de stocker toutes les récompenses précédentes et de recalculer leur somme à chaque étape temporelle. Avec les mises à jour incrémentales, cela devient inutile. La formule pour les mises à jour incrémentales peut être dérivée ainsi :

où, pour une action donnée :

• $Q_k$ est une estimation de la $k$-ième récompense, qui peut être exprimée comme une moyenne des $k-1$ premières récompenses ;
• $R_k$ est la véritable $k$-ième récompense.

Intuition

En connaissant l'estimation de la $k$-ième récompense, $Q_k$, et la véritable $k$-ième récompense, $R_k$, il est possible de mesurer l'erreur comme la différence entre ces valeurs. Ensuite, la prochaine estimation peut être calculée en ajustant légèrement l'estimation précédente dans la direction de la récompense réelle, afin de réduire l'erreur.

Cette intuition conduit à une autre formule, qui s'écrit ainsi :

où $\alpha$ est un paramètre de taux d'apprentissage contrôlant la vitesse d'apprentissage. Comme dans la formule précédente, alpha peut être $\frac1k$, ce qui donne une estimation par moyenne d'échantillon. Alternativement, un $\alpha$ constant est couramment utilisé, car il ne nécessite aucun espace supplémentaire (pour stocker le nombre de fois qu'une action a été choisie) et permet une adaptation à des environnements non stationnaires en accordant plus de poids aux observations récentes.

Initialisation optimiste

Au début d'un processus d'apprentissage, les estimations des valeurs d'action peuvent varier considérablement, ce qui peut entraîner une exploitation prématurée. Cela signifie que l'agent peut exploiter ses connaissances initiales trop tôt, en privilégiant des actions sous-optimales sur la base d'une expérience limitée. Pour atténuer ce problème et encourager une exploration initiale, une technique simple et efficace est l'initialisation optimiste.

Avec l'initialisation optimiste, les valeurs d'action sont initialisées à des valeurs relativement élevées (par exemple, $Q_0(a) = 1$ au lieu de 0). Cette approche donne l'impression que toutes les actions sont prometteuses au départ. En conséquence, l'agent est incité à explorer chaque action plusieurs fois avant de se fixer sur le meilleur choix. Cette technique est particulièrement efficace lorsqu'elle est utilisée en combinaison avec une taille de pas constante.