multi-armed bandit

The Means of Prediction: How AI Really Works (And Who Benefits)

by Maximilian Kasy  · 15 Jan 2025  · 209pp  · 63,332 words

. Successful AI, in online settings, needs to both explore new things, by experimenting, and to exploit what it has learned, in just the right balance. Multi-armed bandit algorithms are designed to do exactly that: They aim to find exactly the right balance between experimenting with different options and doing what seems best

…

based on what has been learned from actions they have previously tried. Reinforcement learning goes one step further than multi-armed bandit algorithms. Reinforcement learning builds algorithms that learn to plan by learning how likely it is that different states of the world are favorable down the

…

be stuck with pizza. We can only observe how well an option did if we chose it. Situations where this is the case are called multi-armed bandits in AI. The name comes from gambling. Imagine you are playing slot machines in a casino (not that you should do that). Slot machines are

…

uncertainty. Regulatory agencies such as the US Food and Drug Administration have recently released guidelines allowing adaptive designs. By far the most widespread use of multi-armed bandit algorithms, however, is to sell you stuff. The big tech companies that provide search engines or social media platforms make most of their profits by

…

selling targeted advertisements. They earn money whenever you click on an ad. Their prime objective, therefore, is to maximize ad clicks. Multi-armed bandit algorithms are key tools in doing this. When surfing the internet, you are constantly the subject of little experiments. Algorithms decide what ads are displayed

…

algorithm’s actions affect its ability to learn and to make better decisions in the future. This is addressed in the multi-armed bandit framework, which formalizes a concern for exploration. But the multi-armed bandit framework is itself still shortsighted in important ways. This framework considers how actions impact the ability to learn, but it

…

does not involve any concern for how actions impact rewards in the future. The multi-armed bandit framework does not involve any notion of planning, which is as crucial in many real-world tasks as it is in playing games. The problem

…

a computer? Your computer has no innate desire for treats, after all. Let us start by again considering the multi-armed bandits. How would they perform in a game of chess or go? A multi-armed bandit algorithm initially makes random moves. If a move is rewarded (leads to a win), the algorithm will be more

…

rather pointless. Most board positions in these games do not lead to a win, no matter what move is made. What is missing from the multi-armed bandit framework for this setting? The key point to note is that the goal of most moves is not to yield an immediate win. Instead, good

…

every configuration encountered during play: First, predict whether you will get a win or loss right now. This is exactly the type of prediction a multi-armed bandit would make. Second, predict what the configuration of the board will be after your move, by the next time it is your turn, and for

…

particular in low-income countries (where AI might be used in matters related to fertility policy). In both examples, some combination of supervised learning and multi-armed bandits could be used to allocate services and treatments. And since machine learning algorithms are designed to maximize observed rewards, that means that in practice algorithms

…

negligible cost, in terms of predictive accuracy, relative to unrestricted machine learning. This holds true for supervised learning tasks, and it also holds true for multi-armed bandits and related settings. Democratic Data Governance To summarize, data externalities are built into machine learning and AI: The reason anyone bothers with all the work

…

sound familiar. We have already talked about causal effects of decisions earlier in this book, even if we did not use the language of causality. Multi-armed bandit algorithms are constantly running experiments, to learn about the causal effect of the different arms that the algorithms might choose. Let us now come back

…

.2103.09177. Berger, J. Statistical Decision Theory and Bayesian Inference. Springer Verlag, 1985. Bubeck, S., and N. Cesa-Bianchi. “Regret Analysis of Stochastic and Nonstochastic Multi-Armed Bandit Problems.” Foundations and Trends in Machine Learning 5, no. 1 (2012): 1–122. Caria, S., G. Gordon, M. Kasy, S. Quinn, S. Osman Shami, and

…

–41, 40 models, used for explainability, 178–79 monopolies, 90, 104, 109 Moore’s Law, 45, 46 MTurk. See Amazon Mechanical Turk Muller, Chris, 200 multi-armed bandit algorithms, 12, 58–62 multitasking, 125, 127–28, 130 Musk, Elon, 3, 106 Naidu, Suresh, 200 nationalism, 72 natural language modeling, 53 Netanyahu, Benjamin, 126

Artificial Intelligence: A Modern Approach

