Сценарий
Представьте, что вы находитесь перед тремя игровыми автоматами, каждый из которых имеет разную вероятность выплаты. Как вы должны играть их, чтобы максимизировать ваши выплаты?
Эту проблему решает алгоритм многорукого бандита.
Вы можете сказать, что решение состоит в том, чтобы просто попробовать их все и посмотреть, какой из них лучше, и вы были бы правы! Но сколько стоит играть на каждом игровом автомате? Сколько мало, слишком мало? Вот где это становится сложным. Это не так уж плохо. Небольшой байесовский трюк со статистикой может сделать это довольно легко. На самом деле все, что нам нужно сделать, — это играть на автомате с наибольшей вероятностью выплат.
Сокращение неизвестного итеративно
Теперь, когда мы знаем, что нам не нужно знать точную вероятность для любого из вариантов, давайте рассмотрим, как мы можем найти лучший вариант.
Допустим, мы начнем с машины А, опустимся на четверть и потянем ручку назад. Нет выплат. Как это влияет на нашу веру в эту машину? Оказывается, это похоже на то, как мы обновили наши убеждения в подбрасывании монет в моем предыдущем посте. (Вы можете прочитать это здесь: http://www.databozo.com/2013/09/15/Bayesian_updating_of_probabi lity_distributions.html )
Ключевой особенностью, которую мы хотим, является экспериментирование различных вариантов. Мы можем сделать это, собрав ряд достоверных гипотез о вероятности выплаты и выбрав случайную выборку. Существует действительно удобная статистическая функция, которую мы можем использовать для выполнения этой функции, которая называется «бета». Бета-функция определяется следующим образом:
случайное правдоподобие = бета (1 + играет, что приводит к выплате, 1 + играет НЕ
в результате выплаты)
Представьте, что вы играли в игровой автомат A десять раз без выплаты. Бета-функция будет выглядеть так:
В работе [44]:
%load_ext rmagic from pretty import pprint
Расширение rmagic уже загружено. Чтобы перезагрузить его, используйте:% reload_ext rmagic
В работе [2]:
%%R curve(dbeta(x, 1, 11))
Это показывает, как вероятности ближайшего нуля наиболее вероятны. Все, что выше .4 практически невозможно. Конечно, ноль — это наиболее вероятная вероятность, но это не единственная возможность. Так что теперь, если бы мы взяли образец вероятности из вышеупомянутой бета-функции, мы должны увидеть, что мы получаем низкую вероятность для этой машины.
В работе [3]:
%%R print(rbeta(1,1,11))
[1] 0,04452788
Вот где это круто! Мы можем использовать эту же технику даже для игровых автоматов, которые мы еще не пробовали. Давайте посмотрим, должны ли мы попробовать игровой автомат B дальше. Мы оценим функцию бета без предварительной информации. Это бета (1,1). Выше мы используем rbeta с дополнительным параметром (первым), чтобы указать, сколько сэмплов мы хотим извлечь из функции. Так что это будет все.
В [4]:
%%R
print("Likelihood for Slot Machine B to payout")
print(rbeta(1,1,1))
[1] «Вероятность выплаты игрового автомата B»
[1] 0.655021
Хорошо отстой. Если у игрового автомата A есть только 4,5% шансов на выплату, а у игрового автомата B — 65,5%, то мы будем безумно играть в Machine A. Но давайте посмотрим, какова вероятность игрового автомата C.
В работе [5]:
%%R
print("Likelihood for Slot Machine C to payout")
print(rbeta(1,1,1))
[1] «Вероятность выплаты игрового автомата C»
[1] 0,8438229
Просто так получилось, что мы выбрали еще более высокую вероятность. Затем мы играем в игровой автомат C и отслеживаем, добьемся ли мы успеха или провала. Можно смело предположить, что мы провалим следующую игру. Мы снова производим выборку из бета-функции для каждого игрового автомата с обновленными параметрами.
В работе [18]:
%%R
print("Likelihood for Slot Machine A to payout")
print(rbeta(1,1,11))
print("Likelihood for Slot Machine B to payout")
print(rbeta(1,1,2))
print("Likelihood for Slot Machine C to payout")
print(rbeta(1,1,2))
[1] «Вероятность выплаты игрового автомата А»
[1] 0,07449518
[1] «Вероятность выплаты игрового автомата B»
[1] 0.740949 [1] «Вероятность выплаты игрового автомата C»
[1] 0,2574801
Так как игровой автомат B сэмплирует самое высокое, мы играем в него и продолжаем. Давайте запустим полную симуляцию и посмотрим, как наши результаты изменяются с течением времени в соответствии с этим алгоритмом.
В работе [47]:
def create_slot_machines():
return {
'A': {'true_payout_rate': .1, 'payouts':0, 'plays':0},
'B': {'true_payout_rate': .05, 'payouts':0, 'plays':0},
'C': {'true_payout_rate': .01, 'payouts':0, 'plays':0}
}
create_slot_machines()
{‘A’: {‘payouts’: 0, ‘plays’: 0, ‘true_payout_rate’: 0.1},
‘B’: {‘payouts’: 0, ‘plays’: 0, ‘true_payout_rate’: 0.05},
‘ C ‘: {‘ payouts ‘: 0,’ plays ‘: 0,’ true_payout_rate ‘: 0.01}}
These are the true likelihoods for each slot machine. Our multi-armed bandit algorithm won’t know about them. We just use them to decide if we let the machine pay out. We will also track the stats on how each machine has performed.
Now if the simulation works, what we should see is the best slot machine getting played a lot more than the worst, and the middle one getting somewhere in between them.
In[43]:
from numpy.random import beta
from random import random
def sample_likelihood(machine_info):
payouts = machine_info['payouts']
plays = machine_info['plays']
return beta(1 + plays, 1 + plays - payouts, 1)[0]
def machine_to_play(machines):
expected_likelihoods = [(name, sample_likelihood(machine_info)) for name, machine_info in machines.iteritems()]
expected_likelihoods.sort(key=lambda element: element[1], reverse=True)
return expected_likelihoods[:1][0][0]
def play_machine(chosen_machine, slot_machines):
decision_number = random()
slot_machines[chosen_machine]['plays'] += 1
if decision_number <= slot_machines[chosen_machine]['true_payout_rate']:
slot_machines[chosen_machine]['payouts'] += 1
def run_sim(iterations=1000):
slot_machines = create_slot_machines()
for i in xrange(iterations):
chosen_machine = machine_to_play(slot_machines)
machine_won = play_machine(chosen_machine, slot_machines)
pprint(slot_machines)
run_sim()
{‘A’: {‘true_payout_rate’: 0.1, ‘plays’: 539, ‘payouts’: 50},
‘C’: {‘true_payout_rate’: 0.01, ‘plays’: 199, ‘payouts’: 2},
‘ B ‘: {‘ true_payout_rate ‘: 0,05,’ plays ‘: 262,’ payouts ‘: 8}}
Уф. Таким образом, из 1000 игр этот алгоритм играл на лучшем игровом автомате> 50% времени, а наихудший — <20% времени. Уровень выплат нашего алгоритма до сих пор составляет около 6%. Все еще намного ниже, чем наш идеал в 10%, но, по крайней мере, это лучше, чем два самых низких варианта. Если мы просто выберем слот-автомат случайным образом, мы ожидаем выплату в размере 5,3%, что означает, что мы добиваемся примерно на 14% лучше, чем случайные. Что произойдет, если мы увеличим до 10000?
В работе [48]:
run_sim(10000)
{‘A’: {‘true_payout_rate’: 0.1, ‘plays’: 7576, ‘payouts’: 768},
‘C’: {‘true_payout_rate’: 0.01, ‘plays’: 738, ‘payouts’: 5},
‘ B ‘: {‘ true_payout_rate ‘: 0,05,’ plays ‘: 1686,’ payouts ‘: 88}}
Похоже, что> 75% времени он предпочитает играть на лучшем игровом автомате, а ~ 7% — на худшем. Кроме того, похоже, что наша ставка выплат составляет 8,6% и приближается к нашей идеальной ставке в 10% (наилучшая возможная из всех имеющихся у нас игровых автоматов). Теперь мы работаем на 63% лучше, чем если бы мы просто выбирали игровые автоматы случайным образом!
отражающий
I’m a little surprised to see how long it takes for the algorithm to begin exploiting an option. It doesn’t mean this isn’t optimal but I’m willing to be there are probably some hacks one could make or some general prior knowledge one could feed into the algorithm to improve it. That’s all there is to a simple multi-armed bandit algorithm. Hopefully I’ve explained it well enough that you can think of new ways to apply it on your own. Really it all comes down to an understanding of what the beta function is doing and what the parameters you pass to it mean.
There are probably more optimal and complex ways to go about this as well but MEH! It’s easier to learn something if it can be kept simple.
Thanks for reading!
(Note: This article and the opinions expressed are solely my own and do not represent those of my employer.)