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

Dec 24, 2023

Semi-Bandit Learning for Monotone Stochastic Optimization

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.

Arpit Agarwal, Rohan Ghuge, Viswanath Nagarajan +1

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

Ask PDF

Oct 17, 2026

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

We consider the task of learning an (approximately) optimal policy for stochastic optimization problems where the true distributions are unknown. In each period, the algorithm plays a policy for the stochastic problem and observes semi-bandit feedback, i.e., it only receives new samples from the random variables that were selected by the policy. We obtain an algorithm that works for a large class of

monotone'' stochastic problems, including prophet inequality, Pandora's box, series testing, stochastic knapsack and stochastic matching. We obtain $\tilde{O}(\sqrt{nkT})$ regret for

weakly'' monotone problems and

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

regret for

strongly'' monotone problems, where $T$ is the number of periods, $n$ is the problem dimension (number of random variables) and $k$ is the maximum support size of any random variable. This improves over previous regret bounds by a $\sqrt{n}$ factor. In fact, our dependence on $n$ and $T$ is the best-possible due the $Ω(\sqrt{nT})$ lower bound for multi-armed-bandits. Our main technique is the use of Hellinger distance in bounding the

error'' between the true and learned distributions, and the use of a constant-factor chain rule for the Hellinger distance of dependent random variables.

Zhengjia Zhuo, Viswanath Nagarajan

Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, USA.

Stochastic Optimization Combinatorial Semi-Bandits

Ask PDF

Jun 6, 2026

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

We study high-probability regret bounds for online convex optimization (OCO) with strongly convex losses and establish three results that resolve open questions at the intersection of noise adaptivity, feedback structure, and constraint satisfaction. For the full-information setting with sub-Gaussian stochastic gradients, we prove a noise-adaptive high-probability regret bound in which the martingale deviation term scales with the noise level

σ

rather than the gradient bound

G

, yielding a multiplicative improvement of

G/σ

over the classical Azuma-Hoeffding baseline. Our analysis introduces an exponential supermartingale argument that bypasses the bounded-difference requirement of Freedman's inequality, enabling direct treatment of unbounded sub-Gaussian noise without truncation artifacts. For bandit feedback, we prove a minimax lower bound: the high-probability regret scales linearly in

\log(1/δ)

, in contrast to the

\sqrt{\log(1/δ)}

confidence cost under full information. This constitutes a formal separation in the confidence cost of strongly convex OCO across feedback models. Regarding constrained OCO with stochastic constraints satisfying a Slater condition, we provide simultaneous high-probability guarantees for both cumulative regret and long-run constraint violation, achieving

\mathcal{O}(\sqrt{T\log(m/δ)})

regret and

\mathcal{O}(\sqrt{T}/(ζδ) + m\sqrt{T\log(m/δ)})

violation. Synthetic experiments corroborate all theoretical predictions.

Wentao Zhang, Yutong Zhang, Wentao Mo

Tsinghua Shenzhen International Graduate School, Tsinghua University, China · College of Mathematics, Sichuan University, China

Online Convex Optimization Bandit Convex Optimization Adaptive Learning

Ask PDF

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