Decomposing and Optimizing Regret in Classical Multi-Armed Bandit Algorithms: ETC, UCB, and Thompson Sampling

Brunel London School, North China University of Technology, Beijing, China

^* Corresponding author: This email address is being protected from spambots. You need JavaScript enabled to view it.

Abstract

Define and decompose the regret values of three classic algorithms, Explore-then-commit, Upper confidence bounds, and Thompson Sampling. First determine which part of the algorithm, function or equation yield the regret, then decompose the regret to find the source of the regret, usually into two parts: exploration phase and exploitation phase. For Explore-then-commit, the regret comes from fixed trial rounds in exploration phase; for UCB, the regret comes from running trial rounds to separate optimal arm from sub-optimal arms; for Thompson Sampling, the regret comes from the differences between posterior distribution and actual distribution. Later optimize the corresponding part of the function or equation to reduce the regret from different types of the total decomposed regret. Python coding will be used to construct original algorithm and optimized algorithm, including plotting the image of the cumulative regret of each algorithm. The effectiveness of the optimized algorithm will be verified through the comparison of original and optimized cumulative regret image.