Задача многорукого бандита — это классическая задача обучения с подкреплением для решения проблемы выбора наилучшего выбора в условиях неопределенности.

Что такое многорукий бандит?

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

Исследуй-эксплуатируй компромисс

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

Теперь давайте разберемся с этим на более практическом примере. Например, у нас есть 2 объявления и нам нужно решить, какое из них привлечет больше клиентов. Теперь решение о том, какой из них лучше, можно определить по рейтингу кликов (CTR).

CTR = (Общее количество кликов / Общее количество показов) * 100

Чтобы получить точную меру CTR, нам нужно показать как можно больше рекламных объявлений, потому что чем больше данных мы соберем, тем больше будет сокращаться наш доверительный интервал.

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

Чтобы найти лучший выбор с минимальным количеством образцов, у нас есть различные математические методы, которые мы обсудим в этой статье.

Эпсилон-жадный подход

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

В эпсилон-жадном подходе небольшое число определяется как эпсилон, которое представляет собой вероятность исследования (E), и для каждой выборки выбирается другое случайное число вероятности (p), которое решает между исследованием и использованием. Теперь, если случайное число (p) больше, чем эпсилон, мы выбираем бандита, который кажется лучшим до этого момента, чтобы провести над ним эксперимент и обновить среднее значение этого бандита, которое является эксплуатацией. Если он меньше, чем Эпсилон, мы выбираем случайного бандита из всех вариантов для эксперимента «Исследование». Обычно вероятность Эпсилон принимается близкой к 10%.

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

Теперь давайте посмотрим на реализацию этого подхода на Python.

Приведенный выше код показывает код выбора бандита в цикле «для», где «вероятность» — это случайная вероятность выбора между разведкой и эксплуатацией, которая затем сравнивается с эпсилон, которая в данном случае составляет 10%. После выбора бандита он используется для генерации результата бандита для этой итерации, а затем обновляется в общем среднем значении бандита.

Теперь давайте построим кумулятивное среднее вознаграждений по отношению к стандартному среднему значению каждого бандита. На этом графике стандартное среднее значение 3 бандитов равно 1, 2 и 3.

Полный код этого подхода можно найти здесь.

Алгоритм эпсилон-жадности действительно прост в реализации, но алгоритм наследует случайность, которая делает алгоритм непредсказуемым при выборе лучшего бандита каждый раз в ограниченном количестве выборок. Мы можем приблизиться к лучшему бандиту с большим количеством образцов, но это приведет к ненужному исследованию бандитов. Для эпсилон 0,1 и очень больших данных после определенных экспериментов мы в конечном итоге будем проводить исследование в 10% случаев, даже если найдем лучшего бандита. Кроме того, бандитский подход не полностью сходится к лучшему бандиту в ограниченных выборках, которые мы видим на рисунке 1.

Оптимистичный подход к начальной стоимости

Оптимистическое начальное значение лучше подходит для задачи о многоруком бандите. Этот подход устраняет случайность эпсилон-жадного подхода.

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

Теперь давайте посмотрим на реализацию подхода на Python.

При реализации подхода все параметры, а также pull_arm и update_mean класса бандита будут одинаковыми, кроме начального среднего значения. Начальное среднее значение будет инициализировано числом, превышающим ожидаемое_среднее значение.

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

Теперь давайте сравним производительность Epsilon_greedy с 0,1 эпсилон и Optimum_initial_value для 10000 выборок.

Как мы видим на рисунке 2, подход Optimum_initial_value сходится быстрее и ближе к правильному бандиту, чем подход Epsilon_greedy. Хотя epsilon_greedy работает хуже, чем начальное значение Optimistic, мы можем настроить значение epsilon, чтобы улучшить его производительность.

Итак, вот два метода решения дилеммы «исследуй-эксплуатируй». В следующей статье мы обсудим другие методы решения дилеммы «исследуй-эксплуатируй».