📊 statistics

Bayesian learning for the stochastic shortest path problem

This paper proposes a Bayesian framework for the stochastic shortest path problem that directly constructs posterior beliefs for the optimal action-value function via Bellman's optimality equations, offering a more data-efficient and uncertainty-aware alternative to existing temporal-difference-based methods while addressing challenges related to likelihood relaxation and unidentifiability.

Original authors: Chon Wai Ho, Sumeetpal S. Singh, Jiaqi Guo

Published 2026-06-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Chon Wai Ho, Sumeetpal S. Singh, Jiaqi Guo

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the quickest, safest path through a massive, foggy maze to reach a treasure chest at the end. This is the Stochastic Shortest Path (SSP) problem. You don't have a map. Every time you take a step (an action), you might get a reward (like finding a clue) or a penalty (like hitting a dead end), and you end up in a new spot (a state). Your goal is to learn the best route by trial and error, but you want to do it efficiently so you don't waste time wandering aimlessly.

This paper proposes a new, smarter way to learn that route using Bayesian Learning. Think of this as a "learning by belief" system. Instead of just guessing the best path, the computer maintains a "cloud of possibilities" (a probability distribution) about what the best path looks like. As it gathers more data, this cloud shrinks and tightens around the true best path.

Here is a breakdown of their approach using simple analogies:

1. The Core Idea: Learning the "Scorecard"

In standard learning, computers often try to guess the score of a move directly. This paper says, "Let's guess the Scorecard (called $Q^*$ ) instead."

The Scorecard: Imagine a giant spreadsheet where every possible move in every possible room has a score. This score represents the total treasure you'd get if you started there and played perfectly from then on.
The Rulebook (Bellman Equations): There is a strict mathematical rule (the Bellman Optimality Equation) that says: "The score of a move must equal the immediate reward plus the best possible score of the next move."
The Innovation: Most existing methods try to force their guesses to fit this rulebook by tweaking numbers in a messy, ad-hoc way. This paper says, "Let's build our entire learning system directly on top of this rulebook." They treat the rulebook as a law of physics that the data must obey.

2. The "Manifold" vs. The "Fuzzy Cloud"

This is the most technical but also the most interesting part of the paper.

The Perfect World (The Manifold): If the rewards in the maze are perfectly clear (no noise), the computer's belief about the Scorecard doesn't float around in 3D space. Instead, it collapses onto a thin, flat sheet (a manifold) inside that space.
- Analogy: Imagine trying to find a specific line drawn on a piece of paper. If you have perfect information, you know the answer is exactly on that line. You don't need to look at the whole paper; you just need to look at the line. Mathematically, this is hard to calculate because you are trying to sample from a "line" inside a "room."
The Real World (The Fuzzy Cloud): To make the math easier, the authors "fuzz up" the rules slightly. They say, "Okay, the answer doesn't have to be exactly on the line; it can be within a tiny distance of the line."
- Analogy: Instead of looking for a needle in a haystack, we are looking for a needle inside a small, fuzzy cloud of hay. This makes it much easier for the computer to sample answers (using a method called Monte Carlo sampling).

3. The Trap: "Improper" Paths

The paper discovers a tricky side effect of making the rules "fuzzy."

The Problem: In a maze, some paths lead you in circles forever, never reaching the treasure. These are called improper policies.
The Trap: When the authors relaxed the rules to make the math easier, they accidentally made it very easy for the computer to believe in these "infinite loop" paths.
- Analogy: Imagine you are teaching a robot to walk to a door. If you are too loose with your instructions, the robot might think, "Oh, I can just walk in circles in the hallway forever; that's a valid plan!" The math shows that if the computer isn't careful, it might assign a huge amount of "belief" to these useless, infinite loops, even when it has seen the whole maze.
The Fix: The paper warns that you have to be very careful with how "fuzzy" you make the rules. If you make it too fuzzy, the robot gets confused by the infinite loops. If you make it too sharp, the math becomes impossible to solve.

4. The Results: Better than the Competition

The authors tested their method on a famous benchmark called "Deep Sea" (a digital maze where you have to choose left or right at every step to find a treasure).

