В чем разница между итерацией политики и итерацией значения в обучении с подкреплением?
Насколько я понимаю, в итерации значений вы используете уравнение Беллмана для определения оптимальной политики, тогда как в итерации политики вы случайным образом выбираете политику π и находите вознаграждение за эту политику.
Я сомневаюсь, что если вы выбираете случайную политику π в PI, как она гарантированно будет оптимальной политикой, даже если мы выбираем несколько случайных политик.
Давайте посмотрим на них рядом. Ключевые части для сравнения выделены. Рисунки взяты из книги Саттона и Барто: Обучение с подкреплением: Введение.
Ключевые моменты:
По моему опыту, итерация политики выполняется быстрее, чем итерация значения, поскольку политика сходится быстрее, чем функция значения. Я помню, это тоже описано в книге.
Я предполагаю, что путаница в основном возникла из-за всех этих в некотором роде похожих терминов, которые раньше меня тоже сбивали с толку.
В алгоритмах итерации политики вы начинаете со случайной политики, затем находите функцию значения этой политики (этап оценки политики), затем находите новую (улучшенную) политику, основанную на предыдущей функции значения, и так на. В этом процессе каждая политика гарантированно будет строго улучшена по сравнению с предыдущей (если она уже не оптимальна). Для данной политики ее функцию значения можно получить с помощью оператора Беллмана.
В итерации значения вы начинаете с функции случайного значения, а затем находите новую (улучшенную) функцию значения в итеративном процессе, пока не достигнете функции оптимального значения. Обратите внимание, что вы можете легко вывести оптимальную политику из функции оптимального значения. Этот процесс основан на операторе Беллмана оптимальности.
В некотором смысле оба алгоритма используют один и тот же принцип работы, и их можно рассматривать как два случая < em> обобщенная итерация политики. Однако оператор Беллмана оптимальности содержит оператор max, который является нелинейным и, следовательно, имеет другие функции. Кроме того, можно использовать гибридные методы между итерацией чистого значения и итерацией чистой политики.
Основная разница -
В Итерации политики - вы случайным образом выбираете политику и находите соответствующую ей функцию значения, затем находите новую (улучшенную) политику на основе предыдущей функции значения, и так далее это приведет к оптимальной политике.
В Итерации значений - вы случайным образом выбираете функцию значения, затем находите новую (улучшенную) функцию значения в итеративном процессе до достижения функции оптимального значения, а затем получаете оптимальную политику из этой функции оптимального значения.
Итерация политики работает по принципу «Оценка политики -> Улучшение политики».
Value Iteration работает по принципу «Функция оптимального значения -> оптимальная политика».
Основное различие в скорости связано с максимальной операцией на каждой итерации итерации значения (VI).
В VI каждое состояние будет использовать только одно действие (с максимальным значением полезности) для вычисления обновленного значения полезности, но сначала необходимо вычислить значение всех возможных действий, чтобы найти это действие с помощью уравнения Беллмана.
В итерации политики (PI) эта максимальная операция опускается на шаге 1 (оценка политики), просто следуя промежуточной политике для выбора действия.
Если существует N возможных действий, VI должен вычислить уравнение Беллмана N раз для каждого состояния, а затем взять максимум, тогда как PI просто вычисляет его один раз (для действия, указанного в текущей политике).
Однако в PI есть шаг улучшения политики, который по-прежнему использует оператор max и выполняется так же медленно, как шаг в VI, но поскольку PI сходится за меньшее количество итераций, этот шаг будет происходить не так часто, как в VI.
Насколько мне известно, вопреки идее @zyxue, VI обычно намного быстрее, чем PI.
Причина очень проста, как вы уже знаете, уравнение Беллмана используется для решения функции ценности для данной политики. Поскольку мы можем решить функцию значения для оптимальной политики напрямую, решение функции значения для текущей политики, очевидно, является пустой тратой времени.
Что касается вашего вопроса о сходимости PI, я думаю, вы могли упустить из виду тот факт, что если вы улучшите стратегию для каждого информационного состояния, то вы улучшите стратегию для всей игры. Это также легко доказать, если вы были знакомы с минимизацией контрфактического сожаления - сумма сожаления для каждого информационного состояния сформировала верхнюю границу общего сожаления, и, таким образом, минимизация сожаления для каждого состояния минимизирует общее сожаление, которое приводит к оптимальной политике.
