Procesos de decisión de Markov y aprendizaje por refuerzo

Un proceso de decisión de Markov, o MDP, describe decisiones repetidas cuando las acciones pueden tener resultados inciertos. El agente observa su estado actual, elige una acción disponible, recibe una recompensa y pasa a un nuevo estado. Estas cuatro partes describen una transición; una secuencia de transiciones describe una trayectoria.

Interpreta un modelo de transición

El conjunto de estados es $S$, y $A(s)$ enumera las acciones permitidas en el estado $s$. El modelo de transición $T(s,a,s^{\mathrm{\prime }})=P(s^{\mathrm{\prime }}\mid s,a)$ indica la probabilidad de llegar a $s^{\mathrm{\prime }}$ después de realizar $a$ en $s$. Para cada par estado-acción, todas estas probabilidades son no negativas y suman 1. La recompensa $R(s,a,s^{\mathrm{\prime }})$ corresponde a esa transición. Una recompensa negativa representa un costo o una penalización.

Considera un robot de reparto con los estados batería Alta, Baja y Agotada. Agotada termina el episodio. Su modelo es:

Las dos filas de Trabajar suman 1 cada una. Para Trabajar en Baja, la recompensa inmediata esperada es $\mathrm{0,6}(4)+\mathrm{0,4}(-10)=-\mathrm{1,6}$. Esta media es útil para planificar, pero un intento real da 4 o −10. Elegir Trabajar determina la distribución; no determina el resultado favorable.

Incluye el pasado relevante en el estado

La propiedad de Markov significa que el estado y la acción actuales contienen la información necesaria para predecir el estado siguiente:

El mundo puede tener una larga historia. Esa historia importa a través de las variables incluidas en el estado actual. La ubicación de un robot por sí sola puede ser insuficiente si su batería determina si un trabajo tiene éxito. Incluir el nivel de batería permite al modelo distinguir situaciones con distintos riesgos.

Un MDP estándar supone que el agente observa el estado exactamente. Si partes importantes del estado están ocultas, el agente necesita una creencia sobre los posibles estados; eso conduce a un MDP parcialmente observable, o POMDP.

Reconoce los finales y el movimiento aleatorio

Un estado terminal tiene valor 0 porque no le siguen recompensas. La recompensa al entrar en él sigue contando: el robot recibe −10 en su última transición a Agotada. Las tareas episódicas terminan en un estado terminal; las tareas continuas, como la gestión constante de la temperatura, no necesitan un estado terminal.

En un mundo de cuadrícula, un movimiento elegido puede tener éxito con probabilidad 0,8 y desviarse hacia cada dirección perpendicular con probabilidad 0,1. Un intento de moverse hacia una pared deja al agente en su sitio. Las probabilidades de los resultados que llegan a la misma casilla deben sumarse.

Las transiciones deterministas son un caso particular: un sucesor tiene probabilidad 1. Para un estado inicial conocido y una tarea adecuada de alcance de objetivos, puede bastar un plan fijo. Con resultados inciertos, una política especifica cómo responder en cualquier estado que se produzca. Algunos textos escriben las recompensas como $R(s)$ o $R(s,a)$; comprueba la convención temporal antes de traducir una fórmula.

Una política describe cómo actúa el agente. Una política determinista y estacionaria $\pi (s)$ elige una acción para cada estado y mantiene esa elección con el tiempo. Para el robot, «Trabajar con batería Alta, Cargar con batería Baja» es una política de este tipo. Una política estocástica $\pi (a\mid s)$ asigna probabilidades a las acciones disponibles.

Calcula un retorno

El retorno descontado combina las recompensas de una trayectoria:

La primera transición obtiene $r_0$ con peso 1. Cada recompensa posterior recibe un factor más del descuento $\gamma$. Para las recompensas −1, −1, −1 y +10, seguidas de la terminación, usar $\gamma =\mathrm{0,9}$ da

Con $\gamma =\mathrm{0,5}$, la misma trayectoria da $-1-\mathrm{0,5}-\mathrm{0,25}+10(\mathrm{0,125})=-\mathrm{0,5}$. La ganancia retrasada pierde gran parte de su peso. El descuento puede representar una preferencia por las recompensas más tempranas o la probabilidad de que el proceso continúe un paso más.

Una política se evalúa por su retorno esperado, promediado sobre sus posibles trayectorias. Una trayectoria afortunada no demuestra que una política sea buena. Una política óptima ${\pi }^{\ast }$ da el mayor retorno esperado desde cada estado. Un MDP finito descontado tiene una política óptima determinista y estacionaria.

Mantén finito un futuro infinito

Con recompensas acotadas y $0\le \gamma <1$, la serie geométrica acota todos los retornos. Si $\mathrm{\mid }{r}_t\mathrm{\mid }\le R_{\max }$, entonces

La mayor magnitud de recompensa del robot es 10, por lo que $\gamma =\mathrm{0,9}$ da $\mathrm{\mid }U\mathrm{\mid }\le 100$. Como su mayor recompensa positiva es 4, su retorno tampoco puede superar $4\mathrm{/}(1-\mathrm{0,9})=40$. Estas son cotas, no afirmaciones de que el robot pueda alcanzarlas.

La cantidad $1\mathrm{/}(1-\gamma )$ es un horizonte efectivo aproximado: unos 10 pasos para $\gamma =\mathrm{0,9}$. No es un corte. Una recompensa 10 pasos después aún recibe el peso ${\mathrm{0,9}}^{10}\approx \mathrm{0,35}$. Las tareas continuas sin descuento requieren especial cuidado: las recompensas positivas repetidas pueden hacer que los retornos sean infinitos. Un horizonte finito fijo hace que la suma sea finita; los modelos episódicos también necesitan duraciones de episodio adecuadas para obtener valores esperados finitos.

