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

26

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

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

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

    
задан Arslán 22.05.2016 в 04:43
источник
  • Было бы более уместно задавать этот вопрос на таких сайтах, как ai.stackexchange.com, stats.stackexchange.com или datascience.stackexchange.com. –  nbro 17.12.2017 в 01:12

2 ответа

33

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

Ключевые моменты:

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

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

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

ответ дан zyxue 27.02.2017 в 19:35
источник
  • Я согласен, что итерация политики сходится в меньшем количестве итераций, и я также читал в нескольких местах, что это быстрее. Я сделал несколько простых экспериментов по созданию бокса и лабиринта с обоими методами в Burlap. Я обнаружил, что итерация значений выполняла больше итераций, но занимала меньше времени, чтобы достичь конвергенции. YMMV. –  Ryan 25.01.2018 в 02:17
  • @Ryan Вы видели мир гридов? Итерация значения стоимости сходится быстрее, чем итерация политики. Я не совсем уверен в других системах, но я прочитал в книге Ричарда Саттона, что значение итерации лучше. Зачем? - Поскольку при выполнении итерации политики на этапе оценки политики вы должны оценить политику до конвергенции, даже если оценка после некоторого шага не нужна. –  Cbrom 11.03.2018 в 13:51
  • @Chrom, вы должны были прочитать oppposite. Вот цитата из книги: «Итерация политики часто сходится на удивительно немногих итерациях, что иллюстрируется примером на рисунке 4.1.», Начиная с версии книги версии 2017nov5. –  zyxue 11.03.2018 в 23:41
  • Да, я играл с несколькими вкусами грид-мира. Я просто пытался указать, что «быстрее» с точки зрения итераций, вероятно, будет способствовать PI. Но «Быстрее» с точки зрения секунд может действительно способствовать VI. –  Ryan 12.03.2018 в 19:44
  • Чтобы уточнить, итерация политики займет меньше итераций, но более сложна в вычислительном отношении, чем итерация значения; который быстрее зависит от окружающей среды. –  R.F. Nelson 10.05.2018 в 16:02
31

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

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

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

    
ответ дан Pablo EM 23.05.2016 в 09:34
источник
  • Хорошее описание по этому вопросу. Хорошо, позвольте мне добавить эту вещь в итерацию политики, она использует уравнение ожидания belman, а в итерации значения использует уравнение максимального размера. Для итерации значений это может быть меньше итераций, но для одной итерации может быть так много работы. Для итерации политики больше итераций –  Shamane Siriwardhana 07.11.2017 в 06:40
  • не существует ли оператор max в итерации политики? в противном случае, как обновить политику, основанную на новой функции значений? –  huangzonghao 07.04.2018 в 22:04
  • Нет, алгоритм SARSA является типичным примером итерации политики. Как вы можете видеть в этом псевдокоде (incompleteideas.net/book/ebook/node64.html), обновление функции значения не содержит никакого оператора max. Однако, если вы имеете в виду макс-оператор для выбора наилучших действий из функции значений (то есть жадных действий), да, в таком процессе есть максимальная операция. –  Pablo EM 08.04.2018 в 17:19