Introduction
In the traditional Multi-Armed Bandit (MAB) problem, a learner interacts with a set of options (arms) to maximize rewards or identify the best-performing choice. While standard models often assume rewards are drawn from fixed probability distributions, real-world applications—such as algorithm configuration and human preference modeling—frequently involve non-stochastic rewards and complex interactions between choices.
This research, conducted by scholars at Paderborn University and LMU Munich, introduces a robust framework for Best Arm Identification (BAI) in combinatorial bandits. The study addresses scenarios where feedback is subset-dependent, rewards are non-stochastic, and the learner operates under a strictly finite budget.
The Problem: Beyond Stochastic Independence
Classic MAB models typically assume that an arm's performance is independent of other arms. However, this paper tackles four specific complexities that better reflect practical environments:
- Combinatorial/Semi-bandit Feedback: Instead of pulling a single arm, the learner selects a subset (size $k$) and observes the performance of each individual arm within that specific context.
- Non-stochastic/Adversarial Rewards: Rewards do not necessarily follow a stationary distribution. They may be chosen by an oblivious adversary or evolve over time, requiring the algorithm to be robust against non-random fluctuations.
- Subset-Dependent Feedback: The performance of an arm may change depending on the other arms in its subset. This captures "context effects," such as how a user might rank a product differently depending on the competing products displayed alongside it.
- Fixed Budget: The learner is constrained by a total number of queries $B$, necessitating an efficient elimination strategy to identify the optimal arm before resources are exhausted.
The primary goal is to identify the Generalized Condorcet Winner (GCW)—the arm that consistently outperforms others within any subset it belongs to—rather than the traditional Borda winner (the arm with the highest average performance).
The Combinatorial Successive Elimination (CSE) Framework
To solve this, the authors propose the Combinatorial Successive Elimination (CSE) algorithm. The framework operates in rounds, partitioning active arms into sets of size $k$, querying them, and applying an elimination function $f$ to prune the search space. The paper analyzes three distinct strategies within this framework:
- Combinatorial Winner Stays (CSWS): An aggressive strategy where only the top-performing arm in each subset advances.
- Combinatorial Successive Reject (CSR): A conservative approach that eliminates only the single worst-performing arm from each subset.
- Combinatorial Successive Halving (CSH): A balanced strategy that discards the bottom 50% of arms in each subset.
A key innovation of CSE is the abstraction of feedback into a general "statistic" $s$. This allows the framework to handle both numerical rewards (e.g., execution time) and preference-based feedback (e.g., pairwise rankings) interchangeably.
Theoretical and Empirical Results
Theoretical Bounds
The researchers derived the first lower bounds for the budget required in non-stochastic combinatorial settings. They demonstrated that the sufficient budget for CSE algorithms is approximately $\tilde{O}(n/k)$, where $n$ is the number of arms and $k$ is the subset size. This matches the theoretical "speed limit" for this problem class, proving the efficiency of the proposed approach.
Empirical Performance
The framework was evaluated using both synthetic data and a real-world algorithm selection task:
- Synthetic Benchmarks: Using multivariate Gaussian distributions, the authors simulated environments where Borda and Condorcet winners diverged. The CSE variants proved capable of identifying the GCW even when average-based metrics failed.
- Algorithm Selection (SAPS): The authors applied their methods to the SAPS solver (a stochastic local search solver for SAT problems). Using a dataset of 20 parameterizations across 5,000 problem instances, they tested which parameterization could solve problems fastest in parallel. Combinatorial Successive Halving (CSH) significantly outperformed standard Successive Halving and Round Robin baselines, demonstrating high robustness across various budgets.
Discussion and Future Directions
The paper establishes that the Condorcet winner is a more natural and robust target for subset-dependent bandit problems than the Borda winner. By unifying numerical and preference-based feedback under a single framework, the authors provide a versatile tool for complex optimization tasks.
However, the study notes certain limitations. The guarantees rely on the existence of a GCW; in scenarios with cyclic preferences (like rock-paper-scissors), the definition of "best" remains an open question. Future work may explore "switching" strategies that transition from conservative to aggressive elimination, as well as extending the framework from identifying the single best arm to identifying the optimal subset of arms.
Summary updated