Beyond Monotonicity: Stochastic Online Optimization under Semi-Bandit Feedback

Tsubasa Harada; Yasushi Kawase; Hanna Sumita

cs.LGNov 2, 2026

Beyond Monotonicity: Stochastic Online Optimization under Semi-Bandit Feedback

Authors: Tsubasa Harada, Yasushi Kawase, Hanna Sumita

Organizations: Institute of Science Tokyo · Chuo University

Abstract

We study stochastic online optimization (SOO) under semi-bandit feedback: in each of $T$ rounds, a policy adaptively observes $n$ independent random variables with unknown distributions, learning only from observed values. First-order stochastic dominance (FSD) monotonicity enables general reductions for learning SOO, but can fail when observations change future feasibility, resource use, or reference points. Our algorithm runs the dynamic program for the optimal policy, replacing each expectation by its most optimistic value over a confidence set of distributions. Its regret depends on the level-set complexity $s_i$ of the computed values as functions of the $i$ th variable: the number of intervals needed to describe their superlevel sets. For rewards in $[0,1]$ , the regret is $\tilde{O}(\sqrt{ST})$ without this monotonicity, where $S=\sum_{i=1}^n\min\{s_i,k_i\}$ and $k_i$ is the support size of the $i$ th distribution, which may be infinite when $s_i$ is finite. For constant level-set complexities, regret is $\tilde{O}(\sqrt{nT})$ , even for continuous distributions. The algorithm requires no knowledge of $s_i$ , $k_i$ , or the supports, and it also achieves regret $\tilde{O}(\sqrt{nkT})$ for supports of size at most $k$ without any level-set condition, which improves the previous bound $\tilde{O}(n(\sqrt{kT}+k))$ for FSD-monotone problems. We also prove a lower bound of $Ω(\min\{T,\sqrt{ST}\})$ for all positive integers $s_1,\ldots,s_n$ with $k_i=2s_i+1$ , which holds even under full feedback and matches the upper bound up to logarithmic factors. We obtain $\tilde{O}(\sqrt{nT})$ regret for these problems, all nonmonotone under FSD: stochastic Boolean function evaluation, the full-information secretary problem, optimal stopping with loss aversion, scheduling with deadlines and correlated stochastic knapsack with unimodal rewards, and overbooking with group reservations.

Figures & tables

Result	Condition	Supports	Regret
[ 15 ]	FSD monotonicity	known $k$ points	$\widetilde{O}\big(n(\sqrt{kT}+k)\big)$
[ 17 , 15 ]	none	known $k$ points	$\widetilde{O}\big((nkT)^{2/3}\big)$
[ 15 ]	FSD monotonicity	2 points	$\Omega(\sqrt{nT})$
Theorem 3.2	level-set complexity $s_{i}$	arbitrary	$\widetilde{O}(\sqrt{ST})$
Theorem 3.2	realization monotonicity	arbitrary	$\widetilde{O}(\sqrt{nT})$
Corollary 3.3	none	unknown $k$ points	$\widetilde{O}(\sqrt{nkT})$

Table 1: Regret bounds for learning SOO under semi-bandit feedback with rewards in

[0,1]

. Here,

k_{i}

is the support size of

D_{i}

k=\max_{i}k_{i}

, and

S=\sum_{i}\min\{s_{i},k_{i}\}

. We assume

T\geq S

Panel of Figure 1 — Figure 1: SBFE (Section 4.1 ) for the majority function of three variables, $F(x)=\mathbf{1}\{x_{1}+x_{2}+x_{3}\geq 2\}$ , with unit testing costs. Here, $\mathrm{obs}(r)=\emptyset$ , $\mathrm{obs}(u_{i})=\{i\}$ , and $\mathrm{obs}(u_{ij})=\{i,j\}$ . At $u_{ij}$ , the dashed stopping edge is feasible if $x_{i}=x_{j}$ , and the solid edge revealing the remaining coordinate is feasible if $x_{i}\neq x_{j}$ . Each leaf shows its reward, 1 minus the number of tests divided by 3.

Problem	Why FSD monotonicity fails	$s_{i}$	Reference	Regret
SBFE	balanced outcomes need the most tests	1	Prop. 3.5	$\sqrt{nT\,C^{}(\Gamma-C^{})}+\Gamma n$
Secretary	larger later values favor waiting	2	Prop. 3.5	$\sqrt{nT\,p^{}(1-p^{})}+n$
Loss aversion	early values raise the reference point	2	Prop. 3.5	$\sqrt{nT\,(U^{}+\lambda)(1-U^{})}+\Gamma n$
Scheduling	longer jobs delay later jobs	1	Prop. 3.8	$\sqrt{nT\,\Gamma\mathrm{OPT}^{*}}+\Gamma n$
Overbooking	arrivals save refunds but cause overflow	1	Prop. 3.8	$\sqrt{nT\,\Gamma(W^{*}+C)}+\Gamma n$

Table 2: Applications in Section 4 , with regret in the original objective up to logarithmic factors. Here,

\Gamma

is the normalizing constant,

C^{*}

p^{*}

U^{*}

\mathrm{OPT}^{*}

, and

W^{*}

are the optimal values,

C

is the largest overflow cost, and the scheduling reward functions

r_{i}

are unimodal. For scheduling and overbooking,

s_{i}

is the parameter of Theorem 3.7 .

Stochastic Optimization

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

See all 218 papers

Near-Optimal Regret Bounds for Monotone Stochastic Optimization under Semi-Bandit Feedback
Oct 12, 2026Tao Hu, Rohan GhugeStochastic Optimization Monotonicity Constraints
Department of Information, Risk, and Operations Management, University of Texas at Austin, Austin, USA.
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.

Oct 12, 2026J/K move · Enter open · S save

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

Tao Hu, Rohan Ghuge

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

Stochastic Optimization Monotonicity Constraints

Open paper AskPDF arXiv

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.

Abstract

Stochastic Optimization

Explore similar work

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

Semi-Bandit Learning for Monotone Stochastic Optimization

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