by Stuart Russell and Peter Norvig  · 14 Jul 2019  · 2,466pp  · 668,761 words

, J., Darrell, T., and Malik, J. (2016). Region-based convolutional networks for accurate object detection and segmentation. PAMI, 38, 142–58. Gittins, J. C. (1989). Multi-Armed Bandit Allocation Indices. Wiley. Gittins, J. C. and Jones, D. M. (1974). A dynamic allocation index for the sequential design of experiments. In Gani, J. (Ed

Model Thinker: What You Need to Know to Make Data Work for You

by Scott E. Page  · 27 Nov 2018  · 543pp  · 153,550 words

Choice 21 Game Theory Models Times Three 22 Models of Cooperation 23 Collective Action Problems 24 Mechanism Design 25 Signaling Models 26 Learning Models 27 Multi-Armed Bandit Problems 28 Rugged-Landscape Models 29 Opioids, Inequality, and Humility About the Author Notes Bibliography Index To Michael D. Cohen (1945–2013) It can scarcely

…

convince well-connected employees can introduce new strategies that trump culture. According to the second model, culture trumps weak incentives but not strong ones. 27. Multi-Armed Bandit Problems There’s one thing I’m really good at, and that’s hitting the ball over a net, in a box. I’m excellent

…

. —Serena Williams In this chapter, we add uncertainty to the problem of learning the best alternative to create a class of models known as multi-armed bandit problems. In bandit problems, rewards from alternatives are distributions rather than fixed amounts. Bandit problems apply to a wide variety of real-world situations. Any

…

optimal rule: if an alternative is always successful, keep choosing that alternative. Experimentation can have no value because no other alternative could perform better. Bayesian Multi-Armed Bandit Problems In a Bayesian bandit problem, the decision-maker has prior beliefs over the reward distributions of the alternatives. Given these prior beliefs, a decision

…

the optimal action requires rather tedious calculations. In real-world applications, these exact calculations may be impractical, obliging decision makers to rely on approximations. Bayesian Multi-Armed Bandit Problems A collection of alternatives {A, B, C, D,…, N} have associated reward distributions {f (A), f (B), f (C), f (D),…, f (N)}. The

…

chapter: rugged-landscape models. Presidential Elections We now apply three models to analyze outcomes in presidential elections: the spatial model, the category model, and the multi-armed bandit model. Spatial model: To attract voters, candidates compete in an ideological issue space. Thus, we should expect candidates to tend toward moderate positions, elections to

…

Ohio. In 2016, Clinton and Trump also spent more than half of their television dollars in three moderate states: Florida, Ohio, and North Carolina.7 Multi-armed bandit model (retrospective voting): Voters will be more likely to reelect a party that produces good outcomes. Voting for effective parties corresponds to pulls of a

…

how the epidemic arose, we apply four models to generate some core intuitions as to how the crisis came to be. The first model, the multi-armed bandit model, explains why opioids were approved for use. When seeking drug approval, a pharmaceutical company runs clinical trials to demonstrate drug efficacy and a lack

…

of deleterious side effects. We can model a clinical trial as a multi-armed bandit problem where one arm corresponds to prescribing the new drug and the other arm corresponds to a placebo or the existing drug. A Model of

…

Opioid Approval Multi-Armed Bandit Model To demonstrate their efficacy, opioids were tested against placebos. In clinical trials, patients were randomly assigned to take either opioids or a placebo. The

…

+ 300B Rearranging terms gives 20(1 − B) > 80B. Thus, applying replicator dynamics, the cultural action increases if and only if: 0.2 > B. Chapter 27: Multi-Armed Bandit Problems 1 See Bergemann and Valimaki 2008 for the relevance to economic phenomena. 2 See Hills et al. 2015 for a survey. 3 See Scott

…

2010 for an analysis of the multi-armed bandit problem and various heuristics. 4 Gittins and Jones (1972) first characterized the optimal rule. The Gittins index can be reformulated as a Bellman equation, which

…

, no. 4: 621–646. Schelling, Thomas. 1978. Micromotives and Macrobehavior. New York: W. W. Norton. Scott, Steven L. 2010. “A Modern Bayesian Look at the Multi-Armed Bandit.” Applied Stochastic Models in Business and Industry 26: 639–658. Shalizi, Cosma, and Andrew C. Thomas. 2011. “Homophily and Contagion Are Generically Confounded in Observational

…

basic growth model, output in, 102 (fig.) basic reproduction number, defining, 138 basins of attraction, 330, 332 (fig.) basketball, 157 Bass model, 136–137 Bayesian multi-armed bandit problems, 321–324 Beatles, 132 Bednar, Jenna, 283 behavioral rules, 284 belief-based learning rule, 316 beliefs, 14 in rational-actor model, 48 benchmarks rational

…

monotonic ordering, 16 Monte Carlo method, for random networks, 121 Moore, Marianne, 131 Mount Fuji landscape, 328, 328 (fig.), 334 Mount-Reiter diagram, 284–286 multi-armed bandit problems, 319, 326, 340 Bayesian, 321–324 multiple congestible goods, 277 multiple-variable regression, 88–89 multivariable linear models, 87–90 Munger, Charlie, 1 music

Algorithms to Live By: The Computer Science of Human Decisions

by Brian Christian and Tom Griffiths  · 4 Apr 2016  · 523pp  · 143,139 words

, exploring so that others may exploit. In computer science, the tension between exploration and exploitation takes its most concrete form in a scenario called the “multi-armed bandit problem.” The odd name comes from the colloquial term for a casino slot machine, the “one-armed bandit.” Imagine walking into a casino full of

…

the best machines they’ve got before the casino turns them out. Win-Stay Finding optimal algorithms that tell us exactly how to handle the multi-armed bandit problem has proven incredibly challenging. Indeed, as Peter Whittle recounts, during World War II efforts to solve the question “so sapped the energies and minds

…

algorithm always says you should go to another place—even if it’s your last night in town. Still, Robbins’s initial work on the multi-armed bandit problem kicked off a substantial literature, and researchers made significant progress over the next few years. Richard Bellman, a mathematician at the RAND Corporation, found

…

possible futures, we of course don’t always know exactly how many opportunities (or even how many options) we’ll have. For these reasons, the multi-armed bandit problem effectively stayed unsolved. In Whittle’s words, “it quickly became a classic, and a byword for intransigence.” The Gittins Index As so often happens

…

each option, and a certain amount of effort (or money, or time) to be allocated among them. It was, of course, another incarnation of the multi-armed bandit problem. Both the for-profit drug companies and the medical profession they serve are constantly faced with the competing demands of the explore/exploit tradeoff

…

true of profits. Economists refer to this idea, of valuing the present more highly than the future, as “discounting.” Unlike previous researchers, Gittins approached the multi-armed bandit problem in those terms. He conceived the goal as maximizing payoffs not for a fixed interval of time, but for a future that is endless

…

geometric-discounting assumption, Gittins investigated a strategy that he thought “at least would be a pretty good approximation”: to think about each arm of the multi-armed bandit separately from the others, and try to work out the value of that arm on its own. He did this by imagining something rather ingenious

…

thing over the uncertainty of the briefcase prize. Gittins (albeit many years before the first episode of Deal or No Deal aired) realized that the multi-armed bandit problem is no different. For every slot machine we know little or nothing about, there is some guaranteed payout rate which, if offered to us

…

play the arm with the highest index.* In fact, the index strategy turned out to be more than a good approximation. It completely solves the multi-armed bandit with geometrically discounted payoffs. The tension between exploration and exploitation resolves into the simpler task of maximizing a single quantity that accounts for both. Gittins

…

that a payoff on our next pull is worth 90% of a payoff now. These values can be used to resolve a variety of everyday multi-armed bandit problems. For example, under these assumptions you should, in fact, choose the slot machine that has a track record of 1–1 (and an expected

…

future into account, rather than focusing just on the present, drives us toward novelty. The Gittins index thus provides an amazingly straightforward solution to the multi-armed bandit problem. But it doesn’t necessarily close the book on the puzzle, or help us navigate all the explore/exploit tradeoffs of everyday life. For

…

since the development of the Gittins index, such concerns have sent computer scientists and statisticians searching for simpler and more flexible strategies for dealing with multi-armed bandits. These strategies are easier for humans (and machines) to apply in a range of situations than crunching the optimal Gittins index, while still providing comparably

…

: a life with minimal regret. Regret is the result of comparing what we actually did with what would have been best in hindsight. In a multi-armed bandit, Barnard’s “inestimable loss” can in fact be measured precisely, and regret assigned a number: it’s the difference between the total payoff obtained by

…

). We can calculate this number for different strategies, and search for those that minimize it. In 1985, Herbert Robbins took a second shot at the multi-armed bandit problem, some thirty years after his initial work on Win-Stay, Lose-Shift. He and fellow Columbia mathematician Tze Leung Lai were able to prove

…

will have a wider confidence interval, though the same expected value, as a machine that has paid out five times on ten pulls.) In a multi-armed bandit problem, an Upper Confidence Bound algorithm says, quite simply, to pick the option for which the top of the confidence interval is highest. Like the

