Méthodes de différences temporelles

Section 8.2 Méthodes de différences temporelles

Précemment nous avons introduit deux familles de méthodes. Les méthodes de programmation dynamique qui estime la fonction valeur en parcourant l'ensemble des transitions possibles maus en utilisant l'estimation de la fonction valeur pour les états directement accessibles (équation de Bellman). A l'inverse les méthodes de Monte-Carlo qui échantillonne l'ensemble des possibiltés mais qui utilise une trajectoire complète pour estimer une fonction valeur. Les méthodes que nous allons introduire sont une combinaison des deux précédentes appelée méthodes de différences temporelles. Il s'agit aussi, comme les méthodes de Monte-Carlo de méthodes sans modèle. On va commencer par introduire une méthode rarement utilisée mais très explicative.

La méthode MC propose d'estimer l'espérance

\begin{equation*} V^{\pi}(s) = \mathbb{E}[G_t, s_t=s, \pi] \end{equation*}

On va maintenant utiliser la caractérisation de la fonction valeur (7.2). L'idée de la méthode TD(0) que l'ont introduit consiste à appliquer une méthode de Monte-Carlo sur cette caractérisation. On se donne une trajectoire $(s_1,a_1,...s_t,a_t,...)$ (voir plusieurs) obtenu en interaction avec l'environemment suivant la politique $\pi$ qui donne:

\begin{equation*} V^{\pi}(s_t)= \frac{1}{N(s_t)}\sum_{t} r_{\pi}(s_{t+1}) +\gamma V_{\pi}(s_{t+1}) \end{equation*}

En utilisant la version incrémentale de l'estimation empirique de l'espérence on obtient:

\begin{equation*} V_{n+1}^{\pi}(s_t) =V_{n}^{\pi}(s_t) +\frac{1}{N(s_t)+1}\left(r_{\pi}(s_{t+1}) +\gamma V_{\pi}(s_{t+1}) - V_n(s_t) \right) \end{equation*}

Le théorème Proposition 1.17 nous dit qu'on peut avoir un algorithme convergent en remplacant $\frac{1}{N(s_t)+1}$ par un pas positif $\alpha_n\text{.}$ Cela donne une étape de notre algorithme:

\begin{equation*} V_{n+1}^{\pi}(s_t) =V_{n}^{\pi}(s_t) +\alpha_n\left(r_{\pi}(s_{t+1}) +\gamma V_n^{\pi}(s_{t+1}) - V_n(s_t) \right) \end{equation*}

Cet algorithme permet de calculer une estimation de la fonction valeur et donc d'évaluer une politique. On appelle $\delta_t=\left(r_{\pi}(s_{t+1}) +\gamma V_{\pi}(s_{t+1}) - V_n(s_t) \right)$ la différence temporelle. Comme dit on peut voir cet algorithme comme une méthode de MC appliquée à la caractérisation "recurcive" de la fonction valeur. La méthode MC précédente s'écrit:

\begin{equation} V_{n+1}^{\pi}(s) =V_{n}^{\pi}(s) +\alpha_n\left(G_t - V_n(s) \right)\tag{8.1} \end{equation}

On écrit $G_t$ le long d'une trajectoire. On obtient:

\begin{equation*} G_t= r_{t+1} + \gamma (r_{t+2}+\gamma r_{t+3} + .....)= r_{t+1} +\gamma G_{t+1} \end{equation*}

et donc

\begin{equation*} \mathbb{E}[G_t]= \mathbb{E}[r_{t+1} +\gamma V_{t+1} ] \end{equation*}

On voit donc que lorsque cette relation est échantillonnée et utilisée dans (8.1) on retrouve l'appropximation TD(0).

Subsection 8.2.1 Méthodes de type SARSA

Le principe de l'algorithme TD(0) introduit juste au dessus nous donne une stratégie d'évaluation d'une politique. Ici on souhiate utiliser la même idée afin de construire une algorithme constructif de la politique. Ici on considère la Q-fonction dont la définition est donnée par Définition 7.15. La caractérisation nous donne la relation (7.3). En utilisant comme pour l'approche TD(0) la méthode de Monte-Carlo dans sa version incrémentale sur une trajectoire on obtient:

\begin{equation*} Q_{n+1}^{\pi}(s)(s_t,a_t)= Q_{n+1}^{\pi}(s)(s_t,a_t) + \alpha_n ( r(s_t,a_t) +\gamma Q_{n}^{\pi}(s)(s_{t+1},a_{t+1}) - Q_{n}^{\pi}(s)(s_t,a_t)) \end{equation*}

