Информатика и искусственный интеллект: учебник для 10–11 классов

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

Две кнопки новостной страницы

Редактор выбирает один из заголовков статьи. У варианта $a$ есть неизвестная вероятность клика $\mu_a$ . После показа наблюдается $R_t\in\{0,1\}$ . Если сначала провести равный эксперимент, а потом навсегда выбрать победителя, часть аудитории увидит слабый вариант. Если сразу показывать текущего лидера, случайный ранний успех может закрепить ошибку.

В стационарном $K$ -руком бандите на каждом раунде $t$ алгоритм выбирает $A_t\in\{1,\ldots,K\}$ и получает награду с математическим ожиданием $\mu_{A_t}$ . Лучшее среднее

\mu^*=\max_a\mu_a.

Потерю относительно всезнающего выбора измеряет накопленный regret:

\mathcal R_T =T\mu^*-\mathbb E\sum_{t=1}^T R_t =\sum_{a=1}^K\Delta_a\,\mathbb E N_a(T),

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

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

История выборов трёх рук, накопленная награда и regret — Рис. 70.1. Цена раннего любопытства
Верхняя полоса показывает выбранную руку на каждом раунде, точки — награды. Ниже идут накопленная награда алгоритма и линия идеального ожидаемого результата $t\mu^*$ . Вертикальный зазор равен реализации regret; раннее исследование создаёт зазор, но помогает выбрать лучшую руку позже.

Жадность с небольшой случайностью

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

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

Он прост и полезен как baseline. При постоянном $\varepsilon$ исследование никогда не прекращается, поэтому regret растёт линейно. Убывающее $\varepsilon_t$ уменьшает лишние проверки, но расписание надо подбирать.

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

UCB: оптимизм с формулой

Upper Confidence Bound выбирает

A_t=\arg\max_a\left[ \widehat\mu_a(t) +c\sqrt{\frac{\log t}{N_a(t)}} \right].

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

Для ограниченных наград концентрационные неравенства объясняют форму корня. При подходящей настройке ожидаемое число выборов неоптимальной руки имеет порядок

\mathbb E N_a(T)=O\left(\frac{\log T}{\Delta_a^2}\right),

а её вклад в regret — $O(\log T/\Delta_a)$ . Близкие руки различить трудно: малый $\Delta_a$ требует много показов.

Доверительные интервалы трёх рук и выбор UCB — Рис. 70.2. Среднее плюс неопределённость
Для каждой руки точка показывает $\widehat\mu_a$ , вертикальный отрезок — бонус $c\sqrt{\log t/N_a}$ . У третьей руки среднее ниже, но верхняя граница выше остальных, поэтому следующий показ достаётся ей. Числа $N_a$ подписаны под осью.

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

Для кликов удобна модель Бернулли с beta-prior:

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

После $s_a$ кликов и $f_a$ пропусков posterior:

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

На каждом раунде алгоритм сэмплирует $\widetilde\mu_a$ из каждого posterior и выбирает максимальное. Неопределённая рука иногда рисует оптимистичное значение и получает показ; хорошо изученная слабая рука почти никогда.

Это probability matching: вероятность выбрать действие близка к апостериорной вероятности, что оно лучшее. Prior влияет особенно сильно в начале. Псевдосчёт $\operatorname{Beta}(1,1)$ равномерен, а $\operatorname{Beta}(100,100)$ уже выражает сильную уверенность около $0{,}5$ .

Связь с байесовским выводом здесь прямая, но корректность зависит от модели награды и стационарности.

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

Зафиксируйте три близкие вероятности и сравните $\varepsilon$ -greedy, UCB и Thompson sampling на одинаковых последовательностях потенциальных наград. Один запуск может ввести в заблуждение, поэтому смотрите медиану и диапазон regret по многим seed.

Затем в середине опыта поменяйте лучшую руку. Стационарные алгоритмы слишком доверяют старым данным. Скользящее окно или экспоненциальное забывание реагирует быстрее, но повышает шум. Это уже другая постановка: dynamic regret относительно меняющегося лидера.

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

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

\mathbb E[R_t\mid x_t,A_t=a].

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

Журнал адаптивной политики смещён: популярные действия наблюдаются чаще, а награды альтернатив неизвестны. Для offline-оценки новой стратегии используют propensity $p_t=\Pr(A_t=a\mid x_t)$ и inverse propensity weighting:

