# Как мы делаем RL в more.tv
## Мотивация
Всем привет! Меня зовут Анатолий, я не проверяю ссылки, которые вставляю в статьи на Хабре и заодно лидирую команду машинного обучения в онлайн-кинотеатре more.tv. В своей работе мы активно прототипируем и внедряем сервисы на основе обучения с подкреплением. Этот раздел машинного обучения всё ещё продолжает стоять особняком в индустрии, однако ситуация начинает постепенно меняться. Два года назад я впервые разработал контекстуальных бандитов для решения задачи ранжирования. По сравнению с мейнстримными [listwise, pairwise и pointwise подходами](https://medium.com/@mayurbhangale/pointwise-pairwise-and-listwise-learning-to-rank-baf0ad76203e), результат лично меня удивил. Конечно, как и всё, что делается в первый раз, было сделано с не очень большим пониманием дела. Однако, уже было понимание того, что RL - парадигмально иной раздел машинного обучения, требующий, в каком-то смысле, перестроения способа мышления. Полученный результат заставил меня более детально разбираться с теоретическими основами обучения с подкреплением и различными постановками задач.
Я более чем уверен, что **мой пример не является аномалией или каким-то выдающимся случаем**. Умея разрабатывать RL, каждый сможет существенно улучшить качество имеющихся ML/DL моделей, которые уже хорошо зарекомендовали себя в проде, или разработать собственное перспективное sota-решение для нового сервиса. Мне всегда было интересно разобраться в том, какие новаторские способы применяются в ML за пределами мейнстримных библиотек и сервисов. К примеру, в первую очередь я ознакомился не с функциональностью chatGPT, а с её разработкой по исходной статье. Возможно, я "подсмотрю" интересное решение, которое смогу применить в своём рабочем проекте? А если и не получится, то получу опыт и расширю кругозор. И как же было забавно наблюдать, что RL подходы, описанные в оригинале статьи о разработке chatGPT, **я уже применил на практике** вместе со своей командой в наших бизнес-задачах.
На мой взгляд, было бы довольно эгоцентричным не делиться подобным опытом постоянно. Именно поэтому недавно я решил создать свой [telegram-канал, посвящённый RL и дизайну бизнес-задач машинного обучения](t.me/rl_enthusiasts ). Далеко не всё влазит в формат поста или серии постов, а требует более широкого обзора. Поэтому в этой я хотел бы рассказать вам о некоторых **теоретических основах обучения с подкреплением** и рассмотреть RL **на примерах решения задач рекомендаций контента, аплифт моделирования и look-a-like моделирования** в нашем онлайн-кинотеатре. Поехали.

## Немного вводных о способах применения RL для решения бизнес-задач
Глобально существует три способа применить RL для решения бизнес-задач. Сегодня мы рассмотрим каждый из этих трёх способов. Именно они наиболее часто встречаются в научно-технических статьях об RL. Однако, не буду утверждать то, что я прочёл львиную долю статей об RL за последние 10 лет. Возможно, такой взгляд будет смещённым, но я редко на практике встречал несмещённые оценки чего-либо. К тому же недавно изученный мной исходник статьи о разработке chatGPT содержал все три способа, с которыми я уже и так был знаком из других статей.
**Первый способ - это представить ML/DL модель как RL систему с латентным пространством признаков.** Латентные переменные выражают т.н."скрытую взаимосвязь" $\Theta$ между значениями признаков объектов. Например, вектор ответов ML/DL модели, выражающий оценки максимального правдоподобия на каждой итерации классификации, является результатом оценки такой взаимосвязи $V(\Theta)$ и может быть использован в качестве информации, подкрепляющей обучение любой модели.
**Второй способ - это применить обучение с покреплением для обучения ML/DL модели.** В этом случае классическая постановка задачи обучения ML/DL модели дополняется постановкой задачи обучения с подкреплением. Информация, которая образуется в результате итерационного обучения ML/DL моделей, например, значение функции потерь, используется как дополнительный сигнал(подкрепление) в целях улучшения качества обучения.
**Третий способ - реализовать RL в самостоятельной задаче/подзадаче в многоуровневой архитектуре.** Задача машинного обучения полностью либо частично решается при помощи обучения с подкреплением. В случае с частичным решением на вход RL модели подаются ответы ML/DL моделей.

Давайте посмотрим на каждый из примеров подробнее.

## ML/DL модель как RL система с латентным пространством признаков на примере рекомендаций похожего контента
Особенность нашего онлайн кинотеатра - это громкие премьеры и новинки. Они настолько громкие, что их шум заглушает любой другой звук от иного контента. Поэтому получается, что в среднесроке выходит не очень выгодная ситуация как для нас, так и для пользователя. Опираясь на предпочтения, сформированные громкими премьерами, пользователь хочет найти подобный контент. В старой версии рекомендательной системы у него это выходило не очень хорошо. Новые пользователи довольно часто заглядывали в подборку похожих проектов, разочаровывались и больше туда не заходили. Напротив, тем, кому удавалось найти в подборке что-то стоящее, оставались с нами надолго. Опираясь на такую особенность потребления, мы бы хотели решить проблему разочарования в подборках похожего контента и найти немного контента, который пользователь смог бы посмотреть после громкой премьеры и новинок.

В данных такая особенность потребления выглядит как сильное смещение распределения практически любых метрик (просмотры, конверсии) в сторону удачных премьер и новинок. А что, если хороший контент попросту слабо рекомендовался? Исходный набор данных item-user матрицы содержал пять признаков:
* Процент досмотра
* Дата релиза
* Добавление в избранное
* Лайк
* Дизлайк

Исходное значение оценок $coef$ в item-user матрицы рассчитывали по базовой формуле $base$, взвешенной на добавочный коэффициент.
$base$ выглядит следующим образом:
Высокий процент досмотра определяем как медианный процент досмотра, характерный для подавляющего большинства зрителей. Расчёт $coef$ происходит так:
* если дата выхода контента больше даты трэшхолда, то взвешиваем на экспоненту $coef = e^{base}$
* если дата выхода контента меньше трэшхолда, то не взвешиваем
* значение трэшхолда релизной даты определяется на АБ тестах

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

По свойству экспоненциальной функции, стандартное отклонение исходных значений item-user матрицы становится значительно больше. Рост стандартного отклонения вызовет смещение оценок в сторону того контента, который мы хотим рекомендовать. Информация о смещении, которое мы создали расчётом $coef$, для модели станет сигналом к тому, чтобы выбирать тот контент, который решает нашу задачу.

Остаётся проблема смещения распределения просмотров в сторону премьер и новинок. Исходная item-user матрица получается местами сильно разреженной, а значит, слабо информативной. Чаще всего разреженность сильнее проявляется в "негорячем контенте". Таким образом, решив проблему частичной разреженности, мы решим нашу бизнес-задачу по прогреву нужного нам контента. Решить такую проблему возможно путём представления обучающей выборки в виде латентного пространства, полученного при помощи ML/DL модели. В нашем случае мы использовали усечённое SVD разложение item-user матрицы.

Латентное пространство в контексте усеченного SVD означает, что мы можем представить исходную матрицу данных, используя только наиболее значимые признаки (сингулярные значения). Для этого мы уменьшаем размерность данных так, чтобы использовать наиболее значимую информацию о взаимодействии пользователя с контентом, сохраняя k первых сингулярных значений. Информация о k наиболее значимых сингулярных значениях служит подкреплением для вычисления нового разложения. На каждой итерации разложения получаем три компонента: левую сингулярную матрицу (в нашем случае латентные признаки контента), диагональную матрицу и правую сингулярную матрицу (в нашем случае латентные признаки пользователя). Иными словами, на итерации n мы получаем сигналы о значимости признаков item-user матрицы и используем информацию о k значимых сингулярных значений для вычисления разложения на итерации n+1.

Полученное в результате разложения латентное пространство может быть представлено как RL система (описание поведения агента и/или внешней среды). В нашем случае мы брали топ k значений по доли объяснённой дисперсии, но можно использовать и другой алгоритм. К примеру, можно составить генеративный алгоритм в виде дополнительной функции потерь, оптимизирующей некоторую ML метрику (тот же recall) и на каждой итерации дополнительно вознаграждать разложение за прирост к этой метрике.
Также декомпозированная матрица может быть использована для выявления структуры и связанности в данных, которую **невозможно либо очень сложно распознать в исходных данных более простыми методами**. Ниже представлена визуализация структуры исходных данных и декомпозированной матрицы при помощи [TSNE](https://scikit-learn.org/stable/modules/generated/sklearn.manifold.TSNE.html)
Исходная item-user матрица напоминает устройство очень большого радиального города-мегаполиса. Чётко выражена небольшая центральная часть и обширная периферия, сложившаяся вокруг центра. Имея такое представление, довольно сложно решить поставленную проблему. Рекомендации будут лучше работать для центрального контента, тогда как периферийный контент останется на задворках без каких-либо шансов выйти оттуда.
Структура латентного пространства больше напоминает загородный коттеджный посёлок. Объекты не склонны группироваться вокруг одного центра. Такое представление данных позволяет существенно улучшить разнообразие рекомендованного контента и не смещать рекомендации в сторону премьер и новинок.

Очевидно, что имея правильно выраженную структуру в данных, можно существенно повысить качество обучения и результатов даже простых моделей, например, метода ближайшего соседа ([KNN](https://github.com/facebookresearch/faiss)). В случае с исходным представлением item-user матрицы KNN будет работать примерно так же, как топ, тогда как во втором случае можно надеяться на более интересные результаты. Ниже представлены скриншоты рекомендаций полки похожие проекты для недавней премьеры сериала [Фишер](https://more.tv/fisher/reviews) с применением усечённого SVD + KNN


Основу рекомендаций составили детективы и триллеры с примесью ужастика, в том числе и про маньяков-убийц. Это концептуально действительно похоже на родительский проект. Тем не менее, не обходится без очевидных фейлов. Среди таких фэйлов можно отметить следующие:
* Проекты среди похожих часто рекомендуются одинаковыми парами среди разных родительских проектов. Это связано с недостаткой сортировки по скорам KNN.
* Рекомендации не учитывают контекста просмотра. К примеру, среди рекомендованных появляются проекты, совершенно не похожие по жанру и сюжету. В примере с сериалом Фишер это контент про животных и природу. Такой недостаток решается при помощи разработки отдельной логики **контекстуального ранжирования** над текущей реализацией.
* Расположение проектов в латентном пространстве довольно сильно детерменированно высоким процентом досмотра. Поэтому довольно часто "невпопад" может рекомендоваться хорошо досматриваемый контент, например, эротический. Недавние оффлайн-эксперименты показали, что, если, добавить большее количество признаков, описывающих контент, то можно нивелировать этот недостаток.

Мы считаем то, что нам необходимо развивать представления данных в виде латентных пространств. В дальнейшем для этого мы планируем использовать нейронные сети. Информация, получаемая при помощи функций активаций в слоях нейронных сетей, представляет собой неявного учителя. Такую информацию в каждом слое можно считать сигналом, который целесообразно использовать как подкрепление (вознаграждение) для файнтюнинга нейронной сети или обучения другого алгоритма поверх слоёв нейронной сети.
Также интересной идеей выглядит описание внешней среды при помощи представления результатов KNN в виде ориентированного графа. Используя такие внешние среды, можно осуществлять дополнительное ранжирование контента RL алгоритмом.

## RL как способ обучения ML/DL модели на примере Uplift-моделирования

Перед DS отделом была поставлена задача увеличить конверсию в подписку с помощью полезных воздействий на пользователей. Один из способов решения данной задачи – Uplift моделирование, о чём мы расскажем подробнее.

### Задача Uplift-моделирования

Задача Uplift моделирования заключается в **предсказании изменения поведения или решений пользователей в ответ на различные воздействия**. Нам нужно было найти таких пользователей, кто продлит подписку, если мы осуществим некоторое воздействие.

**Почему бы просто не сделать воздействие на всех?**
- Упадёт выручка.

**Но вдруг рост конверсии будет настолько высоким, что он компенсирует падение?**
- Вряд ли – уже сделали бы полезное воздействие по всей базе до нас;
- Жалко терять выручку на тех пользователях, кто конвертнулся бы без воздействия – их же так много.

**Как же собрать данные для обучения?** На помощь приходят АБ-тесты. Мы можем разбить на части наших пользователей и проверить, как они реагируют на воздействие (а заодно убедиться, что воздействие вообще даёт прирост конверсии в подписку). Берём 2 группы: в **тестовой** делаем воздействие, в **контрольной** воздействия не делаем; проверяем, что в группах различий нет; считаем конверсию в подписку после проведения теста; она статзначима; ура, мы собрали данные, на которых можем обучить uplift-модель!

Вернее, **мы собрали целевые метрики**, которые можем использовать для решения задачи. Также нужно собрать признаки пользователей, которые будут подаваться на вход модели и на которых будет обучаться Uplift модель. В нашем случае – **это действия в интерфейсе за последние 30 дней перед началом эксперимента**:
- факторы обратной связи (просмотры, лайки, добавление в избранное) – показывают общую заинтересованность пользователя в контенте;
- факторы узости контентной базы (взаимодействие с поиском).

Есть разные [подходы](https://github.com/uber/causalml#causal-ml-a-python-package-for-uplift-modeling-and-causal-inference-with-ml) построения Uplift моделей, остановимся на деревьях (а где деревья, там и лес).

### Деревья
Рассмотрим дерево решений для решения задачи классификации. Алгоритм представляет собой древовидную структуру, где каждый **узел представляет тест на значение одного из признаков**, а каждая **ветвь соответствует возможному результату теста**. Признак, который будет использоваться в тесте, определяется с помощью критерия разбиения.

**Критерий разбиения** определяет, какой признак будет использоваться для разделения данных на две группы. В каждом узле дерева выбирается тот признак, который максимально уменьшит неоднородность в данных после разделения. Наиболее распространенными критериями разбиения являются критерий Джини и энтропия ([подробнее про деревья](https://scikit-learn.org/stable/modules/tree.html)).

### Uplift деревья

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

**Как же оценить Uplift в листьях?** Будем просто сравнивать средние значения целевой переменной в тестовой и контрольной группах:

$$\hat{\tau}_{node} = \frac{\sum_{i \in node} Y_iT_i}{\sum_{i \in node} T_i} - \frac{\sum_{i \in node} Y_i(1 - T_i)}{\sum_{i \in node} (1 - T_i)}$$

Соответственно, вся суть в том, какой критерий мы используем. В нашей задаче мы остановились на **максимизации дивергенций в листьях**:

$$\Delta = D_{aftersplit} - D_{beforesplit}\\
D_{beforesplit} = D(P^T_{node} \vert\vert P^C_{node})\\
D_{aftersplit} = \sum_{child \in left, right} \frac{N_{child}}{N_{node}}D(P^T_{child} \vert\vert P^C_{child}),$$

где $N_{child}, N_{node}$ – количество сэмплов в листе и узле дерева соответственно, $P^T$ – сэмплы из тестовой группы, $P^C$ – сэмплы из контрольной группы.

Используемой дивергенцией была **дивергенция Кульбака-Лейблера**:
$$KL(P^T \vert\vert P^C) = \sum_{i}p^T_ilog{\frac{p^T_i}{p^C_i}}$$

Как и любой алгоритм машинного обучения, **деревья решений могут переобучаться**. Причинами могут быть:
1. Слишком глубокое дерево с большим количеством листьев;
2. Подстройка алгоритма на множество значений признаков из тренирововчной выборки.

Первую проблему можно решить, применив прунинг – ограничение глубины дерева (и, конечно же, проверить скор на кросс-валидации).

Однако, в нашем случае **не удалось решить проблему стабильных, робастных результатов**.

Пайплайн обучения был классическим: разбивали выборку на трейн/валидацию (в отношении 80:20), обучали Uplift дерево на трейне, получали предсказания на валидационной выборке, считали метрику ([Area under uplift curve](https://habr.com/ru/companies/ru_mts/articles/538934/)) на трейне и валидации, а затем сравнивали метрики на этих двух выборках.

Изначально мы не фиксировали `random_seed` при разбиении на трейн/валидацию. Поэтому, при каждом новом запуске пайплайна у нас получались различные наборы данных для обучения. **Результаты были крайне нестабильны**; метрика на валидационной выборке отличалась более, чем на 20% в зависимости от выбранного `random_seed`:

На графике выше по оси `Х` – разные значения `random_seed`, по оси `Y` – скор на валидационной выборке по результатам выполнения пайплайна.

Первая мысль – наверное, дело в различных валидационных выборках, попробуем её зафиксировать. А трейн будем набирать из оставшихся сэмплов с повторениями, а-ля [бутстреп](https://ru.wikipedia.org/wiki/%D0%91%D1%83%D1%82%D1%81%D1%82%D1%80%D1%8D%D0%BF_(%D1%81%D1%82%D0%B0%D1%82%D0%B8%D1%81%D1%82%D0%B8%D0%BA%D0%B0)). Запустили такой процесс 1000 раз, и решили посмотреть, что будет с метрикой на валидации:


На графике выше по оси `Х` – количество экспериментов, по оси `Y` – скор на валидационной выборке по результатам выполнения пайплайна. Синяя линия – среднее значение метрики AUUC по результатам `x` экспериментов, чёрный пунктир – метрика при случайном присвоении Uplift скоров сэмплам, синяя область – зона 95% всех значений метрики по результатам `x` экспериментов (от 2.5 до 97.5 перцентилей).

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

Эту проблему мы и пытались решить с помощью обучения Uplift дерева стратегией Thompson sampling. Давайте разберёмся подробнее.

### Марковские процессы
**Марковская цепь** – это концепция, которая описывает последовательность событий, где вероятность перехода от одного состояния к другому зависит только от текущего состояния и не зависит от предыдущих состояний.

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

Мы можем определить вероятности перехода между этими состояниями на основе наблюдений за поведением человека. Например, если мы знаем, что обычно человек работает 5 дней в неделю и отдыхает 2 дня в неделю, то мы можем определить вероятность того, что он будет работать в следующий день как 5/7, а вероятность того, что он будет отдыхать, как 2/7.

Таким образом, мы можем создать **матрицу вероятностей перехода между состояниями "отдых" и "работа"**. Например:

| Состояние | Отдых | Работа |
|-----------|-------|--------|
| Отдых | 0.3 | 0.7 |
| Работа | 0.3 | 0.7 |

Эта матрица показывает, что вероятность остаться в состоянии отдыха на следующий день равна 0.3, а вероятность перейти в состояние работы равна 0.7. Аналогично, вероятность остаться в состоянии работы равна 0.7, а вероятность перейти в состояние отдыха равна 0.3.

Но, допустим, что у этого же человека на носу закрытие важного проекта. И ему нужно оставаться сверхурочно. Тогда он будет работать 6 дней в неделю, а отдыхать 1 день. Матрица переходов будет следующей:

| Состояние | Отдых | Работа |
|-----------|-------|--------|
| Отдых | 0 | 1 |
| Работа | 0.2 | 0.8 |

По сравнению с исходным примером, **вероятность остаться в состоянии отдыха стала равной нулю** – сотрудник не будет отдыхать больше одного дня подряд.

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

### Процесс Монте-Карло
**Процесс Монте-Карло** – это метод численного моделирования, который используется для оценки вероятностей и статистических характеристик сложных систем. Он может быть применен для исследования марковских цепей, которые являются моделями случайных процессов, где вероятность перехода в следующее состояние зависит только от текущего состояния.

Для исследования марковских цепей с помощью процесса Монте-Карло, необходимо **выполнить следующие шаги**:

1. Определить начальное состояние системы, которое может быть выбрано случайным образом или задано вручную.
2. Смоделировать случайный переход системы в следующее состояние, используя матрицу переходных вероятностей марковской цепи.
3. Повторять шаг 2 многократно, чтобы собрать статистические данные о системе в различных состояниях.
4. Анализировать полученные данные для определения статистических оптимальных стратегий управления системами, которые моделируются марковскими цепями.

### Задача о многоруком бандите и Thompson sampling
**Задача о многоруком бандите (Multi-Armed Bandit Problem)** является одной из классических задач в области обучения с подкреплением. В этой задаче **агент должен выбирать** одно из нескольких возможных действий. За каждое действие агент может получить **вознаграждение**. **Цель агента** заключается в том, чтобы **максимизировать суммарное вознаграждение за заданное количество итераций**.
Максимизация суммарного вознаграждения представляет собой **частный случай марковского процесса и процесса Монте-Карло**. Каждое действие агента $n$ выражает состояние марковского процесса $s$. Вознаграждение, полученное за каждое действие, это численное выражение состояния, определяющее следующее действие $n+1$. Агент совершает такую последовательность действий, каждое из которых **изменяет состояние среды** $s$ до $s'$, так и **определяет следующее действие** агента $n+1$.
Действие агента - **величина ожидаемая** и довольно стохастическая. Для оценки ожидаемой награды для действия $n+1$ используется процесс Монте-Карло. А именно, осуществляется **многократная симуляция (моделирование)** действия $n+1$ и **усреднение** полученных результатов. В процессе Монте-Карло мы можем оценить, какие действия приводят к **наибольшей награде**, и использовать эту информацию для выбора действия $n+1$. Использование процесса Монте-Карло позволяет существенно улучшить воспроисзводимость результатов и повысить робастность решения.
На практике в задаче о многоруком бандите моделирование действия $n+1$ осуществляется не случайным переходом, как в классическом процессе Монте-Карло, а по **заранее определённой стратегии**, т.е. максимизация вознаграждения агента проходит по **заранее заданной функции стратегии (policy function)**. Такая функция определяет, **какие действия должен выбирать агент в каждом состоянии среды**. Она является функцией от состояния $s$, которая возвращает **вероятности выбора** для каждого возможного действия $n+1$. Функция стратегии может быть определена как детерминированная (когда для каждого состояния определено одно конкретное действие) или стохастическая (когда для каждого состояния определено распределение вероятностей выбора каждого возможного действия).
Таким образом, мы не всегда получаем одинаковое вознаграждение. Вознаграждение будет принадлежать **какому-то распределению вероятностей** и от действия к действию будет **меняться как вознаграждение, так и состояние системы**. Для каждого действия мы можем лишь предположить, как распределены награды. Соответственно, можем **задать гиперпараметры этого распределения и обновлять их после каждого успешного взаимодействия**.

На основе этого предположения работает стратегия **Thompson Sampling(TS)**. **TS** - это стратегия принятия решений, использующая **вероятностную оценку функции ценности действий** и выбирающая действие на основе **распределения вероятностей вознаграждения для действия** ${n+1}$. TS состоит из **двух основных шагов**: генерации случайной выборки из апостериорного распределения вероятности для каждого возможного действия и выбора действия с наибольшей оценкой ценности из этой выборки. Такая стратегия особенно эффективна в ситуациях, где данные [нестационарны](https://ru.wikipedia.org/wiki/%D0%A1%D1%82%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%B0%D1%80%D0%BD%D0%BE%D1%81%D1%82%D1%8C) или когда присутствует неопределенность в модели среды.

Теперь давайте посмотрим на стратегию TS по шагам:
0. Инициализируем априорные гиперпараметры распределения вознаграждения для каждого действия.
1. Получаем данные о вознаграждении выполнения каждого действия и обновляем априорное значение гиперпараметров распределения вознаграждения(получаем апостериорные значения для каждого действия)
1. Выполняем то действие, от которого ожидаем наибольшее вознаграждение.
1. Обновляем апостериорные распределения вероятностей для всех действий на основе данных о вознаграждении, т.е. получаем априорные значения гиперпараметров распределения вознаграждения для каждого действия.

Шаги 1-3 моделируются на довольно большом количестве итераций, как правило, от 1 тысячи. Также на практике определяется критерий останова исходя из логики конкретной задачи.

В нашей задаче **агент – Uplift дерево, сэмплы – кластеры в тренировочном датасете, вознаграждение – скор модели**. В вознаграждении нам важна не только величина, но и **дельта между скором на трейне и валидации**. Ведь в случае переобучения или недообучения модель не сможет создавать робастные предсказания, что будет отражено в значительном различии метрик. Таким образом, **скор на валидации выполняет роль штрафа** для получения итогового вознаграждения. **Обучение Uplift дерева стратегией TS с введением штрафа на валидации позволит нам эффективно бороться с переобучением**, используя при этом довольно **небольшое количество дорогих данных**.

Кластеры в датасете формируются случайным образом, но [стратифицированно](http://www.machinelearning.ru/wiki/index.php?title=%D0%A1%D1%82%D1%80%D0%B0%D1%82%D0%B8%D1%84%D0%B8%D0%BA%D0%B0%D1%86%D0%B8%D1%8F). Стратификация идёт по целевым переменным (купил ли пользователь подписку и было ли воздействие) и некоторым описательным признакам (берём не все признаки, потому как получается слишком много страт). Разделение по описательным признакам нестационарно, например, рассмотрим признак "**Количество дней за период, когда пользователь был активен в интерфейсе**".

На графике **представлена зависимость доли конвертнувшихся** пользователей от количества таких активных дней. Чем больше дней – тем больше процент конвертнувшихся пользователей. Соответственно, стратификация будет гаратировать нам, что пропорции пользователей в кластерах будут идентичны генеральной совокупности. Но эти данные также указывают и на то, что пользователь может продлить подписку в любой момент действующей подписки.


### Обучение с помощью Thompson Sampling

Каждому кластеру нужно смоделировать распределение, которому подчиняются награды. Остановились на [β-распределении](https://ru.wikipedia.org/wiki/%D0%91%D0%B5%D1%82%D0%B0-%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5), поскольку нас интересует выросла ли метрика и нет ли переобучения. Если метрика выросла и переобучения нет, то считаем, что мы выбрали правильный кластер. В противном случае считаем, что выбрали "неправильный" кластер. Таким образом, на каждой итерации мы моделируем **априорное β-распределение успешности нашего обучения.**

**Итоговый алгоритм обучения**:

1. ½ выборки – обучающая выборка, остальное – пул для набора данных
2. Остаток разбиваем на 4 стратифицированных кластера
3. Выбираем кластер, из которого будет брать сэмплы (β-распределение)
4. Из кластера берём 10% сэмплов от общего количества сэмплов в кластере
5. Добавляем их в обучающую выборку.
6. Обучаем Uplift-дерево;
7. На оставшихся данных измеряем качество – Area under uplift curve (AUUC);
8. Если AUUC на трейне и валидации отличается не более чем на 5% и AUUC > 0 (лучше рандома), то обогащаем train, α+=1;
9. Если нет, то трейн не изменяется, β+=1;
10. Останавливаемся, когда в обучающей выборке будет более 80% от всех данных.

В результате многократных запусков **получены качественные Uplift модели**: метрика лучше, чем в случае случайного присвоения Uplift скоров и разница метрики на обучающей и валидационной выборке не выше 5%. Также **модели робастны**: при разных исходных наборах обучающей выборке, итоговые значения метрики колеблются в районе 0.4±10%, что существенно ниже исходных 50%.

Важна и **интерпретируемость результатов**. Обратите внимание на график: резкий рост в районе 10-15% от общего числа пользователей и относительное плато далее. Это значит, что основной доход сосредоточен на первых 10-15% пользователей по скору, и что разослав им предложение, мы получим прирост конверсии без просадки выручки (поскольку не будем воздействовать на остальных пользователей). Впрочем, аналогичный рост наблюдается для пользователей на 70-м перцентиле и на 95-м перцентиле. А это значит, что ранжирование неидеально, есть группы пользователей, для которых предсказанный uplift-скор слишком низок, но которые могут принести прибыль, если с ними провзаимодействовать.


Следующими шагами по развитию Uplift моделирования мы планируем сделать предсказание не по одному, а по нескольким методам воздействия. Иными словами, будем **повышать персонализированность воздействий** на каждого пользователя. Также планируем использовать иные подходы построения моделей, менее интерпретируемые, чем одиночные деревья, а именно **леса**. Плюс ко всему, со течением времени и проведением экспериментов по внедрению моделей, будет пополняться объём обучающей выборки, а, следовательно, можно будет использовать **нейросети на действительно больших данных**.

## RL как подзадача в многоуровневой архитектуре либо самостоятельная задача на примере look-a-like задачи
В этой задаче нам необходимо выделить сегмент пользователей, которые наиболее чувствительны к высокой частоте показов рекламы в плеере и временно снизить частоту показов. Мы провели рандомный АБ тест и выяснили, что сниженная частота открутки рекламы снижает уровень оттока и повышает общий охват, особенно среди новых пользователей. Более высокий охват позволяет показывать рекламу большему количеству пользователей, что и формирует дополнительную выручку. Однако, далеко не каждого пользователя раздражает реклама в плеере, а значит, снижение показов рекламы тем, кому это не нужно, означает просадку в выручке.
Решение этой задачи подразумевает использование двухуровневой архитектуры. На первом этапе мы используем решающее дерево и решаем look-a-like задачу. На втором этапе мы решаем задачу о многоруком бандите, используя ответы первого этапа.
**Ключевая цель look-a-like задачи** - найти такие объекты $X$, которые наиболее похожи на некоторый искомый,якорный тип объектов $\lambda$. В зависимости от способа решения задачи выделяют разные метрики схожести.

- Для обучения без учителя, как правило, применяют L1 и L2 норму. Чем меньше значение этих метрик, тем сильнее некоторый объект похож на искомый.

- Для обучения с учителем это вероятность (скор правдоподобия).

Необходимо найти такой вектор состояний $v=R[0, 1]$, где $R[0, 1]$ выражает вероятность(правдоподобие) принадлежности множеству якорных объектов $\lambda$. Чем выше значение $v$, тем сильнее некоторый объект похож на якорный. Поскольку полученные ответы численно выражают схожесть объектов с якорными, то можно говорить о том, что осуществляется сегментация объектов. При этом такая сегментация не будет эвристической. Постановка задачи предполагает, что критерий сегментации определяется заранее при помощи выделения якорных объектов. Существуют разные алгоритмы решения look-a-like задачи, которые выдают разные оценки принадлежности $X$ -> $\lambda$, даже если метрики качества классификации получаются одинаковыми.
В нашем случае мы использовали решающее дерево, которое обучали при помощи **алгоритма "Ожидание-Максимизация" (EM алгоритм)**.
**Что мы делаем на шаге "Ожидание"**

1. Необходимо определить подвыборки, с которыми мы будем работать. Подвыборки в нашем случае это классы, определяющие факт вовлечённости пользователя. Они определялись экспертно.
2. Необходимо оценить вероятность (правдоподобие) принадлежности каждого объекта к каждой подвыборке. В нашем случае это предикты решающего дерева.

**На шаге "Максимизация"** мы должны взять argmax от оценок правдоподобия, полученных на шаге "Ожидание". Делать это можно по-разному, главное в обучении использовать подкрепляющую информацию.В нашем алгоритме мы выбирали верно классифицированные объекты по roc-auc и среднему гармоническому и убирали их из тестовой выборки. Таким образом, значения roc-auc и среднего гармонического являлись для дерева подкрепляющей информацией, которая определяла набор объектов и их значений в листьях. А **каждое следующее состояние $s'$** определялось **предыдущим состоянием $s$** по определению марковской цепи. В качестве критерия остановы использовали **early stopping rounds** (отсуствие роста метрик на протяжении n итераций) и крайне малое значение **tol**, определяющее количество оставшихся объектов в отложенной выборке.

**Итоговый алгоритм обучения**:
0. Определить классы вовлечённости объекта.

1. До тех пор, пока не достигли значения tol, либо n:
а. Получить оценки вероятности принадлежности к классу на отложенной выборке
б. Определить верно классифицированные объекты при помощи roc-auc и fscore
в. Убрать верно классифицированные объекты из отложенной выборки

С третьей итерации алгоритм сошёлся. На roc-auc алгоритм не повлиял никак, но значение остальных метрик немного изменилось.
Оценки схожести отличаются довольно существенно. Если учитывать изначальный баланс классов невовлечённых и вовлечённых, то получим, что EM алгоритм даёт более правдоподобные оценки схожести, особенно в части определения самых вовлечённых пользователей.

Представленная реализация алгоритма "Ожидание-Максимизация" является **самой простой из всех возможных**. Однако даже такой простой алгоритм за счёт **прямого использования подкрепляющей информации** способен существенно повысить качество оценок правдоподобия и классификации в целом.

Однако, ошибки в классификации неизбежны и нам бы ещё хотелось повысить её качество, **причём существенно и быстро**. Вектор оценок $1 - v=R[0, 1]$ использовали как **штрафующую метрику** для решения задачи о многоруком бандите. **Вознаграждение** - это количество времени, проведённого пользователем на сервисе. Так получали итоговый вектор оценок вовлечённости пользователя, где **решающим признаком является время, проведённое на сервисе, а тормозящим признаком - общая оценка довольствия.** Итоговые ответы получали при помощи **epsilon-greedy стратегии.**
**Epsilon greedy стратегия** - это стратегия выбора действия, где агент должен выбрать наилучшее действие из возможных в текущем состоянии. Она заключается в том, что агент с вероятностью epsilon выбирает случайное действие из всех возможных, а с вероятностью 1-epsilon выбирает наилучшее действие. По сравнению со случайной стратегией, уменьшается вероятность получения неоптимального результата при выборе наилучшего действия. Значение epsilon позволяет сделать стратегию недетерменированной. На каждой итерации агент исследует новые действия, собирает больше информации о внешней среде и выбирает наилучшее действие, переходя в новое состояние. Например, если epsilon=0.1, то агент в 90% случаев будет выбирать оптимальное действие, а в 10% случаев будет выбирать случайное действие. Это позволяет агенту исследовать новые возможности и не застревать в локальных оптимумах. Чем выше значение epsilon, тем больше информации о внешней среде получает агент, но ниже вероятность совершить наилучшее следующее действие. Поэтому значение epsilon для каждой конкретной задачи является гиперпараметром.
Нам было интересно посмотреть, действительно ли ответы многорукого бандита зависят от штрафа и вознаграждения. Измерение корреляции показало, что **результаты оценок вовлечённости на 86% зависят от вознаграждения и на 14% зависят от штрафа**, что полностью соотвествует как задумке, так и здравому смыслу.
Следующими шагами в развитии решения задачи мы видим уточнение штрафующих оценок, которое выдаёт дерево за счёт двух способов: расширение признакового пространства и использование в EM алгоритме техники hard negative sampling, позволяющей минимизировать ошибку эксперта в разметке якорных объектов $\lambda$.

## Что делать завтра
Теперь вы знакомы с практическими кейсами RL в разных бизнес-задачах на примере нашего онлайн-кинотеатра. Мы наглядно продемонстрировали то, что обучение с подкреплением показывает существенное улучшение результатов в ML метриках, робастности и достижении бизнес-логики. А также то, что при должном уровне подготовке, решение задач при помощи обучения с подкреплением может быть гораздо эффективнее аналогичных мейнстримных подходов. Вы просто потратите меньше усилий и нервов, а процесс эксперементов будет нагляднее, прозрачнее и результативнее.
Сразу предвосхищу множество вопросов и скепсиса. С деплоем этих решений всё нормально. Как и с финансовой отдачей. Что-то уже внедрено, что-то находится в процессе, ведь бэклог на разработку не резиновый. Никаких загвоздок не обнаруживается, поскольку используется простой и масштабируемый архитектурный подход в интеграции ML контура и контура разработки. И, если бы, речь шла в том числе и об онлайн решениях, уверен, что всё было бы также.
Надеюсь, нам удалось убедить вас в том, что существует множество бизнес-кейсов, где мейнстримные подходы обладают слабой отдачей. А также в том, что специфика бизнеса и экспертиза играют ключевую роль. За каждой хорошей известной либой, будь то LightGBM или causalml стоят **свои разработчики** из конкретных компаний, которые **решали конкретные задачи для своих компаний**. А эти задачи имели **свои конкретные бизнес-цели и специфику**, которая, наверняка отличается от вашей.
Надеюсь, мне удалось показать вам, что есть куда расти. И, если, chatGPT такая уже себе "атомная бомба", то, скорее всего, стоит уже сегодня или завтра осваивать современный стэк и делать эту самую бомбу. Как видите на наших примерах, эти технологии и подходы вовсе не rocket science.
Возможно, теперь у вас есть интересные мысли по дальнейшей траектории развития ваших проектов. Или вы хотя бы немного расширили кругозор и заинтересовались обучением с подкреплением. В любом случае, я не прощаюсь и оставляю ссылку на [свой канал](t.me/rl_enthusiasts). Там мы постоянно делаем интересные небольшие ML обзоры. В том числе регулярно обсуждаем RL.
А здесь всё!;)