A Comparative Analysis of Cumulative Regret Based on Multi-Armed Bandit Algorithms

Abstract

This study aims to conduct a detailed comparison of the performance of three classic Multi-Armed Bandit algorithms: Thompson Sampling, UCB, and ETC. The MAB problem, as an important sequential decision-making framework, primarily challenges lie in how to strike a balance between "exploration" and "exploitation". We quantitatively analyzed each algorithm's long-term performance using 100 independent experiments and cumulative regret as the primary metric. The experimental findings demonstrate that the three algorithms' performance varies significantly in the tested context. The Thompson sampling method performed the best, with the least increase in regret and the lowest final value. The UCB algorithm performed second-best, with regret growing logarithmically. The ETC algorithm saw rapid accumulation of regret in the early stages before stabilizing, but it had the poorest performance because it lacked the ability for continuous exploration. These findings confirm that the Thompson sampling method is the most efficient in balancing exploration and exploitation, and is the best choice for solving such Random Stationary Multi-Armed Bandit Problem.