Anytime Exploration for Multi-armed Bandits using Confidence Information

Area of Science:

• Machine Learning
• Artificial Intelligence
• Optimization

Background:

• Multi-armed bandit (MAB) problems are crucial for sequential decision-making under uncertainty.
• Existing top-m arm identification in MAB often relies on fixed budgets or confidence levels, limiting practical application.
• Many real-world scenarios involve finite, unpredictable resource constraints, necessitating adaptive algorithms.

Purpose of the Study:

• To introduce the anytime Explore-m problem, a more practical formulation for identifying top-m arms in MAB.
• To develop and analyze the first nontrivial algorithm, AT-LUCB (AnyTime Lower and Upper Confidence Bound), capable of solving the anytime Explore-m problem.
• To evaluate the performance and sample complexity of AT-LUCB against existing methods.

Main Methods:

• Formulation of the anytime Explore-m problem, emphasizing prediction at every time step.
• Development of the AT-LUCB algorithm, a novel approach based on lower and upper confidence bounds.
• Theoretical analysis of AT-LUCB's sample complexity.
• Empirical evaluation comparing AT-LUCB with state-of-the-art baseline algorithms.

Main Results:

• AT-LUCB is presented as the first provably correct algorithm for the anytime Explore-m problem.
• The sample complexity of AT-LUCB is shown to be competitive with anytime variants of existing MAB algorithms.
• Empirical results demonstrate that AT-LUCB performs comparably to or better than current state-of-the-art methods.

Conclusions:

• The anytime Explore-m problem offers a more practical approach to top-m arm identification in MAB settings with unpredictable budgets.
• AT-LUCB is a significant advancement, providing a theoretically sound and empirically effective solution.
• AT-LUCB demonstrates strong performance, making it a valuable tool for applications requiring continuous top-m arm identification.