Multi-Armed Bandit Algorithms: Learning from Experience

Abstract

Consider a scenario where a decision-maker faces a row of slot machines, each offering unknown and varying payout rates. The objective is to maximize cumulative rewards, yet each action simultaneously provides new information. This problem—balancing the exploration of new options against the exploitation of known rewarding ones—is termed the multi-armed bandit problem. It has evolved from a simple gambling question into a fundamental tool for modern computer systems. This paper looks at three main ways to solve this problem: Explore-Then-Commit, Upper Confidence Bound, and Thompson Sampling. Through careful testing, Thompson Sampling stands out as the best performer, cutting total regret down to 0.60 where UCB reaches 3.63. It also handles delays well—when feedback comes 1000 steps late, Thompson Sampling's lead over UCB grows to nearly 4 times. The paper shows where these methods are used in real life: online ads, where they improve click rates by about 11%; movie and music suggestions, where they help new users find content they like; and medical trials, where they can put over 80% of patients on better treatments. The paper ends with a look at new research areas, including methods that adapt to changing conditions and handle complex choices.