What type of study is this?

September 10, 2025Open Access

Comparison of Regret in Ucb Algorithms and Thompson Sampling Under Different Reward Distributions

Key Points

Thompson Sampling achieved a cumulative regret of approximately 16, while UCB exceeded 70, showing superior performance.
In scenarios with skewed or high-variance reward distributions, TS consistently outperforms UCB.
Evaluations were conducted using Bernoulli, Gaussian mixture model, and Beta distributions over different scales.
UCB remains valuable when the reward gap is small or the environment changes rapidly, emphasizing its practical relevance.

Abstract

The Multi-Armed Bandit (MAB) problem is a classic framework for solving the trade-off between exploration and exploitation, which is widely used in fields such as online advertising, recommendation systems, and A/B testing. This study systematically compares the performance of the Upper Confidence Bound (UCB) and Thompson Sampling (TS) algorithms under different reward distributions. Based on the MovieLens dataset, three typical reward environments, namely Bernoulli, Gaussian mixture model (GMM), and Beta distributions, are constructed. The convergence and stability of the algorithms under different scales (large and small rounds) are evaluated using two indicators: cumulative regret and regret growth rate. The experimental results show that the TS algorithm is significantly better than the UCB algorithm in most environments, especially when the reward distribution is skewed, high variance, or irregular. In the Beta setting with 5000 rounds, TS achieves a cumulative regret of approximately 16, compared to over 70 for UCB, which is about a 75% reduction. TS also shows stronger adaptability and faster convergence speed. At the same time, the UCB algorithm still has essential practical value when the reward gap is small, the environment changes rapidly, or the prior is unknown.

Read Full Paperexternally

Mark Helpful

Bookmark

Relay

View Full Paper