…

Gittins index, therefore, Upper Confidence Bound algorithms assign a single number to each arm of the multi-armed bandit. And that number is set to the highest value that the arm could reasonably have, based on the information available so far. So an Upper

…

, perhaps even the prices you see—and certainly the ads—have come from an explore/exploit algorithm, tuning itself to your clicks. In this particular multi-armed bandit problem, you’re not the gambler; you’re the jackpot. The process of A/B testing itself has become increasingly refined over time. The most

…

a growing community of doctors and statisticians think that we’re doing it wrong: that we should be treating the selection of treatments as a multi-armed bandit problem, and trying to get the better treatments to people even while an experiment is in progress. In 1969, Marvin Zelen, a biostatistician who is

…

already concluded this before the Ware study, and were vocal about it. The critics included Don Berry, one of the world’s leading experts on multi-armed bandits. In a comment that was published alongside the Ware study in Statistical Science, Berry wrote that “randomizing patients to non-ECMO therapy as in the

…

from the statistics department at the University of Minnesota to the MD Anderson Cancer Center in Houston, where he has used methods developed by studying multi-armed bandits to design clinical trials for a variety of cancer treatments. While he remains one of the more vocal critics of randomized clinical trials, he is

…

trust—that they might at last be willing to explore alternatives. The Restless World Once you become familiar with them, it’s easy to see multi-armed bandits just about everywhere we turn. It’s rare that we make an isolated decision, where the outcome doesn’t provide us with any information that

