Многорукий бандит

Многорукий бандит убирает состояния и оставляет один чистый конфликт: потратить показ на нынешнего лидера или проверить менее изученный вариант. Лучшее действие неизвестно, а каждое измерение уже меняет результат — потому что измеряем мы теми же показами, которыми зарабатываем.

Пять фильмов и один бюджет показов

Витрина кинотеатра показывает посетителю одну рекомендацию. У каждого фильма есть неизвестная нам заранее вероятность понравиться. Чтобы не выдумывать цифры, возьмём реальный лог MovieLens 100K, тот же, на котором мы строили рекомендации: наградой будем считать событие «зритель поставил оценку не ниже четырёх». Пять хорошо оценённых фильмов дают пять «рук»:

$$\mu_{\text{SW}}=0{,}859,\quad \mu_{\text{GF}}=0{,}850,\quad \mu_{\text{Far}}=0{,}799,\quad \mu_{\text{Con}}=0{,}676,\quad \mu_{\text{LL}}=0{,}406.$$

Эти числа посчитаны по 583, 413, 508, 509 и 485 реальным оценкам соответственно. Мы, читатели учебника, их видим. Алгоритм — нет: он узнаёт мир только через отклики тех зрителей, которым сам же и показал фильм.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

В стационарном $K$-руком бандите на каждом раунде $t=1,\ldots,T$ алгоритм выбирает руку $A_t\in\{1,\ldots,K\}$ и получает случайную награду $R_t$ с условным средним

$$\mathbb E[R_t\mid A_t=a]=\mu_a .$$

Лучшее из средних обозначим

$$\mu^*=\max_{a}\mu_a,\qquad a^*=\arg\max_a\mu_a .$$

Бандит проще марковского процесса принятия решений: нет состояния и нет влияния действия на будущую динамику среды. Но он труднее обычного A/B-теста, потому что данные собираются адаптивно — тем самым правилом, качество которого мы и оцениваем.

Regret: во что обходится незнание

Сравнивать алгоритм с нулём бессмысленно; сравним его с всезнающим оракулом, который с первого раунда играет $a^*$. Разность накопленных ожидаемых наград и есть regret:

$$\mathcal R_T=T\mu^*-\mathbb E\sum_{t=1}^{T}R_t .$$

Ключевое тождество получается заменой суммы по времени на сумму по рукам. Обозначим $\Delta_a=\mu^*-\mu_a$ — разрыв руки $a$, а $N_a(T)$ — сколько раз она была выбрана за $T$ раундов. Тогда

$$\mathcal R_T=\sum_{a=1}^{K}\Delta_a\,\mathbb E N_a(T).$$

Формула буквально выписывает счёт: каждый показ неоптимальной руки стоит ровно её разрыв. Ошибиться в пользу Godfather дёшево ($\Delta=0{,}009$), ошибиться в пользу Liar Liar дорого ($\Delta=0{,}453$).

Это тонкость, которую стоит проговорить: вклад руки равен произведению $\Delta_a N_a$, а хороший алгоритм выбирает её порядка $\log T/\Delta_a^2$ раз. Произведение ведёт себя как

$$\Delta_a\cdot\frac{\log T}{\Delta_a^{2}}=\frac{\log T}{\Delta_a},$$

то есть растёт при уменьшении разрыва. Самые дорогие руки — не безнадёжные, а те, что почти хороши.

Жадность и её ловушка

Простейшая политика: оценивать средние по наблюдениям

$$\widehat\mu_a(t)=\frac{1}{N_a(t)}\sum_{s<t:\,A_s=a}R_s$$

и всегда выбирать максимум $\widehat\mu_a(t)$. Проблема видна сразу: оценка, полученная по трём показам, участвует в сравнении на равных с оценкой по трёмстам. Рука, которой один раз повезло, получает $\widehat\mu=1$ и забирает все дальнейшие показы. Обратной связи по остальным больше не будет — они навсегда останутся с плохими случайными оценками.

Заметьте странность: медианный regret чистой жадности за 5000 раундов равен всего 48 — лучше, чем у $\varepsilon$-жадности с $\varepsilon=0{,}10$. Но при этом в 56,6% запусков она заперлась не на лучшей руке. Обе цифры верны и обе важны: у нашей задачи две верхние руки почти одинаковы, поэтому «неверный» выбор часто почти бесплатен. Если бы целью было назвать лучший вариант, а не максимизировать сумму наград, жадность провалилась бы.

