Сходимость итерации по значениям
Выше было указано, что процедура итерации по значениям в конечном итоге сходится к уникальному множеству решений уравнений Беллмана. В этом разделе показано, почему это происходит. В ходе этого будут представлены некоторые полезные математические идеи и получены определенные методы оценки ошибки в значении функции полезности, возвращаемом при преждевременном завершении работы алгоритма; это важно, поскольку означает, что количество применяемых итераций алгоритма не обязательно должно стремиться к бесконечности. Изложение в этом разделе является весьма формальным.
Основным понятием, используемым при доказательстве того, что процедура итерации по значениям сходится, является сжатие. Грубо говоря, функция сжатия — это функция от одного параметра, которая после ее последовательного применения к двум различным входным значениям вырабатывает два выходных значения, которые "ближе друг к другу" по меньшей мере на некоторую постоянную величину, чем первоначальные фактические параметры. Например, функция "деления на два" представляет собой функцию сжатия, поскольку после деления двух чисел на два разница между ними уменьшается наполовину. Обратите внимание на то, что функция "деления на два" имеет фиксированную точку, а именно нуль, которая остается неизменной в результате применения этой функции. На основании данного примера можно установить два важных свойства функций сжатия, описанных ниже.
• Функция сжатия имеет только одну фиксированную точку; если бы были две фиксированные точки, они бы не приближались друг к другу после применения функции, поэтому такая функция не соответствовала бы определению функции сжатия.
• После применения функции к любому параметру полученное значение должно стать ближе к фиксированной точке (поскольку фиксированная точка не движется), поэтому в пределе повторное применение функции сжатия всегда приводит к достижению фиксированной точки.
Теперь предположим, что обновление Беллмана (уравнение 17.6) рассматривается как оператор В, который используется для одновременного обновления значений полезности каждого состояния. Обозначим через Ui вектор полезностей для всех состояний в i-й итерации. В таком случае уравнение обновления Беллмана может быть записано следующим образом:
Затем нужно найти способ измерения расстояний между векторами полезностей. Мы будем использовать нормализованный максимум, который измеряет длину вектора по длине его максимального компонента, следующим образом:
При использовании этого определения "расстояние" между двумя векторами, | | [/-[/* | |, представляет собой максимальную разность между двумя соответствующими элементами. Основным математическим результатом данного раздела является такое утверждение: допустим, что Ui и Ui1 — два вектора полезностей. В таком случае получим следующее:
Это означает, что обновление Беллмана представляет собой функцию сжатия на коэффициент у, применяемую к пространству векторов полезностей. Таким образом, процедура итерации по значениям всегда сходится к уникальному решению уравнений Беллмана.
В частности, можно заменить значение Ui' в уравнении 17.7 истинными полезностя-ми и, для которых ви=и. В таком случае будет получено следующее неравенство:
Поэтому, если | | Ui-U\ | рассматривается как ошибка в оценке [7Ь то можно видеть, что эта ошибка уменьшается при каждой итерации на коэффициент, по меньшей мере равный у. Это означает, что процедура итерации по значениям сходится экспоненциально быстро. Можно легко рассчитать количество итераций, требуемых для достижения заданной предельной ошибки 8, как описано ниже. Вначале напомним, что, как показывает уравнение 17.1, полезности всех состояний ограничены значением ±Rmayi/ (1-у) • Из этого следует, что максимальная начальная ошибка определяется соотношением | | U0-U\ | <2R/ (1-у). Предположим, что для достижения ошибки, не превышающей 8, выполнено N итераций. В таком случае потребуется У*'2Ятах/ (1-у) ? итераций, поскольку ошибка уменьшается каждый раз по меньшей мере на величину у. Взяв логарифмы от этого выражения, можно определить, что достаточно применить следующее количество итераций:
N= riog(2JWe(l-Y) )/1од(1/у)1
На рис. 17.4, б показано, как количество итераций N изменяется в зависимости от Y при различных значениях отношения Положительной особенностью этого
соотношения является то, что из-за экспоненциально быстрой сходимости значение
iVHe очень зависит от отношения е/Ятах, а отрицательной особенностью — то, что N быстро возрастает по мере приближения значения у к 1. Уменьшение значения у позволяет добиться ускорения сходимости, но это фактически приводит к сужению горизонта агента и может не позволить агенту обнаруживать долговременные последствия своих действий.
Анализ предельной ошибки, приведенный выше, позволяет получить определенное представление о том, какие факторы влияют на продолжительность прогона данного алгоритма, но сам подход, основанный на определении предельной ошибки, иногда становится слишком консервативным способом принятия решения о прекращении итераций. Для последней цели можно использовать предел, связывающий ошибку с размерами обновления Беллмана в каждой конкретной итерации. На основании свойства сжатия (уравнение 17.7) можно показать, что если обновление невелико (т.е. не происходит значительного изменения полезности ни одного состояния), то ошибка также является небольшой по сравнению с истинным значением функции полезности. Точнее, выполняется следующее условие:
if | | Ui+1-Ui\ |<е(1-у) /у then | | Ui+1-u\ |<е (17.8)
В этом и состоит условие завершения, используемое в алгоритме Value-Iteration, который приведен в листинге 17.1.
До сих пор мы анализировали ошибку в значении функции полезности, возвращаемом алгоритмом итерации по значениям. Но для агента фактически гораздо важнее то, насколько успешно он будет действовать, принимая свои решения на основе данной функции полезности. Предположим, что после i итераций в процедуре итерации по значениям агент получает оценку Ui истинной полезности и и определяет максимальную ожидаемую полезность стратегии тг± на основе прогнозирования на один шаг вперед с использованием значения Ui (как в уравнении 17.4). Будет ли выбранное в итоге поведение почти столь же хорошим, как и оптимальное поведение? Это — крайне важный вопрос для любого реального агента, и было показано, что ответ на него является положительным. Значение lfi(s) — это полезность, достигаемая, если, начиная с состояния s, осуществляется стратегия 7ii? а убыточность стратегии | | lfi-u\ | — это самая большая часть полезности, которую агент может потерять, осуществляя стратегию тг± вместо оптимальной стратегии я*. Убыточность стратегии щ связана с ошибкой в значении полезности Ui следующим неравенством:
if | | Ui-U\ |<е then | | ifi-и\ | <2еу/ (1-у) (17.9)
На практике часто происходит так, что стратегия 7Г± становится оптимальной задолго до того, как сходится значение Ui. На рис. 17.5 показано, как максимальная ошибка в значении UL и убыточность стратегии приближаются к нулю по мере осуществления процедуры итерации по значениям для среды 4x3 со значением у = 0 . 9. Стратегия 7Г± становится оптимальной при i=4, даже несмотря на то, что максимальная ошибка в значении Ui все еще остается равной 0.46.
Теперь подготовлено все необходимое для использования процедуры итерации по значениям на практике. Известно, что процедура итерации по значениям в пределе сходится к правильным значениям полезности; ошибка в оценках полезностей может быть ограничена, даже если процедура итерации по значениям останавливается после конечного количества итераций; кроме того, может быть ограничена убыточность стратегии, которая связана с осуществлением соответствующей стратегии с максимальной ожидаемой полезностью. В качестве заключительного замечания отметим, что все результаты, приведенные в данном разделе, соответствуют такому случаю, когда применяется обесценивание полезностей, а у<1. Если у=1 и среда содержит терминальные состояния, то можно вывести аналогичное множество результатов оценки сходимости и определения предельных значений ошибок, если выполняются некоторые формальные условия.
В предыдущем разделе было показано, что возможно выработать оптимальную стратегию, даже если оценка функции полезности является неточной. Если очевидно, что одно действие лучше по сравнению со всеми остальными, то нет необходимости точно определять истинные значения величины полезности всех рассматриваемых состояний. Эта идея подсказывает альтернативный метод поиска оптимальных стратегий. В алгоритме итерации по стратегиям чередуются описанные ниже два этапа, начиная с некоторой исходной стратегии п0.
• Оценка стратегии. На основе стратегии 7Г± вычислить L7i=[/ti, полезность каждого состояния, если будет осуществлена стратегия 7Г±.
• Усовершенствование стратегии. Вычислить новую стратегию ni+1 с максимальной ожидаемой полезностью, используя прогноз на один шаг и исходя из значения Ui (как в уравнении 17.4).
Алгоритм завершает свою работу после того, как этап усовершенствования стратегии не приводит к изменению значений полезности. Как известно, в этот момент функция полезности и± представляет собой фиксированную точку обновления Беллмана, поэтому является решением уравнений Беллмана, а тг± должна быть оп-