arXiv CS open access

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

2026 · arxiv_cs

arXiv CS · Papers · 2026

deep-learning machine-learning neural-networks

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

An Efficient Near-Optimal Algorithm for Adversarial m-Set Bandits Francesco Bacchiocchi1 , Tommaso Cesari2 , and Roberto Colomboni3 1

DEIB, Politecnico di Milano, Milano, Italy School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, Canada 3 School of Mathematics, University of Bristol, Bristol, United Kingdom francesco.bacchiocchi@polimi.it, tcesari@uottawa.ca, roberto.colomboni@bristol.ac.uk

August 13, 2026

arXiv:2608.12231v1 [cs.LG] 12 Aug 2026

Abstract 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 d resulting action set contains K = 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 p RT = O dT log(K/δ) . This matches the high-probability regret bound of the finite-action EXP3–KW algorithm of Zimmert and Lattimore [29, Theorem 6 and Algorithm 3], 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. [26].

Introduction

In this paper, we study adversarial m-set bandits. At each round, the learner selects m out of d items and incurs the sum of their losses, but observes only the aggregate loss, not the loss of each d selected item. Since any m-subset may be chosen, the learner has K = m possible actions, and its goal is to minimize regret with respect to the best fixed m-set in hindsight. For finite action sets, Zimmert and Lattimore [29, Theorem 6 and Algorithm √3] show that e dmT ) when EXP3–KW achieves a high-probability regret bound that, for m-sets, becomes O( m ≤ d/2.1 However, its direct implementation maintains one weight for every action, and since d K = m , this can require exponential space. A possible workaround is to use the results in [26]. Specifically, Maiti et al. [26, Appendix E.6] give a polynomial-time high-probability algorithm based on a general directed acyclic graph representation that, for m-sets, turns into an algorithm √ e achieving O(d mT ) regret bound. Despite this implementation being computationally efficient, it √ e dmT ). remains unclear whether one can efficiently obtain the sharper rate O( We provide a positive answer to this question with a polynomial-time algorithm. Against adap√ e dsT ) regret with high probability, tive non-anticipating adversaries, our algorithm guarantees O( 1

e suppresses logarithmic factors. The notation O

where √ s := min{m, d − m}. In the regime m ≤ d/2, we have s = m, and the bound becomes e O( dmT ), and thus it matches the regret rate of finite-action EXP3–KW by Zimmert and Lattimore [29, Theorem 6 and Algorithm 3]. To obtain our efficient algorithm, we work with weighted m-set distributions, a family of distribution that can be represented by d item weights, from which one can sample and compute the required moments in polynomial time [11, 24]. The high-level idea is to implement the finite-action EXP3–KW algorithm while keeping the sampling distributions at all iterates within this family. The main obstacle is that the updates of EXP3-KW come with a quadratic correction, which does not preserve the weighted m-set structure. We overcome this difficulty by using the covariance bound of Cesari and Colomboni [10, Corollary 1.3] to construct a carefully chosen affine majorant of the quadratic correction on the m-set action space: exponential-weights updates using this majorant preserve the family of weighted m-set distributions, while the majorant also provides the estimation-error control needed to obtain the desired high-probability regret rate.

Setting and problem formulation

Preliminary definitions. For a positive integer n, we write [n] := {1, . . . , n}. For a vector z = (z1 , . . . , zn ) and k ∈ [n], we define its k-th elementary symmetric polynomial as X Y ek (z) := zi , e0 (z) := 1, ek (z) := 0 for k < 0 or k > n. S⊆[n]: |S|=k i∈S

Fix two integers d ≥ 2 and 1 ≤ m ≤ d − 1. We define the action set and its size as n o d d X := Xd,m := x ∈ {0, 1} : ∥x∥1 = m , K := |X | = . m

(1)

Each action x ∈ X selects exactly m of the d items, xi = 1 if item i is selected and xi = 0 otherwise. Its support is supp(x) := {i ∈ [d] : xi = 1}. Thus, the support of each action is an m-element subset of [d], which we call an m-set. Conversely, each m-set S ⊆ [d] corresponds to the indicator vector 1S ∈ X . We therefore use actions in X and m-sets interchangeably. Let s := min{m, d − m}. By the symmetry of the binomial coefficient, log K ≤ s log (ed/s) . Linear-algebra notation. For a symmetric matrix A ∈ Rd×d , we denote its kernel by ker(A) := {z ∈ Rd : Az = 0} and its Moore–Penrose pseudoinverse by A+ . For two symmetric matrices A, B ∈ Rd×d , we write A ⪰ B if A − B is positive semidefinite or, equivalently z ⊤ Az ≥ z ⊤ Bz

for every z ∈ Rd .

We write A ≻ 0 if z ⊤ Az > 0 for every nonzero z ∈ Rd . In particular, A is positive semidefinite if A ⪰ 0, and positive definite if A ≻ 0. Let 1 := (1, . . . , 1)⊤ , and define H0 := {y ∈ Rd : ⟨y, 1⟩ = 0}.

span{1} := {a1 : a ∈ R},

Thus, H0 is the subspace orthogonal to span{1}. If A is positive semidefinite and ker(A) = span{1}, then A is invertible on H0 . For every y ∈ H0 , the vector A+ y is the inverse of A applied to y within this subspace. We will use the order-reversing property of matrix inversion [18, Corollary 7.7.4(a)]. Specifically, suppose that A and B are positive semidefinite linear operator with ker(A) = ker(B) = span{1}, 2

then their restrictions to H0 = 1⊥ are positive definite. Consequently, if A ⪰ cB, for c > 0, then (A|H0 )−1 ⪯

1 (B|H0 )−1 . c

Equivalently, 1 A+ ⪯ B + . c In particular, y ⊤ A+ y ≤ Probability notation.

1 ⊤ + y B y c

for every y ∈ H0 .

For a finite set Y ⊆ Rd , we denote its probability simplex by     X ∆(Y) := p : Y → [0, 1] : p(y) = 1 .   y∈Y

For p, q ∈ ∆(Y), we define the entropy of p and the Kullback–Leibler (KL) divergence from p to q as X X p(y) . H(p) := − p(y) log p(y), KL(p ∥ q) := p(y) log q(y) y∈Y

y∈Y

We use the convention 0 log(0/q) = 0, and set KL(p ∥ q) := +∞ if p(y) > 0 = q(y) for some y ∈ Y. Let X be a random vector drawn from p ∈ ∆(Y). We define the marginal vector, second-moment matrix, and covariance matrix of p as µ(p) := EX∼p [X],

M (p) := EX∼p [XX ⊤ ],

Σ(p) := CovX∼p (X) = M (p) − µ(p)µ(p)⊤ .

When Y = X , the i-th marginal probability is µi (p) = EX∼p [Xi ] = PX∼p [Xi = 1]. Thus, µi (p) is the probability that action X selects item i. If M (p) is invertible, we refer to the inverse-design quadratic form x⊤ M (p)−1 x as the leverage score of x under p. Weighted m-set distributions. Given θ ∈ Rd , define wi := eθi > 0 for every i ∈ [d]. For every m-set S ⊆ [d], the weighted m-set distribution pθ is P Q exp wi i∈S θi = i∈S . P pθ (S) := P em (w) A⊆[d]: |A|=m exp i∈A θi Its log-partition function is ! F (θ) := log

exp

A⊆[d]: |A|=m

θi

= log em (eθ1 , . . . , eθd ).

i∈A

If S ∼ pθ and X := 1S ∈ X is its indicator vector, then ∇F (θ) = EX∼pθ [X] = µ(pθ ),

∇2 F (θ) = CovX∼pθ (X) = Σ(pθ ). 3

Although pθ may assign positive probability to exponentially many actions, the d parameters θ1 , . . . , θd represent it. Finally, we define a set of distributions whose marginal probabilities stay away from 0 and 1. Let r := m/d and fix λ ∈ (0, 1). Define Pλ := {p ∈ ∆(X ) : λr ≤ µi (p) ≤ 1 − λ(1 − r) for every i ∈ [d]} .

(2)

The uniform distribution U over X satisfies µi (U ) = r for every i ∈ [d]. Therefore, U ∈ Pλ . Adversarial m-set bandit protocol. Fix a time horizon T ≥ 1. Let (Ft )Tt=0 denote the filtration generated by the interaction history, where Ft−1 contains the information available before round t. At each round t ∈ [T ], the learner selects an Ft−1 -measurable distribution pt ∈ ∆(X ), where X , defined in Equation (1), represents the set of actions available to the learner. The adversary selects a loss vector ℓt ∈ Rd that is also Ft−1 -measurable. Thus, the adversary is adaptive nonanticipating. The loss vector ℓt may depend on the entire interaction history up to round t − 1, but not on the learner’s random draw at round t. Therefore, conditionally on Ft−1 , both pt and ℓt are fixed. The learner then draws Xt ∼ pt and observes only the loss Yt := ⟨Xt , ℓt ⟩. We use the standard action-level normalization |⟨x, ℓt ⟩| ≤ 1

∀x ∈ X , t ∈ [T ],

also adopted by Maiti et al. [26, Assumption 1] and Zimmert and Lattimore [29, Section 1]. 2 The learner’s realized regret after T rounds, measured against the best fixed action in hindsight, is RT :=

T T X X ⟨Xt , ℓt ⟩ − min ⟨x, ℓt ⟩. x∈X

t=1

Throughout, we use the shorthand Et [ · ] := E[ · |Ft−1 ] for conditional expectation given the information available before round t ∈ [T ].

Original contributions

Our main contribution is an algorithm (Algorithm 1) for adversarial m-set bandits that achieves the regret guarantee summarized in the following. Theorem (Informal version of Theorem 1). There exists an algorithm that can be implemented in polynomial time such that, against any adaptive non-anticipating adversary, with probability at least 1 − δ, it achieves s ! d 1 RT = O dT log + log . m δ For example, one may take Algorithm 1. We first discuss the state-of-the-art results for adversarial m-set bandits. Maiti et al. [26, √ e Appendix E.6] obtain √ a high-probability regret bound of O(d mT ) for m-set bandits and leave open whether the extra d factor in this bound can be removed with an efficient algorithm. Although this consequence is not stated explicitly in their paper, applying their general DAG guarantee [26, Theorem 7] to the m-set DAG constructed in Maiti et al. [26, Appendix E.6], which has O(md) 2

More generally, if the action losses are bounded in absolute value by L, rescaling gives the same result with the regret bound multiplied by L.

d paths, and using log K ≤ m log(ed/m) yields, for m ≤ d/2, the regret bound edges and K = m √ e O(m dT ). √ e dsT ), where s := min{m, d − m}. In Our algorithm achieves a regret upper bound of O( √ e particular, when m √ our bound √ ≤ d/2, we have s = m, and the bound becomes O( dmT ). Thus, e improves the √ O(d mT ) guarantee of Maiti et al. [26, Appendix E.6] by a factor of d, and the √ e derived O(m dT ) consequence above [26, Theorem 7 and Appendix E.6] by a factor of m. Consequently, relative to the better of these two bounds in the regime m ≤ d/2, the improvement √ is a factor of m. Zimmert and Lattimore [29, Theorem √6 and Algorithm 3] obtain a high-probability regret bound e dmT ), matching our regret bound. However, their finitethat, when m ≤ d/2, yields the rate O( d action exponential-weights algorithm is stated with one weight for each of the K = m actions, which can be exponential in d. Our algorithm achieves the same regret rate using only d parameters and running in polynomial time (see Section 5.3 for the implementation details). √ In Table 1, we summarize the best known high-probability guarantees with T dependence for adversarial m-set bandits. All results reported there consider action-normalized losses and adaptive non-anticipating adversaries. We next discuss the regret lower bound in the regime m ≤ d/2, making its dependence on d − m explicit. Let ρ := (d − m)/d. When the loss vectors belong to {0, 1}d Ito et al. [19, Theorem 2] prove the expected-regret lower bound n √ o Ω min ρ2 dm3 T , ρm3/4 T . To compare this result with our action-normalized setting, observe that an m-set may incur a loss as large as m when the loss vectors belong to {0, 1}d . We therefore divide the losses by m. Since regret scales linearly with the losses, this yields the action-normalized lower bound √ ρT 2 Ω min ρ dmT , 1/4 . m √ Consequently, when m ≤ d/2 and T ≥ dm3/2 , this lower bound is Ω( dmT ). On the other hand, setting δ = T −2 in√our high-probability guarantee and using RT ≤ 2T yields an expected-regret e dmT ). Therefore, our rate matches the minimax expected-regret lower bound upper bound of O( up to logarithmic factors in this regime. In particular, any improvement in the polynomial dependence of a uniform high-probability bound valid for δ = T −2 would imply the same improvement in expected regret and would therefore contradict this lower bound. Work Zimmert and Lattimore [29] (Theorem 6 and Algorithm 3) Maiti et al. [26] (Appendix E.6) Maiti et al. [26] (Theorem 7 applied here to the DAG of Appendix E.6) This work

Regret bound √ e dmT ) O(

Computational complexity Exponential

√ e O(d mT ) √ e O(m dT )

Polynomial

√ e dmT ) O(

Polynomial

Table 1: Statistical and computational comparison for the regime m ≤ d/2. All upper bounds hold with high probability against adaptive non-anticipating adversaries.

Challenges and techniques. In their finite-action EXP3–KW algorithm, Zimmert and Lattimore [29, Algorithm 3] obtain a high-probability regret bound using the biased surrogate loss ⟨x, ℓbt ⟩ − ηx⊤ Mt−1 x, where η > 0 is the learning rate, Mt = EX∼pt [XX ⊤ ] is the second-moment matrix of the sampling distribution pt , and ℓbt := Mt−1 Xt ⟨Xt , ℓt ⟩ is the loss estimate constructed after drawing Xt ∼ pt and observing the scalar loss ⟨Xt , ℓt ⟩. The main obstacle to an efficient implementation of this approach is that the leverage score is quadratic in x. Even if we start from a weighted m-set distribution and we insert this term directly into an action-level multiplicative-weights update, the updated distribution need not remain in the d weighted m-set family and, consequently, it may require one weight for each of the K = m actions. Our first step is to replace the leverage score with an affine upper bound. Starting from the covariance inequality of Cesari and Colomboni [10, Corollary 1.3], we derive ⊤

Mt−1 x ≤ ϕt (x) := 1 + 2

d X (xi − µt,i )2 i=1

µt,i (1 − µt,i )

(3)

Although the expression P defining ϕt appears quadratic, it is affine on X . Indeed, every x ∈ X satisfies x2i = xi and di=1 xi = m. For later convenience, we scale this affine majorant by four and write c⊤ for every x ∈ X . t x = 4ϕt (x) We then define the surrogate loss Zt (x) := ⟨x, ℓbt ⟩ − ηc⊤ t x.

(4)

The correction in Equation (4) plays the same role as the quadratic correction used by Zimmert and Lattimore [29, Algorithm 3], but remains affine in x. Consequently, the multiplicative-weights step maps a weighted m-set distribution to another weighted m-set distribution. A further difficulty is that the affine leverage majorant can become arbitrarily large when a marginal probability approaches 0 or 1. Consequently, the estimated action losses ⟨x, ℓbt ⟩ can have arbitrarily large one-step magnitude and conditional second moment, preventing both the secondorder exponential-weights analysis and the required high-probability concentration arguments. To obtain the uniform leverage bound needed in the analysis, we project the updates toward the set Pλ introduced in Section 2. More precisely, the exact constrained OMD iterate is the KL projection of the unprojected exponential-weights distribution pet+1 onto Pλ . Our polynomial-time approximation is instead guaranteed to belong to Pλ/2 , where the extra slack serves to accommodate the finite accuracy of the projection procedure. The approximate KL update also preserves the weighted m-set family, as shown in Lemma 11. Hence, every iterate can be represented as pθt using the d parameters θt,1 , . . . , θt,d , rather than one weight for each of the K actions.

The comparator in the OMD analysis must also belong to Pλ . However, the distribution δx , which puts all its probability on x, has marginal probabilities in {0, 1} and does not belong to Pλ . We therefore use the smoothed comparator qx := (1 − λ)δx + λU,

(5)

where U is the uniform distribution over X . By construction, qx ∈ Pλ . Since the losses are action-normalized, using qx in place of δx adds at most 2λT to the regret. The remaining analytical challenge is to control the estimation error under the smoothed comparator qx , namely, T X EX∼qx [⟨X, ℓbt ⟩] − EX∼qx [⟨X, ℓt ⟩] . t=1

Applying a concentration bound to this estimation error introduces the positive term T

ηX EX∼qx [c⊤ t X]. 4 t=1

Controlling this term separately would not give the desired regret bound. However, the affine correction in Equation (4) contributes −η

T X

EX∼qx [c⊤ t X]

t=1

to the OMD bound. Since c⊤ t X = 4ϕt (X) ≥ 0, this negative contribution dominates the positive concentration term. Their sum is therefore non-positive and may be dropped from the regret upper bound. Finally, the elementary-symmetric-polynomial recurrence of Chen and Liu [11, Section 2, Method 2] allows us to compute the marginal probabilities and second-moment matrix of pt in polynomial time. The associated conditional-Bernoulli procedure gives an exact sample from pt without enumerating X ; see Chen and Liu [11, Section 4, Procedure 3], as well as the alternative backward-path construction in Procedure 5. This sampling rule is also the L = diag(w) specialization of Kulesza and Taskar [24, Section 3.1 and Algorithm 2]. Together with the fact that both the affine update and the approximate KL update preserve the family of weighted m-set distributions, these routines establish the polynomial-time implementation in Proposition 1.

Related work

Optimal design and finite-action linear bandits. Kiefer [21] introduced the general framework of approximate optimal design, and Kiefer and Wolfowitz [22] proved the equivalence between D- and G-optimality. For a finite action set A ⊂ Rd , Bubeck p et al. [8, Theorem 4] combined exponential weights with John’s exploration and obtained O( dT log |A|) expected regret under action-normalized losses. For general convex action sets, Abernethy et al. [2, √ Theorem 1] used e 3/2 T ). self-concordant barriers to obtain an efficient expected-regret bound of O(d √ The first general high-probability bound with T dependence against adaptive adversaries √ e 3/2 T ) had a larger dependence on the dimension. Bartlett et al. [5, Theorem 1] obtained O(d regret. Abernethy and Rakhlin [1, Theorem 4 and Section 5.4] then gave a general high-probability reduction. Its efficient implementation requires affine confidence bounds tailored to the geometry 7

of the action set. Later, Lee et al. [25, Theorem 3.1] √ gave the first general polynomial-time high7/2 e probability algorithm, with√worst-case regret O(d T ). Zimmert and Lattimore [29, Theorem 4] e 2 T ). improved this rate to O(d For a finite action set A, Zimmert and Lattimore [29, Theorem 3] also comp 6 and Algorithm bined EXP3 with Kiefer–Wolfowitz exploration and obtained O dT log(|A|/δ) regret with high probability. We use this regret bound as our statistical benchmark. When applied to our action set d X = Xd,m , a direct implementation maintains K = m weights. However, K can be exponential in d. Combinatorial optimization with bandit feedback. Early adversarial bandit algorithms for structured action sets were given by McMahan and Blum [27] and Awerbuch and Kleinberg [4]. Cesa-Bianchi and Lugosi [9] subsequently introduced ComBand, a general framework for adversarial combinatorial bandits. This line of work was subsequently developed by Audibert et al. [3, Section 4, after Theorem 5], who considered full-information, semi-bandit, and full-bandit feedback and established several lower bounds. √ In particular, they conjectured that the minimax regret in the bandit setting should scale as m dT , where each action selects m out of d items and T is the time horizon. On the computational side, Combes et al. [14, Theorem 6 and 7] later introduced CombEXP, improving the computational complexity for some combinatorial action classes while preserving the existing regret scaling. Cohen et al. [13, Theorems 1 and 5] disproved the conjecturep of Audibert et al. [3]. Using correlated losses, they proved an expected-regret lower bound of Ω( dm3 T / log T ) for a multitask √ problem in which every action selects m items. Ito et al. [19, Theorem 2] later removed the 1/ log T factor using binary correlated losses. For m-set bandits, their result also describes the dependence on d − m and on the time horizon, as discussed in Section 3. Efficient algorithms for structured action sets. Several works avoid enumerating exponentially large action sets by using a compact representation or an optimization oracle. For expected or pseudo-regret, Hazan and Karnin [17, Corollary 35] use volumetric spanners, while Ito et al. [20,√Theorem 1] use an optimization oracle. Both approaches run in polynomial time and achieve e T ) regret with polynomial dependence on the dimension. O( Earlier efficient high-probability guarantees with T 2/3 dependence were obtained by Braun and Pokutta [7, Theorem 3.1], using a linear-optimization oracle over the action polytope, and by Sakaue et al. [28, Theorem 1], using a zero-suppressed binary decision diagram. These approaches are √ efficient when the required oracle or compact representation is available, but do not attain the T dependence achieved here. The work most closely related to ours is Maiti et al. [26, Appendix E.6]. They represent the actions as paths in a DAG and obtain an efficient algorithm with a high-probability regret √ e guarantee against adaptive adversaries. For m-sets, their algorithm achieves O(d mT ) regret, and √ e dmT ) can be achieved efficiently. Our result answers this question with a they ask whether O( polynomial-time algorithm. Finally, Kontogiannis et al. [23, Theorem 3.2 and Appendix G.5] show that their kernelized e 2/3 4/3 2/3 payoff-based framework applies to m-sets and yields √ O(d m T ) high-probability regret. Our result improves the dependence on the horizon to T . Weighted m-set distributions. The weighted m-set distribution introduced in Section 2 is also known as a conditional Bernoulli or rejective-sampling distribution [11, 12, 16]. Classical methods

based on elementary symmetric polynomials allow us to compute its normalizing constant and marginal probabilities, and to sample from it efficiently [11, 24]. Beyond these computational properties, weighted m-set distributions have a covariance structure central to our analysis: Cesari and Colomboni [10, Corollary 1.3] prove exactly the halfnormalized covariance bound used below.

A near-optimal algorithm for m-set bandits

5.1

Affine upper bound on the leverage score

In this section, we derive the affine upper bound on the leverage score x⊤ M −1 x used by our algorithm. Complete proofs of the consequences derived here are in Section A. The covariance bound itself is imported from Cesari and Colomboni [10, Corollary 1.3] and is not reproved here. Lemma 1 (Cesari–Colomboni covariance bound). Let p ∈ ∆(X ) be a weighted m-set distribution with positive weights, where 1 ≤ m ≤ d − 1, and let Σ be its covariance matrix. For every i ∈ [d], define vi := Σii . Then 1 vv ⊤ Σ⪰ D− , 2 V P where v := (v1 , . . . , vd )⊤ , D := diag(v) , and V := di=1 vi . Using Lemma 1, we prove the following bound on the Moore–Penrose pseudoinverse Σ+ of Σ. Lemma 2. Let p ∈ ∆(X ) be a weighted m-set distribution with positive weights, where 1 ≤ m ≤ d−1. Let Σ be its covariance matrix, and define vi := Σii for every i ∈ [d]. Then, ker(Σ) = span{1}, and, for every y ∈ H0 := {z ∈ Rd : ⟨z, 1⟩ = 0}, we have y ⊤ Σ+ y ≤ 2

d X y2 i

i=1

Proof sketch. Let P := D −vv ⊤ /V . A direct calculation, given in Section A.1, shows that ker(P ) = ker(Σ) = span{1}. Therefore, both matrices are positive definite, and hence invertible, on H0 . On H0 , the bound in Lemma 1 gives 1 Σ ⪰ P. 2 Thus, on H0 , we have y ⊤ Σ+ y ≤ 2y ⊤ P + y for every y ∈ H0 . (6) P We now relate P + to D−1 . Since y ∈ H0 , we have di=1 yi = 0. Therefore, PD

−1

vv ⊤ D− V

−1

v X y=y− yi = y. V

(7)

i=1

We also have P (P + y) = y,

(8)

because P + coincides with the inverse of P on H0 . Subtracting Equation (8) from Equation (7) gives P (D−1 y − P + y) = 0. It follows that D−1 y − P + y ∈ ker(P ) = span{1}. 9

Since y ∈ H0 , this difference is orthogonal to y. Thus, ⊤

⊤

y P y=y D

−1

d X y2 i

i=1

(9)

Combining (6) and (9) proves the result. See Section A.1 for the complete proof. The next lemma relates the pseudoinverse Σ+ of the covariance matrix of a weighted m-set distribution to the inverse M −1 of its second-moment matrix. Lemma 3. Let p ∈ ∆(X ) be a weighted m-set distribution with positive weights and 1 ≤ m ≤ d − 1. Then its second-moment matrix M is positive definite and, for every y ∈ H0 , y ⊤ M −1 y = y ⊤ Σ+ y. Consequently, for every x ∈ X , x⊤ M −1 x = 1 + (x − µ)⊤ Σ+ (x − µ), where µ = µ(p) is the marginal vector of p. Proof sketch. If a⊤ M a = 0, full support implies a⊤ x = 0 for every x ∈ X . Comparing two actions that differ by swapping items i and j forces ai = aj . Hence a = c1, and then 0 = a⊤ x = cm gives c = 0. Thus M ≻ 0. Hence, M 1 = EX∼p [XX ⊤ 1] = mµ. In addition, since M is invertible, M −1 µ =

1 . m

(10)

Now fix y ∈ H0 . By Equation (10), µ⊤ M −1 y = (M −1 µ)⊤ y =

1 ⊤ 1 y = 0. m

Therefore, ΣM −1 y = (M − µµ⊤ )M −1 y = y. Since Σ+ is the inverse of Σ on H0 , the vectors M −1 y and Σ+ y differ by an element of ker(Σ) = span{1}. This difference is orthogonal to y, and thus y ⊤ M −1 y = y ⊤ Σ+ y.

(11)

Finally, fix x ∈ X . Since both x and µ have coordinates that sum to m, we have x − µ ∈ H0 . Expanding x = µ + (x − µ) and using Equation (10) and Equation (11) gives x⊤ M −1 x = 1 + (x − µ)⊤ Σ+ (x − µ). See Section A.2 for the complete proof. We now combine Lemmas 2 and 3 to obtain the affine upper bound on the leverage score used by our algorithm.

Lemma 4. Let p ∈ Pλ be a weighted m-set distribution, where 1 ≤ m ≤ d − 1, and let µ and M be its marginal vector and second-moment matrix. For every x ∈ X , define ϕp (x) := 1 + 2

d X (xi − µi )2 i=1

µi (1 − µi )

Then, for every x ∈ X , x⊤ M −1 x ≤ ϕp (x). Moreover, 4ϕp (x) = c⊤ p x, where   P µ 1 + 2 dj=1 1−µj j 1 − 2µ i  cp,i = 4  +2 for every i ∈ [d]. m µi (1 − µi ) Finally, EX∼p [ϕp (X)] = 2d + 1, and, for every x ∈ X , 0 ≤ ϕp (x) ≤ 1 + 4d/λ. Proof sketch. Fix x ∈ X . Since both x and µ have coordinates that sum to m, we have x − µ ∈ H0 . Therefore, Lemmas 2 and 3 give x⊤ M −1 x = 1 + (x − µ)⊤ Σ+ (x − µ) ≤ 1 + 2

d X (xi − µi )2 i=1

µi (1 − µi )

= ϕp (x).

Since EX∼p [(Xi − µi )2 ] = µi (1 − µi ), we have EX∼p [ϕp (X)] = 1 + 2d. Moreover, p ∈ Pλ implies µi ≥ λr and 1 − µi ≥ λ(1 − r), where r = m/d. Separating the m coordinates for which xi = 1 from the d − m coordinates for which xi = 0 gives d X (xi − µi )2 i=1

µi (1 − µi )

≤

m d−m 2d + = . λr λ(1 − r) λ

Hence, 0 ≤ ϕp (x) ≤ 1 +

4d . λ

Finally, using x2i = xi , we obtain ϕp (x) = 1 + 2

d X j=1

X 1 − 2µi µj +2 xi . 1 − µj µi (1 − µi ) i=1

P Since i xi = m, we can write the constant term as a linear function of x. Multiplying the resulting affine representation by four gives 4ϕp (x) = c⊤ p x, with cp defined in the statement. See Section A.3 for the complete proof.

5.2

Algorithm and high-probability regret

In this section, we present Algorithm 1 and prove its high-probability regret guarantee. At each round t, the learner draws an action Xt from a weighted m-set distribution pt ∈ Pλ/2 and observes only the scalar loss ⟨Xt , ℓt ⟩. It uses this observation to construct the KW loss estimate ℓbt . At round t, we set ϕt := ϕpt and ct := cpt , where ϕp and cp are defined in Lemma 4. The b learner forms a biased surrogate loss by subtracting the affine correction ηc⊤ t x from ⟨x, ℓt ⟩. Finally, the learner computes an approximate entropic OMD update toward Pλ (defined in Eq. (2)). The update is accurate enough for the OMD analysis and returns a distribution in Pλ/2 , so its marginal probabilities stay away from 0 and 1. We state the resulting regret bound in Theorem 1. 11

Algorithm 1 Affine KW–OMD with approximate entropic updates toward Pλ Require: T ≥ 1, δ ∈ (0, 1) q 1 1: Set η ← min 256d , log(12K/δ) 320dT 2: Set λ ← 128ηd and εp ← η/T 3: Initialize θ1 ← 0 and p1 ← pθ1 = U

▷ U is a uniform distribution

4: for t = 1, . . . , T do 5: 6:

Compute µt ← µ(pt ), Mt ← M (pt ) = EX∼pt [XX ⊤ ] Set ϕt ← ϕpt and ct ← cpt , so that, for every x ∈ X , ϕt (x) ← 1 + 2

d X (xi − µt,i )2 i=1

7: 8: 9: 10: 11: 12:

and

µt,i (1 − µt,i )

c⊤ t x = 4ϕt (x)

Draw Xt ∼ pt Observe Yt = ⟨Xt , ℓt ⟩ Compute ℓbt ← M −1 Xt Yt t

Define Zt (x) ← ⟨x, ℓbt ⟩ − ηc⊤ t x, for every x ∈ X Set zt ← ℓbt − ηct , θet+1 ← θt − ηzt , and pet+1 ← p e

θt+1

Apply a fixed deterministic implementation of the procedure in Lemma 11 to obtain pt+1 = pθt+1 satisfying pt+1 ∈ Pλ/2 and, simultaneously for every q ∈ Pλ , KL(q∥pt+1 ) + KL(pt+1 ∥e pt+1 ) ≤ KL(q∥e pt+1 ) + εp .

13: end for

Theorem 1 (High-probability KW bound). There exists a universal constant C > 0 such that the following holds. Let T ≥ 1 be an integer, let δ ∈ (0, 1), and assume 1 ≤ m ≤ d − 1. Run Algorithm 1. Then, with probability at least 1 − δ, s 1 RT ≤ C dT log K + log , δ where K =

d m . One may take C = 160.

Proof sketch. For every x ∈ X , define the smoothed comparator qx := (1 − λ)δx + λU, where δx puts all its probability on x and U is the uniform distribution over X . By construction, qx ∈ Pλ . The concentration bounds below hold simultaneously for every x ∈ X , so we can then choose x to be a best action. By adding and subtracting the expected losses under pt and qx , and applying Lemma 9, we

obtain, with high probability, RT ≤

T X

r (EX∼pt [⟨X, ℓt ⟩] − EX∼qx [⟨X, ℓt ⟩]) +O

t=1

1 T log δ

! + O(λT ).

(12)

}

