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

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

Я рад, что вы спросили.

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

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

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

Что такое проблема многоруких бандитов (MABP)?

Бандитом считается тот, кто ворует ваши деньги. Однорукий бандит - это простой игровой автомат, в котором вы вставляете монету в автомат, нажимаете на рычаг и сразу получаете вознаграждение. Но почему его называют бандитом? Оказывается, все казино настраивают эти игровые автоматы таким образом, что все игроки в конечном итоге теряют деньги!

Многорукий бандит - это сложный игровой автомат, в котором вместо одного есть несколько рычагов, которые игрок может потянуть, причем каждый рычаг дает разную отдачу. Распределение вероятности вознаграждения, соответствующее каждому рычагу, разное и неизвестно игроку.

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

Разведка и эксплуатация в контексте Bernoulli MABP

В приведенной ниже таблице показаны результаты выборки для пятирукого бандита Бернулли с руками, обозначенными цифрами 1, 2, 3, 4 и 5:

Это называется Бернулли, так как возвращаемое вознаграждение равно 1 или 0. В этом примере похоже, что рука номер 3 дает максимальную отдачу, и, следовательно, одна идея состоит в том, чтобы продолжать играть этой рукой, чтобы получить максимальное вознаграждение (чистая эксплуатация ).

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

Случаи применения

Алгоритмы Bandit используются во многих исследовательских проектах в отрасли. В этом разделе я перечислил некоторые из их вариантов использования.

Клинические испытания

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

Сетевая маршрутизация

Маршрутизация - это процесс выбора пути для трафика в сети, такой как телефонные сети или компьютерные сети (Интернет). Выделение каналов нужным пользователям, чтобы общая пропускная способность была максимальной, можно сформулировать как MABP.

Он-лайн реклама

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

Дизайн игр

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

Стратегии решения

В этом разделе мы обсудим некоторые стратегии решения проблемы многорукого бандита. Но перед этим давайте познакомимся с несколькими терминами, которые мы будем использовать в дальнейшем.

Действие-значение Функция

Ожидаемый выигрыш или ожидаемое вознаграждение также можно назвать функцией ценности действия. Он представлен q (a) и определяет среднее вознаграждение за каждое действие в момент времени t.

Предположим, вероятности награды для K-вооруженного бандита задаются как {P1, P2, P3 …… Pk}. Если ая рука выбрана в момент времени t, то Qt (a) = Pi.

Вопрос в том, как нам решить, лучше ли данная стратегия, чем остальные? Один из способов напрямую - сравнить общую или среднюю награду, которую мы получаем для каждой стратегии после n испытаний. Если мы уже знаем, какое действие лучше всего подходит для данной проблемы с бандитом, то интересный способ взглянуть на это - это концепция сожаления.

Сожалеть

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

Но в реальной постановке задачи нам нужно проводить повторные испытания, вытягивая разные руки, пока мы не будем приблизительно уверены в том, какая рука будет тянуть, чтобы получить максимальную среднюю отдачу за раз t. Убыток, который мы понесем из-за времени / раундов, потраченных на обучение, называется сожалением. Другими словами, мы хотим максимизировать мое вознаграждение даже на этапе обучения. Сожаление названо очень удачно, поскольку оно точно определяет, насколько вы сожалеете о том, что не выбрали оптимальную руку.

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

В зависимости от того, как проводится разведка, есть несколько способов решить MABP. Далее мы обсудим некоторые возможные стратегии решения.

Нет исследования (жадный подход)

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

Затем он выбирает действие на каждом временном шаге, которое максимизирует указанное выше выражение, заданное следующим образом:

Однако для оценки этого выражения в каждый момент времени t нам нужно будет выполнять вычисления для всей истории вознаграждений. Этого можно избежать, если рассчитать текущую сумму. Таким образом, в каждый момент времени t значение q для каждого действия может быть вычислено с использованием вознаграждения:

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

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