On obtient donc un incrément sur la Q-fonction. Cela nous donne un algorithme appelé SARSA.

Algorithm 8.10. Algorithme SARSA.

Initialisation de $Q(.,.)$ arbitraire avec $Q(s_{terminal},.)=0$
$\displaystyle \forall k \leq K$
- initialiser $s_0$ de façon aléatoire,
- choisir $a_0$ selon la politique $\pi$ (dépendante de Q) à partir de $s_0\text{,}$
- $\displaystyle \forall t \in \left\{0,...,T\right\}$
  - calculer $s_{t+1}$ et $r_{t+1}$ en utilisant l'environemment et $(s_t,a_t)$
  - choisir $a_{t+1}$ selon la politique $\pi$ a partir de $s_{t+1}$
  - on calcul:
    
    \begin{equation*} Q(s_t,a_t)= Q(s_t,a_t)+ \alpha (r_{t+1}+\gamma Q(s_{t+1},a_{t+1}) - Q(s_t,a_t)) \end{equation*}
  - on met à jour la politique $\pi$ (si dépend de Q)
  - $s_{t}=s_{t+1}\text{,}$ $a_{t}=a_{t+1}$
On renvoit $\pi(a\mid s)=\operatorname{argmax}_{a} Q(s,a)$

L'algorithme précedent n'utilise a chaque transition que le quintuplet $(s_t,a_t,r_{t+1},s_{t+1},a_{t+1})$ d'ou le nom. Le terme $r_{t+1}+\gamma Q(s_{t+1},a_{t+1})$ correspond à un échantillon de de la méthode de Monte-Carlo incrémental appliquée à l'espérance (7.3). Cette estimation de l'espérance utilise ici une action générée par la politique d'exploration $\pi\text{,}$ on est donc entrain d'évaluer la Q fonction de la politique $\pi\text{.}$ On a donc a faire à un algorithme dit "on policy" qui à la fin convergera vers une politique stochastique. Pour obtenir à la limite une politique gloutonne (souvent privilégié) il faut un certains type de politique d'exploration qui progréssivement se rapproche de la politique gloutonne.

Subsection 8.2.2 Méthodes de type "Q-learning"

La méthode de Q-learning \cite{Watkins1992} que nous allons introduire dans cette sous section peut être interprétrée comme une version "off policy" de l'algorithme SARSA précédent. Elle est simple et utilisable dans beaucoup de problème. Cela en fait une méthode très populaire voir la plus populaire pour les problèmes de petite taille.

Subsubsection 8.2.2.1 Méthode de "Q-learning"

Pour construire la méthode de Q learning on repart de la caractérisation de la fonction optimale cette fois:

\begin{equation} Q(s,a) = \mathbb{E}[r(s_t,a_t) + \gamma \operatorname{max}_{a^{'}}Q(s_{t+1},a^{'}) \mid s_t =s , a_t=a; \pi]\tag{8.2} \end{equation}

On remarque que l'ont réécrire cela rapidement sous la forme:

\begin{equation} Q(s,a) = \mathbb{E}[r(s_t,a_t) + \gamma Q(s_{t+1},\operatorname{argmax}_{a^{'}} Q(s_{t+1},a^{'})) \mid s_t =s , a_t=a, \pi]\tag{8.3} \end{equation}

Si on définit la politique gloutonne (donc déterministe) $\mu(s)= \operatorname{argmax} Q(s,a)$ dans ce cas on obtient:

\begin{equation} Q(s,a) = \mathbb{E}[r(s_t,a_t) + \gamma Q(s_{t+1},\mu(s_{t+1})) \mid s_t =s , a_t=a, \pi]\tag{8.4} \end{equation}

On voit ici qu'on évalue l'espèrance liée à la politique $\mu(s)$ a partir de trajectoire générée par $\pi(.\mid .)\text{.}$ On utilise donc moralement une methode d'échantillon préférentielle et comme dans le cas Monte-Carlo cela va mener à une méthode "off-policy". Pour cela on fait comme précédemment on approche l'espérance (8.4) à l'aide de la méthode de Monte-Carlo dans sa forme incrémentale ce qui donne l'incrément:

\begin{equation*} Q^{\pi}(s)(s_t,a_t)= Q^{\pi}(s)(s_t,a_t) + \alpha ( r(s_t,a_t) +\gamma \operatorname{max}_{a^{'}} Q^{\pi}(s)(s_{t+1},a^{'}) - Q^{\pi}(s)(s_t,a_t)) \end{equation*}

A partir de la on obtient l'algorithme de Q-learning.

Algorithm 8.11. Algorithme de Q learning.

Initialisation de $Q(.,.)$ arbitraire avec $Q(s_{terminal},.)=0$
$\displaystyle \forall k \leq K$
- initialiser $s_0$ de façon aléatoire,
- $\displaystyle \forall t \in \left\{0,...,T\right\}$
  - choisir $a_t$ selon la politique $\pi$ (dépendante de Q) à partir de $s_t$
  - calculer $s_{t+1}$ et $r_{t+1}$ en utilisant l'environemment et $(s_t,a_t)$
  - choisir $a_{t+1}$ selon la politique $\pi$ a partir de $s_{t+1}$
  - on calcul:
    
    \begin{equation*} Q(s_t,a_t)= Q(s_t,a_t)+ \alpha (r_{t+1}+\gamma \operatorname{max}_{a} Q(s_{t+1},a) - Q(s_t,a_t)) \end{equation*}
  - on met à jour la politique $\pi$ (si dépend de Q)
  - $\displaystyle s_{t}=s_{t+1}$
On renvoit $\pi(a\mid s)=\operatorname{argmax}_{a} Q(s,a)$

L'algorithme de "Q-learning" est l'algorithme de base le plus utiliser à cause de sa simplicité et de son aspect général.

Subsubsection 8.2.2.2 Méthodes dérivées du Q-learning

On peut constuire d'autre méthodes dérivées du "Q-learning". La première est la méthode dite "excepted SARSA" [1.35] il s'agit d'une méthode intermédiaire entre le "Q-learning" et le SARSA. Il s'agit de remplacer dans l'incrément de SARSA, le terme $Q(s_{t+1},a_{t+1})$ par son espérance:

\begin{equation*} \mathbb{E}_{\pi}[Q(s_{t+1},a_{t+1}) \mid s_{t+1}] = \sum_{a^{'}} b(a\mid s_t)Q(s_t,a) \end{equation*}

Si on prend $b=\pi$ la politique cible du SARSA on se retrouve avec un algorithme "on-policy" mais dont la variance est moins grande puisqu'il ne choisit une action selon une politique aléatoire mais l'espérance sur la variable aléatoire du choix des actions. Si on prend $b \neq \pi$ il s'agit d'un algorithme "off policy" qui coincide avec le "Q-learning" pour $b=\mu$ la politique gloutonne. L'algorithme est donc exactement le même que SARSA mais avec $\sum_{a^{'}} b(a\mid s_t)Q(s_t,a)$ à la place $Q(s_{t+1},a_{t+1})$ dans l'incrément. On peut voir le "expected SARSA" comme une généralisation du "Q-learning" et du SARSA.

La seconde méthode dérivée du "Q-learning" est une variante appelée double Q-learning [1.36] très utilisée pour contrecarrer un défaut de l'algorithme d'origine qui le biais de maximisation. Puisque pendant le procéssus itératif la fonction Q est approchée on peut se retrouver facilement (notamment dans un contexte stochastique) dans une situation ou:

\begin{equation*} Q_k(s_{t+1},a^{'}) = Q^{*}(s_{t+1},a^{'}) + e_{a^{'}} \end{equation*}

avec $e_{a^{'}} \geq 0\text{.}$ Prenons le cas ou l'estimateur $Q_k(s_{t+1},a^{'})$ est un estimateur sans biais ($\mathbf{E}[e_{a^{'}}]=0$) de $Q^{*}(s_{t+1},a^{'})\text{.}$ On passe au maximum. Puisque $e_{a^{'}} \geq 0$ on a donc

\begin{equation*} max_{a^{'}}Q_k(s_{t+1},a^{'}) = max_{a^{'}}Q^{*}(s_{t+1},a^{'}) + max_{a^{'}} e_{a^{'}} \end{equation*}

On peut se demander quelle sont les propriétés de l'estimateur $max_{a^{'}}Q_k(s_{t+1},a^{'})$ pour la quantité $max_{a^{'}}Q^*(s_{t+1},a^{'})\text{.}$ On prend donc l'espérance et puisque on a supposé les erreurs positives on va avoir que

\begin{equation*} \mathbb{E}[max_{a^{'}}Q_k(s_{t+1},a^{'}) ] \geq \mathbb{E}[max_{a^{'}}Q^*(s_{t+1},a^{'}) ]. \end{equation*}

On a donc un estimateur avec un biais positif. Ce biais dans l'estimation ne génère pas forcement de problème. La sur-estimation est plus importante dans les zones fortement stochastique. En effet car on va explorer plus fortement une zone ou on surestime les valeurs de la Q fonction. Si cela correspond a une zone ou la Q fonction est faible, on va beaucoup explorer une zone ou les actions ont une faible valeur. Pour regler ce problème il a été proposé le "double Q-learning". L'idée est de construire deux Q fonctions. Au lieu d'estimer une action avec le maximum de la fonction Q qui génère l'action on va utiliser l'autre fonction Q. Cela permet de décoreler de façon plus importante l'exploration de l'estimation.

Algorithm 8.12. Algorithme double "Q-learning".

Initialisation de $Q_1(.,.)$ et $Q_2(.,.)$ arbitraire avec $Q_{1,2}(s_{terminal},.)=0$
$\displaystyle \forall k \leq K$
- initialiser $s_0$ de façon aléatoire,
- $\displaystyle \forall t \in \left\{0,...,T\right\}$
  - choisir $a_t$ selon la politique $\pi$ (dépendante de $Q_1+Q_2$) à partir de $s_t$
  - calculer $s_{t+1}$ et $r_{t+1}$ en utilisant l'environemment et $(s_t,a_t)$
  - choisir $a_{t+1}$ selon la politique $\pi$ a partir de $s_{t+1}$
  - Tirer un nombre aléatoire $p$ selon une loi uniforme,
  - Si $p \lt 0.5$
    
    \begin{equation*} Q_1(s_t,a_t)= Q_1(s_t,a_t)+ \alpha (r_{t+1}+\gamma Q_1(s_{t+1},\operatorname{argmax}_{a^{'}}Q_2(s_{t+1},a^{'})) - Q_1(s_t,a_t) \end{equation*}
    
    sinon
    
    \begin{equation*} Q_2(s_t,a_t)= Q_2(s_t,a_t)+ \alpha (r_{t+1}+\gamma Q_2(s_{t+1},\operatorname{argmax}_{a^{'}}Q_1(s_{t+1},a^{'})) - Q_2(s_t,a_t) \end{equation*}
  - on met à jour la politique $\pi$ (si dépend de $Q_1+Q_2$)
  - $\displaystyle s_{t}=s_{t+1}$
On renvoit $\pi(a\mid s)=\operatorname{argmax}_{a} Q(s,a)$

Subsection 8.2.3 Exploration/Exploitation

Dans la méthode SARSA on doit définir une politique stochastique qui sera la politique construite. Cette politique doit à la fois permettre d'explorer les possibilités et en même temps doit converger ou se rapprocher d'une politique optimale. Dans la méthode de Q-learning on doit aussi construire une pollitique d'exploration qui ici sera différente de la politique gloutonne. Cette politique peut aussi se rapprocher de la politique optimale même si c'est moins nécéssaire. La question importante qui nous reste à traiter est le choix de cette politique d'exploration $\pi(a \mid a)\text{.}$ Il existe differentes approches d'exploration:

exploration gloutonne
exploration par stochasticité,
exploration par optimalité,
exploration par motivation intrasèque,

On va rapidement introduire ces différentes possibilités.

Subsubsection 8.2.3.1 Exploration Gloutonne

Ici il s'agit simplement de prendre la politique gloutonne comme politique d'exploration. Pour cela on définit

\begin{equation*} \mathcal{B}_{Q} = \left\{ a, \mbox{ tel que } a=\operatorname{argmax}_{a^{'}} Q(s,a^{'}) \right\} \end{equation*}

ce qui nous donne la politique

\begin{equation*} \pi_{g}(a\mid s)= \frac{\mathbb{I}_{[a\in \mathcal{B}_Q]}}{\mid \mathcal{B}_{Q} \mid} \end{equation*}

avec $\mathbb{I}$ la fonction indicatrice.

On pourrait se dire que cette politique serait la plus adaptée car on va chercher la meilleur action. Le problème c'est qu'on risque de ne jamais passer par un certains nombre d'action et rater des actions/sous ensemble d'actions qui pourrait être meilleur. Ici on parle d'amélioration pur sans exploration.

Exemple 8.13. Parcours de graphe.

On cherche a optimiser le parcours sur un graphe pondéré avec $\gamma=1\text{.}$ On se donne un graphe avec comme matrice d'adjacence:

\begin{equation*} A=\begin{pmatrix} 0. \amp 0.4 \amp 0 \amp 0 \amp 0 \amp 2.0 \amp 0 \amp \cdots \amp 0 \\ 0. \amp 0 \amp 0.9 \amp 0.2 \amp 0.0 \amp 0 \amp 0 \amp \cdots \amp 0 \\ 0. \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp \cdots \amp 0 \\ 0. \amp 0.3 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1.4 \amp \cdots \amp 0 \\ \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \\ \end{pmatrix} \end{equation*}

ce qui nous donne

\begin{equation*} R=\begin{pmatrix} 0. \amp -0.4 \amp 0 \amp 0 \amp 0 \amp -2.0 \amp 0 \amp \cdots \amp 0 \\ 0. \amp 0 \amp -0.9 \amp -0.2 \amp 0.0 \amp 0 \amp 0 \amp \cdots \amp 0 \\ 0. \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp \cdots \amp 0 \\ 0. \amp -0.3 \amp 0 \amp 0 \amp 0 \amp 0 \amp -1.4 \amp \cdots \amp 0 \\ \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \\ \end{pmatrix} \end{equation*}

On suppose la matrice $Q_0$ initiale aléatoire donnée par exemple par

\begin{equation*} Q=\begin{pmatrix} 0. \amp 1.0 \amp 0 \amp 0 \amp 0 \amp 0.7 \amp 0 \amp \cdots \amp 0 \\ 0. \amp 0 \amp 0.6 \amp 1.1 \amp 0.0 \amp 0 \amp 0 \amp \cdots \amp 0 \\ 0. \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp \cdots \amp 0 \\ 0. \amp 1.2 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0.2 \amp \cdots \amp 0 \\ \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \\ \end{pmatrix} \end{equation*}

On initialise avec $s_0=1$ (premier noeud du graphe) et on applique l'algorithme de Q-learning avec $\alpha=1$ (conseillé pour les environnements déterministe).

Itération 1: $\operatorname{argmax}_a Q(1,a)=2$

\begin{equation*} Q=\begin{pmatrix} 0. \amp 1.15 \amp 0 \amp 0 \amp 0 \amp 0.7 \amp 0 \amp \cdots \amp 0 \\ 0. \amp 0 \amp 0.6 \amp 1.1 \amp 0.0 \amp 0 \amp 0 \amp \cdots \amp 0 \\ 0. \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp \cdots \amp 0 \\ 0. \amp 1.2 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0.2 \amp \cdots \amp 0 \\ \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \\ \end{pmatrix} \end{equation*}

Itération 2: $\operatorname{argmax}_a Q(2,a)=4$

\begin{equation*} Q=\begin{pmatrix} 0. \amp 1.15 \amp 0 \amp 0 \amp 0 \amp 0.7 \amp 0 \amp \cdots \amp 0 \\ 0. \amp 0 \amp 0.6 \amp 1.15 \amp 0.0 \amp 0 \amp 0 \amp \cdots \amp 0 \\ 0. \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp \cdots \amp 0 \\ 0. \amp 1.2 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0.2 \amp \cdots \amp 0 \\ \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \\ \end{pmatrix} \end{equation*}

Itération 3: $\operatorname{argmax}_a Q(4,a)=2$

\begin{equation*} Q=\begin{pmatrix} 0. \amp 1.15 \amp 0 \amp 0 \amp 0 \amp 0.7 \amp 0 \amp \cdots \amp 0 \\ 0. \amp 0 \amp 0.6 \amp 1.1 \amp 0.0 \amp 0 \amp 0 \amp \cdots \amp 0 \\ 0. \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp \cdots \amp 0 \\ 0. \amp 1.025 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0.2 \amp \cdots \amp 0 \\ \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \\ \end{pmatrix} \end{equation*}

Itération 4: $\operatorname{argmax}_a Q(2,a)=4$

\begin{equation*} Q=\begin{pmatrix} 0. \amp 1.15 \amp 0 \amp 0 \amp 0 \amp 0.7 \amp 0 \amp \cdots \amp 0 \\ 0. \amp 0 \amp 0.6 \amp 0.9875 \amp 0.0 \amp 0 \amp 0 \amp \cdots \amp 0 \\ 0. \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp \cdots \amp 0 \\ 0. \amp 1.2 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0.2 \amp \cdots \amp 0 \\ \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \amp \cdots \\ \end{pmatrix} \end{equation*}

On voit que le processus va rester longtemps dans un cycle entre le noeud 2 et le noeud 4. Plus $\alpha$ sera proche de $1$ plus il risque de rester longtemps dans un cycle. On voit donc le défaut ici de la politique d'exploration gloutonne. De façon général la convergence du Q-learning est assurée que si mes états et actions sont tous exploré au moins une fois ce qui n'est pas assurée avec cette politique.

Subsubsection 8.2.3.2 Exploration par stochasticité

Le problème principal de l'exploration précédente est qu'on ne transite pas par l'ensemble des actions. On peut donc rester coincer dans une zone sans qu'elle soit optimale. Pour résoudre ce problème le choix naturel est d'exploré de façon aléatoire afin d'assurer a terme une transition par l'ensemble des actions. Le choix le plus simple est donc de prendre une politique purement aléatoire qui sera donnée par:

\begin{equation*} \pi_{a} (a \mid s) = \frac{1}{\mid A(s)\mid} \end{equation*}

avec $A(s)$ l'ensemble des actions possibles à partir de l'état $s\text{.}$ On a donc une loi uniforme sur les actions possible. Cette politique d'exploration est très peu utilisée en pratique. En effet on va converger très lentement. Cependant elle permet d'introduire la seconde politique d'exploration par stochasticité qui elle est très utilisée en pratique.

Définition 8.14. Politique d'exploratoire $\epsilon$-gloutonne.

La politique d'exploration dit $\epsilon$-gloutonne est donnée par

\begin{equation*} \pi (a \mid s) = (1-\epsilon_t) \pi_{g} (a \mid s) + \epsilon_t \pi_{a} (a \mid s) \end{equation*}

On voit donc que l'idée est simple. Il s'agit d'une combinaison convexe entre les deux lois précédente. Lorsque $\epsilon$ tends vers 1 on est proche d'une politique aléatoire et lorsque $\epsilon$ tends vers 0 on est proche d'une politique gloutonne. En général on utilise un $\epsilon_t$ variable durant l'algorithme. On part en général de $\epsilon_t \approx 1$ il descend progressivement jusqu`à zéro, ce que revient a explorer beaucoup au début puis on se dirigera de plus en plus vers le choix optimale d'action. Une autre façon de construire une politique paramètrique qui tend vers la politique gloutonen ou aléatoire est d'utilisée une fonction softmax (vu précédemment pour les ANN).

Définition 8.15. Politique d'exploratoire de Boltzmann.

La politique d'exploration dit de Boltzmann est donnée par

\begin{equation*} \pi(a\mid s) =\frac{\operatorname{exp}\left( \frac{1}{\beta}Q(s,a)\right) }{\sum_{a^{'}}\operatorname{exp}\left(\frac{1}{\beta}Q(s,a^{'})\right) } \end{equation*}

A la limite $\beta$ tends vers zéro on retrouve la politique gloutonne et à la limite $\beta$ très grand on retrouve la politique aléatoire.

Subsubsection 8.2.3.3 Exploration par motivation intrinsèque

L'idée ici vient du lien entre l'apprentissage machine et l'apprentissage Humain. L'idée c'est en plus de la motivation extérieur qui est de maximiser les recompenses, un agent peu avoir une motivation intrinséque/interne comme de la curiosité/l'attrait de la nouveauté etc et elle peut pousser l'agent à explorer de nouvelles régions. Pour cela lidée est assez simplement d'ajouter une recompense qui modélisera cette motivation intrinsèque. Il existe deux possibilités

Par modification des recompenses: dans le "Q-learning" par exemple on remplace la recompense classique $r(s_t,a_t)$ par la somme de cette recompense avec la nouvelle $r(s_t,a_t)+r^{+}(s_t,a_t)\text{.}$ C'est donc l'increment de l'algorithme qui est modifié.
Par modification de la selection d'action: $a_t = \operatorname{argmax}_a (Q(s_t,a) +r^{+}(s_t,a))$

Apprentissage et calcul scientifique