Представьте себе игрока у ряда игровых автоматов. Допустим, у каждой машины есть распределение вероятности выигрыша с заданным средним значением и стандартным отклонением, и вам разрешено играть только определенное количество игр. Затем вы хотите максимизировать свой выигрыш, выиграв наибольшее количество игр, однако вы не знаете распределения вероятностей каждой машины. Чтобы выиграть как можно больше игр, вы можете выбрать одно из двух действий для каждой дополнительной игры: исследовать или использовать.

Чтобы понять эти два варианта, давайте представим, что это три машины, и их распределение вероятностей относится к ожидаемому выигрышу, который вы можете получить, играя в игру на этой машине. Пусть количество игр, в которые мы можем сыграть, равно 120. Распределения вероятностей трех машин показаны ниже. Например, машина 1 имеет средний ожидаемый выигрыш 0,7 со стандартным отклонением 8. Из этого примера мы видим, что наилучший возможный доход, который можно получить, равен 120. Тогда значение сожаления ⍴ представляет собой максимальный доход за вычетом фактического вернуть полученное (⍴ = 120 - r). Цель состоит в том, чтобы получить как можно меньшее значение сожаления.

1. Оптимистично-жадный алгоритм

Исследование означает опробовать каждую из машин достаточное количество раз, чтобы выяснить, какая из них повысит ваши шансы на победу. Вы можете провести все свои 300 игр, изучая машины. Это повлечет за собой выбор случайной машины для каждой игры и отметку ваших результатов. Поскольку есть равные возможности выбора каждой из машин, мы можем предположить, что каждая машина выбрана 40 раз из 120 игр. Тогда каждая машина будет давать отдачу 40μ. Это приведет к значению сожаления, равному 70. См. другие примеры.

Благодаря этой методике мы получили относительно высокое значение сожаления. Это связано с тем, что исследование лишает вас возможности использовать предыдущие знания для принятия решений, на какой машине играть дальше, что принесло бы вам максимально возможную отдачу. Это подчеркивает важность эксплуатации, которая является концепцией Алгоритма Жадности для многоруких бандитов.

2. Оптимистично-жадный алгоритм

Эксплуатация — это использование ваших знаний о том, какая машина принесет наибольший выигрыш, и выбор этой конкретной машины для следующей игры. Чтобы понять этот алгоритм, давайте вернемся к нашему примеру с тремя разными игровыми автоматами. На этот раз мы могли сыграть в каждый игровой автомат по одному разу и отметить наше возвращение. В оставшихся 117 играх мы играли только на той машине, которая давала нам наибольшую отдачу. Теоретически это кажется правдоподобным подходом. Однако, поскольку это вероятностный подход, мы можем в конечном итоге получить самую высокую отдачу от машины, которая не обязательно приведет к самой высокой долгосрочной отдаче. В нашем примере машина 1 имеет самое высокое среднее значение возврата. Однако давайте предположим, что нам не повезло, и когда мы играем на автомате 1, мы получаем доход в размере 0,2. Тогда это будет означать, что мы думаем, что машина с самой высокой доходностью — это машина 2, поскольку ее доходность равна 0,5. Затем мы будем играть на машине 2 в оставшихся 117 играх, и это приведет к значению сожаления 60,5, а не 36,6, если бы мы действительно выбрали машину с наивысшим возвращаемым значением. Это подчеркивает важность разведки. Этот подход называется жадным алгоритмом, поскольку мы постоянно выбираем машину, которая, как мы знаем, дает наилучший результат. Другими словами, мы выбираем «жадно».

Из этого мы видим, что и разведка, и эксплуатация являются важными инструментами для принятия решений при ограниченной информации. Проблема многорукого бандита ставит вопрос, как мы можем сбалансировать разведку и эксплуатацию, чтобы максимизировать нашу прибыль. Существует много алгоритмов, решающих эту проблему, однако я сосредоточусь на эпсилон-жадном алгоритме, который сочетает в себе жадный алгоритм и оптимистический жадный алгоритм, чтобы попытаться найти баланс, который максимизирует вознаграждение.

