Задача о многоруком бандите

Урок разбирает многорукого бандита — простейшую модель, на которой видно ядро RL без сложностей с состояниями.

Многорукий бандит (multi-armed bandit) — задача, где есть несколько «рычагов», каждый даёт случайную награду с неизвестным средним; нужно за ограниченное число попыток набрать как можно больше награды.

Почему именно бандит

Название — от «однорукого бандита», игрового автомата. Представьте ряд автоматов с разной (неизвестной) щедростью. У вас ограниченное число монет. Какой автомат дёргать? Это RL в чистом виде, но без состояний: ситуация всегда одна и та же, важен только выбор действия. Поэтому бандит — идеальный полигон, чтобы понять дилемму исследования и использования отдельно от всего остального.

Оценка ценности рычага

Агент не знает истинных средних наград и оценивает их по опыту — усредняя полученные награды. Чтобы не хранить всю историю, используют инкрементальное среднее: новая оценка = старая + (награда − старая)/число проб. Эта же формула — частный случай обновления, которое мы увидим в Q-learning.

import random
random.seed(0)

# Три автомата с вероятностью выигрыша. Истинные значения агенту неизвестны.
true_probs = [0.2, 0.5, 0.75]
n = len(true_probs)
counts = [0] * n       # сколько раз дёргали рычаг
values = [0.0] * n     # оценка средней награды
eps = 0.1

for t in range(2000):
    if random.random() < eps:
        arm = random.randint(0, n - 1)                  # исследуем
    else:
        arm = max(range(n), key=lambda x: values[x])    # используем лучший
    reward = 1.0 if random.random() < true_probs[arm] else 0.0
    counts[arm] += 1
    values[arm] += (reward - values[arm]) / counts[arm] # инкрементальное среднее

print("Оценки ценности автоматов:", [round(v, 2) for v in values])
print("Сколько раз дёргали каждый:", counts)
print("Лучший автомат по оценке:", max(range(n), key=lambda x: values[x]))

Вывод:

Оценки ценности автоматов: [0.19, 0.4, 0.76]
Сколько раз дёргали каждый: [110, 62, 1828]
Лучший автомат по оценке: 2

Агент сошёлся к истинным вероятностям (0.2/0.5/0.75 ≈ 0.19/0.4/0.76) и большую часть попыток отдал лучшему автомату, но всё же иногда проверял остальные — благодаря epsilon-исследованию.

Как работает под капотом

Качество стратегии в бандите измеряют сожалением (regret) — разницей между наградой идеального игрока (всегда лучший автомат) и реальной наградой агента. Хорошая стратегия (например, UCB) делает сожаление растущим логарифмически: чем дольше играем, тем меньше относительная потеря. Бандиты с состояниями (contextual bandits) — мостик к полноценному RL: там награда зависит ещё и от контекста, как в рекламе и рекомендациях.

Частые ошибки

• Считать среднее по всей истории заново. Это медленно и затратно по памяти; инкрементальная формула обновляет оценку за O(1).
• Игнорировать дисперсию. Автомат с высокой средней наградой, но огромным разбросом, может потребовать больше проб, чтобы это подтвердить.
• Думать, что бандит — это «не настоящий RL». Бандит — частный случай RL с одним состоянием; на нём проще всего изучать исследование.

Итоги

• Многорукий бандит — RL без состояний: важен только выбор действия.
• Ценность рычага оценивают инкрементальным средним полученных наград.
• Метрика качества — сожаление (regret); contextual bandits ведут к полноценному RL.