Deja que el tiempo y las recompensas por paso influyan en las decisiones

Con un plazo límite, la mejor acción puede depender del tiempo restante. Considera una máquina en estado Desgastada. Funcionar da 6 y la deja Desgastada o Averiada con igual probabilidad. Reparar da −4 y la deja en Buen estado. En Buen estado, Funcionar da 10; en Averiada, Reparar da −20. Si queda un paso, en Desgastada conviene Funcionar: $6>-4$. Si quedan dos pasos y $\gamma =\mathrm{0,9}$, Reparar da $-4+\mathrm{0,9}(10)=5$. Funcionar da $6+\mathrm{0,9}[\mathrm{0,5}(6)+\mathrm{0,5}(-20)]=-\mathrm{0,3}$. El tiempo adicional invierte la elección.

La recompensa por paso no terminal de un mundo de cuadrícula, obtenida en los pasos no terminales, cambia el costo de la demora. Las recompensas negativas por paso favorecen llegar a una salida; una penalización mayor puede hacer preferible una mala salida cercana frente a una ruta larga. Una recompensa positiva por paso suficientemente grande puede favorecer permanecer en la cuadrícula. La elección exacta también depende del descuento, las distancias y los riesgos de desviación.

Formular un MDP convierte un objetivo práctico en decisiones que una computadora puede evaluar. Comienza por elegir cuándo ocurren las decisiones. Después define un estado observable, las acciones permitidas, las probabilidades de transición, las recompensas, los posibles estados terminales y un descuento o un horizonte. La calidad de la política resultante depende de estas elecciones.

Modela el mantenimiento de una máquina

Supón que se inspecciona una máquina una vez por paso de decisión. Su estado es Buen estado, Desgastada o Averiada. El modelo es:

Averiada no es terminal: la reparación permite continuar el trabajo. La tarea es continua, con $\gamma =\mathrm{0,9}$. Observa que las acciones disponibles dependen del estado; Funcionar no está disponible en Averiada.

Al resolver este modelo se obtienen valores óptimos de aproximadamente 78,64 en Buen estado, 66,78 en Desgastada y 50,78 en Averiada. En Desgastada, Reparar tiene valor $-4+\mathrm{0,9}(\mathrm{78,64})\approx \mathrm{66,78}$. Funcionar tiene valor $6+\mathrm{0,9}[\mathrm{0,5}(\mathrm{66,78})+\mathrm{0,5}(\mathrm{50,78})]\approx \mathrm{58,90}$. La recompensa inmediata negativa de la reparación da acceso a un futuro más productivo.

Elige suficiente información para el estado

El estado debe permitir predecir tanto los resultados como las recompensas. La posición de una pelota en movimiento por sí sola omite su velocidad, por lo que dos posiciones idénticas pueden tener distintas posiciones siguientes. Una posición en un juego de mesa también debe indicar a quién le toca jugar. Si el tiempo restante cambia qué acciones resultan rentables, inclúyelo en una regla de decisión de horizonte finito o amplía el estado con él.

Las variables adicionales aumentan el espacio de estados. Diez variables de sí/no permiten $2^{10}=1024$ combinaciones. Conserva la información que cambia las predicciones o las recompensas; almacenar toda la historia puede hacer innecesariamente grande un modelo manejable. El MDP estacionario habitual supone las mismas reglas de transición y recompensa a lo largo del tiempo. Un estado oculto requiere un modelo de creencias, mientras que los oponentes estratégicos requieren un modelo de juego.

Haz que la recompensa exprese el objetivo

Un robot de limpieza recompensado por cada trozo de suciedad recogido puede beneficiarse si esparce suciedad y vuelve a recogerla. Esto es explotación de la función de recompensa: la optimización exitosa de una medida deficiente. Una recompensa ligada a la limpieza deseada evita ese ciclo concreto. Una recompensa escasa por alcanzar el objetivo expresa claramente el éxito, pero proporciona poca retroalimentación durante un intento largo.

El moldeado de recompensas añade retroalimentación sobre el progreso. Las bonificaciones arbitrarias pueden cambiar el objetivo. Dos comparaciones útiles son:

• Multiplicar todas las recompensas por el mismo número positivo conserva la ordenación de las políticas.
• Sumar una constante a cada recompensa conserva las políticas óptimas en una tarea continua descontada, porque todas las políticas ganan la misma constante descontada. En una tarea episódica, las trayectorias más largas y más cortas ganan cantidades diferentes, por lo que la ordenación puede cambiar.

Un término de moldeado que conserva la política tiene la forma $F(s,a,s^{\mathrm{\prime }})=\gamma \mathrm{\Phi }(s^{\mathrm{\prime }})-\mathrm{\Phi }(s)$. Aquí $\mathrm{\Phi }$ asigna un potencial a cada estado. Con potenciales acotados en una tarea continua descontada, los términos descontados añadidos se cancelan salvo por un desplazamiento correspondiente al estado inicial. Para tareas episódicas, establecer todos los potenciales terminales en 0 elimina el término terminal restante. Un potencial terminal distinto de cero puede cambiar qué final o qué momento de terminación se prefiere.

Un valor mide el retorno disponible desde una situación bajo una forma particular de actuar. Incluye las recompensas futuras, ponderadas por sus probabilidades y el momento en que llegan. Esto distingue los valores de la recompensa obtenida en una sola transición.

Distingue la elección inicial

