Введение

Привет! Наша команда Glowbyte Advanced Analytics разрабатывает ML-решения для прикладных индустрий (ритейл, банки, телеком и др). Многие задачи требуют нестандартных решений. Одно из них — оптимизация цепочек коммуникаций с клиентом с помощью Reinforcement Learning (RL), которому мы решили посвятить данную статью.

Мы разбили статью на три блока: введение в задачу оптимизации цепочек коммуникаций; введение в RL; а в третьем блоке мы объединяем 1 и 2 вместе.

Задача оптимизации цепочек коммуникаций

Для начала, небольшой глоссарий:

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

Клиент — тот, кто пользуется услугами некой организации.

Атрибуты клиента — накопленные знания о клиенте. Примеры:

Средний чек;
Средняя частота покупок в месяц;
Возраст;
Регион проживания.

Маркетинговая кампания \ коммуникация \ предложение — промо-предложения, которые клиенты получают от организации. Примеры:

Вам начислено ХХХ баллов, успейте потратить до YYY;
Для вас скидка XXX на товары бренда YYY.

Цепочка коммуникаций — последовательность маркетинговых кампаний.

Программа лояльности — комплекс маркетинговых активностей, направленных на повышение ценности клиента. Типичный пример — дисконтные карты.

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

Рекомендательная система — система, формирующая оптимальные с точки зрения ценности для бизнеса предложения клиенту.

LTV (lifetime value) — ожидаемая прибыль с клиента за всё время сотрудничества с ним.

Считается, что при разработке программы лояльности, главная задача аналитика — создание первоклассной рекомендательной системы, которая знает что, когда и в каких количествах нужно клиенту в данный момент времени. Это безусловно важно, и даже приносит определенную прибыль, но это не ключевая задача бизнеса. Любая организация прежде всего хочет выработать привычку своих покупателей пользоваться их услугами. Идеальный клиент — это тот, кто пользуется услугами исключительно данной организации, приносит стабильную прибыль, рекомендует услуги друзьям, требуя при этом минимум затрат со стороны бизнеса. Лояльность клиента не зарабатывается мгновенно и задача организации — провести клиента по пути от первого заказа до регулярных покупок наиболее эффективным образом.

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

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

Итак, какие у нас вводные:

Цель — привести клиента в некоторое идеальное состояние (например, высокий LTV или стабильный отклик на маркетинговые кампании). Допустим, мы можем однозначно определить, находится ли клиент в идеальном состоянии или нет;
У нас есть некоторые знания о клиенте, которые мы получаем по его транзакционной истории, информации в анкете и т.д;
Мы можем влиять на поведение клиента, отправляя ему маркетинговые коммуникации, стимулирующие совершить то или иное действие;
Соответственно, наша задача найти оптимальную цепочку коммуникаций, которая приведет клиента к идеальному состоянию из п.1. Каждый раз принимая решение о выборе кампании, мы принимаем во внимание текущие знания о клиенте (см п.2). Так как каждый клиент обладает своими индивидуальными характеристиками, оптимальная цепочка коммуникаций для каждого клиента индивидуальна.

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

Reinforcement Learning. INTRO

Что это и зачем?

Задача Reinforcement Learning — сформировать оптимальный алгоритм взаимодействия с некоторой средой для достижения желаемого результата.

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

В чем особенности RL с точки зрения ML?

Reinforcement Learning — это отдельный класс алгоритмов машинного обучения. Как правило, информация о среде изначально отсутствует, другими словами, нет размеченных примеров для обучения.

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

Чем RL отличается от случайного перебора всех вариантов?

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

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

Что значит оптимальный алгоритм взаимодействия со средой?

Не всегда мгновенный выигрыш гарантирует долгосрочный успех.

Например, в игре Шахматы взятие фигуры противника может обернуться более дорогими потерями.

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

Где это используется?

В играх. Помимо этого есть успехи в обучении роботов, переговорных ботов, рекомендательных систем. Несколько интересных референсов:

Обучение игре Go: победа алгоритма AlphaGo в игре Go над лучшими профессионалами
Переговорный бот: бот ведет переговоры с другим агентом и его цель совершить определенную сделку
A self-driving car
Здесь можно найти подборку применения RL в самых разных областях

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