\widehat V(\pi)=\frac1T\sum_{t=1}^T \frac{\mathbf1\{\pi(x_t)=A_t\}R_t}{p_t}.

Если старая политика почти никогда не выбирала нужное действие, веса огромны и оценка нестабильна. Логировать propensity необходимо во время эксперимента; восстановить их задним числом часто нельзя.

Вероятности клика двух вариантов для новых и постоянных читателей — Рис. 70.3. Одна средняя скрывает два контекста
Столбцы показывают CTR вариантов $A$ и $B$ отдельно для новых и постоянных читателей. В общей смеси побеждает $A$ , но внутри обеих групп — $B$ : доли аудиторий при показах различались. Схема связывает контекстный выбор с парадоксом Симпсона.

Реальные логи и смещение

Open Bandit Dataset содержит логи рекомендательной политики интернет-магазина: контекст, выбранное действие, награду и вероятность выбора. Он создан именно для offline policy evaluation. Но даже хороший открытый набор не превращает оценку в реальный запуск: пользователи, интерфейс и каталог относятся к конкретному периоду.

При анализе сравнивайте:

среднюю награду и накопленный regret в симуляции;
дисперсию IPS-оценки;
долю контекстов, где новая политика не поддержана старой;
результат clipping больших весов и возникающее смещение;
качество по группам, а не только в среднем.

Мини-исследование: сколько стоит узнать победителя

Создайте две Bernoulli-руки со средними $0{,}2$ и $0{,}2+\Delta$ , где $\Delta\in\{0{,}005;0{,}02;0{,}08\}$ . Для каждого разрыва проведите 1000 запусков UCB на горизонтах от $10^2$ до $10^5$ . Измерьте не только regret, но и вероятность, что к концу алгоритм чаще выбирает истинного лидера.

При малом $\Delta$ различие слабее случайного разброса на коротком горизонте. Алгоритм может потратить значительную долю бюджета на исследование и всё равно не получить уверенности. При большом разрыве несколько десятков наблюдений достаточно, и дальнейшие пробы слабой руки почти полностью становятся regret.

Добавьте режим fixed A/B: половина показов каждой руке, затем выбор лидера. Он хорошо идентифицирует разность, но не оптимизирует награду во время сбора. Bandit делает обратный обмен. Нанесите методы на плоскость «ошибка выбора финального лидера — накопленный regret». Универсального победителя нет: точка зависит от цели эксперимента.

Для связи с проверкой статистических гипотез постройте confidence sequence, действительную при адаптивной остановке, либо честно зафиксируйте горизонт заранее. Обычный p-value после многократного просмотра текущего лидера может оказаться слишком оптимистичным.

Добавьте стоимость показа: один вариант может приносить больше кликов, но чаще вызывать быстрый уход. Тогда reward задаётся вектором. Скаляризация $R=\text{click}-\lambda\cdot\text{bounce}$ меняет лидера при разных $\lambda$ . Постройте Pareto frontier рук вместо скрытого выбора одного коэффициента.

Это связывает бандитов с многокритериальной оценкой моделей. Эксперимент не должен оптимизировать удобную мгновенную метрику, если решение принимается по более долгому результату.

Индекс и горизонт

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

Главный урок проще конкретного алгоритма. Исследование нужно ровно потому, что данные появляются после действия. Чем меньше разрыв между руками и короче горизонт, тем дороже выяснять победителя. Чем быстрее среда меняется, тем опаснее копить старую уверенность.

Задачи

3баллов

Три руки Бернулли имеют средние $(\mu_1,\mu_2,\mu_3)=(0{,}12,0{,}15,0{,}19)$ и за 1 000 раундов выбраны $(N_1,N_2,N_3)=(100,300,600)$ раз. По формуле ожидаемого regret $R=\sum_iN_i(\mu_*-\mu_i)$ вычислите общий результат и вклад каждой неоптимальной руки, затем поменяйте местами $N_1$ и $N_2$ . Случайности в расчёте нет; ответ нужен в ожидаемых единицах награды с точностью $10^{-3}$ и с проверкой суммы вкладов.

4баллов