$\varepsilon$-жадность: постоянная плата за любопытство

Добавим случайность. С вероятностью $1-\varepsilon$ выбираем текущего лидера, с вероятностью $\varepsilon$ — случайную руку:

$$A_t=\begin{cases} \arg\max_a\widehat\mu_a(t), & \text{с вер. }1-\varepsilon,\\[2pt] \text{равномерно из }\{1,\ldots,K\}, & \text{с вер. }\varepsilon. \end{cases}$$

Это простой и честный baseline. Но его regret растёт линейно: даже когда всё уже понятно, доля $\varepsilon$ показов уходит наугад, и каждый такой показ стоит в среднем

$$\frac{\varepsilon}{K}\sum_{a}\Delta_a .$$

Для наших пяти рук эта величина равна $\varepsilon\cdot0{,}1413$: при $\varepsilon=0{,}1$ — примерно $0{,}0141$ потерянного отклика на каждый раунд, и это плата навсегда.

Убывающее расписание $\varepsilon_t\propto 1/t$ лечит линейность, но требует подбора константы. Другой приём — оптимистичная инициализация: положить начальные оценки заведомо завышенными (например, 1). Тогда любая непроверенная рука выглядит привлекательно, и алгоритм сам обойдёт их все, пока оценки не опустятся до правды.

UCB: оптимизм перед лицом неопределённости

Разумная альтернатива — сравнивать руки не по средним, а по верхним границам того, чем они ещё могут оказаться:

$$A_t=\arg\max_{a}\left[ \widehat\mu_a(t)+c\sqrt{\frac{\ln t}{N_a(t)}}\right].$$

Первое слагаемое — найденное качество, второе — бонус неопределённости. Он велик у редко выбранной руки и тает как $1/\sqrt{N_a}$ по мере накопления данных; логарифм в числителе медленно поднимает бонус со временем, заставляя иногда возвращаться к давно забытым вариантам.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Откуда берётся корень

Форма бонуса не выдумана. Для награды из $[0,1]$ неравенство Хёфдинга даёт для среднего по $n$ независимым наблюдениям

$$\Pr\left(\widehat\mu-\mu\ge u\right)\le e^{-2nu^{2}} .$$

Приравняв правую часть к $t^{-4}$ и решив относительно $u$, получаем

$$u=\sqrt{\frac{2\ln t}{n}},$$

то есть тот самый корень с $c=\sqrt2$. Смысл выбора уровня: мы хотим, чтобы вероятность «оптимизм оказался ложью» суммарно по всем раундам и рукам была мала. Тогда с большой вероятностью верхняя граница лучшей руки никогда не опускается ниже $\mu^*$, а значит, выбор неоптимальной руки возможен лишь пока её бонус не сжался. Приравнивая бонус к разрыву,

$$c\sqrt{\frac{\ln T}{N_a}}\approx\Delta_a \quad\Longrightarrow\quad N_a\approx\frac{c^{2}\ln T}{\Delta_a^{2}},$$

получаем классический результат: ожидаемое число выборов неоптимальной руки имеет порядок $\log T/\Delta_a^2$, а её вклад в regret — $\log T/\Delta_a$.

Константа решает больше, чем название

Теория говорит про порядок, практика живёт при конечном $T$. Прогоним на одних и тех же реальных откликах шесть политик, 300 независимых запусков, горизонт 5000.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Осторожный UCB с теоретической константой $c=\sqrt2$ оказался худшим: на горизонте 5000 он всё ещё «оплачивает» проверку Liar Liar и Contact, хотя те давно проиграли. Уменьшение константы до $0{,}5$ снижает regret втрое. Это не опровержение теории, а её честное прочтение: гарантия $O(\log T)$ описывает поведение при $T\to\infty$ и в худшем случае, а нам нужен конкретный бюджет и конкретные разрывы.

Цена разрыва: сколько нужно, чтобы узнать победителя

Из $N\sim\ln T/\Delta^2$ следует практическое правило: чтобы уверенно различить две руки, нужно порядка $1/\Delta^2$ наблюдений. Проверим его на наших парах.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Обратите внимание на левый нижний угол: при $T=50$ и $T=100$ доля верных ответов ниже половины. Это не парадокс — на коротком горизонте случайность однажды повезённой руки сильнее реального различия в один процентный пункт.

Томпсоновское сэмплирование

