Online learning и regret bounds

2003 год. Трейдер каждое утро выбирает одну из N акций - не зная завтрашних цен. Через год его потери не должны сильно превышать потери лучшего актива задним числом. Это не предсказание будущего - это управление сожалением.

• Спам-фильтр: паттерны спама меняются еженедельно - IID нарушено, online learning необходим
• Рекомендательные системы: вкусы пользователей дрейфуют, нет фиксированного распределения предпочтений
• Финансовые стратегии: market regime shifts делают исторические IID-предположения несостоятельными

Предварительные знания

• (no prerequisites)

• PAC framework: formalizing 'learning from examples'

Online протокол: предсказание без IID

В PAC-обучении данные приходят из фиксированного неизвестного распределения D. Обучаем модель один раз - и используем. В online learning никакого распределения нет. На каждом шаге t противник (или природа) показывает задачу, мы отвечаем, получаем loss. Распределение может меняться произвольно - или вообще определяться адверсарием, который знает наш алгоритм. PAC-теория здесь молчит.

На каждом шаге t = 1, 2, ..., T: 1. обучающийся выбирает гипотезу h_t из класса H 2. противник открывает функцию потерь l_t: H -> [0,1] 3. обучающийся несёт потерю l_t(h_t). Единственное ограничение: противник фиксирует l_t до того, как видит h_t (oblivious adversary). Цель: минимизировать суммарные потери sum_{t=1}^T l_t(h_t).

Что значит «хорошо» в этом протоколе? Сравниваться с нулевыми потерями бессмысленно - адверсарий может сделать любую гипотезу плохой на любом шаге. Но можно сравниваться с лучшей фиксированной гипотезой, которую мы бы выбрали, знай мы всё заранее.

Regret после T шагов: R_T = sum_{t=1}^T l_t(h_t) - min_{h in H} sum_{t=1}^T l_t(h). Это разрыв между тем, что набрал алгоритм, и тем, что набрала бы лучшая фиксированная стратегия задним числом. Цель: sublinear regret, R_T = o(T). Тогда среднее сожаление R_T/T стремится к нулю.

Первая идея: Follow-the-Leader (FTL). На каждом шаге выбирай гипотезу, которая лучше всего сработала в прошлом: h_t = argmin_{h} sum_{s=1}^{t-1} l_s(h). Звучит разумно - и легко ломается.

N = 2 гипотезы: h1 и h2. Шаг 1: l_1(h1) = 0, l_1(h2) = 1. FTL выбирает h1 на шаге 2. Шаг 2: l_2(h1) = 1, l_2(h2) = 0. FTL переключается на h2. Шаг 3: l_3(h1) = 0, l_3(h2) = 1. FTL снова переключается. На каждом чётном шаге FTL несёт потерю 1. Лучшая фиксированная стратегия несёт T/2. Regret FTL = T/2 - линейный, не sublinear.

Провал FTL - не случайность. Детерминированный алгоритм всегда можно обмануть адверсарием, знающим его стратегию. Выход - рандомизация (распределение над гипотезами) или регуляризация (штраф за резкие переключения).

Hedge: мультипликативные веса и O(sqrt(T log N)) regret

Фройнд и Шапир в 1997 году предложили алгоритм Hedge. Идея: не выбирать одну гипотезу детерминированно, а поддерживать вероятностное распределение над N гипотезами и сэмплировать из него.

Инициализация: w_{1,i} = 1 для всех i = 1,...,N. На шаге t: 1. вычисли вероятности p_{t,i} = w_{t,i} / sum_j w_{t,j} 2. выбери гипотезу i_t ~ p_t 3. понеси ожидаемую потерю E[l_t] = sum_i p_{t,i} l_t(i) 4. обнови веса: w_{t+1,i} = w_{t,i} * exp(-eta * l_t(i)). Параметр eta > 0 - learning rate.

Обновление мультипликативное: хорошие эксперты теряют вес медленно, плохие - быстро. При большом eta алгоритм почти детерминированный (жадный, как FTL). При маленьком eta - почти равномерный (медленно адаптируется). Оптимальный eta балансирует эти крайности.

Теорема (Freund-Schapire 1997): для eta = sqrt(2 ln N / T) алгоритм Hedge гарантирует E[R_T] <= sqrt(T/2 * ln N) = O(sqrt(T ln N)). Sublinear по T и логарифмический по N - можно работать с огромным пространством гипотез.

Скетч доказательства через потенциал. Пусть W_t = sum_i w_{t,i}. Тогда W_{T+1} / W_1 = prod_t (W_{t+1}/W_t). С одной стороны: W_{T+1} >= w_{T+1,i*} = exp(-eta * sum_t l_t(i*)) для лучшего эксперта i*. С другой: W_{t+1}/W_t = sum_i p_{t,i} exp(-eta l_t(i)) <= exp(-eta E_t[l_t] + eta^2/8) по неравенству Хёфдинга. Телескопируем, делим на eta - получаем bound.

