Bayesian learning for the stochastic shortest path problem

A new Bayesian framework directly learns optimal strategies for stochastic shortest path problems, an infinite-horizon Markov decision process with terminal states, by constructing posterior beliefs for the action-value function through Bellman’s optimality equations [1]. The framework, detailed in a paper submitted on 3 June 2026, targets the stochastic shortest path (SSP) problem, which models sequential decision-making tasks where an agent must reach an absorbing goal state without a discount factor [1][2]. Unlike many existing Bayesian approaches that rely on simplifying assumptions, this method directly constructs posterior beliefs for the optimal action-value function Q* [1]. The authors characterize the posterior as a distribution with a manifold density when rewards are deterministic [2]. To enable simpler inference, they relax the likelihood so a Lebesgue density exists, though this introduces unidentifiability issues where the relaxed posterior can assign significant mass to improper decision rules [2][3]. The SSP formulation is more general than the usual discounted infinite-horizon MDP because the absence of a discount factor requires an absorbing terminal state for the objective to be well-defined [3]. The research focuses on finite state and action spaces, which can present high-dimensional learning challenges [3]. The optimal action-value function Q* uniquely satisfies the Bellman optimality equations and characterizes the expected cumulative rewards under the optimal policy [3]. For benchmarking, the authors calculate exact posterior probabilities for optimal action selections using a tabular parametrization of Q*, a Gaussian likelihood relaxation, and a Gaussian prior [1][2]. Numerical studies on variants of the Deep Sea benchmark verified the framework’s ability to quantify uncertainty [1]. The approach demonstrated greater data efficiency compared to other temporal-difference-based Bayesian methodologies [1][2]. Posterior sampling has been applied to SSP problems in prior work. A 2023 study proposed PSRL-SSP, a posterior sampling-based reinforcement learning algorithm that operates in epochs and draws samples from the posterior distribution on unknown model dynamics [4][5]. That algorithm established a Bayesian regret bound of Õ(B∗S√AK), where B∗ bounds the expected cost of the optimal policy, S is the state-space size, A is the action-space size, and K is the number of episodes [4][5]. The new Bayesian framework differs by learning Q* directly rather than sampling model dynamics, and the authors conclude with recommendations for future work [1][2].