An Efficient Minimax-Optimal Algorithm for Adversarial m-Set Bandits

The paper studies adversarial combinatorial bandits with m-set actions. At each round, the learner selects m out of d items and observes only the aggregate loss of the selected items, not the individual item losses. The action set contains K = C(d,m) elements, which can be exponentially large. The loss of every action is determined by the same d-dimensional vector of item losses.

The learner's goal is to minimize regret with respect to the best fixed m-set in hindsight. The adversary is adaptive non-anticipating, meaning the loss vector at round t may depend on the entire interaction history up to round t-1, but not on the learner's random draw at round t.

The paper proposes a computationally efficient algorithm that exploits the structure of m-set actions without explicitly enumerating the action set. The main result is:

Against adaptive non-anticipating adversaries, it guarantees, with probability at least 1 − δ, regret against the best fixed action of 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. The new algorithm instead represents each sampling distribution with d parameters and runs in polynomial time without enumerating the action set. This resolves the open problem posed by Maiti et al. [26].

The main obstacle is that the updates of EXP3-KW come with a quadratic correction (the leverage score x T M t-1 x), which does not preserve the weighted m-set structure. The paper overcomes this by:

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.

Specifically, the paper derives the affine upper bound (Lemma 4):

x T M-1 x ≤ φ p(x):= 1 + 2 Σ i=1 d (x i − μ i)2 / (μ i(1 − μ i))

This expression is affine on X because every x ∈ X satisfies x i2 = x i and Σ x i = m.

The affine leverage majorant can become arbitrarily large when marginal probabilities approach 0 or 1. The paper handles this by:

To obtain the uniform leverage bound needed in the analysis, we project the updates toward the set P λ introduced in Section 2.

The algorithm projects toward P λ (defined as distributions whose marginal probabilities stay away from 0 and 1), and the approximate projection returns a distribution in P λ/2.

Since the distribution δ x (putting all probability on x) does not belong to P λ, the paper uses:

qx:= (1 − λ)δ x + λU, where U is the uniform distribution over X. By construction, qx ∈ P λ.

Using qx in place of δ x adds at most 2λT to the regret.

The concentration bound for the estimation error introduces a positive term involving E[c t T X]. However:

Since c t 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.

Algorithm 1 (Affine KW–OMD with approximate entropic updates toward P λ):

1. Set learning rate η = min 1/(256d), √(log(12K/δ)/(320dT))

2. Set λ = 128ηd and ε p = η/T

3. Initialize θ 1 = 0 and p 1 = p θ 1 = U (uniform distribution)

4. At each round t:

• Compute moments μ t and M t of p t

• Set φ t and c t so that c t T x = 4φ t(x)

• Draw X t p t

• Observe Y t = ⟨X t, l t⟩

• Compute loss estimate l̂ t = M t-1 X t Y t

• Define surrogate loss Z t(x) = ⟨x, l̂ t⟩ − ηc t T x

• Update θ̃ t+1 = θ t − η(l̂ t − ηc t)

• Apply approximate KL projection to obtain p t+1 ∈ P λ/2

The main theorem (Theorem 1) states:

"There exists a universal constant C > 0 such that... with probability at least 1 − δ, RT ≤ C√(dT(log K + log(1/δ))), where K = C(d,m). One may take C = 160."

When m ≤ d/2, the bound becomes Õ(√(dmT)), matching the finite-action EXP3–KW rate.

The paper compares its results with existing algorithms:

Work Regret bound Computational complexity

---

Zimmert and Lattimore [29] Õ(√(dmT)) Exponential

Maiti et al. [26] (Appendix E.6) Õ(d√(mT)) Polynomial

Maiti et al. [26] (Theorem 7 applied) Õ(m√(dT)) Polynomial

This work Õ(√(dmT)) Polynomial

The improvement over Maiti et al. [26, Appendix E.6] is a factor of √d, and over the derived consequence of their Theorem 7 is a factor of √m.

The paper proves (Proposition 1) that Algorithm 1 can be implemented in T · poly(d, m, log T) time and poly(d, m) space without enumerating X. Key components:

1. Weighted m-set distributions: Represented by d parameters θ 1,..., θ d, with p θ(S) ∝ exp(Σ i∈S θ i).

2. Moment computation: Using elementary symmetric polynomial recurrences (Lemma 12), all marginals and pairwise marginals can be computed in O(d2m) operations.

3. Sampling: A conditional-Bernoulli procedure draws exact samples in O(dm) operations.

4. KL projection: The projection onto P λ reduces to a convex problem in 2d variables (Lemma 10), solved to inverse-polynomial accuracy using the ellipsoid method (Lemma 11).

The paper discusses the regret lower bound in the regime m ≤ d/2. From Ito et al. [19, Theorem 2], after action-normalization, the lower bound is Ω(√(dmT)) when m ≤ d/2 and T ≥ dm 3/2. Setting δ = T-2 in the high-probability guarantee yields expected regret Õ(√(dmT)), matching the minimax lower bound up to logarithmic factors.

The paper leaves two main questions open:

1. 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. This issue is noted as open even for ordinary adversarial multi-armed bandits (m = 1).

2. Whether the approach extends beyond m-sets to more general matroid-base action sets. The paper notes that affine exponential-weights updates still preserve weighted matroid-base distributions, but the analysis requires additional structural and computational ideas that do not follow from our present covariance-based construction.

Improvement 1: Polynomial-Time Structured Action-Space Optimization

The AI system can now handle exponentially large combinatorial action spaces (e.g., selecting m items from d) without enumeration, using a compact d-parameter representation. It computes sampling distributions, moments, and projections in O(d2m) time per round, enabling real-time decision-making in high-dimensional settings (e.g., d=106, m=103) where prior exponential-space methods fail. This directly improves AI systems for online resource allocation, portfolio selection, or feature subset selection where the action space is combinatorial.

Improvement 2: High-Probability Regret Guarantees Under Adaptive Adversaries

The AI system achieves O(√(dT log(K/δ))) regret with probability ≥ 1−δ against adaptive non-anticipating adversaries, matching the theoretical optimum for finite-action bandits. This allows AI systems to provide robust performance guarantees in non-stationary environments (e.g., dynamic pricing, ad placement) where the environment adapts to past decisions, ensuring reliable worst-case behavior rather than just average-case performance.

Improvement 3: Affine Majorant for Quadratic Surrogate Losses

The system leverages a novel affine upper bound (xTM−1x ≤ 1 + 2Σ(xi−μi)2/(μi(1−μi))) to replace costly quadratic corrections with linear computations. This enables AI systems to maintain exponential-weight updates in structured domains without violating the action-space geometry, improving computational efficiency in online learning with dependent actions (e.g., recommending bundles of items where item interactions matter).

Improvement 4: Safe Exploration via Projection onto Bounded-Marginal Sets

The algorithm projects updates onto P λ (marginals bounded away from 0 and 1), preventing degenerate distributions and ensuring uniform leverage bounds. This makes AI systems more stable in practice—avoiding extreme exploration/exploitation swings—and enables safe deployment in high-stakes applications (e.g., clinical trial design, autonomous navigation) where overly confident or overly random actions are risky.

Improvement 5: Smoothed Comparator for Regret Analysis

By comparing against qx = (1−λ)δx + λU instead of δx, the system tolerates a small λT regret penalty while gaining analytical tractability. This allows AI systems to provide near-optimal performance guarantees even when the best fixed action is not in the feasible set, improving robustness in misspecified or constrained real-world problems (e.g., fairness constraints in recommendation systems).

Improved AI System Capabilities:

• Real-time combinatorial bandit learning with polynomial time/space complexity, enabling deployment in IoT, robotics, or cloud computing where action spaces are massive.

• Provable robustness to adaptive adversaries, making it suitable for security-sensitive applications (e.g., fraud detection, cyber defense) where attackers learn from system responses.

• Scalable multi-item selection with near-optimal regret (O(√(dmT))), improving AI systems for online advertising (choosing ad sets), logistics (selecting routes), or genomics (picking gene subsets).

• Theoretical guarantees at constant confidence, allowing AI systems to certify performance with high probability, which is critical for regulatory compliance in finance or healthcare.