Performance Comparison and Analysis of UCB, ETC, and Thompson Sampling Algorithms in the Multi-Armed Bandit Problem

Abstract

In this study, the nuanced interplay between problem complexity, prior knowledge, and the exploration-exploitation balance is examined, given their critical impact on algorithmic performance in diverse settings. To gain a deeper understanding of these dynamics, three algorithms – Upper Confidence Bound (UCB), Explore-Then-Commit (ETC), and Thompson Sampling – are selected for a comprehensive investigation. Each of these algorithms presents unique approaches to handling the challenges posed by varying problem contexts. The UCB algorithm, known for its robustness in balancing exploration and exploitation, is scrutinized for its performance in environments with differing levels of complexity and uncertainty. This algorithm's reliance on confidence bounds makes it particularly relevant in scenarios where accurate estimates of uncertainty can significantly enhance decision-making processes. ETC, on the other hand, is characterized by its phased approach, initially exploring options before committing to a seemingly optimal choice. This study examines how the ETC algorithm's performance is influenced by the availability of prior knowledge and the intricacy of the problem at hand. Its phased nature makes it a subject of interest in environments where initial exploration can yield substantial insights for subsequent exploitation.