Tema

Ecuaciones de Bellman

Aprendizaje por refuerzo
Nivel intermedio

Las ecuaciones de Bellman expresan el valor de un estado como la recompensa inmediata esperada más el valor descontado del estado siguiente, con esperanza sobre la política y sobre las transiciones.

Nombre en inglés

Bellman equations

Intuición

El valor de estar en un sitio se descompone en lo que se cobra ahora y en lo que valdrá el sitio al que se va, de modo que una suma infinita se convierte en una relación entre valores vecinos. La versión de evaluación promedia sobre las acciones que dicta la política, mientras que la de optimalidad toma el máximo sobre las acciones. Toda la familia de algoritmos del aprendizaje por refuerzo consiste en resolver alguna de esas dos ecuaciones, de forma exacta o por muestreo.

Fórmula

V^{\pi}(s) = \sum_a \pi(a \mid s) \sum_{s'} P(s' \mid s, a) [R(s, a, s') + \gamma V^{\pi}(s')] \qquad V^{*}(s) = \max_a \sum_{s'} P(s' \mid s, a) [R + \gamma V^{*}(s')]

Ejemplo resuelto

Desde el estado s, la acción a lleva con probabilidad 0.8 a un estado que vale 10 y entrega recompensa 1, y con probabilidad 0.2 a un estado que vale 0 y no entrega nada. Con un descuento de 0.9, el valor de la acción es 0.8 por (1 más 0.9 por 10) más 0.2 por 0, es decir, 0.8 por 10 = 8. Si la política eligiese esa acción la mitad de las veces y otra que vale 4 la otra mitad, el valor del estado bajo esa política sería 0.5 por 8 más 0.5 por 4 = 6, mientras que el valor óptimo del estado no bajaría de 8.

Errores frecuentes

Tomar el máximo dentro de la esperanza en vez de fuera, lo que supone que el agente conoce el resultado del azar antes de elegir y produce un valor optimista.
Confundir el valor de estado con el valor de acción, cuando el primero mide lo que vale estar en un sitio bajo la política y el segundo mide lo que vale una acción concreta desde ese sitio.
Olvidar que el valor de un estado terminal vale cero por definición, fallo que arrastra un sesgo por todo el cálculo.

Ejercicio

Desde s la única acción lleva con probabilidad 0.5 a un estado que vale 4 con recompensa 2, y con probabilidad 0.5 a un estado terminal con recompensa 0. Con un descuento de 0.5, ¿cuánto vale el estado s?

Ver la solución

El primer ramal aporta 0.5 por (2 más 0.5 por 4), es decir, 0.5 por 4 = 2. El segundo aporta 0.5 por (0 más 0.5 por 0), es decir, 0, porque el valor de un estado terminal es cero. La suma da 2.

Respuesta: 2