Основателем современного подхода к анализу задач последовательного принятия решений был Ричард Беллман [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] основные усилия сосредоточены на динамическом программировании с использованием символических представлений моделей перехода и функций стоимости на основе формул пропозициональной логики и логики первого порядка.
  В [47] впервые было показано, что задачи MDP в частично наблюдаемой среде могут быть преобразованы в обычные задачи MDP с использованием доверительных состояний. Первый полный алгоритм точного решения для марковских процессов принятия решений в частично наблюдаемой среде (Partially-Observable Markov Decision Process— POMDP) был предложен Эдвардом Сондиком [1446] в его докторской диссертации (опубликованная позднее журнальная статья Смоллвуда и Сондика [1433] содержит некоторые ошибки, но является более доступной). В [946] приведен обзор состояния разработок в области решения задач POMDP. Первым значительным вкладом в рамках искусственного интеллекта был алгоритм Witness [227], [758] — усовершенствованная версия алгоритма итерации по значениям, применяемого для решения задач POMDP. Вслед за ним вскоре были разработаны другие алгоритмы, в том числе основанные на подходе, предложенном Хансеном [612], который предусматривает инкрементное определение стратегии с помощью конечного автомата. В представлении стратегии с помощью конечного автомата доверительные состояния непосредственно соответствуют конкретным состояниям автомата. Приближенно оптимальные стратегии для задач POMDP могут формироваться с помощью прямого поиска, применяемого в сочетании с формированием выборок из возможных результатов наблюдений и действий [784], [1134]. Другие результаты исследований в области алгоритмов POMDP описаны в главе 21.
  Основные идеи по созданию архитектуры агента с использованием динамических сетей принятия решений были предложены в [360]. В книге Planning and Control Дина и Уэллмана [363] этот подход развит намного глубже и установлена связь между моделями DBN/DDN и классической литературой теории управления, посвященной вопросам фильтрации. Татмен и Шахтер [1497] показали, как применять алгоритмы динамического программирования к моделям DDN. В [1325] описаны различные способы обеспечения применения таких агентов в более широких масштабах и указан ряд нерешенных исследовательских проблем.
  Корни теории игр можно проследить до предложений по изучению конкурентных и кооперативных взаимодействий людей с помощью научного и математического подхода, которые были выдвинуты еще в XVII столетии Христианом Гюйгенсом и Готфридом Лейбницем. На протяжении XIX столетия некоторые ведущие экономисты создавали простые математические модели для анализа конкретных примеров конкурентных ситуаций. Первые формальные результаты в области теории игр принадлежат Цермело [1641], который за год до этого предложил некоторую форму минимаксного поиска для игр, хотя и неправильную. Эмиль Борель [152] ввел понятие смешанной стратегии. Джон фон Нейман [1545] доказал, что любая игра с двумя участниками и нулевой суммой имеет максиминное равновесие в смешанных стратегиях и полностью определенное значение. Сотрудничество Джона фон Неймана с экономистом Оскаром Моргенштерном привело к публикации в 1944 году книги Theory of Games and Economic Behavior (Теория игр и экономического поведения) [1546], которая сыграла решающую роль в создании теории игр. Публикация этой книги задерживалась из-за нехватки бумаги во время войны до тех пор, пока один из членов семейства Рокфеллеров не субсидировал публикацию.
  В 1950 году в возрасте 21 года Джон Нэш опубликовал свои идеи, касающиеся достижения равновесия в играх общего типа [1112]. Его определение равновесного решения получило известность под названием равновесия Нэша (хотя впервые появилось в работе Курно [297]). После длительной задержки из-за шизофрении, которой он страдал с 1959 года, Нэш получил Нобелевскую премию по экономике (наряду с Рейнхартом Селтеном и Джоном Харсаньи) в 1994 году.
  Равновесие Байеса-Нэша описано в [622] и обсуждается в [757]. Некоторые проблемы использования теории игр для управления агентами рассматриваются в [129].
  Дилемма заключенного была разработана для использования в качестве учебного упражнения Альбертом В. Такером в 1950 году и тщательно исследована в [50]. Понятие повторяющихся игр было представлено в [963], а игры с частичной информацией—в [862]. Первый практически применимый алгоритм для игр с частичной информацией был разработан в рамках искусственного интеллекта Коллером идр.[821]; в статье [822] дано удобное для чтения введение в эту общую область и описана действующая система представления и решения последовательных игр. Теория игр и задач MDP объединена в теорию марковских игр [937]. Шепли [1398] фактически описал алгоритм итерации по значениям до Беллмана, но его результаты не получили широкого признания, вероятно, потому, что были представлены в контексте марковских игр. К числу основных учебников по теории игр относятся [510], [1109] и [1161].
  Задача, послужившая стимулом к созданию области проектирования механизма, трагическая деградация общих пастбищ, была представлена в [619]. Гурвич [709] создал математические основы для проектирования механизма. Милгром [1048] описал разработанный им механизм аукциона, который охватывает диапазон сделок в несколько миллиардов долларов. Понятие аукционов может также использоваться в планировании [706] и составлении расписаний [1267]. В [1539] приведен краткий обзор тематики аукционов в связи с публикациями по компьютерным наукам, а в [ 1307] представлено описание способов применения этого подхода для решения распределенных задач искусственного интеллекта, занявшее целую книгу. Родственные работы по проблематике распределенных задач искусственного интеллекта публикуются также под другими названиями, включая коллективный интеллект [1516] и управление на основе рынка [269]. Статьи по вычислительным проблемам, связанным с аукционами, часто публикуются в трудах конференции ACM Conferences on Electronic Commerce.

Принятие сложных решений