m-Set Adversarial Bandits with Winner Feedback

1 INTRODUCTION

• The paper situates m-sets between combinatorial bandits, whose subset utility sums unknown rewards, and MNL bandits, whose utility is the reward of a drawn action.MNL bandits use known rewards and unknown attraction parameters; their feedback includes the drawn action's index.Source: §1 · p. 1
• FB+WF combines the sum of unknown adversarial rewards with full-bandit and Plackett–Luce winner-index feedback, making it richer than full-bandit but poorer than semi-bandit feedback.The model identifies attraction parameters with the unknown rewards.Source: §1 · p. 1
• FB+WF minimax regret is characterized up to logarithmic factors against the best fixed m-set for the adversarial reward sequence.The paper presents this as its main result.Source: §1 · p. 1
• With winner feedback only, minimax regret is linear even when the learner observes both the winning arm's index and reward.This contrasts with the FB+WF setting, which also provides full-bandit feedback.Source: §1 · pp. 1–2
• For winner-reward utility, sum-of-rewards feedback yields linear regret even when the winner index is also revealed.The paper also reports linear regret for sum utility with winner index and reward feedback.Source: §1 · p. 2
• For the studied alternative models, identical feedback laws can conceal different optimal actions, and the paper uses this property in its lower bounds.The paper distinguishes this phenomenon from Plackett–Luce scale invariance.Source: §1 · p. 2

2 RELATED WORKS

• Bubeck et al. (2012), Ito et al. (2019), and Audibert et al. (2014) established minimax regret bounds for m-set adversarial bandits with full-bandit and semi-bandit feedback.The cited work covers upper and lower bounds for full-bandit feedback and bounds for semi-bandit feedback.Source: §2 · p. 2
• In MNL bandits, attraction parameters determine the winner while known rewards determine utility; adversarial attractions with a no-purchase option can yield regret exponential in m.The cited exponential dependence is tied to the no-purchase option in the stated model.Source: §2 · p. 2
• Table 1 summarizes old and new results for m-set bandits, while the cited related models use different action-set and feedback assumptions.The supplied passages do not specify the table's row or column layout.Source: Table 1 · p. 3, §2 · p. 3
• Pasteris et al. (2024) study maximum-reward winner feedback with sets of size at most m, while Bhaskara et al. (2023) study stochastic bandits with probes and realized-reward winners.These related models differ in their winner definitions and/or the allowed set sizes.Source: §2 · p. 3

3 PROBLEM STATEMENT

• An oblivious adversary assigns each of K base arms a reward in [0, 1] on each of T rounds, and the learner selects a subset of exactly m arms, with m < K.The played action space is all m-sized subsets of [K].Source: §3 · p. 3
• The learner receives the played subset's total reward and, in FB+WF, also observes a winner arm sampled from that subset by a Plackett–Luce choice model.Neither the winner's choice probability nor its reward is revealed.Source: §3 · pp. 3–4
• Expected total regret is measured against the best subset in hindsight, with expectation over the learner's decisions and feedback randomness.The comparator is a fixed subset of the base arms.Source: §3 · p. 4
• Unlike formulations that allow constrained action sets, this problem uses the unconstrained action space of all m-subsets.The passage identifies these as multitask bandits in Ito et al. (2019).Source: §3 · p. 4

4.1 Algorithm

• OSMA-W adapts Online Stochastic Mirror Ascent with forced exploration and base-arm reward estimates combining full-bandit and winner feedback.The algorithm maximizes and uses unbiased estimates built from the observed set reward and winner.Source: §4.1 · p. 4

4.2 Regret Upper Bound

• Winner-feedback randomness adds a factor m to the estimator variance, producing an extra √m factor in the regret upper bound.Forced exploration controls the estimates and exploration cost in the proof.Source: §4.2 · p. 5
• Using loss estimates would remove the need for forced exploration but lose the nonnegativity required by OSMD, preventing the stated route to removing logarithmic factors.The passage notes loser feedback as a possible but conceptually different interaction model.Source: §4.2 · p. 5

4.3 Regret Lower Bound

• The lower-bound proof averages over choices of ⌊m/2⌋ good arms and uses reward-distribution alternatives whose per-round KL divergence is O(ε^2/m).Shared uniform noise limits information from the winner feedback; the analysis accounts for the winner index’s additional information.Source: §4.3 · p. 6
• The FB+WF lower bound matches OSMA-W’s upper bound up to logarithmic factors, and the regret rate lies between full- and semi-bandit rates.The comparison places FB+WF above full bandit and below semi-bandit in difficulty.Source: §4.2 · p. 5, §4.3 · p. 6