Третья идея старше UCB: действовать по случайной выборке из собственного незнания. Для бинарной награды удобна модель Бернулли с сопряжённым бета-априорным распределением:

$$\mu_a\sim\operatorname{Beta}(\alpha_a,\beta_a).$$

После $s_a$ успехов и $f_a$ неудач апостериорное распределение получается сложением счётчиков:

$$\mu_a\mid D\sim\operatorname{Beta}(\alpha_a+s_a,\;\beta_a+f_a).$$

На каждом раунде алгоритм берёт по одному сэмплу из каждого posterior и играет руку с наибольшим сэмплом:

$$\widetilde\mu_a\sim\operatorname{Beta}(1+s_a,\,1+f_a),\qquad A_t=\arg\max_a\widetilde\mu_a .$$

Это заголовок статьи Томпсона — и одновременно точная формулировка того, что делает алгоритм. Он реализует probability matching: вероятность выбрать руку равна апостериорной вероятности того, что она лучшая,

$$\Pr(A_t=a)=\Pr\left(\mu_a=\max_j\mu_j\;\middle|\;D_{t}\right).$$

Плохо изученная рука иногда вытягивает оптимистичный сэмпл и получает показ; хорошо изученная слабая рука не вытягивает почти никогда.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Русская линия: бандит как задача управления по неполным данным

В западной традиции бандит идёт от Роббинса и Гиттинса, в советской — от теории оптимального управления со случайными возмущениями. Эрнст Львович Пресман и Исаак Моисеевич Сонин в монографии «Последовательное управление по неполным данным» (Наука, 1982) разобрали байесовскую постановку именно того конфликта, о котором идёт речь: наблюдатель управляет процессом, не зная его параметров, и вынужден платить за информацию действиями. Двурукий бандит разбирается там как каноническая модель, а решение строится через апостериорное распределение параметра как достаточную статистику: задача с неизвестным $\mu$ превращается в задачу управления полностью наблюдаемым процессом, состояние которого — само наше незнание. В 1990 году книга вышла по-английски с прямым упоминанием многоруких бандитов в заглавии.

Из этого взгляда естественно вырастает индекс Гиттинса. Для дисконтированного бандита с независимыми руками оптимальная стратегия выглядит поразительно просто: каждой руке приписывается число $\nu_a$, зависящее только от её собственного posterior и коэффициента дисконтирования, и играется рука с наибольшим индексом:

$$\nu_a=\sup_{\tau>0} \frac{\mathbb E\left[\sum_{t=0}^{\tau-1}\gamma^{t}R_t\right]} {\mathbb E\left[\sum_{t=0}^{\tau-1}\gamma^{t}\right]} .$$

Многомерная задача распадается на $K$ одномерных. Красота теоремы не должна обманывать: она опирается на независимость рук, дисконтирование и стационарность. Для контекстных или меняющихся сред готовый индекс не переносится.

Лаборатория бандита

Начните с чистой жадности: нередко она запирается на второй руке и кривая regret идёт почти прямой линией с малым наклоном. Включите $\varepsilon=0{,}2$ — наклон вырастет и уже не изменится: прямая линия и есть подпись постоянного исследования. Переключитесь на UCB и потяните $c$: при $c=0$ получается жадность, при $c=2$ алгоритм почти равномерно перебирает руки. Найдите значение, при котором кривая заметно загибается. Затем Thompson sampling: проследите, как доля показов худшей руки падает почти до нуля за первую сотню раундов.

Наконец, нажмите «сломать среду». Лучшая и четвёртая руки меняются местами. Посмотрите на счётчики: у бывшего лидера накоплены тысячи наблюдений, и его среднее падает мучительно медленно — каждое новое наблюдение весит $1/N$.

Когда среда меняется

Стационарность — сильное допущение. Вкусы, интерфейс, состав аудитории меняются. Формально мы переходим к dynamic regret относительно движущегося лидера:

$$\mathcal R^{\text{dyn}}_T=\sum_{t=1}^{T}\left(\mu^*_t-\mu_{t,A_t}\right).$$

Лечение — забывание. Скользящее окно считает средние по последним $W$ наблюдениям,

$$\widehat\mu_{a,t}^{W}= \frac{\sum_{s=t-W}^{t-1}R_s\mathbf 1\{A_s=a\}} {\sum_{s=t-W}^{t-1}\mathbf 1\{A_s=a\}},$$

а дисконтирование делает то же плавно, с весами $\lambda^{t-1-s}$:

$$N^{\lambda}_{a,t}=\sum_{s<t}\lambda^{t-1-s}\mathbf 1\{A_s=a\},\qquad \widehat\mu^{\lambda}_{a,t}= \frac{1}{N^{\lambda}_{a,t}}\sum_{s<t}\lambda^{t-1-s}R_s\mathbf 1\{A_s=a\}.$$

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Контекст: кому именно показывать

Один вариант может быть лучше для одной аудитории и хуже для другой. Тогда разумно наблюдать признаки $x_t$ до выбора и моделировать

$$\mathbb E[R_t\mid x_t,A_t=a]=f_a(x_t).$$

В LinUCB предполагают линейность, $f_a(x)=x^\top\theta_a$, оценивают $\theta_a$ гребневой регрессией и добавляют бонус, зависящий от того, насколько направление $x$ уже покрыто прошлыми наблюдениями:

$$A_t=\arg\max_a\left[x_t^\top\widehat\theta_a +\alpha\sqrt{x_t^\top V_a^{-1}x_t}\right],\qquad V_a=\lambda I+\sum_{s\:A_s=a}x_sx_s^\top .$$

Это буквально та же схема «оценка плюс неопределённость», только неопределённость теперь зависит от направления в пространстве признаков.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Логи адаптивной политики и offline-оценка

Журнал, собранный бандитом, смещён по построению: популярные действия наблюдаются часто, а об альтернативах данных почти нет. Оценивать по такому журналу новую политику $\pi$ наивным усреднением нельзя. Спасает взвешивание на обратную вероятность выбора (inverse propensity scoring):

$$\widehat V(\pi)=\frac1T\sum_{t=1}^{T} \frac{\mathbf 1\{\pi(x_t)=A_t\}}{p_t}\,R_t,\qquad p_t=\Pr(A_t\mid x_t),$$

где $p_t$ — вероятность, с которой старая политика выбрала действие. Оценка несмещена, если $p_t>0$ для всех действий, которые может выбрать $\pi$:

$$\mathbb E\left[\frac{\mathbf 1\{\pi(x)=A\}R}{p}\right] =\mathbb E\left[R^{\pi(x)}\right].$$

Но дисперсия растёт как $1/p$: одно наблюдение с $p_t=0{,}01$ входит с весом 100. Отсюда практика clipping — обрезать веса сверху, сознательно обменяв часть несмещённости на устойчивость.

Отсюда же следует осторожность с выводами: p-value, вычисленное после того, как вы много раз посматривали на текущего лидера, оптимистично. Нужны либо методы, корректные при адаптивной остановке (доверительные последовательности), либо честно зафиксированный заранее горизонт — тот же разговор о доверительных интервалах и покрытии, только с адаптивно собранными данными.

Где исследовать нельзя

Формула regret молчалива о том, чем именно мы платим. В медицине «показать менее изученный вариант ради информации» означает лечить человека хуже, чем умеем сейчас. Существуют safe bandits с ограничением

$$\mu_{A_t}\ge(1-\eta)\,\mu_{\text{baseline}}$$

и байесовские правила остановки, но само ограничение приходит из предметной области, а не из математики. То же с честностью: политика, максимизирующая общий CTR, может систематически недообслуживать малую группу, потому что её вклад в средний показатель мал.

Что остаётся, когда алгоритм забыт

Роббинс написал это, открывая ту самую область, в которой мы провели урок. Главное в ней — не конкретная формула бонуса. Главное — что данные появляются после действия и в ответ на него, а значит, план эксперимента и есть часть решения.

Три величины определяют всё остальное. Разрыв $\Delta$ говорит, насколько трудно различить варианты: нужно порядка $1/\Delta^2$ наблюдений. Горизонт $T$ говорит, окупится ли различение вообще: при 28 днях на один процентный пункт разницы дешевле выбрать любой вариант и вернуться к вопросу позже. Скорость изменения среды говорит, сколько прошлого имеет смысл помнить: полная память дала 9,4 regret до слома и 60,2 сразу после.

Ни один алгоритм не отменяет этой арифметики — они лишь по-разному распределяют плату. $\varepsilon$-жадность платит равномерно и вечно, UCB — по убывающей, но в худшем случае, Thompson sampling — по вероятности быть лучшим. Понимание, за что вы платите, переносится на любую задачу, где решение и измерение — это одно и то же действие.

Задачи