8. Programación Dinámica

Introducción al Algoritmo Val

Conceptos Básicos del Algoritmo

• Se presenta el algoritmo Val, que es similar a la iteración de políticas (policy iteration), utilizando funciones de valor para explorar el espacio de políticas sin una política explícita.

• El espacio de la función de valor es n-dimensional, donde n representa el número de estados en el espacio. Cada punto en este espacio indica la expectativa de recompensa acumulada a largo plazo desde un estado específico.

Evaluación y Función de Valor

• La función de valor proporciona información sobre lo que se espera ganar a partir de diferentes estados, evaluando una política específica.

• Los valores en este vector representan las recompensas esperadas acumuladas si se parte desde cada uno de los estados del sistema.

Ejemplo Práctico

• Se ilustra un sistema simple con tres estados, donde cada estado tiene transiciones regidas por la dinámica del ambiente y las acciones tomadas.

• El valor asociado a un estado indica cuánto se espera ganar a largo plazo siguiendo una política determinada.

Iteración y Evaluación de Políticas

Proceso Inicial

• En la iteración de políticas, se comienza con una política arbitraria (por ejemplo, aleatoria o determinista).

• Se inicia un proceso llamado evaluación de políticas (policy evaluation), comenzando típicamente desde un punto inicial en el espacio de funciones que suele ser cero.

Objetivo y Resultados

• El objetivo es calcular el valor esperado acumulado para la política inicial. Este proceso implica moverse hacia un punto conocido como bp, que representa el valor esperado bajo esa política.

• La fase clave es determinar cuál es el valor esperado al seguir una política específica desde cualquier estado dado.

Mejoramiento y Optimización

Teorema del Mejoramiento

• A partir del valor obtenido, se puede aplicar el teorema del mejoramiento (policy improvement), generando así otra política que sea estrictamente mejor.

• Esta nueva política (pi prima) se desarrolla utilizando la función de valor obtenida previamente, moviéndose hacia una dirección óptima en términos del control político.

Iteraciones Adicionales

• Es posible calcular nuevamente la función de valor para esta nueva política pi prima mediante otro ciclo similar al anterior.

Evaluación de Políticas y Iteraciones

Introducción a la Evaluación de Políticas

• Se discute el proceso de evaluación de políticas (policy evaluation) como un medio para llegar a una política óptima, destacando la importancia de las fases consecutivas de evaluación y mejora.

• Se enfatiza que el término "policy" es fundamental en este contexto, sugiriendo que se debe tener claro su significado.

Generación de Políticas Arbitrarias

• Se plantea un escenario donde se lanza un dardo al azar para establecer un punto arbitrario desde el cual se puede generar una política de control.

• A partir del valor arbitrario, se puede crear una política (denominada BX), aunque su calidad no está garantizada debido a la naturaleza aleatoria del valor inicial.

Progreso hacia la Política Óptima

• La discusión gira en torno a cómo, incluso con valores arbitrarios, es posible avanzar hacia una mejor política mediante evaluaciones sucesivas.

• Se menciona que si uno se detiene prematuramente en el proceso de evaluación, aún podría derivar una nueva política basada en los pasos dados hasta ese momento.

Iteraciones y Actualizaciones

• La idea central es que cada iteración puede llevar a mejoras significativas en la dirección correcta hacia la política óptima.

• Se introduce el concepto de "Val iteration", donde las actualizaciones son realizadas basándose en estimaciones actuales sin necesidad de tener una función explícita.

Convergencia hacia la Optimalidad

• El proceso se detiene cuando se alcanza la función óptima, lo cual está relacionado con la ecuación de optimalidad conocida como Bellman.

• Aunque no hay una política explícita durante las iteraciones, es posible derivar políticas utilizando los valores obtenidos hasta ese momento.

Generación Continua de Nuevas Políticas

• En cada iteración del Val iteration, se genera continuamente una nueva política basada en los valores actuales y las mejores acciones disponibles.

¿Cuál es la dinámica en la industria?

Dinámica y algoritmos en la industria

• Se discute que los algoritmos presentados no son utilizados directamente en la industria, lo que resalta la importancia de entender la dinámica general de los problemas.

• Aunque no se utilicen estos métodos, el desarrollo de intuiciones y teorías sobre su comportamiento es fundamental para resolver problemas de optimización.

Evaluación y mejora de políticas

• La elección del mejor algoritmo depende del problema específico; a menudo, las mejores soluciones no son extremas.

