Алгоритм итерации по значениям
Уравнение Беллмана является основой алгоритма итерации по значениям, применяемого для решения задач MDP. Если существует п возможных состояний, то количество уравнений Беллмана также равно п, по одному для каждого состояния. Эти п уравнений содержат п неизвестных — полезностей состояний. Поэтому можно было бы заняться поиском решений системы этих уравнений, чтобы определить полезности. Тем не менее возникает одна проблема, связанная с тем, что эти уравнения являются нелинейными, поскольку оператор "max" — это нелинейный оператор. Системы линейных уравнений могут быть решены очень быстро с использованием методов линейной алгебры, а для решения систем нелинейных уравнений необходимо преодолеть некоторые проблемы. Один из возможных подходов состоит в использовании итерационных методов. Для этого нужно начать с произвольных исходных значений полезностей, вычислить правую часть уравнения и подставить ее в левую, тем самым обновляя значение полезности каждого состояния с учетом полезностей его соседних состояний. Такая операция повторяется до тех пор, пока не достигается равновесие. Допустим, что Ui(s) — это значение полезности для состояния s в i-й итерации. Шаг итерации, называемый обновлением Беллмана, выглядит следующим образом:
Если обновление Беллмана используется неопределенно большое количество раз, то гарантируется достижение равновесия (см. следующий подраздел), и в этом случае конечные значения полезности должны представлять собой решения уравнений Беллмана. В действительности они также представляют собой уникальные решения, и соответствующая стратегия (полученная с помощью уравнения 17.4) является оптимальной. Применяемый при этом алгоритм, называемый Value-Iteration, показан в листинге 17.1.
Листинг 17Л. Алгоритм итерации по значениям для вычисления полезностей состояний. Условие завершения работы взято из уравнения 17.8
function Value-Iteration(mdp, е) returns функция полезности
inputs: mdp, задача MDP с состояниями S, моделью перехода Т, функцией вознаграждения R, коэффициентом обесценивания у е, максимально допустимая ошибка определения полезности любого состояния local variables: U, Uy , векторы полезностей для состояний из S, первоначально равные нулю 5, максимальное изменение полезности любого состояния во время итерации
Мы можем применить алгоритм итерации по значениям к миру 4x3 (см. рис. 17.1, а). Начиная с исходных значений, равных нулю, полезности изменяются, как показано на рис. МЛ, а. Обратите внимание на то, как состояния, находящиеся на различных расстояниях от квадрата (4,3), накапливают отрицательное вознаграждение до тех пор, пока в какой-то момент не обнаруживается путь к состоянию (4,3), после чего значения полезности начинают возрастать. Алгоритм итерации по значениям может рассматриваться как способ распространения информации через пространство состояний с помощью локальных обновлений.