Comment les fonctions de valeur afterstate sont-elles définies mathématiquement?

Question

Dans cette réponse , les fonctions de valeur afterstate sont mentionnées, et que les méthodes de différence temporelle (TD) et Monte Carlo (MC) peuvent également utiliser ces fonctions de valeur. Mathématiquement, comment ces fonctions de valeur sont-elles définies? Oui, ils sont fonction de l'état suivant, mais quelle est l'équation de Bellman ici? Est-il simplement défini comme$v(s') = \mathbb{E}\left[ R_t \mid S_t = s, A_t = a, S_{t+1} = s' \right]$? Si oui, comment pouvons-nous le définir en termes d'état,$v(s)$, et état-action, $q(s, a)$, des fonctions de valeur ou comme une équation de Bellman (récursive)?

Le livre de Sutton & Barto (2e édition) décrit de manière informelle les fonctions de valeur afterstate dans la section 6.8 , mais ils ne fournissent pas de définition formelle (c'est-à-dire l'équation de Bellman en termes de récompense ou d'autres fonctions de valeur), c'est pourquoi je pose cette question.

Answer 1

Sur la base de ceci et de ces ressources, permettez-moi de donner une réponse à ma propre question, mais, essentiellement, je vais simplement réécrire le contenu de la première ressource ici, à des fins de reproductibilité, avec quelques modifications mineures de la notation (pour être cohérent avec Sutton & Livre de Barto, 2e édition). Notez que je ne suis pas tout à fait sûr que cette formulation soit universelle (c'est-à-dire qu'il existe peut-être d'autres façons de la formuler), mais le contenu de la première ressource semble être cohérent avec le contenu de la deuxième ressource .

Installer

Supposons que nous ayons un MDP à horizon infini

$$\mathcal{M} = (\mathcal{S}, \mathcal{Y}, \mathcal{A}, \mathcal{T}, \mathcal{R}, \gamma),$$ où

• $\mathcal{S}$ est l'ensemble des états
• $\mathcal{Y} \subseteq \mathcal{S}$est l'ensemble des états d' après (aka états post-décision ou états "fin de période" [ 1 ], qui peuvent également être écrits comme états d'après )
• $\mathcal{A}$ est l'ensemble des actions
• $\mathcal{T}$ est la fonction de transition
• $\mathcal{R}$ est la fonction de récompense
• $\gamma$ est un facteur de remise

Laisser

• $y \in \mathcal{Y}$ être un après-état
• $f: \mathcal{S} \times \mathcal{A} \rightarrow \mathcal{Y}$être une fonction déterministe (des paires état-action aux états arrière), nous avons donc$f(s, a) = y$

La fonction de transition $\mathcal{T}$ pour $\mathcal{M}$ est défini comme

\begin{align} \mathcal{T}(s, a, s^{\prime}) &\doteq P ( s^{\prime} \mid f(s, a)) \\ &= P ( s^{\prime} \mid y) \end{align}

Une transition est composée de 2 étapes

1. une étape déterministe, où nous appliquons la fonction déterministe $f(s, a) = y$, qui dépend d'une action $a$ pris en l'état $s$, suivi par
2. une étape stochastique, où nous appliquons la distribution de probabilité $P (s^{\prime} \mid y)$, qui ne dépend pas de l'action $a$ plus, mais seulement sur $y$

Donc, j'ai désigné les États-Unis avec une lettre différente, $y$, parce que les états arrière sont atteints avec une fonction déterministe $f$, tandis que d'autres États, $s$ ou $s'$, sont atteints avec $P$.

Après avoir agi $a$ dans l'état $s$, nous obtenons une récompense (c'est-à-dire que nous obtenons une récompense à l'étape 1), mais nous n'obtenons pas de récompense après l'étape stochastique (étant donné qu'aucune action n'est entreprise).

Ainsi, nous pouvons définir la fonction de récompense $\mathcal{R}$ pour ce MDP comme suit

$$ \mathcal{R} (s, a, s^{\prime} ) \doteq \mathcal{R}(s, a) $$

La situation est illustrée par le schéma suivant

Alors, ici, $P$est la fonction de transition stochastique (c'est-à-dire une distribution de probabilité) telle qu'utilisée ci-dessus. Notez que, ici,$r_t$ est une réalisation spécifique de $R_t$ (la variable aléatoire) dans les formules ci-dessous.

Fonction de valeur d'état

Rappelons la définition de la fonction de valeur d'état $v_\pi(s)$ pour une politique donnée $\pi$ (tel que défini dans Sutton & Barto, section 3.5)

\begin{align} v_{\pi}(s) &\doteq \mathbb{E}_{\pi}\left[G_{t} \mid S_{t}=s\right] \\ &= \mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} \gamma^{k} R_{t+k+1} \mid S_{t}=s\right], \end{align} pour tous $s \in \mathcal{S}$ et

\begin{align} G_{t} &\doteq \sum_{k=0}^{\infty} \gamma^{k} R_{t+k+1} \\ &= R_{t+1} + \gamma R_{t+2} + \gamma^{2} R_{t+3}+ \cdots \\ &= \mathcal{R}(s_t, a_t) + \gamma \mathcal{R}(s_{t+1}, a_{t+1})+\gamma^{2} \mathcal{R}(s_{t+2}, a_{t+2}) +\cdots, \end{align} où $\pi(s_t) = a_t$ et $\mathcal{R}(s_t, a_t) = R_{t+1}$, pour $t=0, 1, 2, \dots$. (Alors, notez que$\mathcal{R} \neq R_t$: la première est la fonction de récompense, tandis que la seconde est une variable aléatoire qui représente la récompense reçue après avoir agi $a_t$ au pas $s_t$)

La fonction de valeur d'état optimale est définie comme

$$ v_{*}(s) \doteq \max _{\pi} v_{\pi}(s) $$

Fonction de valeur après-état

De même, nous définirons la fonction de valeur afterstate, mais nous utiliserons la lettre $w$ juste pour le différencier de $v$ et $q$.

\begin{align} w_{\pi}\left(y\right) &\doteq \mathbb{E}_{\pi}\left[G_{t+1} \mid Y_{t}=y\right] \\ &= \mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} \gamma^{k} R_{t+k+2} \mid Y_{t}=y\right] \\ &= \mathbb{E}_{\pi}\left[ R_{t+2} + \gamma R_{t+3}+\gamma^{2} R_{t+4} + \cdots \mid Y_{t}=y\right] \\ &= \mathbb{E}_{\pi}\left[ \mathcal{R}(s_{t+1}, a_{t+1})+\gamma \mathcal{R}(s_{t+2}, a_{t+2}) + \gamma^{2} \mathcal{R}(s_{t+3}, a_{t+3}) + \cdots \mid Y_{t}=y\right] , \end{align} où $\mathcal{R}(s_{t+1}, a_{t+1}) = R_{t+2}$, pour tous $t$.

