Définitions équivalentes du processus décisionnel de Markov

Question

Je lis actuellement le Reinforcement Learning de Sutton où dans le chapitre 3 la notion de MDP est définie.

Ce que l'auteur me semble dire, c'est qu'un MDP est complètement défini au moyen de la probabilité $p(s_{t+1},r_t | s_t, a_t)$.

Cependant, selon wikipedia , et de nombreuses autres références, j'ai trouvé qu'un MDP est un quadruple ensemble d'états, ensemble d'actions, probabilité de transition$P_{s_{t+1,s_t}}^{a_t} = p(s_{t+1} | s_t, a_t)$et une récompense attendue $R_{s_{t+1},s_t}^{a_t}$.

Maintenant, je suppose qu'une définition implique l'autre, à moins que je ne me trompe, alors dites-moi s'il vous plaît ...

Le fait est que Sutton parvient à dériver de ses définitions celle de Wikipédia. Cependant, comme je ne peux pas trouver l'inverse, j'essayais de montrer l'inverse.

La seule intuition que j'avais était d'observer cela

$$ R_{s_{t+1},s_t}^{a_t} = \sum_{r_{t+1},s_{t+1}} r_{t+1} p(r_{t+1}, s_{t+1} | s_t, a_t) $$

et peut-être qu'il y a des conditions qui me permettraient de récupérer $p(r_{t+1},s_{t+1} | s_t, a_t)$ mais je ne peux pas le voir honnêtement.

Pouvez-vous me dire alors si les deux sont équivalents et pourquoi?

Answer 1

Je pense que le nom de la question est un peu trompeur ...

En général, en mathématiques, la question des «définitions équivalentes» se pose généralement lorsqu'il y a deux définitions formellement complètes d'une chose que nous nous attendons en fait à être la même chose.

Compte tenu du cas présenté ici, j'ai les sentiments suivants:

1. Sutton est une mauvaise référence car il ne définit ni ne prouve formellement la plupart des choses. Cela rend ce livre vraiment déroutant à lire. Exemple: Ils «prouvent» l'équation de Bellman mais en fait ils manquent / omettent / ignorent la plupart des preuves, ce qui est assez compliqué (voir ma réponse ). NOTE: Ceci est juste mon point de vue très personnel et je suis sûrement en désaccord avec certaines personnes qui regrettent cette opinion sur ce livre. Donc, quelle que soit la «définition» utilisée par Sutton, je suis presque sûr qu'elle est ambiguë, trompeuse et / ou déroutante.

