Стохастическое динамическое программирование
Первоначально представленное Ричардом Э. Беллманом в ( Bellman 1957 ), стохастическое динамическое программирование представляет собой метод моделирования и решения проблем принятия решений в условиях неопределенности . Тесно связанное со стохастическим программированием и динамическим программированием , стохастическое динамическое программирование представляет собой исследуемую проблему в форме уравнения Беллмана . Цель состоит в том, чтобы разработать политику, предписывающую, как оптимально действовать в условиях неопределенности.
Мотивирующий пример: Азартная игра.
[ редактировать ]У игрока есть 2 доллара, ему разрешено сыграть в азартную игру 4 раза, и его цель состоит в том, чтобы максимизировать вероятность того, что в итоге у него останется как минимум 6 долларов. Если игрок ставит $ при ходе игры, то с вероятностью 0,4 она выигрывает игру, возвращает первоначальную ставку и увеличивает свою капитальную позицию на $ ; с вероятностью 0,6 она теряет сумму ставки $ ; все пьесы попарно независимы . В любом ходе игры игрок не может ставить больше денег, чем он имел в своем распоряжении в начале этой игры. [1]
Стохастическое динамическое программирование можно использовать для моделирования этой проблемы и определения стратегии ставок, которая, например, максимизирует вероятность игрока получить богатство в размере как минимум 6 долларов к концу горизонта ставок.
Обратите внимание: если нет ограничений на количество игр, в которые можно играть, проблема становится вариантом известного петербургского парадокса .
Формальный фон
[ редактировать ]Рассмотрим дискретную систему, определенную на этапы, на которых каждый этап характеризуется
- состояние исходное , где — множество возможных состояний в начале этапа ;
- переменная решения , где это набор возможных действий на этапе - Обратите внимание, что может быть функцией начального состояния ;
- немедленная функция затрат/вознаграждения , представляющий стоимость/награду на этапе если это начальное состояние и выбранное действие;
- функция перехода состояний что ведет систему к состоянию .
Позволять представляют оптимальные затраты/вознаграждение, полученные путем следования оптимальной политике на этапах . Без ограничения общности в дальнейшем мы будем рассматривать настройку максимизации вознаграждения. В детерминированном динамическом программировании обычно имеют дело с функциональными уравнениями, имеющими следующую структуру:
где а граничное условие системы есть
Цель состоит в том, чтобы определить набор оптимальных действий, которые максимизируют . Учитывая нынешнее состояние и текущее действие , мы точно знаем, какое вознаграждение будет получено на текущем этапе и – благодаря функции перехода состояний – будущее состояние, к которому переходит система.
Однако на практике, даже если мы знаем состояние системы в начале текущего этапа, а также принятое решение, состояние системы в начале следующего этапа и вознаграждение за текущий период часто являются случайными величинами , которые можно наблюдать лишь в конце текущего этапа.
Стохастическое динамическое программирование имеет дело с задачами, в которых вознаграждение текущего периода и/или состояние следующего периода являются случайными, т.е. с многоступенчатыми стохастическими системами. Цель лица, принимающего решения, — максимизировать ожидаемое (дисконтированное) вознаграждение в течение заданного горизонта планирования.
В своей наиболее общей форме стохастические динамические программы имеют дело с функциональными уравнениями, имеющими следующую структуру:
где
- это максимальная ожидаемая награда, которую можно получить на этапах , данное состояние в начале этапа ;
- принадлежит к множеству возможных действий на этапе данное начальное состояние ;
- – коэффициент дисконтирования ;
- — условная вероятность того, что состояние в конце этапа является учитывая текущее состояние и выбранное действие .
Марковские процессы принятия решений представляют собой особый класс стохастических динамических программ, в которых лежащий в основе случайный процесс является стационарным процессом , обладающим марковским свойством .
Азартная игра как стохастическая динамическая программа.
[ редактировать ]Азартную игру можно сформулировать как стохастическую динамическую программу следующим образом: существуют игры (т.е. этапы ) в горизонте планирования
- государство в период представляет собой первоначальное богатство на начало периода ;
- действие , заданное состояние в период это сумма ставки ;
- вероятность перехода из штата заявить когда действие взят в штат легко выводится из вероятности выигрыша (0,4) или проигрыша (0,6) в игре.
Позволять — вероятность того, что к концу игры 4 у игрока будет не менее 6 долларов при условии, что у него есть в начале игры .
- немедленная прибыль, полученная в случае действия взят в штат определяется ожидаемым значением .
Чтобы вывести функциональное уравнение , определим как ставка, которая достигает , то в начале игры
- если невозможно достичь цели, т.е. для ;
- если цель достигнута, т. для ;
- если игрок должен сделать ставку, достаточную для достижения цели, т.е. для .
Для функциональное уравнение , где колеблется в ; цель состоит в том, чтобы найти .
Учитывая функциональное уравнение, оптимальную политику ставок можно получить с помощью алгоритмов прямой рекурсии или обратной рекурсии, как описано ниже.
Методы решения
[ редактировать ]Стохастические динамические программы можно решить оптимально, используя алгоритмы обратной или прямой рекурсии . Мемоизация обычно используется для повышения производительности. Однако, как и детерминированное динамическое программирование, его стохастический вариант страдает от проклятия размерности . По этой причине приближенные методы решения в практических приложениях обычно используются .
Обратная рекурсия
[ редактировать ]Учитывая ограниченное пространство состояний, обратная рекурсия ( Берцекас 2000 ) начинается с табулирования для каждого возможного состояния относящийся к заключительному этапу . После того, как эти значения сведены в таблицу вместе с соответствующими оптимальными действиями, зависящими от состояния, , можно перейти на сцену и свести в таблицу для всех возможных состояний, принадлежащих сцене . Процесс продолжается, рассматривая в обратном порядке все оставшиеся этапы до первого. После завершения процесса табуляции – ценность оптимальной политики при данном начальном состоянии – а также связанное с ним оптимальное действие можно легко извлечь из таблицы. Поскольку вычисления выполняются в обратном порядке, ясно, что обратная рекурсия может привести к вычислению большого количества состояний, которые не нужны для вычисления .
Пример: Азартная игра.
[ редактировать ]![[икона]](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/20px-Wiki_letter_w_cropped.svg.png){kind=small} | Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( январь 2017 г. ) |
Прямая рекурсия
[ редактировать ]Учитывая исходное состояние системы в начале периода 1, прямая рекурсия ( Берцекас 2000 ) вычисляет путем постепенного расширения функционального уравнения ( проход вперед ). Это включает в себя рекурсивные вызовы для всех которые необходимы для вычисления заданного . Значение оптимальной политики и ее структура затем извлекаются посредством ( обратного прохода ), в ходе которого разрешаются эти приостановленные рекурсивные вызовы. Ключевым отличием от обратной рекурсии является тот факт, что вычисляется только для состояний, которые имеют отношение к вычислению . Мемоизация используется, чтобы избежать повторного расчета уже рассмотренных состояний.
Пример: Азартная игра.
[ редактировать ]Мы проиллюстрируем прямую рекурсию в контексте ранее рассмотренного экземпляра азартной игры. Мы начинаем проход вперед, рассматривая
На данный момент мы еще не рассчитали , которые необходимы для вычисления ; мы продолжаем и вычисляем эти элементы. Обратите внимание, что , поэтому можно использовать мемоизацию и выполнить необходимые вычисления только один раз.
- Расчет
Мы теперь вычислили для всех которые нужны для вычисления . Однако это привело к дополнительным приостановленным рекурсиям, включающим . Мы продолжаем и вычисляем эти значения.
- Расчет
Поскольку этап 4 является последним этапом в нашей системе, представляют собой граничные условия , которые легко вычисляются следующим образом.
- Граничные условия
На этом этапе можно продолжить и восстановить оптимальную политику и ее значение посредством обратного прохода , включающего сначала этап 3.
- Обратный проход с участием
и затем этап 2.
- Обратный проход с участием
Наконец мы восстанавливаем значение оптимальной политики
Это оптимальная политика, которая была проиллюстрирована ранее. Обратите внимание, что существует несколько оптимальных политик, приводящих к одному и тому же оптимальному значению. ; например, в первой игре можно поставить либо 1 доллар, либо 2 доллара.
Реализация на Python. Следующий пример представляет собой полную на Python реализацию этого примера .
from typing import List, Tuple
import functools
class memoize:
def __init__(self, func):
self.func = func
self.memoized = {}
self.method_cache = {}
def __call__(self, *args):
return self.cache_get(self.memoized, args, lambda: self.func(*args))
def __get__(self, obj, objtype):
return self.cache_get(
self.method_cache,
obj,
lambda: self.__class__(functools.partial(self.func, obj)),
)
def cache_get(self, cache, key, func):
try:
return cache[key]
except KeyError:
cache[key] = func()
return cache[key]
def reset(self):
self.memoized = {}
self.method_cache = {}
class State:
"""the state of the gambler's ruin problem"""
def __init__(self, t: int, wealth: float):
"""state constructor
Arguments:
t {int} -- time period
wealth {float} -- initial wealth
"""
self.t, self.wealth = t, wealth
def __eq__(self, other):
return self.__dict__ == other.__dict__
def __str__(self):
return str(self.t) + " " + str(self.wealth)
def __hash__(self):
return hash(str(self))
class GamblersRuin:
def __init__(
self,
bettingHorizon: int,
targetWealth: float,
pmf: List[List[Tuple[int, float]]],
):
"""the gambler's ruin problem
Arguments:
bettingHorizon {int} -- betting horizon
targetWealth {float} -- target wealth
pmf {List[List[Tuple[int, float]]]} -- probability mass function
"""
# initialize instance variables
self.bettingHorizon, self.targetWealth, self.pmf = (
bettingHorizon,
targetWealth,
pmf,
)
# lambdas
self.ag = lambda s: [
i for i in range(0, min(self.targetWealth // 2, s.wealth) + 1)
] # action generator
self.st = lambda s, a, r: State(
s.t + 1, s.wealth - a + a * r
) # state transition
self.iv = (
lambda s, a, r: 1 if s.wealth - a + a * r >= self.targetWealth else 0
) # immediate value function
self.cache_actions = {} # cache with optimal state/action pairs
def f(self, wealth: float) -> float:
s = State(0, wealth)
return self._f(s)
def q(self, t: int, wealth: float) -> float:
s = State(t, wealth)
return self.cache_actions[str(s)]
@memoize
def _f(self, s: State) -> float:
# Forward recursion
values = [sum([p[1]*(self._f(self.st(s, a, p[0])) if s.t < self.bettingHorizon - 1
else self.iv(s, a, p[0])) # value function
for p in self.pmf[s.t]]) # bet realisations
for a in self.ag(s)] # actions
v = max(values)
try:
self.cache_actions[str(s)]=self.ag(s)[values.index(v)] # store best action
except ValueError:
self.cache_actions[str(s)]=None
print("Error in retrieving best action")
return v # return expected total cost
instance = {
"bettingHorizon": 4,
"targetWealth": 6,
"pmf": [[(0, 0.6), (2, 0.4)] for i in range(0, 4)],
}
gr, initial_wealth = GamblersRuin(**instance), 2
# f_1(x) is gambler's probability of attaining $targetWealth at the end of bettingHorizon
print("f_1(" + str(initial_wealth) + "): " + str(gr.f(initial_wealth)))
# Recover optimal action for period 2 when initial wealth at the beginning of period 2 is $1.
t, initial_wealth = 1, 1
print(
"b_" + str(t + 1) + "(" + str(initial_wealth) + "): " + str(gr.q(t, initial_wealth))
)
Java-реализация. GamblersRuin.java — это отдельная Java 8 реализация приведенного выше примера на .
Примерное динамическое программирование
[ редактировать ] | Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( январь 2017 г. ) |
Введение в приближенное динамическое программирование представлено ( Powell 2009 ).
Дальнейшее чтение
[ редактировать ]- Беллман, Р. (1957), Динамическое программирование , Princeton University Press, ISBN 978-0-486-42809-3 . Дуврское издание в мягкой обложке (2003 г.).
- Росс, С.М.; Бимбаум, ZW; Лукач, Э. (1983), Введение в стохастическое динамическое программирование , Elsevier, ISBN 978-0-12-598420-1 .
- Берцекас, Д. П. (2000), Динамическое программирование и оптимальное управление (2-е изд.), Athena Scientific, ISBN 978-1-886529-09-0 . В двух томах.
- Пауэлл, ВБ (2009), «Что следует знать о приблизительном динамическом программировании», Naval Research Logistics , 56 (1): 239–249, CiteSeerX 10.1.1.150.1854 , doi : 10.1002/nav.20347 , S2CID 7134937
См. также
[ редактировать ]
- Теория управления – Отделение техники и математики
- Динамическое программирование - метод оптимизации задачи
- Обучение с подкреплением - Область машинного обучения
- Стохастическое управление - Вероятностное оптимальное управление.
- Случайный процесс – сбор случайных величин.
- Стохастическое программирование - основа моделирования задач оптимизации, связанных с неопределенностью.
Ссылки
[ редактировать ]- ^ Эта проблема адаптирована из книги WL Winston, Operations Research: Applications and Algorithms (7th Edition), Duxbury Press, 2003, глава. 19, пример 3.