Derivación de la ecuación de Bellman en el aprendizaje por refuerzo

Question

Veo la siguiente ecuación en " En Reinforcement Learning. An Introduction ", pero no sigue del todo el paso que he resaltado en azul a continuación. ¿Cómo se deriva exactamente este paso?

Answer 1

Esto es sólo un comentario/adición a la respuesta aceptada.

Me confundí en la línea en la que se aplica la ley de la expectativa total. No creo que la forma principal de la ley de la expectativa total pueda ayudar aquí. De hecho, aquí se necesita una variante de la misma.

Si $X,Y,Z$ son variables aleatorias y suponiendo que toda la expectativa existe, entonces se cumple la siguiente identidad:

$E[X|Y] = E[E[X|Y,Z]|Y]$

En este caso, $X= G_{t+1}$ , $Y = S_t$ y $Z = S_{t+1}$ . Entonces

$E[G_{t+1}|S_t=s] = E[E[G_{t+1}|S_t=s, S_{t+1}=s'|S_t=s]$ que por la propiedad de Markov equivale a $E[E[G_{t+1}|S_{t+1}=s']|S_t=s]$

A partir de ahí, se puede seguir el resto de la prueba desde la respuesta.

Answer 2

Aunque ya se ha dado la respuesta correcta y ha pasado algún tiempo, he pensado que la siguiente guía paso a paso podría ser útil:
Por linealidad del Valor Esperado podemos dividir $E[R_{t+1} + \gamma E[G_{t+1}|S_{t}=s]]$ en $E[R_{t+1}|S_t=s]$ y $\gamma E[G_{t+1}|S_{t}=s]$ .
Voy a resumir los pasos sólo para la primera parte, ya que la segunda parte sigue los mismos pasos combinados con la Ley de la Expectativa Total.

\begin{align} E[R_{t+1}|S_t=s]&=\sum_r{ r P[R_{t+1}=r|S_t =s]} \\ &= \sum_a{ \sum_r{ r P[R_{t+1}=r, A_t=a|S_t=s]}} \qquad \text{(III)} \\ &=\sum_a{ \sum_r{ r P[R_{t+1}=r| A_t=a, S_t=s] P[A_t=a|S_t=s]}} \\ &= \sum_{s^{'}}{ \sum_a{ \sum_r{ r P[S_{t+1}=s^{'}, R_{t+1}=r| A_t=a, S_t=s] P[A_t=a|S_t=s] }}} \\ &=\sum_a{ \pi(a|s) \sum_{s^{'},r}{p(s^{'},r|s,a)} } r \end{align}

Mientras que (III) sigue la forma: \begin{align} P[A,B|C]&=\frac{P[A,B,C]}{P[C]} \\ &= \frac{P[A,B,C]}{P[C]} \frac{P[B,C]}{P[B,C]}\\ &= \frac{P[A,B,C]}{P[B,C]} \frac{P[B,C]}{P[C]}\\ &= P[A|B,C] P[B|C] \end{align}

Answer 3

¿Qué pasa con el siguiente enfoque?

$$\begin{align} v_\pi(s) & = \mathbb{E}_\pi\left[G_t \mid S_t = s\right] \\ & = \mathbb{E}_\pi\left[R_{t+1} + \gamma G_{t+1} \mid S_t = s\right] \\ & = \sum_a \pi(a \mid s) \sum_{s'} \sum_r p(s', r \mid s, a) \cdot \,\\ & \qquad \mathbb{E}_\pi\left[R_{t+1} + \gamma G_{t+1} \mid S_{t} = s, A_{t+1} = a, S_{t+1} = s', R_{t+1} = r\right] \\ & = \sum_a \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a) \left[r + \gamma v_\pi(s')\right]. \end{align}$$

Las sumas se introducen para recuperar $a$ , $s'$ y $r$ de $s$ . Después de todo, las posibles acciones y los posibles estados siguientes pueden ser . Con estas condiciones adicionales, la linealidad de la expectativa conduce al resultado casi directamente.

Sin embargo, no estoy seguro de la rigurosidad de mi argumento desde el punto de vista matemático. Estoy abierto a mejoras.

Answer 4

$\mathbb{E}_\pi(\cdot)$ normalmente denota la expectativa asumiendo que el agente sigue la política $\pi$ . En este caso $\pi(a|s)$ parece no determinista, es decir, devuelve la probabilidad de que el agente realice la acción $a$ cuando en el estado $s$ .

Parece que $r$ , en minúsculas, está sustituyendo a $R_{t+1}$ una variable aleatoria. La segunda expectativa sustituye a la suma infinita, para reflejar el supuesto de que seguimos $\pi$ para todos los futuros $t$ . $\sum_{s',r} r \cdot p(s′,r|s,a)$ es entonces la recompensa inmediata esperada en el siguiente paso de tiempo; La segunda expectativa -que se convierte en $v_\pi$ -es el valor esperado del siguiente estado, ponderado por la probabilidad de acabar en el estado $s'$ habiendo tomado $a$ de $s$ .

Así pues, la expectativa tiene en cuenta la probabilidad de la política, así como las funciones de transición y de recompensa, que aquí se expresan conjuntamente como $p(s', r|s,a)$ .

Answer 5

Aquí hay un enfoque que utiliza los resultados de los ejercicios en el libro (suponiendo que está utilizando la 2ª edición del libro). En el ejercicio 3.12 deberías haber obtenido la ecuación $$v_\pi(s) = \sum_a \pi(a \mid s) q_\pi(s,a)$$ y en el ejercicio 3.13 deberías haber obtenido la ecuación $$q_\pi(s,a) = \sum_{s',r} p(s',r\mid s,a)(r + \gamma v_\pi(s'))$$ Utilizando estas dos ecuaciones, podemos escribir $$\begin{align}v_\pi(s) &= \sum_a \pi(a \mid s) q_\pi(s,a) \\ &= \sum_a \pi(a \mid s) \sum_{s',r} p(s',r\mid s,a)(r + \gamma v_\pi(s'))\end{align}$$ que es la ecuación de Bellman. Por supuesto, esto empuja la mayor parte del trabajo en ejercicio 3.13 (pero asumiendo que estás leyendo/haciendo los ejercicios linealmente, esto no debería ser un problema). En realidad, es un poco extraño que Sutton y Barto hayan decidido optar por la derivación directa (supongo que no querían dar las respuestas a los ejercicios).