В сегодняшней статье мы сосредоточимся на итерации политики MDP. Мы по-прежнему используем пример мира сетки из книги Стюарта Рассела и Питера Норвига Artificial Intelligence A Modern Approach.

Код в этой истории является частью нашего проекта MAD с нуля, где MAD означает машинное обучение, искусственный интеллект и наука о данных. Полный код, использованный в этой истории, можно найти в этом репозитории: https://github.com/clumsyhandyman/mad-from-scratch.

Оглавление:

  1. Политика как тропинка дерева
  2. Полезность состояний
  3. Дисконтные награды
  4. Добавить обратно стохастик
  5. Оценка политики
  6. Улучшение политики
  7. Политическая итерация
  8. Эффекты дисконтированного фактора
  9. Псевдокод итерации политики
  10. Реализовать итерацию политики в Python

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

В нашей первой истории MDP мы показали, что не все политики одинаковы. По статистике одни лучше других. Например, мы исследовали три случайно сгенерированные политики, многократно запуская каждую из них 10 000 раз. В среднем общее вознаграждение, получаемое каждой политикой за прогон, составляет -1,7, -1,2 и 0,7 соответственно. Ясно, что третья политика лучше двух других. Наш вопрос заключается в том, как найти наилучшую политику среди всех возможных?

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

Политика как путь дерева

В нашем мире сетки нормальное состояние имеет награду -0,04, хорошее зеленое конечное состояние имеет награду +1, а плохое красное конечное состояние имеет награду -1.

Теперь представьте, что мы стоим в нашем начальном состоянии s = 8, и нам нужно решить, какое действие предпринять: либо перейти вправо к s = 9, либо подняться к s= 4. Состояние s = 9 дает нам вознаграждение в размере -0,04, как и состояние s = 4. Они кажутся одинаковыми для нас. Однако интуитивно мы знаем, что они не одинаковы. Какое бы состояние ни было ближе к нашему хорошему конечному состоянию, оно должно быть лучше другого.

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

В каком-то смысле мы можем думать о нашем выборе действий как о дереве, где каждое состояние является узлом, а каждое действие — ветвью. В нашем примере начальное состояние s = 8 — это корневой узел, а 4 возможных действия — это 4 ветви. Для простоты давайте на мгновение пренебрежем стохастикой MDP. Наша награда за выбор действия ВВЕРХ составляет -0,04, как и при выборе ВПРАВО, ВНИЗ или ВЛЕВО. Итак, если мы посмотрим только на первый уровень нашего дерева, выбор любого действия приведет к одинаковому вознаграждению.

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

Здесь мы сталкиваемся с проблемой резервного копирования: нам нужно отразить вознаграждения узлов вниз по дереву резервного копирования вдоль ветвей, чтобы мы могли выбрать ветви, которые ведут к этим предпочтительным узлам. Давайте посмотрим, как мы можем это сделать.

Полезность состояний

Для выполнения резервного копирования мы вводим понятие полезность или значение. У каждого состояния есть полезность, которая показывает, насколько оно хорошо с точки зрения продвижения к хорошему пути в будущем.

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

Теперь наш вопрос заключается в том, как сопоставить утилиту с каждым состоянием. А пока давайте продолжим пренебрегать стохастикой MDP. Представьте, что мы стоим в s = 8. Если мы дойдем до s = 9, мы получим вознаграждение в размере -0,04; если мы перейдем к s = 4, мы также получим вознаграждение в размере -0,04. Однако, если мы выберем s = 9, это может привести нас к пути [9, 10, 11, 7], соответствующем вознаграждению [-0,04, -0,04, -0,04, -1]. . Поскольку MDP обладает свойством дополнительного вознаграждения, общее вознаграждение на этом пути равно -1,12. Напротив, если мы выберем s = 4, это может привести нас к пути [4, 0, 1, 2, 3], соответствующем вознаграждению [-0,04, -0,04, -0,04, -0,04, +1] с общей наградой 0,84. В упрощенном подходе мы можем выбрать s = 9 или s = 4 в качестве нашего следующего состояния в зависимости от того, что нам предпочтительнее -1,12 или 0,84. Здесь -1,12 — полезность состояния s = 9, а 0,84 — полезность состояния s = 4. Обычно мы используем v для обозначения полезность государств.

Конечно, найти полезность состояний не так просто, поскольку разные действия приводят к разным состояниям. В результате мы не уверены, какой путь мы достигнем, следуя данному состоянию. Например, мы можем двигаться по пути [9, 10, 11, 7] или [9, 10, 6, 2, 3] или даже [9, 10, 6, 2, 1, 0, 4…] после s = 9. Чтобы рассчитать полезность s = 9, какой из всех возможных путей следует использовать?

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

Согласно этим предположениям, для любого состояния значение полезности является суммой вознаграждения самого себя и всех будущих состояний, следующих этой политике. Например, если мы посмотрим на s = 6 и будем следовать политике, перед нами будет путь [6, 10, 11, 7]. Следовательно, полезность s= 6 равна сумме r(6), r(10), r(11) и r(7).

