[PDF] [PDF] Décision dans lincertain - Cours 10: Décisions - LAMSADE

[PDF] Introduction aux décisions et processus décisionnels (1) 1

Décision et processus décisionnels - Bernard ESPINASSE - 1 Introduction aux D3 : La cour doit décider si un accusé est coupable ou non : ▫ Il y a 2 erreurs 

[PDF] Les Décisions et le processus de décision

Décisions et Processus de décisions L'analyse des décisions et des processus décisionnels permet d'identifier les logiques projet au cours d'un Conseil 

[PDF] Les théories et la prise de décision

Ce cours est organisé en trois axes: I- les différents constitue l'essence même du processus de direction Le processus de décision de H Simon (appelé «

[PDF] Comprendre le processus décisionnel stratégique à - HEC Montréal

Evolution du processus décisionnel stratégique relatif à une mise en oeuvre d' environnementaux (internes et externes) qui peuvent se produire en cours de

[PDF] Le processus décisionnel

Le processus décisionnel Les personnes qui contribuent à trouver une solution ont plus de chances d'appuyer la décision Les décisions, particulièrement 

[PDF] 1 Le processus de décision dans une approche - Ce document est

comprendre la m anière dont les relations entre acteurs se nouent au cours du processus de décision Le chapitre 2 précise le contexte organi sationnel dans 

Les fondements institutionnels du processus décisionnel de la Cour

Morel, F (1986) Les fondements institutionnels du processus décisionnel de la Cour supérieure et de la Commission des affaires sociales Les Cahiers de droit  

[PDF] Lentreprise, un centre de décisions - OECONOMIA

l'incidence d'une décision ou au processus décisionnel 1 terme qui engagent l'entreprise sur plusieurs exercices (ces décisions sont la plupart du temps 

[PDF] Décision dans lincertain - Cours 10: Décisions - LAMSADE

Cours 10: Décisions séquentielles - PDM– (Stéphane Airiau) Processus de décision Un Processus décisionnel de Markov est un tuple S,A,T,R,γ où S est un 

[PDF] la caricature sous la révolution française

[PDF] charge virale définition

[PDF] charge virale normale

[PDF] charge virale 20 copies/ml

[PDF] mon assureur ne veut plus m'assurer que faire

[PDF] un long dimanche de fiancailles résumé film

[PDF] aucune assurance ne veut assurer ma voiture

[PDF] mon assurance me résilie que faire

[PDF] aucune assurance auto ne veut m'assurer

[PDF] refus d'assurance auto

[PDF] refus d'assurance habitation

[PDF] bct assurance auto

[PDF] trouver une assurance habitation après résiliation par l'assureur

[PDF] définition de l'encadrement d'une équipe

[PDF] made in vietnam livre resume

Processus de décision markovien

Cours 10: Décisions séquentielles - PDM

Stéphane Airiau

Université Paris-Dauphine

Cours 10: Décisions séquentielles - PDM- (Stéphane Airiau)

Pr ocessusde décision markovien 1

PDM

Définition(Processus décisionnel de Markov)

UnProcessus décisionnel de Markovest un tuple⟨S,A,T,R,

⟩oùSest un ensemble fini d"étatsAest un ensemble fini d"actionsTest une matrice de transition

T ass′=P?St+1=s′?St=s,At=a]probabilité d"arriver dans l"état s" à l"instant+1 quand on a pris l"actionadans l"étatsà l"instanttRest le vecteur de récompenses R as=E[Rt+1?St=s,At=a]valeur moyenne obtenue après avoir pris l"actionadans l"étatsun ensemble d"état initial parfois un ensemble d"états terminaux Cours 10: Décisions séquentielles - PDM- (Stéphane Airiau)

Pr ocessusde décision markovien 2

Les composants d"un agent : politique

C"est ce qui gouverne le comportement de l"agent

politique déterministe: La fonction associe à chaque étatune action ?S↦ASTART-1+1

1234123

←politique optimale pour un pénalité de 0.03 par déplacement Cours 10: Décisions séquentielles - PDM- (Stéphane Airiau)

