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

arXiv:2610.17320v1 Announce Type: new Abstract: Stochastic optimization models sequential decision-making under uncertainty, typically assuming known input distributions. When these distributions are unknown, itet{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(nsqrt T), where n is the number of variables and T the horizon. For optimal stopping and Pandora's box, itet{liu2025improved} achieve widetilde O(sqrt{nT}) using problem-specific algorithms. 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 errors weighted by the executed policy's probing probabilities. The rate is optimal up to logarithmic factors for Tge n, even under full feedback. Under monotonicity and uniformly bounded coordinate-wise variation, the same algorithm achieves widetilde O(n^{3/4}sqrt 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.

Source: arXiv cs.LG | 2026-10-14