Thompson sampling

Thompson sampling is a heuristic for choosing actions that addresses the exploration-exploitation dilemma in the multi-armed bandit problem, where a decision maker must repeatedly pick among options whose rewards are uncertain. It is named after William Rae Thompson. At each step the method holds a belief about how rewarding each action is, draws one random sample from that belief, and then picks the action that maximizes the expected reward under the drawn sample. Actions that look promising are therefore chosen often, while uncertain actions still receive occasional trials because a random draw can favor them. As observations accumulate the belief narrows and the choices concentrate on the best action. The idea is applied in online decision problems such as choosing among competing options while learning from feedback.