Представьте, что вы развлекаетесь в казино. Есть много игровых автоматов, и каждый автомат имеет разную ставку выплат. Как логичный человек, вы хотите вложить свои деньги в машину с максимальной ожидаемой отдачей. Отсюда и проблема многорукого бандита. Здесь мы рассмотрим два основных понятия: бета-распределение и выборка Томпсона.
Бета-распределение
Мы используем бета-распределение для моделирования простейшей формы задачи о многоруком бандите, которая представляет собой бинарный результат/вознаграждение. В примере с казино каждая машина будет выплачивать вознаграждение в размере 1 доллара в случае успеха и 0 долларов в случае неудачи. Наша цель — определить машину с наибольшей вероятностью успеха. Бета-распределение — это семейство непрерывных вероятностных распределений, определенных на интервале [0, 1], параметризованных двумя положительными параметрами формы, обозначаемыми α и β, которые появляются как показатели степени случайной величиной и контролировать форму распределения. Более подробную информацию можно найти здесь".
Мы используем бета-распределение для следующих двух важных свойств:
1. Бета-распределение определяется между 0 и 1, что соответствует диапазону наших оценок.
2. Апостериорная вероятность – это Бета с обновленными параметрами.
Используйте бейсбол в качестве примера. Средний балл (BA) — это метрика для оценки игрока, и мы хотим оценить BA для нового игрока, истинный BA которого составляет 30%. Поскольку у нового игрока нет истории отбивания мяча, мы можем предположить, что распределение оценочного BA соответствует бета (1,1), то есть наша оценка равномерно распределена между 0 и 1.
По мере развития игр мы можем собирать больше данных и лучше оценивать БА игрока. Используя свойство Beta, мы наблюдаем, что расчетная БА составляет ~10% после 10 АБ(At Bats), но очень близка к истинному значению 30% после 1000 АБ (код).
Томпсон Сэмплинг
Продолжая обсуждение, мы используем 3 игровых автомата с бета-распределением, чтобы объяснить, как работает Thompson Sampling. Истинная вероятность успеха слотов 0, 1 и 2 составляет 0,7, 0,8 и 0,9 соответственно, однако вероятность нам неизвестна. Наша цель — определить машину с наибольшей вероятностью успеха.
Опять же, поскольку у нас нет информации, мы предполагаем, что все 3 машины имеют одинаковое априорное распределение Бета (1,1), т. е. 3 машины с равной вероятностью будут выбраны для эксперимента. В начальный момент времени t = 0 мы проводим 1000 экспериментов и наблюдаем, что машины 0, 1 и 2 выбирают 324, 345 и 331 эксперимент соответственно. Затем мы используем результаты эксперимента для обновления α и β бета-распределения трех машин, а затем используем обновленную бета-версию в качестве новой априорной вероятности в момент времени t = 1 для следующие 1000 опытов. Продолжаем процесс до t = 1000 и результаты показаны ниже (код). Thompson Sampling позволяет нам определить действительно лучшую машину (машина № 2). Этот пример также известен как Бета-Бернулли Бандит.
Резюме
После прочтения этой статьи вы должны знать 1) что такое Бета-распределение и почему мы предполагаем Бета-распределение; и 2) как применить выборку Томпсона для решения простейшей задачи о многоруком бандите. Увидимся в следующий раз!