2. La même chose s'applique à Wikipedia. Thea dit qu'il y a une fonction de récompense$R_a(s,s')$mais qu'est-ce que cette fonction est censée faire? Comment s'intègre-t-il exactement aux variables de probabilité? Et si la récompense n'est pas déterministe mais plutôt aléatoire (comme dans l'un des tout premiers exemples de Reinforcement Learning, la machine à bandits)? Ces variables aléatoires ont-elles une densité commune qui se divise en quelque sorte ou pourquoi wikipedia dit-il exactement que le MDP est complètement décrit par les distributions marginales$p(s_{t+1}|s_t, a_t)$? Que se passe-t-il si nous avons deux moments différents dans le temps$t,r$ et $a_t = a_r$ et $s_{t+1}=s_{r+1}$ et $s_t = s_r$... est alors $p(s_{t+1}|s_t,a_t) = p(s_{r+1}|s_r,a_r)$? Ce n'est pas du tout clair car formellement,$S_t$ est une variable aléatoire différente de $S_r$...

En résumé: nous avons deux définitions, l'une est confuse et incomplète et l'autre est plutôt considérée comme un résumé et est également incomplète. Par conséquent, il est difficile de répondre à la question de savoir s'ils sont équivalents ou non. Cependant, il y a de l'espoir. Il y a une définition `` complète '' qui nous permet de prouver deux choses: l'équation de Bellman et le fait que l'état et l'espace d'action sont `` gentils '', alors il y a une meilleure politique prouvée (étonnamment déterministe)! La preuve de l'équation de Bellman peut être trouvée dans le lien ci - dessus et la preuve du fait surprenant qu'il existe une meilleure politique peut être trouvée dans le seul livre que j'ai vraiment trouvé jusqu'à présent comme une source précieuse d'informations sur RL: Puterman , Processus décisionnels de Markov.

Cette définition va comme suit:

Définition Un processus de décision de Markov se compose d'ensembles$\mathcal{S}, \mathcal{A}, \mathcal{R}$ et un ensemble (potentiellement infini) de variables aléatoires $(S_t, A_t, R_t)_{t \in \text{time}}$ où $\text{time}$ est soit $\mathbb{N}_0 = \{0,1,2,...\}$ ou un ensemble du formulaire $\text{time} = \{0,1,2,...,T\}$ pour certains $T \in \mathbb{N}$ et tel que pour tous $t \in \text{time}$, les variables aléatoires $S_t,A_t,R_t,S_{t-1},A_{t-1},R_{t-1}, ..., S_0, A_0, R_0$ avoir une densité commune $f_{S_t,A_t,R_t,S_{t-1},A_{t-1},R_{t-1}, ..., S_0, A_0, R_0}$ et tout $S_t$ carte dans $\mathcal{S}$, tout $A_t$ carte dans l'ensemble $\mathcal{A}$ et tout $R_t$ carte dans l'ensemble $\mathcal{R}$. Nous faisons les hypothèses suivantes sur toutes les densités communes:

• Pour chaque $t, s_{t+1}, r_t, a_t, s_t, r_{t-1}, a_{t-1}, s_{t-1}, ..., r_0, a_0, s_0$ $$p(s_{t+1}, r_{t} ,a_t | s_t, r_{t-1}, a_{t-1}, s_{t-1}, ..., r_{0}, a_0, s_0) = p(s_{t+1}, r_{t}, a_t | s_t)$$ Cette propriété est appelée la propriété Markov.
• Notons la densité d'une variable aléatoire $X$ par $f_X$. Laisser$t,q \in \text{time}$ et laissez $s, s' \in S, a \in A, r \in \mathcal{R}$ puis
  • $f_{S_{t+1} | A_t, S_t}(s' | a, s) = f_{S_{q+1} | A_{q}, S_{q}}(s' | a, s)$
  • $f_{R_{t} | S_{t+1}, A_t, S_t}(r | s', a, s) = f_{R_{q} | S_{q+1}, A_{q}, S_{q}}(r | s', a, s)$
  • $f_{S_t|A_t}(s|a) = f_{S_{q}|A_{q}}(s|a)$
    ou plutôt formulé comme ceci: si $s_{t+1} = s_{q+1}, r_{t} = r_{q}, a_t = a_{q}$ et $s_t = s_{q}$ puis $$p(s_{t+1} | a_t, s_t) = p(s_{q+1} | a_{q}, s_{q})$$ $$p(r_{t} | s_{t+1}, a_t, s_t) = p(r_{q} | s_{q+1}, a_{q}, s_{q})$$ et $$p(s_t|a_t) = p(s_{q}|a_{q})$$

Remarques:

1. Il n'est pas clair que les variables aléatoires aient une densité commune, il faut la supposer car il y a des variables aléatoires sans densité (ne parlant même pas de densité commune!).
2. Il n'est pas clair que ces variables aléatoires soient oublieuses par rapport au «passé», nous devons le supposer!
3. Il n'est pas clair que les densités à des moments différents coïncident, il faut le supposer!
4. Disons que nous avons deux MDP $M = (S_t, A_t, R_t)$ et $M' = (S'_t, A'_t, R'_t)$sur le même ensemble d'indices de temps. Alors on dit que$M$ et $M'$ sont 'égaux' si toutes leurs densités finies coïncident, c'est-à-dire si pour tout $t$, $$ f_{S_t,A_t,R_t,S_{t-1},A_{t-1},R_{t-1}, ..., S_0, A_0, R_0} = f_{S'_t,A'_t,R'_t,S'_{t-1},A'_{t-1},R'_{t-1}, ..., S'_0, A'_0, R'_0}$$ (comme fonctions). Écrivons$p(x)$ pour la densité $f_X$afin de rendre les choses plus simples. Par définition et la première hypothèse, nous avons $$\begin{align*} &p(s_t,a_t,r_t,s_{t-1},a_{t-1},r_{t-1}, ..., s_0, a_0, r_0) \\ &= p(s_t,a_t,r_t|s_{t-1},a_{t-1},r_{t-1}, ..., s_0, a_0, r_0) * p(s_{t-1},a_{t-1},r_{t-1}, ..., s_0, a_0, r_0) \\ &= p(s_t,a_t,r_t|s_{t-1}) * p(s_{t-1},a_{t-1},r_{t-1}, ..., s_0, a_0, r_0) \end{align*} $$ En décomposant la dernière partie de manière inductive, nous voyons que nous pouvons écrire $p(s_t,a_t,r_t,s_{t-1},a_{t-1},r_{t-1}, ..., s_0, a_0, r_0)$ en tant que produit des densités $p(s_t,a_t,r_t|s_{t-1})$ et $p(s_0)$. Par un simple calcul, nous voyons que $$p(s_{t+1}, r_t, a_t| s_t) = p(r_t|s_{t+1}, a_t, s_t) p(s_{t+1}|a_t,s_t)p(a_t|s_t)$$ Selon la seconde hypothèse, toutes ces densités sont les mêmes (indépendamment du temps). Cela conduit à l'aperçu très important suivant: Tout ce que nous savons pour décrire un MDP jusqu'à `` l'égalité '' comme défini ci-dessus est les quatre densités$p(r|s',a,s), p(s'|a,s), p(a|s)$ (où $s'$ prend le rôle de $s_{t+1}$, $s$ est $s_t$, $a$ est $a_t$ et $r$ est $r_t$) et enfin, $p(s_0)$. Donc, en ce sens, un MDP est complètement décrit en disant comment la situation évolue d'une étape dans le temps à l'autre (en ce sens que si deux MDP ont la même façon de passer d'un pas dans le temps au suivant, alors ils sont égaux) . Maintenant, une question intéressante se pose: étant donné ces quatre densités, pouvons-nous créer un MDP (dans un certain sens «l'unique» MDP, parce que deux différents avec les mêmes quatre densités seraient «égaux») à partir d'elles? La réponse est oui, mais ce n'est pas aussi simple que vous pourriez le penser: voir ma question sur mathoverflow .

