На рис. 17.4, б показано, как количество итераций N изменяется в зависимости от γ при различных значениях отношения. Положительной особенностью этого соотношения является то, что из-за экспоненциально быстрой сходимости значение N не очень зависит от отношения , а отрицательной особенностью — то, что N быстро возрастает по мере приближения значения γ к 1. Уменьшение значения γ позволяет добиться ускорения сходимости, но это фактически приводит к сужению горизонта агента и может не позволить агенту обнаруживать долговременные последствия своих действий.

Анализ предельной ошибки, приведенный выше, позволяет получить определенное представление о том, какие факторы влияют на продолжительность прогона данного алгоритма, но сам подход, основанный на определении предельной ошибки, иногда становится слишком консервативным способом принятия решения о прекращении итераций. Для последней цели можно использовать предел, связывающий ошибку с размерами обновления Беллмана в каждой конкретной итерации. На основании свойства сжатия (уравнение 17.7) можно показать, что если обновление невелико (т.е. не происходит значительного изменения полезности ни одного состояния), то ошибка также является небольшой по сравнению с истинным значением функции полезности. Точнее, выполняется следующее условие:

(17.8)

В этом и состоит условие завершения, используемое в алгоритме Value-Iteration, который приведен в листинге 17.1.

До сих пор мы анализировали ошибку в значении функции полезности, возвращаемом алгоритмом итерации по значениям. Но для агента фактически гораздо важнее то, насколько успешно он будет действовать, принимая свои решения на основе данной функции полезности. Предположим, что после i итераций в процедуре итерации по значениям агент получает оценкуистинной полезности U и определяет максимальную ожидаемую полезность стратегиина основе прогнозирования на один шаг вперед с использованием значения(как в уравнении 17.4). Будет ли выбранное в итоге поведение почти столь же хорошим, как и оптимальное поведение? Это — крайне важный вопрос для любого реального агента, и было показано, что ответ на него является положительным. Значение— это полезность, достигаемая, если, начиная с состояния s, осуществляется стратегия, а убыточность стратегии— это самая большая часть полезности, которую агент может потерять, осуществляя стратегиювместо оптимальной стратегии π*. Убыточность стратегиисвязана с ошибкой в значении полезностиследующим неравенством:

(17.9)