m-Set Adversarial Bandits with Winner Feedback

Nicolò Cesa-Bianchi; Matteo Papini

cs.LGOct 7, 2026

m-Set Adversarial Bandits with Winner Feedback

Authors: Nicolò Cesa-Bianchi, Matteo Papini

Organizations: Universit`a degli Studi di Milano · Politecnico di Milano

Abstract

We show upper and lower bounds on the regret of $m$ -set adversarial bandits for different utilities (winner reward or sum of rewards) and feedback models (winner index, winner reward, sum of rewards, and their combinations). By comparing to standard bounds for combinatorial and MNL bandits, our results reveal how subtle changes in the setting can have a dramatic impact on the learning rates. Our main technical contributions are the information-theoretic lower bounds on the regret. Experiments on synthetic data confirm our theoretical analyses.

Figures & tables

Utility	Feedback	Name	Regret	Reference
Sum of
rewards	Sum of
rewards	Full-bandit	$\mathcal{O}\big(m^{3/2}\sqrt{KT\ln\frac{K}{m}}\big)$	Bubeck et al. (2012)
			$\Omega\big(m^{3/2}\sqrt{KT}\big)$	Ito et al. (2019)
\SetRow bg=rowcolor Sum of
rewards	Reward of

Table 1: Old and new results for

m

-set bandits.

Panel of Figure 1 — Figure 1: Results of no-regret algorithms with their respective feedback on the stationary correlated reward instance. On the left (a), total regret per round, averaged over 10 seeds; on the right (b), final total regret after $20k$ rounds for increasing action size $m$ , averaged over 5 seeds; 95% bootstrap confidence intervals are shown.

Figure 2: Results on corrupted rewards. Total regret per round, averaged over 10 seeds, with 95% bootstrap confidence intervals.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 3: Results on stationary correlated rewards. Total regret per round, averaged over 100 independent reward sequences, with 99% bootstrap confidence intervals.

Figure 4: Results on stationary uniform rewards. Total regret per round, averaged over 10 seeds, with 95% bootstrap confidence intervals.

Figure 5: Results on nonstationary rewards. Total dynamic regret per round, averaged over 10 seeds, with 95% bootstrap confidence intervals.

Figure 6: Results on binary rewards. Total regret per round, averaged over 10 seeds, with 95% bootstrap confidence intervals.

Explore similar work

An Efficient Near-Optimal Algorithm for Adversarial $m$ -Set Bandits
Aug 12, 2026Francesco Bacchiocchi, Tommaso Cesari, Roberto ColomboniStochastic Multi-Armed Bandits Bounded Adversary
DEIB, Politecnico di Milano, Milano, Italy · School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, Canada · School of Mathematics, University of Bristol, Bristol, United Kingdom
Multi-Armed Bandits With Best-Action Queries
May 8, 2026Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi +1Stochastic Multi-Armed Bandits \Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret
Politecnico di Milano
Bandits with Probing: Optimal Regret and the Limits of Winner Feedback
Sep 14, 2026Yongjie GuanOptimal Regret Minimax
Zhejiang University of Technology

Aug 12, 2026, cs.LGJ/K move · Enter open · S save

An Efficient Near-Optimal Algorithm for Adversarial $m$ -Set Bandits

Francesco Bacchiocchi, Tommaso Cesari, Roberto Colomboni

DEIB, Politecnico di Milano, Milano, Italy · School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, Canada · School of Mathematics, University of Bristol, Bristol, United Kingdom

Stochastic Multi-Armed Bandits Bounded Adversary Adversarial Robustness

Open paper AskPDF arXiv

We study adversarial combinatorial bandits with

m

-set actions, where at each round the learner selects

m

out of

d

items and observes only the aggregate loss of the selected items. The resulting action set contains

K=\binom{d}{m}

elements and can therefore be exponentially large. Nevertheless, the loss of every action is determined by the same

d

-dimensional vector of item losses. We propose a computationally efficient algorithm that exploits this structure without explicitly enumerating the action set. Against adaptive non-anticipating adversaries, it guarantees, with probability at least

1-δ

, regret against the best fixed action of

R_T = O\left(\sqrt{dT\log(K/δ)}\right).

This matches the high-probability regret bound of the finite-action EXP3-KW algorithm of Zimmert and Lattimore, whose direct implementation may require exponential space. Our algorithm instead represents each sampling distribution with

d

parameters and runs in polynomial time without enumerating the action set. Thus, it resolves the open problem posed by Maiti et al.

Abstract

Explore similar work

An Efficient Near-Optimal Algorithm for Adversarial mmm-Set Bandits

Multi-Armed Bandits With Best-Action Queries

Bandits with Probing: Optimal Regret and the Limits of Winner Feedback

An Efficient Near-Optimal Algorithm for Adversarial $m$ -Set Bandits