В чем разница между итерацией значения и итерацией политики?

94

В обучении с подкреплением, в чем разница между итерации политики и значение итерации ?

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

Я сомневаюсь, что если вы выбираете случайную политику π в PI, как гарантировать, что она будет оптимальной политикой, даже если мы выбираем несколько случайных политик.

Арслан
источник
13
Уместнее было бы задать этот вопрос на таких сайтах, как ai.stackexchange.com , stats.stackexchange.com или datascience.stackexchange.com .
nbro

Ответы:

124

Давайте посмотрим на них рядом. Выделены ключевые части для сравнения. Рисунки взяты из книги Саттона и Барто: Обучение с подкреплением: Введение .

введите описание изображения здесь Ключевые моменты:

  1. Итерация политики включает в себя: оценку политики + улучшение политики , и они повторяются итеративно до тех пор, пока политика не сойдется.
  2. Итерация значения включает: поиск функции оптимального значения + одно извлечение политики . И то и другое не повторяется, потому что, как только функция ценности является оптимальной, политика вне ее также должна быть оптимальной (т. Е. Конвергентной).
  3. Нахождение функции оптимального значения также можно рассматривать как комбинацию улучшения политики (из-за max) и усеченной оценки политики (переназначение v_ (s) после всего лишь одного цикла всех состояний независимо от сходимости).
  4. Алгоритмы оценки политики и поиска функции оптимального значения очень похожи, за исключением операции max (как выделено)
  5. Кроме того , ключевой шаг на пути к совершенствованию политики и извлечению политики является идентичным , за исключением бывшего включает в себя проверку на стабильность.

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

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

Zyxue
источник
3
Я согласен с тем, что итерация политики сходится за меньшее количество итераций, и я также читал в нескольких местах, что это быстрее. Я провел несколько простых экспериментов с миром ящиков и решением лабиринтов обоими методами в Burlap. Я обнаружил, что итерация значений выполняет больше итераций, но требует меньше времени для достижения сходимости. YMMV.
Райан
1
@Chrom, ты должен был прочитать противоположное. Вот цитата из книги « Итерация политики часто сводится к удивительно небольшому количеству итераций. Это иллюстрируется примером на рисунке 4.1. » Со страницы 65 версии книги 2017nov5 .
zyxue
3
Да, я играл с несколькими разновидностями Grid world. Я просто пытался указать, что «Быстрее» с точки зрения итераций, вероятно, будет предпочтение PI. Но «Быстрее» в секундах на самом деле может быть лучше VI.
Ryan
3
Чтобы уточнить, итерация политики потребует меньше итераций, но является более сложной в вычислительном отношении, чем итерация значения; какой из них быстрее, зависит от окружающей среды.
RF Nelson
2
Я знаю, что это старый пост. Но я настоятельно рекомендую изучить это ( medium.com/@m.alzantot/… ). Ссылка предоставляет код, и это сделало его более понятным для меня.
тандем
73

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

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

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

Пабло Э.М.
источник
1
Хорошее описание по этому поводу. Что ж, позвольте мне добавить эту вещь в итерацию политики, она использует уравнение ожидания Бельмана, а в итерации значения использует уравнение максимума Мелмана. Для итерации значения может быть меньше итераций, но для одной итерации может потребоваться очень много работы. Для итерации политики - больше итераций
Шаман Сиривардхана
нет ли оператора max в итерации политики? иначе как обновить политику на основе новой функции значения?
huangzonghao
Нет, алгоритм SARSA - типичный пример итерации политики. Как вы можете видеть в этом псевдокоде ( incompleteideas.net/book/ebook/node64.html ), обновление функции значения не содержит никакого оператора max. Однако, если вы имеете в виду оператор max для выбора лучших действий из функции значения (т.е. жадные действия), да, в таком процессе есть операция max.
Pablo EM
11

Основная разница -

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

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

Итерация политики работает по принципу «Оценка политики -> Улучшение политики».

Value Iteration работает по принципу «функция оптимального значения -> оптимальная политика».

Химаншу Гупта
источник
0

Насколько мне известно, вопреки идее @zyxue, VI обычно намного быстрее, чем PI.

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

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

Ответ777
источник