В момент $t=220$ эмпирические средние двух рук равны $\widehat\mu_1=0{,}20$ , $\widehat\mu_2=0{,}24$ , а числа выборов $N_1=20$ , $N_2=200$ . Используйте ровно $U_i(t)=\widehat\mu_i+\sqrt{2\ln(t)/N_i}$ и при равенстве выбирайте меньший номер. Вычислите оба индекса и следующую руку. Затем зафиксируйте $N_2=200$ и обе эмпирические средние, но для каждого проверяемого $N_1\ge1$ полагайте $t=N_1+200$ ; найдите наименьшее целое $N_1$ , при котором $U_2(t)>U_1(t)$ . Случайности и единиц измерения нет; первые два индекса нужны с четырьмя знаками, а порог должен быть проверен для найденного целого и непосредственно предшествующего ему.

5баллов

Для двух Bernoulli-рук независимые prior равны $\mu_i\sim\operatorname{Beta}(1,1)$ . Первая рука дала 8 успехов и 12 неудач, вторая 40 успехов и 60 неудач. Выпишите оба posterior по формуле $\operatorname{Beta}(1+s_i,1+f_i)$ . Из PCG64 seed 7003 сгенерируйте ровно 1 000 000 независимых пар posterior-сэмплов, оцените $\Pr(\mu_1>\mu_2)$ и центральные 95%-интервалы обоих средних. Начальное состояние цепи не нужно; зачёт требует параметры распределений и оценки с Монте-Карло стандартной ошибкой для вероятности.

6баллов

Смоделируйте 500 опытов по 5 000 раундов для Bernoulli-рук $\mu=(0{,}10,0{,}11,0{,}14,0{,}20)$ . Таблицу потенциальных наград $Y_{e,t,i}$ создайте один раз PCG64 seed 7004 в порядке индексов опыт–раунд–рука и используйте общей для трёх алгоритмов. Каждый алгоритм сначала выбирает руки 1,2,3,4. Для $\varepsilon$ -greedy в опыте $e\in\{0,\ldots,499\}$ заведите отдельный PCG64 с seed 704100+e. На каждом следующем раунде сначала извлекайте одно $U\sim U[0,1)$ ; если $U<0{,}05$ , следующим вызовом извлекайте равномерный целый номер руки 1–4, иначе выбирайте руку с наибольшим эмпирическим средним. Не извлекайте номер руки в режиме exploitation. UCB выбирает максимум $\widehat\mu_i+\sqrt{2\ln t/N_i}$ , Thompson sampling берёт $\theta_i\sim\operatorname{Beta}(1+s_i,1+f_i)$ ; его генератор имеет seed $704000+e$ и на каждом раунде извлекает четыре значения по номерам рук. Все ничьи разрешайте меньшим номером. Вычислите реализованный cumulative regret $\sum_t(Y_{e,t,4}-Y_{e,t,A_t})$ , его медиану и IQR по опытам, а также долю руки 4 на последних 500 шагах. Зачёт требует общую таблицу случайных исходов, формулы, кривые и итоговые интервалы.

7баллов

Среда имеет 5 000 раундов и три Bernoulli-руки: при $t\le3000$ средние равны $(0{,}18,0{,}12,0{,}10)$ , затем $(0{,}10,0{,}12,0{,}20)$ . Сравните обычный $U_i=\widehat\mu_i+\sqrt{2\ln t/N_i}$ , window-UCB для $W\in\{100,500,1000\}$ с тем же выражением по последним $W$ наблюдениям и discounted UCB с $\lambda=0{,}995$ : $N_{i,t}^{\lambda}=\sum_{s<t}\lambda^{t-1-s}\mathbf1(A_s=i)$ , $\widehat\mu_{i,t}^{\lambda}= \sum_{s<t}\lambda^{t-1-s}Y_s\mathbf1(A_s=i)/N_{i,t}^{\lambda}$ и бонусом $\sqrt{2\ln(\sum_jN_{j,t}^{\lambda})/N_{i,t}^{\lambda}}$ . Нулевой счётчик даёт индекс $+\infty$ ; первые три действия равны 1,2,3, ничьи идут к меньшему номеру. Создайте общие таблицы наград для 200 опытов PCG64 seed 7005. Dynamic regret равен $\sum_t(\mu_t^*-\mu_{t,A_t})$ . Объявленный лидер есть рука с максимальным обычным, оконным или дисконтированным средним без бонуса. Задержка равна первому $t-3000$ , когда лидер 3 и остаётся им 100 шагов; ложное переключение есть смена объявленного лидера на неоптимальную руку в интервалах 200–3000 или после найденной задержки. Зачёт требует медианы и IQR трёх метрик по 200 опытам.