Пример Beginners

Традиционно, начнем с многорукого бандита.

Рассмотрим игровой автомат с N ручками. За один раз можно поднять только одну ручку автомата.

Цель: определить действие (то есть ручку), которое приносит максимальный выигрыш.

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

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

Очевидно, такая стратегия будет работать только в стационарной среде (то есть там, где нет изменений со временем). В нестационарной среде (например, кто-то время от время меняет настройки автомата) со временем при использовании жадной стратегии оптимального результата не будет.

Помимо жадной стратегии, есть и другие:

ε-жадная стратегия: в $\epsilon$ % случаев выбираем оптимальное действие, в $(1-\epsilon)$ % — случайное;
Upper confidence bound (UCB) стратегия: при выборе действия используется весовой коэффициент, значение которого зависит от того, насколько хорошо протестировано событие (то есть чем менее исследовано событие, тем выше вероятность выбора этого действия);
Softmax: чем больше ожидаемый выигрыш, тем выше вероятность выбора этого действия.

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

Что мы узнали из примера:

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

Пример Intermediate

Теперь можно немного усложнить задачу и рассмотреть в качестве примера стержень:

Каретка со стержнем может совершать движения “влево” и “вправо”.

Цель: необходимо научиться удерживать стержень в вертикальном положении как можно дольше.

Отличие от предыдущей задачи: теперь необходимо учитывать дополнительные параметры: угол наклона $inline$ и скорость стержня $inline$ и принимать решение с учетом этих сведений.

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

Любая комбинация $inline$ называется состоянием. Количество состояний может быть как непрерывным, так и конечным. Алгоритмы работающие с конечным набором состояний, как правило, проще в реализации.

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

Что мы узнали из примера:

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

Пример Advanced

А теперь рассмотрим игру шахматы.

Количество возможных расположений фигур на доске выражается 52-х значным числом. И это не единственная сложность. Отличие от предыдущих двух задач заключается в том, что в случае шахмат важно выбрать не то действие, которое принесет максимальный результат сейчас, а то, которое приведет к победе в будущем (через много шагов вперед).

Что мы узнали из примера:

При принятии решения нужно учитывать долгосрочный эффект, а не мгновенную выгоду.

Теперь, используя примеры, дадим определение общепринятым терминам RL.

Основная терминология RL

Агент — субъект, который взаимодействует со средой, выполняя определенные действия, получает обратную связь от нее и запоминает ее.

Например, двигатель, который приводит в движение каретку со стержнем; многорукий бандит — это агенты.

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

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

Например, когда каретка со стержнем делает движение, обратная связь предпринятого действия — это результат упал стержень или нет. Каретка и стержень — среда.

Состояние — любые знания, помогающие принимать решения. Состояния относятся к среде и определяют ее однозначно в каждый момент времени. Как правило, такие состояния записываются в виде набора параметров, матриц или тензоров высшего порядка.

Например, текущее положение фигур на шахматной доске — это состояние.

Действие — действия, которые доступны агенту. Как правило, количество действий в пространстве конечно.

Например, движения стержня вправо или влево — это действия.

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

Например, выигрыш автомата в задаче многорукого бандита — вознаграждение.

Цель — как правило, целью агента является максимизация суммарного вознаграждения. Другими словами, конечная цель — максимизация вознаграждения не на текущем шаге, а итогового вознаграждения по результатам последовательности шагов.

Например, наша цель не разово удержать стержень, а как можно дольше.

Стратегия — отображение состояний в действия. Например, вероятность выбора действия A в состоянии S.

Формальная постановка задачи

На каждом шаге среда может находиться в состоянии $s \in S$ .
На каждом шаге агент выбирает из имеющегося набора действий действие $a \in A$ согласно некоторой стратегии π.
Окружающая среда сообщает агенту, какое вознаграждение $inline$ он за это получил и в каком состоянии $s^* \in S$ после этого оказался.
Агент корректирует стратегию π.

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

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

Табличные алгоритмы RL

Одними из фундаментальных методов RL являются табличные методы, используемые для задач, в которых множества состояний и действий конечны. Характерной чертой таких методов является использование таблиц Состояние-Действие. По строкам обычно отложены состояния, по столбцам — действия. В ячейках — значения функции ценности.

