БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕТКИ
Основателем современного подхода к анализу задач последовательного принятия решений был Ричард Беллман [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.
УПРАЖНЕНИЯ
17.1. Для мира 4x3 (см. рис. 17.1) рассчитайте, какие квадраты могут быть достигнуты из квадрата (1,1) с помощью последовательности действий [Up, Up,Right, Right, Right] и с какими вероятностями. Объясните, как эти вычисления связаны с задачей проектирования скрытой марковской модели.
17.2. Предположим, что в качестве полезности последовательности состояний определено максимальное вознаграждение, полученное в любом из состояний этой последовательности. Покажите, что данная функция полезности не приводит к формированию стационарных предпочтений между последовательностями состояний. Остается ли возможным определение на состояниях такой функции полезности, что принятие решений на основе полезности MEU позволит сформировать оптимальное поведение?
17.3. Может ли любая задача конечного поиска быть точно преобразована в марковскую задачу принятия решений, такую, что оптимальное решение последней является также оптимальным решением первой? Если да, то объясните, как преобразовать эту задачу и как выполнить обратное преобразование решения, а если нет, объясните, почему ваш ответ отрицателен (в частности, приведите контрпример).
17.4. Рассмотрите задачу MDP без обесценивания, имеющую три состояния, (1, 2 , 3 ), с вознаграждениями -1, -2, 0 соответственно. Состояние 3 является терминальным. В состояниях 1 и 2 имеются два возможных действия, а и Ь. Модель перехода описана ниже.
• В состоянии 1 действие а переводит агента в состояние 2 с вероятностью 0,8 и оставляет агента в том же состоянии с вероятностью 0,2.
• В состоянии 2 действие а переводит агента в состояние 1 с вероятностью 0,8 и оставляет агента в том же состоянии с вероятностью 0,2.
• Либо в состоянии 1, либо в состоянии 2 действие Ъ переводит агента в состояние 3 с вероятностью 0,1 и оставляет агента в том же состоянии с вероятностью 0,9.
Дайте ответы на приведенные ниже вопросы.
а) Какие характеристики оптимальной стратегии в состояниях 1 и 2 могут
быть определены качественно?
б) Примените алгоритм итерации по стратегиям для определения опти-
мальной стратегии и значений состояний 1 и 2, полностью демонстрируя
каждый этап. Примите предположение, что исходная стратегия включает
действие Ь в обоих состояниях.
в) Как повлияет на работу алгоритма итерации по стратегиям включение в
исходная стратегия действия а в обоих состояниях? Поможет ли приме-
нение обесценивания? Зависит ли оптимальная стратегия от коэффици-
ента обесценивания?
17.5. Иногда задачи MDP формулируются на основе функции вознаграждения R(s, а), которая зависит от выполненного действия, или функции вознаграждения R( s, а, s1 ), которая зависит также от результирующего состояния.
а) Запишите уравнения Беллмана для этих формулировок.
б) Покажите, как можно преобразовать задачу MDP с функцией вознаграж-
дения R(s,a, s' ) в другую задачу MDP с функцией вознаграждения
R(s,a), такую, что оптимальные стратегии в новой задаче MDP будут
точно соответствовать оптимальным стратегиям в первоначальной задаче
MDP.
в) Выполните аналогичные действия для преобразования задачи MDP
с функцией R(s, а) в задачу MDP с функцией R(s).
17.6. w Рассмотрим мир 4x3, показанный на рис. 17.1.
а) Реализуйте имитатор для этой среды, такой, чтобы можно было легко из-
менять географию данной среды. Некоторый код для решения указанной
задачи уже находится в оперативном репозитарии кода.
б) Создайте агента, в котором используется итерация по стратегиям, и из-
мерьте его производительность в имитаторе среды, начиная с различных
начальных состояний. Выполните несколько экспериментов из каждого
начального состояния и сравните среднее суммарное вознаграждение,
полученное за каждый прогон, с полезностью состояния, которая опре-
деляется применяемым вами алгоритмом.
в) Проведите эксперименты в среде с увеличенными размерами. Как изме-
няется время прогона алгоритма итерации по стратегиям в зависимости
от размеров этой среды?
17.7. (И)Для среды, показанной на рис. 17.1, найдите все пороговые значения функции полезности R(s), такие, что после пересечения этого порога изменяется оптимальная стратегия. Вам потребуется способ вычисления оптимальной стратегии и его значения для фиксированной функции R(s). (Подсказка. Докажите, что значение любой фиксированной стратегии линейно зависит от функции R{ s).)
17.8. В этом упражнении рассматриваются задачи MDP с двумя игроками, которые соответствуют играм с нулевой суммой и поочередными ходами, подобным описанным в главе 6. Допустим, что игроки обозначены как А и В, и предположим, что R (s) — вознаграждение для игрока А в состоянии s. (Вознаграждение для игрока в всегда равно ему и противоположно.)
а) Допустим, что UA (s) — полезность состояния s, когда очередь хода в состоя-
нии s принадлежит игроку A; UB{s) — полезность состояния s, когда очередь
хода в состоянии s принадлежит игроку в. Все вознаграждения и полезности
вычисляются с точки зрения игрока А (как и в минимаксном дереве игры).
Запишите уравнения Беллмана, определяющие UA{s) nUB{s).
б) Объясните, как осуществить итерацию по значениям для двух игроков с
помощью этих уравнений, и определите подходящий критерий останова.
в) Рассмотрите игру, приведенную на рис. 6.12. Изобразите пространство
состояний (а не дерево игры), показывая ходы игрока А сплошными ли-
ниями, а ходы игрока в — штриховыми линиями. Обозначьте каждое состояние значением R(s). Вы обнаружите, что удобно расположить состояния (sA/sB) в виде двухмерной решетки, используя в качестве "координат" значения sA и sB. г) Теперь примените итерацию по значениям для двух игроков, чтоб# найти решение этой игры, и определите оптимальную стратегию.
17.9. Покажите, что любое равновесие доминантной стратегии представляет собой равновесие Нэша, но обратное утверждение не верно.
17.10. В детской игре в камень, бумагу и ножницы каждый игрок в какое-то время пытается выяснить, кто выбрал камень, бумагу или ножницы. Бумага обертывает камень, камень тупит ножницы, а ножницы режут бумагу. В расширенной версии игры в камень, бумагу, ножницы, огонь и воду приняты следующие условия: огонь побеждает камень, бумагу и ножницы; камень, бумага и ножницы побеждают воду; вода побеждает огонь. Запишите матрицу вознаграждений и найдите решение со смешанной стратегией для этой игры.
17.11. Найдите решение для игры в чет и нечет на трех пальцах.
17.12. До 1999 года команды Национальной хоккейной лиги получали 2 очка за победу, 1 за ничью и 0 за поражение. Можно ли рассматривать хоккей с такими правилами как игру с постоянной суммой? В 1999 году правила были изменены таким образом, что команда получает 1 очко за проигрыш в дополнительное время. Победившая команда все еще получает 2 очка. Изменится ли с учетом этого дополнения ответ на вопрос, приведенный выше? Если бы за это не было наказания, то было бы рациональным для двух команд втайне договариваться, чтобы оканчивать отборочную игру ничьей, а затем доводить ее до результативного завершения в дополнительное время? Предполагается, что полезность для каждой команды измеряется количеством полученных ею очков и что обоюдно известна априорная вероятность р того, что первая команда победит в дополнительное время. При каких значениях р обеим командам следовало бы заключать такое соглашение?
17.13. Приведенная в табл. 17.4 матрица вознаграждений, впервые опубликованная Блиндером [137] и проанализированная Бернштейном [114], показывает, какую игру ведут между собой конгрессмены-политики (сокращенно Pol) и руководство Федеральной резервной системы (сокращенно Fed).
Конгрессмены могут расширять или сужать налоговую политику, а руководители Федеральной резервной системы могут расширять или сужать бюджетную политику (и, безусловно, та и иная сторона может выбрать вариант, в котором не предусматривается внесение каких-либо изменений.) Кроме того, каждая из этих сторон имеет определенные предпочтения в отношении того,
кто и что должен делать, поскольку ни те ни другие не хотят вызвать недовольство населения. Показанные выше вознаграждения представляют собой ранги упорядочения от 9 до 1, т.е. от первого варианта до последнего. Найдите равновесие Нэша для этой игры в рамках чистых стратегий. Является ли это решение оптимальным согласно критерию Парето? Рекомендуем читателю проанализировать в свете этих исследований политику администраций США последних созывов.