El valor de estado $V^{\pi }(s)$ es el retorno descontado esperado al comenzar en el estado $s$ y seguir la política $\pi$. El valor de acción $Q^{\pi }(s,a)$ fija la primera acción en $a$ y después sigue $\pi$. No significa realizar $a$ en todos los pasos posteriores.

Los valores óptimos sustituyen esa política de continuación por el mejor comportamiento posible. Así, $V^{\ast }(s)$ es el mejor retorno esperado desde $s$, y $Q^{\ast }(s,a)$ es el mejor retorno esperado después de fijar la primera acción. Su relación es

El máximo es un número; el argmax identifica una acción que lo alcanza. Si varias acciones empatan, puede elegirse cualquiera de ellas.

Interpreta las opciones del robot

Para el robot de reparto con $\gamma =\mathrm{0,9}$, los valores Q óptimos son:

El máximo de cada fila es el valor óptimo del estado. En Alta conviene Trabajar; en Baja conviene Cargar. Cargar da 0 inmediatamente, pero en Baja recupera el acceso a Alta y a sus mejores oportunidades futuras. Trabajar en Baja sigue teniendo un valor Q óptimo positivo porque un robot que conserve batería puede cargarla después.

La política de continuación importa. Con «Trabajar siempre», los valores de estado bajan a aproximadamente 8,27 en Alta y −3,48 en Baja. El modelo no ha cambiado; han cambiado las decisiones posteriores a cada resultado. Un número identificado solo como «el valor» está incompleto si no queda clara la política prevista o su optimalidad.

Distingue las capas de elección y azar

Un árbol expectimax alterna dos tipos de nodos. En un estado, el agente selecciona una acción; en un par estado-acción, a veces llamado estado Q, el azar selecciona el estado siguiente según el modelo de transición. El agente maximiza entre las acciones y promedia sus resultados.

Un MDP cíclico repite los mismos estados en muchos lugares del árbol. La programación dinámica almacena un valor para cada estado y lo reutiliza. Esto evita volver a calcular el mismo problema de continuación cada vez que un camino del árbol regresa a ese estado.

Extrae una política de los valores disponibles

Con una tabla Q, compara los valores de acción de la fila actual. No se necesita un modelo de transición. Solo con valores de estado, calcula primero la recompensa esperada de una acción más el valor descontado de los sucesores:

Ese cálculo necesita las transiciones y las recompensas. Elegir simplemente la acción que puede llegar al sucesor de mayor valor ignora la probabilidad de llegar a él y el costo de la acción. Un valor esperado alto también deja margen para una trayectoria desafortunada: describe una media de resultados, no una recompensa garantizada en cada intento.

El retorno de una trayectoria puede dividirse después de su primera transición: la recompensa inmediata más el retorno descontado desde el estado siguiente. Al calcular una esperanza se obtiene una ecuación de Bellman. Esta relaciona el valor de un estado con los valores de sus sucesores, incluida la posibilidad de regresar al mismo estado.

Evalúa una política fija

Para una política determinista, solo aparece la acción que selecciona:

Cada rama aporta su probabilidad multiplicada por su recompensa inmediata más el valor futuro. Hay una ecuación por estado. En un MDP finito descontado, son ecuaciones lineales con una solución única.

Para la política «Trabajar siempre» del robot, comienza en Baja. Las dos transiciones posibles dan

Desarrolla y agrupa la incógnita: $V(L)=\mathrm{2,4}+\mathrm{0,54}V(L)-4$, por lo que $\mathrm{0,46}V(L)=-\mathrm{1,6}$. Por tanto, $V(L)\approx -\mathrm{3,48}$. La recompensa −10 permanece aunque el valor futuro de Agotada sea 0.

En Alta, ambos resultados dan 4, por lo que sus recompensas inmediatas se combinan en 4:

Agrupar términos da $\mathrm{0,37}V(H)=4+\mathrm{0,27}V(L)$. Usar el valor de Baja sin redondear produce $V(H)\approx \mathrm{8,27}$. Conserva toda la precisión al sustituir; redondea los valores presentados al final.

Añade la elección de la acción

Para obtener valores óptimos, calcula la esperanza de cada acción disponible y después toma la mejor:

La maximización está fuera del sumatorio porque el agente elige una acción antes de ver el resultado. Elegir una acción actual distinta para cada posible estado siguiente le daría información que aún no tiene.

La forma Q fija esa primera acción, pero permite elegir la mejor acción siguiente después de observar el sucesor:

Estas ecuaciones de optimalidad contienen máximos, por lo que no se resuelven directamente mediante una sola resolución lineal de política fija.

Comprueba los valores propuestos

Usa los valores óptimos candidatos del robot $V(H)\approx \mathrm{31,50}$ y $V(L)\approx \mathrm{28,35}$. En Alta, Trabajar da $4+\mathrm{0,9}[\mathrm{0,7}(\mathrm{31,50})+\mathrm{0,3}(\mathrm{28,35})]\approx \mathrm{31,50}$. Cargar da $\mathrm{0,9}(\mathrm{31,50})=\mathrm{28,35}$. El resultado mayor coincide con el valor candidato de Alta.

En Baja, Trabajar da $\mathrm{0,6}[4+\mathrm{0,9}(\mathrm{28,35})]+\mathrm{0,4}(-10)\approx \mathrm{13,71}$; Cargar da 28,35. El máximo también coincide con el valor candidato de Baja. Comprobar un solo estado dejaría la otra ecuación sin verificar. Se esperan pequeñas diferencias cuando los valores candidatos se han redondeado.

Descuenta solo el término futuro. Sustituir $R+\gamma V$ por $\gamma (R+V)$ retrasa incorrectamente la recompensa inmediata un paso.

