Многорукий бандит (UCB, Thompson Sampling)

Многорукий бандит (MAB) — это адаптивная экспериментальная структура, которая последовательно распределяет испытания между конкурирующими «руками» (вариантами) с целью минимизации совокупного сожаления при одновременном обучении тому, какая рука работает лучше. Формализованная Роббинсом в 1952 году и получившая гарантии для конечного времени от Auer et al. (2002), она балансирует исследование неопределенных вариантов с эксплуатацией в настоящее время известных лучших вариантов, превосходя классическое A/B-тестирование всякий раз, когда важна ранняя остановка или чувствительное к затратам распределение.