ML//RL//exploration-exploitation trade-off//multi-armed bandit
A multi-armed bandit is the simplest sequential decision problem with learning: an agent repeatedly picks one of several options (the arms, after a row of slot machines), each paying a random reward from a distribution it does not know, and it wants to collect as much as possible over many rounds. It is the exploration-exploitation trade-off stripped of everything else (no state, no dynamics, each choice independent of the last), and it runs in production wherever options can be tried cheaply and often: which supplier's spare part to order, which of three dispatch rules to run on today's shift, which version of a page to show.
A multi-armed bandit is the simplest sequential decision problem with learning: an agent repeatedly picks one of several options (the arms, after a row of slot machines), each paying a random reward from a distribution it does not know, and it wants to collect as much as possible over many rounds. It is the exploration-exploitation trade-off stripped of everything else (no state, no dynamics, each choice independent of the last), and it runs in production wherever options can be tried cheaply and often: which supplier's spare part to order, which of three dispatch rules to run on today's shift, which version of a page to show.
Performance is measured by regret, the reward lost against always pulling the best arm had it been known. Pulling at random keeps regret growing in proportion to time, and so does committing early to the arm that looked best after a few tries, because sometimes that arm is wrong. Good algorithms make regret grow only with the logarithm of time: each extra round costs less, because doubt about the losing arms shrinks.
UCB (upper confidence bound) is optimism with arithmetic. Each arm is scored by its average reward plus a bonus that is large when it has been tried rarely, and the arm with the highest score is pulled. A rarely tried arm gets its chance because its bonus is large; once it has been tried enough, its bonus shrinks and only a good average keeps it chosen.
at=argmaxi(xˉi+2lntni)a_t=\arg\max_i\left(\bar x_i+\sqrt{\frac{2\ln t}{n_i}}\right)at=argimax(xˉi+ni2lnt)
Here xˉi\bar x_ixˉi is arm iii's average reward so far, nin_ini how often it was pulled and ttt the round; the square root is the width of a confidence interval, which falls as 1/ni1/\sqrt{n_i}1/ni (standard error).
Thompson sampling is the Bayesian answer: keep a posterior over each arm's mean (Bayes' rule), draw one sample from each posterior, and pull the arm whose sample is highest. An arm is chosen exactly as often as it is probably the best, so exploration fades by itself as the posteriors narrow. With success-or-failure rewards each posterior is a Beta distribution updated by counting, a few lines of code, and it usually beats UCB in practice.
A contextual bandit lets the best arm depend on observed features (the machine type, the time of day). Once a choice also changes what the next situation will be, the problem has a state and becomes full reinforcement learning.
The bandit assumes rewards that do not drift; a supplier whose quality changes needs forgetting, a sliding window or a discount on old pulls. And it learns only from what it tries, so its logs are biased toward the arms it liked, which matters when the same data are later reused for anything else.