Efficient Swap Regret Minimization in Combinatorial Bandits

AI summary

Overview

Research area: Online learning and bandit theory, specifically adversarial combinatorial bandits and the design of no-swap-regret algorithms.

Technical level: Advanced. The paper builds on swap-to-external-regret reductions, online mirror descent, barycentric spanners, and Carathéodory decomposition; readers need familiarity with bandit regret analysis.

Scope: This paper introduces a no-swap-regret algorithm for combinatorial bandits whose swap regret and per-iteration complexity both depend polylogarithmically on the exponentially large action space.

What This Paper Is About

In a combinatorial bandit, a learner repeatedly picks a combination of up to m elements from a ground set of d elements, out of roughly N = O(d^m) possible combinations, and only observes the combined reward of the chosen set. Prior work has largely focused on the weaker notion of external regret (comparison against the single best fixed combination in hindsight), leaving open whether the stronger swap regret (comparison against the best fixed swap function applied to the learner's own policy) could be minimized with polylogarithmic dependence on N. This paper answers that question affirmatively, giving an algorithm whose swap regret and per-iteration running time both scale polylogarithmically in N when the combinatorial structure is exploited.

Key Contributions

1. First polylogarithmic-in-N no-swap-regret algorithm for combinatorial bandits. The proposed algorithm achieves swap regret O(T log(d log T) / log T), which contains no polynomial dependence on the action count N = O(d^m).

2. A tightness statement in the practical regime. By applying the lower bound of Daskalakis et al. (2024) (Theorem 4.1 there, invoked here via Corollary 4.3), the authors show that in the regime T = poly(d, m) there is no T^p-no-swap-regret scheme (for constant p < 1) with polylogarithmic dependence on d^m. That lower bound is Ω(T / log^6 T) and holds for m ≥ d^{12/13}, T ≤ exp(Ω(d^{1/14})).

3. An efficiently implementable instantiation. The framework is realized through Lazy-ComBCP (Algorithm 2), which uses 2-approximate barycentric spanners, Carathéodory decomposition, and KL projection, and runs in time poly(d, m) or poly(m, d, log T) per iteration. The authors state it applies to online shortest paths, m-sets, spanning trees, and permutations.

4. A swap-to-external-regret decomposition under bandit feedback. Lemma 3.2 decomposes the master learner's swap regret into a sum of external regrets of the individual ScaleLearners plus a T/K term, extending the full-information reduction of Dagan et al. (2024) and Peng and Rubinstein (2024) to the partial-information setting.

Main Findings

• Main upper bound: There exists a combinatorial bandit algorithm with swap regret at most O(T log(d log T) / log T) (abridged Theorem; formally Theorem 4.1).

• Practical-regime advantage: The paper's Table 1 states that only this work's swap regret upper bound "remains meaningful in the realistic regime where T = poly(d, m)."

• Comparison with prior bounds: Stoltz (2005) gives O(d^m sqrt(mT log d)) swap regret with per-iteration complexity exp(d^m); Blum and Mansour (2007) give O(d^m sqrt(m d^m T log d)) with poly(d^m) complexity; Ito (2020) gives O(d^m sqrt(T)) with poly(d^m) complexity; Dagan et al. (2024) give O(T log(m log T) / log(T/d^m) + sqrt(d^m T log(d^m T))) with poly(d^m, log T) per-iteration complexity — but the authors note that approach has O(N) per-iteration complexity and uses a stronger swap-regret notion with the max operator inside the expectation.

• External regret of the sub-learner: Theorem 3.9 bounds the external regret of Lazy-ComBCP_{k,l} by 3 H^{k-1} H^{2/3} d^3 m^{3/2} log d, which is no-regret because H^{k-1} is the maximum reward per meta-day of that learner.

• Minimum eigenvalue guarantee: Lemma 3.5 shows that under the barycentric spanner exploration policy μ, the minimum eigenvalue of the co-occurrence matrix satisfies λ_min(μ) ≥ 1/(4d^3), which is used to control estimator variance.

• Estimator properties: Lemma 3.8 establishes that the aggregated reward estimate is unbiased with respect to the master's policy, E[q_h · X̃_h] = E[q_h · X_h], and bounded, with ‖X̃_h‖_2 ≤ 4 H^{k-1} d^3 sqrt(m) / γ.

• Variance analysis differs from standard practice: The authors report that bounding the variance requires controlling E[M_τ^T Σ_τ^{+2} M_τ] rather than the usual E[M_τ^T Σ_τ^+ M_τ]; Lemma 3.13 gives E[M_τ^T Σ_τ^{+2} M_τ] ≤ d λ_min^{-1}(Σ_τ), and Lemma 3.14 bounds the variance term by 4 H^{2k-2} d^4 / γ.

• Anytime guarantees: The paper states (Lemma 4.2) that a regret upper bound of O(T log(d log T) / log T) can yield anytime guarantees for any online learning algorithm achieving that bound, including the proposed algorithms.

Methodology in Plain English

The central difficulty is that swap regret is hard to control when the learner's policy changes over time, because a swap function can exploit that variability. The authors exploit a simple observation (Proposition 3.1): if the policy stays fixed over an interval, swap deviations cannot beat the best fixed action, so swap regret is bounded by external regret.

They therefore build an ensemble of "lazy" learners. A master learner plays a uniform mixture over K ScaleLearners (Algorithm 1), where ScaleLearner k freezes its policy for H^{k-1} days between updates and restarts every H^k days, with T in [H^{K-1}, H^K]. Mixing multiple scales of laziness balances stability against adaptivity, and lets the swap regret be decomposed into a sum of external regrets (Lemma 3.2) plus a T/K slack term.

The twist for bandits is that the master only sees the reward of the action it actually played. The master forms an unbiased reward estimate using the pseudo-inverse of its own co-occurrence matrix, r_t (E_{p̂_t}[MM^T])^+ M_t, and broadcasts that estimate to all ScaleLearners. This estimate is unbiased with respect to the master's policy but biased with respect to any individual ScaleLearner's policy, which is what makes the analysis non-standard and forces the Σ^{+2} variance term rather than Σ^+.

Each ScaleLearner is instantiated as Lazy-ComBCP (Algorithm 2), which works in the d-dimensional coordinate space, uses a 2-approximate barycentric spanner for exploration, decomposes m·q into a small-support distribution over at most d actions via Carathéodory decomposition, mixes with the exploration policy μ, and updates via exponentiated gradients followed by KL projection onto the scaled convex hull of the action set. The small support keeps sampling efficient.

Why This Matters

Impact on research. The paper resolves a question highlighted as open in Blum and Mansour (2007): whether efficient no-swap-regret learning is possible when the number of actions is exponentially large. It shows that the extra combinatorial structure is what enables polylogarithmic dependence on N, whereas unstructured bandits have lower bounds (e.g., the external-regret lower bound of Auer et al. (2002a)) that preclude such dependence. It also extends the full-information swap-to-external reductions of Dagan et al. (2024) and Peng and Rubinstein (2024) to the bandit setting.

Real-world applications. The paper's motivation section cites combinatorial bandit models applied to:

• Path planning and online shortest paths.
• Resource allocation.
• Recommender systems.
• The efficient implementations are stated to cover online shortest paths, m-sets, spanning trees, and permutations.

Industry relevance. Swap regret is directly connected to game-theoretic rationality and multi-agent learning: no-external-regret learning is not rationalizable because of examples (Viossat and Zapechelnyuk, 2013) where every player plays a strictly dominated strategy at all times, whereas no-swap-regret learning avoids this. That makes the result relevant to equilibrium computation, multi-agent reinforcement learning, and any repeated decision system where reactivity to changing conditions matters. The paper itself does not report specific industrial deployments or empirical experiments.

Future Directions

• Closing the gap between the upper bound and the lower bound. The paper's swap regret O(T log(d log T) / log T) is matched against a lower bound of Ω(T / log^6 T) valid for T ≤ exp(Ω(d^{1/14})) and m ≥ d^{12/13}; tightening these logarithmic factors and the parameter regime is a natural next step.

• Extending beyond binary combinatorial actions. Algorithm 2 assumes ‖M‖_1 = m for every action in the set; the paper indicates the more general case ‖M‖_1 ≤ m is discussed in Section 4.2, leaving broader action families to explore.

• Adaptivity to unknown structure. The framework requires choosing K and H with T ∈ [H^{K-1}, H^K] and a 2-approximate barycentric spanner of the action set; making the method robust when such structure is unknown or only approximately available is an open direction.

• Empirical validation. The paper presents theory and complexity statements but the provided content reports no experiments, so evaluating Swap-ComBCP against prior algorithms in practice remains open.

Target Audience

Researchers and graduate students in online learning, bandit theory, and algorithmic game theory who are already comfortable with regret analysis and convex optimization. It is most valuable to those working on the theory of swap regret, equilibrium learning in multi-agent systems, and structured large-action-space decision problems such as routing and combinatorial allocation. Practitioners interested in applying no-swap-regret methods to combinatorial optimization would need substantial mathematical background to benefit fully.

Authors’ abstract

This paper addresses the problem of designing efficient no-swap regret algorithms for combinatorial bandits, where the number of actions $N$ is exponentially large in the dimensionality of the problem. In this setting, designing efficient no-swap regret translates to sublinear -- in horizon $T$ -- swap regret with polylogarithmic dependence on $N$. In contrast to the weaker notion of external regret minimization - a problem which is fairly well understood in the literature - achieving no-swap regret with a polylogarithmic dependence on $N$ has remained elusive in combinatorial bandits. Our paper resolves this challenge, by introducing a no-swap-regret learning algorithm with regret that scales polylogarithmically in $N$ and is tight for the class of combinatorial bandits. To ground our results, we also demonstrate how to implement the proposed algorithm efficiently -- that is, with a per-iteration complexity that also scales polylogarithmically in $N$ -- across a wide range of well-studied applications.