📊 statistics

Bayesian learning for the stochastic shortest path problem

Este artículo propone un marco bayesiano para el problema de la ruta más corta estocástica que construye directamente creencias posteriores para la función de valor de acción óptima a través de las ecuaciones de optimalidad de Bellman, ofreciendo una alternativa más eficiente en datos y consciente de la incertidumbre frente a los métodos existentes basados en la diferencia temporal, al tiempo que aborda los desafíos relacionados con la relajación de la verosimilitud y la no identificabilidad.

Autores originales: Chon Wai Ho, Sumeetpal S. Singh, Jiaqi Guo

Publicado 2026-06-04

📖 6 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Chon Wai Ho, Sumeetpal S. Singh, Jiaqi Guo

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que estás intentando encontrar el camino más rápido y seguro a través de un laberinto masivo y neblinoso para llegar a un cofre del tesoro al final. Este es el problema del Camino Más Corto Estocástico (SSP, por sus siglas en inglés). No tienes un mapa. Cada vez que das un paso (una acción), podrías recibir una recompensa (como encontrar una pista) o una penalización (como chocar con un callejón sin salida), y terminas en un nuevo lugar (un estado). Tu objetivo es aprender la mejor ruta mediante el ensayo y error, pero quieres hacerlo de manera eficiente para no perder tiempo deambulando sin rumbo.

Este artículo propone una forma nueva y más inteligente de aprender esa ruta utilizando el Aprendizaje Bayesiano. Piensa en esto como un sistema de "aprendizaje por creencia". En lugar de simplemente adivinar el mejor camino, la computadora mantiene una "nube de posibilidades" (una distribución de probabilidad) sobre cómo es el mejor camino. A medida que recopila más datos, esta nube se reduce y se estrecha alrededor del verdadero mejor camino.

Aquí tienes un desgño de su enfoque utilizando analogías sencillas:

1. La idea central: Aprender la "Hoja de Puntuación"

En el aprendizaje estándar, las computadoras suelen intentar adivinar la puntuación de un movimiento directamente. Este artículo dice: "Vamos a adivinar la Hoja de Puntuación (llamada $Q^*$ ) en su lugar".

La Hoja de Puntuación: Imagina una hoja de cálculo gigante donde cada movimiento posible en cada habitación posible tiene una puntuación. Esta puntuación representa el tesoro total que obtendrías si empezaras desde ahí y jugaras perfectamente de ahí en adelante.
El Libro de Reglas (Ecuaciones de Bellman): Existe una regla matemática estricta (la Ecuación de Optimalidad de Bellman) que dice: "La puntuación de un movimiento debe ser igual a la recompensa inmediata más la mejor puntuación posible del siguiente movimiento".
La Innovación: La mayoría de los métodos existentes intentan forzar sus conjeturas para que encajen con este libro de reglas ajustando números de una manera desordenada y arbitraria. Este artículo dice: "Construyamos todo nuestro sistema de aprendizaje directamente sobre este libro de reglas". Tratan el libro de reglas como una ley de la física que los datos deben obedecer.

2. El "Manifold" frente a la "Nube Difusa"

Esta es la parte más técnica pero también la más interesante del artículo.

El Mundo Perfecto (El Manifold): Si las recompensas en el laberinto fueran perfectamente claras (sin ruido), la creencia de la computadora sobre la Hoja de Puntuación no flotaría en un espacio 3D. En su lugar, colapsaría sobre una hoja delgada y plana (un manifold) dentro de ese espacio.
- Analogía: Imagina que intentas encontrar una línea específica dibujada en un papel. Si tienes información perfecta, sabes que la respuesta está exactamente en esa línea. No necesitas mirar todo el papel; solo necesitas mirar la línea. Matemáticamente, esto es difícil de calcular porque estás intentando muestrear de una "línea" dentro de una "habitación".
El Mundo Real (La Nube Difusa): Para facilitar las matemáticas, los autores "difuminan" las reglas ligeramente. Dicen: "Está bien, la respuesta no tiene que estar exactamente en la línea; puede estar dentro de una distancia mínima de la línea".
- Analogía: En lugar de buscar una aguja en un pajar, estamos buscando una aguja dentro de una pequeña y difusa nube de heno. Esto hace que sea mucho más fácil para la computadora muestrear respuestas (usando un método llamado muestreo de Monte Carlo).

