An Online Minimax Optimal Algorithm for Adversarial Multiarmed Bandit Problem

Area of Science:

• Machine Learning
• Reinforcement Learning
• Online Algorithms

Background:

• The adversarial multiarmed bandit problem presents a significant challenge in online decision-making.
• Existing algorithms often require knowledge of game length or strategy switches, limiting their applicability.
• Developing truly online algorithms with strong performance guarantees is crucial for real-world applications.

Purpose of the Study:

• To introduce a novel online algorithm for the adversarial multiarmed bandit problem.
• To achieve asymptotically optimal performance compared to the best switching bandit arm selection strategy.
• To provide algorithms with performance guarantees independent of statistical assumptions on arm losses.

Main Methods:

• Development of a truly online algorithm for the adversarial multiarmed bandit problem.
• Theoretical analysis to establish individual sequence performance guarantees without statistical assumptions.
• Derivation of minimax optimal regret bounds up to logarithmic terms.
• Achieving log-linear computational complexity with respect to game length.

Main Results:

• The proposed algorithm asymptotically matches the performance of the best switching bandit strategy.
• Regret bounds are minimax optimal, holding in an individual sequence manner.
• Computational complexity is log-linear, enabling efficient application to big data.
• Experimental results show significant performance improvements over state-of-the-art algorithms.

Conclusions:

• The developed online algorithm offers a powerful solution for the adversarial multiarmed bandit problem.
• The algorithm's efficiency and strong theoretical guarantees make it suitable for big data scenarios.
• A general, implementable framework for bandit arm selection is introduced, adaptable to various applications.