# Bayesian learning for the stochastic shortest path problem

arXiv: https://arxiv.org/abs/2606.04845 · HTML: https://mlsanity.com/paper/2606.04845/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 58 references that are in the map.
- First posted on arXiv 3 Jun 2026.

## Builds on (most cited first, 24 of 24)

- [Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning](https://mlsanity.com/paper/1506.02142/) (2015)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Reinforcement learning](https://mlsanity.com/paper/2405.10369/) (2024)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Randomized Prior Functions for Deep Reinforcement Learning](https://mlsanity.com/paper/1806.03335/) (2018)
- [A Theoretical Analysis of Deep Q-Learning](https://mlsanity.com/paper/1901.00137/) (2019)
- [Deep Exploration via Randomized Value Functions](https://mlsanity.com/paper/1703.07608/) (2017)
- [Behaviour Suite for Reinforcement Learning](https://mlsanity.com/paper/1908.03568/) (2019)
- [Why is Posterior Sampling Better than Optimism for Reinforcement Learning?](https://mlsanity.com/paper/1607.00215/) (2016)
- [Efficient Exploration through Bayesian Deep Q-Networks](https://mlsanity.com/paper/1802.04412/) (2018)
- [Learning Unknown Markov Decision Processes: A Thompson Sampling Approach](https://mlsanity.com/paper/1709.04570/) (2017)
- [Worst-Case Regret Bounds for Exploration via Randomized Value Functions](https://mlsanity.com/paper/1906.02870/) (2019)
- [An Information-Theoretic Analysis for Thompson Sampling with Many Actions](https://mlsanity.com/paper/1805.11845/) (2018)
- [A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learning](https://mlsanity.com/paper/2208.10904/) (2022)
- [Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo](https://mlsanity.com/paper/2305.18246/) (2023)
- [Bayesian Bellman Operators](https://mlsanity.com/paper/2106.05012/) (2021)
- [TD Convergence: An Optimization Perspective](https://mlsanity.com/paper/2306.17750/) (2023)
- [Kalman Temporal Differences](https://mlsanity.com/paper/1406.3270/) (2014)
- [The Stochastic Shortest Path Problem : A polyhedral combinatorics perspective](https://mlsanity.com/paper/1702.03186/) (2017)
- [Manifold Markov chain Monte Carlo methods for Bayesian inference in diffusion models](https://mlsanity.com/paper/1912.02982/) (2019)
- [Trace-class Gaussian priors for Bayesian learning of neural networks with MCMC](https://mlsanity.com/paper/2012.10943/) (2020)
- [Bayesian Learning of Optimal Policies in Markov Decision Processes with Countably Infinite State-Space](https://mlsanity.com/paper/2306.02574/) (2023)

## Abstract (arXiv)

Sequential decision-making problems are often modelled as a Markov decision process (MDP). We focus on the stochastic shortest path (SSP) problem, which is an infinite-horizon undiscounted MDP with absorbing terminal states. We develop a Bayesian framework to learn the optimal decision strategy through interactions with the decision-making task. Specifically, we learn the optimal action-value function Q^*, but unlike many existing Bayesian approaches, we do not rely on unrealistic modelling assumptions and ad-hoc approximations. Our approach is to directly construct the posterior beliefs for Q^* through Bellman's optimality equations. For deterministic rewards, we characterise the posterior as a distribution with a manifold density. To facilitate simpler inference, we relax the likelihood so that a Lebesgue density exists. The flip side is to create unidentifiability issues. Specifically, the relaxed posterior can have significant mass on improper decision rules, while the exact posterior will not. We also calculate the exact posterior probabilities for optimal action selections for the tabular parametrisation of Q^*, a Gaussian likelihood relaxation and a Gaussian prior, which is useful in benchmarking studies. Numerical studies on variants of the Deep Sea benchmark verify our findings. We demonstrate that our framework faithfully quantifies uncertainty and, compared to other temporal-difference-based Bayesian methodologies, is more data efficient. We conclude with recommendations for future work.