Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Apprendre Conditions d'Optimalité | Programmation Dynamique
Introduction à l'Apprentissage par Renforcement

bookConditions d'Optimalité

Dans le chapitre précédent, vous avez découvert les équations de Bellman pour les fonctions de valeur d’état et de valeur d’état-action. Ces équations décrivent comment les valeurs d’état peuvent être définies de manière récursive à partir des valeurs d’autres états, ces valeurs dépendant d’une politique donnée. Cependant, toutes les politiques ne sont pas aussi efficaces. En réalité, les fonctions de valeur établissent un ordre partiel entre les politiques, qui peut être décrit comme suit :

π≥π′  ⟺  vπ(s)≥vπ′(s)∀s∈S\pi \ge \pi' \iff v_\pi(s) \ge v_{\pi'}(s) \qquad \forall s \in S

Ainsi, la politique π\pi est meilleure ou égale à la politique π′\pi' si, pour tous les états possibles, le rendement espéré de la politique π\pi n’est pas inférieur à celui de la politique π′\pi'.

Note
Approfondir

Un ordre partiel suit les règles habituelles d’ordre mais n’impose pas la comparaison de chaque paire. Dans notre cas, nous ne pouvons classer deux politiques que si elles produisent les mêmes résultats, ou si l’une surpasse clairement l’autre. Dans tous les autres cas, les politiques restent incomparables.

Politique optimale

Note
Définition

Pour tout MDP, il existe au moins une politique qui est aussi bonne ou meilleure que toutes les autres politiques. Cette politique est appelée politique optimale π∗\pi_*. Bien qu'il puisse exister plusieurs politiques optimales, elles sont toutes notées π∗\pi_*.

Pourquoi une politique optimale existe-t-elle toujours ?

Vous vous demandez peut-être pourquoi une politique optimale existe toujours pour tout MDP. C'est une excellente question, et l'intuition derrière cela est étonnamment simple. Rappelez-vous que les états dans un MDP capturent entièrement la condition de l'environnement. Cela implique que chaque état est indépendant des autres : l'action choisie dans un état n'affecte pas les récompenses ou les résultats atteignables dans un autre. Par conséquent, en sélectionnant l'action optimale dans chaque état séparément, vous obtenez naturellement la meilleure séquence globale d'actions sur l'ensemble du processus. Et cet ensemble d'actions optimales dans chaque état constitue une politique optimale.

De plus, il existe toujours au moins une politique qui est à la fois optimale et déterministe. En effet, si pour un certain état ss, deux actions aa et a′a' produisent le même retour espéré, en choisir une seule n'affectera pas l'optimalité de la politique. Appliquer ce principe à chaque état rendra la politique déterministe tout en préservant son optimalité.

Fonctions de valeur optimales

Les politiques optimales partagent les mêmes fonctions de valeur — un fait qui devient évident lorsque l’on considère la manière dont les politiques sont comparées. Cela signifie que les politiques optimales partagent à la fois la fonction de valeur d’état et la fonction de valeur d’action.

De plus, les fonctions de valeur optimales possèdent leurs propres équations de Bellman qui peuvent être formulées sans référence à une politique spécifique. Ces équations sont appelées équations d’optimalité de Bellman.

Fonction de valeur d’état optimale

Note
Définition

La fonction de valeur d’état optimale V∗V_* (ou v∗v_*) représente le rendement espéré maximal atteignable à partir d’un certain état en suivant une politique optimale.

Elle peut être définie mathématiquement comme suit :

v∗(s)=max⁡πvπ(s)=E⁡π∗[Gt∣St=s]\def\E{\operatorname{\mathbb{E}}} v_*(s) = \max_\pi v_\pi(s) = \E_{\pi_*}[G_t | S_t = s]

L’équation d’optimalité de Bellman pour cette fonction de valeur peut être dérivée ainsi :

v∗(s)=∑aπ∗(a∣s)∑s′,rp(s′,r∣s,a)(r+γv∗(s′))=max⁡a∑s′,rp(s′,r∣s,a)(r+γv∗(s′))\begin{aligned} v_*(s) &= \sum_a \pi_*(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr)\\ &= \max_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr) \end{aligned}

Intuition

