Near-Optimal Regret Bounds for Monotone Stochastic Optimization under Semi-Bandit Feedback
Abstract
Stochastic optimization models sequential decision-making under uncertainty, typically assuming known input distributions. When these distributions are unknown, \citet{agarwal2026semibandit} give an online-to-offline reduction for monotone stochastic optimization under semi-bandit feedback, where only probed variables are observed. Its expected regret relative to the offline guarantee is Õ(n√T), where n is the number of variables and T the horizon. For optimal stopping and Pandora's box, \citet{liu2025improved} achieve Õ(√(nT)) using problem-specific algorithms. \emph{Can a general online-to-offline reduction achieve this improved rate?} We give such a reduction for strongly monotone stochastic optimization, answering the corresponding open question. Strong monotonicity is defined relative to the chosen offline algorithm. Our oracle-efficient reduction achieves Õ(√(nT)) expected regret while preserving approximation guarantees for oracles satisfying the same condition. It combines Bernstein-type optimistic distribution estimates with a Hellinger stability bound for adaptive policy transcripts, aggregating squared marginal errors weighted by the executed policy's probing probabilities. The rate is optimal up to logarithmic factors for T≥ n, even under full feedback. Under monotonicity and uniformly bounded coordinate-wise variation, the same algorithm achieves Õ(n3/4√T) expected approximation regret, improving the previous linear dependence on n. The exponent 3/4 is sharp for its ordinary regret over instances and exact oracle choices. Our framework applies to prophet inequality, Pandora's box, best-of-K selection, stochastic knapsack, stochastic orienteering, and stochastic submodular maximization.
Related
- Near-Optimal First-Order Regret for Bandits with Feedback Graphs
- Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization
- Dual-Anchor Acceleration Is Near-Optimal for Stochastic Monotone Root-Finding
- Non-monotone direct-search methods for deterministic and stochastic derivative-free optimization
- Online Feedback Optimization for Constrained Stochastic Problems with Decision-Dependent Distributions
BibTeX
@misc{hu2026nearoptimal,
title = {{Near-Optimal Regret Bounds for Monotone Stochastic Optimization under Semi-Bandit Feedback}},
author = {Tao Hu and Rohan Ghuge},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.17320},
eprint = {2610.17320},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.17320},
}
RIS
TY - UNPB
TI - Near-Optimal Regret Bounds for Monotone Stochastic Optimization under Semi-Bandit Feedback
AU - Tao Hu
AU - Rohan Ghuge
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.17320
UR - https://arxiv.org/abs/2610.17320
AB - Stochastic optimization models sequential decision-making under uncertainty, typically assuming known input distributions. When these distributions are unknown, \citet{agarwal2026semibandit} give an online-to-offline reduction for monotone stochastic optimization under semi-bandit feedback, where only probed variables are observed. Its expected regret relative to the offline guarantee is Õ(n√T), where n is the number of variables and T the horizon. For optimal stopping and Pandora's box, \citet{liu2025improved} achieve Õ(√(nT)) using problem-specific algorithms. \emph{Can a general online-to-offline reduction achieve this improved rate?} We give such a reduction for strongly monotone stochastic optimization, answering the corresponding open question. Strong monotonicity is defined relative to the chosen offline algorithm. Our oracle-efficient reduction achieves Õ(√(nT)) expected regret while preserving approximation guarantees for oracles satisfying the same condition. It combines Bernstein-type optimistic distribution estimates with a Hellinger stability bound for adaptive policy transcripts, aggregating squared marginal errors weighted by the executed policy's probing probabilities. The rate is optimal up to logarithmic factors for T≥ n, even under full feedback. Under monotonicity and uniformly bounded coordinate-wise variation, the same algorithm achieves Õ(n^3/4√T) expected approximation regret, improving the previous linear dependence on n. The exponent 3/4 is sharp for its ordinary regret over instances and exact oracle choices. Our framework applies to prophet inequality, Pandora's box, best-of-K selection, stochastic knapsack, stochastic orienteering, and stochastic submodular maximization.
ER -