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