Performance Bounds for Rollout Policies in Stochastic Shortest Path Problems
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913154216230912 |
|---|---|
| author | Hansson, Anders Wahlberg, Bo |
| author_facet | Hansson, Anders Wahlberg, Bo |
| contents | This paper concerns rollout and certainty-equivalent rollout policies for stochastic shortest path problems with absorbing terminal states. The main result provides a direct non-asymptotic performance certificate for a fixed rollout policy: the loss relative to the optimal value is controlled by the uniform accuracy of the value approximation and by the expected time for which the rollout closed loop remains away from the terminal state. Thus, in the undiscounted transient setting, the expected hitting time plays the role of a discount or finite-horizon parameter in more standard approximate dynamic programming bounds. This paper also gives a performance-difference identity showing that suboptimality is exactly accumulated through the transient occupation measure, and a deterministic sharpness example showing that the hitting-time factor is unavoidable. Finally, consequences under uniform hitting-time and Foster-Lyapunov drift conditions are given, and extend the argument to certainty-equivalent rollout by adding a separate local model-mismatch term. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_22965 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Performance Bounds for Rollout Policies in Stochastic Shortest Path Problems Hansson, Anders Wahlberg, Bo Optimization and Control Systems and Control This paper concerns rollout and certainty-equivalent rollout policies for stochastic shortest path problems with absorbing terminal states. The main result provides a direct non-asymptotic performance certificate for a fixed rollout policy: the loss relative to the optimal value is controlled by the uniform accuracy of the value approximation and by the expected time for which the rollout closed loop remains away from the terminal state. Thus, in the undiscounted transient setting, the expected hitting time plays the role of a discount or finite-horizon parameter in more standard approximate dynamic programming bounds. This paper also gives a performance-difference identity showing that suboptimality is exactly accumulated through the transient occupation measure, and a deterministic sharpness example showing that the hitting-time factor is unavoidable. Finally, consequences under uniform hitting-time and Foster-Lyapunov drift conditions are given, and extend the argument to certainty-equivalent rollout by adding a separate local model-mismatch term. |
| title | Performance Bounds for Rollout Policies in Stochastic Shortest Path Problems |
| topic | Optimization and Control Systems and Control |
| url | https://arxiv.org/abs/2605.22965 |