La evaluación de políticas pregunta cuánto retorno esperado obtiene una política fija. Se conocen el modelo y la política. Durante este cálculo no se mejora ninguna elección de acción; el resultado es $V^{\pi }$, que después puede servir para un paso de mejora independiente.

Resuelve las ecuaciones exactamente

Toma la política «Trabajar con batería Alta, Cargar con batería Baja» y $\gamma =\mathrm{0,9}$. Cargar en Baja no da recompensa inmediata y siempre lleva a Alta, por lo que $V(L)=\mathrm{0,9}V(H)$. Trabajar en Alta da

Sustituye la primera ecuación en la segunda:

Entonces $\mathrm{0,127}V(H)=4$, lo que da $V(H)=4\mathrm{/}\mathrm{0,127}\approx \mathrm{31,50}$ y $V(L)\approx \mathrm{28,35}$. Esto establece los valores de esa política. Demostrar que es óptima también requiere comprobar las acciones alternativas.

La evaluación exacta resuelve una ecuación lineal por cada estado no terminal. La eliminación estándar para matrices densas cuesta del orden de $\mathrm{\mid }S{\mathrm{\mid }}^3$ operaciones. El método resulta práctico para un modelo pequeño porque las relaciones pueden examinarse directamente.

Evalúa mediante barridos repetidos

Una alternativa iterativa comienza con $V_0(s)=0$ y aplica la actualización de política fija a cada estado:

Cada nuevo valor usa el arreglo anterior. Para «Trabajar siempre», los tres primeros barridos, en el orden Alta y luego Baja, dan:

Por ejemplo, el segundo valor de Baja es $\mathrm{0,6}[4+\mathrm{0,9}(-\mathrm{1,6})]+\mathrm{0,4}(-10)=-\mathrm{2,464}$. Alta en ese mismo barrido usa el valor anterior de Alta, 4, y el valor anterior de Baja, −1,6, lo que da $4+\mathrm{0,9}[\mathrm{0,7}(4)+\mathrm{0,3}(-\mathrm{1,6})]=\mathrm{6,088}$.

Con un descuento menor que 1, los barridos convergen a aproximadamente 8,27 y −3,48. Un barrido denso de política fija cuesta del orden de $\mathrm{\mid }S{\mathrm{\mid }}^2$ operaciones porque cada estado suma sobre sus sucesores. Los modelos de transición dispersos pueden omitir los sucesores con probabilidad 0.

Interpreta los valores intermedios

Al comenzar en cero, $V_k(s)$ es la recompensa descontada esperada durante las próximas $k$ transiciones bajo la política fija, sin valor más allá de ese horizonte. El primer barrido solo ve las recompensas inmediatas. El segundo incluye una transición más. Estos valores intermedios tienen un significado claro incluso antes de la convergencia.

Actualizar sobre el mismo almacenamiento usa algunos valores recién calculados dentro del mismo barrido. Con las condiciones habituales de descuento también puede converger, pero sus arreglos intermedios no tienen por qué ser iguales a estos valores síncronos de horizonte finito. En un cálculo a mano, mantén separados los arreglos antiguo y nuevo al comparar barridos síncronos.

No añadas un máximo sobre las acciones durante la evaluación. Eso permitiría al agente cambiar su comportamiento y respondería a una pregunta distinta de la que define la política fija.

La iteración de valores pregunta repetidamente qué es lo mejor cuando se permite una decisión más. Comienza con $V_0=0$ y actualiza cada estado con su mejor recompensa esperada más el valor descontado de sus sucesores. El mismo cálculo maneja ciclos porque los valores de los sucesores proceden de un arreglo almacenado.

Realiza un barrido completo

Para cada estado no terminal, calcula

En el primer barrido del robot, todos los términos futuros son 0. Alta compara Trabajar con 4 y Cargar con 0, por lo que $V_1(H)=4$. Baja compara Trabajar con $\mathrm{0,6}(4)+\mathrm{0,4}(-10)=-\mathrm{1,6}$ y Cargar con 0, por lo que $V_1(L)=0$.

El segundo barrido usa todo este arreglo anterior. En Alta, Trabajar da $4+\mathrm{0,9}[\mathrm{0,7}(4)+\mathrm{0,3}(0)]=\mathrm{6,52}$, mientras que Cargar da $\mathrm{0,9}(4)=\mathrm{3,6}$. En Baja, Trabajar sigue dando −1,6, mientras que Cargar da 3,6. Así, $V_2=(\mathrm{6,52};\mathrm{3,6})$. Un tercer barrido da aproximadamente $(\mathrm{9,08};\mathrm{5,87})$.

Si el nuevo valor de Alta, 6,52, se usara inmediatamente para actualizar Baja, el resultado sería distinto. Esa es una actualización sobre el mismo almacenamiento, no el segundo barrido síncrono que se acaba de mostrar.

Comprende qué converge

Con inicialización en cero, $V_k$ es el retorno esperado óptimo cuando quedan exactamente $k$ oportunidades de decisión, permitiendo que los episodios terminales terminen antes. Cada barrido amplía en uno el horizonte de planificación útil. El operador de optimalidad de Bellman es una contracción para $\gamma <1$: el mayor error entre los estados se reduce al menos por un factor de $\gamma$ en cada aplicación. Los valores convergen al único $V^{\ast }$ desde cualquier arreglo inicial finito.

Un barrido denso considera estados, acciones y sucesores, con un costo del orden de $\mathrm{\mid }S{\mathrm{\mid }}^2\mathrm{\mid }A\mathrm{\mid }$ operaciones. Un descuento cercano a 1 suele ralentizar la convergencia porque las recompensas lejanas conservan más peso.

