Введение в многорукие бандиты

Авторские права 2021 Авторы TF-Agents.

Вступление

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

Возможно , чистейший примером является проблема , которая одолжила свое имя МАБ: представьте себе , что мы столкнулись с k игровых автоматов (однорукие бандиты), и мы должны выяснить , какой из них имеет лучший выигрыш, а не потерять слишком много денег.

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

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

Многорукие бандиты и обучение с подкреплением

Почему в библиотеке TF-Agents есть MAB Suite? Какая связь между RL и MAB? Многоруких бандитов можно рассматривать как частный случай обучения с подкреплением. Цитирую Введение в RL :

На каждом временном шаге, агент принимает действие на окружающей среду на основе его политика $\pi(a_t|s_t)$, где $s_t$ является текущим наблюдением из окружающей среды, и получает вознаграждение $r_{t+1}$ и следующее наблюдение , $s_{t+1}$ из окружающей среды . Цель состоит в том, чтобы улучшить политику, чтобы максимизировать сумму вознаграждений (возврат).

В общем случае RL, следующее наблюдение $s_{t+1}$ зависит от предыдущего состояния $s_t$ и действия $a_t$ принятого политиками. Эта последняя часть - то, что отделяет MAB от RL: в MAB следующее состояние, которым является наблюдение, не зависит от действия, выбранного агентом.

Это сходство позволяет нам повторно использовать все концепции, существующие в TF-Agents.

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

Грибная среда

В иллюстративных целях мы используем игрушечный пример под названием «Грибная среда». Грибов набор данных ( Schlimmer, 1981 ) состоит из меченых примеров съедобных и ядовитых грибов. Особенности включают формы, цвета, размеры различных частей гриба, а также запах и многое другое.

Набор данных грибов, как и все наборы данных контролируемого обучения, можно превратить в контекстную проблему MAB. Мы используем метод также используется Рикельме и соавт. (2018) . В этом преобразовании агент приобретает черты гриба, решает есть его или нет. Поедание съедобного гриба дает награду +5, в то время как употребление ядовитого гриба дает +5 или -35 с равной вероятностью. Если вы не едите гриб, вы получите 0 наград, независимо от вида гриба. В следующей таблице приведены назначения вознаграждений:

           | edible | poisonous
-----------|--------|----------
eating it  |     +5 | -35 / +5
leaving it |      0 |        0

Агент LinUCB

Чтобы добиться хороших результатов в контекстной бандитской среде, необходимо хорошо оценить функцию вознаграждения за каждое действие с учетом наблюдений. Одна из возможностей - оценить функцию вознаграждения с помощью линейных функций. То есть, для каждого действия $i$, мы пытаемся найти параметр $\theta_i\in\mathbb R^d$ для которых оценка

$r_{t, i} \sim \langle v_t, \theta_i\rangle$

максимально приближены к реальности. Здесь $v_t\in\mathbb R^d$ контекст получил на время шага $t$. Затем, если агент очень уверен в своих оценках, он может выбрать $\arg\max_{1, ..., K}\langle v_t, \theta_k\rangle$ , чтобы получить самую высокую ожидаемую награду.

Как объяснялось выше, простой выбор руки с наилучшей оценкой вознаграждения не приводит к хорошей стратегии. Есть много различных способов смешивать эксплуатации и исследование в линейных оценках агентов, и один из самых известных являются линейным верхним доверительным пределом алгоритма (LinUCB) (смотрите , например , Li и др. 2010 ). LinUCB состоит из двух основных строительных блоков (некоторые детали опущены):

1. Он поддерживает оценки параметров каждого плеча с линейным методом наименьших квадратов: $\hat\theta_i\sim X^+_i r_i$, где $X_i$ и $r_i$ являются уложенные контексты и выгоды раундов , где рука $i$ был выбран, и $()^+$ является псевдо - обратная .
2. Он поддерживает доверительные эллипсоиды определенные обратной ковариационной $X_i^\top X_i$ для приведенных выше оценок.

Основная идея LinUCB - «Оптимизм перед лицом неопределенности». Агент включает разведку, увеличивая оценки на величину, соответствующую дисперсии этих оценок. То есть , где уверенность эллипсоиды входят в картину: для каждой руки, оптимистическая оценка $\hat r_i = \max_{\theta\in E_i}\langle v_t, \theta\rangle$, где $E_i$ является эллипсоид вокруг $\hat\theta_i$. В выбираете агента наиболее перспективная рука $\arg\max_i\hat r_i$.

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

Что дальше?

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