3. ε-Жадный алгоритм

Цель этого алгоритма — максимизировать выигрыш, балансируя разведку и эксплуатацию. Это включает в себя установку значения эпсилон, обычно около 8–10%, а затем использование этого значения эпсилон, чтобы выбрать, будете ли вы в следующей игре исследовать или использовать. Допустим, эпсилон равен 8%. Тогда для данной игры вероятность использования машины, которая, как вы знаете, в настоящее время является лучшим вариантом, составляет 92 %, а вероятность исследования случайной машины составляет 8 %. Подробнее о эпсилон-жадных алгоритмах.

Из этого мы видим, что этот алгоритм устанавливает некий баланс между разведкой и эксплуатацией, однако выбранный баланс напрямую зависит от выбранного значения эпсилон. Если значение эпсилон равно 0%, то это возвращает нас к эксплуатации только жадного алгоритма. С другой стороны, если эпсилон равен 100%, это возвращает нас к алгоритму только исследования. Итак, какое значение эпсилон приводит к наибольшей отдаче? Я не буду слишком углубляться в то, как можно рассчитать среднее вознаграждение для различных значений эпсилон, однако ниже приведен график, показывающий общую тенденцию вознаграждения по сравнению со значением эпсилон. Подробнее о выборе наилучшего значения эпсилон.

Обсуждение

Проблема многорукого бандита — очень популярная концепция в мире, особенно в машинном обучении в области, называемой подкреплением. Например, когда вы заходите на веб-сайт с рекламой, компьютер должен решить, какую рекламу вам дать, на которую вы, скорее всего, нажмете. Должен ли он попробовать новую рекламу или должен дать вам что-то близкое к тому, на что вы ранее нажимали.

Эта проблема также проявляется в решениях, которые мы принимаем каждый день. Один из них, через который я недавно прошел, — это выбор моей специальности в колледже. Я выбирал между тремя специальностями и посещал занятия по всем трем специальностям, чтобы посмотреть, какие из них приносят мне больше всего счастья. Даже не осознавая этого, я пытался найти баланс между тем, чтобы сразу выбрать специальность или продолжить изучение между тремя специальностями.

Эта проблема сложна, потому что ее нелегко проверить и решить. Когда мы играем в игру на одной из машин, мы не наблюдаем вознаграждений на других машинах, поэтому нам нужно попробовать все остальные машины, чтобы сравнить. И даже в этом случае среднее значение доходности машин не гарантируется, поскольку оно основано на кривой распределения вероятностей. Эта задача является NP-трудной.

Если бы я продолжил этот проект, одной областью, которую я бы исследовал больше, было бы среднее значение сожаления для каждого из трех алгоритмов. Таким образом, я смогу напрямую сравнить, какой алгоритм работает лучше всего. Кроме того, я бы использовал этот подход для поиска сожаления, чтобы рассчитать среднюю доходность при разных значениях эпсилон.

В целом, мне понравилось исследовать эту тему, потому что она возникла из идеи, что люди хотят найти способ обыграть игровые автоматы. Эти машины предназначались для того, чтобы мы побеждали очень редко, поэтому, конечно, они должны были быть очень сложными проблемами. В данном случае это класс наиболее сложных разрешимых задач: NP-сложные задачи. Хотя этот метод не идеален, он показывает, насколько важен выбор правильного алгоритма для решения проблемы.

использованная литература

Лэнгфорд, Джон и Тонг Чжан. «Жадный до эпохи алгоритм для контекстуальных многоруких бандитов». 2021, по состоянию на 19 мая 2021 г.

Робертс, Стив. Бандитские алгоритмы. Medium, 2021 г., https://towardsdatascience.com/bandit-algorithms-34fd7890cb18#0145.

ритвикмат. Многорукий бандит: концепции науки о данных. Youtube.Com, 2021 г., https://www.youtube.com/watch?v=e3L4VocZnnQ&t=480s.