Detente con una cota de error

Sea ${\mathrm{\Delta }}_k={\max }_s\mathrm{\mid }{V}_{k+1}(s)-V_k(s)\mathrm{\mid }$. Para $0<\gamma <1$, el error máximo del nuevo arreglo está acotado por $\gamma {\mathrm{\Delta }}_k\mathrm{/}(1-\gamma )$. Para garantizar un error inferior a una tolerancia elegida $\epsilon$, basta con que

Para $\gamma =\mathrm{0,9}$ y una tolerancia de 0,01, el umbral es aproximadamente 0,00111. Un cambio inferior a 0,01 por sí solo no certifica un error de valor inferior a 0,01. Con $\gamma =0$, una sola actualización da las recompensas inmediatas óptimas, por lo que no es necesario dividir por el descuento.

Obtén la política

Después de detenerte, compara las esperanzas de las acciones usando el arreglo de valores final. Esta anticipación de un paso da una política voraz. La política puede estabilizarse antes que los valores: la política voraz del robot a partir de $V_1$ ya indica «Trabajar con batería Alta, Cargar con batería Baja», pero sus valores necesitan 77 barridos para quedar a menos de 0,01 del par óptimo $(\mathrm{31,50};\mathrm{28,35})$.

Una política que parece estable y unos valores precisos son dos comprobaciones distintas. La actualización debe comparar los resultados esperados de cada acción; seleccionar únicamente el sucesor posible de mayor valor omite tanto el riesgo como la recompensa inmediata.

La iteración de políticas alterna dos tareas: medir una política y después mejorar sus acciones con esa medición. Comienza con cualquier política determinista. Una buena estimación inicial puede ahorrar trabajo, pero no es necesaria para que el método sea correcto en un MDP finito descontado.

Separa la evaluación de la mejora

Primero calcula $V^{{\pi }_i}$, los valores de la política actual. Después, para cada estado, compara todas las acciones usando esos mismos valores:

La evaluación describe el comportamiento anterior. La mejora pregunta si cambiar la primera acción mejoraría el retorno si después se siguiera la política anterior. Cambiar todas esas acciones produce una política al menos igual de buena en cada estado. Si la política anterior no es óptima, la mejora es estricta en al menos un estado.

Conserva la acción actual siempre que empate con la mejor. De lo contrario, acciones igual de buenas pueden hacer que parezca que una política sigue cambiando aunque no haya mejora de valor.

Mejora la política del robot

Comienza con «Trabajar siempre». La evaluación exacta da aproximadamente 8,27 en Alta y −3,48 en Baja. En Alta, conservar Trabajar da 8,27; cambiar a Cargar da $\mathrm{0,9}(\mathrm{8,27})\approx \mathrm{7,45}$. Conserva Trabajar. En Baja, Trabajar da −3,48 y Cargar da aproximadamente 7,45. Cambia Baja a Cargar.

Ahora evalúa la nueva política «Trabajar con batería Alta, Cargar con batería Baja». Sus valores son aproximadamente 31,50 y 28,35. Mejora de nuevo:

Ninguna acción cambia, así que la iteración de políticas se detiene. Los valores de la política fija también satisfacen las ecuaciones de optimalidad, lo que demuestra que esta política es óptima. El robot necesitó dos evaluaciones completas desde esta política inicial.

Explica por qué termina el proceso

Un MDP finito solo tiene un número finito de políticas deterministas. Si cada uno de los $\mathrm{\mid }S\mathrm{\mid }$ estados tiene $\mathrm{\mid }A\mathrm{\mid }$ opciones, hay $\mathrm{\mid }A{\mathrm{\mid }}^{\mathrm{\mid }S\mathrm{\mid }}$ políticas de este tipo. El robot tiene dos estados no terminales con dos acciones cada uno, lo que da $2^2=4$ políticas. Con mejora estricta cuando sea necesaria y una gestión coherente de los empates, el proceso no puede volver a una política peor y debe terminar.

Compara los métodos de planificación

Las evaluaciones completas hacen más costosas las rondas de iteración de políticas, pero a menudo se necesitan menos rondas. Los 77 barridos de iteración de valores y las dos evaluaciones de políticas del robot son unidades de trabajo distintas, por lo que los conteos por sí solos no establecen qué método es más rápido. Usa los valores que pertenecen a la política actual durante cada mejora; mezclarlos con valores de una política anterior rompe el significado de ese paso.

En el aprendizaje por refuerzo, un agente aprende de la experiencia en un problema de decisión. Observa un estado, elige una acción disponible y recibe una muestra $(s,a,r,s^{\mathrm{\prime }})$: el estado anterior, la acción, la recompensa y el estado siguiente. El objetivo sigue siendo obtener un retorno esperado alto, pero deben aprenderse las probabilidades de transición y las recompensas.

Separa el aprendizaje de la planificación

La planificación usa un modelo de MDP para calcular valores o políticas. Puede tener lugar antes de actuar o mientras un agente vuelve a planificar durante su funcionamiento. El aprendizaje usa la experiencia observada, ya sea de la interacción continua o de un conjunto de datos recogido previamente. El aprendizaje por refuerzo fuera de línea también aprende de la experiencia; simplemente usa experiencias registradas.

En el aprendizaje pasivo, la política es fija y la tarea consiste en estimar qué tan bien funciona. En el aprendizaje activo, el agente también elige acciones para descubrir mejores comportamientos. Esas elecciones afectan tanto a la recompensa obtenida como a la información disponible para futuras actualizaciones.

Estima las transiciones mediante conteos