Pr ocessusde décision markovien 3

Focus pour le cours

problèmes itératifs en continue. objectif : maximiser la somme "avec dévaluation"Gt=∞ k=0 krt+k+1Pour éviter une récompense infinie si on tombe dans des cycles Le futur reste uncertain! Bon compromis entre court et long terme

Tendance naturelle vers le court terme

Mathématiquement, c"est quand même pratique! la fonction de transition est stochastique la fonction de récompense est connue

Comment trouver la meilleure politique?

Cours 10: Décisions séquentielles - PDM- (Stéphane Airiau)

Pr ocessusde décision markovien 4

Evaluation

On va s"aider de deux quantités

v ⋆(s)quelle est la valeur de me trouver dans l"étatspuis de continuer avec la politique optimale q ⋆(s,a)quelle est la valeur de prendre l"actionadans l"état spuis de continuer avec la politique optimale ⋆(s)politique optimale pour l"état s(i.e. quelle est la meilleure action). Cours 10: Décisions séquentielles - PDM- (Stéphane Airiau)

Pr ocessusde décision markovien 5

Valeur optimale d"un étatv⋆(s)on calcule la valeur espérée en supposant qu"on suive la politique

optimaleon prend la moyenne pondérée des récompenses escomptée

ëcomme dans expectimax!

v ⋆(s)=maxa?Aq⋆(s,a) q ⋆(s,a)=Ras+ s ′?STass′v⋆(s′) donc v ⋆(s)=maxa?A?Ras+ s

′?STass′v⋆(s′)?Cours 10: Décisions séquentielles - PDM- (Stéphane Airiau)Pr ocessusde décision markovien 6

Idée d"itération sur les valeurs

Cours 10: Décisions séquentielles - PDM- (Stéphane Airiau)

Pr ocessusde décision markovien 7

Value Iteration

1for eachs?Sandk?N

2V k(s)←0

34repeat fork=0to...

56for eachs?S

78V
k+1(s)←maxa?A?Ras+ s ′?STass′Vk(s′)?/* mise à jour */

910untilconvergenceCours 10: Décisions séquentielles - PDM- (Stéphane Airiau)Pr ocessusde décision markovien 8

Value Iteration - plus efficace pour la mémoire

1for eachs?S

2V(s)←0

34repeat

56for eachs?S

78V(s)←maxa?A?Ras+

s ′?STass′V(s′)?/* mise à jour */

910untilconvergenceCours 10: Décisions séquentielles - PDM- (Stéphane Airiau)Pr ocessusde décision markovien 9

Value Iteration - avec test de convergence

1for eachs?S

2V(s)←0

34repeat

5←0/* mesure le plus grand changement */

6for eachs?S

7v←V(s)/* sauvegarde l"ancienne valeur pour mesurer le changement */

8V(s)←maxa?A?Ras+

s ′?STass′V(s′)?/* mise à jour */

9←max(,?v-V(s)?)/* mise à jour du plus grand changement*/

10until

On a un théorème de convergence

Cours 10: Décisions séquentielles - PDM- (Stéphane Airiau)

Pr ocessusde décision markovien 10

Itération sur les valeurs :k=0r=0

=0.9

bruit=0.2Cours 10: Décisions séquentielles - PDM- (Stéphane Airiau)Pr ocessusde décision markovien 11

Itération sur les valeurs :k=1r=0

=0.9

bruit=0.2Cours 10: Décisions séquentielles - PDM- (Stéphane Airiau)Pr ocessusde décision markovien 12

Itération sur les valeurs :k=2r=0

=0.9

bruit=0.2Cours 10: Décisions séquentielles - PDM- (Stéphane Airiau)Pr ocessusde décision markovien 13

Itération sur les valeurs :k=3r=0

=0.9

bruit=0.2Cours 10: Décisions séquentielles - PDM- (Stéphane Airiau)Pr ocessusde décision markovien 14

Itération sur les valeurs :k=4r=0

=0.9

bruit=0.2Cours 10: Décisions séquentielles - PDM- (Stéphane Airiau)Pr ocessusde décision markovien 15