Нижняя граница: любой алгоритм (включая рандомизированные) несёт regret Omega(sqrt(T log N)) на некотором адверсарном входе. Hedge оптимален с точностью до константы.

Из вывода видно: Hedge не превышает теоретический bound, и при N=100 логарифм ln(100) ≈ 4.6 - умеренная цена за гибкость выбирать из ста гипотез. FTL при N=2 показывает линейный regret, как и предсказывает анализ.

FTRL, online-to-batch, bandits и связь с RL

Hedge - частный случай более общего принципа: Follow-the-Regularized-Leader (FTRL). FTL проигрывал из-за нестабильности переключений. Добавим регуляризатор - нестабильность исчезнет.

На каждом шаге t выбираем: h_t = argmin_{h in H} [sum_{s=1}^{t-1} l_s(h) + (1/eta) * R(h)], где R(h) - строго выпуклый регуляризатор. С энтропийным регуляризатором R(p) = sum_i p_i ln p_i получаем Hedge. С L2 регуляризатором R(w) = ||w||^2 / 2 получаем online gradient descent.

Регуляризатор удерживает h_t близко к предыдущему выбору, не позволяя резко переключаться из-за одного плохого шага. Это устраняет слабость FTL. Общий regret bound для FTRL с подходящим R: R_T = O(sqrt(T)) - та же скорость, что у Hedge, в более общей постановке.

Если данные всё-таки IID (PAC-обстановка), online алгоритм даёт PAC-гарантию. Теорема: пусть h_bar = (1/T) sum_{t=1}^T h_t - равновзвешенная смесь онлайн-гипотез. Тогда E[L_D(h_bar)] <= min_h L_D(h) + R_T/T. Если R_T = O(sqrt(T ln N)), то gap = O(1/sqrt(T)) - стандартная PAC-скорость.

Это мост между двумя мирами: online алгоритм с sublinear regret автоматически становится PAC-алгоритмом при IID данных. Online learning строже - работает без предположения о распределении.

В Hedge на каждом шаге видны потери всех N экспертов. В bandit задаче видна только потеря выбранного эксперта - как в многоруком бандите. Нужно балансировать exploration и exploitation. Алгоритм EXP3 даёт regret O(sqrt(T * N * ln N)) - на sqrt(N) хуже Hedge из-за неполной информации.

Если оба игрока в игре с нулевой суммой используют Hedge, их смешанные стратегии сходятся к Nash equilibrium. Regret алгоритма = duality gap игры. Это алгоритмическое доказательство minimax теоремы: min_x max_y f(x,y) = max_y min_x f(x,y). В RL: Q-learning можно рассматривать как online gradient descent в пространстве value functions; policy gradient методы используют те же идеи мультипликативных весов.

Из вывода видно: разрыв между риском h_bar и лучшим экспертом задним числом не превышает R_T/T - ровно как предсказывает теорема. При T -> inf разрыв стремится к нулю без каких-либо предположений о форме распределения.

Главное

• Online learning не требует IID: на каждом шаге learner предсказывает, видит потерю, противник может быть адверсарным
• Regret R_T = sum l_t(h_t) - min_h sum l_t(h) - разрыв с лучшей фиксированной стратегией задним числом; цель - sublinear R_T = o(T)
• FTL проигрывает на адверсарных последовательностях - линейный regret; нужна рандомизация или регуляризация
• Hedge (мультипликативные веса): w_{t+1,i} = w_{t,i} * exp(-eta * l_t(i)), regret O(sqrt(T ln N)) - оптимально
• FTRL обобщает Hedge (энтропийный регуляризатор) и online gradient descent (L2 регуляризатор)
• Online-to-batch conversion: при IID данных sublinear regret автоматически даёт PAC-гарантию O(1/sqrt(T))

Связи с другими концепциями

Online learning - мост между статистическим обучением и теорией игр. PAC-обучение (lt-01) требует IID; online learning снимает это ограничение и через online-to-batch conversion всё равно даёт PAC-гарантии. AdaBoost (lt-10) использует те же мультипликативные веса, что Hedge - boosting есть online learning применённый к ансамблям. PAC-Bayes (lt-09) работает с распределениями над гипотезами - та же идея смешения стратегий, но в байесовском языке.

• lt-01-pac-intro — связано
• lt-09-pac-bayes — связано
• lt-10-boosting-theory — связано

Вопросы для размышления

• Hedge гарантирует sublinear regret даже против адверсария. Означает ли это, что алгоритм «побеждает» адверсария? Чем «не проигрывать в среднем» отличается от «выигрывать»?
• Online-to-batch conversion говорит: при IID online алгоритм становится PAC-алгоритмом. Но специализированный PAC-алгоритм может лучше использовать структуру задачи. В каких случаях стоит предпочесть PAC-подход?
• В bandit feedback мы не видим потери невыбранных экспертов. Как несмещённо оценить их потери? Почему это сложнее, чем кажется?

Связанные уроки

• stat-01-sampling