Для любого состояния s в момент времени t= 0 его полезность может быть записана как

Теперь у нас есть v(6) = r(6) + r(10) + r(11) + r(7). Таким образом, полезность s=10 равна v(10) = r(10) + r(11) + r(7). Комбинируя эти два, мы получаем v(6) = r(6) + v(10). Это справедливо для любого государства и его государств-преемников.

Другими словами, полезность государства — это непосредственная награда этого государства плюс полезность его преемника, следующего за данной политикой.

Награды со скидкой

Теперь давайте посмотрим на другое состояние s = 0. Следуя политике, будущие состояния — это [0, 1, 2, 1, 2, 1, 2, 1, 2, …], что представляет собой цикл 1 и 2 навсегда. Если следовать нашему определению полезности, v(0) = r(0) + r(1) + r(2) + r(1) + r(2) + …, мы получили бы отрицательную бесконечность.

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

Основная идея дисконтных вознаграждений заключается в том, что вознаграждение, полученное в будущем, менее ценно, чем вознаграждение, полученное прямо сейчас. Это похоже на экономику в реальной жизни. Из-за процентной ставки один доллар, который вы получили сейчас, более ценен, чем один доллар, который вы получите через 10 лет. В MDP мы используем коэффициент дисконтирования γ для имитации процентной ставки.

Прежде чем мы получим дополнительные вознаграждения, т.е.

Теперь, используя награды со скидкой, мы

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

С дисконтированным коэффициентом отношение между полезностью государства и полезностью его государства-преемника равно

Добавить обратно стохастик

Мы определили полезность в детерминированной среде. Теперь пришло время снова добавить стохастик в нашу игру. В детерминированной среде, когда мы смотрим на s = 6, мы имеем определенный путь [6, 10, 11, 7] и, таким образом, v(6) = г(6) + r(10) + r(11) + r(7). В стохастической среде, даже если мы будем следовать политике, мы не гарантированно будем двигаться по пути [6, 10, 11, 7]. Чтобы быть более конкретным, у нас есть только вероятность 0,8³ = 0,512 действительно двигаться по этому пути.

Глядя на другие пути, мы имеем вероятность 0,1 двигаться по пути [6, 7], вероятность 0,04096 двигаться по пути [6, 10, 11, 10, 11, 7] и все остальные вероятности для всех остальных пути. Полезность состояния s = 6 — это ожидаемое вознаграждение после распределения вероятностей всех этих возможных путей.

Обобщая это, мы можем определить полезность в стохастической среде как

где E — математическое ожидание относительно распределения вероятностей по возможным путям, следующим определенной политике.

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

Например, если мы посмотрим на s= 6, следуя нашей политике DOWN, у нас будет 0,8 вероятность достижения s′= 10, вероятность 0,1 достичь s′= 7 и вероятность 0,1 остаться в s′= 6. Таким образом, полезность s= 6 есть

Оценка политики

Для заданной политики теперь мы готовы определить значения полезности для каждого состояния. Мы уже имеем

Точно так же мы можем написать это уравнение для каждого состояния:

Поскольку мы знаем вознаграждение каждого состояния, а γ — это произвольный коэффициент от 0 до 1, который мы определяем, у нас здесь 11 уравнений и 11 неизвестных. Задача решена. Мы можем определить полезность каждого состояния, непосредственно решая эти уравнения. Этот процесс называется оценка политики: для данной политики мы оцениваем эту политику, определяя полезность каждого состояния.

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

Например, если мы установим γ равным 0,5 (подробнее об этом в следующей части этой истории) и переберем состояния от s= 0 до s = 11, мы иметь

Это называется проверкой на месте. «На месте» означает, что мы используем обновленную утилиту немедленно в этом же цикле. Например, мы обновили v(1) как -0,04, а затем сразу же использовали это значение как v(1) при расчете v(2 ).

Продолжаем еще одну развертку:

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

Эти значения полезности являются приблизительными решениями линейных уравнений, которые мы перечислили выше. Например, давайте проверим состояние s = 6. Утилита должна быть

Здесь у нас есть

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

Улучшение политики

После того, как мы получим утилиту для этой политики, пришло время улучшить политику. Как мы уже говорили, полезность показывает, насколько хорошо состояние. При выборе действий для состояния следует отдавать предпочтение последующим состояниям с более высокой полезностью. Например, если мы посмотрим на состояние s = 2, потенциальные последующие состояния включают 1, 3 и 6. Очевидно, что s = 3 — лучший выбор, поскольку он имеет наивысшее значение. полезность 1,999. Другой пример: если мы посмотрим на состояниеs = 8, потенциальные последующие состояния включают 4 и 9 с полезностью -0,0814 и -0,1110 соответственно. Таким образом, s=4 предпочтительнее, чем s=9.

Поскольку наш MDP является стохастическим, выбор предпочтительного состояния-преемника не гарантирует, что мы его достигнем. Сравнивать следует не государства-преемники, а действия. Для состояния s = 6 у нас есть четыре возможных действия. Если мы выберем действие ВВЕРХ, ожидаемая награда составит

