Многорукие бандиты

1. Постановка задачи

k-рукий бандит — задача последовательного выбора действий из конечного множества \(\mathcal{A} = \{1, 2, \ldots, k\}\): на шаге \(t = 1, 2, \ldots\) агент выбирает действие \(A_t \in \mathcal{A}\) («дёргает за рычаг» одного из \(k\) игровых автоматов) и получает случайную награду \(R_t\), распределение которой \(\nu_a\) своё у каждого действия и агенту неизвестно. В стационарной постановке распределения не зависят от времени.

По сравнению с полной задачей RL из конспекта 1 здесь всё упрощено: состояний нет, каждое действие немедленно даёт наблюдаемую награду, и текущее решение не меняет устройство среды. Тем не менее центральная проблема уже возникает: чтобы узнать, какое действие лучшее, нужно пробовать разные, но чтобы максимизировать награду — надо чаще выбирать те, что уже кажутся хорошими. Это конфликт разведки и использования (англ. exploration vs exploitation).

Истинной ценностью действия \(a\) называется математическое ожидание награды при его выборе:

Если бы значения (2.1) были известны, задача была бы тривиальной — всегда выбирать

На практике \(q(a)\) неизвестны, и агент вынужден оценивать их по наблюдаемым наградам.

2. Regret: цена неоптимальных действий

Качество алгоритма естественно измерять накопленными потерями относительно гипотетического агента, который всегда выбирает оптимальное действие. Эта величина называется regret (в строгой терминологии — pseudo-regret, поскольку сравниваются ожидаемые награды); за \(T\) шагов:

Введём число выборов каждого действия и разрыв (англ. gap) каждого действия до оптимума:

Утверждение (разложение regret). Для любого алгоритма

Доказательство. Каждый шаг выбирает ровно одно действие, поэтому \(\sum_a N_T(a) = T\). Сгруппируем сумму наград по действиям: \(\sum_{t=1}^{T} q(A_t) = \sum_a q(a)\, N_T(a)\). Подставляя оба равенства в (2.3):

и взятие математического ожидания обеих частей даёт (2.5). ∎

Формула (2.5) фундаментальна: минимизировать regret — значит ограничить число выборов неоптимальных действий, причём каждый выбор действия \(a\) стоит ровно \(\Delta_a\). Хороший алгоритм имеет \(\langle R_T \rangle = O(\log T)\): тогда regret на шаг убывает как \(O(\log T / T) \to 0\) — алгоритм всё реже ошибается.

3. Жадная и ε-жадная стратегии

Пусть \(Q_t(a)\) — оценка ценности действия \(a\), построенная по наградам, наблюдённым до шага \(t\) (как именно строить — раздел 4). Действие называется жадным, если его оценка максимальна: \(a \in \arg\max_b Q_t(b)\). Стратегия «всегда выбирать жадное действие» (чистая жадная, англ. pure greedy) выглядит естественно, но может застрять навсегда.

Пример. Два автомата, \(q(1) = 1\), \(q(2) = 0{,}9\). Пусть первые наблюдения оказались нетипичными: первый автомат выдал низкую награду, второй — высокую. Жадный алгоритм объявит лучшим второй автомат и почти перестанет выбирать первый — оценка \(Q(1)\) так и останется заниженной, и исправить её будет некому: по разложению (2.5) regret растёт линейно со скоростью \(\Delta_2 = 0{,}1\) за шаг.

Лекарство — принудительная разведка. ε-жадная стратегия:

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

поскольку и в фазе разведки оптимальный рычаг выпадает с вероятностью \(1/k\). Обратная сторона: при фиксированном \(\varepsilon\) разведка не выключается никогда, среднее число случайных неоптимальных выборов пропорционально \(T\), и по (2.5) regret растёт линейно: \(\langle R_T \rangle \ge c\,T\) для некоторой константы \(c > 0\). Поэтому на практике \(\varepsilon\) уменьшают по мере стабилизации оценок \(Q\) — либо по расписанию, либо переключаясь на более умные стратегии.