3. La Trampa: Caminos "Impropios"

El artículo descubre un efecto secundario truculento de hacer las reglas "difusas".

El Problema: En un laberinto, algunos caminos te hacen dar vueltas en círculos para siempre, sin llegar nunca al tesoro. Estos son políticas impropias.
La Trampa: Cuando los autores relajaron las reglas para facilitar las matemáticas, accidentalmente hicieron que fuera muy fácil para la computadora creer en estos caminos de "bucles infinitos".
- Analogía: Imagina que le estás enseñando a un robot a caminar hacia una puerta. Si eres demasiado permisivo con sus instrucciones, el robot podría pensar: "Oh, puedo simplemente caminar en círculos en el pasillo para siempre; ¡ese es un plan válido!". Las matemáticas muestran que, si la computadora no tiene cuidado, podría asignar una enorme cantidad de "creencia" a estos bucles infinitos e inútiles, incluso cuando ya ha visto todo el laberinto.
La Solución: El artículo advierte que hay que ser muy cuidadoso con qué tan "difusas" haces las reglas. Si las haces demasiado difusas, la computadora se confunde con los bucles infinitos. Si las haces demasiado nítidas, las matemáticas se vuelven imposibles de resolver.

4. Los Resultados: Mejor que la Competencia

Los autores probaron su método en un benchmark famoso llamado "Deep Sea" (un laberinto digital donde tienes que elegir izquierda o derecha en cada paso para encontrar un tesoro).

Eficiencia de Datos: Su método aprendió el camino correcto mucho más rápido que otros métodos bayesianos populares. Necesitó menos intentos para descifrar el mapa.
Precisión: Cuando observaron la "nube de creencias", su método identificó correctamente el mejor camino e ignoró los malos. Otros métodos a veces se quedaban atrapados creyendo en esos caminos de "bucles infinitos" o tardaban mucho más en converger.
El "Estándar de Oro": Incluso calcularon la respuesta exacta (sin la aproximación difusa) para problemas más pequeños para demostrar que su método difuso era una buena aproximación.

Resumen

El artículo presenta una nueva forma para que las computadoras aprendan el mejor camino a través de un mundo complejo e incierto.

Se construye directamente sobre las leyes matemáticas de cómo funcionan las recompensas, en lugar de usar atajos.
Reconoce que el conocimiento perfecto crea una "línea delgada" de posibilidades, lo cual es difícil de computar, por lo que utiliza una "nube difusa" para que sea manejable.
Advierte que esta "difusión" puede engañar a la computadora haciéndole creer que los bucles infinitos inútiles son buenos planes, por lo que la "difusión" debe ajustarse cuidadosamente.
En las pruebas, este método aprendió más rápido y con mayor precisión que otros métodos actuales, demostando que mantenerse cerca de las matemáticas fundamentales rinde frutos.

Los autores concluyen que, si bien su método es poderoso, el trabajo futuro necesita encontrar mejores formas de enseñar a la computadora a ignorar esas trampas de "bucles infinitos" sin tener que depender de un ajuste tan cuidadoso.

Resumen Técnico: Aprendizaje Bayesiano para el Problema de la Ruta Más Corta Estocástica

1. Formulación del Problema

El artículo aborda el problema de la Ruta Más Corta Estocástica (SSP, por sus siglas en inglés), definido como un proceso de decisión de Markov (MDP) de horizonte infinito y sin descuento, con un estado terminal absorbente. A diferencia de los MDP estándar con descuento, la formulación SSP ( $\gamma = 1$ ) requiere la existencia de un estado objetivo único con recompensa cero ( $s_g$ ) y la existencia de al menos una política "adecuada" (una política que alcanza $s_g$ con probabilidad 1 desde cualquier estado).