En d'autres termes, la valeur d'un afterstate $y$ (au pas de temps $t$, ie donné $Y_t = y$) est définie comme l'attente du retour à partir de l'état dans lequel vous vous êtes retrouvé après l' après -État$y$.

Cela me semble raisonnable et est similaire à ma proposition de définition de la fonction de valeur après-état dans la question, même si je ne considérais aucune fonction déterministe dans une formulation potentielle, et je ne pensais pas non plus aux états afters comme des états intermédiaires , atteints par une étape déterministe, entre les états habituels.

De la même manière que pour la fonction de valeur d'état optimale, nous définissons également la fonction de valeur optimale après-état

$$ w_{*}(y) \doteq \max _{\pi} w_{\pi}(y) $$

Fonction de valeur après-état définie en termes de fonction de valeur d'état

Nous pouvons définir la fonction de valeur afterstate en termes

$$ w_{*}(y) = \sum_{s^{\prime}} P (s^{\prime} \mid y ) v_{*} ( s^{\prime} ) $$ En d'autres termes, $w_{*}(y)$ est défini comme une attente sur la valeur des prochains états possibles $s'$ de l'arrière-état $y$.

Cela semble correct et conforme aux définitions ci-dessus.

Plus d'équations

Dans ceci et dans ces ressources, la fonction de valeur d'état est également définie en termes de fonction de valeur afterstate comme suit

$$v_{*}(s)=\max_{a}\left(\mathcal{R}(s, a)+\gamma w_{*}(f(s, a))\right)$$

L' équation de Bellman pour la fonction de valeur afterstate (à partir de laquelle une règle de mise à jour peut être dérivée) est donnée par

$$ w_{*}(y) = \sum_{s^{\prime}} P(s^{\prime} \mid y ) \max_{a} ( \mathcal{R} (s^{\prime}, a) + \gamma w_{*}(f ( s^{\prime}, a ))), $$ qui est vraiment similaire à l'équation de Bellman pour la fonction de valeur d'état.

Enfin, nous pouvons également exprimer la fonction de valeur état-action en termes de fonction de valeur afterstate

$$ q_\pi(s_t, a_t) = \mathcal{R}\left(s_{t}, a_{t}\right)+\gamma w_{\pi}\left(f\left(s_{t}, a_{t}\right)\right) $$

Étant donné que cette réponse est déjà assez longue, consultez la ressource pour plus de détails (y compris un algorithme basé sur l'équation de Bellman d'après-état).

la mise en oeuvre

Si vous êtes le type de personne qui comprend les concepts en regardant le code, alors ce projet Github , qui implémente une méthode de Monte Carlo qui utilise afterstates pour jouer au tic-tac-toe, peut être utile. Les Afterstates sont utiles dans le tic-tac-toe car il s'agit d'un jeu à 2 joueurs, où deux agents agissent à tour de rôle, afin que nous puissions estimer l'action à entreprendre de manière déterministe (comme si c'était le$f$ ci-dessus) avant que l'autre agent ne prenne une action (de manière probabiliste), au moins, c'est mon interprétation actuelle de l'utilité des afterstates dans ce jeu (et des jeux / problèmes similaires).