Узнайте об этом классическом алгоритме динамического программирования для оптимального решения марковских моделей процесса принятия решений.
Несколько дней назад я написал статью об итерации ценности (Ричард Беллман, 1957), сегодня пришло время для итерации политики (Рональд Ховард, 1960). Итерация политики — это точный алгоритм для решения моделей марковского процесса принятия решений, который гарантирует поиск оптимальной политики. По сравнению с итерацией значения преимуществом является наличие четкого критерия остановки — когда политика стабильна, она доказуемо оптимальна. Однако он часто имеет более высокую вычислительную нагрузку для задач со многими состояниями.
Итерация политики лежит в основе многих современных алгоритмов обучения с подкреплением, в частности алгоритмов класса аппроксимации политики. Фактически Берцекас и Цициклис (1996) интерпретируют ее как модель актора-критика, сочетающую обновление политики с функциями ценности. Прежде чем перейти к оптимизации проксимальной политики и градиентам естественной политики, имеет смысл сначала понять этот фундаментальный алгоритм.
Итерация политики
По сравнению с итерацией значения, итерация политики немного более обширна. Sutton & Barto (2019) разбивают его на три этапа.
Шаг 1 — инициализация — устанавливает (возможно произвольно) как функции значений, так и политику. Функции ценности дают воспринимаемую ценность пребывания в каждом состоянии, политика — это правило, которое возвращает действие для любого заданного состояния.
На шаге 2 — оценка политики — значение для каждого состояния определяется способом, очень похожим на итерацию значения. Однако вместо того, чтобы определять значения путем максимизации по всем действиям, мы просто вычисляем значения, используя текущую политику. Короче говоря, мы умножаем значение действия a=π(s) (прямое вознаграждение r+ нижестоящее значение V(s’)) на вероятность перехода p. Для получения более подробной информации, например о допуске к ошибкамθ, ознакомьтесь со статьей об итерации значений.
Шаг 3 — улучшение политики — направлен на улучшение политики с использованием функций преобладающей ценности. Для каждого состояния он проверяет, действительно ли действие, предлагаемое текущей политикой, является действием, максимизирующим ценность. Если нет, политика обновляется и шаг 2 повторяется. Алгоритм чередует оба шага, пока политика не останется стабильной. В этот момент достигается оптимальная политика, и алгоритм завершает работу.
Для прямого сравнения между итерацией значения и итерацией политики см. их рядом друг с другом здесь.
Минимальный рабочий пример
Время для примера кодирования. Мне нравится демонстрировать алгоритмы на очень простых задачах, о чем свидетельствует приведенный ниже краткий план.
Проблема
Интересующая проблема представляет собой одномерный мир (ряд плиток). В середине есть плитка, которая служит конечным состоянием. Приземление на эту плитку дает награду +10, переход между плитками стоит -1 за ход. Агент может принять решение двигаться влево или вправо, но в конечном итоге в 10% случаев движется в неправильном направлении. С прямым вознаграждением, ожидаемым последующим вознаграждением и вероятностями перехода он имеет основные элементы MDP.
Алгоритм
Алгоритм Python не слишком отличается от математической процедуры, показанной ранее. Обратите внимание, что максимальное количество итераций является упрощением для ограничения вычислительных ресурсов. В частности, если две или более политик работают одинаково хорошо, алгоритм может бесконечно переключаться между ними.
Некоторые эксперименты
Время немного поэкспериментировать. Я приведу несколько вычислительных примеров, а также немного поразмышляю над результатами.
Мы устанавливаем все функции значений V(s)=0 и инициализируем политику в π=[0,0,0,0,0] (т. е. всегда двигаемся влево).
Затем мы переходим к оценке политики. Повторим: на этом этапе мы определяем значения состояния в соответствии с текущей политикой π. Оценка политики — это повторяющийся шаг, который повторяется до тех пор, пока все значения не окажутся ниже порога ошибки θ. В этом случае (состояние 0, итерация 1) начальная оценка V(0) равна 0. Поскольку прямое вознаграждение равно -1, ошибка Δ также равна 1, и нам нужно повторить.
Требуется некоторое время, чтобы получить правильные значения. Если мы возьмем θ= 1e-10, нам потребуется не менее 185 итераций до Δ<θ для всех состояний. Получаем V=[-8.62, -7.08, 10.00, 7.61, 5.68].
Теперь переходим к усовершенствованию политики. Мы проверяем, действительно ли наша первоначальная политика («всегда идти налево») оптимальна — внимание, спойлер: это не так — с учетом значений, которые мы только что определили.
Очевидно, что на крайнем левом тайле лучше идти направо, чем налево. Таким образом, критерий остановки не выполняется. Мы обновляем π и возвращаемся к этапу оценки политики для повторного вычисления значений.
В конце концов, мы должны прийти к точке, где политика больше не меняется. В данном случае это просто еще один цикл. После обновления политики мы вычисляем новые значения состояния (16 итераций) во время оценки политики и не вносим никаких изменений в политику на последующем этапе улучшения политики. Алгоритм завершился, что дало π=[1,1,0,0,0].
Кроме этого, на самом деле сказать особо нечего. Существует вычислительный компромисс между θ и количеством циклов между Шагом 2 и Шагом 3, но для этой конкретной задачи это вряд ли имеет значение.
Хотя во многом это похоже на итерацию значения, обратите внимание, что итерация политики возвращает политику, а итерация значения — набор функций значения. При переходе к приближенным (обучение с подкреплением) алгоритмам это различие становится актуальным. У вас может быть хорошая политика, не имея больших функций ценности (или даже не зная их), и вы можете иметь точные функции ценности без явного понимания самой политики.
Заключительные слова
Как и итерация значения, итерация политики является фундаментальным алгоритмом, из которого выводятся многие приближенные алгоритмы. Прежде чем по-настоящему погрузиться в мир обучения с подкреплением, убедитесь, что понимаете итерацию политики.
Еще несколько минимальных рабочих примеров, которые могут вас заинтересовать:
Рекомендации
Беллман, Р. (1957). Марковский процесс принятия решений. Журнал математики и механики, 6(5), 679–684.
Берцекас, Д. П., и Цициклис, Дж. Н. (1996). Нейродинамическое программирование. Афина научная.
Ховард, Р. А. (1960). Динамическое программирование и марковские процессы.
Саттон, Р.С., и Барто, А.Г. (2019). Обучение с подкреплением: введение. Массачусетский технологический институт Пресс.
