Bayesian learning for the stochastic shortest path problem

Chon Wai Ho; Sumeetpal S. Singh; Jiaqi Guo

stat.MLJun 3, 2026

Bayesian learning for the stochastic shortest path problem

Authors: Chon Wai Ho, Sumeetpal S. Singh, Jiaqi Guo

Organizations: Department of Engineering, University of Cambridge, UK · School of Mathematics and Physics, University of Wollongong, Wollongong, Australia

Abstract

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.

Explore similar work

Apr 17, 2026cs.LG

Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model

We study the sample complexity of learning an

ε

-optimal policy in the Stochastic Shortest Path (SSP) problem. We first derive sample complexity bounds when the learner has access to a generative model. We show that there exists a worst-case SSP instance with

S

states,

A

actions, minimum cost

c_{\min}

, and maximum expected cost of the optimal policy over all states

B_{\star}

, where any algorithm requires at least

Ω(SAB_{\star}^3/(c_{\min}ε^2))

samples to return an

ε

-optimal policy with high probability. Surprisingly, this implies that whenever

c_{\min} = 0

an SSP problem may not be learnable, thus revealing that learning in SSPs is strictly harder than in the finite-horizon and discounted settings. We complement this lower bound with an algorithm that matches it, up to logarithmic factors, in the general case, and an algorithm that matches it up to logarithmic factors even when

c_{\min} = 0

, but only under the condition that the optimal policy has a bounded hitting time to the goal state.

Jean Tarbouriech, Matteo Pirotta, Michal Valko +1

Optimal Policies Shortest Paths Sample Complexity Generative Models

Ask PDF

May 14, 2024stat.ML

Thompson Sampling for Infinite-Horizon Discounted Decision Processes

This paper develops a framework for learning in discounted infinite-horizon Markov decision processes (MDPs) with Borel state and action spaces, whose rewards and transitions depend on an unknown parameter.To analyze sampling-based adaptive learning algorithms in this setting, we introduce a canonical probability space that explicitly incorporates sampled parameters into the history of the process. As a performance criterion, we adopt the per-period suboptimality gap used in discounted-MDP regret analysis and specialize it to our parametrized Bayesian setting. Since this quantity captures the remaining loss in future performance from the current period onward, we refer to it as residual regret. We use the expected residual regret to connect discounted-MDP regret analysis with asymptotic discount optimality from adaptive control and the temporal-difference error perspective from reinforcement learning. We then focus on Thompson sampling (TS) in discounted infinite-horizon MDPs. Under assumptions that extend those used in prior work on finite state and action spaces to the Borel setting, we show that the expected residual regret for TS converges to zero exponentially fast. We further show that, under mild conditions ensuring the existence of the relevant limits, the ample-path residual regret converges to zero almost surely and TS achieves complete learning.

Daniel Adelman, Cagla Keceli, Alba V. Olivares-Nadal

Thompson Sampling Markov Decision Processes

Ask PDF

Aug 9, 2026cs.LG

Path-dependent Discrete Amortized Inference

We consider the problem of sampling compositional and discrete objects from a given unnormalized posterior distribution. Notably, recent studies have shown that this problem can be efficiently solved by learning a deterministic Markov Decision Process (MDP) that progressively builds each object in proportion to the posterior. In this work, however, we demonstrate that the Markovian assumption can both hamper signal propagation during training and catastrophically reduce the learned sampler's expressivity due to state aliasing. To address these issues, we propose lifting the MDP with a learnable latent dynamical system that allows the underlying policy to depend on the entire past trajectory---and not only on the current state. In view of this, we refer to the resulting method as path-dependent discrete amortized inference. Importantly, we provably extend existing learning algorithms for discrete amortized samplers to our setting. In experiments on standard benchmark problems, we also show that our approach often leads to faster learning convergence and improved state space exploration relatively to prior techniques.

Tiago da Silva, Esmeralda S. Whitammer, Salem Lahlou

Markov Decision Processes Posterior Efficient Exploration

Ask PDF