2-динамическое программирование

2-динамическое программирование

В этой статье мы рассмотрим несколько возможных решений для MDP, чтобы получить наилучшую политику для торговли в марковской среде.

Общая итерация политики:

Общая итерация политики (GPI) — это общая структура решения в Reinforcement Learning, а не только для MDP. Стратегия решения чередуется между двумя методами расчета: «оценка политики» и «улучшение политики». На этапе оценки политики функция значения для текущей политики оценивается для каждого состояния: степень детализации оценки, метод обновления функции значения и окончательный критерий оценки различаются в зависимости от метода, используемого на этом этапе. категория алгоритмов оценки. Цель шага улучшение политики — обновить политику после этапа оценки функции ценности предыдущей политики. Обновление ищет жадное действие для лучшего следующего значения функции значения состояния во всех состояниях.

Принцип чередования этих двух процессов можно увидеть на рисунке выше. Эта процедура ведет к наилучшей политике с соответствующей функцией оцененного значения в каждом состоянии.

Динамическое программирование:

Динамическое программирование (DP) — это мощный метод решения проблем, при котором основная проблема может быть разбита на подзадачи с той же структурой, что и основная проблема.Основная идея DP состоит в том, чтобы запомнить результаты подзадач (это называется запоминанием) и избежать пересчета предыдущих результатов. Этот тип методологии соответствует рекурсивному исчислению, поскольку здесь значение функции выражается другими значениями той же функциональной формы/структуры.

§ Пример:

Чтобы продемонстрировать концепцию DP, мы используем функцию Фибоначчи для вычисления последовательности рядов чисел Фибоначчи.

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

Двумя широко используемыми методами DP для решения MDP для небесконечных наборов состояний и действий в марковских средах являются итерация политики и итерация значения.

+++ Итерация политики:

Основная идея итерации политики заключается в чередовании оценки политики и улучшения политики, что приводит к монотонному и строгому улучшению политик и оценки функций ценности в каждом состоянии по сравнению с предыдущими итерациями. Этот аспект проявляется в следующих последовательностях:

Базовый алгоритм показан в следующем поле:

Теперь мы можем пройти вычислительные этапы этого алгоритма: (1) сначала мы произвольно определяем значения всех функций ценности каждого состояния; Кроме того, мы создаем политику случайного ответа из набора действий в каждом состоянии.

На этапе оценки политики (2) мы запускаем два цикла. Первый проверяет, соблюдается ли критерий остановки, в нашем случае, если разница между последовательными итерациями для всех функций значений состояния ниже определенного порога, тогда аутцикл переходит к следующему алгоритму «улучшение политики». . Во внутреннем цикле выполняется итерация по всем состояниям, на каждой итерации предыдущее значение функции значения рассматриваемого состояния сохраняется в переменной «v», затем обновляется новая функция значения этого соответствующего состояния в соответствии со следующим уравнение:

Как видите, обновление функции текущего значения состояния «s» выполняется со значением s-хода следующего состояния, но с предыдущей итерации, а не с текущей.

Обновление функции значения каждого состояния будет выполняться до тех пор, пока функция значения для текущей политики не достигнет фиксированной точки для каждой функции значения состояния.

На шаге (3) «улучшение политики» мы сначала проверяем, является ли политика уже стабильной и не изменилась ли она по сравнению с последней политикой. Если это так, то можно сказать, что мы получили оптимальную политику для данной среды. Если нет, нам нужно перебрать все состояния и для каждого состояния сохранить предыдущий ответ политики в этом состоянии. Затем мы изучаем, какое действие в этом состоянии может привести к максимальному расчетному доходу на основе последнего обновления функций ценности для всех состояний. Полученное действие в этом состоянии будет сохранено как новый ответ в карте политик. Если ранее сохраненная карта политик и новая карта политик не имеют различий, то можно сказать, что мы достигли оптимальной политики, которую искали. Напротив, нам нужно начать с шага (2), но с новой рассчитанной политикой для обновления функций значений всех состояний.

Итерация значения +++:

Итерация значений — это альтернативный метод итерации политики для вычисления оптимальной политики для марковских сред.

Как видно из приведенного выше блока, этап оценки и улучшения функции и политики ценности здесь отсутствует.

Вместо этого мы проходим через все состояния и действия, мы жадно реагируем на действия, которые приводят к максимальной функции ценности действия в каждом состоянии. Этот процесс заканчивается, когда функция значения (в нашем случае функция значения соответствует последней функции значения максимального действия в этом состоянии) всех состояний сходится к соответствующей им фиксированной точке. В этот момент оптимальной стратегии соответствует последнее выбранное действие в каждом состоянии, которое привело к максимуму функции ценности в этом состоянии.

Ссылка:

• Обучение с подкреплением для киберфизических систем: с примерами кибербезопасности, Chong Li, Meikang Qiu
• Обучение с подкреплением: введение, Ричард С. Саттон и Эндрю Дж. Барто.