#multi-armed-bandit — Reinforcement learning

Multi-armed bandit: explore or exploit?

What you'll play with

Welcome to #multi-armed-bandit. On screen, five slot machines lined up. Each hides a different winning probability — a number no one will tell you. Above each machine, a blue bar: your estimate Q(a) of its mean (all zero, you haven't pulled yet); a thin indigo bar: your uncertainty. Below each machine, a chip stack will count your pulls; on the right, two curves will track your cumulative reward (blue) and your cumulative regret (pink). The dilemma: every pull on a machine you know is one less pull to find out whether another pays better. Exploit what you know or explore what you ignore — that is the multi-armed bandit problem, and also the problem of an A/B test, a recommendation engine or picking a restaurant tonight.
Pull ten times with the default greedy strategy: /pull 10. It always plays the machine with the largest Q (at random on ties). Watch the balls drop: green, the machine paid; red, nothing.
Let's check. Reveal the true probabilities: /reveal. A grey bar appears behind each blue bar — the machine's true mean — and the best arm is marked in green.
Let's add a little randomness: /strategy epsilon. With ε-greedy, one pull in ten (ε = 0.10) goes to a machine picked at random; the other nine exploit the current best estimate.
Start a long run: /play 500. Five hundred pulls at once; bars slide toward their new values and the curves are drawn.
Switch to a finer strategy: /strategy ucb. UCB (upper confidence bound) plays the machine whose Q(a) + c·√(ln t / N(a)) is largest: the estimate plus an uncertainty bonus that shrinks as the machine is pulled.
Replay five hundred pulls, this time with UCB: /play 500.
Take stock: /regret. The reply gives the cumulative regret, the optimal machine and what each machine cost you; the scene writes it in pink on each machine.
Your turn: /strategy thompson then /play 2000 (Bayesian sampling: often the best regret of all), /arms 10 for ten machines (exploration costs more), /epsilon 0.3 or /c 0.5 to tune the appetite for exploration, /seed 42 for different machines, /reveal to hide the true means again, /reset to restart. Next stop: #q-learning, where the agent must also account for the state it is in — the bandit becomes a sequential decision problem.

Channel commands

/arms <2..10> — Number of machines; new hidden means, counters reset to zero.
/strategy <greedy|epsilon|ucb|thompson> — Way of choosing the machine at each pull; Q and N are kept.
/epsilon <0..1> — Exploration rate ε of the ε-greedy strategy.
/c <0..3> — UCB exploration bonus c: Q(a) + c·√(ln t / N(a)).
/pull <1..50> — A few pulls, replayed one by one on screen (green ball = gain, red = nothing).
/play <100..2000> — Long simulation: play n pulls in one go and draw the curves.
/reveal — Show or hide the true means (grey bars) and the best arm.
/regret — Summary: cumulative regret, optimal machine and each machine's share (shown or hidden on the scene).
/seed <1..9999> — Changes the hidden means and the random draws; counters reset to zero.
/reset — Back to five machines, greedy strategy, ε = 0.10, c = 1, hidden means.

Glossary

multi-armed bandit: A problem where you repeatedly choose one of k slot machines ("arms") with unknown mean gains, observing only the gain of the pulled arm. Model of A/B testing, recommendation and clinical trial allocation: learning by acting, never seeing "what the other choice would have done".
exploration and exploitation: The central dilemma: exploit means playing the arm you think is best to collect; explore means trying another to check that you are not mistaken. Too much exploitation locks in on an error; too much exploration wastes. Every bandit strategy is a way to dose this trade-off.
greedy strategy: Always plays the arm with the largest estimated Q(a). Without exploration it locks in on the first arm that paid: its Q stays positive while arms never tried stay at zero. Linear regret in the worst case — the "negative lesson" of the bandit.
ε-greedy: With probability ε, a random arm; otherwise the best Q. Fixes the greedy defect, but a fixed ε implies a constant share of wasted pulls: linear regret, slope ≈ ε × mean gap. ε can decay over time to reach sub-linear regret.
UCB (upper confidence bound): Plays the arm that maximizes Q(a) + c·√(ln t / N(a)): the estimate plus an uncertainty bonus, large for a rarely pulled arm and shrinking with N(a). The optimism in the face of uncertainty principle. UCB1 (Auer, 2002) guarantees O(ln t) regret, the optimal order.
Thompson sampling: Bayesian approach: each arm has a belief distribution over its mean — for 0/1 gains, a Beta(1 + gains, 1 + failures). Each round we draw one value from each distribution and play the arm with the largest sample: an arm is therefore chosen with the probability it is the best. Simple, parameter-free, often the most effective in practice.
regret: What you have lost compared to a player who knew the best arm: L(t) = Σ (μ* − μ_{a_s}) over t pulls. A strategy is good if its regret is sub-linear (grows slower than t): the fraction of wasted pulls tends to zero. Only computable when the true means are known — in practice you bound it, you don't measure it.
action value Q(a): Estimate of the mean gain of arm a: the mean of observed gains, updated by Q ← Q + (r − Q) / N(a) after each pull (incremental mean). Same quantity as Q(s, a) in Q-learning, without the state s: the bandit is a one-state reinforcement problem.
stochastic reward: An arm's gain is random: here 1 with probability μ_a, 0 otherwise (Bernoulli law). A single pull says almost nothing about μ_a; you need N pulls to estimate it to about 1/√N — that uncertainty is what the thin bars show and what exploration must reduce.
contextual bandit: Variant where you observe a context (user profile, time of day, page) before choosing the arm, and the mean gain depends on that context. Model of recommender systems and online ads; one step further, with a state that evolves with the actions, and you reach full reinforcement learning.

Other channels in Reinforcement learning

#multi-armed-bandit — Multi-armed bandit: explore or exploit?
#q-learning — Q-learning: learning a path by trial and error.