Принцип однократного отклонения для бесконечных повторяющихся игр и динамического программирования

5

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

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

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

academic-graduate dynamic-programming dynamic-games Metta World Peace
источник
Я не понимаю, о чем вопрос. Можете ли вы расширить или объяснить более формально? Динамическое программирование - это просто общая техника, которая полезна только для решения некоторых проблем. Когда это полезно, это потому, что оптимальное решение имеет форму оптимального решения подзадач, а затем принятия оптимального решения на текущем «уровне» с учетом решений подзадач. Поскольку мы принимаем оптимальное решение на каждом этапе или уровне, конечно, любое другое решение или «отклонение» не будет лучше ...
usul

Ответы:

2

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

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

Sander Heinsalu
источник
Спасибо за ваш ответ. Но мне пришло в голову, ваш аргумент справедлив только для стохастического динамического программирования, верно? Что если правило перехода в пространстве состояний является детерминированным?
Metta World Peace
2

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

Исходную ссылку см. В следствии теоремы 1. Вот ,

Michael Greinecker
источник