Проблема заклинювання
Бандит, що постійно виграє
Звичайний UCB1 перераховує оцінки на кожному кроці. Вибирає один важіль. Тягне його. Оновлює n_k та mean_reward(k). Повторює. У довгому тренуванні з багатьма джерелами один важіль може зібрати серію високих винагород, підняти свою середню та стати майже неможливим для перевершення. Інші важелі застають на низькому n_k зі застарілими середніми. Заклинювання.
Заклинювання шкодить ANDREA двома способами:
1. Колапс різноманітності. Модель, яка навчається 90% кроків на одному джерелі, вивчає стилістичні особливості цього джерела. Згенеровані зразки зсуваються до повторюваних патернів, що відповідають домінуючому джерелу.
2. Застаріле дослідження. Руки з застарілими середніми значеннями не можуть відновитися. Рука, чиє середнє значення впало на початку, залишається закріпленою на цьому значенні, навіть якщо модель тепер має достатню ємність для отримання винагороди з неї.
Фаза купує час
Рішення: утримувати фіксований набір фокусних рук на фазу (кілька кроків) перед переоцінкою. Фаза з 14 кроків означає, що 14 прямих проходжень впливають на ті самі фокусні руки. Середні винагороди стабілізуються. Стохастичний шум усереднюється. Потім бандит перекидає кубики.
Змінна довжина фази
ANDREA випадково обирає довжину фази з {7, 14, 21, 28, 42} кроків на кожній межі фази. П'ять значень, рівномірний випадковий розподіл. Короткі фази (7) швидко реагують на погані вибори; довгі фази (42) дозволяють стабільним наборам фокусу повністю експлуатувати. Стеля обмежує шкоду: щонайбільше 42 кроки витрачаються на погану конфігурацію фокусу перед примусовим перекидом.
Статистика довжини фази
1d3 (2-очний) та 1d4 (3-очний)
Нотація грального кубика
Нотація настільних ігор: NdM означає кидок N кубиків з M гранями кожен. 1d3 кидає один 3-гранний кубик, повертаючи значення з {1, 2, 3}. 1d4 кидає один 4-гранний кубик, повертаючи {1, 2, 3, 4}. ANDREA також дозволяє результат 0 за конвенцією: кидок 0 означає повністю випадкову фазу (без фокусування на рукавах UCB).
Конфігурації 2-очний проти 3-очний
Тренувальна конфігурація ANDREA вибирає один з двох режимів кубиків:
Конфігурація 2-очі (1d3). Можливі кількості ручок фокусу: {0, 1, 2, 3}. Результат 0 зарезервовано для випадкової фази.
Конфігурація 3-очі (1d4). Можливі кількості ручок фокусу: {0, 1, 2, 3, 4}. Більші пули дозволяють більш концентровані фази.
Спочатку випадково, потім UCB
Незалежно від результатів кидків кубиків, ANDREA заповнює слоти фокусу у два проходи:
1. Спочатку випадкові ручки. Випадково рівномірно обирається частка слотів фокусу з усіх доступних ручок. Це змушує комбінаторну різноманітність кожної фази, незалежно від рейтингів UCB.
2. UCB заповнює решту слотів. Обчисліть оцінки UCB1 для рук, які ще не обрані. Візьміть найкращі за рейтингом решту рук, доки не заповниться кількість слотів фокусу.
Спочатку випадковий має значення. Якщо UCB обирає першим, лідер серії завжди займатиме слот. З random-first, навіть найкраща рука UCB може пропустити фазу. Різноманітність залишається гарантованою.
Чисто випадкові фази
Коли кубик показує 0, весь набір фокусу формується з випадкових виборів. UCB нічого не вносить. Близько 25% фаз (1d4) або 33% фаз (1d3) потрапляють сюди. Чисто випадкові фази змушують бандита оновлювати вибірку слабо задіяних рук, зберігаючи чесними оцінки середньої винагороди для всього пулу рук.
Ймовірності результатів кубика
Обмеження шкоди
Погана фаза коштує до 42 кроків
Припустимо, UCB обирає фокусну руку з істинним середнім набагато нижчим за спостережене середнє. Фаза фіксує цю руку. Нагорода залишається низькою на всю фазу. Скільки часу знадобиться бандиту, щоб виправити?
Максимальна довжина фази: 42 кроки. Після 42 кроків фаза закінчується, кубики перекидаються, фокусні руки перетасовуються. Поганий вибір не може тривати довше 42 прямолінійних проходів.
Чому 42 (а не 100, а не 1000)
Довгі фази дозволяють стабілізуватися оцінкам mean_reward. Статистична теорія: дисперсія середнього n зразків зменшується як 1/n. Перехід від 7 зразків до 42 зразків дає 6x більше зразків, sqrt(6) ≈ 2.45x менша стандартна похибка. Після 42 зразків mean_reward лежить приблизно в межах +/-15% від свого істинного значення (залежно від дисперсії винагороди).
Після 42 зразків приріст зменшується: 100 зразків проти 42 = 2.4x більше, sqrt(2.4) ≈ 1.55x менша стандартна похибка. Гранична користь падає, тоді як вартість поганого закріплення зростає. 42 кроки балансують обидва аспекти.
Різноманітність проти збіжності
Короткі фази (7 кроків): оцінки винагород залишаються шумними, але погані вибори коштують мало. Довгі фази (42 кроки): оцінки точні, але погані вибори коштують більше. ANDREA змішує довжини фаз рівномірно, щоб обидва режими з'являлися в кожному тренувальному запуску.
Вартість перебудови Btok
Кожен кордон фази запускає перебудову файлу btok для фокусних рук. Перебудова btok виконується у фоновому потоці; CUDA гаряче перезавантажується при зміні mtime. Перебудова займає секунди; фази повинні тривати достатньо довго, щоб накладні витрати на перебудову залишалися малими. 42 кроки при швидкості тренування ANDREA-120M комфортно перевищують час перебудови.
Роздуми про стелю
Наступне
Що Ви Маєте
Контроль кубиків на основі фаз обгортає UCB1 у три захисні правила: змінна довжина фази (7-42), спочатку випадкові руки, фази випадковості на основі кубиків (25-33% чистої випадковості). Стеля в 42 кроки обмежує шкоду; випадкові фази запобігають заклинюванню; змінні довжини поєднують швидкість реакції з стабільністю оцінки.
Що Залишилося
Звідки походить сигнал винагороди, який живить UCB? Активність 78 (приписування винагороди) показує, як CUDA повідомляє втрати на джерело на кожен крок, як EMA на джерело відстежує винагороду, та чому ANDREA масштабує сирі винагороди в 1000 разів перед подачею в UCB1.
Підлоги та штрафи епох (активність 79) додають подальші захисні правила поверх виводу бандита, забезпечуючи, щоб крихітні джерела не голодували, а великі джерела не повторювалися для меморизації.
Посилання
ANDREA whitepaper, розділ 3.2.