Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 226
Текст из файла (страница 226)
Например, функция "деления на два" представляет собой функцию сжатия, поскольку после деления двух чисел на два разница между ними уменьшается наполовину. Обратите внимание на то, что функция чделения на два" имеет фиксированную точку, а именно нуль, которая остается неизменной в результате применения этой функции. На основании данного примера можно установить два важных свойства функций сжатия, описанных ниже. ° Функция сжатия имеет только одну фиксированную точку; если бы были две фиксированные точки, они бы не приближались друг к другу после применения функции, поэтому такая функция не соответствовала бы определению функции сжатия. ° После применения функции к любому параметру полученное значение должно стать ближе к фиксированной точке )поскольку фиксированная точка не 827 Глава 17.
Принятие сложных решений движется), поэтому в пределе повторное применение функции сжатия всегда приводит к достижению фиксированной точки. Теперь предположим, что обновление Беллмана (уравнение 17.6) рассматривается как оператор в, который используется для одновременного обновления значений полезности каждого состояния. Обозначим через с/с вектор полезностей для всех состояний в с-й итерации. В таком случае уравнение обновления Беллмана может быть записано следующим образом: и„, с — вгд Затем нужно найти способ измерения расстояний между векторами полезностей. Мы будем использовать 'т.
нормализованный максимум, который измеряет длину вектора по длине его максимального компонента, следующим образом: ((у) ) = мах ) п(в) ) При использовании этого определения "расстояние" между двумя векторами, ~ ) сс-с/' ) ~, представляет собой максимальную разность между двумя соответствую- шими элементами. Основным математическим результатом данного раздела является такое утверждение: ог допустим, что С)с и с)с ' — два вектора полезноопей. В таком случие получим следующее: ()всс,-всс,'(( < у ) ) пс-сс, ) ( (17.7) Это означает, что обновление Беллмана представляет собой функцию сжатия на коэффициент у, применяемую к пространству векторов полезностей. Таким образом, процедура итерации по значениям всегда сходится к уникальному решению уравнений Беллмана.
В частности, можно заменить значение ссс ' в уравнении 17.7 истинными полезностями с), для которых врь сс В таком случае будет получено следующее неравенство: ) (впс-ц) ( < у ) ) и„-и) ) Поэтому, если ) ) ссс — ст! ! рассматривается как ошибка в оценке сс„, то можно видеть, что эта ошибка уменьшается при каждой итерации на коэффициент, по меньшей мере равный у.
Это означает, что процедура итерации по значениям сходится экспоненциально быстро. Можно легко рассчитать количество итераций, требуемых для достижения заданной предельной ошибки е, как описано ниже. Вначале напомним, что, как показывает уравнение 17.1, полезности всех состояний ограничены значением ч в / (1-у) . Из этого следует, что максимальная начальная ошибка определяется соотношением ~ ~ С/,-Сс~ ~ <2)С / (1-у). Предположим, что для достижения ошибки, не превышающей е, выполнено д) итераций. В таком случае потребуется у" 2)С /(1-у)<е итераций, поскольку ошибка уменьшается каждый раз по меньшей мере на величину у. Взяв логарифмы от этого выражения, можно определить, что достаточно применить следующее количество итераций; Сч = ) 1сд(2Л /Е(1-у) ) /1од(1/у)1 На рис. ! 7.4, б показано, как количество итераций в) изменяется в зависимости от у при различных значениях отношения е/)с .
Положительной особенностью этого соотношения является то, что из-за экспоненциально быстрой сходимости значение 828 Часть У. Неопределенные знания и рассуждения в условиях неопределенности ь) не очень зависит от отношения е!я, „, а отрицательной особенностью — то, что ьг быстро возрастает по мере приближения значения у к 1. Уменьшение значения у позволяет добиться ускорения сходимости, но это фактически приводит к сужению горизонта агента и может не позволить агенту обнаруживать долговременные последствия своих действий.
Анализ предельной ошибки, приведенный выше, позволяет получить определенное представление о том, какие факторы влияют на продолжительность прогона данного алгоритма, но сам подход, основанный на определении предельной ошибки, иногда становится слишком консервативным способом принятия решения о прекрашении итераций. Для последней цели можно использовать предел, связываюший ошибку с размерами обновления Беллмана в каждой конкретной итерации. На основании свойства сжатия (уравнение ! 7.7) можно показать, что если обновление невелико (т.е.
не происходит значительного изменения полезности ни одного состояния), то ошибка также является небольшой по сравнению с истинным значением функции полезности. Точнее, выполняется следуюшее условие: вя ) ) ш, -цН ) <е(1-у) 7у еиеи ) ) ц„~-ст) )<е (17.В) В этом и состоит условие завершения, используемое в алгоритме Уа1цетгегагйоп, который приведен в листинге 17.1. До сих пор мы анализировали ошибку в значении функции полезности, возврагцаемом алгоритмом итерации по значениям. гян Оо для агента фактически гораздо валенсе то, насколько успешно он будет действовать, принимая свои решения на основе динной функции полезности. Предположим, что после з итераций в процедуре итерации по значениям агент получает оценку уз истинной полезности Гг и определяет максимальную ожидаемую полезность стратегии я, на основе прогнозирования на один шаг вперед с использованием значения г)г (как в уравнении 17.4).
Будет ли выбранное в итоге поведение почти столь же хорошим, как и оптимальное поведение? Это — крайне важный вопрос для любого реального агента, и было показано, что ответ на него является положительным. Значение (Г' ( э) — это полезность, достигаемая, если, начиная с состояния я, осушествляется стратегия я„а 'ж убыточность стратегии ) ) о' -и) ) — это самая большая часть полезности, которую агент может потерять, осушествляя стратегию я, вместо оптимальной стратегии п*.
Убыточность стратегии я, связана с ошибкой в значении полезности гг„следующим неравенством: 1)гг,-ц) ) <е ейеп 1 ) оч-о) ) <2еу7 ) 1-у) (17.9) На практике часто происходит так, что стратегия я; становится оптимальной задолго до того, как сходится значение )),. На рис. 17.5 показано, как максимальная ошибка в значении ц, и убыточность стратегии приближаются к нулю по мере осушествления процедуры итерации по значениям для среды 4хЗ со значением у = О.9. Стратегия и, становится оптимальной при 1=4, даже несмотря на то, что максимальная ошибка в значении гг, все ЕШе ОстаетсЯ равнОй О .
46. Теперь подготовлено все необходимое для использования процедуры итерации по значениям на практике. Известно, что процедура итерации по значениям в пределе сходится к правильным значениям полезности; ошибка в оценках полезностей может быть ограничена, даже если процедура итерации по значениям останавливастся после конечного количества итерации; кроме того, может быть ограничена убы- 829 Глава 17. Принятие сложных решений точность стратегии, которая связана с осуществлением соответствующей стратегии с максимальной ожидаемой полезностью.
В качестве заключительного замечания отметим, что все результаты, приведенные в данном разделе, соответствуют такому случаю, когда применяется обесценивание полезностей, а 7<2. Если 7=1 и среда содержит терминальные состояния, то можно вывести аналогичное множество результатов оценки сходимостн и определения предельных значений ошибок, если выполняются некоторые формальные условия. 0,8 о в ОП Об жйф 02 0 0 2 4 6 8 10 !2 34 Колнчесгва выпалненныл итервинй Рис. ! 7.5. Зависимости максимальной ошибки /1цз-П/ / в оценках полезности и убыточности стратегии ( /П~з-П( ! по сравнению с оптимальной стратегией от количества итераций в процедуре итерации по значениям 17.3.
ИТЕРАЦИЯ ПО СТРАТЕГИЯМ В предыдущем разделе было показано, что возможно выработать оптимальную стратегию, даже если оценка функции полезности является неточной. Если очевидно, что одно действие лучше по сравнению со всеми остальными, то нет необходимости точно определять истинные значения величины полезности всех рассматриваемых состояний. Эта идея подсказывает альтернативный метод поиска оптимальных стратегий.
В алгоритме гь итерации по стратегиям чередуются описанные ниже два этапа, начиная с некоторой исходной стратегии я,. ° 'ак Оценка стратегии. На основе стратегии я„вычислить 024=0', полезность каждого состояния, если будет осуществлена стратегия я„. ° 2ь Усовершенствование стратегии. Вычислить новую стратегию я,„с максимальной ожидаемой полезностью, используя прогноз на один шаг и исходя из значения гув (как в уравнении 17.4). Алгоритм завершает свою работу после того, как этап усовершенствования стратегии не приводит к изменению значений полезности. Как известно, в этот момент функция полезности 02, представляет собой фиксированную точку обновления Беллмана, поэтому является решением уравнений Беллмана, а я, должна быть оп- 830 Часть |).
Неопределенные знания и рассуждения в условиях неопределенности тимальной стратегией. Поскольку для каждого конечного пространства состояний количество возможных стратегий является конечным и можно показать, что каждая итерация приводит к определению лучшей стратегии, то алгоритм итерации по стратегиям должен всегда завершать свою работу. Этот алгоритм показан в листинге 17.2.
Листинг 17.2. Алгоритм итерации по стратегиям лля вычисления оптимальной стратегии Счпссвоп Ро11су-1еегае1оп(тг)р) гееигпп стратегия впряги: юс)р, задача ИПР с состояниями Я, моделью перехода Т 1оса1 чагааЬ1еп: У, Ш, векторы полезностей для состояний из Я, первоначально равные нулю я, вектор стратегий, индексированный по состояниям, первоначально сформированный случайным образом гереас (7 < — Ро1[су-еча1пас[оп(я, у, тс)р) ипслапдес)? г — истинное значение гог васЬ состояние з вл Я с)о вг юах ,) т(а,а,а') ()[з'] > ,) т(а,я[я],а') 0[з'1 сьеп а 5 я[з] ь-агдгаах ~ т(а,а,з') (г[з'] а а ппсдапдес(? ь- ложное значение ипе11 ипслалдес)? гееигп я Очевидно, что этап усовершенствования стратегии является несложным, а как реализовать процедуру Ро11су-Еуа1ыадзоп? Оказалось, что осуществление такого подхода намного проше по сравнению с решением стандартных уравнений Беллмана (а именно зто происходит в алгоритме итерации по значениям), поскольку действие, применяемое в каждом состоянии, зафиксировано в соответствии с выбранной стратегией.
Стратегия я, определяет действие я, ( в ), выполняемое в состоянии л на 1-й итерации. Это означает, что можно воспользоваться упрошенной версией уравнения Беллмана (17.5), которая связывает полезность состояния а (соответствуюшую стратегии яг) с полезностями его соседних состояний, следующим образом: ц,(з) = я(з) + у ) Т(з,п,(з),з') У,(з') (17.10) Например, предположим, что я,— зто стратегия, показанная на рис. 17.2,а. В таком случае имеет место я, (1, 1) = [[р, я„(1, 2) =(гр и тд., а упроШенные уравнения Беллмана принимают следующий вид: 0,(1,1) = -0.04 + О.В ГА(1,2) -ь 0.1 Ш(1,1) -ь 0.1 Ш(2,1) У,(1,2) = -0.04 а О.В 01(1,3) + 0.2 У,(1,2) Важно отметить, что эти уравнения — линейные, поскольку оператор "гцах" был удален.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
