Exploration и бандиты

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

Выход — менять логирующую политику. Два дешёвых способа: случайная квота (ε-greedy) и софтмакс-сэмплинг с температурой. Ими обычно забирают первые 95% выгоды. Дальше — бандитный слой с оценкой неопределённости.

Важная оговорка про софтмакс-сэмплинг: он переранжирует только то, что уже отобрала воронка, а воронка отбирала жадно. Настоящее исследование требует механизма и на retrieval.

Из неравенства Хёфдинга: для выборки на [0,1] с истинным средним μ и выборочным \(\hat\mu\) верно \(\mathbb{P}(\mu \ge \hat\mu + u) \le e^{-2nu^2}\). Приравниваем правую часть к δ и разрешаем относительно u: \(U = \sqrt{-\ln\delta / 2n}\).

Дальше выбираем δ = 1/k^c — с ростом времени требуем всё более надёжную границу — и получаем \(a_k = \arg\max [Q_k(a) + c\sqrt{\log k / n_k(a)}]\).

Читается как «оценка средней награды плюс ширина доверительного интервала». Бонус убывает как \(1/\sqrt{n}\): при 1 показе он 3.03, при 1000 уже 0.096. Поэтому отдельной ручки исследования не нужно — алгоритм сам сокращает его по мере накопления данных.

UCB детерминирован и оптимистичен: берёт верхнюю границу интервала. Thompson байесовский: сэмплирует параметры из апостериора и действует жадно относительно сэмпла. Для бинарной награды это Beta-Bernoulli — априор Beta сопряжён с бернуллиевским, обновление тривиально (успех → α+1, неуспех → β+1), три строки кода и никаких гиперпараметров кроме априора.

По regret оба сублинейны, в отличие от ε-greedy: у того при удвоении отрезка прирост удваивается (73.9 → 142.5), потому что фиксированная доля случайного трафика тратится вечно.

Главное отличие на практике — не в награде, а в измеримости, см. следующий вопрос.

Из-за склонностей. UCB детерминирован: при данном состоянии порядок один и тот же, значит π(i|u) равна нулю или единице, и IPS, SNIPS, doubly robust превращаются в деление на ноль. Офлайн оценить новую модель по таким логам нельзя.

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

Оговорка: положительных склонностей мало, важен ещё их разброс. Если у 1% наблюдений вес 100, эффективный размер выборки падает с 1000 до 39 — оценка формально несмещённая, но бесполезная. Отсюда обрезка весов и требование, чтобы политика не уходила далеко от логирующей.

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

Почти всегда выбирают айтем, и это возможно потому, что счётчик показов — не единственный источник неопределённости. Обученная модель умеет отвечать «я не знаю» про айтем с незнакомыми признаками и пустой историей. Неопределённость берётся из модели, а не из счётчика.

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

Четыре инженерные причины. Цена ошибки ограничена: слой переставляет сотню уже отфильтрованных кандидатов, худшее — показать девятого вместо второго; на retrieval цена не ограничена ничем. Здесь есть полный вектор признаков, а σ нужна про пару (пользователь, айтем) в контексте. Кандидатов мало: ансамбль из пяти моделей на сотне — посильно, на десяти тысячах — нет. И это точка, где решение и так принимается.

Ограничение: слой исследует только то, что отобрала воронка. Если retrieval жадный, бандит исследует внутри уже смещённого пула.

Три источника: ансамбль моделей (выборочная дисперсия предсказаний), MC-dropout (дропаут на инференсе, несколько проходов головы) и neural linear (байесовская линейная регрессия поверх последнего слоя, даёт честную \(\sqrt{x^\top A^{-1}x}\)). Первые два почти ничего не стоят по разработке.

Главное — не перепутать эпистемическую неопределённость («модель не знает», убывает от данных) с алеаторической («событие случайно», не убывает никогда). Соблазн взять \(\sigma = \sqrt{p(1-p)}\) велик — формула под рукой. Но это чистая алеаторика: при p = 0.3 она равна 0.4583 и при одном показе, и при десяти тысячах. Такой бонус максимален при p = 0.5 и просто тянет наверх середнячков.

Проверка: постройте σ как функцию числа показов. Нет зависимости — измеряете не то. И не собирайте ансамбль из моделей с общей таблицей эмбеддингов: предсказания совпадут, σ схлопнется.

Помнить, что зависимость — горб, а не лестница. В симуляции α = 3 даёт 0.909 от идеальной выдачи против 0.834 у жадного (плюс 9% перестановкой того же пула), а α = 5 уже 0.891: мы начинаем поднимать наверх и тех, про кого всё понятно.

И отдельно — про малые α. При α = 0.5 самородок заглядывает в топ в 7 каталогах из 8, а закрепляется в топ-1 только в 2: он получает несколько показов, ловит неудачную серию, оценка проседает, а бонус \(\propto 1/\sqrt{n}\) уже подсох. Малый бонус хуже, чем никакой — тратит показы, но не доводит дело до конца.

Когда хватает случайной квоты и софтмакс-сэмплинга — а хватает их, чтобы забрать первые 95% выгоды. Слой окупается при трёх условиях сразу: каталог быстро обновляется, есть честная оценка неопределённости, нужны склонности для офлайн-оценки.

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

И методическая ловушка: выигрыш exploration проявляется в качестве будущих моделей, а меряют его недельным A/B по сегодняшним метрикам. На этом горизонте он почти всегда выглядит проигрышем.