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

Oct 12, 2026

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

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.

Tao Hu, Rohan Ghuge

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

Stochastic Optimization Monotonicity Constraints

Ask PDF

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

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