Metraipolis › archive › dc_7d6e478a3607

Beyond Monotonicity: Stochastic Online Optimization under Semi-Bandit Feedback — arXiv:2611.02739

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.02739
License (as archived)
CC0-1.0
Archived
2026-11-03T11:22:53.765Z
SHA-256 of the archived text
a5cf034039510db44165bac485218ec7f1348e2b1a1f3c58e47c58a67aae43c2
Stable URL of this page
https://metraipolis.com/documento/dc_7d6e478a3607

How to cite

Beyond Monotonicity: Stochastic Online Optimization under Semi-Bandit Feedback — arXiv:2611.02739 — arXiv (en), https://arxiv.org/abs/2611.02739 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7d6e478a3607 (Metraipolis archive dc_7d6e478a3607, sha256 a5cf034039510db44165bac485218ec7f1348e2b1a1f3c58e47c58a67aae43c2)
BibTeX
@misc{dc7d6e478a3607,
  title = {Beyond Monotonicity: Stochastic Online Optimization under Semi-Bandit Feedback — arXiv:2611.02739},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.02739},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7d6e478a3607; sha256 a5cf034039510db44165bac485218ec7f1348e2b1a1f3c58e47c58a67aae43c2},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.02739. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\Omega(\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.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2611.02739 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:02:37.636Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).