ИТЕРАЦИЯ ПО ЗНАЧЕНИЯМ
В этом разделе представлен алгоритм вычисления оптимальной стратегии, называемый итерацией по значениям. Основная его идея состоит в том, что нужно рассчитать полезность каждого состояния, а затем использовать полезности состояний для выбора оптимального действия в каждом состоянии.
Полезности состояний
Полезность состояний определяется в терминах полезности последовательностей состояний. Грубо говоря, полезность любого состояния представляет собой ожидаемую полезность последовательностей состояний, которые могут привести к этому состоянию. Очевидно, что перечень таких последовательностей состояний зависит от осуществляемой стратегии, поэтому начнем с определения полезности iP{s) по отношению к конкретной стратегии к. Если мы предположим, что st — это состояние, в котором находится агент после осуществления стратегии к в течение t шагов (обратите внимание на то, что st — случайная переменная), то получим следующее:
На основании этого определения можно утверждать, что истинная полезность любого состояния, которую обозначим как U{s), представляет собой (s), т.е. ожидаемую сумму обесцениваемых вознаграждений, при условии, что агент осуществляет оптимальную стратегию. Обратите внимание на то, что U(s) и R(s) — совершенно разные величины; R{s) — это "кратковременное" вознаграждение за пребывание в состоянии s; U(s) — "долговременное" суммарное вознаграждение, которое начинается с состояния s и продолжается дальше. На рис. 17.3 показаны рассматриваемые значения полезности для мира 4x3. Заслуживает внимание то, что значения полезности по мере приближения состояний к выходу +1 становятся выше, поскольку уменьшается количество шагов, требуемых для достижения этого выхода.
Эта функция полезности u(s) позволяет агенту выбирать действия с использованием принципа максимальной ожидаемой полезности, приведенного в главе 16, т.е. выбирать действие, которое максимизирует ожидаемую полезность в следующем состоянии:
Итак, если полезность некоторого состояния представляет собой ожидаемую сумму обесцениваемых вознаграждений, начиная с данного момента и дальше, то существует прямая связь между полезностью состояния и полезностью его соседних состояний: полезность некоторого состояния равна сумме непосредственного вознаграждения за пребывание в этом состоянии и ожидаемой обесцениваемой полезности следующего состояния, при условии, что агент выбирает оптимальное действие. Это означает, что полезность любого состояния можно определить с помощью следующего соотношения:
Уравнение 17.5 называется уравнением Беллмана в честь Ричарда Беллмана [97]. Полезности состояний (определяемые с помощью уравнения 17.3 как ожидаемые полезности дальнейших последовательностей состояний) являются решениями множества уравнений Беллмана. В действительности, как будет показано в следующих двух разделах, они являются уникальными решениями.
Рассмотрим одно из уравнений Беллмана для мира 4x3. Уравнение для состояния (1,1) приведено ниже.
После подстановки в это уравнение чисел, приведенных на рис. 17.3, можно обнаружить, что наилучшим действием является Up.