$inline$ — ценность действия $inline$ в состоянии $inline$ . Грубо говоря, это ожидаемая выгода, которую мы получим, если выберем действие $inline$ , находясь в состоянии $inline$ . На первом шаги значения $inline$ инициализируются, например, нулями.

На примере с лабиринтом начальная таблица Состояние-Действие может выглядеть следующим образом:

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

1, если объект нашел выход из лабиринта;
0, в противном случае.

Кроме того, после того как агент получил фактическую обратную связь от среды, значение $inline$ корректируется. Алгоритмы корректировки бывают разные, например, метод Монте-Карло, SARSA, Q-learning. Подробнее о них читайте здесь или здесь.

К примеру, формулы Q-learning и SARSA на первый взгляд очень похожи:

В обоих методах используется ожидаемое значение ценности действия на следующем шаге. Получают его очень просто: допустим, агент находится в состоянии $inline$ и выполняет действие $inline$ . Затем среда сообщает агенту, что в результате своего действия он получается вознаграждение $inline$ и новое состояние $inline$ . Пользуясь таблицей Состояние-Действие, можно найти строку с состоянием $inline$ и определить, какую ценность в нем принесет то или иное действие.

Отличие в том, что в Q-learning $inline$ — это всегда максимальная ценность в новом состоянии. В то время как в методе SARSA предполагается, что агент моделирует выбор действия в состоянии $inline$ , например, согласно ε-жадной или UCB-стратегии. При использовании жадной стратегии методы эквивалентны.

Недостаток подобных алгоритмов — необходимость хранения таблицы Состояние-Действие. Некоторые задачи могут иметь большое пространство состояний и действий, что делает невозможным использование классических табличных методов. В таких случаях, используют подходы к аппроксимации значений $inline$ с помощью нейронных сетей.

Альтернативой табличным методам может быть динамическое программирование. Мы не будем останавливаться на этих алгоритмах, но рекомендуем почитать книгу Р. С. Саттон и Э. Г. Барто Обучение с подкреплением.

На этом с теорией мы закончим и далее расскажем о том, как Reinforcement Learning может быть использован в прикладной задаче.

Подбор оптимальной стратегии стимулирования клиента с помощью Reinforcement Learning

Постановка задачи в бизнес-терминах

Ограничения, в условиях которых разрабатывался наш подход:

Решение должно быть гибким к ограничениям коммуникационной политики с клиентами;
Оптимизируемая функция должна быть обусловлена бизнес-целями и может быть сложнее, чем просто отклик;
Система должна самоадаптироваться под изменения в поведении клиентов без привлечения эксперта;
Система должна выбирать предложение с учетом потенциальной выгоды в будущем (то есть, по сути, принимать решение не на один шаг вперед, а на несколько);
Система должна еженедельно подбирать оптимальные предложения с учетом новых данных о клиентах.

Постановка задачи в терминах RL

Итак,
Агент и Среда — это система программы лояльности, которая отправляет клиенту коммуникации с маркетинговыми предложениями, и сам клиент.

State — это состояние клиента, которое характеризуется клиентскими атрибутами.

Actions — это маркетинговые предложения (например, “получи скидку Х% за покупку Y”). Предполагается, что список предложений зафиксирован и конечен.

Reward — некоторая функция от изменения поведения клиента (например, увеличение выручки или отклик на целевую кампанию).

Подход к решению

Теперь рассмотрим возможные варианты решения с помощью табличных методов Reinforcement Learning.

Алгоритм решения с помощью Q-Learning или Sarsa может быть таким:

1. Определение состояний клиентов

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

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

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

2. Выбор вознаграждения

Выбор вознаграждения — важнейший этап разработки системы. Для данной задачи вознаграждение может характеризовать успешность проведенной кампании. Например, возможные варианты:

Конверсия на предложение;
Прирост отклика на предложение;
Удельная выручка на участника кампании;
Удельная прибыль с учетом затрат;
…

Возвращаясь к проблеме повышения лояльности клиента, в качестве целевой метрики могут быть LTV или метрика близости клиента к сегменту лояльных.

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