Одно из возможных решений - это сейчас, и тогда мы сможем изучить новые действия, чтобы убедиться, что мы не упускаем лучший выбор руки. С вероятностью эпсилон мы выберем случайное действие (исследование) и выберем действие с максимальным qt (a) с вероятностью 1-эпсилон.

С вероятностью 1 - эпсилон - выбираем действие с максимальным значением (argmaxa Qt (a))

С вероятностью эпсилон - мы случайным образом выбираем действие из набора всех действий A

Например, если у нас есть проблема с двумя действиями - A и B, жадный алгоритм epsilon работает, как показано ниже:

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

Softmax Exploration

Решение состоит в том, чтобы сделать вероятность выбора действия пропорциональной q. Это можно сделать с помощью функции softmax, где вероятность выбора действия a на каждом шаге задается следующим выражением:

Разложившийся Эпсилон Жадный

Значение epsilon очень важно при принятии решения о том, насколько хорошо epsilon greedy работает для данной проблемы. Мы можем избежать установки этого значения, если оставим эпсилон зависимым от времени. Например, эпсилон можно оставить равным 1 / log (t + 0,00001). С течением времени он будет уменьшаться до такой степени, что мы начинаем исследовать все меньше и меньше, поскольку мы становимся более уверенными в оптимальном действии или руке.

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

Верхняя граница уверенности

Верхняя граница уверенности (UCB) - наиболее широко используемый метод решения проблем многоруких бандитов. Этот алгоритм основан на принципе оптимизма перед лицом неопределенности.

Другими словами, чем больше мы не уверены в руке, тем важнее становится ее исследовать.

  • Распределение функций ценность-действие для 3 различных рук a1, a2 и a3 после нескольких испытаний показано на рисунке выше. Это распределение показывает, что значение действия для a1 имеет наибольшую дисперсию и, следовательно, максимальную неопределенность.
  • UCB говорит, что мы должны выбрать руку a1 и получить вознаграждение, что сделает нас менее неуверенными в ее ценности действия. Для следующего испытания / временного шага, если мы все еще очень не уверены в a1, мы будем выбирать его снова, пока неопределенность не снизится ниже порогового значения.

Интуитивная причина, по которой это работает, заключается в том, что при таком оптимистическом действии происходит одно из двух:

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

UCB - это фактически семейство алгоритмов. Здесь мы обсудим UCB1.

Шаги, связанные с UCB1:

  • Выполните каждое из K действий один раз, задав начальные значения средних наград, соответствующих каждому действию в
  • Для каждого раунда t = K:
  • Пусть Nt (a) представляет количество раз, когда действие a было сыграно до сих пор
  • Воспроизвести действие при максимальном увеличении следующего выражения:

  • Наблюдайте за вознаграждением и обновляйте среднее вознаграждение или ожидаемую выплату за выбранное действие

Мы не будем вдаваться в математическое доказательство UCB. Однако важно понимать выражение, которое соответствует выбранному нами действию. Помните, что при случайном исследовании у нас было только Q (a) для максимизации, а здесь у нас есть два члена. Первый - это функция ценности действия, а второй - показатель уверенности.

  • Каждый раз, когда выбирается a, неопределенность предположительно уменьшается: Nt (a) увеличивается, и, как указано в знаменателе, член неопределенности уменьшается.

  • С другой стороны, каждый раз, когда выбирается действие, отличное от a, t увеличивается, а Nt (a) - нет; поскольку t появляется в числителе, оценка неопределенности увеличивается.

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

Сравнение с сожалением

Среди всех алгоритмов, приведенных в этой статье, только алгоритм UCB обеспечивает стратегию, при которой сожаление увеличивается как log (t), в то время как в других алгоритмах мы получаем линейное сожаление с разными наклонами.

Проблемы с нестационарными бандитами

Важное предположение, которое мы делаем здесь, заключается в том, что мы работаем с одним и тем же бандитом, и распределения, из которых отбираются награды на каждом временном шаге, остаются неизменными. Это называется стационарной задачей. Чтобы объяснить это на другом примере, предположим, что вы получаете вознаграждение в размере 1 каждый раз, когда бросается монета, и в результате получается голова. Скажем, после 1000 подбрасываний монеты из-за износа монета становится смещенной, тогда это становится нестационарной проблемой.