Sum utility with winner feedback

• With sum-of-rewards utility, observing winner index and reward without the set’s total reward can still yield linear regret.The theorem’s stated setting requires m ≥ 3 and K ≥ 2m.Source: §5 · p. 6

Idealized Multiplayer MAB

• When only winner index and reward are observed under sum utility, the lower bound matches the upper bound up to logarithmic factors for the idealized Multiplayer MAB setting.The result adapts the FB+WF lower-bound proof to uniform sampling within the played set.Source: §5 · p. 6

Comparison of feedback models

• The section concludes that when set total reward is unavailable, observing a uniformly random arm’s reward is preferable in the worst case to observing the winner’s reward.The feedback models are not comparable because neither can simulate the other.Source: §5 · p. 6

Expected-winner-reward utility with FB+WF feedback

• For expected-winner-reward utility with FB+WF feedback, the regret is linear because indistinguishable feedback can conceal whether adding an arm improves or cannibalizes utility.The proof sketch constructs two models with the same feedback law for every action and an average suboptimality gap of at least 1/444.Source: §5 · pp. 6–7

Expected-winner-reward utility with winner feedback

• For expected-winner-reward utility with winner index and reward feedback, an INF adaptation achieves sublinear regret, but the dependence on m is exponential.The passage states that revealing the winner index does not change this exponential dependence.Source: §5 · p. 7

Stationary correlated rewards

• All four algorithms’ regret curves are sublinear and ordered as predicted by theory, although K-Metaplayer performs slightly better than OSMA-W in their respective settings.Figure 1a reports regret per round on stationary correlated rewards; the appendix reports qualitatively analogous results across 100 reward-sequence instances.Source: Figure 1 · p. 8, §6 · p. 8

Action-size comparison

• For increasing action size m, the gaps between feedback models widen as predicted, but the tested m range is too small to establish polynomial dependence on m.Figure 1b reports final total regret after 20,000 rounds with K = 20.Source: Figure 1 · p. 8, §6 · p. 8

Corrupted rewards

• With 20% of rounds corrupted by decoy-arm rewards, the results are similar to the stationary stochastic case.The decoy arms are sampled at the start, and receive reward 1 on corrupted rounds.Source: §6 · p. 8

Additional reward instances

• Additional experiments on uncorrelated uniform and Bernoulli rewards and on block-wise stationary rewards also produce similar results.Source: §6 · p. 8

7 CONCLUSION

• Alternative OSMD regularizers may remove logarithmic regret factors, although the INF regularizer does not apply directly.The conclusion identifies this as a potential improvement to OSMA-W.Source: §7 · p. 8
• OSMA-W currently works only with the complete action space; constrained spaces require adapting forced exploration, and efficient algorithms with reward proxies remain unresolved.Source: §7 · p. 8
• Further models to study include loser feedback, nonlinear attractions, a no-purchase option, and decoupled attractions and revenues.Loser feedback makes choice probability proportional to losses rather than rewards.Source: §7 · p. 8

A PROOF OF THEOREM 1

• The proof adapts semi-bandit OSMD analysis by maximizing rewards and replacing base-arm rewards with unbiased estimates, including for selected arms.Source: A PROOF OF THEOREM 1 · p. 10
• A general OSMD lemma bounds expected regret for Legendre regularizers when the reward estimator is unbiased and the update satisfies a domain condition.The proof then instantiates the lemma with negative entropy over the convex hull of m-sized action vectors.Source: A PROOF OF THEOREM 1 · pp. 10, 12
• The first regret term is bounded using the three-point Bregman identity, projection inequality, and telescoping divergence terms.Source: A PROOF OF THEOREM 1 · p. 11
• The remaining term uses the estimator’s conditional expectation and a choice of exploration and learning-rate parameters to satisfy the proof’s bound conditions.Source: A PROOF OF THEOREM 1 · pp. 11–13

B PROOF OF THEOREM 2

• Theorem 2 considers m ≥ 2, K ≥ 2m, and T > K/27; the construction keeps arm rewards in [1/4, 3/4].Source: B PROOF OF THEOREM 2 · pp. 16, 19
• Yao’s minimax principle reduces the lower bound to a random hard instance, with a uniform permutation selecting good arms and an alternative model removing one good arm.Source: B PROOF OF THEOREM 2 · pp. 16–17
• The models are compared through the learner’s observations of set reward and winner index; their conditional observation laws differ only when the played set contains the canceled arm.Source: B PROOF OF THEOREM 2 · p. 18
• The proof bounds distinguishability using total variation and KL divergence, applying Lemma 3 to the selected arms’ reward construction.Source: B PROOF OF THEOREM 2 · pp. 14, 18

