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

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

Shortest Paths Sample Complexity Generative Models

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 Probabilistic Inference Posterior Stochastic Exploration

Ask PDF

May 5, 2026cs.LG

Optimal Posterior Sampling for Policy Identification in Tabular Markov Decision Processes

We study the

(\varepsilon, δ)

-PAC policy identification problem in finite-horizon episodic Markov Decision Processes. Existing approaches provide finite-time guarantees for approximate settings (

\varepsilon>0

) but suffer from high computational cost, rendering them hard to implement, and also suffer from suboptimal dependence on

\log(1/δ)

. We propose a randomized and computationally efficient algorithm for best policy identification that combines posterior sampling with an online learning algorithm to guide exploration in the MDP. Our method achieves asymptotic optimality in sample complexity, also in terms of posterior contraction rate, and runs in

O(S^2AH)

per episode, matching standard model-based approaches. Unlike prior algorithms such as MOCA and PEDEL, our guarantees remain meaningful in the asymptotic regime and avoid sub-optimal polynomial dependence on

\log(1/δ)

. Our results provide both theoretical insights and practical tools for efficient policy identification in tabular MDPs.

Cyrille Kone, Kevin Jamieson

Finite-Horizon Episodic Markov Decision Processes Optimal Policies Markov Decision Processes Posterior Sampling

Ask PDF