Near-Optimal Regret Bounds for Monotone Stochastic Optimization under Semi-Bandit Feedback

Tao Hu, Rohan Ghuge

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 $\widetilde O(n\sqrt T)$, where $n$ is the number of variables and $T$ the horizon. For optimal stopping and Pandora's box, \citet{liu2025improved} achieve $\widetilde O(\sqrt{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 $\widetilde O(\sqrt{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…