ИТЕРАЦИЯ ПО СТРАТЕГИЯМ
тимальной стратегией. Поскольку для каждого конечного пространства состояний количество возможных стратегий является конечным и можно показать, что каждая итерация приводит к определению лучшей стратегии, то алгоритм итерации по стратегиям должен всегда завершать свою работу.
Листинг 17.2. Алгоритм итерации по стратегиям для вычисления оптимальной стратегии
function Policy-Iteration(mdp) returns стратегия
inputs: mdp, задача MDP с состояниями S, моделью перехода Т local variables: U, U' , векторы полезностей для состояний из S,
первоначально равные нулю к, вектор стратегий, индексированный по состояниям, первоначально сформированный случайным образом
repeat
U <— Policy-Evaluation(я, U, mdp) unchanged? <— истинное значение for each состояние s in S do
Очевидно, что этап усовершенствования стратегии является несложным, а как реализовать процедуру Policy-Evaluation? Оказалось, что осуществление такого подхода намного проще по сравнению с решением стандартных уравнений Беллмана (а именно это происходит в алгоритме итерации по значениям), поскольку действие, применяемое в каждом состоянии, зафиксировано в соответствии с выбранной стратегией. Стратегия 7Г± определяет действие 7Г± (s), выполняемое в состоянии s на i-й итерации. Это означает, что можно воспользоваться упрощенной версией уравнения Беллмана (17.5), которая связывает полезность состояния s (соответствующую стратегии тг±) с по-лезностями его соседних состояний, следующим образом:
Например, предположим, что 7Г± — это стратегия, показанная на рис. 17.2, а. В таком случае имеет место п± (1,1) = Up, 7ti (1, 2) - Up и т.д., а упрощенные уравнения Беллмана принимают следующий вид:
СМ1,1) = -0.04 + 0.8 C7i(l,2) + 0.1 C7i (1, 1) + 0.1 C7i(2,l) C7i(l,2) = -0.04 + 0.8 C7i(l,3) + 0.2 C7i (1,2)
Важно отметить, что эти уравнения — линейные, поскольку оператор "max" был удален. Для п состояний имеется п линейных уравнений с п неизвестными, которые могут быть решены точно за время О (л3) с помощью стандартных методов линейной алгебры.
Для небольших пространств состояний оценка стратегии с использованием точных методов решения часто является наиболее эффективным подходом, а для больших пространств состояний затраты времени О (л3) могут оказаться чрезмерно большими. К счастью, точная оценка стратегии не требуется. Вместо этого можно выполнить некоторое количество упрощенных этапов итерации по значениям (они являются упрощенными, поскольку стратегия зафиксирована) для получения достаточно хорошей аппроксимации полезности. Упрощенное обновление Беллмана для этого процесса определяется таким соотношением:
и определяемая в нем операция подстановки повторяется к раз для получения следующей оценки полезности. Результирующий алгоритм называется модифицированной итерацией по стратегиям. Он часто оказывается намного более эффективным, чем стандартная итерация по стратегиям или итерация по значениям.
Алгоритмы, описанные до сих пор в данной главе, требуют одновременного обновления полезности или стратегии для всех состояний. Как оказалось, применение такой организации работы не является строго необходимым. В действительности в каждой итерации можно выбирать любое подмножество состояний и применять к этому подмножеству либо тот, либо другой вид обновления (усовершенствование стратегии или упрощенную итерацию по значениям). Такой наиболее общий алгоритм называется асинхронной итерацией по стратегиям. При соблюдении определенных условий выбора исходной стратегии и функции полезности гарантируется сходимость асинхронной итерации по стратегиям к определенной оптимальной стратегии. А то, что мы вправе выбирать для работы с ними любые состояния, означает, что могут быть разработаны гораздо более эффективные эвристические алгоритмы, например, алгоритмы, которые сосредоточиваются на обновлении значений состояний, которые с наибольшей вероятностью будут достигнуты при осуществлении качественной стратегии. Такой подход имеет гораздо больше смысла в реальной жизни — если человек не намеревается попасть на прибрежную полосу, спрыгнув с высокой скалы, то для него нет смысла заниматься точной оценкой стоимости связанных с этим результирующих состояний.
В описании марковских процессов принятия решений, приведенном в разделе 17.1, предполагалось, что среда является полностью наблюдаемой. При использовании этого предположения агент всегда знает, в каком состоянии он находится. Это предположение, в сочетании с предположением о марковости модели перехода, означает, что оптимальная стратегия зависит только от текущего состояния. А если среда является только частично наблюдаемой, то вполне очевидно, что ситуация становится гораздо менее ясной. Агент не всегда точно знает, в каком состоянии находится, поэтому не может выполнить действие к (s), рекомендуемое для этого состояния. Кроме того, полезность состояния s и оптимальное действие в состоянии s зависят не только от s, но и от того, насколько много агент знает, находясь в состоянии s. По этим причинам задачи MDP в частично наблюдаемой среде (Partially Observable MDP — POMDP, читается как "пом-ди-пи") обычно рассматриваются как намного более сложные по сравнению с обычными задачами MDP. Однако невозможно игнорировать необходимость решения задач POMDP, поскольку реальный мир изобилует такими задачами.