=:(⋆)

The square-root term controls the difference between the learner’s realized and expected losses. The term O(λT ) is the cost of using qx in place of x. It remains to bound (⋆). Adding and subtracting the expectations of the estimated losses gives (⋆) =

T X

EX∼pt [⟨X, ℓt ⟩] − EX∼pt [⟨X, ℓbt ⟩]

t=1 T X

T X EX∼pt [⟨X, ℓbt ⟩] − EX∼qx [⟨X, ℓbt ⟩] + EX∼qx [⟨X, ℓbt ⟩] − EX∼qx [⟨X, ℓt ⟩] .

t=1

(13)

t=1

The first and third terms in (13) can be bounded by applying Lemma 7 under pt and qx , respectively. To bound the second term, recall the surrogate loss Zt (x) := ⟨x, ℓbt ⟩ − ηc⊤ t x,

x ∈ X.

Since ⟨x, ℓbt ⟩ = Zt (x) + ηc⊤ t x, we can apply Lemma 6 and Lemma 8 to the surrogate losses Zt . Moreover, Lemma 4 gives EX∼pt [c⊤ t X] = 4(2d + 1) = O(d). Combining these results, we have (⋆) ≤ O

T ηX log K + log(1/δ) + ηdT + 1 + −η + EX∼qx [c⊤ t X] . η 4 t=1 | {z }