Un agente que aprende basado en modelos registra cuántas veces se prueba cada acción en cada estado. Sea $N(s,a)$ el número de esos ensayos y $N(s,a,s^{\mathrm{\prime }})$ el número de ensayos que terminan en un sucesor concreto. Entonces

Los conteos del numerador dividen los ensayos del denominador según su resultado, por lo que sus probabilidades estimadas suman 1. Un par no probado tiene denominador 0 y necesita más experiencia o una elección explícita de modelado; todavía no tiene una distribución de transición empírica.

Para el robot, Trabajar en Alta se probó 20 veces: 13 transiciones permanecieron en Alta y 7 llegaron a Baja. Las estimaciones son $13\mathrm{/}20=\mathrm{0,65}$ y $7\mathrm{/}20=\mathrm{0,35}$. Trabajar en Baja se probó 10 veces: en 7 conservó batería y en 3 llegó a Agotada, lo que da 0,7 y 0,3. La segunda estimación subestima la probabilidad real de quedarse sin batería, 0,4.

Registra también las recompensas de cada transición. El robot tiene recompensas fijas para sus resultados. Si las recompensas de transiciones idénticas repetidas tienen ruido, estima su recompensa media condicionada a partir de las muestras observadas.

Planifica con el modelo aprendido

Usa las transiciones y recompensas estimadas en la iteración de valores o de políticas. Para estos conteos del robot, con las transiciones de Cargar conocidas y $\gamma =\mathrm{0,9}$, los valores óptimos estimados son aproximadamente $(\mathrm{30,42};\mathrm{27,38})$. Las acciones óptimas siguen coincidiendo con las del modelo real: Trabajar en Alta, Cargar en Baja. Por tanto, distintas estimaciones de valores pueden dar lugar a políticas similares.

Pocas muestras pueden producir modelos inexactos. Una experiencia más representativa mejora las estimaciones, pero recoger datos solo bajo una política limitada puede dejar acciones útiles sin probar. Un agente que aprende basado en modelos también necesita explorar.

Compara dos vías de aprendizaje

Un modelo aprendido puede reutilizar muestras para muchas actualizaciones de planificación y permitir volver a planificar cuando cambian los objetivos. También requiere almacenamiento y cálculo, y los errores del modelo pueden distorsionar el plan. Los métodos sin modelo evitan construir una tabla de transiciones, pero suelen requerir mucha experiencia para que sus estimaciones de valores sean fiables.

Una política fija puede evaluarse sin conocer su modelo de transición. La evaluación directa promedia retornos completos muestreados. El aprendizaje por diferencias temporales, o aprendizaje TD, actualiza a partir de una sola recompensa y una estimación del valor del sucesor. Ambos aprenden los valores de la política a partir de la experiencia.

Promedia retornos de episodios completos

Sigue «Trabajar siempre» con $\gamma =\mathrm{0,9}$. Un episodio del robot es Alta → Alta (+4), Alta → Baja (+4), Baja → Agotada (−10). Los retornos desde sus visitas a Alta son $4+\mathrm{0,9}(4)+\mathrm{0,81}(-10)=-\mathrm{0,5}$ y $4+\mathrm{0,9}(-10)=-5$. Su retorno desde Baja es −10.

Un segundo episodio es Alta → Baja (+4), Baja → Baja (+4), Baja → Agotada (−10). Su retorno desde Alta es −0,5; sus retornos desde Baja son −5 y −10. Las medias de todas las visitas son, por tanto, $(-\mathrm{0,5}-5-\mathrm{0,5})\mathrm{/}3=-2$ para Alta y $(-10-5-10)\mathrm{/}3\approx -\mathrm{8,33}$ para Baja. Un método de primera visita contaría solo la primera visita a un estado en cada episodio.

Estas estimaciones difieren mucho de los valores reales de la política $(\mathrm{8,27};-\mathrm{3,48})$ porque ambos episodios terminaron pronto. Los retornos completos presentan variación de muestreo. Con suficientes episodios completos y representativos, sus medias se acercan a los retornos esperados de la política. La evaluación directa espera hasta que el retorno necesario esté disponible al final del episodio y estima los estados por separado.

Actualiza después de una transición

TD usa la estimación actual de lo que sigue:

El objetivo es $r+\gamma V(s^{\mathrm{\prime }})$. El error TD es el objetivo menos la estimación actual. La tasa de aprendizaje $\alpha$ controla la fracción de ese error que se usa en la actualización.

Supón que $V(H)=10$, $V(L)=8$, $\gamma =\mathrm{0,9}$ y $\alpha =\mathrm{0,5}$. Después de Alta → Baja con recompensa 4, el objetivo es $4+\mathrm{0,9}(8)=\mathrm{11,2}$. El error es $\mathrm{11,2}-10=\mathrm{1,2}$, por lo que la nueva estimación de Alta es $10+\mathrm{0,5}(\mathrm{1,2})=\mathrm{10,6}$. El valor almacenado de Baja sigue siendo 8 en esta actualización. Un estado siguiente terminal no aporta ningún término futuro.

TD actualiza mediante estimaciones: usa una estimación para mejorar otra. Esto transmite información entre estados conectados y permite actualizar en tareas continuas, pero los objetivos iniciales pueden estar sesgados por estimaciones deficientes de los sucesores.

Controla cuánto cuenta la nueva evidencia

Una tasa de aprendizaje grande reacciona intensamente a cada objetivo. Con $\alpha =1$ la estimación antigua se sustituye por el último objetivo. Una tasa positiva fija generalmente sigue el ruido de las muestras. Las tasas que disminuyen adecuadamente, junto con visitas repetidas y los supuestos habituales de un problema finito y descontado, favorecen la convergencia TD tabular. Una tasa $1\mathrm{/}N(s)$ promedia la secuencia de objetivos TD observados; esos objetivos cambian a medida que mejoran las estimaciones de los sucesores.

