Monotone Multiple Stopping and Last-Success Problems
Abstract
An optimal stopping problem is monotone when its stopping region is preserved under subsequent transitions, so that the one-step look-ahead stopping time is optimal. We develop a finite-horizon discrete-time theory of multiple stopping that separates general recursive dynamic programming from this stronger monotone structure. Extending the classical martingale-system approach, we construct a recursively defined optimal vector of stopping times without assuming monotonicity. If monotonicity holds at every exercise level, this vector coincides with the recursive vector of one-step look-ahead stopping times. A bounded counterexample shows that monotonicity of the original single-stopping problem alone is insufficient, whereas monotonicity propagates to every level when the level-one one-step look-ahead function is deterministic. We apply the theory to multiple-selection last-success problems. For the classical independent odds setting, a continuous-time Poisson embedding gives an alternative proof of the multiple-stopping lower bound and clarifies the associated threshold constants. We also examine random horizons, Markov-dependent trials, and an unknown success probability
Related
- Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities
- On optimal stopping problems with full information and rank-dependent reward
- Early stopping of stochastic variance reduced gradient for linear inverse problems by the discrepancy principle
- Local W2,1p convergence of penalization for time-inconsistent stopping problems
- Single-call Polyak-Type Extragradient Methods for Monotone Root-Finding Problems
BibTeX
@misc{ano2026monotone,
title = {{Monotone Multiple Stopping and Last-Success Problems}},
author = {Katsunori Ano},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.10237},
eprint = {2610.10237},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.10237},
}
RIS
TY - UNPB
TI - Monotone Multiple Stopping and Last-Success Problems
AU - Katsunori Ano
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.10237
UR - https://arxiv.org/abs/2610.10237
AB - An optimal stopping problem is monotone when its stopping region is preserved under subsequent transitions, so that the one-step look-ahead stopping time is optimal. We develop a finite-horizon discrete-time theory of multiple stopping that separates general recursive dynamic programming from this stronger monotone structure. Extending the classical martingale-system approach, we construct a recursively defined optimal vector of stopping times without assuming monotonicity. If monotonicity holds at every exercise level, this vector coincides with the recursive vector of one-step look-ahead stopping times. A bounded counterexample shows that monotonicity of the original single-stopping problem alone is insufficient, whereas monotonicity propagates to every level when the level-one one-step look-ahead function is deterministic. We apply the theory to multiple-selection last-success problems. For the classical independent odds setting, a continuous-time Poisson embedding gives an alternative proof of the multiple-stopping lower bound and clarifies the associated threshold constants. We also examine random horizons, Markov-dependent trials, and an unknown success probability
ER -