(14)

=:(⋆⋆)≤0

The coefficient −η in (⋆⋆) comes from the affine correction −ηc⊤ t x in Zt , while the coefficient η/4 comes from the concentration bound for the third term in (13). Since c⊤ t X = 4ϕt (X) ≥ 0, the term (⋆⋆) is nonpositive. The additive constant in (14) is the accumulated error of the approximate KL updates: by the choice εp = η/T , its total contribution is T εp /η = 1. Substituting (14) into (12) gives ! r log K + log(1/δ) 1 RT ≤ O + ηdT + 1 + λT + T log . (15) η δ Finally, substituting λ = 128ηd and the value of η, and combining the resulting high-probability estimate with the deterministic bound RT ≤ 2T , gives the stated result with C = 160. The complete two-case calculation is given in Section B.1. √ e dsT ). In Let s := min{m, d − m}. Since√log K ≤ s log (ed/s) , the bound in Theorem 1 is O( e dmT ). particular, when m ≤ d/2, it is O( 13

5.3

Polynomial-time implementation

We now show that Algorithm 1 can be implemented in polynomial time without enumerating X . The key idea is to maintain pt in the weighted m-set form pθt , with θt ∈ Rd , thereby allowing all steps of the algorithm to be performed without enumerating X . The convex problem used in the update is solved to the explicit inverse-polynomial objective accuracy established in Lemma 11. Proposition 1. Algorithm 1 can be implemented in T · poly(d, m, log T ) time and poly(d, m) space, without enumerating X . At every round, pt is a weighted m-set distribution pθt represented by the d parameters θt,1 , . . . , θt,d . Proof sketch. We observe that if pt has a weighted m-set representation, its moments can be computed and a sample can be drawn in polynomial time using the recurrences in Lemma 12. The strategy update in Algorithm 1 can be decomposed into two steps. First, define the exponential update pet+1 (x) ∝ pt (x) exp −ηZt (x) . The exact update toward which we compute is the KL projection p⋆t+1 ∈ arg min KL(p∥e pt+1 ). p∈Pλ

Since Zt is affine, the exponential update only changes the d parameters, and pet+1 remains a weighted m-set distribution. The exact projection is characterized by a convex problem in 2d variables. Solving this problem to the objective accuracy in Lemma 11 returns a weighted m-set distribution pt+1 ∈ Pλ/2 and introduces at most εp = η/T error in the KL inequality used by OMD. The required objective accuracy is inverse-polynomial, and the ellipsoid method obtains it using polynomially many evaluations of the objective and its gradient. Since the initial distribution p1 is uniform and admits a weighted m-set representation, this representation is preserved at every round. Thus, all steps of the algorithm can be performed in polynomial time without enumerating X . The complete proof is given in Section C.3.

Conclusion and future work

We introduced an algorithm for adversarial m-set bandits whose high-probability regret matches the finite-action EXP3–KW rate up to logarithmic factors, while running in polynomial time without enumerating the action set. Our results leave two main questions open. First, it remains open to determine whether the log K term in the leading bound can be replaced by s := min{m, d − m}, √ yielding O( dsT ) realized regret at constant confidence, or whether an additional logarithmic factor is unavoidable against adaptive non-anticipating adversaries. We remark, to the best of our knowledge, this issue is open already for ordinary adversarial multi-armed bandits, corresponding to m = 1. Second, it would be interesting to determine whether our approach extends beyond m-sets. A natural test case is that of matroid-base action sets, since m-sets are precisely the bases of a uniform matroid. Although affine exponential-weights updates still preserve weighted matroidbase distributions, our analysis also requires an efficiently computable affine leverage majorant with controlled expectation and range, as well as efficient moment and KL-projection routines. These properties do not follow from our present covariance-based construction, so extending the nearoptimal high-probability guarantee to broader matroid classes would require additional structural and computational ideas. 14

Appendix A

Proofs from Section 5.1

A.1

Proof of Lemma 2

Lemma 2. Let p ∈ ∆(X ) be a weighted m-set distribution with positive weights, where 1 ≤ m ≤ d−1. Let Σ be its covariance matrix, and define vi := Σii for every i ∈ [d]. Then, ker(Σ) = span{1}, and, for every y ∈ H0 := {z ∈ Rd : ⟨z, 1⟩ = 0}, we have y ⊤ Σ+ y ≤ 2

d X y2 i

i=1

Proof. Let vv ⊤ . V We first identify the kernels of P and Σ. Since p has positive weights, it has full support on X . Therefore, z ⊤ Σz = VarX∼p (⟨z, X⟩) = 0 P := D −

only if ⟨z, x⟩ is the same for every x ∈ X . Fix i ̸= j. Since 1 ≤ m ≤ d − 1, we can choose two actions that differ only by exchanging item i with item j. The equality of their inner products with z gives zi = zj . Thus, all the coordinates of z are equal. Conversely, ⟨1, X⟩ = m for every X ∈ X , so Σ1 = 0. Hence, ker(Σ) = span{1}.

(16)

Moreover, for every z ∈ Rd , z⊤P z =

d X

P vi zi2 −

i=1

where

d i=1 vi zi

d X

vi (zi − z̄v )2 ,

i=1

Pd z̄v :=

i=1 vi zi

Full support also gives vi = Var(Xi ) = µi (1 − µi ) > 0

for every i ∈ [d].

It follows that z ⊤ P z = 0 if and only if all the coordinates of z are equal. Therefore, ker(P ) = span{1}.

(17)

By (16) and (17), the pseudoinverse order property stated in the preliminaries applies to the bound in Lemma 1. Hence, for every y ∈ H0 , y ⊤ Σ+ y ≤ 2y ⊤ P + y.

(18)

It remains to compute y ⊤ P + y. Since D = diag(v), we have v ⊤ D−1 = 1⊤ . Thus, for every y ∈ H0 , v (19) P D−1 y = y − 1⊤ y = y. V 15

Moreover, range(P ) = H0 , so P P + y = y.

(20)

Equations (19) and (20) show that D−1 y and P + y both solve the equation P z = y. Therefore, D−1 y − P + y ∈ ker(P ) = span{1}. Since y ∈ H0 , it is orthogonal to this difference. Consequently, y ⊤ P + y = y ⊤ D−1 y =

d X y2 i

i=1

(21)

Combining (18) and (21) proves the result.

A.2

Proof of Lemma 3

Lemma 3. Let p ∈ ∆(X ) be a weighted m-set distribution with positive weights and 1 ≤ m ≤ d − 1. Then its second-moment matrix M is positive definite and, for every y ∈ H0 , y ⊤ M −1 y = y ⊤ Σ+ y. Consequently, for every x ∈ X , x⊤ M −1 x = 1 + (x − µ)⊤ Σ+ (x − µ), where µ = µ(p) is the marginal vector of p. Proof. We first show that M is positive definite. Suppose that a⊤ M a = 0. Since a⊤ M a = EX∼p (a⊤ X)2 , we have a⊤ x = 0 for every x ∈ X , because p has full support. Fix i ̸= j. Since 1 ≤ m ≤ d − 1, we can choose two actions that differ only by exchanging item i with item j. Comparing their inner products with a gives ai = aj . Thus, a = c1 for some c ∈ R. Since every x ∈ X has m nonzero coordinates, 0 = a⊤ x = cm. Therefore, c = 0, and hence a = 0. This proves that M ≻ 0. By Lemma 2, ker(Σ) = span{1}. Since Σ is symmetric, this also gives range(Σ) = H0 . Every X ∈ X satisfies ⟨X, 1⟩ = m. Therefore, M 1 = EX∼p X⟨X, 1⟩ = mµ. Since M is invertible, M −1 µ =

1 1. m

Now fix y ∈ H0 and let z := M −1 y. By (22), µ⊤ z = (M −1 µ)⊤ y =

1 ⊤ 1 y = 0. m

It follows that Σz = (M − µµ⊤ )z = y. 16

(22)

Moreover, Σ+ y also solves the equation Σu = y. Therefore, z − Σ+ y ∈ ker(Σ) = span{1}. Since y ∈ H0 , it is orthogonal to this difference. Hence, y ⊤ M −1 y = y ⊤ Σ+ y.

(23)

Finally, fix x ∈ X and let y := x − µ. Since 1⊤ x = 1⊤ µ = m, we have y ∈ H0 . Expanding x = µ + y gives x⊤ M −1 x = µ⊤ M −1 µ + 2y ⊤ M −1 µ + y ⊤ M −1 y = 1 + y ⊤ Σ+ y, where the second equality follows from (22) and (23). Substituting y = x − µ proves that x⊤ M −1 x = 1 + (x − µ)⊤ Σ+ (x − µ). This concludes the proof.

A.3

Proof of Lemma 4

Lemma 4. Let p ∈ Pλ be a weighted m-set distribution, where 1 ≤ m ≤ d − 1, and let µ and M be its marginal vector and second-moment matrix. For every x ∈ X , define ϕp (x) := 1 + 2

d X (xi − µi )2 i=1

µi (1 − µi )

Then, for every x ∈ X , x⊤ M −1 x ≤ ϕp (x). Moreover, 4ϕp (x) = c⊤ p x, where  cp,i = 4 

1+2

µj j=1 1−µj

 1 − 2µi  +2 µi (1 − µi )

for every i ∈ [d].

Finally, EX∼p [ϕp (X)] = 2d + 1, and, for every x ∈ X , 0 ≤ ϕp (x) ≤ 1 + 4d/λ. Proof. For x ∈ X , put y = x − µ ∈ H0 . By Lemma 3, x⊤ M −1 x = 1 + y ⊤ Σ+ y. Lemma 2 gives y ⊤ Σ+ y ≤ 2

X i

yi2 , µi (1 − µi )

and hence x⊤ M −1 x ≤ ϕp (x). Taking expectations and using E[(Xi − µi )2 ] = µi (1 − µi ) yields EX∼p [ϕp (X)] = 2d + 1. For the range bound, if xi = 1, then 2

(xi − µi )2 1 − µi 2 =2 ≤ ; µi (1 − µi ) µi λr 17

if xi = 0, then 2

(xi − µi )2 2 µi ≤ =2 . µi (1 − µi ) 1 − µi λ(1 − r)

Since x has m ones and d − m zeros, 4d 2m 2(d − m) + =1+ . λr λ(1 − r) λ

ϕp (x) ≤ 1 + Finally, because xi ∈ {0, 1}, 2

1 − 2µi (xi − µi )2 µi + 2xi =2 . µi (1 − µi ) 1 − µi µi (1 − µi )

Thus ϕp (x) = 1 + 2

X i

X 1 − 2µi µi +2 xi . 1 − µi µi (1 − µi ) i

Distribute the constant term evenly over the selected coordinates using the resulting affine representation by four, to obtain 4ϕp (x) = c⊤ p x.

i xi = m, and multiply

Proofs from Section 5.2

Assumption 1. Throughout this appendix, T ≥ 1 is an integer, δ ∈ (0, 1), 0<η≤

1 , 64

1 λ = 128ηd ≤ . 2

The loss sequence (ℓt )Tt=1 is predictable, that is, ℓt is Ft−1 -measurable for every t ∈ [T ], and satisfies the action-normalized condition in Section 2. The initialization and the update in Algorithm 1 ensure that, at every round t, the sampling distribution pt is a weighted m-set distribution with positive weights and pt ∈ Pλ/2 . Hence, the assumptions of Lemmas 1 and 4 hold at every round. Recall from Algorithm 1 that ϕt := ϕpt ,

ct := cpt ,

c⊤ t x = 4ϕt (x),

Zt (x) := ybt (x) − ηc⊤ t x.

We also write ybt (x) := ⟨x, ℓbt ⟩ = x⊤ Mt−1 Xt Yt . Set

8d . λ Applying Lemma 4 with λ/2, for every x ∈ X , we have B := 1 +

0 ≤ c⊤ t x ≤ 4B,

EX∼pt [c⊤ t X] = 4(2d + 1),

x⊤ Mt−1 x ≤

c⊤ t x . 4

Lemma 5. Fix t ∈ [T ]. Suppose that 0 < η ≤ 1/64, λ = 128ηd ≤ 1/2, the loss at round t satisfies the action-normalized condition, and pt is a weighted m-set distribution with positive weights in Pλ/2 . Then, for every x ∈ X , η|Zt (x)| ≤ 1/4.

Proof. Since |Yt | ≤ 1, the Cauchy–Schwarz inequality in the norm induced by Mt−1 gives q q |b yt (x)| = |x⊤ Mt−1 Xt Yt | ≤ x⊤ Mt−1 x Xt⊤ Mt−1 Xt . Applying Lemma 4 to pt ∈ Pλ/2 , both leverage scores in the last inequality are at most ϕt (x) and ϕt (Xt ), respectively, and both ϕt -values are at most B =1+

8d . λ

1 5 8ηd =η+ ≤ . λ 16 64

Therefore

η|Zt (x)| ≤ (1 + 4η)ηB ≤

1 1+ 16

5 85 1 = < , 64 1024 4

where we used η ≤ 1/64. This proves the claim. Lemma 6. Under Assumption 1, for every distribution q ∈ Pλ , T X t=1

X KL(q∥p1 ) (EX∼pt [Zt (X)] − EX∼q [Zt (X)]) ≤ + 1 + 2η EX∼pt [Zt (X)2 ]. η t=1

Proof. Fix t ∈ [T ] and define the unprojected multiplicative-weights distribution pet+1 (x) :=

pt (x) exp(−ηZt (x)) , EX∼pt [exp(−ηZt (X))]

x ∈ X.

Since Zt (x) = zt⊤ x and pt = pθt , the distribution above is precisely pθet+1 from Algorithm 1. The guarantee in Algorithm 1 therefore gives, for every q ∈ Pλ , KL(q∥pt+1 ) ≤ KL(q∥e pt+1 ) + εp , where we dropped the nonnegative term KL(pt+1 ∥e pt+1 ). By the definition of pet+1 , KL(q∥e pt+1 ) = KL(q∥pt ) + ηEX∼q [Zt (X)] + log EX∼pt [exp(−ηZt (X))]. Combining this identity with (24) and rearranging gives η (EX∼pt [Zt (X)] − EX∼q [Zt (X)]) ≤ KL(q∥pt ) − KL(q∥pt+1 ) + ηEX∼pt [Zt (X)] + log EX∼pt [exp(−ηZt (X))] + εp . By Lemma 5, |ηZt (x)| ≤

1 4

for every x ∈ X . 19

(24)

Using 1 for |u| ≤ , 4

e−u ≤ 1 − u + 2u2 we obtain

EX∼pt [exp(−ηZt (X))] ≤ 1 − ηEX∼pt [Zt (X)] + 2η 2 EX∼pt [Zt (X)2 ]. The inequality log(1 + s) ≤ s then gives ηEX∼pt [Zt (X)] + log EX∼pt [exp(−ηZt (X))] ≤ 2η 2 EX∼pt [Zt (X)2 ]. Therefore, EX∼pt [Zt (X)] − EX∼q [Zt (X)] ≤

εp KL(q∥pt ) − KL(q∥pt+1 ) + 2ηEX∼pt [Zt (X)2 ] + . η η

Summing over t telescopes the KL terms. Finally, KL(q∥pT +1 ) ≥ 0, so T X t=1

X T εp KL(q∥p1 ) + 2η EX∼pt [Zt (X)2 ] + . (EX∼pt [Zt (X)] − EX∼q [Zt (X)]) ≤ η η t=1

Since εp = η/T , the last term equals one. Lemma 7. Under Assumption 1, let ρ ∈ (0, 1), and let (qt )Tt=1 be a predictable sequence of distributions in ∆(X ). For every t ∈ [T ], define At (qt ) := EX∼qt [⟨X, ℓt ⟩],

bt (qt ) := EX∼qt [b A yt (X)].

Then, with probability at least 1 − ρ, T X

bt (qt ) − At (qt ) A

t=1

≤

ηX log(2/ρ) EX∼qt [c⊤ . t X] + 4 η t=1

Proof. For every t ∈ [T ], define bt (qt ) − At (qt ). ∆t := A Recall that Et [·] = E[· | Ft−1 ]. Since pt , qt , and ℓt are predictable, they are fixed conditionally on Ft−1 . The only randomness at round t comes from Xt ∼ pt . We first show that ∆t has conditional mean zero. By the definition of the KW loss estimate, Et [ℓbt ] = Mt−1 Et [Xt Xt⊤ ]ℓt = Mt−1 Mt ℓt = ℓt . Therefore, bt (qt )] = At (qt ), Et [A

Et [∆t ] = 0.

Define x̄t := EX∼qt [X]. Then bt (qt ) = x̄⊤ M −1 Xt Yt . A t t Since |Yt | ≤ 1, bt (qt )2 ] ≤ x̄⊤ M −1 Et [Xt X ⊤ ]M −1 x̄t = x̄⊤ M −1 x̄t . Et [A t t t t t t The matrix Mt−1 is positive semidefinite. Hence, Jensen’s inequality gives h i −1 −1 ⊤ x̄⊤ M x̄ ≤ E X M X . t X∼qt t t t 20

By Lemma 4 and c⊤ t X = 4ϕt (X), X ⊤ Mt−1 X ≤ It follows that

c⊤ t X . 4

bt (qt )2 ] ≤ 1 EX∼qt [c⊤ Et [A t X]. 4

bt (qt )] = At (qt ), we obtain Since Et [A 1 Et [∆2t ] ≤ EX∼qt [c⊤ t X]. 4

(25)

We next bound ∆t uniformly. Since c⊤ t x ≤ 4B for every x ∈ X , the previous leverage bound gives −1 x̄⊤ t Mt x̄t ≤ B,

Xt⊤ Mt−1 Xt ≤ B.

8ηd 1 5 =η+ ≤ . λ 16 64

Therefore, |η∆t | ≤ 2ηB ≤

5 < 1. 32

(26)

For every u with |u| ≤ 1, eu ≤ 1 + u + u2 . Using (26), Et [∆t ] = 0, and (25), we obtain Et [exp(η∆t )] ≤ 1 + η 2 Et [∆2t ] ≤ exp η 2 Et [∆2t ] 2 η ⊤ ≤ exp EX∼qt [ct X] . 4 For s ∈ {0, . . . , T }, define Ms := exp η

s X t=1

! s η2 X EX∼qt [c⊤ ∆t − t X] . 4 t=1

The previous conditional moment bound shows that (Ms )Ts=0 is a nonnegative supermartingale with M0 = 1. Hence, E[MT ] ≤ 1. By Markov’s inequality, with probability at least 1 − ρ/2, T X t=1

ηX log(2/ρ) ∆t ≤ EX∼qt [c⊤ . t X] + 4 η t=1

The same argument applied to −∆t gives, with probability at least 1 − ρ/2, T X

−

t=1

log(2/ρ) ηX EX∼qt [c⊤ . ∆t ≤ t X] + 4 η t=1

A union bound over the two events proves the result. Lemma 8. Under Assumption 1, for every ρ ∈ (0, 1), with probability at least 1 − ρ, T X

1 8d log . ϕt (Xt ) ≤ 2(2d + 1)T + 2 1 + λ ρ

t=1

Proof. Recall that B = 1 + 8d/λ. Conditionally on Ft−1 , the distribution pt and the function ϕt are fixed, while Xt ∼ pt . Therefore, Lemma 4 gives Et [ϕt (Xt )] = EX∼pt [ϕt (X)] = 2d + 1,

0 ≤ ϕt (Xt ) ≤ B.

Since ϕt (Xt )/B ∈ [0, 1], convexity of the exponential gives eu ≤ 1 + (e − 1)u,

u ∈ [0, 1].

It follows that Et exp

ϕt (Xt ) B

(e − 1)(2d + 1) ≤1+ ≤ exp B

(e − 1)(2d + 1) B

For s ∈ {0, . . . , T }, define s

Ms := exp

1 X (e − 1)(2d + 1)s ϕt (Xt ) − B B

! .

t=1

The previous conditional moment bound shows that (Ms )Ts=0 is a nonnegative supermartingale with M0 = 1. Hence, E[MT ] ≤ 1. By Markov’s inequality, with probability at least 1 − ρ, T X t=1

1 ϕt (Xt ) ≤ (e − 1)(2d + 1)T + B log . ρ

Using e − 1 ≤ 2 and substituting the definition of B proves the result. Lemma 9. Under Assumption 1, for every ρ ∈ (0, 1), with probability at least 1 − ρ, T X

r (⟨Xt , ℓt ⟩ − EX∼pt [⟨X, ℓt ⟩]) ≤

t=1

1 2T log . ρ

Proof. Define Dt := ⟨Xt , ℓt ⟩ − EX∼pt [⟨X, ℓt ⟩]. Since pt and ℓt are determined before Xt is sampled, E[Dt | Ft−1 ] = 0. 22

Thus, (Dt )Tt=1 is a martingale difference sequence. By the action-normalized condition, ⟨Xt , ℓt ⟩ ∈ [−1, 1]. Therefore, conditionally on Ft−1 , Dt belongs to an interval of length at most 2. The Azuma–Hoeffding inequality then gives, for every u > 0, ! T X u2 P Dt ≥ u ≤ exp − . 2T t=1 p Taking u = 2T log(1/ρ) proves the result.

B.1

Proof of the main regret theorem

d m . One may take C = 160.

Proof. For every x ∈ X , define the smoothed comparator qx := (1 − λ)δx + λU, where δx assigns probability one to x, and U is the uniform distribution over X . If xi = 1, the i-th marginal of qx is 1 − λ(1 − r), while, if xi = 0, it is λr. Therefore, qx ∈ Pλ . Moreover, since p1 = U , KL(qx ∥p1 ) = KL(qx ∥U ) = log K − H(qx ) ≤ log K. Applying Lemma 6 with q = qx gives T X

(EX∼pt [Zt (X)] − EX∼qx [Zt (X)]) ≤

t=1

X log K + 1 + 2η EX∼pt [Zt (X)2 ]. η t=1

We first bound the second-order term. Since Zt (X) = ybt (X) − ηc⊤ t X, we have 2 Zt (X)2 ≤ 2b yt (X)2 + 2η 2 (c⊤ t X) .

Furthermore, we have EX∼pt [b yt (X)2 ] = Yt2 Xt⊤ Mt−1 EX∼pt [XX ⊤ ]Mt−1 Xt = Yt2 Xt⊤ Mt−1 Xt ≤ ϕt (Xt ), where the last inequality follows from |Yt | ≤ 1 and Lemma 4. Recall that 0 ≤ c⊤ t X ≤ 4B,

EX∼pt [c⊤ t X] = 4(2d + 1). 23

(27)

Hence, 2 ⊤ EX∼pt [(c⊤ t X) ] ≤ 4BEX∼pt [ct X] = 16B(2d + 1).

It follows that 2ηEX∼pt [Zt (X)2 ] ≤ 4ηϕt (Xt ) + 64η 3 B(2d + 1).

(28)

Using Zt (X) = ybt (X) − ηc⊤ t X in (27), and then applying (28), gives T X

(EX∼pt [b yt (X)] − EX∼qx [b yt (X)])

t=1 T

≤

X X log K + 1 + 4η ϕt (Xt ) + 64η 3 B(2d + 1)T + 4η(2d + 1)T − η EX∼qx [c⊤ t X]. η t=1

(29)

t=1

We now apply Lemma 8 with ρ = δ/4. With probability at least 1 − δ/4, 4η

T X t=1

4 ϕt (Xt ) ≤ 8η(2d + 1)T + 8ηB log . δ

Since ηB = η +

8ηd 1 5 =η+ ≤ , λ 16 64

we have 8ηB ≤ 5/8. Therefore, 4η

T X t=1

4 ϕt (Xt ) ≤ 8η(2d + 1)T + log . δ

(30)

Next, apply Lemma 7 to the predictable sequence qt = pt , with ρ = δ/4. With probability at least 1 − δ/4, T X

(EX∼pt [⟨X, ℓt ⟩] − EX∼pt [b yt (X)]) ≤ η(2d + 1)T +

t=1

log(8/δ) . η

(31)

For every x ∈ X , apply the same lemma to the constant predictable sequence qt = qx , with ρ = δ/(4K). A union bound over the K actions shows that, with probability at least 1 − δ/4, simultaneously for every x ∈ X , T X t=1

ηX log(8K/δ) (EX∼qx [b yt (X)] − EX∼qx [⟨X, ℓt ⟩]) ≤ EX∼qx [c⊤ . t X] + 4 η

(32)

t=1

Combining (29), (30), (31), and (32), we obtain, simultaneously for every x ∈ X , T X

(EX∼pt [⟨X, ℓt ⟩] − EX∼qx [⟨X, ℓt ⟩]) ≤

t=1

log K + log(8/δ) + log(8K/δ) η T

t=1

X 4 ηX EX∼qx [c⊤ EX∼qx [c⊤ + 1 + 13η(2d + 1)T + 64η B(2d + 1)T + log − η t X] + t X]. δ 4 3

(33)

The last two terms satisfy −η

T X

EX∼qx [c⊤ t X] +

t=1

3η X ηX EX∼qx [c⊤ EX∼qx [c⊤ t X] = − t X] ≤ 0, 4 4

3 2 2 because c⊤ t X ≥ 0. Moreover, 64η B = 64η (ηB) ≤ 5η ≤ 5η. Therefore, (33) gives T X

(EX∼pt [⟨X, ℓt ⟩] − EX∼qx [⟨X, ℓt ⟩]) ≤

t=1

4 log K + log(8/δ) + log(8K/δ) + 1 + 18η(2d + 1)T + log . η δ

Using 2d + 1 ≤ 3d and enlarging the logarithmic terms, we obtain T X

(EX∼pt [⟨X, ℓt ⟩] − EX∼qx [⟨X, ℓt ⟩]) ≤

t=1

3 log K + 3 log(12/δ) 4 + 1 + 54ηdT + log . η δ

(34)

Let x⋆ be a best action in hindsight. Since qx⋆ = (1 − λ)δx⋆ + λU and every action loss belongs to [−1, 1], EX∼qx⋆ [⟨X, ℓt ⟩] ≤ ⟨x⋆ , ℓt ⟩ + 2λ. Applying (34) with x = x⋆ gives T X

(EX∼pt [⟨X, ℓt ⟩] − ⟨x⋆ , ℓt ⟩)

t=1

4 3 log K + 3 log(12/δ) + 1 + 54ηdT + 2λT + log η δ 4 3 log K + 3 log(12/δ) + 1 + 310ηdT + log , ≤ η δ

≤

where the last inequality uses λ = 128ηd. Finally, apply Lemma 9 with ρ = δ/4. With probability at least 1 − δ/4, T X

r (⟨Xt , ℓt ⟩ − EX∼pt [⟨X, ℓt ⟩]) ≤

t=1

r 4 4 2T log ≤ 2 T log . δ δ

Since 310 ≤ 320 and 1 + log(4/δ) ≤ 4 log(12/δ), a union bound over the four failure events gives r 3 log K + 3 log(12/δ) 12 12 RT ≤ + 320ηdT + 4 log + 2 T log . (35) η δ δ It remains to substitute the value of η. Define A := log K + log Also set

Since K =

12 . δ

1 S := log K + log . δ d m

≥ 2, we have S ≥ log 2, and therefore log 12 23 A = S + log 12 ≤ 1 + S ≤ S, log 2 5 25

(36)

p where the last inequality follows from 125 < 218 . If η = A/(320dT ), then the first two terms in (35) are exactly √ 3A + 320ηdT = 4 320dT A. η Moreover, r √ 12 12 4 log ≤ 4A, 2 T log ≤ 2 dT A. δ δ It remains to consider the case in which η = 1/(256d). In this case, r A 1 ≥ , 320dT 256d which implies 2562 T ≤ dA. 320 Since the action-normalized condition gives the deterministic bound RT ≤ 2T , we also have r √ 2562 √ dT A ≤ 29 dT A. RT ≤ 2 320 √ In the non-clipped case, Equation (35) is at most 74 dT A + 4A. Since 29 < 74 and A > 0, the same bound also holds in the clipped case. Hence, by (36), r 23 √ 92 RT ≤ 74 dT S + S. (37) 5 5 Set r S γ := > 0. dT Since √ S = γ dT S, if γ ≤ 1/160, then r RT ≤

23 92 + γ 5 5

√ dT S

√ 43 92 1 ≤ 74 + dT S 20 5 160 √ 31843 √ dT S < 160 dT S, = 200 where we used

23 43 < . 5 20 If instead γ > 1/160, the deterministic bound RT ≤ 2T and d ≥ 2 give √ 2 √ 1√ RT ≤ 2T = dT S ≤ dT S < 160 dT S. dγ γ Thus, in all cases, s RT ≤ 160 dT

1 log K + log , δ

which proves the theorem with C = 160. 26

Polynomial-time implementation

This appendix proves Proposition 1. We show that our algorithm can be implemented in polynomial time without enumerating X . It maintains each pt as a weighted m-set distribution, computes the required moments and draws samples in polynomial time, and reduces the target KL projection to a convex problem in 2d variables. The convex problem is solved only to the inverse-polynomial accuracy specified below.

C.1

Updates and KL projection

We first identify the exact KL projection toward which the algorithm computes and show that it reduces to a convex problem in 2d variables. We then prove that solving this problem to an explicit objective accuracy is sufficient for the approximate update in Algorithm 1. Suppose that pt = pθt . Define the unprojected multiplicative-weights update pet+1 (x) :=

pt (x) exp(−ηZt (x)) . EX∼pt [exp(−ηZt (X))]

For every p ∈ Pλ , ηEX∼p [Zt (X)] + KL(p∥pt ) = KL(p∥e pt+1 ) − log EX∼pt [exp(−ηZt (X))]. The last term does not depend on p. Therefore, the exact constrained OMD iterate is the KL projection of pet+1 onto Pλ , namely, p⋆t+1 ∈ arg min KL(p∥e pt+1 ). p∈Pλ

The algorithm computes the approximate replacement specified in Algorithm 1 rather than assuming access to this exact projection. We next show that the first step preserves the weighted m-set form. Since c⊤ t x is affine in x, the surrogate loss is affine on X : ⊤ Zt (x) = ⟨x, ℓbt ⟩ − ηc⊤ t x = zt x,

zt := ℓbt − ηct .

Consequently, pet+1 (x) =

pθt (x) exp(−ηzt⊤ x) = pθet+1 (x), EX∼pθt [exp(−ηzt⊤ X)]

θet+1 := θt − ηzt .

(38)

Hence, if pt is a weighted m-set distribution, then so is pet+1 . It remains to analyze the target KL projection. The next lemma shows that the projection of a weighted m-set distribution onto Pλ is again a weighted m-set distribution. It also shows that the projection can be obtained by solving a convex problem in 2d variables. Lemma 10. Define ai := λr,

bi := 1 − λ(1 − r),

For every θe ∈ Rd , the KL projection arg min KL(p∥pθe) p∈Pλ

i ∈ [d].

is a weighted m-set distribution pθ+ , where θ+ = θe + α⋆ − β ⋆ . Here, (α⋆ , β ⋆ ) ∈ Rd+ × Rd+ minimizes the convex function Ψθe(α, β) := F (θe + α − β) − α⊤ a + β ⊤ b. Moreover, ∂Ψθe = bi − µi (θe + α − β). ∂βi

∂Ψθe = µi (θe + α − β) − ai , ∂αi

Proof. The projection minimizes KL(p∥pθe) over p ∈ ∆(X ), subject to ai − EX∼p [Xi ] ≤ 0,

EX∼p [Xi ] − bi ≤ 0.

The uniform distribution has all marginals equal to r, strictly between ai and bi . Hence, Slater’s condition holds. We may therefore use the standard strong-duality and KKT results of Boyd and Vandenberghe [6, Sections 5.2.3 and 5.5.3]. Introduce multipliers αi , βi ≥ 0. The Lagrangian is L(p, α, β) = KL(p∥pθe) + α⊤ a − β ⊤ b + EX∼p [(β − α)⊤ X]. For fixed (α, β), minimizing over p gives ⊤

p(x) ∝ pθe(x)e(α−β) x = pθ+α−β (x). e The resulting dual maximization is equivalent to minimizing Ψθe. Strong duality proves the first claim, and the derivative identities follow from ∇F = µ. Lemma 11. Let 0 < λ ≤ 1/2, let ε > 0, and let θe ∈ Rd satisfy KL(U ∥pθe) ≤ T. Define h :=

λs λ min{r, 1 − r} = , 2 2d

and

Let

R := 2dT,

2 2 ε ε . τ := min 2h , , 2 2R2

(39)

n o DR := (α, β) ∈ Rd+ × Rd+ : ∥α∥1 + ∥β∥1 ≤ R .

Suppose that (α, β) ∈ DR satisfies Ψθe(α, β) ≤

min (u,v)∈DR

Ψθe(u, v) + τ.

(40)

Set θ+ := θe + α − β,

p+ := pθ+ .

Then p+ ∈ Pλ/2 , and, for every q ∈ Pλ , KL(q∥p+ ) + KL(p+ ∥pθe) ≤ KL(q∥pθe) + ε. Moreover, a pair satisfying (40) can be computed by the ellipsoid method in time 1 poly d, m, log R, log . τ 28

(41)

Proof. Write bi := 1 − λ(1 − r).

ai := λr, Let (α⋆ , β ⋆ ) be an exact minimizer of Ψθe, let

θ⋆ := θe + α⋆ − β ⋆ ,

p⋆ := pθ⋆ ,

and write µ⋆ := µ(p⋆ ). We first show that an exact minimizer belongs to DR . By strong duality, the value of the dual function at (α⋆ , β ⋆ ) equals the value of the KL projection problem and is therefore nonnegative. Evaluating the Lagrangian from the proof of Lemma 10 at the uniform distribution gives 0 ≤ KL(U ∥pθe) − (1 − λ)r∥α⋆ ∥1 − (1 − λ)(1 − r)∥β ⋆ ∥1 . Consequently, ∥α⋆ ∥1 + ∥β ⋆ ∥1 ≤

T 2dT ≤ ≤ R. (1 − λ) min{r, 1 − r} s

Thus the minimum over DR in (40) is the global minimum. Let p := p+ , let µ := µ(p), and abbreviate Ψ := Ψθe. The KKT conditions for the exact projection give ai ≤ µ⋆i ≤ bi , αi⋆ (µ⋆i − ai ) = 0, βi⋆ (bi − µ⋆i ) = 0. Using KL(p⋆ ∥p) = F (θ+ ) − F (θ⋆ ) − (µ⋆ )⊤ (θ+ − θ⋆ ), and the complementary-slackness identities above, direct expansion gives the exact identity Ψ(α, β) − Ψ(α⋆ , β ⋆ ) = KL(p⋆ ∥p) + α⊤ (µ⋆ − a) + β ⊤ (b − µ⋆ ).

(42)

All three terms on the right-hand side are nonnegative. Hence, KL(p⋆ ∥p) ≤ τ. Pinsker’s inequality and the fact that every coordinate of an action belongs to [0, 1] imply r τ ⋆ ⋆ ∥µ − µ ∥∞ ≤ TV(p, p ) ≤ ≤ h. 2 Every marginal of p⋆ belongs to [λr, 1−λ(1−r)]. The distance from this interval to the corresponding boundary of [λr/2, 1 − λ(1 − r)/2] is at least h. Therefore, p ∈ Pλ/2 . Define the residual κ := α⊤ (µ − a) + β ⊤ (b − µ). By (42) and (α, β) ∈ DR , κ = α⊤ (µ⋆ − a) + β ⊤ (b − µ⋆ ) + (α − β)⊤ (µ − µ⋆ ) r τ ε ε ≤ + = ε, ≤τ +R 2 2 2 where the last inequality follows from (39). For every q ∈ Pλ , the exponential-family representation gives the three-point identity KL(q∥pθe) − KL(q∥p) − KL(p∥pθe) = (µ(q) − µ)⊤ (α − β). 29

Since a ≤ µ(q) ≤ b coordinatewise and α, β ≥ 0, the right-hand side is at least −κ. The bound κ ≤ ε proves (41). It remains to justify the computational claim. Put √ L :=

2d,

r0 :=

R , 8d

w0 :=

R 12d . 4d

For v ∈ R2d and r > 0, write B(v, r) := {u ∈ R2d : ∥u − v∥2 ≤ r}. The set DR has an explicit separation procedure, is contained in the Euclidean ball of radius R, and contains B(w √ 0 , r0 ). Indeed, every point of this ball has nonnegative coordinates and ℓ1 -norm at most R/2 + 2d r0 ≤ R. By the derivative formulas in Lemma 10, for every w ∈ R2d .

∥∇Ψθe(w)∥2 ≤ L

Thus Ψθe is globally L-Lipschitz. Its value and gradient can be evaluated using poly(d, m) operations by Lemma 12. Let w⋆ minimize Ψθe over DR . For 0 < ζ ≤ r0 , define ζ ζ wζ := 1 − w ⋆ + w0 . r0 r0 Convexity of DR and B(w0 , r0 ) ⊆ DR imply B(wζ , ζ) ⊆ DR . Moreover, ∥w⋆ − w0 ∥2 ≤ 2R, and hence Ψθe(wζ ) ≤ Ψθe(w⋆ ) + 16dLζ. Set

τ ζ := min r0 , 1 + (16d + 1)L

Weak constrained convex-function minimization returns a point w b at Euclidean distance at most ζ from DR , whose objective is at most ζ above the objective of every point whose closed ζ-ball is contained in DR [15, Problem (2.1.22) and Theorem 4.3.13]. In particular, Ψθe(w) b ≤ Ψθe(w⋆ ) + (16dL + 1)ζ. Let w be the Euclidean projection of w b onto DR . Since DR is the nonnegative ℓ1 -ball, its coordinates have the form wi = max{w bi − χ, 0}, wherePχ = 0 if the positive part of w b has ℓ1 -norm at most R, and otherwise χ is chosen so that i max{w bi − χ, 0} = R. Sorting the coordinates finds χ in O(d log d) time. Furthermore, ∥w − w∥ b 2 ≤ ζ, so global Lipschitzness gives Ψθe(w) ≤ Ψθe(w⋆ ) + 1 + (16d + 1)L ζ ≤ Ψθe(w⋆ ) + τ. Writing w = (α, β) gives a pair in DR satisfying (40). Since R/r0 = 8d and log(1/ζ) = O(log d + log R + log(1/τ )), the weak optimizer and the final projection use poly(d, m, log R, log(1/τ )) operations.

C.2

Moment and sampling routines

We now show how to compute the moments of a weighted m-set distribution and draw samples from it without enumerating X . Given its parameters θ, we compute its marginals, its second-moment matrix, and an exact sample using dynamic programs for elementary symmetric polynomials. Lemma 12. Given θ ∈ Rd , the log-partition function F (θ), all marginals µi (pθ ), all pairwise marginals πij (pθ ) := PX∼pθ (Xi = Xj = 1), and a sample from pθ can be drawn using a number of arithmetic operations polynomial in d and m, without enumerating X . Proof. Let wi := eθi , and define E[i, k] := ek (w1 , . . . , wi ). The recurrence E[i, k] = E[i − 1, k] + wi E[i − 1, k − 1]

(43)

computes all entries with 0 ≤ i ≤ d and 0 ≤ k ≤ m in O(dm) arithmetic operations. In particular, E[0, 0] = 1 and E[i, k] = 0 whenever k < 0 or k > i. Moreover, F (θ) = log E[d, m]. Write Ek := ek (w). For each i ∈ [d], define (−i)

(−i)

:= Ek − wi Ek−1 .

(−i,−j)

:= Ek

:= 1,

For i ̸= j, define (−i,−j)

:= 1,

(−i)

(−i,−j)

− wj Ek−1

We use the value zero for both arrays at negative indices. These recurrences give (−i,−j)

(−i)

wi Em−1 , µi (pθ ) = Em

πii (pθ ) = µi (pθ ),

wi wj Em−2 πij (pθ ) = Em

(i ̸= j).

(44)

All pairwise marginals can be obtained in O(d2 m) arithmetic operations. The recurrence is Method 2 of Chen and Liu [11, Section 2]. For sampling, start from (i, k) = (d, m). At state (i, k), include item i with probability wi E[i − 1, k − 1] . E[i, k]

(45)

If item i is selected, continue from (i − 1, k − 1); otherwise, continue from (i − 1, k). The recurrence (43) shows that (45) is the correct conditional probability. Thus, the procedure samples from pθ using O(dm) arithmetic operations after the table has been computed. It is the reverse-indexed conditional-Bernoulli procedure of Chen and Liu [11, Section 4, Procedure 3]; it is also equivalent to their direct backward-path construction (Procedure 5) and to the diagonal-L specialization of Kulesza and Taskar [24, Section 3.1 and Algorithm 2].

C.3

Proof of Proposition 1

Proposition 1. Algorithm 1 can be implemented in T · poly(d, m, log T ) time and poly(d, m) space, without enumerating X . At every round, pt is a weighted m-set distribution pθt represented by the d parameters θt,1 , . . . , θt,d . Proof. Recall that

η . T We prove by induction that every pt is a weighted m-set distribution in Pλ/2 and that εp =

KL(U ∥pt ) ≤ (t − 1)

1 + εp . 2

(46)

This holds at t = 1, because θ1 = 0 and p1 = pθ1 = U . Suppose that the claim holds at round t. Given θt , Lemma 12 computes the marginals and the second-moment matrix Mt in O(d2 m) operations. The same marginals determine ϕt and ct in O(d) operations. The sampling procedure in Lemma 12 draws Xt from pt without enumerating X : at each step, it draws one uniform random variable and compares it with the conditional probability in (45). By Lemma 3, Mt is positive definite. Therefore, Mt−1 and ℓbt can be computed in O(d3 ) operations. The surrogate loss is represented by the d-dimensional vector zt = ℓbt − ηct , and (38) gives pet+1 = pθet+1 . We next verify the hypothesis of Lemma 11. By the definition of the unprojected update, KL(U ∥e pt+1 ) = KL(U ∥pt ) + ηEX∼U [Zt (X)] + log EX∼pt [e−ηZt (X) ]. Under the induction hypothesis, Lemma 5 gives |ηZt (x)| ≤ 1/4 for every x ∈ X . In particular, 1 ηEX∼U [Zt (X)] ≤ , 4

1 log EX∼pt [e−ηZt (X) ] ≤ log(e1/4 ) = . 4

Hence, t 1 ≤ + (t − 1)εp ≤ T, 2 2 where the last inequality uses t ≤ T and T εp = η ≤ 1/64. Apply Lemma 11 with ε = εp . It computes (αt , βt ) ∈ D2dT so that (40) holds with the value τ in (39). Set θt+1 := θet+1 + αt − βt , pt+1 := pθt+1 . KL(U ∥e pt+1 ) ≤ KL(U ∥pt ) +

The lemma gives pt+1 ∈ Pλ/2 and the KL inequality required in Algorithm 1. Since U ∈ Pλ , that inequality also gives 1 KL(U ∥pt+1 ) ≤ KL(U ∥e pt+1 ) + εp ≤ t + εp . 2 This closes the induction. It remains to bound the number of operations uniformly over the rounds. Since K ≥ 2 and δ < 1, the learning rate in Algorithm 1 satisfies η≥

1 √ . 256d T

Consequently, εp ≥

1 , 256dT 3/2

λs 1 ≥ √ , 2d 4d T

R = 2dT.

The value τ in (39) therefore satisfies τ≥

1 219 d4 T 5

Thus log R + log(1/τ ) = O(log(dT )), and Lemma 11 runs in poly(d, m, log T ) time per round. All other steps run in time polynomial in d and m. The algorithm therefore runs in T · poly(d, m, log T ) time, uses poly(d, m) space, and never enumerates X .

References [1] Jacob Abernethy and Alexander Rakhlin. Beating the adaptive bandit with high probability. In Proceedings of the 22nd Annual Conference on Learning Theory, 2009. URL https://www.learningtheory.org/colt2009/papers/025.pdf. [2] Jacob Abernethy, Elad Hazan, and Alexander Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. In Proceedings of the 21st Annual Conference on Learning Theory, pages 263–274, 2008. URL https://www.learningtheory.org/colt2008/papers/123-Abernethy.pdf. [3] Jean-Yves Audibert, Sébastien Bubeck, and Gábor Lugosi. Regret in online combinatorial optimization. Mathematics of Operations Research, 39(1):31–45, 2014. doi: 10.1287/moor.2013.0598. URL https://doi.org/10.1287/moor.2013.0598. [4] Baruch Awerbuch and Robert D. Kleinberg. Adaptive routing with end-to-end feedback: Distributed learning and geometric approaches. In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, pages 45–53. ACM, 2004. doi: 10.1145/1007352.1007367. URL https://doi.org/10.1145/1007352.1007367. [5] Peter L. Bartlett, Varsha Dani, Thomas P. Hayes, Sham M. Kakade, Alexander Rakhlin, and Ambuj Tewari. High-probability regret bounds for bandit online linear optimization. In Proceedings of the 21st Annual Conference on Learning Theory, pages 335–342. Omnipress, 2008. URL https://www.learningtheory.org/colt2008/papers/30-Bartlett.pdf. [6] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. [7] Gábor Braun and Sebastian Pokutta. An efficient high-probability algorithm for linear bandits, 2016. URL https://arxiv.org/abs/1610.02072. [8] Sébastien Bubeck, Nicolò Cesa-Bianchi, and Sham M. Kakade. Towards minimax policies for online linear optimization with bandit feedback. In Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors, Proceedings of the 25th Annual Conference on Learning Theory, volume 23 of Proceedings of Machine Learning Research, pages 41.1–41.14. PMLR, 2012. URL https://proceedings.mlr.press/v23/bubeck12a.html. [9] Nicolò Cesa-Bianchi and Gábor Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78(5):1404–1422, 2012. doi: 10.1016/j.jcss.2012.01.001. URL https://doi.org/10.1016/j.jcss.2012.01.001. 33

[10] Tommaso Cesari and Roberto Colomboni. Effective resistance in fixed-rank external-field measures and constant-stretch correlated sampling on the hypersimplex, 2026. URL https://arxiv.org/abs/2607.13990. [11] Sean X. Chen and Jun S. Liu. Statistical applications of the poisson-binomial and conditional bernoulli distributions. Statistica Sinica, 7(4):875–892, 1997. URL https://www3.stat.sinica.edu.tw/statistica/j7n4/j7n44/j7n44.htm. [12] Xiang-Hui Chen, Arthur P. Dempster, and Jun S. Liu. Weighted finite population sampling to maximize entropy. Biometrika, 81(3):457–469, 1994. doi: 10.1093/biomet/81.3.457. URL https://doi.org/10.1093/biomet/81.3.457. [13] Alon Cohen, Tamir Hazan, and Tomer Koren. Tight bounds for bandit combinatorial optimization. In Satyen Kale and Ohad Shamir, editors, Proceedings of the 30th Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 629–642. PMLR, 2017. URL https://proceedings.mlr.press/v65/cohen17a.html. [14] Richard Combes, Mohammad Sadegh Talebi Mazraeh Shahi, Alexandre Proutière, and Marc Lelarge. Combinatorial bandits revisited. In Advances in Neural Information Processing Systems, volume 28, pages 2116–2124. Curran Associates, Inc., 2015. URL https://proceedings.neurips.cc/paper/2015/hash/ 0ce2ffd21fc958d9ef0ee9ba5336e357-Abstract.html. [15] Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics. Springer, Berlin, 1988. doi: 10.1007/978-3-642-97881-4. URL https://doi.org/10.1007/978-3-642-97881-4. [16] Jaroslav Hájek. Asymptotic theory of rejective sampling with varying probabilities from a finite population. The Annals of Mathematical Statistics, 35(4):1491–1523, 1964. doi: 10.1214/aoms/1177700375. URL https://doi.org/10.1214/aoms/1177700375. [17] Elad Hazan and Zohar Karnin. Volumetric spanners: An efficient exploration basis for learning. Journal of Machine Learning Research, 17(119):1–34, 2016. URL https://jmlr.org/papers/v17/hazan16a.html. [18] Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, 2 edition, 2012. doi: 10.1017/CBO9781139020411. URL https://doi.org/10.1017/CBO9781139020411. [19] Shinji Ito, Daisuke Hatano, Hanna Sumita, Kei Takemura, Takuro Fukunaga, Naonori Kakimura, and Ken-ichi Kawarabayashi. Improved regret bounds for bandit combinatorial optimization. In Advances in Neural Information Processing Systems, volume 32, pages 12027–12036. Curran Associates, Inc., 2019. URL https://proceedings.neurips.cc/ paper/2019/hash/d5b3d8dadd770c460b1cde910a711987-Abstract.html. [20] Shinji Ito, Daisuke Hatano, Hanna Sumita, Kei Takemura, Takuro Fukunaga, Naonori Kakimura, and Ken-ichi Kawarabayashi. Oracle-efficient algorithms for online linear optimization with bandit feedback. In Advances in Neural Information Processing Systems, volume 32, pages 10589–10598. Curran Associates, Inc., 2019. URL https://proceedings. neurips.cc/paper/2019/hash/e6385d39ec9394f2f3a354d9d2b88eec-Abstract.html. 34

[21] Jack Kiefer. Optimum experimental designs. Journal of the Royal Statistical Society: Series B (Methodological), 21(2):272–304, 1959. doi: 10.1111/j.2517-6161.1959.tb00338.x. URL https://doi.org/10.1111/j.2517-6161.1959.tb00338.x. [22] Jack Kiefer and Jacob Wolfowitz. The equivalence of two extremum problems. Canadian Journal of Mathematics, 12:363–366, 1960. doi: 10.4153/CJM-1960-030-4. URL https://doi.org/10.4153/CJM-1960-030-4. [23] Andreas Kontogiannis, Vasilis Pollatos, Gabriele Farina, Panayotis Mertikopoulos, and Ioannis Panageas. Efficient kernelized learning in polyhedral games beyond full information: From Colonel Blotto to congestion games. In Advances in Neural Information Processing Systems, volume 38, 2025. URL https://proceedings.neurips.cc/paper_files/paper/ 2025/hash/d6b452383b070d5ccf042d8d25e0cdb2-Abstract-Conference.html. NeurIPS 2025 Main Conference Track. [24] Alex Kulesza and Ben Taskar. k-DPPs: Fixed-size determinantal point processes. In Proceedings of the 28th International Conference on Machine Learning, pages 1193–1200. Omnipress, 2011. URL https://icml.cc/2011/papers/611_icmlpaper.pdf. [25] Chung-Wei Lee, Haipeng Luo, Chen-Yu Wei, and Mengxiao Zhang. Bias no more: High-probability data-dependent regret bounds for adversarial bandits and MDPs. In Advances in Neural Information Processing Systems, volume 33, pages 15522–15533. Curran Associates, Inc., 2020. URL https://proceedings.neurips.cc/paper/2020/hash/ b2ea5e977c5fc1ccfa74171a9723dd61-Abstract.html. [26] Arnab Maiti, Zhiyuan Fan, Kevin Jamieson, Lillian J. Ratliff, and Gabriele Farina. Efficient near-optimal algorithm for online shortest paths in directed acyclic graphs with bandit feedback against adaptive adversaries. In Nika Haghtalab and Ankur Moitra, editors, Proceedings of the Thirty-Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pages 3881–3932. PMLR, 2025. URL https://proceedings.mlr.press/v291/maiti25a.html. [27] H. Brendan McMahan and Avrim Blum. Online geometric optimization in the bandit setting against an adaptive adversary. In Proceedings of the 17th Annual Conference on Learning Theory, volume 3120 of Lecture Notes in Computer Science, pages 109–123. Springer, 2004. doi: 10.1007/978-3-540-27819-1 8. URL https://doi.org/10.1007/978-3-540-27819-1_8. [28] Shinsaku Sakaue, Masakazu Ishihata, and Shin-ichi Minato. Efficient bandit combinatorial optimization algorithm with zero-suppressed binary decision diagrams. In Amos Storkey and Fernando Perez-Cruz, editors, Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pages 585–594. PMLR, 2018. URL https://proceedings.mlr.press/v84/sakaue18a.html. [29] Julian Zimmert and Tor Lattimore. Return of the bias: Almost minimax optimal high probability bounds for adversarial linear bandits. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of the Thirty-Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 3285–3312. PMLR, 2022. URL https://proceedings.mlr.press/v178/zimmert22b.html.

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

Analyze & explore related research in Conceptio

Related documents