Серия непрерывного обучения

Многорукий бандит: методы решения

Часть 2 из серии "Обучение с подкреплением"

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

- СП Садхгуру

В этом блоге мы обсудим многоруких бандитов, а также увидим, как настроить испытательный стенд для экспериментов. Multi-Armed Bandit помогает нам понять ключевую идею RL в очень упрощенных условиях. Предположим, что задача является стационарной и неассоциативной (см. Часть 1, если вы не поняли этих двух терминов). Соответствующий код доступен на GitHub.

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

K-вооруженный бандит проблема

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

Настройка TestBed

В 10-вооруженном бандите у нас есть набор из 10 действий. Давайте сначала попробуем получить истинное вознаграждение из нормального распределения со средним значением 0 и дисперсией 1. Это одна из проблем бандитов.

Теперь у нас есть настоящие награды, но подождите, обратите внимание на следующую строку. Во время проведения наших экспериментов мы не будем возвращать эти истинные вознаграждения, а когда наш агент выберет действие, мы будем выбирать вознаграждение из нормального распределения со средним значением = True Reward ( соответствует выбранному действию) и дисперсии единицы. Теперь давайте визуализируем, как будет выглядеть такое распределение, когда каждое из 10 плеч выбирается 1000 раз.

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

Заключительные экспериментальные настройки

В приведенном выше разделе мы увидели, как мы создадим проблему с бандитами и как настоящие награды будут использоваться во время экспериментального запуска. Но давайте предположим, что вы разработали очень умный алгоритм обучения - L. Как вы оцените его производительность? Будет ли хорошо решить одну проблему с бандитами и заявить о своем превосходстве? Конечно, нет. Таким образом, мы создадим 2000 различных бандитских задач. Мы выполним 1000 временных шагов для каждой задачи бандита и, в конце концов, усредним доход, полученный на каждом шаге.

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

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

Поиск баланса между разведкой и разработкой

Предположим, что руки с 10 рычагами в нашей задаче о бандите обозначены как 1,2,…, 10. Теперь предположим, что в первый раз вы решили потянуть 5-ю руку, которая принесла вознаграждение r. Что ты будешь делать дальше? Вы можете использовать текущую информацию и продолжать тянуть пятую руку, чтобы получить ту же награду r. Но можем ли мы сделать лучше? Еще 9 рук ждут своего исследования !!! Мы не знаем, стоит ли пробовать какой-либо из них. Итак, отсюда у нас есть два пути:

1. Жадный выбор действий

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

2. Эпсилон-Жадный Выбор Действия

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

Давайте рассмотрим пример, чтобы понять это. Предположим, в задаче о бандите нам разрешено тянуть за руки 1000 раз. Пусть Эпсилон = 0,1. Затем из всех 1000 доступных шагов мы действуем жадно 900 раз, что означает, что мы потянем руку с максимальной известной наградой на этом временном шаге. Для остальных шагов (100 = 0,1 * 1000) мы игнорируем нашу текущую информацию о вознаграждении и просто случайным образом выберем одно из 10 рук с равными вероятностями.

Жадный выбор действия - это частный случай Эпсилон-Жадность с Эпсилон = 0.

В верхнем левом углу этого графика приведены значения Epsilon. Наилучшие результаты (в нашем случае средняя награда за шаг) достигаются при epsilon = 0,1. При выборе дикого высокого значения 0,9 мы получили худший результат на нашем стенде.

Запустите этот блокнот, чтобы изучить жадные и эпсилон-жадные методы.

Оптимистичное начальное значение

Можем ли мы продвигать исследования без использования Epsilon-Greedy?

Оказывается, мы можем сделать это, используя концепцию оптимистического начального значения.

Без оптимистичного начального значения

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

At t = 0, estimated_rewards = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Предположим, что мы нажимаем на первый рычаг и получаем награду 0,2. Таким образом, средняя награда для этой руки будет (0 + 0,2) / 2 = 0,1.

At t = 1, estimated_rewards = [0.1, 0, 0, 0, 0, 0, 0, 0, 0]

Теперь, поскольку мы следуем «Жадному выбору действия» (а не «Эпсилону»), поэтому по мере продвижения в этой игре мы просто продолжаем выбирать первый рычаг. Пусть нажатие первого плеча рычага даст вознаграждение в размере 0,18 (помните, что вознаграждения, выдаваемые во время выполнения, выбираются из истинных вознаграждений). Таким образом, средняя награда для этой руки будет (0 + 0,2 + 0,18) / 3 = 0,126.

At t =2, estimated_rewards = [0.126, 0, 0, 0, 0, 0, 0, 0, 0]

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

С оптимистичным начальным значением

Теперь предположим, что мы инициализируем оценочные вознаграждения со значением +5 каждое. Итак, изначально у нас есть:

At t = 0, estimated_rewards = [5, 5, 5, 5, 5, 5, 5, 5, 5, 5]