Theorem 3

• With feedback (It, rt(It)) but no observation of rt(St), indistinguishable models force regret at least γT on some deterministic oblivious sequence.The proof shows the feedback law is identical conditional on any valid action, then compares expected rewards under the two models.Source: C PROOFS OF SECTION 5 · pp. 19, 20, 22

Theorem 4

• For uniform-index winner feedback Yt = (Jt, rt(Jt)), Theorem 4 assumes m ≥ 2, K ≥ 2m, and T > K/3; its proof replaces Equation (105) with Equation (121) in Step 4.Source: C PROOFS OF SECTION 5 · p. 22

Theorem 5

• For winner-reward utility with feedback (rt(St), It), indistinguishable models force regret at least T/444 on some oblivious sequence.The two models have identical conditional feedback; their optimal actions differ, with a minimum suboptimal-action gap of 1/222.Source: C PROOFS OF SECTION 5 · pp. 23–24

Theorem 6

• For winner-reward feedback (It, rt(It)), an INF adaptation treats each m-set as a bandit arm and uses its sampled winner reward while ignoring the winner index.The sampled reward lies in [0, 1] and has expectation equal to that set’s expected winner reward.Source: C PROOFS OF SECTION 5 · p. 24
• Theorem 6’s lower-bound construction makes feedback identical for actions other than the targeted m-set, whose reward-vector distribution is altered by parity.Under the reference model, base-arm rewards are independent Bernoulli(1/2); the alternative changes the targeted set while preserving the distribution on other actions.Source: C PROOFS OF SECTION 5 · p. 25

• At least one model P_S induces the stated regret, and averaging over its oblivious reward-sequence distribution yields a deterministic sequence with at least that regret.Source: C PROOFS OF SECTION 5 · p. 26

D AUXILIARY LEMMAS

• Lemma 4 considers mixtures of two probability measures and bounds their KL divergence using chi-squared divergence and triangular discrimination.The passage also cites Topsøe (2000) for bounding triangular discrimination by twice the total variation distance.Source: D AUXILIARY LEMMAS · pp. 26–27
• Lemma 5 studies feedback consisting of an arm drawn uniformly from the played set and that arm’s reward under two reward models.It defines the corresponding marginal reward laws for each arm.Source: D AUXILIARY LEMMAS · p. 27
• The proof applies the KL chain rule and uses that the sampled arm has the same uniform law under both models and is independent of the reward vector.Source: D AUXILIARY LEMMAS · p. 27

Experimental setup

• The experiments use K = 10, m = 4, T = 50000, a random set of m good arms, and ε = 0.1.Each algorithm is tested with its corresponding feedback model.Source: E EXPERIMENTS: FURTHER RESULTS AND… · p. 27

Stationary uniform rewards

• The stationary uniform experiment uses independent rewards Ut,i + εI{i ∈G}, with Ut,i uniform on [0, 1 − ε].Figure 4 reports total regret per round over 10 seeds with 95% bootstrap confidence intervals.Source: E EXPERIMENTS: FURTHER RESULTS AND… · p. 27, Figure 4 · p. 29

Stationary stochastic correlated rewards

• Figure 3 repeats the Figure 1a experiment across 100 independently generated instances of stationary stochastic correlated rewards.The plot reports total regret per round with 99% bootstrap confidence intervals.Source: E EXPERIMENTS: FURTHER RESULTS AND… · p. 27, Figure 3 · p. 28

Stationary Bernoulli rewards

• The stationary binary experiment uses independent Bernoulli rewards with means Ut,i + εI{i ∈G}, where Ut,i is uniform on [0, 1 − ε].Figure 6 reports total regret per round over 10 seeds with 95% bootstrap confidence intervals.Source: E EXPERIMENTS: FURTHER RESULTS AND… · p. 28, Figure 6 · p. 30

Nonstationary uniform rewards

• All algorithms appear capable of keeping dynamic regret sublinear against the best per-block m-subset in the nonstationary experiment.The good-arm set changes across four blocks of geometrically increasing size; the per-block comparator is stronger than the one considered in the theory.Source: E EXPERIMENTS: FURTHER RESULTS AND… · p. 28, Figure 5 · p. 29