4. Оценка ценностей по выборке

Естественная оценка ценности — выборочное среднее наград, полученных при выборе действия \(a\):

(ещё не выбиравшимся действиям ставят начальную оценку, например \(Q_1(a) = 0\)). Два свойства этой оценки доказываются в одну строку каждое. Пусть награды действия \(a\) независимы, одинаково распределены, с ожиданием \(q(a)\) и дисперсией \(\sigma_a^2\), и действие выбрано \(n\) раз. Несмещённость: по линейности ожидания

Скорость сходимости: по независимости дисперсия среднего

а по усиленному закону больших чисел \(Q_n(a) \to q(a)\) почти наверное. Оценка честная — вопрос лишь в том, чтобы каждое действие выбиралось достаточно часто (для чего и нужна разведка).

4.1. Инкрементальное обновление

Формула (2.8) в лоб требует хранить все прошлые награды. Выведем пересчёт «на лету». Пусть действие выбрано \(n\) раз с наградами \(r_1, \ldots, r_n\) и \(Q_n = \frac{1}{n}\sum_i r_i\). После награды \(r_{n+1}\):

Хранить нужно только текущее \(Q_n\) и счётчик \(n\). Структура результата важнее самой формулы:

Это общая схема обучения оценок, с которой мы будем встречаться до конца траектории: в (2.11) шаг \(\alpha_n = \frac{1}{n+1}\), в TD-обучении (конспект 4) целью станет «награда + оценка следующего состояния», в Q-обучении (конспект 5) — максимум по действиям. Величину \(R - Q\) — расхождение цели и текущей оценки — там будут называть TD-ошибкой.

4.2. Постоянный шаг и нестационарность

Что если взять в (2.12) постоянный шаг \(\alpha \in (0, 1)\) вместо \(1/n\)? Развернём рекуррентность:

(второе равенство получается подстановкой такого же выражения для \(Q_n\), и так \(n\) раз; строгое обоснование — индукция по \(n\)). Веса наблюдений убывают геометрически с давностью: свежая награда весит \(\alpha\), награда \(m\) шагов назад — \(\alpha(1-\alpha)^m\). Это экспоненциальное сглаживание: оценка «забывает» старое, поэтому постоянный шаг — правильный выбор для нестационарных задач, где ценности рычагов дрейфуют со временем (реклама, рекомендации). Платой служит то, что дисперсия оценки уже не убывает до нуля, как в (2.10), а стабилизируется на уровне порядка \(\alpha \sigma_a^2 / (2 - \alpha)\).

5. Реализация: ε-жадный агент на numpy

Псевдокод из лекции переносится в numpy дословно: инициализировать \(Q\) и \(N\) нулями, на каждом шаге выбрать действие по (2.6), получить награду, обновить счётчик и оценку по (2.11). Тестовая среда — гауссовский 10-armed testbed Саттона–Барто: истинные ценности разыгрываются один раз из \(N(0,1)\), награды шумят вокруг них с единичной дисперсией:

import numpy as np

def run_bandit(eps, T=1000, k=10, rng=None):
    rng = rng or np.random.default_rng()
    q = rng.normal(0, 1, k)          # истинные ценности — формула (2.14)
    a_star = np.argmax(q)            # оптимальный рычаг (агенту неизвестен)

    Q = np.zeros(k)                  # оценки ценностей
    N = np.zeros(k)                  # счётчики выборов
    rewards, optimal = [], []

    for t in range(T):
        if rng.random() < eps:                    # разведка — формула (2.6)
            a = rng.integers(k)
        else:                                     # использование
            a = np.argmax(Q)
        r = q[a] + rng.normal()                   # награда — формула (2.14)
        N[a] += 1
        Q[a] += (r - Q[a]) / N[a]                 # инкрементальное обновление (2.11)
        rewards.append(r)
        optimal.append(a == a_star)
    return np.array(rewards), np.array(optimal)

