Thompson Sampling for Non-Stationary Bandit Problems.

Area of Science:

• Machine Learning
• Artificial Intelligence
• Optimization

Background:

• Non-stationary multi-armed bandit (MAB) problems, characterized by changing reward distributions, are increasingly important.
• Abruptly changing environments, where distributions shift at unknown time steps, present unique challenges.
• Existing Thompson sampling (TS) methods lack regret bound analysis for uninformative priors in these non-stationary settings.

Purpose of the Study:

• To develop and analyze algorithms for MAB problems with abruptly changing reward distributions.
• To provide theoretical regret bounds for TS-based approaches in such dynamic environments.
• To evaluate the empirical performance of the proposed algorithms against existing methods.

Main Methods:

• Proposed two novel algorithms: discounted Thompson sampling (TS) and sliding-window TS.
• Designed algorithms specifically for sub-Gaussian reward distributions.
• Established an upper bound for expected regret by analyzing the frequency of suboptimal arm plays.

Main Results:

• Derived an expected regret upper bound of O~(TBT) for both discounted TS and sliding-window TS, where T is the time horizon and BT is the number of breakpoints.
• Demonstrated that this upper bound closely matches the established lower bound for abruptly changing MAB problems.
• Empirical evaluations showed competitive performance compared to other non-stationary bandit algorithms.

Conclusions:

• Discounted TS and sliding-window TS offer effective solutions for abruptly changing MAB problems.
• The theoretical regret bounds provide valuable insights into the performance of these algorithms.
• The proposed methods represent a significant advancement in handling dynamic bandit environments.