Polynomial-Time Algorithms for Multiple-Arm Identification with Full-Bandit Feedback.

Area of Science:

• Machine Learning
• Reinforcement Learning
• Optimization

Background:

• Stochastic multiple-arm identification involves selecting the best subset of arms (super arm) from a larger set.
• Existing methods often rely on the semi-bandit setting, which is not always feasible due to costly individual arm observations.
• The full-bandit setting, where only a noisy sum of rewards is observed, presents unique challenges.

Purpose of the Study:

• To develop an efficient algorithm for the full-bandit setting of stochastic multiple-arm identification.
• To address the computational infeasibility of naive linear bandit approaches when the number of super arms is exponential.
• To achieve an exponential speedup in computation time while maintaining worst-case optimal sample complexity.

Main Methods:

• Designed a polynomial-time approximation algorithm for a 0-1 quadratic programming problem related to confidence ellipsoid maximization.
• Proposed a novel bandit algorithm leveraging the approximation algorithm for efficient computation.
• Derived a sample complexity upper bound for the proposed algorithm.

Main Results:

• The proposed bandit algorithm achieves a computation time of O(log N), offering an exponential speedup over linear bandit algorithms.
• The algorithm's sample complexity is proven to be worst-case optimal.
• Experiments on large-scale datasets (>10^6 super arms) demonstrate superior performance in computation time and sample complexity.

Conclusions:

• The developed algorithm efficiently solves the stochastic multiple-arm identification problem in the full-bandit setting.
• This work provides a computationally feasible and sample-efficient solution for real-world applications with complex arm structures.
• The findings significantly advance the state-of-the-art in bandit algorithms for large-scale identification tasks.