Itération sur les valeurs :k=5r=0

=0.9

bruit=0.2Cours 10: Décisions séquentielles - PDM- (Stéphane Airiau)Pr ocessusde décision markovien 16

Itération sur les valeurs :k=6r=0

=0.9

bruit=0.2Cours 10: Décisions séquentielles - PDM- (Stéphane Airiau)Pr ocessusde décision markovien 17

Itération sur les valeurs :k=7r=0

=0.9

bruit=0.2Cours 10: Décisions séquentielles - PDM- (Stéphane Airiau)Pr ocessusde décision markovien 18

Itération sur les valeurs :k=100r=0

=0.9

bruit=0.2Cours 10: Décisions séquentielles - PDM- (Stéphane Airiau)Pr ocessusde décision markovien 19

Limitations de Value Iteration

la méthode est lente la valeur du max change rarement

ëpourtant c"est cela qui va aider à changer toutes les valeurs!les valeurs peuvent mettre longtems à converger exactement alors

que la politique, elle, est déjà optimale depuis longtemps

ëon va essayer de travailler sur la politique.Cours 10: Décisions séquentielles - PDM- (Stéphane Airiau)Pr ocessusde décision markovien 20

Fonctions de valeurs

Similairement à la fonction optimale, on peut définir deux fonctions de valeurs pour une politique fixée.Définition(fonction de valeurs pour les états) Lafonction de valeurs pour les états v(s)d"un PDM est la valeur espérée de gains en partant dans l"étatset en poursuivant la poli- tique.Définition(fonction de valeurs pour les paires (état, action)) Lafonction de valeurs pour les paires état-actions q(s,a)d"un PDM est la valeur espérée de gains en partant dans l"états, en effec-

tuant l"actiona puiset en poursuivant la politique.Cours 10: Décisions séquentielles - PDM- (Stéphane Airiau)Pr ocessusde décision markovien 21

Equation de Bellman : pour les états

Dans l"étatson tire notre action avec la politique(s)pour chaque action, on choisit l"actionaavec la probabilité(a?s),on va effectuer l"actionapuis continuer avecdans l"état suivant

ëon peut utiliserq!

v (s)=E[rt+1+ v(St+1)?St=s]

a?A(a?s)q(s,a)Cours 10: Décisions séquentielles - PDM- (Stéphane Airiau)Pr ocessusde décision markovien 22

Equation de Bellman : pour les actions

Similairement pour la fonction de valeurs pour les actions le modèle de récompense nous donne la récompense pour avoir effectué l"actionadans l"états.le modèle de transition nous donne l"état suivants′ ëdans ce nouvel états′, on peut utiliserv! q (s,a)=E[rt+1+ q(St+1,At+1)?St=s,At=a] =Ras+ s

′?STass′v(s′)Cours 10: Décisions séquentielles - PDM- (Stéphane Airiau)Pr ocessusde décision markovien 23

Equation de Bellman

On a établi :

v (s)=? a?A(a?s)q(s,a) q (s,a)=Ras+ s ′?STass′v(s′)

Ensemble on obtient :

v (s)=? a?A(a?s)?Ras+ s ′?STass′v(s′)? q (s,a)=Ras+ s ′?STass′? a

′?A(a′?s′)q(s′,a′)Cours 10: Décisions séquentielles - PDM- (Stéphane Airiau)Pr ocessusde décision markovien 24

Equation de Bellman

v (s)=? a?A(a?s)?Ras+ s ′?STass′v(s′)? a?A(a?s)Ras+ a?A? s ′?S(a?s)Tass′v(s′) a?A(a?s)Ras+ s ′?S? a?A(a?s)Tass′v(s′) =Rs+ s ′?STss′v(s′)

On peut donc écrire l"expression vectorielle

v =R+

TvCours 10: Décisions séquentielles - PDM- (Stéphane Airiau)Pr ocessusde décision markovien 25

Evaluation d"une politique fixéeOn peut utiliser l"équation de Bellman comme une règle de mise à jour :