Для решения нестационарной проблемы будут важны более свежие образцы, и, следовательно, мы могли бы использовать постоянный коэффициент дисконтирования альфа, и мы можем переписать уравнение обновления следующим образом:

Обратите внимание, что мы заменили Nt (at) здесь на постоянную альфа, которая гарантирует, что последним выборкам будут присвоены более высокие веса, а приращения будут больше определяться такими недавними выборками. Есть и другие методы, которые предлагают бандитам разные решения с нестационарными наградами. Подробнее о них вы можете прочитать в этой газете.

Реализация Python с нуля для оптимизации CTR рекламы

Как упоминалось в разделе вариантов использования, MABP имеет множество приложений в области интернет-рекламы.

Предположим, рекламная компания размещает на веб-странице 10 различных объявлений, ориентированных на одинаковую аудиторию. У нас есть результаты, по которым пользователь нажимал на рекламу здесь. Индекс каждого столбца представляет собой отдельное объявление. У нас есть 1, если на объявление нажал пользователь, и 0, если это не так. Ниже показан образец исходного набора данных:

Это смоделированный набор данных, и в нем указано объявление № 5, которое дает максимальное вознаграждение.

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

# Random Selection

# Importing the libraries
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd

# Importing the dataset
dataset = pd.read_csv('Ads_Optimisation.csv')

# Implementing Random Selection
import random
N = 10000
d = 10
ads_selected = []
total_reward = 0
for n in range(0, N):
    ad = random.randrange(d)
    ads_selected.append(ad)
    reward = dataset.values[n, ad]
    total_reward = total_reward + reward

Общее вознаграждение за алгоритм случайного выбора составляет 1170. Поскольку этот алгоритм ничего не изучает, он не будет разумно выбирать рекламу, дающую максимальную отдачу. И, следовательно, даже если мы посмотрим на последние 1000 испытаний, он не сможет найти оптимальную рекламу.

Теперь давайте попробуем сделать то же самое с помощью алгоритма верхней границы уверенности:

# Implementing UCB
import math
N = 10000
d = 10
ads_selected = []
numbers_of_selections = [0] * d
sums_of_reward = [0] * d
total_reward = 0

for n in range(0, N):
    ad = 0
    max_upper_bound = 0
    for i in range(0, d):
        if (numbers_of_selections[i] > 0):
            average_reward = sums_of_reward[i] / numbers_of_selections[i]
            delta_i = math.sqrt(2 * math.log(n+1) / numbers_of_selections[i])
            upper_bound = average_reward + delta_i
        else:
            upper_bound = 1e400
        if upper_bound > max_upper_bound:
            max_upper_bound = upper_bound
            ad = i
    ads_selected.append(ad)
    numbers_of_selections[ad] += 1
    reward = dataset.values[n, ad]
    sums_of_reward[ad] += reward
    total_reward += reward

total_reward для UCB составляет 2125. Ясно, что это намного лучше, чем случайный выбор, и действительно умный метод исследования, который может значительно улучшить нашу стратегию решения MABP.

Всего после 1500 испытаний UCB уже отдает предпочтение объявлению № 5 (индекс 4), которое оказывается оптимальным рекламным объявлением и получает максимальную отдачу от данной проблемы.

Конечные заметки

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

Забегая вперед, есть и другие методы, основанные на вероятностных моделях, такие как выборка Томпсона, объясненная профессором Балараманом в этом удивительном видео.

Вы также можете посетить долгожданный и чрезвычайно полезный доклад об обучении с подкреплением от него на DataHack Summit 2018 в Бангалоре! Для получения дополнительной информации посетите https://www.analyticsvidhya.com/datahack-summit-2018/.

Первоначально опубликовано на www.analyticsvidhya.com 24 сентября 2018 г.