Occupation-Weighted Performance Bounds for Rollout Policies in Stochastic Shortest Path Problems
Abstract
We study rollout policies constructed from an approximate value function for stochastic shortest path problems with an absorbing terminal state. Our main bound weights how much the selected action exceeds the optimal one-step value by expected state visits before termination; the uniform hitting-time estimate follows as a corollary. The bound separates value-approximation and numerical-optimization errors from the error caused by replacing an expectation with a nominal disturbance, and uses approximation errors only at states that can occur after one transition from states visited by the implemented policy. A positive lower bound on nonterminal stage costs also gives conditions under which the generated policy reaches the terminal state almost surely with finite expected total cost. In the minimum expected hitting-time problem, a uniform value-approximation error smaller than one half guarantees almost-sure termination, finite expected cost, and a multiplicative hitting-time bound, and the value one half cannot be increased. A deterministic construction shows that the factor two in the uniform rollout bound is asymptotically sharp. Certainty-equivalent rollout is covered by the same analysis.
Related
- Functional limit theorems for weighted occupation times of supercritical superprocesses
- Continuous-Time Reinforcement Learning for N-Player Stochastic Differential Games with Exploratory Policies
- Optimal long-run control of endemic infections: bang-bang threshold policies in a stochastic SIS model
- A 5/3 Guarantee for Echelon Stock (R,nQ) Policies in Two-Stage Stochastic Serial Systems
- Weighted selection from elliptical distributions: a stochastic representation and an application to portfolio separation
BibTeX
@misc{hansson2026occupationweighted,
title = {{Occupation-Weighted Performance Bounds for Rollout Policies in Stochastic Shortest Path Problems}},
author = {Anders Hansson and Bo Wahlberg},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2605.22965},
eprint = {2605.22965},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.22965},
}
RIS
TY - UNPB
TI - Occupation-Weighted Performance Bounds for Rollout Policies in Stochastic Shortest Path Problems
AU - Anders Hansson
AU - Bo Wahlberg
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2605.22965
UR - https://arxiv.org/abs/2605.22965
AB - We study rollout policies constructed from an approximate value function for stochastic shortest path problems with an absorbing terminal state. Our main bound weights how much the selected action exceeds the optimal one-step value by expected state visits before termination; the uniform hitting-time estimate follows as a corollary. The bound separates value-approximation and numerical-optimization errors from the error caused by replacing an expectation with a nominal disturbance, and uses approximation errors only at states that can occur after one transition from states visited by the implemented policy. A positive lower bound on nonterminal stage costs also gives conditions under which the generated policy reaches the terminal state almost surely with finite expected total cost. In the minimum expected hitting-time problem, a uniform value-approximation error smaller than one half guarantees almost-sure termination, finite expected cost, and a multiplicative hitting-time bound, and the value one half cannot be increased. A deterministic construction shows that the factor two in the uniform rollout bound is asymptotically sharp. Certainty-equivalent rollout is covered by the same analysis.
ER -