Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Apprendre Amélioration de la Politique | Programmation Dynamique
Introduction à l'Apprentissage par Renforcement

bookAmélioration de la Politique

Note
Définition

Amélioration de la politique : processus d'amélioration de la politique à partir des estimations actuelles de la fonction de valeur.

Note
Remarque

Comme pour l'évaluation de la politique, l'amélioration de la politique peut utiliser la fonction de valeur d'état ou la fonction de valeur d'action. Cependant, pour les méthodes de programmation dynamique, la fonction de valeur d'état sera utilisée.

Maintenant que l'on peut estimer la fonction de valeur d'état pour n'importe quelle politique, une étape naturelle consiste à examiner s'il existe des politiques meilleures que l'actuelle. Une façon de procéder consiste à envisager de prendre une action différente aa dans un état ss, puis de suivre la politique actuelle par la suite. Si cela semble familier, c'est parce que cela ressemble à la définition de la fonction de valeur d'action :

qπ(s,a)=∑s′,rp(s′,r∣s,a)(r+γvπ(s′))q_\pi(s, a) = \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr)

Si cette nouvelle valeur est supérieure à la valeur d'état originale vπ(s)v_\pi(s), cela indique que choisir l'action aa dans l'état ss puis continuer avec la politique π\pi conduit à de meilleurs résultats que de suivre strictement la politique π\pi. Étant donné que les états sont indépendants, il est optimal de toujours sélectionner l'action aa chaque fois que l'état ss est rencontré. Par conséquent, il est possible de construire une politique améliorée π′\pi', identique à π\pi sauf qu'elle sélectionne l'action aa dans l'état ss, ce qui serait supérieur à la politique originale π\pi.

Théorème d'amélioration de la politique

Le raisonnement décrit ci-dessus peut être généralisé sous la forme du théorème d'amélioration de la politique :

qπ(s,π′(s))≥vπ(s)∀s∈S  ⟹  vπ′(s)≥vπ(s)∀s∈S\begin{aligned} &q_\pi(s, \pi'(s)) \ge v_\pi(s) \qquad &\forall s \in S\\ \implies &v_{\pi'}(s) \ge v_\pi(s) \qquad &\forall s \in S \end{aligned}

La démonstration de ce théorème est relativement simple et peut être réalisée par une substitution répétée :

vπ(s)≤qπ(s,π′(s))=E⁡π′[Rt+1+γvπ(St+1)∣St=s]≤E⁡π′[Rt+1+γqπ(St+1,π′(St+1))∣St=s]=E⁡π′[Rt+1+γE⁡π′[Rt+2+γvπ(St+2)]∣St=s]=E⁡π′[Rt+1+γRt+2+γ2vπ(St+2)∣St=s]...≤E⁡π′[Rt+1+γRt+2+γ2Rt+3+...∣St=s]=vπ′(s)\def\E{\operatorname{\mathbb{E}}} \begin{aligned} v_\pi(s) &\le q_\pi(s, \pi'(s))\\ &= \E_{\pi'}[R_{t+1} + \gamma v_\pi(S_{t+1}) | S_t = s]\\ &\le \E_{\pi'}[R_{t+1} + \gamma q_\pi(S_{t+1}, \pi'(S_{t+1})) | S_t = s]\\ &= \E_{\pi'}[R_{t+1} + \gamma \E_{\pi'}[R_{t+2} + \gamma v_\pi(S_{t+2})] | S_t = s]\\ &= \E_{\pi'}[R_{t+1} + \gamma R_{t+2} + \gamma^2 v_\pi(S_{t+2}) | S_t = s]\\ &...\\ &\le \E_{\pi'}[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s]\\ &= v_{\pi'}(s) \end{aligned}

Stratégie d'amélioration

Bien que la mise à jour des actions pour certains états puisse conduire à des améliorations, il est plus efficace de mettre à jour les actions pour tous les états simultanément. Plus précisément, pour chaque état ss, sélectionner l'action aa qui maximise la valeur d'action qπ(s,a)q_\pi(s, a) :

π′(s)←arg max⁡aqπ(s,a)←arg max⁡a∑s′,rp(s′,r∣s,a)(r+γvπ(s′))\begin{aligned} \pi'(s) &\gets \argmax_a q_\pi(s, a)\\ &\gets \argmax_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr) \end{aligned}

où arg max⁡\argmax (abréviation de argument du maximum) est un opérateur qui retourne la valeur de la variable qui maximise une fonction donnée.

La politique gloutonne résultante, notée π′\pi', satisfait les conditions du théorème d'amélioration de politique par construction, garantissant que π′\pi' est au moins aussi bonne que la politique originale π\pi, et généralement meilleure.

Si π′\pi' est aussi bonne que, mais pas meilleure que π\pi, alors π′\pi' et π\pi sont toutes deux des politiques optimales, car leurs fonctions de valeur sont égales et satisfont l'équation d'optimalité de Bellman :

vπ(s)=max⁡a∑s′,rp(s′,r∣s,a)(r+γvπ(s′))v_\pi(s) = \max_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr)
question mark

Comment l'adoption d'une politique gloutonne garantit-elle une amélioration par rapport à la politique précédente ?

Select the correct answer

Tout était clair ?

Comment pouvons-nous l'améliorer ?

Merci pour vos commentaires !

Section 3. Chapitre 5

Demandez à l'IA

expand

Demandez à l'IA

ChatGPT

