Многорукие бандиты
Введение
Давайте рассмотрим две простые задачи по принятию решений:
- На Netflix выходит новый фильм. Нам нужно выбрать одну из нескольких заставок для привлечения максимального количества зрителей к просмотру этого фильма.
- В больницу поступили новые лекарства для лечения серьезного заболевания. Нам необходимо определить лекарство, которое поможет максимальному числу пациентов.
Несмотря на свою простоту, эти проблемы показывают всю сложность принятия решений и дилемму между эксплуатацией и исследованиями.
Подобные задачи, где нужно выбирать одно из множества действий для оптимизации определенной цели, называются многорукими бандитами.
В этой статье мы рассмотрим несколько вариантов решения задачи многоруких бандитов.
Откуда такое название?
В английском сленге одноруким бандитом называют игровой автомат (slot machine). Следовательно, многорукие бандиты означают множество игровых автоматов. Если мы дернем ручку одного из
Многорукие бандиты как упрощенная задача обучения с подкреплением
Задачу многоруких бандитов можно свести к обучению с подкреплением (reinforcement learning, RL) — обучению агента, который максимизирует вознаграждение в ожидании, то есть \( \mathbb{E}[R_t] \).
На каждом временном шаге \( t \) наш агент должен предпринять действие \( A_t \) и сыграть в одном из \( k \) автоматов. Затем агент получит вознаграждение \( R_{t} \).
Математическое ожидание вознаграждения для конкретного действия называется action-value function.
Оно обозначается следующим образом:
\( q_\star(a) = \mathbb E[R_t | A_t = a]. \)
Если бы мы знали точные значения \( q_\star(a) \), выбор наилучшего действия был бы тривиальным. На практике мы их не знаем — вместо этого у нас есть оценка \( Q_t(a) \) в момент времени \( t \). Как только у нас появятся первые оценки \( Q_t(a) \) для каждого действия, мы можем начать их эксплуатировать и всегда выбирать действие, которое максимизирует \( Q_t(a) \): \( A_t = \underset{a}{\arg \min} \ Q_t(a) \). А если наши начальные оценки ошибочны? Тогда мы сталкиваемся с проблемой баланса между исследованием и эксплуатацией — проблемой, которая возникает при разработке любых алгоритмов принятия решений.
Оценка action-value function
Как мы можем оценить action-value function? Самый простой способ — выборочное среднее:
\( Q_t(a) = \frac{\text{сумма вознаграждений при выборе}\ a \ \text{до}\ t}{\text{сколько раз}\ a\ \text{был выбран до}\ t} = \frac{\sum_{i=1}^{t-1} R_i \cdot \mathbb{1}_{A_i=a}}{\sum_{i=1}^{t-1}\mathbb{1}_{A_i=a}} \)
Например, для выбора заставки на Netflix мы покажем каждую заставку \( m \) раз, а затем разделим общее количество просмотров фильма на количество показов каждой заставки. Необязательно хранить все вознаграждения для каждого действия, ведь мы можем переписать выражение для \( Q_t(a) \) в инкрементной форме:
\( Q_{n+1} = Q_n + \frac{1}{n}\left[R_n — Q_n \right] \)
Вывод выражения для \( Q_{n+1} \)
Рассмотрим оценку action-value function одного конкретного действия:
\( Q_n = \frac{R_1 + R_2\dots + R_{n-1}}{n-1} \).
Новая оценка (оценка после получения нового вознаграждения) равна:
\( \begin{align*} Q_{n+1} &= \frac{1}{n}\sum_{i=1}^{n} R_i \\ &= \frac{1}{n}\left(R_n + \sum_{i=1}^{n-1} R_i \right) \\ &= \frac{1}{n}\left(R_n + \frac{n-1}{n-1}\sum_{i=1}^{n-1} R_i \right) \\ &= \frac{1}{n}\left(R_n + (n-1)Q_n \right) \\ &= Q_n + \frac{1}{n}\left[R_n — Q_n \right]. \end{align*} \)
В общем виде выражение новой оценки \( Q \) можно записать таким образом:
\( NewEstimate \leftarrow OldEstimate + StepSize \underbrace{[Target — OldEstimate]}_{estimation\ error} \)
Формула чем-то напоминает градиентный спуск, где \( [Target-OldEstimate] \) представляет некую оценку градиента \( Q. \)
После первичного исследования для оценки \( Q \) мы можем начать оптимизировать наши решения, например, при помощи жадного алгоритма:
\( A_t = \underset{a}{\arg \max} \ Q_t(a). \)
Какие есть подводные камни? Этот алгоритм оптимизирует вознаграждения на коротком горизонте и не проводит исследований. Иными словами, он принимает не оптимальные решения сейчас, чтобы улучшить оценки action-value function и затем увеличить вознаграждения в долгосрочной перспективе.
Далее мы рассмотрим три алгоритма ( \( \epsilon \)-greedy, UCB и Thompson), которые разными способами пытаются найти баланс между исследованием и эксплуатацией.
\( \epsilon \)-greedy
Самый простой способ непрерывного исследования — принимать оптимальное решение с вероятностью \( 1-\epsilon \) и случайное действие с вероятностью \( \epsilon \). Именно это и делает \( \epsilon \)-жадный алгоритм, который представлен ниже:
Upper Confidence Bound (UCB)
Действительно, \( \epsilon \)-жадный алгоритм не является сильно изощренным. Он не использует неопределенность в оценке action-value function, а просто случайным образом выбирает одно из доступных действий (включая оптимальное). Алгоритм Upper Confidence Bound использует неопределенность для исследования: чем меньше у нас уверенности в оценке \( Q_t(a) \), тем больше мы исследуем действие, ведь оно может оказаться наилучшим решением.
Допустим, у нас есть оценка верхнего доверительного предела для каждого действия:
\( q_\star(a) \leq \underbrace{Q_t(a)}_{\text{оценка среднего}} + \underbrace{U_t(a)}_{\text{оценка верхнего предела}} \)
\( U_t(a) \) зависит от количества раз \( N_t(a) \), когда мы выбирали определенное действие:
- чем меньше \( N_t(a) \), тем больше \( U_t(a) \) и бОльшая неопределенность в \( Q_t(a) \)
- чем больше \( N_t(a) \), тем меньше \( U_t(a) \) и более уверенная оценка \( Q_t(a) \)
С использованием оценки верхнего доверительного предела для значения \( Q_t(a) \) алгоритм UCB выбирает действие следующим образом:
\( A_t = \underset{a}{\arg \min} \left[Q_t(a) + c \sqrt{\frac{\ln t}{N_t(a)}} \right], \)
где параметр \( c \) позволяет пользователю настраивать баланс между эксплуатацией и исследованием.
Говоря простым языком, алгоритм UCB выбирает действие с наибольшим \( U_t(a) \). Поэтому в начале мы активно исследуем, но со временем больше переходим к эксплуатации.
Если вы хотите понять, как выводится выражение для \( U_t(a) \) — можно начать знакомство с неравенства Хёфдинга.
Thompson
Алгоритм UCB предполагает наличие верхнего предела для оценки action-value функции, но не делает предположений о распределении \( Q_t(a) \).
Метод Томпсона относится к Байесовским бандитам и использует апостериорное распределение для исследования.
Чтобы со всем разобраться, давайте рассмотрим Бернулли бандитов (получаемое вознаграждение 0 или 1) и смоделируем не просто среднюю оценку, а распределение среднего значения: \( Q_t(a) \sim p \). Для этого возьмем в качестве распределения бета-распределение (им является и апостериорное распределение). Затем, начиная с некоторого априорного бета-распределения, мы сэмплируем средние значения action-value function для каждого действия и принимаем жадные решения на основе этих оценок. Далее берем за основу полученное вознаграждение и пересчитываем апостериорное распределение action-value function принятого решения.
Почему метод Томпсона работает, когда мы принимаем жадные решения? Потому что для этого мы используем выборку из распределения, а не просто его среднее значение. Это позволяет в начале проводить много исследований для уточнения распределения вознаграждений (как на рисунке ниже).
Заключение
Множество задач по принятию решений можно свести к проблеме многоруких бандитов. Простейший метод их решения начинается с того, что мы пробуем все варианты для оценки action-value function, а затем переходим к эксплуатации наших оценок с помощью жадного алгоритма. Однако в долгосрочной перспективе он не оптимален.
\( \epsilon \)-жадный алгоритм представляет собой простое расширение жадного подхода, который постоянно проводит исследования. С вероятностью \( 1-\epsilon \) он выбирает жадное действие, а с вероятностью \( \epsilon \) — случайное.
Более изощренные алгоритмы, такие как Upper Confidence Bound (UCB) и Thompson, используют неопределенность при оценке action-value function для исследования. UCB моделирует верхний доверительный интервал action-value function, который уменьшается с частотой выбора определенного действия. Алгоритм Томпсона создает распределение action-value function и использует выборку из априорного распределения вместо среднего значения. Это стимулирует нашего агента к исследованиям для уменьшения неопределенности в оценке action-value function.
Ресурсы
