Автор: Шамиль Мамедов Редактура: Дмитрий Раков
Давайте рассмотрим две простые задачи по принятию решений:
Несмотря на свою простоту, эти проблемы показывают всю сложность принятия решений и дилемму между эксплуатацией и исследованиями.
Подобные задачи, где нужно выбирать одно из множества действий для оптимизации определенной цели, называются многорукими бандитами.
В этой статье мы рассмотрим несколько вариантов решения задачи многоруких бандитов.
В английском сленге одноруким бандитом называют игровой автомат (slot machine). Следовательно, многорукие бандиты означают множество игровых автоматов. Если мы дернем ручку одного из $k$ автоматов — получим мгновенное вознаграждение $R$ в виде выигрыша $R=1$ или проигрыша $R = 0$.
Рисунок 1. Однорукий бандит
Рисунок 2. Многорукий бандит
Задачу многоруких бандитов можно свести к обучению с подкреплением (reinforcement learning, RL) — обучению агента, который максимизирует вознаграждение в ожидании, то есть $\mathbb{E}[R_t]$.
Рисунок 3. Многорукие бандиты в контексте обучения с подкреплением
На каждом временном шаге $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)$. А если наши начальные оценки ошибочны? Тогда мы сталкиваемся с проблемой баланса между исследованием и эксплуатацией — проблемой, которая возникает при разработке любых алгоритмов принятия решений.