Наруччя, Тяги, Винагороди
Ряд ігрових автоматів
Уявіть K ігрових автоматів, вирівняних в ряд. Кожен автомат виплачує різну середню винагороду, але ви не знаєте жодної з цих середніх. Кожен крок ви обираєте один автомат, тягнете його важіль & спостерігаєте виплату. Ваша мета: максимізувати загальну винагороду за багато тяг.
Така настройка визначає проблему багатонаружного бандита. K = кількість наручь. Тяга обирає одне наруччя. Винагорода надходить з прихованої дистрибуції того наруччя. mean_reward(k) наруччя k відстежує ковзну середню за тягами k.
Дослідження проти Експлуатації
Два тискові фактори тягнуть один проти одного:
Експлуатація тягне руків'я з найвищим спостережуваним середнім винагородою. Жадібна. Ризик: руків'я, яке виглядало чудово після 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ằm всередині reward band. Tolerable. Тепер n_k=10 (рідкісний arm):
1.4 sqrt(9.21 / 10) = 1.4 0.960 = 1.344
1.344 nằm ПОНАД більшістю спостережуваних mean_rewards. Exploration домінує: рідкісний arm перемагає незалежно від його фактичного mean. З багатьма джерелами & довгими тренуваннями, це заповнює schedule низько-середніми arms.
Виправлення: C=0.5
0.5 sqrt(9.21 / 10) = 0.5 0.960 = 0.480
0.480 знаходиться нижче більшості середніх винагород. Дослідження все ще відбувається (рідкісні важелі все ще отримують бонус), але mean_reward веде. ANDREA більше експлуатує, менше досліджує та уникає домінування дослідження.
Налаштування як інженерія, а не теорія
Книжкова межа припускає винагороди в [0, 1]. Винагороди ANDREA живуть приблизно в [0, 5]. Масштабування константи узгоджує константу з величиною винагороди. Той самий алгоритм, відкаліброване середовище.
Діагностика Домінування Дослідження
Наступне Попереду
Що Ви Маєте
UCB1 обирає важіль з найвищим верхнім bound довіри. Bound комбінує mean_reward (експлуатація) з sqrt(ln(N) / n_k), масштабованою C (дослідження). ANDREA налаштовує C=0.5, бо нагороди за крок у діапазоні 0.5 до 3.0, а підручникове 1.4 заповнює розклад важелями з низьким mean.
Що Залишається
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.