Multi-Armed Bandits and Their Classical Algorithms: Strengths and Limitations

Multi-armed Bandits (MAB), which is the short form for multi- armed bandit, is playing a significant role in varied spaces including online advertising, recommendation system, clinical trials and medical decision- making and even in 5G. The model aims to balance “choosing the option with the highest reward known so far” and “exploring the options unknown”. At last, it will reflect the results by a coefficient called regret. It is sometimes not suitable to some special situations. This article shows three of its classical algorithms: Explore Then Commit (ETC), Upper Confidence Bound (UCB) and Thompson Sampling (TS). ETC separates exploitation and commitments into two single parts but it will produce more regrets comparing to the other two algorithms. UCB selects arms based on the “average reward + upper confidence bound” metrics. It is one of the most popular algorithms. TS models uncertainty by leveraging Bayesian updates and random sampling. However, it is much harder than the others. They have different advantages and disadvantages. In summary, MAB has good application scenarios if people make good use of its different types of algorithms.