Algorithms for multi-armed bandit problems

By Volodymyr Kuleshov, Doina Precup. 2014

400 citations recorded by the source corpus.

Although many algorithms for the multi-armed bandit problem are well-understood theoretically, empirical confirmation of their effectiveness is generally scarce. This paper presents a thorough empirical study of the most popular multi-armed bandit algorithms. Three important observations can be made from our results. Firstly, simple heuristics such as epsilon-greedy and Boltzmann exploration outperform theoretically sound algorithms on most settings by a significant margin. Secondly, the performance of most algorithms varies dramatically with the parameters of the bandit problem. Our study identifies for each algorithm the settings where it performs well, and the settings where it performs poorly. Thirdly, the algorithms' performance relative each to other is affected only by the number of bandit arms and the variance of the rewards. This finding may guide the design of subsequent empirical evaluations. In the second part of the paper, we turn our attention to an important area of application of bandit algorithms: clinical trials. Although the design of clinical trials has been one of the principal practical problems motivating research on multi-armed bandits, bandit algorithms have never been evaluated as potential treatment allocation strategies. Using data from a real study, we simulate the outcome that a 2001-2002 clinical trial would have had if bandit algorithms had been used to allocate patients to treatments. We find that an adaptive trial would have successfully treated at least 50% more patients, while significantly reducing the number of adverse effects and increasing patient retention. At the end of the trial, the best treatment could have still been identified with a high level of statistical confidence. Our findings demonstrate that bandit algorithms are attractive alternatives to current adaptive treatment allocation strategies.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Counterfactual reasoning and learning systems: the example of computational advertising (2012, background): “Even in the simple case of multi-armed bandits, excellent empirical results have been obtained using Thompson sampling (Chapelle and Li, 2011) or fixed strategies (Vermorel and Mohri, 2005; Kuleshov and Precup, 2010).”
A New Softmax Operator for Reinforcement Learning (2016, methodology): “Decision rules based on epsilon-greedy and Boltzmann softmax, while very simple, often perform surprisingly well in practice, even outperforming more advanced exploration techniques (Kuleshov & Precup, 2014).”
Boltzmann Exploration Done Right (2017, neutral): “…average of the rewards obtained from arm i up until round t , and η t > 0 is the learning rate . b This variant is broadly used in reinforcement learning (Sutton and Barto, 1998; Szepesvári, 2010; Kaelbling et al., 1996; Vermorel and Mohri, 2005; Kuleshov and Precup, 2014; Osband et al., 2016).”
Deep learning enabled inverse design in nanophotonics (2020, methodology): “If the number is greater than the epsilon value at that step, then the agent uses the network to choose an action, otherwise an action is chosen at random [94].”
Active Reinforcement Learning with Monte-Carlo Tree Search (2018, methodology): “Treatments are assigned using a Bandit design (Kuleshov and Precup, 2014) and after 200 trials the difference in mean evaluation between the two treatments is tiny.”
Multi-Task Learning for Contextual Bandits (2017, background): “The reward for each arm is random according to a fixed distribution, and the agent’s goal is to maximize its cumulative reward [4] through a combination of exploring different arms and exploiting those arms that have yielded high rewards in the past [15, 11].”
Automatic Prompt Optimization with "Gradient Descent" and Beam Search (2023, methodology): “…for all i = 1 , . . . , n 2: Initialize: Q t ( p i ) ← 0 for all i = 1 , . . . , n 3: for t = 1 , . . . , T do While a natural choice, UCB is designed primarily for regret minimization (Kuleshov and Precup, 2014), whereas we wish to perform the related but distinct task of best arm identification.”
Adversarial Attacks on Stochastic Bandits (2018, background): “This is potentially hazardous since stochastic MABs are widely used in the industry to recommend news articles [18], display advertisements [9], improve search results [17], allocate medical treatment [16], and promote users’ well-being [13], among many others.”
Short-Term Satisfaction and Long-Term Coverage: Understanding How Users Tolerate Algorithmic Exploration (2018, methodology): “We chose this method partly because this is how many theoretically-motivated machine learning algorithms explore (e.g., [27]), and partly because it represents the worst-case for frequently missing the user’s interests.”
Preference-based Online Learning with Dueling Bandits: A Survey (2018, background): “For example, MAB algorithms turned out to oﬀer eﬀective solutions for problems in medical treatment design (Lai and Robbins, 1985; Kuleshov and Precup, 2014), online advertisement (Chakrabarti et al., 2008), and recommendation systems (Kohli et al., 2013), just to mention a few.”
Estimation-Action-Reflection: Towards Deep Interaction Between Conversational and Recommender Systems (2020, background): “question [11, 14, 21, 24, 37], the issue has largely been unaddressed in the context of conversational recommender system.”