5.3. Processus de Décision de Markov
Les PDMs font appel à des concepts issus de la
théorie des probabilités et de la théorie de la
décision [85]. Ils mettent en place un cadre théorique qui permet
de définir une stratégie optimale pour un système en
interaction avec son environnement dont l'évolution dans le temps n'est
pas déterministe. Ils permettent la prise en compte de l'incertitude sur
l'effet d'une prise de décision.
Un Processus de Décision de Markov est défini
formellement par le quadruplet <S, A, T,
R> tel que :
47
Chapitre II : Etat de l'art
? S est l'ensemble fini d'états ;
? A est l'ensemble fini d'actions ;
? T : S ? A ? S ? [0, 1] est la fonction de
transition où T(s, a, s') est la probabilité pour un
agent de se trouver dans l'état s ES après qu'il a
effectué l'action a dans l'état s.
? R : S ? A ? S ?? est la fonction récompense
associée à chaque transition. R(s, a, s') =
E?rt+1?st=s, at=a, st+1=s? est
l'espérance mathématique de la fonction de renforcement
(récompense ou sanction) pour la transition d'un état s vers un
état s'.
Les fonctions R et T sont souvent
stochastiques et vérifient la propriété de Markov. Un PDM
vérifie la propriété de Markov [86], dans le sens
où la fonction de transition de l'environnement ne dépend que de
l'état précédent de l'agent ainsi que de l'action que
celui-ci vient d'exécuter. Cette propriété se traduit par
:
? s'?S, P?st+1=s'? st, at? = P?
st+1=s' ? st, at, st-1, at-1,....., s0, at,?, ce qui garantit que la
fonction de transition est indépendante de l'ensemble des états
et des actions passés de l'agent.
5.4. Résolution d'un PDM dans l'incertain
On appelle politique déterministe une fonction ? : S ?
A qui associe à chaque état observé, une action ?(s)
à effectuer. Cette politique détermine le comportement de
l'agent. D'une manière générale, on utilise des politiques
de Markov non déterministes, qui associent à chaque état s
et à chaque action a, la probabilité ? (s, a)
que l'agent choisisse l'action a suite à l'observation
s. La politique est donc définie par ?: S × A
? [0;1] (avec ?a?(s, a) =1).
La résolution d'un PDM consiste à trouver la
politique optimale ? qui maximise la récompense. Lorsque les fonctions T
et R sont connues, il est possible d'utiliser les techniques de la
programmation dynamique pour résoudre le PDM [87], [88]. Mais dans le
cas général, l'agent évolue au sein d'un environnement
dynamique et aléatoire et n'a donc pas accès à ces
fonctions. La résolution du PDM se situe alors dans le cadre de
l'apprentissage par renforcement [89].
L'une des techniques probablement les plus répandues
pour résoudre un PDM est le Q-learning [90]. Il s'agit d'apprendre
itérativement une fonction Q : S ×A ?? qui approxime la
fonction de récompense R du PDM. Les Q-valeurs Q(s, a)
sont utilisées pour mesurer la qualité de choisir une action
spécifique a dans un certain état s en fonction des
récompenses perçues. Initialement, Vs E S, Va E A
Q(s, a) = 0 et la politique de l'agent est pseudo-aléatoire.
À chaque pas de temps, l'agent effectue une action a = ?(s) suivant la
politique ? et modifie la valeur de Q par la règle de mise
à jour suivante :
48
Chapitre II : Etat de l'art
( s, a) t+1 = Q ( s, a) t + as. ( R ( s, a) t + y.
maxa { Q ( s , a)} -- Q ( s, a) t)
2.1
Le taux d'apprentissage as détermine dans
quelle mesure la nouvelle information doit être prise en compte (si
as = 0, l'agent n'apprend rien ; si as = 1, Q(s, a) ne
dépend que de la dernière récompense obtenue). Il
détermine ainsi la vitesse de convergence et la précision.
Le paramètre y joue le rôle d'un taux
d'intérêt, on désigne parfois ce paramètre par le
terme coefficient d'amortissement (discount) qui détermine
l'importance des récompenses futures : une récompense
reçue k unités de temps plus tard vaut seulement
yk-1 de ce qu'elle vaudrait au temps courant. Il pondère donc
les récompenses immédiates par rapport aux récompenses
retardées.
L'importance que l'on accorde aux récompenses futures
varie selon la valeur de y :
· Avec y-* 0, l'agent maximise les récompenses
immédiates, et si y= 0 l'agent apprend à choisir at afin de
maximiser seulement la récompense suivante rt+1
· Avec y-* 1, l'agent a un horizon de plus en plus
lointain, les récompenses futures ont plus d'importance.
Dans l'apprentissage par renforcement l'agent doit choisir la
stratégie à suivre: il peut explorer l'environnement ou exploiter
les états et les récompenses déjà connues. Un agent
qui apprend par renforcement ne connaît pas explicitement les actions
qu'il doit entreprendre. Il doit donc expérimenter toutes les actions
à sa disposition afin d'évaluer leurs qualités
respectives. Il explore alors activement son environnement de façon
à découvrir une politique optimale. Cette situation donne lieu au
problème du compromis exploration/exploitation, où il faut en
même temps chercher la politique optimale et avoir le meilleur gain
possible [90], [91].
5.4.1. La stratégies-greedy
Une approche souvent utilisée pour équilibrer le
dilemme exploration/exploitation est la méthode s-greedy [90] qui
définit des proportions fixes de temps pour explorer ou exploiter. Elle
utilise une action dite gloutonne (qui est la meilleure action
évaluée par la politique courante), une distribution uniforme de
probabilités et un s E [0, 1]. Cette stratégie choisit l'action
gloutonne avec une probabilité 1-s, et une autre action est
aléatoirement choisie (en utilisant une distribution uniforme) avec une
probabilité s. Le choix de l'action prochaine at est
donc :
argmaxaQ(s, a) avec probabilité 1--s
at =
2.2
action aléatoire avec probabilité s
49
Chapitre II : Etat de l'art
| 