• Se pueden combinar pasos de evaluación y mejora de políticas, permitiendo flexibilidad en el enfoque según las iteraciones necesarias.

Mejorando estimaciones con múltiples pasos

Estimaciones avanzadas

• Hasta ahora, se ha utilizado un enfoque de "un paso" para calcular valores esperados; sin embargo, se puede mejorar al considerar múltiples pasos.

• Calcular el valor esperado a través de K pasos proporciona estimaciones más precisas al complementar con estimaciones previas.

Complejidad computacional

• Aumentar el número de pasos incrementa exponencialmente la complejidad del cálculo; existen algoritmos específicos que optimizan este proceso.

Iteración de valor y convergencia

Proceso iterativo

• La iteración de valor utiliza la ecuación de Bellman como regla para actualizar valores; encontrar igualdad entre ambos lados indica una solución única.

• Se demuestra que esta secuencia converge bajo ciertas condiciones, similares a las requeridas para garantizar funciones óptimas.

Práctica vs. teoría

Evaluación de Políticas y Valor en el Algoritmo del Borracho

Progreso en la Iteración de Valores

• Se revisa cómo cambia la evaluación de políticas a través del ejemplo del "borracho", ilustrando el proceso de iteración de valores.

• A pesar de que la política inicial es subóptima, se puede derivar una política óptima con pocas iteraciones, lo que refleja un fenómeno común en la práctica.

Caminando hacia el Valor Óptimo

• La discusión se centra en cómo se avanza hacia el valor óptimo, enfatizando que no solo se busca cualquier política, sino específicamente la óptima.

• Se menciona que el algoritmo implica establecer ecuaciones y un hiperparámetro para medir el progreso durante las iteraciones.

Implementación del Algoritmo

• El algoritmo comienza con un valor inicial arbitrario para la función de valor, asegurándose de que los estados terminales tengan un valor cero.

• Se detiene cuando el progreso es menor que un umbral definido (theta), devolviendo finalmente una política basada en los valores alcanzados.

Complejidad en la Programación

• La complejidad radica tanto en modelar dinámicas como en programar las políticas; esto es similar al caso anterior sobre carros.

• La dificultad principal proviene de calcular sumas ponderadas de probabilidades para transiciones entre estados.

Transiciones y Recompensas

• Para cada estado, es necesario especificar explícitamente las probabilidades de transición a otros estados dentro del espacio considerado.

Cálculo de Recompensas en Saltos

Valor Esperado y Estimaciones

• Se establece que el cálculo del valor esperado de la recompensa por un salto es exacto, considerando todos los elementos involucrados.

• Se introduce la ecuación de Bellman, utilizando estimaciones anteriores para generar nuevos valores estimados a partir del cálculo exacto de recompensas.

• Se plantea la pregunta sobre cómo se mejora la calidad de la información al utilizar estimaciones previas junto con cálculos exactos.

Fuentes de Mejora en Estimaciones

• La mejora en las estimaciones proviene del cálculo exacto de lo que puede suceder respecto a las recompensas en un salto.

• El objetivo es calcular el valor esperado basado en una política dada y la dinámica del sistema, buscando maximizar las ganancias esperadas.

Refinamiento y Generalización

• Se discute la dificultad de calcular todo exactamente, sugiriendo que se puede hacer un cálculo preciso para un solo paso y luego refinarlo con estimaciones anteriores.

• La idea se expande a realizar cálculos exactos K pasos hacia adelante, combinando estos resultados con estimaciones actuales para mejorar el algoritmo.

Complejidad Algorítmica

• Al calcular múltiples pasos hacia adelante, se genera una complejidad exponencial debido a las múltiples ramas posibles en cada iteración.

• Esta técnica puede ser muy útil en ciertos contextos, proporcionando grandes beneficios al aplicar generalizaciones al algoritmo.

Evaluación de Políticas y Búsqueda Monte Carlo

• Se menciona que se pueden realizar K pasos hacia adelante junto con evaluaciones políticas múltiples para optimizar el proceso.

• Se introduce el uso de técnicas como Monte Carlo para identificar ramas prometedoras dentro del árbol algorítmico, evitando explorar todas las posibilidades innecesariamente.

Problema del Apostador y Estrategias de Apuesta

Introducción al Problema

• Se presenta el problema del apostador, donde se exploran diferentes estrategias para maximizar las ganancias en un juego de azar.

• Aunque muchas técnicas no se utilizan directamente en la industria, es crucial entender los fundamentos para aplicar otras variantes más prácticas.

Descripción del Escenario

• El problema clásico involucra a un apostador que busca minimizar sus pérdidas mientras juega con una moneda cargada (no justa).

• El apostador comienza con una cantidad específica de dinero y tiene como meta ganar 100 pesos, jugando hasta alcanzar su objetivo o perder todo.

Dinámica del Juego

• En cada ronda, el apostador decide cuánto apostar; puede arriesgar todo su capital o una parte de él.

• El estado del juego depende de la cantidad de dinero que le queda al apostador, lo que determina sus acciones posibles.

Recompensas y Políticas Óptimas

• La recompensa debe asociarse con el objetivo final: llegar a la meta monetaria. Se otorga una unidad de recompensa solo al alcanzar los 100 pesos.

• La política óptima sugiere que en ciertos estados (como tener 50 pesos), lo mejor es apostar todo para maximizar las probabilidades de ganar.

Análisis y Comparación de Estrategias

• Se discute cómo la función de valor converge hacia la probabilidad de ganar en cada estado, sugiriendo patrones interesantes en las decisiones del apostador.

• Los estudiantes deben experimentar resolviendo el problema mediante diferentes métodos (policy iteration y value iteration), comparando resultados y estrategias conservadoras frente a arriesgadas.

Reflexiones Finales sobre Estrategias

• Se plantea la importancia del tiempo y cómo variar las apuestas puede influir en los resultados finales.

¿Cómo se definen los estados y recompensas en un entorno de programación?

Definición de Estados y Recompensas

• Se menciona que solo hay un estado considerado, el cual es una acción única. La discusión gira en torno a cómo se suman los siguientes estados y recompensas.

• Se identifican dos estados: 0 pesos y 2 pesos, planteando la probabilidad de transición entre ellos. Se discute la importancia de definir correctamente estas probabilidades.

• La probabilidad de ganar se introduce como un factor clave en el análisis del estado actual, enfatizando que no hay recompensa si no se gana.

• Se aclara que las recompensas solo ocurren en transiciones específicas, lo que simplifica el modelo al tener menos formas de moverse entre estados.

Ejemplos y Ciclos

• Se plantea la idea de considerar todos los estados hacia adelante sin retroceder, sugiriendo un enfoque cíclico para el análisis.

• El objetivo del jugador es llegar a 100; si se pasa, no hay incentivos adicionales. Esto resalta la naturaleza compulsiva del juego propuesto.

¿Qué son las políticas y cómo afectan al proceso?

Iteración de Políticas

• Se comparan dos métodos: iteración de políticas (policy iteration) y iteración de valores (value iteration), analizando su tiempo de convergencia.

• Se sugieren diferentes políticas iniciales para evaluar su efectividad, incluyendo apuestas aleatorias o máximas.

Implementación Práctica

• La implementación debe incluir esquemas tanto positivos como negativos para las recompensas, preparando a los estudiantes para futuras programaciones.

¿Qué es una barrida en programación dinámica?

Concepto de Barrida

• Una "barrida" implica pasar por todos los estados para actualizar sus valores o políticas. Este proceso asegura que cada estado sea considerado adecuadamente.

Progreso Iterativo

• Los algoritmos progresan actualizando todos los estados en cada iteración, lo cual es fundamental para mantener la precisión del modelo.

Programación Dinámica Asíncrona

Actualización Distribuida

• La programación dinámica asíncrona permite actualizar ciertos estados más frecuentemente que otros según una distribución definida. Esto puede llevar a situaciones donde algunos estados nunca sean actualizados.

¿Qué es la Programación Dinámica Asíncrona?

Conceptos Clave de la Programación Dinámica

• La programación dinámica asíncrona permite realizar actualizaciones en un orden no secuencial, enfocándose en estados relevantes y evitando invertir tiempo en estados irrelevantes.

• Esta técnica facilita el "focusing", donde se puede dedicar más cómputo a los estados que realmente importan, mejorando así la eficiencia del proceso.

• A pesar de las actualizaciones arbitrarias, se mantienen las propiedades de convergencia siempre que todos los estados sean eventualmente probados.

• En la práctica, esta metodología se utiliza para aprender y controlar simultáneamente, permitiendo una interacción efectiva con el ambiente.

