 |
ML Newsnew | past | best | rss | submit | about |
| Regret Analysis of Stochastic and Nonstochastic Multi-Armed Bandit Problems (arxiv.org) | |
| 2 points by dragontamer on Jan 26, 2018 | hide | past | pdf | 1 comment on HN | |
|
In plain words: A survey of bandit problems: choosing between options while balancing past payoffs against trying new ones. It works out the loss against the best fixed option when payoffs are random or set by an opponent, plus cases where you get hints about each option. Abstract · Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit ProblemsMulti-armed bandit problems are the most basic examples of sequential decision problems with an exploration-exploitation trade-off. This is the balance between staying with the option that gave highest payoffs in the past and exploring new options that might give higher payoffs in the future. Although the study of bandit problems dates back to the Thirties, exploration-exploitation trade-offs arise in several modern applications, such as ad placement, website optimization, and packet routing. Mathematically, a multi-armed bandit is defined by the payoff process associated with each option. In this survey, we focus on two extreme cases in which the analysis of regret is particularly simple and elegant: i.i.d. payoffs and adversarial payoffs. Besides the basic setting of finitely many actions, we also analyze some of the most important variants and extensions, such as the contextual bandit model. | |
| add comment on HN |
The Multi-Armed Bandit Problem describes a gambler who is trying to optimize their gains. There are a finite number of slot machines in front of the gambler, and every slot machine has a different probability of winning.
What strategy should the gambler adopt to maximize their winnings? In general, the various algorithms balance "Exploitation" vs "Exploration". Exploration looks for better machines, while Exploitation plays the machine with the best statistics gathered so far.
In the case of MCTS, the different branches of the search tree are seen as a multi-armed bandit / different slot machines. UCT (Upper Confidence Bounds applied to Tree Searches) is the UCB algorithm (described in this survey) applied to a search tree.
Marketing experts have also used the Multi-armed bandit as a mechanism for A/B testing, determining the best placement of ads.
Finally, there are applications to business and research opportunities. Which research efforts should be funded for example, is very much a multi-armed bandit problem.
As such, the Multi-Armed Bandit Problem is a fundamental component to a lot of Hacker News discussion, even if people don't yet realize it. That's why I'm posting this excellent survey by Bubeck1 and Cesa-Bianchi, which can provide a good introduction to the Multi-Armed Bandit Problem.