Comme vous le savez déjà, il existe toujours au moins une politique à la fois optimale et déterministe. Une telle politique sélectionnerait, pour chaque état, une action particulière qui maximise les retours attendus. Par conséquent, la probabilité de choisir cette action optimale serait toujours 1, et la probabilité de choisir toute autre action serait 0. Dans ce contexte, l’équation de Bellman d’origine n’a plus besoin de l’opérateur de sommation. Puisque l’on sait que la meilleure action sera toujours sélectionnée, il suffit de remplacer la somme par la prise du maximum sur l’ensemble des actions disponibles.

Fonction de valeur d'action optimale

Note
Définition

Fonction de valeur d'action optimale Q∗Q_* (ou q∗q_*) représente le rendement espéré maximal pouvant être obtenu en effectuant une certaine action dans un certain état, puis en suivant la politique optimale par la suite.

Elle peut être définie mathématiquement comme suit :

q∗(s,a)=max⁡πqπ(s,a)=E⁡π∗[Gt∣St=s,At=a]\def\E{\operatorname{\mathbb{E}}} q_*(s, a) = \max_\pi q_\pi(s, a) = \E_{\pi_*}[G_t | S_t = s, A_t = a]

Équation d'optimalité de Bellman pour cette fonction de valeur peut être dérivée ainsi :

q∗(s,a)=∑s′,rp(s′,r∣s,a)(r+γ∑a′π∗(a′∣s′)q∗(s′,a′))=∑s′,rp(s′,r∣s,a)(r+γmax⁡a′q∗(s′,a′))\begin{aligned} q_*(s, a) &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \sum_{a'} \pi_*(a' | s')q_*(s', a')\Bigr)\\ &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \max_{a'} q_*(s', a')\Bigr) \end{aligned}

Intuition

De manière similaire à la fonction de valeur d'état, la somme peut être remplacée par la prise d'un maximum sur toutes les actions disponibles.

question mark

Pourquoi une politique optimale existe-t-elle toujours pour tout processus de décision de Markov ?

Select the correct answer

Tout était clair ?

Comment pouvons-nous l'améliorer ?

Merci pour vos commentaires !

Section 3. Chapitre 3

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

bookConditions d'Optimalité

Glissez pour afficher le menu

Dans le chapitre précédent, vous avez découvert les équations de Bellman pour les fonctions de valeur d’état et de valeur d’état-action. Ces équations décrivent comment les valeurs d’état peuvent être définies de manière récursive à partir des valeurs d’autres états, ces valeurs dépendant d’une politique donnée. Cependant, toutes les politiques ne sont pas aussi efficaces. En réalité, les fonctions de valeur établissent un ordre partiel entre les politiques, qui peut être décrit comme suit :

π≥π′  ⟺  vπ(s)≥vπ′(s)∀s∈S\pi \ge \pi' \iff v_\pi(s) \ge v_{\pi'}(s) \qquad \forall s \in S

Ainsi, la politique π\pi est meilleure ou égale à la politique π′\pi' si, pour tous les états possibles, le rendement espéré de la politique π\pi n’est pas inférieur à celui de la politique π′\pi'.

Note
Approfondir

Un ordre partiel suit les règles habituelles d’ordre mais n’impose pas la comparaison de chaque paire. Dans notre cas, nous ne pouvons classer deux politiques que si elles produisent les mêmes résultats, ou si l’une surpasse clairement l’autre. Dans tous les autres cas, les politiques restent incomparables.

Politique optimale

Note
Définition

Pour tout MDP, il existe au moins une politique qui est aussi bonne ou meilleure que toutes les autres politiques. Cette politique est appelée politique optimale π∗\pi_*. Bien qu'il puisse exister plusieurs politiques optimales, elles sont toutes notées π∗\pi_*.

Pourquoi une politique optimale existe-t-elle toujours ?

Vous vous demandez peut-être pourquoi une politique optimale existe toujours pour tout MDP. C'est une excellente question, et l'intuition derrière cela est étonnamment simple. Rappelez-vous que les états dans un MDP capturent entièrement la condition de l'environnement. Cela implique que chaque état est indépendant des autres : l'action choisie dans un état n'affecte pas les récompenses ou les résultats atteignables dans un autre. Par conséquent, en sélectionnant l'action optimale dans chaque état séparément, vous obtenez naturellement la meilleure séquence globale d'actions sur l'ensemble du processus. Et cet ensemble d'actions optimales dans chaque état constitue une politique optimale.