Давайте снова предположим, что мы выбираем тянуть первую руку и получаем награду 0,2. Таким образом, средняя награда для этой руки будет (5 + 0,2) / 2 = 2,6.

At t = 1, estimated_rewards = [2.6, 5, 5, 5, 5, 5, 5, 5, 5, 5]

Вы это заметили? Предполагаемое среднее вознаграждение от выбранной руки ниже первоначальных оценок. Так что наш агент будет немного разочарован, и это побудит его изучить другие виды оружия. Теперь жадная политика имеет 9 вариантов (поскольку максимальное значение 5 связано с 9 другими действиями). Предполагая, что ничья разрывается случайным образом, будет выбрано случайное действие из оставшихся 9. Допустим, на этот раз выбрана третья рука. Таким образом, средняя награда для этой руки будет (5 + 0,2) / 2 = 2,6.

At t = 2, estimated_reward = [2.6, 5, 2.6, 5, 5, 5, 5, 5, 5, 5]

Обратите внимание, что при вычислении среднего мы не делим на временной шаг. Скорее знаменатель - это количество раз, когда это конкретное действие было выбрано в прошлом.

Легко заметить, что если мы продолжим этот путь, каждая рука будет исследована хотя бы один раз. Итак, мы увидели, как оптимистичное начальное значение может иметь большое значение. Мы также можем комбинировать технику оптимистичного начального значения с epsilon Greedy.

На приведенном выше графике синяя траектория соответствует жадному выбору действий с оценочным вознаграждением, инициализированным до 5. Красная траектория соответствует эпсилон-жадному с эпсилон = 0,1 и оценкам вознаграждения, инициализированным равным 0.

На приведенном выше графике у нас есть эпсилон-жадные методы выбора действий с оценками вознаграждения, инициализированными разными значениями 0,0, 5,0, -5,0, 10,0 и идентичным значением эпсилон = 0,01.

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

Запустите эту записную книжку, чтобы изучить метод оптимистичного начального значения.

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

Вы могли заметить, что в epsilon-greedy, когда мы выбираем исследование, одно из всех возможных действий выбирается случайным образом с равной вероятностью. Это означает, что во время исследования учитывается даже жадное действие. Давайте посмотрим на идею UCB:

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

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

Q(a): Running Reward Average corresponding to action a.
c > 0: Control the degree of exploration.
t: Time steps that have already taken place.
N(a): Number of times action a has been selected until time t.

Как это помогает в исследовании?

Обратите внимание на второй член в приведенном выше уравнении. Каждый раз, когда вы выбираете действие, квадратный корень вычисляет неопределенность в оценке значения а. Что это обозначает? Предположим, вы никогда не выбирали какое-то действие a, поэтому N (a) = 0. Теоретически это приведет к очень большому количеству. Естественно, что при этом действии массив значений будет максимальным и будет выбран следующим. Каким образом c помогает в исследовании? Если положить c = 0 в приведенное выше уравнение, это сведет его к жадной схеме выбора действий. По мере увеличения значения c неопределенность масштабируется на этот коэффициент. Чем больше неопределенность в каком-либо действии, тем больше значение этого действия будет в нашем массиве, а значит, больше шансов быть выбранным.

На приведенном выше графике мы сравниваем производительность выбора эпсилон-жадного действия с UCB.

На приведенном выше графике показана производительность UCB с c = 0, 2 и 5.

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

Алгоритмы градиентного бандита

Во всех вышеперечисленных методах мы делаем примерно два шага:

1. Compute some estimates of action-value
2. Select actions based on those estimates

Существует еще один метод, с помощью которого мы вычисляем численное предпочтение одного действия над другим на каждом временном шаге. Затем эти числовые предпочтения H (a) используются для вычисления вероятности π (a) совершения действия a в некоторый момент t.

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

На приведенной ниже диаграмме показано, как вычислить числовые предпочтения.

Теперь вопрос в том, как вычислить базовый уровень?

Базовая линия может быть любым скаляром, который не зависит от x, где x - значение случайной переменной 𝐴 (t). Здесь мы рассчитаем нашу базовую линию как среднее вознаграждение за предыдущие шаги (t) независимо от действий (a), предпринятых во время этих шагов. Итак, предположим, что награды, полученные на шагах t = 1,2,3, равны 5,20,35 соответственно, тогда новая базовая линия для t = 4 будет (5 + 20 + 35) / 3 = 20.

Нижние правые метки записываются в следующем формате:

( learning_rate , whether baseline is applied or not? )

Как мы видим, при примененной базовой линии = True производительность намного лучше, чем в противном случае.

Запустите этот блокнот, чтобы изучить метод Gradient Bandit.

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

КТО ЭТОТ ПАРЕНЬ?

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

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

  1. Обучение с подкреплением - Введение.
  2. Репозиторий Github, соответствующий этому блогу, находится здесь.

Чтобы оставить отзыв, напишите на [email protected]. Узнайте больше о наших текущих исследованиях на https://research.fynd.com/.

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