v k+1(s)←? a?A(a?s)?Ras+ s

La séquence{vk}k?Nconverge versv.Seconde idée : sans les max, les équations de Bellman forment un système

linéaire à résoudre! Cours 10: Décisions séquentielles - PDM- (Stéphane Airiau)

Pr ocessusde décision markovien 26

Convergence plus rapide

Pour réaliser l"algorithme :

avoir deux vecteurvoldetvnewcalculer completementvnewà partir devold

ë"full back up"

On peut aussi n"utiliser qu"un seulvecteuron remplace directement l"ancienne entrée par la nouvelle

le vecteurvcontient à la fois des nouvelles et des anciennes valeurs

ëon utilise les nouvelles valeurs au plus vite

convergence toujours garantie et plus rapide l"ordre de mise à jour joue un rôle sur la vitesse de convergence. Critère d"arrêt de l"algorithmegarantie de convergence à la limite en pratique, on peut arrêter avant

par exemple : maxs?S?vk+1(s)-vk(s)?

Comment déterminer une bonne action à partir dev?Supposons qu"on connaise les valeurs optimalesv⋆(s)Comment devons-nous agir?

On doit faire une étape d"expectimax!

⋆(s)=argmaxa?Ras+ s ′Tass′v⋆(s′)?

ëon peut appeler cette étape faire une extraction de politique.Cours 10: Décisions séquentielles - PDM- (Stéphane Airiau)Pr ocessusde décision markovien 28

Comment déterminer une bonne action à partir deq?Supposons qu"on connaise les valeurs optimalesq⋆(s,a)Comment devons-nous agir?

Trivial, on choisit la meilleure action! (ou une des meilleurs actions). ⋆(s)=argmaxaq?(s,a) ëmorale de l"histoire : les actions sont plus faciles à obtenir à partir deq

qu"à partir dev!!Cours 10: Décisions séquentielles - PDM- (Stéphane Airiau)Pr ocessusde décision markovien 29

Améliorer une politique

On peut essayer d"améliorer la politique en se comportant de manière "gloutonne" Une foisvévaluée : on peut calculerq(s,a)=Ras+ s ′?STass′v(s′)siq(s,a)>v(s): on a trouvé une amélioration!a ëon peut regarder tous les étatss?Set mettre à jour la politique ′(s)=argmaxa?Aq(s,a) Si aucune amélioration n"est trouvée, on a doncv=v′

ëv′=maxa?ARas+

On reconnait là l"équation de Bellman pour la fonction de valeursoptimale

On a donc trouvév⋆=v′!a.il faut une petite démonstration sur ce point Cours 10: Décisions séquentielles - PDM- (Stéphane Airiau)Pr ocessusde décision markovien 30

Itération de politique

L"idée est donc d"alterner

1- l"évaluation d"une politique 2- l"amélioration de la politique jusqu"à ce qu"on converge vers une politique qui sera la politique optimale. Pour les politiques deterministes, il y a un nombre fini de politiques, on va converger en un nombre fini d"itérations.

Variantes : quand arrêter l"évaluation?convergence à unprèsaprèskitérations (ka une petite valeur)pourquoi pas après chaque itération?

Cours 10: Décisions séquentielles - PDM- (Stéphane Airiau)

Pr ocessusde décision markovien 31

Comparaison

Les deux méthodes calcule le même résultat : à la fin, on a les mêmes valeurs optimales (v⋆etq⋆)Itération sur les valeurs la politique est implicite. A chaque itération, on met à jour les valeurs si on travaille avecv, on doit utiliser l"extraction d"une politique pour obtenir la politique optimale.Iteration sur les politiques plusieurs itérations pour mettre à jour les valeurs d"une politique fixe (mais pour chaque itération, on ne considère qu"une seule action, ce qui devrait être rapide).on met à jour la politique, on doit comparer toutes les actions (peut être lent)soit on améliore la politique, soit on a terminé! Cours 10: Décisions séquentielles - PDM- (Stéphane Airiau)

Pr ocessusde décision markovien 32

quotesdbs_dbs44.pdfusesText_44