Reinforcement Learning в задаче групповой оптимизации цен / forpes.ru

08.07.2024 10:34

muxeu 0 60 Источник

Введение

Привет, Хабр! На связи аналитики больших данных Х5 Tech — Антон Денисов и Михаил Будылин. В предыдущей статье про многоруких бандитов мы показали, как можно искать оптимальную цену в разрезе одного товара. На практике можно встретить ограничение на группу товаров, например, товары категории не должны быть в среднем дороже, чем товары конкурентов. Такое ограничение иногда называют ценовым индексом.

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

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

Оптимизационная задача

Обозначения

Введём следующие обозначения:

- количество товаров,

- количество перебираемых цен для каждого товара $i=\overline{1,n}$ ,

$p \in \mathbb{R}^{n \times m}$ , $p_{i, j}$ - - ая цена товара ,

$p^{(c)} \in \mathbb{R}^{n}$ , $p^{(c)}_{i}$ - средне-рыночная цена товара ,

$c_{i}$ - себестоимость товара ,

$I = \frac{1}{n} \sum_{i=1}^{n} \frac{p_i}{p^{(c)}_{i}}$ - рыночный индекс с ценами сети $p_{i}$ и ценами рынка $p^{(c)}_{i}$ для товаров
$i=\overline{1, n}$

$I_{l}, I_{u}$ - нижняя и верхняя границы индекса по рынку, устанавливаемые экспертно или из исторических данных.

$q \in \mathbb{R}^{n \times m}$ , $q_{i, j}$ - с.в. продаж товара по цене с распределением $Poisson(\lambda_{i, j})$ ,

$\lambda \in \mathbb{R}^{n \times m}$ , $\lambda_{i, j}$ - мат. ожидание продаж товара , по цене .

Постановка задачи

Будем оптимизировать ожидаемую валовую прибыль, целевая функция которой записывается следующим образом:

$M = \mathbb{E} \sum_{i=1}^{n}\sum_{j=1}^{m} (p_{i,j}- с_{i}) \cdot q_{i,j} \cdot x_{i,j} \to \max_{x} \qquad \qquad (1)$

Для каждого товара выбирается ровно одна цена из набора( $x_{i, j} \in \{0, 1\}$ ):

$\sum_{j=1}^{m} x_{i, j} = 1, \ i=\overline{1, n} \qquad \qquad \qquad (2)$

Рыночное позиционирование (иногда называемое ценовым индексом) ограничено сверху и снизу, оно описывается следующим неравенством:

$I_{l} \leqslant \sum_{i=1}^{n} \sum_{j=1}^{m} \frac{p_{i, j}}{p_{i}^{(c)}} x_{i, j} \leqslant I_{u} \qquad \qquad (3)$

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

Примеры используемых модельных данных

Таблица 1. Набор цен и себестоимостей для поиска цен группы товаров

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

					$p^{(c)}$
товар 1	100	110	120	130	105	80
товар 2	50	55	60	65	60	45
товар 3	10	11	12	13	11	9
товар 4	40	45	50	55	40	39
товар 5	70	75	80	85	80	65

Таблица 2. Набор значений спроса для заданной сетки цен

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

	$\lambda(p_1)$	$\lambda(p_2)$	$\lambda(p_3)$	$\lambda(p_4)$
товар 1	4.0	3.5	3.0	2.0
товар 2	3.0	2.0	2.0	1.0
товар 3	7.0	5.0	4.0	2.8
товар 4	9.0	8.6	8.3	8.0
товар 5	3.0	2.6	2.0	1.3

Решение оптимизационной задачи (1-3) для данных таблиц (1-2)

Задача (1-3) является задачей целочисленного линейного программирования, которая будет решаться с помощью библиотеки Pyomo в Python и солвера Highs.

Далее будем сравнивать задачу без ограничения (1-2) с задачей с ограничением (1-3).

Оптимальное решение задач для приведённых в Таблицах (1-2) значений с точки зрения целевой функции и индекса:

задача (1-2): $p_{opt} = [120,\ 60,\ 12,\ 55,\ 80]$ ; $M_{opt} = 320.0$ ; $I_{opt} = 1.122$ ;

задача (1-3): $p_{opt} = [110,\ 50,\ 10,\ 55,\ 70]$ ; $M_{opt} = 270.0$ ; $I_{opt} = 1.008$ .

Полученные значения мы будем использовать для сравнения с результатами моделирования.

Схема экспериментов с RL

Стратегией поиска решения будет алгоритм сэмплирования Томпсона.

