🤖 Navegador Robótico — Iteración de Valores MDP en Vivo

La iteración de valores es un algoritmo de programación dinámica basado en modelo para resolver un Proceso de Decisión de Markov (MDP): un espacio de estados S, un espacio de acciones A, un modelo de transición conocido P(s'|s,a), una función de recompensa R(s,a,s'), y un factor de descuento γ. Partiendo de una función de valor arbitraria V(s), aplica repetidamente la actualización de optimalidad de Bellman V(s) ← max_a Σ_s' P(s'|s,a)[R(s,a,s') + γV(s')] a todos los estados simultáneamente (un barrido síncrono). Como esta actualización es una aplicación de contracción bajo γ<1, los barridos repetidos convergen demostrablemente a la única función de valor óptima V*, a partir de la cual la política óptima π*(s) = argmax_a Σ_s' P(s'|s,a)[R(s,a,s') + γV*(s')] puede leerse directamente.

La iteración de valores está basada en modelo: requiere que las probabilidades de transición P(s'|s,a) y la función de recompensa R(s,a,s') se conozcan de antemano, y calcula una expectativa exacta sobre cada posible resultado de cada acción en cada estado en cada barrido; no se necesita ninguna simulación ni exploración del entorno. El Q-learning (cubierto en la simulación de aprendizaje por refuerzo independiente de este sitio) no tiene modelo: el agente no conoce P ni R de antemano, así que debe actuar realmente en el entorno, observar transiciones muestreadas (s, a, r, s'), y actualizar incrementalmente Q(s,a) con una regla de diferencia temporal Q(s,a) ← Q(s,a) + α[r + γ·max_a' Q(s',a') − Q(s,a)]. La iteración de valores converge al V* exacto en un número acotado de barridos dado el modelo; el Q-learning converge solo asintóticamente, mediante exploración por ensayo y error, y no necesita ningún modelo de transición explícito. Esta simulación implementa deliberadamente el caso basado en modelo para que las dos familias de algoritmos se puedan distinguir claramente.

Los robots reales y los agentes físicos rara vez ejecutan una acción a la perfección: las ruedas resbalan, los sensores derivan y los suelos son irregulares. Esta simulación modela eso con un modelo de transición estocástico clásico: elegir moverse en una dirección dada tiene éxito con probabilidad P(intencionada) (ajustable, por defecto 0,80), mientras que la probabilidad restante se reparte por igual entre desviarse 90° a la izquierda y 90° a la derecha del rumbo deseado. La actualización de Bellman suma sobre los tres resultados posibles ponderados por sus probabilidades, que es exactamente lo que hace de esto un MDP genuino en lugar de una búsqueda de camino más corto determinista: la política óptima tiene que cubrirse ante la posibilidad de un deslizamiento no deseado contra una pared u obstáculo.

Tres términos de recompensa se combinan para definir R(s,a,s'): un pequeño coste negativo por paso (por defecto −0,04) cobrado en cada movimiento no terminal, que presiona a la política óptima hacia caminos más cortos; una penalización por golpe con obstáculo o pared (por defecto −0,75) cobrada siempre que una transición sea bloqueada por una pared, un obstáculo o el límite de la cuadrícula, que presiona a la política a mantener un margen de seguridad alrededor de los obstáculos, especialmente cuando las transiciones son ruidosas; y una recompensa terminal de meta (+1) recibida al entrar en la celda objetivo, que es lo que hace que valga la pena alcanzar la meta. La iteración de valores propaga los tres a través de la actualización de Bellman, de modo que las celdas cercanas a la meta adquieren valores altos primero, y esa señal de alto valor se extiende hacia atrás, barrido tras barrido, hasta que cada estado alcanzable tiene una estimación precisa de su retorno esperado a largo plazo.

Cada barrido síncrono registra el cambio absoluto máximo en el valor de cualquier estado, max_s |V_nuevo(s) − V_viejo(s)|, y la simulación traza esta cantidad en escala logarítmica frente al número de barrido. Como el operador de optimalidad de Bellman es una contracción-γ, esta secuencia de delta máximo está garantizada a reducirse monótonamente hacia cero; la simulación declara la convergencia una vez que cae por debajo de 1e-4. En ese punto, V(s) está dentro de un error pequeño y acotado del verdadero V*(s), y la política voraz extraída de él, π(s) = argmax_a Q(s,a), es la política óptima para el MDP tal como está configurado.

Sí. γ controla cuánto influyen en el valor de un estado las recompensas muchos pasos en el futuro: con γ cercano a 1, las recompensas de meta lejanas se propagan casi sin disminuir por toda la cuadrícula, así que la política óptima planifica con antelación y está dispuesta a tomar desvíos más largos y seguros alrededor de los obstáculos. Con γ más cercano a 0,5, las recompensas futuras se descuentan bruscamente, así que la política se vuelve miope: puede aceptar una ruta más corta pero más arriesgada junto a un obstáculo porque el valor descontado de alcanzar la meta unos pasos después no vale mucho más que alcanzarla un paso antes. γ también controla la velocidad de convergencia: un γ más pequeño hace que el operador de Bellman contraiga más rápido, así que factores de descuento más bajos suelen converger en menos barridos.