Los valores de estado por sí solos no revelan la mejor acción sin información de transición y recompensa para una anticipación. TD pasivo evalúa el comportamiento que genera sus muestras. Aprender valores de acción da al agente una forma directa de comparar acciones sin aprender primero un modelo.

El aprendizaje Q aprende valores de acción a partir de transiciones observadas. Su objetivo supone la mejor acción siguiente, incluso mientras el agente elige acciones exploratorias. Esto le permite aprender a actuar bien sin estimar un modelo de transición.

Sustituye una actualización esperada por una muestra

Una actualización Q basada en modelos promedia todos los sucesores posibles:

El aprendizaje Q observa un sucesor cada vez. Después de una muestra $(s,a,r,s^{\mathrm{\prime }})$, calcula

y actualiza $Q(s,a)\leftarrow Q(s,a)+\alpha [y-Q(s,a)]$. Un sucesor terminal hace que $y=r$. El máximo se toma sobre las acciones disponibles en el estado siguiente, no en el estado que se acaba de dejar.

Inicializa la tabla Q, elige una acción con una regla de exploración, observa el resultado, actualiza la entrada seleccionada y continúa desde el estado siguiente. Reinicia después de la terminación. Para usar la política aprendida, selecciona una acción que alcance el mayor valor Q de la fila actual.

Resuelve dos actualizaciones

Sean $\gamma =\mathrm{0,9}$ y $\alpha =\mathrm{0,5}$. Inicialmente $Q(L,\text{Trabajar})=5$. El robot prueba Trabajar en Baja y se queda sin batería con recompensa −10. El objetivo es −10, por lo que el nuevo valor es $5+\mathrm{0,5}(-10-5)=-\mathrm{2,5}$. No hay retorno futuro después de Agotada.

Después supón que $Q(H,\text{Trabajar})=6$ y el robot trabaja en Alta, obtiene 4 y llega a Baja. En Baja las estimaciones son −2,5 para Trabajar y 3 para Cargar. El mejor valor siguiente es 3, lo que da el objetivo $4+\mathrm{0,9}(3)=\mathrm{6,7}$. El valor actualizado de Alta-Trabajar es $6+\mathrm{0,5}(\mathrm{6,7}-6)=\mathrm{6,35}$. Esta muestra solo actualiza esa entrada de la tabla.

Distingue el comportamiento objetivo del comportamiento real

El aprendizaje Q es fuera de la política: la continuación en su objetivo es voraz, aunque su regla de selección de acciones explore. SARSA aprende según la política: usa $r+\gamma Q(s^{\mathrm{\prime }},a^{\mathrm{\prime }})$ para la acción realmente elegida a continuación.

Cerca de un precipicio, un agente que explora puede dar pasos peligrosos por accidente. SARSA tiene en cuenta esas futuras acciones exploratorias y puede aprender una ruta más prudente. El aprendizaje Q tiene como objetivo la continuación voraz y puede favorecer una ruta más corta junto al borde, incluso cuando la exploración hace arriesgados sus recorridos de entrenamiento.

Enuncia con precisión la garantía tabular

En un MDP finito y estacionario con recompensas acotadas y $\gamma <1$, el aprendizaje Q tabular converge a $Q^{\ast }$ con probabilidad 1 cuando cada par estado-acción recibe infinitas actualizaciones y sus tasas de aprendizaje satisfacen

Una tasa por par $1\mathrm{/}N(s,a)$ tiene esta forma. Una tasa $1\mathrm{/}N(s,a{)}^2$ disminuye demasiado rápido: su suma total es finita, por lo que puede dejar un ajuste insuficiente para eliminar un error inicial. Un ajuste total infinito evita que el aprendizaje se detenga demasiado pronto; un ajuste cuadrático finito controla el ruido acumulado. Las tasas constantes generalmente mantienen fluctuaciones en tareas estocásticas. Estas son condiciones en el límite, por lo que un entrenamiento finito aún necesita evaluación.

La explotación selecciona la acción que actualmente parece mejor. La exploración reúne información que puede revelar una opción mejor. Si un intento inicial desafortunado de Trabajar hace que el robot prefiera Cargar en Alta, la explotación pura puede mantenerlo cargando para siempre y dejar sin corregir la estimación de Trabajar.

Cuenta correctamente la rama aleatoria

Una regla épsilon-voraz explora de manera uniforme con probabilidad $\epsilon$ y, en caso contrario, elige una acción voraz. Supón que hay una acción voraz entre cuatro y $\epsilon =\mathrm{0,2}$. Su probabilidad de selección es $\mathrm{0,8}+\mathrm{0,2}\mathrm{/}4=\mathrm{0,85}$. Cada una de las demás acciones tiene probabilidad 0,05. La rama aleatoria también incluye la acción voraz.

Una exploración baja al principio del entrenamiento puede dejar acciones útiles sin probar; una exploración alta al final sigue sacrificando recompensa. Un programa puede volverse voraz en el límite y seguir probando cada par relevante infinitas veces. Esta propiedad GLIE es más fuerte que simplemente reducir épsilon, y la alcanzabilidad influye en si se visitan todos los estados.

Favorece las acciones con poca evidencia

Una función de exploración puede añadir una bonificación a una estimación de valor. Con $f(u,n)=u+k\mathrm{/}n$ para una acción probada, elige la acción con la mayor puntuación. Da prioridad a las acciones no probadas, por ejemplo, con la puntuación $+\mathrm{\infty }$. Con $k=10$, un valor 5 probado 20 veces obtiene 5,5; un valor 4 probado dos veces obtiene 9. Se selecciona la acción menos probada pese a su menor estimación actual.