…

a cost to not having a secretary, there’s a cost to committing too soon to a particular airline: the world might change. The standard multi-armed bandit problem assumes that the probabilities with which the arms pay off are fixed over time. But that’s not necessarily true of airlines, restaurants, or

…

oneself. So long as things continue to change, you must never fully cease exploring. Still, the algorithmic techniques honed for the standard version of the multi-armed bandit problem are useful even in a restless world. Strategies like the Gittins index and Upper Confidence Bound provide reasonably good approximate solutions and rules of

…

evolution for a world in constant flux isn’t necessarily helpful in an era of industrial standardization. Perhaps most importantly, thinking about versions of the multi-armed bandit problem that do have optimal solutions doesn’t just offer algorithms, it also offers insights. The conceptual vocabulary derived from the classical form of the

…

an extended period of dependence: “it gives you a developmental way of solving the exploration/exploitation tradeoff.” As we have seen, good algorithms for playing multi-armed bandits tend to explore more early on, exploiting the resulting knowledge later. But as Gopnik points out, “the disadvantage of that is that you don’t

…

the two-armed bandit. He then introduced the mathematical form of the problem to his colleagues, and it ultimately became generalized to the multi-armed bandit. A comprehensive introduction to multi-armed bandits appears in Berry and Fristed, Bandit Problems. Our focus in this chapter is on bandits where each arm either produces a payoff or

…

, as the probability distribution that describes a coin flip is called the Bernoulli distribution (after the seventeenth-century Swiss mathematician Jacob Bernoulli). Other kinds of multi-armed bandits are also possible, with unknown distributions of different kinds characterizing the payoffs from each arm. how good the second machine might actually be: The “myopic

…

doesn’t apply) appear in Berry and Fristed, Bandit Problems. exactly how many options and opportunities: This solution to the “finite horizon” version of the multi-armed bandit problem is presented in Bellman’s magnum opus Dynamic Programming, a book that is impressive as the starting point (and sometimes endpoint) of a number

…

