A Thompson Sampling Algorithm With Logarithmic Regret for Unimodal Gaussian Bandit.

Area of Science:

• Machine Learning
• Optimization Algorithms
• Statistical Inference

Background:

• Multi-armed bandit (MAB) problems involve sequential decision-making under uncertainty.
• Unimodal MAB (U-MAB) settings assume a specific structure in expected rewards, allowing for more efficient exploration.
• Existing algorithms may not fully exploit the unimodal structure for optimal performance.

Purpose of the Study:

• To propose a Thompson sampling algorithm tailored for unimodal bandit problems with Gaussian rewards.
• To enhance decision-making by focusing exploration on promising arm neighborhoods.
• To theoretically and empirically validate the algorithm's performance and regret bounds.

Main Methods:

• Development of a Thompson sampling algorithm utilizing a Gaussian prior.
• Implementation of a neighborhood-based exploration strategy guided by posterior distributions and empirical means.
• Theoretical analysis to derive asymptotic regret bounds.
• Empirical evaluation on synthetic and real-world datasets.

Main Results:

• The proposed algorithm achieves an asymptotic regret of O(logT).
• This regret bound is asymptotically optimal and comparable to existing state-of-the-art U-MAB algorithms.
• Experimental results demonstrate the algorithm's effectiveness and efficiency.

Conclusions:

• The novel Thompson sampling algorithm effectively leverages the unimodal reward structure.
• The neighborhood-based exploration strategy significantly improves decision-making efficiency.
• The algorithm offers a competitive and effective solution for unimodal multi-armed bandit problems.