La bonificación también puede entrar en un objetivo de actualización: $r+\gamma {\max }_{a^{\mathrm{\prime }}}f(Q(s^{\mathrm{\prime }},a^{\mathrm{\prime }}),N(s^{\mathrm{\prime }},a^{\mathrm{\prime }}))$. Esto propaga el atractivo de las acciones no exploradas hacia los estados anteriores. Los valores Q iniciales optimistas también pueden animar a probar acciones cuyas estimaciones aún no se han corregido con la experiencia.

Usa una cota de confianza para problemas de bandido

Un problema del bandido multibrazo tiene un estado de decisión y varios brazos con recompensas medias fijas desconocidas. Cada tirada enseña al agente algo sobre la distribución de recompensa de un brazo. UCB1 supone extracciones de recompensa independientes y acotadas, con una distribución fija por brazo; reescala las recompensas al intervalo de 0 a 1. Tira de cada brazo una vez y después elige la mayor puntuación

Aquí ${\bar{x}}_j$ es la media muestral del brazo $j$, $n_j$ su número de tiradas y $N$ el número total entre todos los brazos. La bonificación aumenta para los brazos con pocas muestras. Con medias de 0,6 y 0,5 después de 10 y 2 tiradas, $N=12$. Las puntuaciones son aproximadamente 1,30 y 2,08, por lo que se selecciona el segundo brazo. La puntuación puede superar 1 aunque las recompensas observadas no puedan: es un índice de decisión, no una recompensa observada.

Mide el costo del aprendizaje

El arrepentimiento acumulado compara la recompensa obtenida con la que habrían producido las elecciones óptimas. En un problema de bandido estacionario con un brazo realmente inferior, un épsilon positivo fijo sigue seleccionando ese brazo con una frecuencia positiva, lo que produce un arrepentimiento esperado lineal. Bajo sus supuestos de bandido estocástico, UCB1 tiene un arrepentimiento esperado logarítmico. Un programa de épsilon decreciente cuidadosamente ajustado también puede alcanzar ese orden; una disminución arbitraria no puede garantizarlo.

El objetivo fuera de la política del aprendizaje Q permite usar muestras exploratorias sin redefinir los valores óptimos que busca. La exploración sigue afectando a la recompensa obtenida durante el entrenamiento. Para sistemas físicos, usa simulación, experiencia registrada o límites de acciones permitidas para evitar que la exploración cause daños.

Una tabla Q almacena un número por cada par estado-acción. En un problema grande, es posible que muchos pares nunca se visiten. Las entradas separadas tampoco comparten evidencia entre situaciones similares. El aprendizaje Q aproximado sustituye la tabla por una función de características.

Representa valores con una suma ponderada

Una característica $f_i(s,a)$ es un número que describe un aspecto del estado y la acción. Para un robot de reparto, las características podrían describir el nivel de batería, la distancia a un cargador y los paquetes pendientes. Una aproximación lineal se escribe

Los pesos $w_i$ describen cuánto contribuye cada característica. Las características pueden depender tanto de la acción como del estado, lo que permite que distintas elecciones en el mismo estado tengan valores diferentes.

Actualiza cada peso a partir de un error

Calcula el valor Q actual y después el objetivo $y=r+\gamma {\max }_{a^{\mathrm{\prime }}}Q(s^{\mathrm{\prime }},a^{\mathrm{\prime }})$. La diferencia $\delta =y-Q(s,a)$ determina cada actualización:

Todos los valores usados para el objetivo y el error proceden de los pesos anteriores a la actualización. Una característica con valor cero no cambia su peso. Una característica distinta de cero escala el ajuste, incluido su signo.

Para los pesos $(1;-\mathrm{0,5})$ y las características actuales $(1,2)$, la estimación es $1(1)+(-\mathrm{0,5})(2)=0$. Supón que la recompensa es 4, el mejor valor Q siguiente es 4 y $\gamma =\mathrm{0,9}$. El objetivo es $4+\mathrm{0,9}(4)=\mathrm{7,6}$, por lo que $\delta =\mathrm{7,6}$. Con $\alpha =\mathrm{0,1}$:

La nueva estimación para las mismas características pasa a ser $\mathrm{1,76}+\mathrm{1,02}(2)=\mathrm{3,8}$. Una actualización de pesos compartidos no equivale a sustituir una entrada independiente de la tabla por el objetivo.

Comprende el alcance y los límites de compartir

Un peso participa en muchas predicciones. Actualizarlo cambia los valores de todos los pares en los que esa característica tiene un valor distinto de cero. Esto es generalización y puede ayudar al agente a actuar de forma razonable en estados no vistos. También puede propagar una actualización errónea.

Si dos situaciones tienen vectores de características idénticos para cada acción correspondiente, el modelo debe darles valores de acción idénticos. Si requieren acciones diferentes, ningún ajuste de pesos puede representar correctamente ambas decisiones. Se necesitan mejores características o una función más rica. El aprendizaje tabular es el caso particular con una característica indicadora por cada par estado-acción, activa solo para ese par.

La garantía de convergencia del aprendizaje Q tabular no se extiende a una aproximación de funciones arbitraria. La actualización mediante estimaciones fuera de la política con predicciones compartidas puede oscilar o divergir, por lo que debes evaluar la política aprendida en ensayos separados. Las redes Q profundas aprenden características a partir de entradas como los píxeles de una pantalla de juego; la búsqueda de políticas, en cambio, ajusta directamente una política para aumentar el retorno.