Процесс обновления параметров похож на описанный ранее в случае поиска лучшей цены для одного товара. Отличие в том, что на каждой итерации после шага сэмплирования решается описанная выше оптимизационная задача (1-2) или (1-3).

Схема алгоритма:

Результаты моделирования

Параметры экспериментов

Для запуска моделей будем использовать:

сетку перебираемых цен (таблица 1);
таблицу значений спроса $\lambda$ (таблица 2);
значения для границ рыночного индекса $I_{l}$ и $I_{u}$ равны, соответственно, 0.98 и 1.02.

Параметры априорного распределения спроса $\lambda_{i,j}$ ~ $Gamma(\alpha_{i, j}, \beta_{i, j})$ , которое является сопряжённым к распределению Пуассона, задаются следующими способами:

Задаём одинаковое значение $\alpha$ из набора 2, 4, 12, а параметр $\beta = 1$ ;
Для каждого товара оцениваем $\alpha_{i}$ на предыстории продаж в 30 шагов, считая, что для каждого товара установлена цена $p_{i, 2}$ , а $\beta_{i, j} = 1.$

Метрики для анализа

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

$M_{k} = \mathbb{E} M_{opt, k}$ - мат.ожидание оптимального решения с помощью многорукого бандита на шаге .
$Regret_{k} = \mathbb{E} [M_{opt} - M_{k}]$ - мат.ожидание отклонения решения, полученного с помощью алгоритма от теоретического оптимального значения целевой функции на шаге .
$CumulativeRegret_{k} = \sum_{k'=1}^{k} Regret_{k'}$ - накопленный к шагу .
$I_{k} = \mathbb{E}\frac{1}{n} \sum_{i=1}^{n} \frac{p_{i}^{(opt, k)}}{p_{i}^{(c)}}$ - мат.ожидание ценового индекса оптимального решения $p^{(opt, k)}$ на шаге .

Динамика регрета при различных параметрах инициализации

Сравним поведение Regret для каждой из задач (1-2) (без ограничения на индекс) и (1-3) (с ограничением на индекс) в зависимости от начальной инициализации априорного распределения оценки спроса $\lambda.$
Значение pre_30 соответствует среднему значению на истории, взятому за 30 шагов до начала запуска алгоритма при цене $p_{2}$ .

Рис. 2. Динамика Regret для задачи без ограничения на индекс

Рис. 3. Динамика Regret для задачи с ограничением на индекс

Рис. 4. Динамика накопленного Regret для задачи без ограничения на индекс

Рис. 5. Динамика накопленного Regret для задачи с ограничением на индекс

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

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

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

Рис. 6. Сравнение динамики Regret для двух типов задач

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

Динамика целевого показателя

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

Динамика ценового индекса

Рис. 8. Динамика среднего ценового индекса

Как мы видим по динамике индекса, на начальных шагах он поднимается близко к верхней границе. Связано это с тем, что априорные оценки продаж по каждому товару задаются одинаково для всех цен одного товара, то есть заведомо на старте алгоритм приоритетно выбирает наибольшие цены, ( $(p-c) \cdot q$ ( q = const ) – очевидно, что максимум достигается при наибольшей допустимой цене с учётом ограничений). После исследования области с высокой ценой алгоритм переходит на поиск в области более низких цен, и постепенно это приводит к понижению индекса с выходом на теоретическое значение.

Выбор оптимального решения

Последний вопрос, который мы разберём в этой статье – как выбрать окончательное оптимальное решение? Опишем два подхода выбора финального решения.

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

Оба подхода обоснованы тем, что в ходе работы алгоритма всё чаще и чаще выбирается наилучшее решение, это мы можем наблюдать на графиках Regret'а на рис. (2-3).
Будем использовать второй подход – выбор наиболее частого решения алгоритма за последние шагов.

Сравним статистику отклонения выбранного решения от истинного оптимального (4-5) для каждой из задач с инициализацией pre_30 по значению валовой прибыли. Общее количество шагов для выбора лучшего решения выберем 1000, а период последних шагов – 100.

Рис. 9. Распределение дельты валовой прибыли для найденного решения с оптимальным для задачи без ограничения

Рис. 10. Распределение дельты валовой прибыли для найденного решения с оптимальным для задачи с ограничением

Как мы можем наблюдать на рис. (9-10), критерий выбора решения может выбрать субоптимальное решение с ненулевой вероятностью.

В моделируемых экспериментах доля выбора оптимального значения (которую можно считать оценкой вероятности выбора оптимума) 0.931 для задачи (1-2) и 0.929 для задачи (1-3).

Выводы

В данной статье мы:

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