Sur la base de la dernière note, il y a encore une chose à dire à propos de cette configuration: il y a aussi la notion d'un automate de décision de Markov (MDA). Chaque fois que vous recherchez MDP, vous tomberez certainement sur MDA. Les gens dessinent une sorte de graphique étrange à côté de la définition d'un MDP, mais on ne sait pas du tout comment ces deux choses s'emboîtent. Par la dernière note, le MDP est complètement décrit par quatre densités (dans deux sens: étant donné ces densités, nous pouvons en fait créer un MDP à partir d'eux et les deux MDP que nous créons à partir d'eux sont égaux) et ce qu'un MDA définit exactement ces quatre densités. Cela signifie: Étant donné une MDA qui n'est rien d'autre que de décrire les quatre densités: distribution initiale de l'état$p(s_0)$, une distribution de récompenses $p(r|s',a,s)$, une distribution de transition d'état $p(s'|s)$ et une politique $p(a|s)$ signifie généralement $\pi(a|s)$ puis le MDA donne lieu à un MDP.

Notez que lorsque les gens essaient d'optimiser la politique, ils font en fait quelque chose d'assez compliqué: ils ont des densités fixes $p(s_0), p(r|s',a,s), p(s'|s)$ et ils commencent par une politique $\pi(a|s)$. Ensuite, ils donnent naissance au MDP avec ces densités et l'utilisent pour évaluer la performance de la politique. Puis ils changent la polica en autre chose$\pi'(a|s)$ et refaites cette construction (donnant naissance à un MDP d'un MDA) et réévaluez les performances, etc. etc.

Désolé pour la longue réponse mais j'ai investi beaucoup de temps pour comprendre ce qui se passe réellement sous le capot et les sources que j'ai trouvées m'ont laissé très perplexe (par exemple en utilisant simplement des hypothèses sans les énoncer, etc.).

Note finale: aucune théorie de mesure n'est nécessaire pour comprendre cette réponse ;-)

ANNEXE: On m'a demandé ce que signifie «densité commune». Une variable aléatoire (disons$X$) est une fonction d'un espace de probabilités $\Omega$ dans un autre espace $\mathcal{X}$. Notez que le symbole 'P' dans la théorie des probabilités n'est pas quelque chose de 'faux' / magique mais a plutôt une définition très claire (c'est une mesure sur (l'algèbre sigma sur)$\Omega$). On dit que$X$ a une densité $f$iff. les expressions$P[X \in A]$ peut être exprimé comme $\int_A f(x) dx$ (ici, dx est une mesure `` naturelle '' sur $\mathcal{X}$, par exemple la mesure de Lebesgue si $\mathcal{X}=\mathbb{R}$ et la mesure de comptage si $\mathcal{X}$ est fini) pour tous les ensembles $A$ (dans l'algèbre sigma sur $\mathcal{X}$). Si on nous donne un touple de variables aléatoires$(X,Y)$ alors nous pouvons les considérer comme une seule fonction dans $\mathcal{X} \times \mathcal{Y}$ et si cette variable aléatoire a une densité alors on dit que $X,Y$ont une «densité commune». Intuitivement, cela ne signifie rien de plus que de pouvoir calculer avec des expressions$p(x,y)$ au lieu du maladroit $P[X \in A, Y \in B]$.