# усреднение по 200 независимым прогонам для каждой стратегии
for eps in [0.0, 0.01, 0.1]:
    R = np.mean([run_bandit(eps)[0] for _ in range(200)], axis=0)
    print(eps, R[-100:].mean())     # средняя награда в конце обучения

Одиночный прогон почти ни о чём не говорит — кривые шумные, и какая-нибудь стратегия может случайно выиграть. Сравнивают средние по сотням прогонов кривые двух метрик: средняя награда на шаге и доля выборов оптимального действия.

6. Эксперимент Саттона–Барто

Ожидаемая картина из лекции: жадная стратегия стартует неплохо, но застревает на субоптимальных рычагах (~1.0 средней награды, оптимальное действие лишь в трети случаев); ε = 0.1 быстро находит оптимум, но 10 % шагов вечно тратит на разведку; ε = 0.01 разгоняется медленнее, зато на длинном горизонте её плато выше:

Классические кривые 10-armed testbed. Из лекции курса «RL: от бандитов до RLHF»

Контрольные вопросы

• Чем задача бандита проще полной задачи RL из конспекта 1 и что в ней уже есть?
  Нет состояний, награда наблюдается сразу после действия, и действия не меняют среду. Но уже есть центральный конфликт разведки и использования: чтобы узнать лучший рычаг, надо пробовать все, а чтобы зарабатывать — дёргать лучшую.
• Сформулируйте и докажите разложение regret (2.5).
  ⟨R_T⟩ = Σ_a Δ_a⟨N_T(a)⟩. Доказательство: Σ_a N_T(a) = T (каждый шаг — одно действие) и Σ_t q(A_t) = Σ_a q(a)N_T(a) (группировка по действиям); подстановка в определение (2.3) даёт R_T = Σ_a (q* − q(a))N_T(a), после чего берётся ожидание. Смысл: regret = сумма «число выборов плохого рычага × её отставание».
• Почему чисто жадная стратегия может навсегда застрять на неоптимальном действии?
  Ранний шум может занизить оценку лучшего рычага, после чего жадный выбор перестанет её выбирать, а значит — и исправлять её оценку. Ошибка консервируется: разведки, которая могла бы обновить оценку, нет.
• Почему при фиксированном ε regret растёт линейно по T, хотя алгоритм давно нашёл оптимум?
  Разведка не выключается: доля ε шагов навсегда остаётся случайной, из них доля (k−1)/k — неоптимальные действия с положительными разрывами Δ_a. По разложению (2.5) их вклад пропорционален T. Поэтому ε уменьшают по мере стабилизации оценок.
• Выведите инкрементальную формулу обновления выборочного среднего.
  Q_{n+1} = (Σr_i + r_{n+1})/(n+1) = n/(n+1)·Q_n + 1/(n+1)·r_{n+1} = Q_n + (r_{n+1} − Q_n)/(n+1) — формула (2.11). Хранить нужно только Q_n и n; общий вид Q ← Q + α(цель − оценка) станет основой TD-обучения.
• Когда шаг обновления берут постоянным (α = const), а не 1/n, и чем при этом жертвуют?
  В нестационарных задачах: развёртка (2.13) показывает, что при постоянном α веса прошлых наград убывают геометрически — оценка забывает устаревшее и успевает за дрейфом ценностей. Плата: дисперсия оценки не убывает до нуля, а стабилизируется на уровне порядка ασ²/(2−α).
• Почему выборочное среднее — несмещённая оценка ценности и как быстро убывает её разброс?
  По линейности ожидания ⟨Q_n(a)⟩ = (1/n)Σ⟨R_i⟩ = q(a) — формула (2.9). По независимости наград Var(Q_n) = σ²_a/n — (2.10): чтобы вдвое уменьшить разброс, нужно вчетверо больше выборов данного действия.