• Los estados donde se interactúa frecuentemente son aquellos donde se recibe experiencia valiosa, lo cual alimenta el algoritmo de aprendizaje.

Progreso y Flexibilidad en Algoritmos

• La asincronía en la programación dinámica permite seguir avanzando hacia una política de control sin necesidad de barridas completas.

• Esto otorga flexibilidad al implementar algoritmos, ya que no es necesario seguir un orden estricto para actualizar los estados visitados.

• Se enfatiza la importancia de esta propiedad para mejorar las implementaciones prácticas en entornos dinámicos.

Iteración Generalizada de Políticas

Evaluación y Mejora de Políticas

• El algoritmo general combina evaluación y mejora de políticas, utilizando pasos explícitos para calcular valores esperados que optimizan la política actual.

• Al realizar mejoras en políticas (policy improvement), se busca acercarse a la función real del valor correspondiente a esa política específica.

• Las iteraciones entre evaluación y mejora generan fuerzas opuestas que guían hacia diferentes funciones de valor; sin embargo, ambas convergen hacia una función óptima.

Eficiencia del Aprendizaje por Refuerzo

• Este enfoque global es conocido como iteración generalizada de políticas (generalized policy iteration), aplicable a diversos métodos con distintas aproximaciones.

• Aunque algunos argumentan que estas técnicas no son escalables, su eficiencia radica en resolver problemas complejos dentro del proceso de decisión marcado (Markov Decision Process).

Eficiencia Comparativa: Programación Dinámica vs. Búsqueda Espacial

Argumentos sobre Eficiencia

• A pesar de críticas sobre su escalabilidad, estudios sugieren que la programación dinámica sigue siendo una solución eficiente para problemas complejos debido a su naturaleza polinómica respecto al número de estados y acciones involucradas.

• Resolver problemas mediante programación dinámica resulta ser más eficiente comparado con búsquedas exhaustivas en espacios políticos grandes.

¿Cuál es la complejidad de la programación dinámica en procesos de decisión?

Introducción a la complejidad en programación dinámica

• Se discute sobre las diferentes formas de hacer política y se plantea la necesidad de entender la complejidad de las soluciones en programación dinámica para problemas de decisión basados en el proceso de Markov.

Factores que influyen en la complejidad

• La complejidad depende del tamaño del árbol de recursión y del arreglo de memorización requerido, lo cual es fundamental para calcular eficientemente.

• Se menciona que al considerar todas las decisiones posibles, cada acción puede llevar a múltiples estados, resultando en una complejidad inicial calculada como n por k (n * k).

Evaluación y solución del problema

• En un solo paso, se establece que hay n por k combinaciones posibles, lo que indica una relación polinomial respecto al primer paso evaluado.

• Para implementar una solución efectiva, se sugiere programar desde los casos pequeños hacia los grandes, evitando así un enfoque recursivo que podría resultar exponencialmente costoso.

Cálculo y longitud de episodios

• La solución final requiere calcular valores desde los estados finales hasta el estado inicial. Esto implica un esfuerzo adicional debido a la longitud de los episodios involucrados.

• La longitud total también influye significativamente en la complejidad general; aunque sea polinomial con respecto a n y k, otros factores pueden incrementar el tiempo computacional necesario.

Limitaciones prácticas y alternativas

• A pesar de ser polinomial respecto al número de estados, existen limitaciones prácticas que hacen que no siempre se utilice programación dinámica debido a su ineficiencia comparativa frente a métodos alternativos.

¿Qué son las regiones convexas en programación lineal?

Definición y características

• Se introduce el concepto de encontrar óptimos dentro de regiones convexas definidas por hiperplanos. Estas regiones son cruciales para resolver problemas mediante programación lineal.

• En este contexto, se explica cómo cualquier punto dentro del segmento entre dos puntos también pertenece a esta región convexa sin obstrucciones externas.

Importancia histórica y técnica

• La técnica ha sido ampliamente utilizada debido a su eficacia. Sin embargo, algunos algoritmos tradicionales como el simplex tienen limitaciones teóricas importantes ya que son exponenciales en el peor caso.

• Se menciona una carrera histórica entre soviéticos y estadounidenses para desarrollar algoritmos eficientes para resolver problemas lineales en tiempo polinomial.

Avances recientes

• Aunque los algoritmos propuestos eran polinomiales, su lentitud comparativa frente al método simplex generó debates sobre su aplicabilidad práctica.