Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 235
Текст из файла (страница 235)
Рассмотрите задачу МОР без обесценивания, имеющую три состояния, [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,9. Дайте ответы на приведенные ниже вопросы. а) Какие характеристики оптимальной стратегии в состояниях 1 и 2 могут быть определены качественно? б) Примените алгоритм итерации по стратегиям для определения оптимальной стратегии и значений состояний 1 и 2, полностью демонстрируя каждый этап. Примите предположение, что исходная стратегия включает действие ]з в обоих состояниях.
в) Как повлияет на работу алгоритма итерации по стратегиям включение в исходная стратегия действия а в обоих состояниях? Поможет ли применение обесценивания? Зависит ли оптимальная стратегия от коэффициента обесценивания? 860 Часть Ч. Неопределенные знания и рассуждения в условиях неопределенности 17.5. Иногда задачи МОР формулируются на основе функции вознаграждения П( з, а), которая зависит от выполненного действия, или функции вознаграждения и( э, а, в ' ), которая зависит также от результирующего состояния. а) Запишите уравнения Беллмана для этих формулировок. б) Покажите, как можно преобразовать задачу МОР с функцией вознаграждения к(з,а,э') в другую задачу МОР с функцией вознаграждения п(э, а), такую, что оптимальные стратегии в новой задаче МОР будут точно соответствовать оптимальным стратегиям в первоначальной задаче МРР.
в) Выполните аналогичные действия для преобразования задачи МОР с функцией п(в, а) в задачу МОР с функцией п(э) . 17.6. й) Рассмотрим мир Ахз, показанный на рис. 17.1. а) Реализуйте имитатор для этой среды, такой, чтобы можно было легко изменять географию данной среды.
Некоторый код для решения указанной задачи уже нахолится в оперативном репозитарии кода. б) Создайте агента, в котором используется итерация по стратегиям, и измерьте его производительность в имитаторе среды, начиная с различных начальных состояний. Выполните несколько экспериментов из каждого начального состояния и сравните среднее суммарное вознаграждение, полученное за каждый прогон, с полезностью состояния, которая определяется применяемым вами алгоритмом. в) Проведите эксперименты в среде с увеличенными размерами. Как изменяется время прогона алгоритма итерации по стратегиям в зависимости от размеров этой среды? 17.7. Й)Для среды, показанной на рис.!7.1, найдите все пороговые значения функции полезности и ( э), такие, что после пересечения этого порога изменяется оптимальная стратегия. Вам потребуется способ вычисления оптимальной стратегии и его значения для фиксированной функции п(э).
(Подсказка, Докажите, что значение любой фиксированной стратегии линейно зависит от функции П ( в) .) 17.8. В этом упражнении рассматриваются задачи МОР с двумя игроками, которые соответствуют играм с нулевой суммой и поочередными ходами, подобным описанным в главе 6. Допустим, что игроки обозначены как А и д, и предположим, что п( э) — вознаграждение для игрока А в состоянии в. (Вознаграждение для игрока в всегда равно ему и противоположно.) а) Допустим, что У, ( э) — полезность состояния в, когда очередь хода в состоянии э принадлежит игроку А; (г, ( э) — полезность состояния э, когда очередь хода в состоянии з принадлежит игроку В. Все вознаграждения и полезности вычисляются с точки зрения игрока А (как и в мннимаксном дереве игры).
Запишите уравнения Беллмана, определяющие гк ( э) и (г, ( з) . б) Объясните, как осуществить итерацию по значениям для двух игроков с помощью этих уравнений, и определите подходящий критерий останова. в) Рассмотрите игру, приведенную на рис. 6.12. Изобразите пространство состояний (а не дерево игры), показывая ходы игрока А сплошными ли- 861 Глава !7. Принятие сложных решений Таблица 17.4.
Матрица вознаграждений в административной игре Рей: сузить Рей: ничего не делать Реб: расширить Р=7, Р=1 Р=9,Р=4 Р=5,Р=5 Р=2,Р=7 Р=б,р=б Р=4,Р=9 Р=1,Р=8 Ро!: сузить Ро1: ничего не делать Р=8, Р=2 Р=3, Р=3 Ро1: расширить Конгрессмены могут расширять или сужать налоговую политику, а руководители Федеральной резервной системы могут расширять или сужать бюджетную политику (и, безусловно, та и иная сторона может выбрать вариант, в котором не предусматривается внесение каких-либо изменений.) Кроме того, каждая из этих сторон имеет определенные предпочтения в отношении того, пнями, а ходы игрока в — штриховыми линиями. Обозначьте каждое состояние значением л(э). Вы обнаружите, что удобно расположить состояния (э„эв) в виде двухмерной решетки, используя в качестве "координат" значения э„и э,. г) Теперь примените итерацию по значениям для двух игроков, чтоббг найти решение этой игры, и определите оптимальную стратегию.
17.9. Покажите, что любое равновесие доминантной стратегии представляет собой равновесие Нэша, но обратное утверждение не верно. 17.10. В детской игре в камень, бумагу и ножницы кахсдый игрок в какое-то время пытается выяснить, кто выбрал камень, бумагу или ножницы. Бумага обертывает камень, камень тупит ножницы, а ножницы режут бумагу.
В расширенной версии игры в камень, бумагу, ножницы, огонь и воду приняты следующие условия: огонь побеждает камень, бумагу и ножницы; камень, бумага и ножницы побеждают воду; вода побеждает огонь. Запишите матрицу вознаграждений и найдите решение со смензанной стратегией для этой игры. 17.11. Найдите решение для игры в чет и нечет на трех пальцах. 17.12.До !999 года команды Национальной хоккейной лиги получали 2 очка за победу, ! за ничью и О за поражение. Можно ли рассматривать хоккей с такими правилами как игру с постоянной суммой? В 1999 голу правила были изменены таким образом, что команда получает 1 очко за проигрыш в дополнительное время.
Победившая команда все еще получает 2 очка. Изменится ли с учетом этого дополнения ответ на вопрос, приведенный выше? Если бы за это не было наказания, то было бы рациональным для двух команд втайне договариваться, чтобы оканчивать отборочную игру ничьей, а затем доводить ее до результативного завершения в дополнительное время? Предполагается, что полезность для каждой команды измеряется количеством полученных ею очков и что обоюлно известна априорная вероятность р того, что первая команда победит в дополнительное время. При каких значениях р обеим командам слеловало бы заключать такое соглашение? 17.13. Приведенная в табл.
17.4 матрица вознаграждений, впервые опубликованная Блиндером ]!37] и проанализированная Бернштейном (! )4], показывает, какую игру велут между собой конгрессмены — политики (сокращенно Ро!) и руководство Фелеральной резервной системы (сокращенно Рог)). 862 Часть Ч. Неопределенные знания и рассуждения в условиях неопределенности кто и что должен делать, поскольку ни те ни другие не хотят вызвать недовольство населения.
Показанные выше вознаграждения представляют собой ранги упорядочения от 9 до 1, т.е. от первого варианта до последнего. Найдите равновесие Нэша для этой игры в рамках чистых стратегий. Является ли это решение оптимальным согласно критерию Парето? Рекомендуем читателю проанализировать в свете этих исследований политику администраций США последних созывов. Часть М ОБУЧЕНИЕ Обучение на основе наблюдений Применение знаний в обучении Статистические методы обучения Обучение с подкреплением 864 902 945 10~0 В данной главе рассматриваются агенты, способные усовергаенствовать свое поведение благодаря тщательному изучению собственного опыта.
В основе обучения лежит представление о том, что результаты восприятия должны использоваться не только для осуществления действий, но и лля повышения способности агента действовать в будущем. Обучение происходит по мере того, как агент наблюдает за своим взаимодействием с миром и собственными процессами принятия решений. Обучение может охватывать широкий спектр действий, начиная от тривиального накопления в памяти результатов полученного опыта, как было показано на примере агента для мира вампуса в главе 10, и заканчивая созданием целых научных теорий, что было успешно продемонстрировано Альбертом Эйнштейном. В этой главе рассматривается индуктивное обучение на основе наблюдений.
В частности, в ней описано, как в процессе обучения формируются простые теории в терминах пропозициональной логики. В ней также приведены результаты теоретического анализа, позволяющие понять принципы индуктивного обучения. 18.1. ФОРМЫ ОВуЧЕНИя В главе 2 было показано, что проект обучаюгдегося агента может рассматриваться как состоящий из производительного элемента, определяющего, какие действия лолжны быть выполнены, и обучающего элемента, который модифицирует производительный элемент для того, чтобы он вырабатывал лучшие решения (см. рис.
2.7). Исследователи, работаюцгие в области машинного обучения, предложили целый ряд типов обучающих элементов. Для того чтобы разобраться в их работе, целесообразно рассмотреть, как влияет на их проект тот контекст, в котором они должны функционировать. На проект обучающего элемента влияют три описанных ниже аспекта. Глава 18. Обучение на основе наблюдений 865 ° Компоненты производительного элемента, подлежащие обучению. ° Обратные связи, которые могут применяться для обучения этих компонентов. ° Способы представления, используемые для компонентов.
Проведем анализ каждого из этих аспектов по очереди. В данной книге уже было показано, что существует много способов построения производительного элемента для агента. В главе 2 было описано несколько проектов агентов (см. рис. 2.3 — 2.6). Ниже перечислены компоненты этих агентов. 1. Срелства прямого отображения условий (распространяющихся на текущее состояние) в действия.
2. Средства логического вывода релевантных свойств мира из последовательности результатов восприятия. 3. Информация о том, как развивается мир и какие результаты возможных действий могут быть получены агентом. 4. Информация о полезности, которая показывает, насколько желательными являются те или иные состояния мира. 5. Информация о ценности действий, показывающая желательность действий. 6. Цели, описывающие классы состояний, достижение которых максимизирует полезность для агента.
Обучение каждого из этих компонентов может осуществляться с помощью соответствующей обратной связи. Рассмотрим, например, агента, который учится вожлению, чтобы стать таксистом. Каждый раз, когда инструктор кричит "Тормози!", агент лолжен усвоить очередное правило "условие — действие'*, позволяющее определить, когда следует тормозить (компонент 1). Рассматривая множество видеоизображений, на которых, как ему сказано, имеются автобусы, он может научиться распознавать автобусы (компонент 2).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