P.S. Некоторые из предложенных вариантов вознаграждения рассчитывается агрегировано по группе клиентам (например, прирост отклика на предложения — это отклик в целевой группе минус отклик в контрольной группе). В данном случае было бы корректнее сказать, что мы выбираем действие не для клиента, а для кластера клиентов (которые находятся в одинаковом состоянии), в рамках которого рассчитывается вознаграждение.

3. Выбор возможных действий

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

маркетинговое предложение не должно меняться от запуска к запуску;
выбор количества предложений влияет на скорость обучения алгоритма;
должен быть рассмотрен сценарий, когда состоянию не подходит ни одна из кампаний (например, все варианты предложений приносят отрицательную выручку). В этом случае, одним из действий может быть “default-кампания”. Это может быть либо какая-нибудь базовая рассылка, которую можно отправлять всем клиентам, либо отсутствие предложения (то есть возможен вариант, когда выгоднее ничего не отправлять клиенту).

4. Проектирование алгоритма выбора с учетом ограничений

При проектировании алгоритма следует учесть:

Не все предложения могут подойти клиенту (например, клиенту не нужно предлагать iphone, если у него уже есть iphone).
Для поддержания баланса между исследованием среды и применением знаний, необходимо выбрать подходящую стратегию тестирования системы.
Необходимо учитывать потенциальную выгоду будущих запусков кампаний.
Для этого можно использовать предложенные алгоритмы Q-learning и SARSA для корректировки ценности действий. Методы учитывают ожидаемое значение ценности действия на следующем шаге, таким образом, мы переходим от подбора одной оптимальной кампании к подбору оптимальной стратегии коммуникации с клиентом.
Необходимо спланировать расписание запусков кампаний таким образом, чтобы перед каждым запуском было возможно получить обратную связь (вознаграждения и новые состояния клиентов) и пересчитать значения в таблице Состояние-Действие.

5. Инициализация таблицы Состояние-Действие

Изначально, таблица Состояние-Действие выглядит следующим образом:

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

Однако, если существует некая история, то ее можно использовать, то есть возможно ретроспективное пред-обучение таблицы Состояние-Действие:

Проинициализировать таблицу Состояние-Действие нулями
Взять исторический запуск кампании Х. Рассчитать состояния клиентов-участников кампании на момент запуска и по окончании кампании. Рассчитать вознаграждение, полученное в каждом состоянии.
Согласно формуле для Q-learning или SARSA сделать пересчет таблицы Состояние-Действие с учетом ожидаемых значений ценности кампаний на следующем запуске.

6. Обучение алгоритма на пилотных запусках

Цель нашей системы — научиться подбирать оптимальные предложения всей клиентской базе. Однако на этапе обкатки системы мы советуем проводить пилотные запуски на небольшом репрезентативном семпле клиентов.

На что нужно обращать внимание на данном этапе:

Изменения значений в таблице Состояние-Действие: по мере накопления истории значения в таблице Состояние-Действие должны становиться все более устойчивыми;
Положительная динамика эффекта от кампаний: от запуска к запуску результативность каждого маркетингового предложения должна расти.

Как только (1) и (2) выходят на плато, можно считать, что система готова к раскатке на всю клиентскую базу.

7. Раскатка системы

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

Таким образом, мы выработали следующие рекомендации к раскатке:

Исключить нестабильные состояния из раскатки;
Использовать ε-жадную стратегию, чтобы система могла самостоятельно подстроиться под изменения в поведении клиентской базы;
Продолжать регулярный мониторинг работы системы.

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

Заключение

Мы описали применение RL для решения задачи подбора оптимальной цепочки действий. Однако следует упомянуть, что аналогичная концепция может быть применена и для других маркетинговых задач, например, рекомендательных систем, выбора оптимального канала \ времени коммуникации или подбора персонального баннера на сайте. Несмотря на то, что Reinforcement Learning уступает в популярности традиционным методам ML, мы хотели донести до читателя, что RL может быть отличным решением, если есть необходимость поддерживать автоматическую дообучаемость системы или полностью обучить систему с нуля.

Команда GlowByte благодарит компанию X5 Retail Group за возможность реализовать этот кейс.

Как Reinforcement Learning помогает ритейлерам