Основателем современного подхода к анализу задач последовательного принятия решений был Ричард Беллман [97], который в целом предложил использовать подход на основе динамического программирования и в частности алгоритм итерации по значениям. В тезисах докторской диссертации Рона Говарда [691] введено понятие итерации по стратегиям и изложена идея среднего вознаграждения, предназначенная для применения при решении задач с бесконечным горизонтом. Несколько дополнительных результатов было предложено в [96]. Модифицированный алгоритм итерации по стратегиям описан в [1245] и [1534]. Алгоритм асинхронной итерации по стратегиям был проанализирован Уильямсом и Бердом [1598], которые также доказали свойство граничной убыточности стратегии, рассматриваемое в уравнении 17.9. Результаты анализа обесценивания с точки зрения стационарных предпочтений приведены в [834]. В [120], [121] и [1244] дано строгое введение в проблематику задач последовательного принятия решений. В [1170] описаны результаты исследования вычислительной сложности задач MDP.

Важную роль в ознакомлении сообщества разработчиков в области искусственного интеллекта с задачами MDP сыграли оригинальные работы Саттона [1477] и Уоткинса [1558] по применению методов обучения с подкреплением для решения задач MDP, а также вышедший немного позже обзор [74]. (В более ранней работе [1580] содержались во многом аналогичные идеи, но они не были развиты до такой же степени.) Связь между задачами MDP и задачами планирования в искусственном интеллекте была впервые показана Свеном Кёнигом [817], который также продемонстрировал, что вероятностные операторы Strips позволяют создавать компактные представления для моделей перехода (см. также [1575]). В [359] и [1492] сделана попытка преодолеть комбинаторную сложность больших пространств состояний с использованием ограниченного горизонта поиска и абстрактных состояний. Эвристики, основанные на стоимости информации, могут использоваться для определения в пространстве состояний таких областей, где локальное расширение горизонта приводит к значительному повышению качества решения. Агенты, применяющие такой подход, могут соразмерять свои усилия под давлением дефицита времени и вырабатывать некоторые варианты поведения (такие как использование знакомых "проторенных тропинок") для быстрого поиска путей через пространство состояний без необходимости повторно вычислять в каждой точке оптимальные решения. В опубликованных недавно работах Бутильера и др. [158], [159] основные усилия сосредоточены на динамическом программировании с использованием символических представлений моделей перехода и функций стоимости на основе формул пропозициональной логики и логики первого порядка.