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

School of Management Science and Engineering, Southwestern University of Finance and Economics, Sichuan, 611130, China

42219036@smail.swufe.edu.cn

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.