Absolute Thompson Sampling: новый подход к рандомизированному исследованию в линейных бандитах

В области линейных бандитов, где агент выбирает действия с векторными признаками, традиционные подходы имеют компромиссы: алгоритм Upper Confidence Bound (UCB) прост в анализе, но вычислительно сложен, а Thompson Sampling (TS) эффективен, но труден для теоретического анализа из-за отсутствия гарантированного оптимизма. Исследователи из MIT и других институтов предложили новый метод — Absolute Thompson Sampling (ATS), который решает эту дилемму.

ATS модифицирует стандартный TS, заменяя знаковую случайную добавку (шум) на её абсолютное значение. Это гарантирует, что оценки параметров остаются оптимистичными в ожидании, что позволяет провести простой анализ регрета в стиле UCB. При этом вычислительная сложность не увеличивается — ATS так же легковесен, как и оригинальный TS.

Теоретический анализ показывает, что ATS достигает границы регрета O?(d?/??K), где d — размерность признаков, K — горизонт. Это соответствует лучшим известным границам для TS в линейных бандитах. Таким образом, ATS впервые объединяет вычислительную простоту TS с простотой анализа UCB.

Дополнительно авторы представили ансамблевую версию — Ensemble Absolute Thompson Sampling (EATS). EATS берёт максимум по нескольким абсолютным возмущениям и нормирует на размер ансамбля. При увеличении числа членов ансамбля EATS сходится к UCB-функции. Эксперименты показывают, что даже умеренный размер ансамбля (например, 20) даёт результаты, близкие к UCB по качеству.

Практическая значимость работы в том, что ATS и EATS предоставляют простую и эффективную альтернативу как UCB, так и TS. Методы могут найти применение в рекомендательных системах, онлайн-рекламе и робототехнике, где требуется баланс между исследованием и эксплуатацией. Алгоритмы легко реализовать и они не требуют сложных подстроек гиперпараметров.

Исследование опубликовано на arXiv (ID 2606.28616) и предлагает новый взгляд на связь между рандомизированным исследованием и детерминированным оптимизмом — как теоретически, так и на практике. Результаты открывают путь к более простым и надёжным алгоритмам для обучения с подкреплением в условиях линейной модели.