Руки, Тяги, Вознаграждения
Ряд игровых автоматов
Представьте K игровых автоматов в ряд. Каждый автомат выплачивает разное среднее вознаграждение, но вы не знаете ни одного из средних. На каждом шаге вы выбираете один автомат, тянете его рычаг и наблюдаете выплату. Ваша цель: максимизировать общее вознаграждение за множество тяг.
Эта настройка определяет проблему многорукого бандита. K = количество рук. Тяга выбирает одну руку. Вознаграждение приходит из скрытого распределения этой руки. mean_reward(k) руки k отслеживает скользящее среднее по тягами k.
Исследование vs Эксплуатация
Два давления тянут в противоположных направлениях:
Эксплуатация тянет рычаг с наивысшим наблюдаемым средним вознаграждением. Жадный подход. Риск: рычаг, который выглядел отлично после 2 тяг, может вернуться к более низкому истинному среднему.
Исследование тянет менее протестированный рычаг, чтобы уменьшить неопределённость. Риск: время, потраченное на исследование, стоит вознаграждения, которое можно было собрать с известного хорошего рычага.
Хорошая политика сочетает оба подхода. Чистая эксплуатация навсегда фиксирует ранних победителей. Чистая разведка никогда не собирает вознаграждение.
Руки ANDREA = Источники данных
ANDREA представляет обучение как бандита. Каждый источник данных (hermes3-general, gutenberg, dictionary, synthetic-chat, smoltalk и т.д.) выступает в роли руки. Каждый шаг обучения тянет одну руку: загружает документ из этого источника, проводит прямой проход, наблюдает уменьшение потерь. Среднее вознаграждение на источник отслеживает, насколько этот источник в среднем улучшает потери.
Почему это подходит: потребности модели меняются во время обучения. Ранние шаги выигрывают от широкого охвата (много источников). Поздние шаги выигрывают от целевой полировки (несколько источников с высоким вознаграждением). Бандит адаптируется; фиксированное соотношение выборки не может.
Назови части
Оценка UCB1
Auer, Cesa-Bianchi & Fischer, 2002
Peter Auer и коллеги опубликовали UCB1 в 2002 году как политику бандита с конечным временем и границей сожаления O(log N). UCB1 выбирает руку, комбинируя её текущую среднюю награду с бонусом исследования, который уменьшается по мере тяг руки.
Формула
UCB(k) = mean_reward(k) + C * sqrt(ln(N) / n_k)
По членам:
- mean_reward(k): средняя награда, наблюдаемая для рычага k за его n_k тяг. Член эксплуатации.
- N: общее количество тяг по всем рычагам на данный момент. Растет на каждом шаге.
- n_k: количество тяг конкретно рычага k. Растет только когда k выбран.
- C: константа исследования. Стандартное значение из учебников: 1.4 (sqrt(2)). ANDREA использует C=0.5.
- sqrt(ln(N) / n_k): радиус доверия. Редко тянутый рычаг имеет малое n_k и получает большой бонус; хорошо тянутый рычаг имеет большое n_k и получает малый бонус.
Почему формула работает
ln(N) растет медленно (логарифмически), поэтому числитель плавно увеличивается с общим опытом. n_k в знаменателе уменьшает член по мере накопления доказательств для конкретного рычага. Квадратный корень смягчает реакцию, что не позволяет одному недостаточно исследованному рычагу доминировать вечно.
Выбор по argmax_k UCB(k) на каждом шаге автоматически балансирует оба давления. Нет параметра epsilon, нет расписания, нет температуры. Математика всё решает.
Вычисление оценки UCB
Почему C=0.5 вместо 1.4
Значение из учебника
Auer, Cesa-Bianchi & Fischer выводят границу сожаления, предполагая, что награды лежат в [0, 1]. Граница выполняется для C = sqrt(2) ≈ 1.414. Большинство учебников рекомендуют C=1.4 как безопасное значение по умолчанию.
Величины наград ANDREA
ANDREA сообщает улучшения потерь на шаг как награду. Сырые улучшения составляют около 0.001 (потери падают с 4.521 до 4.520). После множителя масштабирования 1000x (рассматривается в активности 78, атрибуция наград) масштабированные награды имеют величину около 1.0. Средние награды по истории рычага стабилизируются в диапазоне от 0.5 до 3.0.
Теперь рассмотрим бонус исследования при C=1.4 с N=10000, n_k=100:
1.4 sqrt(ln(10000) / 100) = 1.4 sqrt(9.21 / 100) = 1.4 * 0.303 = 0.425
0.425 находится внутри полосы вознаграждения. Допустимо. Теперь n_k=10 (редкий рычаг):
1.4 sqrt(9.21 / 10) = 1.4 0.960 = 1.344
1.344 находится ВЫШЕ большинства наблюдаемых средних вознаграждений. Исследование доминирует: редкий рычаг выигрывает независимо от его реального среднего. При многих источниках и длинных тренировочных запусках это заполняет расписание рычагами с низким средним.
Исправление: C=0.5
0.5 sqrt(9.21 / 10) = 0.5 0.960 = 0.480
0.480 находится ниже большинства средних наград. Исследование всё ещё происходит (редкие рычаги всё ещё получают бонус), но средняя награда лидирует. ANDREA больше эксплуатирует, меньше исследует и избегает доминирования исследования.
Настройка как инженерия, а не теория
Граница из учебника предполагает награды в [0, 1]. Награды ANDREA находятся примерно в [0, 5]. Масштабирование константы подстраивает её под величину наград. Тот же алгоритм, откалиброванная среда.
Диагностика доминирования исследования
Что дальше
Что у вас есть
UCB1 выбирает рычаг с наивысшей верхней границей уверенности. Граница сочетает mean_reward (эксплуатация) с sqrt(ln(N) / n_k), масштабированным по C (исследование). ANDREA настраивает C=0.5, потому что пошаговые награды лежат в диапазоне 0.5–3.0, а учебниковое 1.4 заполняет расписание рычагами с низким средним.
Что осталось
Vanilla UCB1 выбирает один рычаг за раз. ANDREA выбирает несколько фокусных рычагов на фазу, сначала перемешивает случайные рычаги и держит каждую фазу от 7 до 42 шагов. Эта структура (активность 77: фазы кубиков) не даёт UCB перекоммититься к ранним победителям, при этом позволяя сосредоточить усилия.
Приписывание вознаграждения (активность 78) показывает, откуда на самом деле берётся mean_reward(k). Полы и штрафы эпох (активность 79) накладывают защитные правила поверх вывода UCB.
Справка
- Auer, Cesa-Bianchi, Fischer (2002). "Finite-time Analysis of the Multiarmed Bandit Problem." Machine Learning, 47, 235-256.
- Белая книга ANDREA, разделы 3.1 и 3.4.