Improved Learning Complexity in Combinatorial Pure Exploration Bandits.

Victor Gabillon, Alessandro Lazaric, Mohammad Ghavamzadeh, Ronald Ortner, Peter L. Bartlett

Introduction

In the Multi-Armed Bandit (MAB) framework, the "Pure Exploration" objective focuses on identifying the optimal arm or set of arms with maximum accuracy or minimum samples, rather than maximizing cumulative reward. Combinatorial Pure Exploration (CPE) extends this to scenarios where the learner must identify an optimal set of arms—such as the shortest path in a network or the best subset of features—subject to combinatorial constraints.

Identifying the optimal set is challenging because the number of possible combinations often grows exponentially with the number of arms $K$. Previous research characterized the difficulty of CPE using a "global width" measure. However, this paper demonstrates that such global measures are often overly pessimistic, failing to account for the local geometry of the decision space.

A Refined Complexity Measure: The Complement Set

The primary contribution of this work is a new complexity measure, $H$, which is significantly tighter than previous state-of-the-art measures (like $H^\odot$). The key insight lies in how we prove a decision set $U$ is suboptimal. Traditionally, $U$ was compared to the global optimum $U^*$. The authors argue that one only needs to find any set $V$ that is better than $U$ ($\mu_V > \mu_U$) to discard $U$.

For every suboptimal set $U$, the authors define a "complement" set $C_U$—the set that is easiest to distinguish from $U$ based on their expected rewards and shared arms. By focusing on these local comparisons, the learner can identify and eliminate bad options much faster. The authors prove that $H$ is never larger than $H^\odot$ and can be smaller by a factor of up to $K^2$.

Graph Examples 1 and 2 illustrating the local geometry of decision spaces where the new complexity measure H provides tighter bounds.

Algorithms and Sample Complexity

The paper introduces two algorithms designed to exploit this refined complexity:

  1. Fixed Budget Algorithm: A successive rejection approach that estimates the "simplicity" of arms and progressively deactivates those that are easiest to categorize until only the best set remains.
  2. Fixed Confidence Algorithm: An elimination algorithm that maintains a set of active candidates. It uses confidence intervals to identify the most uncertain arms within the "simplest" pairs of sets and samples them preferentially.

The fixed confidence algorithm achieves a sample complexity of $\tilde{O}(H \log(1/\delta))$, directly linking performance to the new, tighter complexity measure.

Structural Efficiency and Practical Application

While calculating the complement set for general combinatorial structures can be computationally expensive ($O(|\mathcal{C}|^2)$), the authors identify several important classes where the complexity is manageable. For structures like multi-bandits or tree-based planning, the computational cost can be reduced to $O(K)$ or $O(Km)$.

Specific combinatorial structures, such as the 2-arm 3-bandit problem and tree-based planning, where the proposed algorithms achieve high computational efficiency.

In tree-structured decision spaces, which represent open-loop planning problems, the goal is to find the best path from root to leaf. The proposed algorithms can navigate these spaces efficiently by focusing on the local differences between branching paths.

Conclusion

By shifting the focus from global optimality to local distinguishability, this research provides a more nuanced understanding of the complexity of combinatorial pure exploration. The resulting algorithms offer significant theoretical and practical improvements, particularly in structured domains like network routing and planning, where they can outperform previous methods by a factor of $K^2$. Future work may explore closing the remaining gap between these upper bounds and theoretical lower bounds using asymmetric distance measures.

Summary updated

Abstract

We study the problem of combinatorial pure exploration in the stochastic multi-armed bandit problem. We first construct a new measure of complexity that provably characterizes the learning performa...
BibTeX
@inproceedings{gabillon2016improved,
  author = {Victor Gabillon and Alessandro Lazaric and Mohammad Ghavamzadeh and Ronald Ortner and Peter L. Bartlett},
  title = {{Improved Learning Complexity in Combinatorial Pure Exploration Bandits.}},
  booktitle = {AISTATS},
  year = {2016},
  url = {https://openreview.net/forum?id=7riGkV-wimO5},
}

Loading related content...

Figure