Data Efficiency: Their method learned the correct path much faster than other popular Bayesian methods. It needed fewer tries to figure out the map.
Accuracy: When they looked at the "cloud of beliefs," their method correctly identified the best path and ignored the bad ones. Other methods sometimes got stuck believing in the "infinite loop" paths or took much longer to converge.
The "Gold Standard": They even calculated the exact answer (without the fuzzy approximation) for smaller problems to prove that their fuzzy method was a good approximation.

Summary

The paper presents a new way for computers to learn the best path through a complex, uncertain world.

It builds directly on the mathematical laws of how rewards work, rather than using shortcuts.
It acknowledges that perfect knowledge creates a "thin line" of possibilities, which is hard to compute, so it uses a "fuzzy cloud" to make it manageable.
It warns that this "fuzziness" can trick the computer into thinking useless, infinite loops are good plans, so the "fuzz" must be tuned carefully.
In tests, this method learned faster and more accurately than other current methods, proving that sticking closer to the fundamental math pays off.

The authors conclude that while their method is powerful, future work needs to find better ways to teach the computer to ignore those "infinite loop" traps without having to rely on such careful tuning.

Technical Summary: Bayesian Learning for the Stochastic Shortest Path Problem

1. Problem Formulation

The paper addresses the Stochastic Shortest Path (SSP) problem, defined as an infinite-horizon, undiscounted Markov Decision Process (MDP) with an absorbing terminal state. Unlike standard discounted MDPs, the SSP formulation ( $\gamma = 1$ ) requires the existence of a unique, zero-reward absorbing goal state ( $s_g$ ) and the existence of at least one "proper" policy (a policy that reaches $s_g$ with probability 1 from any state).

The primary objective is to learn the optimal action-value function, $Q^*$ , which satisfies the Bellman Optimality Equations (BOEs). The challenge lies in the fact that $Q^*$ is not directly observed; only state-action-reward triplets $(s, a, r)$ are observed through interaction. The authors aim to construct a Bayesian framework to quantify uncertainty over $Q^*$ and facilitate exploration-exploitation trade-offs via Thompson Sampling (posterior sampling), without relying on the unrealistic assumptions or ad-hoc approximations common in existing Bayesian Reinforcement Learning (RL) literature.

2. Methodology

2.1. Likelihood Construction via Bellman Equations

The core methodological contribution is the direct construction of the likelihood function based on the BOEs rather than stochastic approximation algorithms (like Q-learning) or temporal difference (TD) errors.

