The Multi-Armed Bandit Problem and Its Solutions

Choosing the option with the best observed results can miss a better option that has barely been tried. The multi-armed bandit problem studies this tension when repeated choices have unknown reward probabilities. Lilian Weng's 2018 tutorial explains how an upper-confidence-bound strategy makes uncertainty part of the decision.

Each option receives its estimated reward plus an uncertainty allowance. An option with little evidence can therefore outrank a familiar one, earning another trial. As evidence accumulates, that allowance shrinks. Exploration is directed toward options that could plausibly be better, while the objective remains collecting reward across the whole sequence of choices.

“If you try new places all the time, very likely you are gonna have to eat unpleasant food from time to time.”