Posez n'importe quelle question ou essayez l'une des questions suggérées pour commencer notre discussion

Awesome!

Completion rate improved to 2.7

bookAmélioration de la Politique

Glissez pour afficher le menu

Note
Définition

Amélioration de la politique : processus d'amélioration de la politique à partir des estimations actuelles de la fonction de valeur.

Note
Remarque

Comme pour l'évaluation de la politique, l'amélioration de la politique peut utiliser la fonction de valeur d'état ou la fonction de valeur d'action. Cependant, pour les méthodes de programmation dynamique, la fonction de valeur d'état sera utilisée.

Maintenant que l'on peut estimer la fonction de valeur d'état pour n'importe quelle politique, une étape naturelle consiste à examiner s'il existe des politiques meilleures que l'actuelle. Une façon de procéder consiste à envisager de prendre une action différente aa dans un état ss, puis de suivre la politique actuelle par la suite. Si cela semble familier, c'est parce que cela ressemble à la définition de la fonction de valeur d'action :

qπ(s,a)=∑s′,rp(s′,r∣s,a)(r+γvπ(s′))q_\pi(s, a) = \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr)

Si cette nouvelle valeur est supérieure à la valeur d'état originale vπ(s)v_\pi(s), cela indique que choisir l'action aa dans l'état ss puis continuer avec la politique π\pi conduit à de meilleurs résultats que de suivre strictement la politique π\pi. Étant donné que les états sont indépendants, il est optimal de toujours sélectionner l'action aa chaque fois que l'état ss est rencontré. Par conséquent, il est possible de construire une politique améliorée π′\pi', identique à π\pi sauf qu'elle sélectionne l'action aa dans l'état ss, ce qui serait supérieur à la politique originale π\pi.

Théorème d'amélioration de la politique

Le raisonnement décrit ci-dessus peut être généralisé sous la forme du théorème d'amélioration de la politique :

qπ(s,π′(s))≥vπ(s)∀s∈S  ⟹  vπ′(s)≥vπ(s)∀s∈S\begin{aligned} &q_\pi(s, \pi'(s)) \ge v_\pi(s) \qquad &\forall s \in S\\ \implies &v_{\pi'}(s) \ge v_\pi(s) \qquad &\forall s \in S \end{aligned}

La démonstration de ce théorème est relativement simple et peut être réalisée par une substitution répétée :

vπ(s)≤qπ(s,π′(s))=E⁡π′[Rt+1+γvπ(St+1)∣St=s]≤E⁡π′[Rt+1+γqπ(St+1,π′(St+1))∣St=s]=E⁡π′[Rt+1+γE⁡π′[Rt+2+γvπ(St+2)]∣St=s]=E⁡π′[Rt+1+γRt+2+γ2vπ(St+2)∣St=s]...≤E⁡π′[Rt+1+γRt+2+γ2Rt+3+...∣St=s]=vπ′(s)\def\E{\operatorname{\mathbb{E}}} \begin{aligned} v_\pi(s) &\le q_\pi(s, \pi'(s))\\ &= \E_{\pi'}[R_{t+1} + \gamma v_\pi(S_{t+1}) | S_t = s]\\ &\le \E_{\pi'}[R_{t+1} + \gamma q_\pi(S_{t+1}, \pi'(S_{t+1})) | S_t = s]\\ &= \E_{\pi'}[R_{t+1} + \gamma \E_{\pi'}[R_{t+2} + \gamma v_\pi(S_{t+2})] | S_t = s]\\ &= \E_{\pi'}[R_{t+1} + \gamma R_{t+2} + \gamma^2 v_\pi(S_{t+2}) | S_t = s]\\ &...\\ &\le \E_{\pi'}[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s]\\ &= v_{\pi'}(s) \end{aligned}

Stratégie d'amélioration

Bien que la mise à jour des actions pour certains états puisse conduire à des améliorations, il est plus efficace de mettre à jour les actions pour tous les états simultanément. Plus précisément, pour chaque état ss, sélectionner l'action aa qui maximise la valeur d'action qπ(s,a)q_\pi(s, a) :

π′(s)←arg max⁡aqπ(s,a)←arg max⁡a∑s′,rp(s′,r∣s,a)(r+γvπ(s′))\begin{aligned} \pi'(s) &\gets \argmax_a q_\pi(s, a)\\ &\gets \argmax_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr) \end{aligned}

où arg max⁡\argmax (abréviation de argument du maximum) est un opérateur qui retourne la valeur de la variable qui maximise une fonction donnée.

La politique gloutonne résultante, notée π′\pi', satisfait les conditions du théorème d'amélioration de politique par construction, garantissant que π′\pi' est au moins aussi bonne que la politique originale π\pi, et généralement meilleure.

Si π′\pi' est aussi bonne que, mais pas meilleure que π\pi, alors π′\pi' et π\pi sont toutes deux des politiques optimales, car leurs fonctions de valeur sont égales et satisfont l'équation d'optimalité de Bellman :

vπ(s)=max⁡a∑s′,rp(s′,r∣s,a)(r+γvπ(s′))v_\pi(s) = \max_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr)
question mark

Comment l'adoption d'une politique gloutonne garantit-elle une amélioration par rapport à la politique précédente ?

Select the correct answer

Tout était clair ?

Comment pouvons-nous l'améliorer ?

Merci pour vos commentaires !

Section 3. Chapitre 5
some-alt