De plus, il existe toujours au moins une politique qui est à la fois optimale et déterministe. En effet, si pour un certain état ss, deux actions aa et a′a' produisent le même retour espéré, en choisir une seule n'affectera pas l'optimalité de la politique. Appliquer ce principe à chaque état rendra la politique déterministe tout en préservant son optimalité.

Fonctions de valeur optimales

Les politiques optimales partagent les mêmes fonctions de valeur — un fait qui devient évident lorsque l’on considère la manière dont les politiques sont comparées. Cela signifie que les politiques optimales partagent à la fois la fonction de valeur d’état et la fonction de valeur d’action.

De plus, les fonctions de valeur optimales possèdent leurs propres équations de Bellman qui peuvent être formulées sans référence à une politique spécifique. Ces équations sont appelées équations d’optimalité de Bellman.

Fonction de valeur d’état optimale

Note
Définition

La fonction de valeur d’état optimale V∗V_* (ou v∗v_*) représente le rendement espéré maximal atteignable à partir d’un certain état en suivant une politique optimale.

Elle peut être définie mathématiquement comme suit :

v∗(s)=max⁡πvπ(s)=E⁡π∗[Gt∣St=s]\def\E{\operatorname{\mathbb{E}}} v_*(s) = \max_\pi v_\pi(s) = \E_{\pi_*}[G_t | S_t = s]

L’équation d’optimalité de Bellman pour cette fonction de valeur peut être dérivée ainsi :

v∗(s)=∑aπ∗(a∣s)∑s′,rp(s′,r∣s,a)(r+γv∗(s′))=max⁡a∑s′,rp(s′,r∣s,a)(r+γv∗(s′))\begin{aligned} v_*(s) &= \sum_a \pi_*(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr)\\ &= \max_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr) \end{aligned}

Intuition

Comme vous le savez déjà, il existe toujours au moins une politique à la fois optimale et déterministe. Une telle politique sélectionnerait, pour chaque état, une action particulière qui maximise les retours attendus. Par conséquent, la probabilité de choisir cette action optimale serait toujours 1, et la probabilité de choisir toute autre action serait 0. Dans ce contexte, l’équation de Bellman d’origine n’a plus besoin de l’opérateur de sommation. Puisque l’on sait que la meilleure action sera toujours sélectionnée, il suffit de remplacer la somme par la prise du maximum sur l’ensemble des actions disponibles.

Fonction de valeur d'action optimale

Note
Définition

Fonction de valeur d'action optimale Q∗Q_* (ou q∗q_*) représente le rendement espéré maximal pouvant être obtenu en effectuant une certaine action dans un certain état, puis en suivant la politique optimale par la suite.

Elle peut être définie mathématiquement comme suit :

q∗(s,a)=max⁡πqπ(s,a)=E⁡π∗[Gt∣St=s,At=a]\def\E{\operatorname{\mathbb{E}}} q_*(s, a) = \max_\pi q_\pi(s, a) = \E_{\pi_*}[G_t | S_t = s, A_t = a]

Équation d'optimalité de Bellman pour cette fonction de valeur peut être dérivée ainsi :

q∗(s,a)=∑s′,rp(s′,r∣s,a)(r+γ∑a′π∗(a′∣s′)q∗(s′,a′))=∑s′,rp(s′,r∣s,a)(r+γmax⁡a′q∗(s′,a′))\begin{aligned} q_*(s, a) &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \sum_{a'} \pi_*(a' | s')q_*(s', a')\Bigr)\\ &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \max_{a'} q_*(s', a')\Bigr) \end{aligned}

Intuition

De manière similaire à la fonction de valeur d'état, la somme peut être remplacée par la prise d'un maximum sur toutes les actions disponibles.

question mark

Pourquoi une politique optimale existe-t-elle toujours pour tout processus de décision de Markov ?

Select the correct answer

Tout était clair ?

Comment pouvons-nous l'améliorer ?

Merci pour vos commentaires !

Section 3. Chapitre 3
some-alt