Последовательная структура принятия решений с байесовским обучением
Делиться
Мы часто принимаем решения в условиях неопределённости. Не один раз, а последовательно. Мы полагаемся на свой прошлый опыт и ожидания относительно будущего, чтобы сделать максимально обоснованный и оптимальный выбор.
Представьте себе компанию, предлагающую несколько видов продукции. Эти товары закупаются по себестоимости и продаются с прибылью. Однако нераспроданные запасы могут облагаться комиссией за пополнение запасов, иметь ликвидационную стоимость или, в некоторых случаях, подлежат полной утилизации.
Таким образом, перед компаниями встаёт важнейший вопрос: сколько товара хранить на складе? Это решение часто приходится принимать до того, как спрос станет полностью известен, то есть в условиях цензурированного спроса. Если у компании избыток товара на складе, она учитывает полный спрос, поскольку все запросы клиентов удовлетворены. Но если у неё дефицит товара на складе, она видит только превышение спроса над предложением, а фактический спрос остаётся неизвестным, что делает это цензурированным наблюдением.
Этот тип задач часто называют моделью продавца газет . В таких областях, как исследование операций и прикладная математика, оптимальное решение о хранении изучается на примере классической задачи о хранении газет; отсюда и название.
В этой статье мы исследуем структуру последовательного принятия решений для задачи складирования в условиях неопределенности и разрабатываем динамический алгоритм оптимизации с использованием байесовского обучения.
Наш подход в значительной степени соответствует структуре, изложенной Уорреном Б. Пауэллом в работе «Обучение с подкреплением и стохастическая оптимизация» (2019), и реализует статью Негоеску, Пауэлла и Фрейзера (2011) «Оптимальные политики обучения для проблемы поставщика новостей с цензурированным спросом и ненаблюдаемыми потерянными продажами», опубликованную в журнале Operations Research.
Настройка проблемы
Следуя подходу, аналогичному подходу Негоеску и др., мы формулируем задачу как оптимизацию уровня запасов одного товара на протяжении последовательности временных шагов. Себестоимость и продажная цена считаются фиксированными. Нераспроданные запасы списываются без остаточной стоимости, в то время как каждая проданная единица товара приносит доход. Спрос неизвестен, и если имеющийся запас меньше фактического спроса, наблюдение за спросом считается цензурированным.
Для целей моделирования спрос ( W ) в каждом периоде берется из экспоненциального распределения с неизвестным параметром скорости.
[
begin{align}
x &in mathbb{R}_+ &&: text{Количество заказа (переменная решения)} \
W &sim mathrm{Экспоненциальный}(lambda) &&: text{Случайный спрос с неизвестным параметром скорости } lambda \
lambda &&&: text{Уровень спроса (неизвестно, предстоит оценить)} \
c &&&: text{Стоимость единицы товара для закупки или производства} \
p &&&: text{Цена продажи единицы товара (предположим } p > c text{ для рентабельности)}
end{выровнено}
]
Параметр (lambda) в экспоненциальном распределении представляет скорость спроса , то есть скорость возникновения событий, связанных со спросом. Средний спрос определяется по формуле (mathbb{E}[W] = frac{1}{lambda}).
Из функции плотности вероятности (ФПВ) экспоненциального распределения можно увидеть, что более высокие значения спроса (W) становятся менее вероятными. Таким образом, экспоненциальное распределение является подходящим выбором для моделирования спроса.
Последовательная формулировка решения
Мы формулируем задачу управления запасами как последовательный процесс принятия решений в условиях неопределенности. Цель — максимизировать общую ожидаемую прибыль в течение конечного временного горизонта (N ), одновременно изучая неизвестный уровень спроса, применяя принципы байесовского обучения.
Мы определяем модель с начальным состоянием и вероятностной моделью, отражающей её убеждения относительно будущих состояний с течением времени. На каждом временном шаге модель принимает решение на основе политики, которая сопоставляет её текущие убеждения с действием. Цель — найти оптимальную политику , максимизирующую заданную функцию вознаграждения.
После выполнения действия модель наблюдает за полученным состоянием и соответственно обновляет свое убеждение, продолжая этот цикл принятия решения, наблюдения и обновления убеждения.
1) Переменная состояния
Мы моделируем спрос в каждом периоде как случайную величину, полученную из экспоненциального распределения с неизвестным параметром скорости λ. Поскольку ( lambda ) не поддаётся непосредственному наблюдению, мы кодируем нашу неопределённость относительно её значения с помощью априорной гамма-распределения:
[
lambda sim mathrm{Гамма}(a_0, b_0)
]
Параметры (a_0 ) и (b_0 ) определяют форму и скорость нашего первоначального представления о спросе. Эти два параметра служат нашими переменными состояния . На каждом временном шаге они суммируют всю прошлую информацию и обновляются по мере поступления новых данных о спросе.
По мере сбора большего количества данных апостериорное распределение по (лямбда) эволюционирует от широкой и неопределенной формы к более узкой и уверенной, постепенно концентрируясь вокруг истинной ставки спроса.
Этот процесс естественным образом отражается в гамма-распределении, которое гибко корректирует свою форму в зависимости от объёма полученной информации. На начальном этапе распределение размыто, что свидетельствует о высокой неопределённости. По мере накопления данных уверенность в правильности данных становится более точной, что позволяет принимать более надёжные и оперативные решения. Функция плотности вероятности (ПВ) гамма-распределения представлена ниже:
Позже мы определим функцию перехода , которая обновляет состояние, то есть то, как ( (a_n, b_n) ) превращается в ( (a_{n+1}, b_{n+1}) ), на основе новых наблюдаемых данных. Это позволяет модели постоянно уточнять свои предположения о спросе и принимать более обоснованные решения по управлению запасами с течением времени.
Обратите внимание, что ожидаемое значение гамма-распределения определяется как:
[
mathbb{E}[лямбда] = frac{a}{b}
]
2) Переменная решения
Переменной решения в момент времени ( n ) является уровень запасов:
[
x_n in mathbb{R}_+
]
Это количество единиц товара, которое необходимо заказать до того, как спрос ( W_{n+1} ) будет реализован. Решение зависит только от текущего убеждения ( (a_n, b_n) ).
3) Экзогенная информация
После выбора ( x_n ) выявляется спрос ( W_{n+1} ):
[
W_{n+1} sim text{Exp}(lambda)
]
Поскольку ( лямбда ) неизвестна, спрос носит случайный характер. Наблюдения:
- Нецензурировано , если ( W_{n+1} < x_n ) (мы наблюдаем фактический спрос)
- Отмечено, если ( W_{n+1} ge x_n ) (мы знаем только, что спрос превышает уровни предложения)
Эта цензура ограничивает доступную для обновления убеждений информацию. Даже если полный спрос не наблюдается, цензурированное наблюдение всё равно несёт ценную информацию и не должно игнорироваться в нашем подходе к моделированию.
4) Функция перехода
Функция перехода определяет, как убеждение модели, представленное переменными состояния, обновляется с течением времени. Она сопоставляет предыдущее состояние с ожидаемым будущим, и в нашем случае это обновление управляется байесовским обучением.
Байесовское моделирование неопределенности
Теорема Байеса объединяет априорные убеждения и наблюдаемые данные, формируя апостериорное распределение. Это обновлённое распределение отражает как априорные знания, так и новую наблюдаемую информацию.
[
p_{n+1}(lambda mid w_{n+1}) = frac{p(w_{n+1} mid lambda) cdot p_n(lambda)}{p(w_{n+1})}
]
Где:
[
p(w_{n+1} mid lambda) : text{ Вероятность нового наблюдения в момент времени } n+1
]
[
p_n(lambda) : text{ Предыдущее в момент времени } n
] [
p(w_{n+1}) : text{ Предельное правдоподобие (константа нормализации) в момент времени } n+1
] [
p_{n+1}(lambda mid w_{n+1}) : text{ Апостериорная функция после наблюдения } w_{n+1}
]
Мы ставим задачу таким образом, что в каждом периоде спрос W определяется экспоненциальным распределением. Априорное представление о λ будет моделироваться с помощью гамма-распределения.
[
p_{n+1}(лямбда mid w_{n+1})
=
frac{
underbrace{lambda e^{-lambda w_{n+1}}}_{text{Вероятность}}
cdot
underbrace{frac{b_n^{a_n}}{Gamma(a_n)} lambda^{a_n – 1} e^{-b_n lambda}}_{text{Априор (Гамма)}}
}{
underbrace{
int_0^infty lambda e^{-lambda w_{n+1}} cdot frac{b_n^{a_n}}{Gamma(a_n)} lambda^{a_n – 1} e^{-b_n lambda} , dlambda
}_{text{Маргинальное (доказательство)}}
}
]
Гамма-распределение и экспоненциальное распределение образуют хорошо известное сопряженное априорное распределение в байесовской статистике. При использовании гамма-априорного распределения и экспоненциального правдоподобия результирующее априорное распределение также является гамма-распределением. Это свойство априорного и апостериорного распределений принадлежать одному и тому же семейству распределений и определяет сопряженное априорное распределение. Апостериорное распределение также принадлежит к семейству гамма-распределений, что значительно упрощает байесовское обновление.
Для справки, подобные сопряжённые обновления в замкнутой форме можно найти в стандартных таблицах сопряжённых априорных распределений, например, в Википедии. Используя эту ссылку, мы можем сформулировать апостериорную функцию следующим образом:
Позволять:
[
lambda mid w_1, dots, w_n sim mathrm{Gamma}left(a_0 + n, b_0 + sum_{i=1}^n w_iright)
]
[
lambda sim mathrm{Гамма}(a_0, b_0) quad : text{ Приор}
]
[
w sim mathrm{Exp}(lambda) quad : text{ Вероятность}
]
Для n независимых наблюдений ( w_1, dots, w_n ) априорное гамма-распределение и экспоненциальное правдоподобие приводят к апостериорному гамма-распределению:
После наблюдения единственного (неотредактированного) спроса ( w ) апостериорная вероятность упрощается до следующей:
[
lambda mid w sim mathrm{Gamma}(a_0 + 1, b_0 + w)
]
- Параметр формы увеличивается на 1, поскольку обнаружена одна новая точка данных.
- Параметр скорости увеличивается на ( w ), поскольку экспоненциальное правдоподобие включает в себя член ( e^{-lambda w} ), который объединяется с экспоненциальным членом априорной вероятности и добавляется к общей экспоненте.
Функция обновления
Апостериорные параметры (переменные состояния) обновляются на основе характера наблюдения:
- Без цензуры (( W_{n+1} < x_n )):
[
a_{n+1} = a_n + 1, quad b_{n+1} = b_n + W_{n+1}
]
- Отмечено цензурой (( W_{n+1} ge x_n )):
[
a_{n+1} = a_n, quad b_{n+1} = b_n + x_{n}
]
Эти обновления отражают то, как каждое наблюдение, полное или частичное, информирует о апостериорном убеждении относительно ( lambda ).
Мы можем определить функцию перехода в Python следующим образом:
из ввода import Tuple def transition_a_b( a_n: float, b_n: float, x_n: float, W_n1: float ) -> Tuple[float, float]: «»» Обновляет апостериорные параметры (a, b) после наблюдения за спросом. Аргументы: a_n (float): Текущий параметр формы априорной гаммы. b_n (float): Текущий параметр скорости априорной гаммы. x_n (float): Объём заказа в момент времени n. W_n1 (float): Наблюдаемый спрос в момент времени n+1 (может быть цензурирован). Возвращает: Tuple[float, float]: Обновлённые значения (a_{n+1}, b_{n+1}). «»» if W_n1 < x_n: # Без цензуры: наблюдается полный спрос a_n1 = a_n + 1 b_n1 = b_n + W_n1 else: # Отредактировано: известно только, что W >= x a_n1 = a_n b_n1 = b_n + x_n возвращает a_n1, b_n1
5) Целевая функция
Модель ищет политику ( пи ), сопоставляя убеждения с решениями о размещении запасов с целью максимизации общей ожидаемой прибыли.
- Прибыль от заказа ( x_n ) единиц и удовлетворения спроса ( W_{n+1} ):
[
F(x_n, W_{n+1}) = p cdot min(x_n, W_{n+1}) – c cdot x_n
]
- Общая цель:
[
макс_пи mathbb{E} left[ сумма_{n=0}^{N-1} F(x_n, W_{n+1}) right]
]
- ( пи ) отображает ( (a_n, b_n) ) в ( x_n )
- ( p ) — это продажная цена за проданную единицу
- ( c ) — стоимость единицы заказа
- Непроданные единицы списываются без какой-либо ликвидационной стоимости.
Обратите внимание, что эта целевая функция максимизирует только ожидаемую немедленную выгоду на всем временном горизонте. В следующем разделе мы представим расширенную версию, учитывающую ценность будущего обучения. Это стимулирует модель к исследованиям, учитывая информацию, которую цензурированный спрос может раскрыть с течением времени.
Мы можем определить функцию прибыли в Python следующим образом:
def profit_function(x: float, W: float, p: float, c: float) -> float: «»» Функция прибыли определяется как: F(x, W) = p * min(x, W) — c * x. Она представляет собой вознаграждение, полученное при удовлетворении спроса W при наличии запасов x, получении цены p за проданную единицу и понесении затрат c за заказанную единицу. Аргументы: x (float): Уровень запасов / переменная решения. W (float): Реализованный спрос. p (float, необязательно): Цена продажи единицы. c (float, необязательно): Себестоимость единицы. Возвращает: float: Прибыль (вознаграждение) за этот период. «»» return p * min(x, W) — c * x
Функции политики
Мы определим несколько политических функций, как это определено Негоеску и др., которые будут обновлять значение (x_{n+1}) (уровень запасов) на основе наших текущих представлений о состоянии ((a_{n}, b_{n})).
1) Политика точечной оценки
В рамках этой политики модель оценивает неизвестную норму спроса (lambda) с использованием текущей апостериорной вероятности и выбирает объем заказа ( x_{n+1} ) для максимизации немедленной ожидаемой прибыли.
В момент времени (n) текущая апостериорная функция относительно (lambda ~ Gamma(a_{n}, b_{n})) равна:
[
hat{lambda}_n = frac{a_n}{b_n}
]
Мы рассматриваем эту оценку как «истинное» значение (lambda) и предполагаем спрос (W sim text{Exp}(hat{lambda}_n)).
Ожидаемое значение
Прибыль для объема заказа (x) и реализованного спроса (W) составляет:
[
F(x, W) = p cdot min(x, W) – c cdot x
]
Мы стремимся максимизировать ожидаемую прибыль.
[
max_{x geq 0} quad mathbb{E}_W left[ p min(x, W) – cx right]
]
Ожидаемое значение случайной величины:
[
mathbb{E}[X] = int_{-infty}^{infty} x cdot f(x) , dx
]
Таким образом, целевую функцию можно записать в виде:
[
max_{x geq 0} left[ p left( int_0^xw f_W(w) , dw + x int_x^infty f_W(w) , dw right) – cx right]
]
Где:
- (f_W(x)): Функция плотности вероятности (PDF) спроса, оцененная при (x)
Плотность плотности вероятности (Exponential(lambda)) составляет:
[
f_W(w) = hat{lambda}_n e^{-hat{lambda}_n w}
]
Эту проблему можно решить следующим образом:
[
mathbb{E}[F(x, W)] = p cdot frac{1 – e^{-hat{lambda}_n x}}{hat{lambda}_n} – cx
]
Условие оптимальности первого порядка
Приравниваем производную функции ожидаемой прибыли к нулю и решаем относительно (x), чтобы найти стоимость запасов, которая максимизирует ожидаемую прибыль:
[
frac{d}{dx} mathbb{E}[F(x, W)] = pe^{-hat{lambda}_n x} – c = 0
]
[
e^{-hat{lambda}_n x^*} = frac{c}{p}
quad Стрелка вправо quad
x^* = frac{1}{hat{lambda}_n} logleft( frac{p}{c} right)
]
Подставим (hat{lambda}_n = frac{a_n}{b_n}):
[
x_n = frac{b_n}{a_n} logleft( frac{p}{c} right)
]
Реализация Python:
import math def point_estimate_policy( a_n: float, b_n: float, p: float, c: float ) -> float: «»» Политика точечной оценки выбирает x_n на основе апостериорного среднего в момент времени n. Аргументы: a_n (float): Параметр формы гаммы в момент времени n. b_n (float): Параметр скорости гаммы в момент времени n. p (float): Цена продажи за единицу. c (float): Себестоимость единицы. Возврат: float: Уровень запасов x_n «»» lambda_hat = a_n / b_n return (1 / lambda_hat) * math.log(p / c)
2) Политика распространения
Политика распределения оптимизирует ожидаемую немедленную прибыль, интегрируя её по всему текущему распределению ожидаемого спроса (lambda). В отличие от политики точечной оценки, она не сворачивает апостериорную вероятность к одному значению.
В момент времени (n) убеждение относительно (лямбда) следующее:
[
лямбда сим текст{Гамма}(a_n, b_n)
]
Спрос моделируется следующим образом:
[
W sim text{Exp}(lambda)
]
Эта политика выбирает размер заказа (x_{n}) путем максимизации ожидаемой немедленной прибыли, усредненной как по неопределенности спроса, так и по неопределенности (lambda)
[
x_n = argmax_{x ge 0} mathbb{E}_{lambda sim text{Гамма}(a_n, b_n)} left[ mathbb{E}_{W sim text{Эксп}(lambda)} left[ p cdot min(x, W) – cx right] right]
]
Это ожидаемая немедленная прибыль, усредненная с учетом неопределенности спроса и неопределенности (лямбда).
Ожидаемое значение
Из предыдущей политики мы знаем, что:
[
mathbb{E}_W[min(x, W)] = frac{1 – e^{-hat{lambda}_n x}}{hat{lambda}_n}
]
Таким образом:
[
mathbb{E}_{lambda} left[ mathbb{E}_{W mid lambda}[min(x, W)] right]
= mathbb{E}_{lambda} left[ frac{1 – e^{-lambda x}}{lambda} right]
]
Если обозначить плотность гамма-излучения как:
[
f(lambda) = frac{b^a}{Gamma(a)} lambda^{a – 1} e^{-b lambda}
]
Тогда ожидание становится:
[
mathbb{E}_lambda left[ frac{1 – e^{-lambda x}}{lambda} right]
=int_0^infty frac{1 – e^{-lambda x}}{lambda} f(lambda) , dlambda
= frac{b^a}{Gamma(a)} int_0^infty (1 – e^{-lambda x}) lambda^{a – 2} e^{-b lambda} , dlambda
]
Не вдаваясь в полное доказательство, ожидание принимает вид:
[
mathbb{E}[text{Прибыль}] = p cdot mathbb{E}_{lambda} left[ frac{1 – e^{-lambda x}}{lambda} right] – cx
= p cdot frac{b}{a – 1} left(1 – left( frac{b}{b + x} right)^{a – 1} right) – cx
]
Условие оптимальности первого порядка
Снова устанавливаем производную функции ожидаемой прибыли равной нулю и решаем относительно (x), чтобы найти стоимость запасов, которая максимизирует ожидаемую прибыль:
[
frac{d}{dx} mathbb{E}[text{Прибыль}]
= frac{d}{dx} left[ p cdot frac{b}{a – 1} left(1 – left( frac{b}{b + x} right)^{a – 1} right) – cx right] = 0
]
Не вдаваясь в доказательство, выражение в закрытой форме, основанное на статье Негоеску и др., выглядит следующим образом:
[
x_n = b_n left( left( frac{p}{c} right)^{1/a_n} – 1 right)
]
Реализация Python:
def distribution_policy( a_n: float, b_n: float, p: float, c: float ) -> float: «»» Политика распределения выбирает x_n путем интегрирования по полной апостериорной вероятности в момент времени n. Аргументы: a_n (float): Параметр формы гамма-распределения в момент времени n. b_n (float): Параметр скорости гамма-распределения в момент времени n. p (float): Цена продажи за единицу. c (float): Себестоимость единицы. Возврат: float: Уровень запасов x_n «»» возврат b_n * ((p / c) ** (1 / a_n) — 1)
Политика градиента знаний (KG)
Политика градиента знаний (KG) — это байесовская политика обучения, которая уравновешивает эксплуатацию (максимизацию немедленной прибыли) и исследование (заказ на получение информации о спросе для будущих решений).
Вместо того чтобы просто максимизировать сегодняшнюю прибыль, KG выбирает такой объем заказа, который максимизирует:
Прибыль сейчас + ценность полученной информации для будущего
[
x_n = argmax_x mathbb{E}left[ p cdot min(x, W_{n+1}) – cx + V(a_{n+1}, b_{n+1}) mid a_n, b_n, x right]
]
Где:
- (W_{n+1} sim text{Exp}(lambda)) (с (lambda sim text{Gamma}(a_n, b_n)))
- (V(a_{n+1}, b_{n+1})) — это значение ожидаемой будущей прибыли при обновленных убеждениях после наблюдения (W_{n+1})
Мы не знаем значения (a_{n+1}, b_{n+1}) в момент времени (n), поскольку мы ещё не наблюдали спрос. Поэтому мы вычисляем их ожидаемое значение при возможных результатах наблюдения (с цензурой и без цензуры).
Затем политика KG оценивает каждый потенциальный объем запаса (x) по:
- Моделирование его влияния на апостериорные убеждения
- Расчет немедленной прибыли
- Расчет ценности будущего обучения на основе обновлений убеждений
Целевая функция
Мы определяем общую ценность выбора (x) в момент времени (n) как:
[
F_{text{KG}}(x) = underbrace{mathbb{E}[p cdot min(x, W) – cx]}_{text{Немедленная прибыль}} + underbrace{(N – n) cdot mathbb{E}_{text{аудиторная вероятность}} left[ max_{x'} mathbb{E}_{lambda sim text{аудиторная вероятность}}[ p cdot min(x', W) – c x' ] right]}_{text{Ценность обучения}}
]
- Первый член — это просто ожидаемая немедленная прибыль.
- Второй член учитывает, как этот выбор увеличивает будущую прибыль, усиливая наше убеждение относительно (лямбда).
- Фактор горизонта ((Nn)): В будущем мы будем принимать ((Nn)) больше решений. Таким образом, ценность более удачных решений, принятых благодаря сегодняшнему обучению, умножается на этот фактор.
- Апостериорное усреднение (mathbb{E}_{text{posterior}}[⋅]): Это означает, что мы усредняем все возможные апостериорные убеждения, которые могут возникнуть после наблюдения за результатом спроса. Поскольку спрос случаен и, возможно, подвергается цензуре, мы не получим идеальную информацию, но обновим наше убеждение.
В статье используется ранее обсуждавшаяся политика распределения в качестве прокси-параметра для оценки функции будущей стоимости. Таким образом:
[
x^*(a, b) = V(a, b) = frac{bp}{a – 1} left( 1 – left( frac{b}{b + x^*} right)^{a – 1} right) – cx^* = b left( left( frac{p}{c} right)^{1/a} – 1 right)
]
Ожидаемое значение
Ожидаемое значение (V) выражается следующим образом, согласно Негоеску и др. Поскольку доказательство этого уравнения довольно сложное, мы не будем вдаваться в подробности.
[
begin{align*}
mathbb{E}[V] &= mathbb{E} left[ mathbb{E} left[ b^{n+1} left( frac{p}{a^{n+1} – 1} left( 1 – left( frac{c}{p} right)^{1 – frac{1}{a^{n+1}}} right) – c left( left( frac{c}{p} right)^{-frac{1}{a^{n+1}}} – 1 right) right) Big| lambda right] Big| a^n, b^n, x^n right] \
&= mathbb{E} left[ int_0^{x^n} left( b^n + y right) left( frac{p}{a^n} left( 1 – left( frac{c}{p} right)^{1 – frac{1}{a^{n+1}}} right) – c left( left( frac{c}{p} right)^{-frac{1}{a^{n+1}}} – 1 right) right) lambda e^{-lambda y} , dy right. \
&quad + left. int_{x^n}^{infty} left( b^n + x^n right) left( frac{p}{a^n – 1} left( 1 – left( frac{c}{p} right)^{1 – frac{1}{a^n}} right) – c left( left( frac{c}{p} right)^{-frac{1}{a^n}} – 1 right) right) lambda e^{-lambda y} , dy right].
end{align*}
]
Поскольку нам уже известно ожидаемое значение функции немедленной прибыли, описанное в предыдущих вариантах политики, мы можем выразить аддитивное ожидаемое значение политики KG как сумму. Поскольку это уравнение довольно длинное, мы не будем вдаваться в подробности, но его можно найти в статье.
Условие оптимальности первого порядка
В этой политике мы также приравниваем производную функции ожидаемой прибыли к нулю и решаем уравнение относительно (x), чтобы найти стоимость запасов, максимизирующую ожидаемую прибыль. Решение уравнения в замкнутой форме, основанное на данной работе, выглядит следующим образом:
[
x_n = b_n left[ left( frac{r}{1 + (N – n) cdot left( 1 + frac{a_n r}{a_n – 1} – frac{(a_n + 1) r}{a_n} right)} right)^{-1 / a_n} – 1 right]
]
Где:
- (r = frac{c}{p}): Соотношение стоимости и цены
Реализация Python:
def knowledge_gradient_policy( a_n: float, b_n: float, p: float, c: float, n: int, N: int ) -> float: «»» Политика градиента знаний, политика одношагового прогнозирования для экспоненциального спроса с апостериорной функцией Gamma(a_n, b_n). Аргументы: a_n (float): Параметр формы Gamma в момент времени n. b_n (float): Параметр скорости Gamma в момент времени n. p (float): Цена продажи за единицу. c (float): Стоимость единицы за единицу. n (int): Индекс текущего периода (с отсчетом от 0). N (int): Общее количество периодов в горизонте. Возвращает: float: Уровень запасов x_n «»» a = max(a_n, 1.001) # Избегайте деления на ноль для малых значений формы r = c / p future_factor = (N — (n + 1)) / N корректировка = 1.0 — future_factor * (1,0 / а) скорректированный_r = мин(макс(r * корректировка, 1e-4), 0,99) вернуть b_n * ((1 / скорректированный_r) ** (1 / а) — 1)
Оценка политики Монте-Карло
Чтобы оценить политику (pi) в стохастической среде, мы моделируем ее эффективность на основе нескольких выборочных путей спроса.
Позволять:
- (M) — число независимых симуляций (путей спроса), каждое из которых обозначается (omega^m) для (m = 1, 2, dots, M)
- (N) — временной горизонт
- (p_n(omega^m)) — смоделированная цена в момент времени (n) на пути (m)
- (x_n(omega^m)) — решение, принятое в момент времени (n) в соответствии с политикой (pi) на пути (n)
Накопительная награда за один путь
Для каждого пути-образца (omega^m) вычислите общую награду:
[
hat{F}^пи(omega^m) = sum_{n=0}^{N-1} left[ p cdot minleft(x_n(omega^m), W_{n+1}(omega^m)right) – c cdot x_n(omega^m) right]
]
Это представляет собой реализованную стоимость политики (пи) вдоль этой конкретной траектории.
Реализация Python:
import numpy as np def simulator_policy( N: int, a_0: float, b_0: float, lambda_true: float, policy_name: str, p: float, c: float, seed: int = 42 ) -> float: «»» Моделирует последовательный процесс принятия решений по инвентаризации с использованием указанной политики. Args: N (int): Количество периодов времени. a_0 (float): Начальный параметр формы априорной гаммы. b_0 (float): Начальный параметр скорости априорной гаммы. lambda_true (float): Истинная экспоненциальная ставка спроса. policy_name (str): Одно из {'point_estimate', 'distribution', 'knowledge_gradient'}. p (float): Цена продажи за единицу. c (float): Стоимость закупки за единицу. seed (int): Случайное начальное число для воспроизводимости. Returns: float: Общая накопленная прибыль за N периодов. «»» np.random.seed(seed) a_n, b_n = a_0, b_0 rewards = [] for n in range(N): # Выберите количество заказов на основе указанной политики if policy_name == «point_estimate»: x_n = point_estimate_policy(a_n=a_n, b_n=b_n, p=p, c=c) elif policy_name == «distribution»: x_n = distribution_policy(a_n=a_n, b_n=b_n, p=p, c=c) elif policy_name == «knowledge_gradient»: x_n = knowledge_gradient_policy(a_n=a_n, b_n=b_n, p=p, c=c, n=n, N=N) else: raise ValueError(f»Unknown policy: {policy_name}») # Выборка спроса W_n1 = np.random.exponential(1 / lambda_true) # Вычислить прибыль и обновить убеждение reward = profit_function(x_n, W_n1, p, c) rewards.append(reward) a_n, b_n = transition_a_b(a_n, b_n, x_n, W_n1) return sum(rewards)
Оценить ожидаемое значение путем усреднения
Ожидаемая выгода от политики (pi) аппроксимируется с использованием выборочного среднего по всем (M) симуляциям:
[
bar{F}^пи = frac{1}{N} sum_{m=1}^{N} hat{F}^пи(omega^m)
]
Это (bar{F}^pi) является несмещенной оценкой истинного ожидаемого вознаграждения при политике (pi).
Реализация Python:
import numpy as np def policy_monte_carlo( N_sim: int, N: int, a_0: float, b_0: float, lambda_true: float, policy_name: str, p: float = 10.0, c: float = 4.0, base_seed: int = 42 ) -> float: «»» Запускает несколько симуляций Монте-Карло для оценки средней совокупной выгоды для заданной политики управления запасами в условиях экспоненциального спроса. Аргументы: N_sim (int): Количество симуляций Монте-Карло для запуска. N (int): Количество временных шагов в каждой симуляции. a_0 (float): Начальный параметр формы гаммы. b_0 (float): Начальный параметр скорости гаммы. lambda_true (float): Истинная скорость экспоненциального спроса. policy_name (str): Имя используемой политики: {«point_estimate», «distribution», «knowledge_gradient»}. p (float): Цена продажи за единицу. c (float): Стоимость закупки за единицу. base_seed (int): Смещение начального значения для воспроизводимости между симуляциями. Возвращает: float: Среднее накопленное вознаграждение за все симуляции. «»» total_rewards = [] for i in range(N_sim): reward = Simulator_policy( N=N, a_0=a_0, b_0=b_0, lambda_true=lambda_true, policy_name=policy_name, p=p, c=c, seed=base_seed + i ) total_rewards.append(reward) return np.mean(total_rewards) # Параметры N_sim = 10000 # Количество симуляций N = 100 # Количество временных периодов a_0 = 10.0 # Начальный параметр формы априорной гаммы b_0 = 5.0 # Начальный параметр скорости априорной гаммы lambda_true = 0,25 # Истинная ставка экспоненциального спроса p = 26,0 # Цена продажи за единицу c = 20,0 # Стоимость единицы base_seed = 1234 # Базовое начальное значение для воспроизводимости results = { policy: policy_monte_carlo( N_sim=N_sim, N=N, a_0=a_0, b_0=b_0, lambda_true=lambda_true, policy_name=policy, p=p, c=c, base_seed=base_seed ) for policy in [«point_estimate», «distribution», «knowledge_gradient»] } print(results)
Результаты
На левом графике показано изменение средней кумулятивной прибыли с течением времени, а на правом — среднее вознаграждение за каждый временной шаг. В результате моделирования мы видим, что политика градиента знаний (KG) значительно превосходит две другие, поскольку оптимизирует не только немедленное вознаграждение, но и будущую стоимость кумулятивного вознаграждения. Политики точечной оценки и распределения работают аналогично.
Из приведенных выше графиков видно, что алгоритм байесовского обучения постепенно сходится к истинному среднему спросу (W).
Эти результаты подчеркивают важность учёта ценности информации при последовательном принятии решений в условиях неопределённости. В то время как более простые эвристические подходы, такие как политика точечной оценки и распределения, ориентированы исключительно на немедленную выгоду, политика градиента знаний использует будущий потенциал обучения, обеспечивая превосходные долгосрочные результаты.
Источник: towardsdatascience.com