Parametrization: The optimal value function is approximated by a parametric function $Q_\theta$ .
Constraint: For a state-action pair $(s, a)$ , the expected reward $\bar{r}_{s,a}$ must satisfy the BOE: $\bar{r}_{s,a} = Q_\theta(s, a) - \mathbb{E}[\max_{a'} Q_\theta(S', a')]$ .
Likelihood: The authors define a likelihood function $p(r_t | \theta, \psi, s_t, a_t)$ where the observed reward $r_t$ is modeled as the deterministic expected reward plus noise. This constrains the parameters $\theta$ to be consistent with the observed BOEs.

2.2. Handling Deterministic Rewards and Manifold Posteriors

A significant theoretical challenge arises when rewards are deterministic (noiseless). In this case, the BOEs impose strict equality constraints on $\theta$ .

Manifold Density: The posterior distribution of $\theta$ collapses from the full parameter space onto a low-dimensional manifold defined by the intersection of the BOE constraints.
Hausdorff Measure: The authors characterize this posterior using a density with respect to the Hausdorff measure (Theorem 2), rather than a standard Lebesgue density. This provides a rigorous mathematical description of the posterior for noiseless rewards.

2.3. Likelihood Relaxation and Approximation

Sampling directly from a manifold density is computationally intractable for standard Monte Carlo methods. To facilitate inference, the authors propose relaxing the likelihood:

Convolution: The exact likelihood is convolved with a kernel (e.g., Gaussian or uniform) with tolerance $\epsilon$ .
Lebesgue Density: This relaxation "thickens" the manifold, resulting in a posterior with a standard Lebesgue density suitable for MCMC sampling.
Trade-off: The paper rigorously analyzes the consequences of this relaxation. While it enables tractable sampling, it introduces unidentifiability issues. Specifically, for tabular parametrizations, the relaxed likelihood can assign infinite mass to sets of parameters corresponding to improper policies (policies that never reach the goal), whereas the exact posterior does not.

2.4. Posterior Sampling for Exploration

The framework utilizes Thompson Sampling (Posterior Sampling) for exploration. At each episode, a policy is sampled from the posterior distribution of $Q_\theta$ (either by sampling $\theta$ directly or computing the probability mass over policies) and deployed until the goal is reached or an improper loop is detected.

3. Key Contributions

Rigorous Bayesian Formulation: The paper provides a first-principles Bayesian formulation for SSPs that derives the likelihood directly from the Bellman Optimality Equations, avoiding the heuristic likelihoods often used in TD-based Bayesian RL.
Manifold Characterization: It establishes that for deterministic rewards, the posterior lies on a low-dimensional manifold and provides the explicit density formula with respect to the Hausdorff measure (Theorem 2).
Analysis of Relaxation and Unidentifiability: The authors mathematically prove that relaxing the likelihood to a Gaussian kernel (to enable Lebesgue density) creates a specific unidentifiability problem: the posterior can become dominated by improper policies if the prior variance is large (Theorem 4). This contrasts with the exact posterior, which correctly excludes improper policies.
Tabular Posterior Derivation: For tabular parametrizations with Gaussian priors and relaxed likelihoods, the posterior is shown to be a mixture of truncated Gaussians (Proposition 1).
Benchmarking and Empirical Validation: The paper introduces a benchmarking protocol using the "Deep Sea" environment variants to compare their method against TD-based Bayesian approaches (Bayes-TD, Bayes-TD-En, Bayes-TD-Max).

4. Results

4.1. Theoretical Findings

Convergence: As the relaxation tolerance $\epsilon \to 0$ , the approximate posterior converges to the exact manifold posterior.
Improper Policy Dominance: In the presence of improper policies, a Gaussian prior combined with a relaxed likelihood can lead to a posterior where the mass is "stretched" along directions corresponding to improper policies, potentially biasing the selection of optimal actions. This effect is mitigated by smaller $\epsilon$ or by using priors that explicitly penalize improper policies.

4.2. Numerical Experiments

Experiments were conducted on variants of the Deep Sea benchmark (standard, pyramid, and swirl environments):

Data Efficiency: The proposed framework (Bayes-BR) demonstrated superior data efficiency compared to TD-based Bayesian methods, particularly when the relaxation tolerance $\epsilon$ was small (e.g., 0.01).
Convergence: The posterior probability of the optimal policy converged rapidly to 1 in the standard Deep Sea environment (8 episodes for depth-3).
Multiple Optima: In the "Deep Sea Pyramid" variant with multiple optimal policies, the posterior correctly distributed mass evenly among all optimal policies.
Improper Policies: In the "Deep Sea Swirl" variant (containing improper policies), the framework successfully recovered the optimal policy class despite the theoretical risk of improper policy dominance, provided $\epsilon$ was sufficiently small.
Sampling Challenges: The study noted that standard Hamiltonian Monte Carlo (HMC) struggled to sample effectively from the relaxed posterior when $\epsilon$ was very small (0.01), highlighting the difficulty of sampling near the manifold even with relaxation.

5. Significance and Claims

The paper claims that its framework faithfully quantifies uncertainty in the SSP setting without relying on the "unrealistic modelling assumptions" or "ad-hoc approximations" found in many existing Bayesian RL works (which often stem from Q-learning updates).

Faithfulness: By deriving the likelihood from the BOEs, the resulting posterior is theoretically grounded in the optimality conditions of the MDP.
Insight into Approximations: The work provides a critical mathematical analysis of the "relaxation" step often used in practice. It reveals that while relaxation enables tractable inference, it fundamentally alters the posterior geometry, potentially leading to the selection of improper policies if not carefully managed.
Benchmarking: The authors provide a new benchmark for comparing Bayesian RL methods, showing that their approach is more data-efficient than competing TD-based Bayesian methodologies in the SSP setting.

The paper concludes modestly, acknowledging that while the framework is robust, future work is needed to design priors that explicitly exclude improper policies and to develop more sophisticated sampling methods to handle the challenges of small $\epsilon$ values.