Introduction

IntroductionBandit problems were introduced by William R. Thompson in an article published in 1933 in Biometrika.Thompson was interested in medical trials and the cruelty of running a trial blindly, without adapting the treatment allocations on the fly as the drug appears more or Figure 1.1 Mouse learning a T-maze.less effective.The name comes from the 1950s, when Frederick Mosteller and Robert Bush decided to study animal learning and ran trials on mice and then on humans.The mice faced the dilemma of choosing to go left or right after starting in the bottom of a T-shaped maze, not knowing each time at which end they would find food.To study a similar learning setting in humans, a 'two-armed bandit' machine was commissioned where humans could choose to pull either the left or the right arm of the machine, each giving a random pay-off with the distribution of pay-offs for each arm unknown to the human player.The machine was called a 'twoarmed bandit' in homage to the one-armed bandit, an old-fashioned name for a leveroperated slot machine ('bandit' because they steal your money).There are many reasons to care about bandit problems.Decision-making with uncertainty is a challenge we all face, and bandits provide a simple model of this dilemma.Bandit problems also have practical applications.We already mentioned clinical trial design, which researchers have used to motivate their work for 80 years.We can't point to an example where bandits have actually been used in clinical trials, but adaptive experimental design is gaining popularity and is actively encouraged by the US Food and Drug Administration, with the justification that not doing so can lead to the withholding of effective drugs until long after a positive effect has been established.While clinical trials are an important application for the future, there are applications where bandit algorithms are already in use.Major tech companies use bandit algorithms for configuring web interfaces, where applications include news recommendation, dynamic pricing and ad placement.A bandit algorithm plays a role in Monte Carlo Tree Search, an algorithm made famous by the recent success of AlphaGo.Finally, the mathematical formulation of bandit problems leads to a rich structure with connections to other branches of mathematics.In writing this book (and previous papers), we have read books on convex analysis/optimisation, Brownian motion, probability theory,

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.