Точно так же, если мы решим пойти НАЛЕВО, у нас будет

Если мы пойдем ВНИЗ, у нас будет

Если мы пойдем ВПРАВО, у нас будет

Сравнивая результаты этих четырех возможных действий, очевидно, что ВВЕРХ — лучший выбор. Следовательно, мы должны обновить политику состояния s = 6 до UP.

Мы выполняем этот процесс для каждого состояния:

В нашем примере после улучшения политики наша политика выглядит так:

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

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

Что делает оценка политики, так это обновляет значения полезности, сохраняя при этом политику неизменной (от π[i], V[i-1] до π [i], V[i]). Улучшение политики заключается в обновлении политики при сохранении постоянных значений полезности (от π[i], V[i] до π[ i +1], V[i]). Когда π[i] совпадает с π[i +1], нет необходимости продолжать, и мы называем это сходимостью. В этом итеративном процессе мы начинаем со случайно сгенерированной политики π[1] и в конечном итоге сходимся к оптимальной политике π[6].

Эффекты дисконтированного фактора

Теперь пришло время поговорить о дисконтированном факторе. Ранее мы произвольно установили его равным 0,5. Что это значит? Что, если мы выберем 0,1 или 0,9?

Коэффициент дисконтирования γ используется для дисконтирования вознаграждений будущих состояний при их сложении.

Если мы выберем 0,1 в качестве γ, мы получим

Напротив, если мы выбираем 0,9, мы имеем

В случае γ = 0,1 вознаграждение, которое мы получим в будущем, мало повлияет на полезность состояния. Например, вознаграждение, полученное при t = 3, имеет коэффициент всего 0,001. Изменения этого вознаграждения почти не влияют на полезность. С другой стороны, когда γ = 0,9, вознаграждение при t = 3 имеет коэффициент 0,729. Изменения этого вознаграждения могут значительно изменить полезность.

Таким образом, меньшее γ подчеркивает немедленную награду за текущее состояние, в то время как большее γ подчеркивает долгосрочное вознаграждение в будущем. Если использовать инвесторов в качестве аналогии, инвестор с меньшим γ — это тот, кто отдает предпочтение компаниям с самой высокой текущей годовой прибылью, независимо от того, как выглядит их будущее. Напротив, инвестор с более высоким значением γ отдает предпочтение компаниям с более блестящим будущим, даже если сейчас они могут иметь низкую годовую прибыль.

Давайте посмотрим на влияние дисконтированного фактора в нашем примере мира сетки, сравнив три значения γ: 0,1, 0,5 и 0,9. После итерации политики полезность и оптимальная политика с использованием каждого γ показаны ниже.

Когда γ равно 0,1, в значениях полезности, как правило, преобладает немедленная награда за состояние. Например, если мы стоим в точке s = 8 и смотрим вокруг, два соседних состояния s = 4 и s = 9 оба имеют значение полезности очень близко к -0,0444. Не совсем понятно, какой из них лучше. Это проблема недальновидности: когда мы игнорируем будущее и смотрим только на немедленную награду, эти два состояния кажутся одинаково хорошими. Напротив, когда γ равно 0,9, значения полезности имеют тенденцию включать состояния в далеком будущем. Теперь полезность s = 4 составляет 5,4953, а полезность s = 9 — 4,0850. Совершенно очевидно, что s= 4 является лучшим последующим состоянием.

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

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

Используя тот же подход Монте-Карло для оценки этих оптимальных политик, соответствующих разным значениям γ, мы можем обнаружить, что их эффективность близка.

Для γ, равного 0,1, 0,5 и 0,9, после 10 000 повторных прогонов среднее общее вознаграждение составляет 0,63, 0,68 и 0,70 соответственно, с разницей около 11%. Однако минимальные общие награды совсем другие: -6,04, -3,68 и -1,6. Это означает, что наихудший сценарий γ = 0,1 намного хуже сценария γ = 0,9. Следовательно, в этой задаче предпочтительнее большее значение γ, поскольку оно обеспечивает как более высокое среднее, так и более высокое минимальное общее вознаграждение.

Тем не менее, у всего есть цена. Чем больше γ, тем лучше результаты в этой задаче, но за это приходится расплачиваться большими вычислительными затратами. В этих трех случаях, хотя все они требуют от 4 до 5 итераций политики, для γ, равного 0,9, требуется до 60 циклов за один проход, а для γ, равного 0,1, требуется менее 4 циклов за один проход. Большее значение γ требует большего количества разверток и, следовательно, требует больше вычислительного времени.

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

Псевдокод итерации политики

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

Для оценки политики мы используем пороговое значение θ в качестве критерия остановки. Когда изменения значений полезности между двумя развертками меньше этого порога, мы называем это конвергенцией.

Для улучшения политики в выходные данные мы включаем двоичную переменную, указывающую, есть ли какие-либо изменения при обновлении политик. Если после улучшения политика остается прежней, эта бинарная переменная выводится как false.

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

Реализовать итерацию политики в Python

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

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

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