New Bayesian method boosts data efficiency in stochastic shortest path problems

Researchers from the University of Cambridge and University of Sydney have published a 50-page paper introducing a principled Bayesian learning framework for the stochastic shortest path (SSP) problem, a classic infinite-horizon undiscounted Markov decision process (MDP) with absorbing states. The key innovation is directly constructing posterior beliefs for the optimal action-value function Q* by embedding Bellman's optimality equations into the likelihood, avoiding the unrealistic modeling assumptions and ad-hoc approximations that plague many existing Bayesian MDP methods.

For deterministic rewards, the exact posterior has a manifold density, which the team pragmaticly relaxes to a measurable Lebesgue density for tractable inference—though this introduces unidentifiability, biasing the relaxed posterior toward improper decision rules. The authors then derive exact posterior probabilities for optimal action selection in the tabular Q* parametrization, using a Gaussian likelihood relaxation and Gaussian prior. Numerical experiments on the Deep Sea benchmark show their framework faithfully quantifies uncertainty and is significantly more data-efficient than competing temporal-difference-based Bayesian approaches. The paper concludes with recommendations for future work, including extensions to continuous state-action spaces.