, 2013. Deal or No Deal: The many worldwide incarnations of this game show began with the Dutch show Miljoenenjacht, which first aired in 2000. the multi-armed bandit problem is no different: Previous researchers had also found solutions for this “one-armed bandit” problem over a fixed interval (Bellman, “A Problem in the

…

Allocation Indices.” we provide the Gittins index values: The table of Gittins index scores for the Bernoulli bandit was taken from Gittins, Glazebrook, and Weber, Multi-Armed Bandit Allocation Indices, which is a comprehensive guide to the topic. It assumes complete ignorance about the probability of a payoff. drives us toward novelty: Taking

…

yields if you’re the patient sort who values tomorrow’s payoff as being essentially as good as today’s. (The rule appears in Kelly, “Multi-Armed Bandits with Discount Factor Near One”; formally, it is optimal under geometric discounting in the limit as the discount rate approaches 1.) In a big city

…

-to-reach-370b-by-2017-e191b-in-europe/. best algorithms to use remain hotly contested: Chris Stucchio, for instance, penned a cutting article titled “Why Multi-armed Bandit Algorithms Are Superior to A/B Testing,” which was then countered by an equally cutting article called “Don’t Use Bandit Algorithms—They Probably Won

…

_bandits.html. Stucchio’s 2012 post was written partly in reference to an article by Paras Chopra titled “Why Multi-armed Bandit Algorithm Is Not ‘Better’ than A/B Testing” (https://vwo.com/blog/multi-armed-bandit-algorithm/), which was itself written partly in reference to an article by Steve Hanov titled “20 lines of code

…

of the binomial rate using a uniform prior. If you try only once and it works out: You may recall that in our discussion of multi-armed bandits and the explore/exploit dilemma in chapter 2, we also touched on estimates of the success rate of a process—a slot machine—based on

…

tradeoff. And randomness turns out to be a source of pretty good strategies for solving problems like multi-armed bandits as well as the kind of optimization problems that Kirkpatrick was focused on. If you recall, the multi-armed bandit offers us several different options—arms we can pull—that provide different, unknown payoffs. The challenge

…

exploitation, why not simply do so explicitly? Spend some amount of your time exploring and some amount exploiting. And that’s exactly the strategy that multi-armed bandit experts call Epsilon Greedy. Epsilon Greedy has two parts—Epsilon and Greedy. The Epsilon part is that some small proportion of the time (the letter

…

decide whether to try something new. If it says yes, close your eyes and point at the menu. If not, enjoy your current favorite. Unfortunately, multi-armed bandit researchers don’t particularly like Epsilon Greedy. It seems wasteful—you’re guaranteed to spend a proportion of your time trying new things even if

…

the probability of trying something new, you hit the sweet spot between exploration and exploitation. There’s also another, more sophisticated algorithm for playing the multi-armed bandit that likewise makes use of randomness. It’s called Thompson Sampling, named after William R. Thompson, the Yale physician who first posed the problem (back

…

guarantees that regret will increase only logarithmically (see Agrawal and Goyal, “Analysis of Thompson Sampling”). The advantage of Thompson Sampling over other algorithms for solving multi-armed bandit problems is its flexibility. Even if the assumptions of the problem change—you have information suggesting one option is better than the others, options depend

…

–793. Agrawal, Rajeev. “Sample Mean Based Index Policies with O(log n) Regret for the Multi-Armed Bandit Problem.” Advances in Applied Probability 27 (1995): 1054–1078. Agrawal, Shipra, and Navin Goyal. “Analysis of Thompson Sampling for the Multi-armed Bandit Problem.” In Proceedings of the 25th Annual Conference on Learning Theory, 2012. Akerlof, George A

…

and Dynamic Allocation Indices.” Journal of the Royal Statistical Society, Series B (Methodological) 41 (1979): 148–177. Gittins, John C., Kevin Glazebrook, and Richard Weber. Multi-Armed Bandit Allocation Indices, 2nd ed. Chichester, UK: Wiley, 2011. Gittins, John C., and D. Jones. “A Dynamic Allocation Index for the Sequential Design of Experiments.” In

…

. Katehakis, Michael N., and Herbert Robbins. “Sequential Choice from Several Populations.” Proceedings of the National Academy of Sciences 92 (1995): 8584–8585. Kelly, F. P. “Multi-Armed Bandits with Discount Factor Near One: The Bernoulli Case.” Annals of Statistics 9 (1981): 987–1001. Kelly, John L. “A New Interpretation of Information Rate.” Information

…

, Julie Morse, Samuel F. B. mortgage crisis of Moser, Leo Mosteller, Frederick movies box-office grosses and running times and sequels and Mozart, Wolfgang Amadeus multi-armed bandits Multiplicative Rule multitasking murder rate Murphy, Tom Myerson, Roger myopic algorithm Nakamura, Hikaru Nash, John Nash equilibrium National Library Sorting Champion Nature NBA NCAA nervous

Range: Why Generalists Triumph in a Specialized World

by David Epstein  · 1 Mar 2019  · 406pp  · 109,794 words

. Miller modeled career matching—and a decision to attend a military academy is a major career choice—as a “multi-armed bandit process.” “One-armed bandit” is slang for a slot machine. A multi-armed bandit process refers to a hypothetical scenario: a single gambler is sitting in front of an entire row of slot machines

…

staying attuned to whether switching is simply a failure of perseverance, or astute recognition that better matches are available. Beast Barracks is perfect for a multi-armed bandit approach to quitting. A group of high achievers, not one of whom has an iota of military experience, pulls the West Point “lever,” so to

…

of his life when he settled on his unique style and creatively erupted. Van Gogh was an example of match quality optimization, Robert Miller’s multi-armed bandit process come to life. He tested options with maniacal intensity and got the maximum information signal about his fit as quickly as possible, and then

Fluke: Chance, Chaos, and Why Everything We Do Matters

by Brian Klaas  · 23 Jan 2024  · 250pp  · 96,870 words

-Being: An Introduction,” Journal of Happiness Studies 9 (2008): 1–11. multiarmed bandit: See, for example, M. N. Katehakis and A. F. Veinott Jr., “The Multi-armed Bandit Problem: Decomposition and Computation,” Mathematics of Operations Research 12 (2) (1987): 262–68. constantly exploring new restaurants: This point was made to me by my

The Alignment Problem: Machine Learning and Human Values

by Brian Christian  · 5 Oct 2020  · 625pp  · 167,349 words

, “Learning Agents for Uncertain Environments (Extended Abstract).” 31. This remains very much an open research question. For recent work, see Chan et al., “The Assistive Multi-Armed Bandit.” 32. Berkeley’s Smitha Milli and Anca Drăgan have explored this question: see Milli and Drăgan, “Literal or Pedagogic Human?” 33. Stefano Ermon, interview by

…

18, 2015. https://www.vox.com/2015/9/18/9348821/photography-race-bias. Chan, Lawrence, Dylan Hadfield-Menell, Siddhartha Srinivasa, and Anca Drăgan. “The Assistive Multi-Armed Bandit.” In 2019 14th ACM/IEEE International Conference on Human-Robot Interaction (HRI), 354–63. IEEE, 2019. “A Chance to Fix Parole in New York.” New

Human Compatible: Artificial Intelligence and the Problem of Control

by Stuart Russell  · 7 Oct 2019  · 416pp  · 112,268 words

.” 41. An initial paper on helping humans who don’t know their own preferences and are learning about them: Lawrence Chan et al., “The assistive multi-armed bandit,” in Proceedings of the 14th ACM/IEEE International Conference on Human–Robot Interaction (HRI), ed. David Sirkin et al. (IEEE, 2019). 42. Eliezer Yudkowsky, in

Shape: The Hidden Geometry of Information, Biology, Strategy, Democracy, and Everything Else

by Jordan Ellenberg  · 14 May 2021  · 665pp  · 159,350 words

clustering; Judea Pearl and the use of directed acyclic graphs in the study of causality; navigation charts of the Marshall Islands; exploitation versus exploration and multi-armed bandits; binocular vision in praying mantis larvae; the maximum size of a subset of the N by N grid with no three points forming an isosceles

Hacking Growth: How Today's Fastest-Growing Companies Drive Breakout Success

by Sean Ellis and Morgan Brown  · 24 Apr 2017  · 344pp  · 96,020 words

comparing two alternatives to comparing every possible combination of each element of a message to find the highest-performing permutation. Or, take what’s called multi-armed bandit, a more sophisticated testing scheme used by companies to find winning results faster. We’ll introduce more types of tests that can be run and