El objetivo principal es aprender la función de valor de acción óptima, $Q^*$ , que satisface las Ecuaciones de Optimalidad de Bellman (BOEs). El desafío radica en que $Q^*$ no se observa directamente; solo se observan tripletos de estado-acción-recompensa $(s, a, r)$ mediante la interacción. Los autores buscan construir un marco bayesiano para cuantificar la incertidumbre sobre $Q^*$ y facilitar los compromisos entre exploración y explotación mediante el Muestreo de Thompson (muestreo posterior), sin depender de las suposiciones poco realistas o aproximaciones ad-hoc comunes en la literatura existente de Aprendizaje por Refuerzo (RL) Bayesiano.

2. Metodología

2.1. Construcción de la Verosimilitud mediante las Ecuaciones de Bellman

La principal contribución metodológica es la construcción directa de la función de verosimilitud basada en las BOEs, en lugar de algoritmos de aproximación estocástica (como Q-learning) o errores de diferencia temporal (TD).

Parametrización: La función de valor óptima se aproxima mediante una función paramétrica $Q_\theta$ .
Restricción: Para un par estado-acción $(s, a)$ , la recompensa esperada $\bar{r}_{s,a}$ debe satisfacer la BOE: $\bar{r}_{s,a} = Q_\theta(s, a) - \mathbb{E}[\max_{a'} Q_\theta(S', a')]$ .
Verosimilitud: Los autores definen una función de verosimilitud $p(r_t | \theta, \psi, s_t, a_t)$ donde la recompensa observada $r_t$ se modela como la recompensa esperada determinista más ruido. Esto restringe los parámetros $\theta$ para que sean consistentes con las BOEs observadas.

2.2. Manejo de Recompensas Deterministas y Posteriores de Variedad

Un desafío teórico significativo surge cuando las recompensas son deterministas (sin ruido). En este caso, las BOEs imponen restricciones de igualdad estrictas sobre $\theta$ .

Densidad de Variedad (Manifold): La distribución posterior de $\theta$ colapsa desde el espacio de parámetros completo hacia una variedad de baja dimensión definida por la intersección de las restricciones de las BOEs.
Medida de Hausdorff: Los autores caracterizan esta posterior utilizando una densidad con respecto a la medida de Hausdorff (Teorema 2), en lugar de una densidad de Lebesgue estándar. Esto proporciona una descripción matemática rigurosa de la posterior para recompensas sin ruido.

2.3. Relajación y Aproximación de la Verosimilitud

El muestreo directo de una densidad de variedad es computacionalmente intratable para los métodos de Monte Carlo estándar. Para facilitar la inferencia, los autores proponen relajar la verosimilitud:

Convolución: La verosimilitud exacta se convierte con un núcleo (por ejemplo, Gaussiano o uniforme) con una tolerancia $\epsilon$ .
Densidad de Lebesgue: Esta relajación "engrosa" la variedad, resultando en una posterior con una densidad de Lebesgue estándar adecuada para el muestreo MCMC.
Compromiso (Trade-off): El artículo analiza rigurosamente las consecuencias de esta relajación. Si bien permite un muestreo tratable, introduce problemas de identificabilidad. Específicamente, para parametrizaciones tabulares, la verosimilitud relajada puede asignar masa infinita a conjuntos de parámetros correspondientes a políticas impropias (políticas que nunca alcanzan el objetivo), mientras que la posterior exacta no lo hace.

2.4. Muestreo Posterior para la Exploración

El marco utiliza el Muestreo de Thompson (muestreo posterior) para la exploración. En cada episodio, se muestrea una política de la distribución posterior de $Q_\theta$ (ya sea muestreando $\theta$ directamente o computando la masa de probabilidad sobre las políticas) y se despliega hasta alcanzar el objetivo o detectar un bucle impropio.

3. Principales Contribuciones

Formulación Bayesiana Rigurosa: El artículo proporciona una formulación bayesiana de primeros principios para los SSP que deriva la verosimilitud directamente de las Ecuaciones de Optimalidad de Bellman, evitando las verosimilitudes heurísticas utilizadas frecuentemente en las aproximaciones de TD en RL Bayesiano.
Caracterización de la Variedad: Establece que, para recompensas deterministas, la posterior reside en una variedad de baja dimensión y proporciona la fórmula de densidad explícita con respecto a la medida de Hausdorff (Teorema 2).
Análisis de la Relajación y la Identificabilidad: Los autores demuestran matemáticamente que relajar la verosimilitud mediante un núcleo Gaussiano (para permitir la densidad de Lebesgue) crea un problema específico de identificabilidad: la posterior puede verse dominada por políticas impropias si la varianza de la previa es grande, mientras que la posterior exacta excluye correctamente las políticas impropias.
Derivación de la Posterior Tabular: Para parametrizaciones tabulares con prioris Gaussianas y verosimilitudes relajadas, se muestra que la posterior es una mezcla de Gaussianas truncadas (Proposición 1).
Evaluación Comparativa y Validación Empírica: El artículo introduce un protocolo de evaluación utilizando las variantes del entorno "Deep Sea" para comparar su método con enfoques Bayesianos basados en TD (Bayes-TD, Bayes-TD-En, Bayes-TD-Max).

4. Resultados

4.1. Hallazgos Teóricos

Convergencia: A medida que la tolerancia de relajación $\epsilon \to 0$ , la posterior aproximada converge a la posterior de la variedad exacta.
Dominancia de Políticas Impropias: En presencia de políticas impropias, una previa Gaussiana combinada con una verosimilitud relajada puede llevar a una posterior donde la masa se "estira" a lo largo de direcciones correspondientes a políticas impropias, lo que podría sesgar la selección de acciones óptimas. Este efecto se mitiga con $\epsilon$ más pequeños o mediante el uso de prioris que penalicen explícitamente las políticas impropias.

4.2. Experimentos Numéricos

Los experimentos se realizaron en variantes del entorno Deep Sea (entornos estándar, pirámide y remolino/swirl):

Eficiencia de Datos: El marco propuesto (Bayes-BR) demostró una eficiencia de datos superior en comparación con los métodos Bayesianos basados en TD, particularmente cuando la tolerancia de relajación $\epsilon$ era pequeña (por ejemplo, 0.01).
Convergencia: La probabilidad posterior de la política óptima convergió rápidamente a 1 en el entorno Deep Sea estándar (8 episodios para profundidad 3).
Múltiples Óptimos: En la variante "Deep Sea Pyramid" con múltiples políticas óptimas, la posterior distribuyó correctamente la masa de manera uniforme entre todas las políticas óptimas.
Políticas Impropias: En la variante "Deep Sea Swirl" (que contiene políticas impropias), el marco recuperó con éxito la clase de política óptima a pesar del riesgo teórico de dominancia de políticas impropias, siempre que $\epsilon$ fuera suficientemente pequeño.
Desafíos de Muestreo: El estudio señaló que el HMC (Hamiltonian Monte Carlo) estándar tuvo dificultades para muestrear eficazmente de la posterior relajada cuando $\epsilon$ era muy pequeño (0.01), resaltando la dificultad de muestrear cerca de la variedad incluso con la relajación.

5. Significado y Reivindicaciones

El artículo afirma que su marco cuantifica fielmente la incertidumbre en el entorno SSP sin depender de las "suposiciones de modelado poco realistas" o "aproximaciones ad-hoc" que se encuentran en muchos trabajos de RL Bayesiano existentes (que a menudo derivan de las actualizaciones de Q-learning).

Fidelidad: Al derivar la verosimilitud de las BOEs, la posterior resultante está teóricamente fundamentada en las condiciones de optimalidad del MDP.
Perspectiva sobre las Aproximaciones: El trabajo proporciona un análisis matemático crítico del paso de "relajación" utilizado a menudo en la práctica. Revela que, si bien la relajación permite una inferencia tratable, altera fundamentalmente la geometría de la posterior, pudiendo llevar a la selección de políticas impropias si no se gestiona cuidadosamente.
Evaluación Comparativa: Los autores proporcionan un nuevo estándar para comparar métodos de RL Bayesiano, mostrando que su enfoque es más eficiente en términos de datos que las metodologías competitivas basadas en TD en el contexto de SSP.

El artículo concluye de manera modesta, reconociendo que, aunque el marco es robusto, es necesario realizar trabajos futuros para diseñar prioris que excluyan explícitamente las políticas impropias y para desarrollar métodos de muestreo más sofisticados que puedan manejar los desafíos de los valores de $\epsilon$ pequeños.