11.2.1 Programación Dinámica

Si se conoce el modelo del ambiente, osea las transiciones de probabilidad ( ${\cal P}_{ss'}^a$ ) y los valores esperados de recompensas ( ${\cal R}_{ss'}^a$ ), las ecuaciones de optimalidad de Bellman nos representan un sistema de $\vert S\vert$ ecuaciones y $\vert S\vert$ incognitas.

Consideremos primero como calcular la función de valor $V^\pi$ dada una política arbitraria $\pi$ .

$\begin{displaymath} \begin{array}{lll} V^{\pi}(s) & = & E_{\pi} \{ R_t \mid s_t ... ...}_{ss'}^a [{\cal R}_{ss'}^a + \gamma V^{\pi}(s')] \end{array}\end{displaymath}$

donde $\pi(s,a)$ es la probabilidad de tomar la acción

en estado

bajo la política $\pi$ .

Podemos hacer aproximaciones sucesivas, evaluando $V_{k+1}(s)$ en términos de $V_{k}(s)$ .

$\begin{displaymath} V_{k+1}(s) = \sum_{a} \pi(s,a) \sum_{s'} {\cal P}_{ss'}^a [{\cal R}_{ss'}^a + \gamma V_{k}(s')] \end{displaymath}$

Podemos entonces definir un algoritmo de evaluación iterativa de políticas como se muestra en la tabla 11.1.

**Tabla 11.1:** Algoritmo iterativo de evaluación de política.
$\begin{table} \begin{tabbing} 123\=123\= \kill Inicializa $V(s)=0$\ para toda $s... ...o positivo peque\~{n}o) \\ Regresa $V \approx V^{\pi}$ \end{tabbing}\end{table}$

Una de las razones para calcular la función de valor de una política es para tratar de encontrar mejores políticas. Dada una función de valor para una política dada, podemos probar una acción $a \neq \pi(s)$ y ver si su

es mejor o peor que el $V^{\pi}(s)$ .

En lugar de hacer un cambio en un estado y ver el resultado, se pueden considerar cambios en todos los estados considerando todas las acciones de cada estado, seleccionando aquella que parezca mejor de acuerdo a una política greedy.

Podemos entonces calcular una nueva política $\pi'(s) = \mbox{argmax}_a Q^{\pi}(s,a)$ y continuar hasta que no mejoremos.

Esto sugiere, partir de una política ( $\pi_0$ ) y calcular la función de valor ( $V^{\pi_0}$ ), con la cual encontrar una mejor política ( $\pi_1$ ) y así sucesivamente hasta converger a $\pi^*$ y

A este procedimiento se llama iteración de políticas y viene descrito en la tabla 11.2.

**Tabla 11.2:** Algoritmo de iteración de política.
$\begin{table} \begin{tabbing} 123\=123\=123\= \kill 1. Inicializaci\a'{o}n: \\ ... ... \\ \> If \emph{pol-estable}, then stop, else go to 2. \end{tabbing}\end{table}$

Uno de los problemas de iteración de políticas es que cada iteración involucra evaluación de políticas que requiere recorrer todos los estados varias veces.

Sin embargo, el paso de evaluación de política lo podemos truncar de varias formas, sin perder la garantía de convergencia. Una de ellas es pararla después de recorrer una sola vez todos los estados. A esta forma se le llama iteración de valor (value iteration). En particular se puede escribir combinando la mejora en la política y la evaluación de la política truncada como sigue:

$\begin{displaymath} V_{k+1}(s) = max_a \sum_{s'} {\cal P}_{ss'}^a [{\cal R}_{ss'}^a + \gamma V_k(s')] \end{displaymath}$

Se puede ver como expresar la ecuación de Bellman en una regla de actualización. Es muy parecido a la regla de evaluación de políticas, solo que se evalúa el máximo sobre todas las acciones (ver tabla 11.3).

**Tabla 11.3:** Algoritmo de iteración de valor.
$\begin{table} \begin{tabbing} 123\=123\= \kill Inicializa $V(s)=0$\ para toda $s... ...{\cal P}_{ss'}^a [ {\cal R}_{ss'}^a + \gamma V^*(s')]$ \end{tabbing}\end{table}$

Para espacios muy grandes, el ver todos los estados puede ser computacionalmente muy caro. Una opción es hacer estas actualizaciones al momento de estar explorando el espacio, y por lo tanto determinando sobre qué estados se hacen las actualizaciones.

El hacer estimaciones en base a otras estimaciones se conoce también como bootstrapping.