TL;DR
This paper introduces near-optimal algorithms for pure-exploration linear and combinatorial bandits by leveraging the theory of empirical processes. By replacing standard, loose union bounds with an experimental design objective based on Gaussian width, the proposed algorithms significantly reduce sample complexity and remain computationally efficient even when the candidate item set is exponentially large.
What Problem Does This Paper Address?
In the pure-exploration transductive linear bandit problem, an agent sequentially chooses measurement vectors from a set $\mathcal{X}$ to identify the best candidate item from a set $\mathcal{Z}$ based on noisy linear observations. This framework generalizes many important problems, including top-$K$ arm identification, shortest-path routing, and matching problems.
A major bottleneck in existing algorithms is their reliance on a naive union bound over all candidate items. This introduces a multiplicative $\log(|\mathcal{Z}|)$ factor into the sample complexity. While seemingly small, $|\mathcal{Z}|$ can be exponentially large in practical combinatorial problems (e.g., the number of perfect matchings in a graph). This paper aims to eliminate this loose $\log(|\mathcal{Z}|)$ penalty by exploiting the underlying geometric correlations between arms.
Methods
Instead of minimizing worst-case variance (such as traditional G-optimal design), the authors leverage the Tsirelson-Ibramov-Sudakov (TIS) inequality from Gaussian process theory. This allows them to bound the deviations of the estimator using the Gaussian width of the arm set, capturing how candidate items are geometrically correlated.
The authors introduce two primary algorithms:
- PEACE (Pure Exploration via Empirical Process Approach to Geometric Experimental Design): Designed for the fixed-confidence setting, it sequentially eliminates suboptimal arms.
- FBPeace: The first algorithm for linear bandits in the fixed-budget setting.
For combinatorial settings where $|\mathcal{Z}|$ is exponentially large, explicitly enumerating the items is impossible. To solve this, the authors develop a computationally efficient variant of PEACE (Algorithm 2) that avoids enumeration by interacting with the item set solely through a linear maximization oracle (e.g., standard shortest-path or matching algorithms). They reformulate the optimization step into a linear program that can be solved efficiently using binary search and oracle calls.
Datasets
The algorithms were evaluated on several synthetically constructed structured bandit problems:
- Matching: Finding the best perfect matching in a balanced complete bipartite graph ($|\mathcal{Z}| = 14! \approx 8.7 \times 10^{10}$).
- Shortest Path: Finding the optimal path through a layered directed acyclic graph (DAG) ($|\mathcal{Z}| \ge 10^8$).
- Multivariate Testing: Optimizing a multi-variable layout with linear and quadratic interaction terms.
- Linear Bandits: A synthetic problem in $\mathbb{R}^2$ designed to show performance as $|\mathcal{Z}|$ scales up to $10^6$.
- Biclique: A small NP-hard combinatorial problem evaluated in the appendix.
Key Insights and Ideas
- Geometry Over Enumeration: Standard union bounds treat all arms as independent entities. By using Gaussian width, the algorithm inherently understands that if two candidate vectors point in nearly the same direction, learning about one teaches you about the other.
- Oracle-Based Tractability: The paper demonstrates that even if an objective function involves an expectation over an exponential number of constraints, it can be optimized efficiently if a linear maximization oracle exists for the underlying structure.
- Convexity via Monotonic Transformation: The authors prove that after a square-root transformation, the Gaussian-width-based objective function becomes convex in the combinatorial setting, enabling the use of stochastic mirror descent.
Key Results
- Immunity to Arm Set Size: In the linear bandits experiment, as the number of candidate arms $|\mathcal{Z}|$ scaled from $10^3$ to $10^6$, the sample complexity of PEACE remained entirely constant. In contrast, the state-of-the-art baseline (RAGE) saw its sample complexity grow linearly with $\log(|\mathcal{Z}|)$.
- Order-of-Magnitude Speedups: In the matching and shortest-path experiments, PEACE outperformed standard baselines like CLUCB and Uniform Allocation by up to an order of magnitude, especially as the suboptimality gap ($h$) became smaller.
Limitations and Future Work
- Statistical vs. Computational Tradeoff: The computationally efficient oracle-based version of PEACE introduces a slight statistical penalty—its sample complexity scales with an additive factor of the dimension $d$ compared to the fully optimal, non-computational baseline. It remains an open question whether this tradeoff is mathematically necessary.
- General Convexity Conjecture: While the authors proved that the objective function is convex for combinatorial bandits (where measurement vectors are canonical basis vectors), they only conjecture its convexity for general linear bandit settings.
Summary updated