Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 225
Текст из файла (страница 225)
Заключительный этап состоит в том, чтобы показать, как осуществляется выбор между стратегиями с учетом того, что каждая конкретная стратегия и вырабатывает не только одну последовательность состояний, но целый ряд возможных последовательностей состояний, притом что каждая из этих последовательностей имеет конкретную вероятность, определяемую моделью перехода для данной среды. Таким образом, стоимость любой стратегии представляет собой ожидаемую сумму полученных обесцениваемых вознаграждений, где это ожидаемое значение вычисляется по всем возможным последовательностям состояний, которые могут возникнуть при осуществлении данной стратегии. Любая оптимальная стратегия и* удовлетворяет следующему соотношению: и* = агапах е ~~) у Л(в,) ( и и е=о (17.2) В следующих двух разделах описаны алгоритмы поиска оптимальных стратегий.
17.2. ИТЕРАЦИЯ ПО ЗНАЧЕНИЯМ В этом разделе представлен алгоритм вычисления оптимальной стратегии, называемый Ъ. итерацией по значениям. Основная его идея состоит в том, что нужно рассчитать полезность каждого состояния, а затем использовать полезности состояний для выбора оптимального действия в каждом состоянии. 823 Глава 17. Принятие сложных решений Полезности состояний Полезность состояний определяется в терминах полезности последовательностей состояний. Грубо говоря, полезность любого состояния представляет собой ожидаемую полезность последовательностей состояний, которые могут привести к этому состоянию. Очевидно, что перечень таких последовательностей состояний зависит от осуществляемой стратегии, поэтому начнем с определения полезности У'(з) по отношению к конкретной стратегии я. Если мы предположим, что э, — это состояние, в котором находится агент после осуществления стратегии я в течение С шагов (обратите внимание на то, что э, — случайная переменная), то получим следующее: (17.3) (р(я) = е На основании этого определения можно утверждать, что истинная полезность любого состояния, которую обозначим как ()(э), представляет собой (Р*(з), т.е.
ожидаемую сумму обесцениваемых вознаграждений, при условии, что агент осуществляет оптимальную стратегию. Обратите внимание на то, что П(э) и )((э) — совершенно разные величины; )1(э) — это "кратковременное" вознаграждение за пребывание в состоянии э; П(в) — "долговременное" суммарное вознаграждение, которое начинается с состояния э и продолжается дальше. На рис. 17.3 показаны рассматриваемые значения полезности для мира йхЗ.
Заслуживает внимание то, что значения полезности по мере приближения состояний к выходу е' становятся выше, поскольку уменьшается количество шагов, требуемых для достижения этого выхода. 3 4 1 2 Рис. 173. Полезности состояний в мире лхз, рассчитанные яри уят и а (а) = -(). ()4 для не- терминальных состояний Эта функция полезности (7( э) позволяет агенту выбирать действия с использованием принципа максимальной ожидаемой полезности, приведенного в главе 16, т.е. выбирать действие, которое максимизирует ожидаемую полезность в следующем состоянии; 824 Часть Ч. Неопределенные знания и рассуждения в условиях неопределенности п*(а) = асятпах ,) т(з,а,я') 0(в') (17.4) Итак, если полезность некоторого состояния представляет собой ожидаемую сумму обесцениваемых вознаграждений, начиная с данного момента и дальше, то существует прямая связь между полезностью состояния и полезностью его соседних состояний: сзг полезность некоторого состояния равна сумме непосредственного вознаграждения за пребывание в этом состоянии и ожидаемой обесцениваемой полезности следующего состояния, при условии, что агеюп выбирает оптимальное действие.
Это означает, что полезность любого состояния можно определить с помо(цью следующего соотношения: П(з) = я(э) ч у п1ах ,) т(я,а, я') П(я') (17.5) а я Уравнение 17.5 называется 'в. уравнением Беллмана в честь Ричарда Беллмана [97]. Полезности состояний (определяемые с помощью уравнения 17.3 как ожидаемые полезности дальнейших последовательностей состояний) являются решениями множества уравнений Беллмана. В действительности, как будет показано в следующих двух разделах, они являются уникальными решениями. Рассмотрим одно из уравнений Беллмана для мира 4хЗ. Уравнение для состояния ( 1, 1 ) приведено ниже. 0(1, 1) = -0.04 -> у пьзх (0.8 щ1,2) я О.). Щ2, 1) + О. 1 0(1, 1), (Ор) 0.9 П(1,1) + 0.1 П(1,2), (Ъасс) О.Э П(1, 1) -> О.
1 П(2, 1), (поп п) 0 8 Ц(2,1) ч 0 1 П(1,2) я 0.1 Я1,1)1 (Яйдпе) После подстановки в это уравнение чисел, приведенных на рис. 17.3, можно обнаружить, что наилучшим действием является ((р. Алгоритм итерации по значениям Уравнение Беллмана является основой алгоритма итерации по значениям, применяемого для решения задач МОР. Если существует и возможных состояний, то количество уравнений Беллмана также равно и, по одному для каждого состояния. Эти и уравнений содержат п неизвестных — полезностей состояний. Поэтому можно было бы заняться поиском решений системы этих уравнений, чтобы определить полезности.
Тем не менее возникает одна проблема, связанная с тем, что эти уравнения являются нелинейными, поскольку оператор "гпах" — это нелинейный оператор. Системы линейных уравнений могут быть решены очень быстро с использованием методов линейной алгебры, а для решения систем нелинейных уравнений необходимо преодолеть некоторые проблемы.
Один из возможных подходов состоит в использовании итерационных методов. Для этого нужно начать с произвольных исходных значений полезностей, вычислить правую часть уравнения и подставить ее в левую, тем самым обновляя значение полезности каждого состояния с учетом полезностей его соседних состояний. Такая операция повторяется до тех пор, пока не достигается равновесие. Допустим, что ()з(а) — это значение полезности для со- 825 Глава 17.
Принятие сложных решений стояния з в 4-и итерации. Шаг итерации, называемый оа обновлением Беллмана, выглядит следующим образом: П„ь(я) < — Я(з) -ь у шах ,) Т(з, а, з') П,(з') а з, (17.6) Листинг 17.1. Алгоритм итерации но значениям дня вычисления полезностей состояний. Условие завершения работы взято из уравнения 17.8 гипсе1оп ча1це-тсегасьоп(шс(р, е) геепгпя функция полезности апрцсв: шс)р, задача ИПР с состояниями о, моделью перехода Т, функцией вознаграждения Я, коэффициентом обесценивания у Е, максимально допустимая ошибка определения полезности любого состояния 1оса1 чагааЬ1ея: П, П', векторы полезностей для состояний из Я, первоначально равные нулю 8, максимальное изменение полезности любого состояния во время итерации гереае и ь- и'; б ь- о гог еасЬ состояние я 1п Я ао щ [я] ь- Л[з] + у шах ,) т(з, а, я') ц[я'! а 1г ! сг [я] — ц[з] [>8 еьеп 6 +- ! щ [я! -п[з] ! ипс41 8 < е(1-У)!У гееигп и Мы можем применить алгоритм итерации по значениям к миру 4х3 (см.
рис, 17.1, а). Начиная с исходных значений, равных нулю, полезности изменяются, как показано на рис. 17.4, а. Обратите внимание на то, как состояния, находящиеся на различных расстояниях от квадрата (4, 3 ), накапливают отрицательное вознаграждение до тех пор, пока в какой-то момент не обнаруживается путь к состоянию (4, 3), после чего значения полезности начинают возрастать.
Алгоритм итерации по значениям может рассматриваться как способ распространения информации через пространство состояний с помощью локальных обновлений. Если обновление Беллмана используется неопределенно большое количество раз, то гарантируется достижение равновесия (см. следующий подраздел), и в этом случае конечные значения полезности должны представлять собой решения уравнений Беллмана. В действительности они также представляют собой уникальные решения, и соответствующая стратегия (полученная с помощью уравнения 17,4) является оптимальной.
Применяемый при этом алгоритм, называемый Уа1це1сегасйоп, показан в листинге 17.1. 826 Часть 'тт. Неопределенные знания и рассуждения в условиях неопределенности 1сь07 Й !сьоб й )ООООО с й !оооо ЮОО 8 юо )О о,з о 06 И ОЛ Я О,2 о о 1 0,5 0,55 0,6 0,65 0,7 0,75 О,В О,В5 0,9 0,95 1 Коэффициснтобссцсниваният б) 5 10 !5 20 25 30 Количество выцолнснныл итераций а) Рис. 7 7.4. Пример применения алгоритма итерации по значениям: график, показывающий изменение полезностеи выбранных состояний в процессе итериции по значениям (а); количество итераций по значениям Х, необходимое для того, чтобы можно было гарантировать, что ошибка не превышает е=с в, для различных значений с, как функция от коэффициента обесценивания убб) Сходимость итерации по значениям Выше было указано, что процедура итерации по значениям в конечном итоге сходится к уникальному множеству решений уравнений Беллмана.
В этом разделе показано, почему это происходит. В ходе этого будут представлены некоторые полезные математические идеи и получены определенные методы оценки ошибки в значении функции полезности, возвраШаемом при преждевременном завершении работы алгоритма; это важно, поскольку означает, что количество применяемых итераций алгоритма не обязательно должно стремиться к бесконечности. Изложение в этом разделе является весьма формальным.
Основным понятием, используемым при доказательстве того, что процедура итерации по значениям сходится, является Ъ, сжатие. Грубо говоря, функция сжатия— это функция от одного параметра, которая после ее последовательного применения к двум различным входным значениям вырабатывает два выходных значения, которые "ближе друг к другу" по меньшей мере на некоторую постоянную величину, чем первоначальные фактические параметры.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
