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

Tao Hu; Rohan Ghuge

cs.LGOct 12, 2026

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

Authors: Tao Hu, Rohan Ghuge

Organizations: Department of Information, Risk, and Operations Management, University of Texas at Austin, Austin, USA.

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 $\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. 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 $T\ge 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.

Figures & tables

N_{i}^{t+1}\leftarrow N_{i}^{t}+\mathbf{1}\{i\in S(\sigma^{t},\bm{x}^{t})\}\qquad\text{for every }i\in[n].

Algorithm 1 The Online Algorithm

Application	Approx.	Our $\alpha$ -Regret	Prior Bound	Our Distributional
	Factor ( $\alpha$ )	$\widetilde{O}(\cdot)$	$\widetilde{O}(\cdot)$	Assumptions
Series Testing	$1$	$C\sqrt{nT}$	$Cn\sqrt{T}$ G	Bernoulli
Best-of- $K$ Selection	$1-\varepsilon$	$\sqrt{nT}$	$\sqrt{nKT}$ C	Arbitrary on $[0,1]$
Single-Choice Prophet Inequality	$1$	$U\sqrt{nT}$	$U\sqrt{nT}$ L	Arbitrary bounded
Multiple-Choice Prophet Inequality	$1$	$kU\sqrt{nT}$	$knU\sqrt{T}$ G	Arbitrary bounded
Pandora’s Box	$1$	$(C+U)\sqrt{nT}$	$U\sqrt{nT}$ L	Arbitrary bounded

Table 1: Summary of expected regret bounds. The Best-of-

K

comparison concerns general marginals; Bernoulli inputs already admit

\widetilde{O}(\sqrt{nT})

regret ( Merlis and Mannor, 2019 ) . Prior knapsack and orienteering bounds assume discrete distributions with at most

k

support values per item. The prior knapsack bounds use an adaptive

(1/2-\varepsilon)

-approximation oracle, whereas our

1/4

-regret guarantee uses a nonadaptive oracle. The prior Pandora bound assumes

c_{i}\leq U

. For stochastic matching,

n=|E|

and

W=\sum_{e\in E}w_{e}

Panel of Figure 1 — Figure 1: Computational results for Bernoulli Best-of- $K$ selection at $n=500$ .

Figure 2: Regret versus

n

for Bernoulli Best-of-

K

selection with

K=n/2

and

T=100{,}000

Panel of Figure 3 — Figure 3: Computational results for prophet inequalities.

Figure 4: Computational results for Uniform/Beta prophet instances with

k=1

Panel of Figure 5 — Figure 5: Computational results for Pandora’s box.

Figure 6: Computational results for Uniform/Beta Pandora instances with

k=5

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 7 — Figure 7: Computational results for Bernoulli Best-of- $K$ selection with $K=n/2$ .

Panel of Figure 8 — Figure 8: Computational results for Bernoulli Best-of- $K$ selection with $K=5$ .

Panel of Figure 9 — Figure 9: Computational results for discrete prophet instances with $k=1$ .

Panel of Figure 10 — Figure 10: Computational results for discrete prophet instances with $k=2$ .

Panel of Figure 11 — Figure 11: Computational results for discrete prophet instances with $k=5$ .

Panel of Figure 12 — Figure 12: Computational results for Uniform-endpoint prophet instances with $k=1$ .

Panel of Figure 13 — Figure 13: Computational results for Uniform-endpoint prophet instances with $k=2$ .

Panel of Figure 14 — Figure 14: Computational results for Uniform-endpoint prophet instances with $k=5$ .

Figure 15: Computational results for Uniform/Beta prophet instances with

k=2

Figure 16: Computational results for Uniform/Beta prophet instances with

k=5

Panel of Figure 17 — Figure 17: Computational results for discrete Pandora instances.

Panel of Figure 18 — Figure 18: Computational results for Uniform-endpoint Pandora instances.

Figure 19: Computational results for Uniform/Beta Pandora instances with

k=1

Figure 20: Computational results for Uniform/Beta Pandora instances with

k=2

Stochastic Optimization

Stochastic optimization studies how to find good decisions or model parameters when objectives, data, or feedback are random or noisy.

See all 206 papers

Semi-Bandit Learning for Monotone Stochastic Optimization
Dec 24, 2023Arpit Agarwal, Rohan Ghuge, Viswanath Nagarajan +1Stochastic Optimization Multi-Armed Bandits
Department of Computer Science & Engineering, Indian Institute of Technology Bombay, Mumbai, India. · Department of Information, Risk, and Operations Management, University of Texas at Austin, Austin, USA. · Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, USA.
Near-Optimal Regret for Semi-Bandit Learning of Monotone Stochastic Problems
Oct 17, 2026Zhengjia Zhuo, Viswanath NagarajanStochastic Optimization Combinatorial Semi-Bandits
Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, USA.
Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization
Jun 6, 2026Wentao Zhang, Yutong Zhang, Wentao MoOnline Convex Optimization Bandit Convex Optimization
Tsinghua Shenzhen International Graduate School, Tsinghua University, China · College of Mathematics, Sichuan University, China

Dec 24, 2023J/K move · Enter open · S save

Semi-Bandit Learning for Monotone Stochastic Optimization

Arpit Agarwal, Rohan Ghuge, Viswanath Nagarajan, Zhengjia Zhuo

Department of Computer Science & Engineering, Indian Institute of Technology Bombay, Mumbai, India. · Department of Information, Risk, and Operations Management, University of Texas at Austin, Austin, USA. · Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, USA.

Stochastic Optimization Multi-Armed Bandits

Open paper AskPDF arXiv

Stochastic optimization is a widely used approach for optimization under uncertainty, where uncertain input parameters are modeled by random variables. Exact or approximation algorithms have been obtained for several fundamental problems in this area. However, a significant limitation of this approach is that it requires full knowledge of the underlying probability distributions. Can we still get good (approximation) algorithms if these distributions are unknown, and the algorithm needs to learn them through repeated interactions? In this paper, we resolve this question for a large class of ''monotone'' stochastic problems, by providing a generic online learning algorithm with

\sqrt{T\log(T)}

regret relative to the best approximation algorithm (under known distributions). Importantly, our online algorithm works in a semi-bandit setting, where in each period, the algorithm only observes samples from the random variables that were actually probed. Moreover, our result extends to settings with censored and binary feedback, where the policy only observes truncated or thresholded versions of the probed variables. Our framework applies to several fundamental problems such as prophet inequality, Pandora's box, stochastic knapsack, single-resource revenue management and sequential posted pricing.

Abstract

Stochastic Optimization

Explore similar work

Semi-Bandit Learning for Monotone Stochastic Optimization

Near-Optimal Regret for Semi-Bandit Learning of Monotone Stochastic Problems

Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization