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

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

Оглавление:

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

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

Пересмотрите итерацию политики

В итерации политики мы итеративно чередуем оценку политики и улучшение политики. При оценке политики мы сохраняем политику неизменной и обновляем утилиту на основе этой политики.

При улучшении политики мы сохраняем полезность неизменной и обновляем политику на основе этой утилиты.

Тогда весь процесс итерации политики

Мы начинаем с любой произвольной политики π₁, получаем ее полезность v₁ путем оценки политики, получаем новую политику π₂ из v₁ путем улучшения политики, получаем полезность v₂ из π₂ по оценке политики, … до тех пор, пока мы не сойдемся на нашей оптимальной политике π*.

Здесь каждая полезность определяется как полезность определенной политики. Например, политика π₁ имеет связанную с ней полезность v₁, политика π₂ имеет связанную с ней полезность v₂, …, а политика πᵢ имеет связанную с ней полезность vᵢ.

Что, если мы определим полезность как полезность политики optima?

Другими словами, можем ли мы определить полезность π* непосредственно в одном процессе, не беспокоясь о чередовании оценки и улучшения?

Уравнение Беллмана

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

Поскольку теперь полезность определяется как связанная с политикой optima, v(s′) уже является лучшим, что мы можем получить после достижения этого состояния s′. Другими словами, если мы решим перейти к s′, в будущем может быть несколько путей, следующих за s′, но v(s′) определяется как результат наилучшего пути среди всех этих возможных путей.

Теперь мы стоим в состоянии s и нам нужно выбрать действие из [a₁, a₂, …]. Давайте посмотрим, что будет, если мы выберем a₁. Если мы имеем в виду a₁, мы знаем возможные результаты и, следовательно, ожидаемые вознаграждения.

Это справедливо для выбора любого возможного действия aᵢ.

Среди всех этих возможных действий, какое мы должны выбрать? Мы должны выбрать действие, которое дает нам наибольшую полезность состояния. Другими словами, среди всех возможных aᵢ мы должны выбрать aᵢ с наибольшим значением v(s|а=аᵢ). По определению это значение полезности равно v(s), потому что это лучший результат, который мы можем получить после достижения состояния s.

Поэтому,

Это называется уравнением Беллмана в честь Ричарда Беллмана и является ключом к решению MDP. Другими словами, решить MDP — это решить уравнение Беллмана. Итерация политики, о которой мы говорили в предыдущей истории, — это один из методов ее решения: чередование оценки и улучшения. Другой метод решения уравнения Беллмана называется итерация значения, при котором полезность оценивается напрямую. Давайте посмотрим, как мы можем реализовать итерацию значений в нашем примере гирд-мира.

Итерация значения

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

Подобно тому, как мы это делали в итерации политики, мы начинаем с инициализации полезности каждого состояния как нуля и устанавливаем γ равным 0,5. Что нам нужно сделать, так это перебрать состояния, используя уравнение Беллмана.

Начнем с s = 0,

Опять же, мы используем процедуру на месте, что означает, что теперь всякий раз, когда мы видим v(0), оно равно −0,04 вместо 0. Перейдем к s = 1, у нас есть

После того, как мы повторим это для состояний 2, 3, … вплоть до 11, мы получим эту утилиту.

Теперь пришло время повторить итерацию, начиная с s = 0 до s = 11.

И повторить снова,

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

По сравнению с итерацией политики, итерация значения также работает, потому что она включает операцию max во время итерации значения. Поскольку мы выбираем максимальную полезность на каждой итерации, мы неявно выполняем операцию argmax, чтобы исключить неоптимальные действия и приблизиться к оптимальному действию.

Получите оптимальную политику

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

Если мы сравним полезности, полученные с помощью итерации значений, с утилитами, полученными с помощью итерации политики, мы обнаружим, что полезности очень близки. Как мы обсуждали ранее, эти утилиты являются решениями уравнений Беллмана. Итерация политики и итерация значения — это всего лишь два альтернативных метода решения уравнений Беллмана. Следовательно, для одного и того же МДП с одними и теми же уравнениями Беллмана, вне зависимости от метода, мы должны получить одни и те же результаты. На практике, из-за таких различий, как критерий остановки в алгоритмах итерации политик и итераций значений, мы получаем немного разные результаты.

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

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

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

Подобно количеству разверток при оценке политики во время итерации политики, в итерации значения большее γ требует большего количества итераций. В нашем примере, когда γ равно 0,1, требуется всего 4 итерации, чтобы изменение значения полезности, которое обозначается как Delta, стало меньше 0,001. Напротив, требуется 11 итераций, когда γ равно 0,5, и 67 итераций, когда γ равно 0,9. Так же, как и в итерации политики, большее γ дает лучшие результаты, но требует дополнительных вычислений.

Псевдокод итерации значения

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

Реализовать итерацию значений в Python

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

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

От MDP к обучению с подкреплением

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

На первый взгляд, MDP кажется очень полезным во многих аспектах реальной жизни. Не только простые игры, такие как Pac-Man, но и сложные системы, такие как фондовый рынок, могут быть представлены в виде MDP (например, цены в виде состояний, а покупка/удержание/продажа в виде действий). Однако есть большое препятствие: мы не знаем ни функции вознаграждения, ни переходной модели. В конце концов, если бы мы каким-то образом узнали функцию вознаграждения MDP, представляющего фондовый рынок, мы могли бы очень быстро стать миллионерами или миллиардерами. В большинстве случаев реального MDP мы не можем получить доступ ни к функции вознаграждения, ни к переходной модели.

Используя нашу игру Pac-Man в нашей первой истории MDP в качестве аналогии, реальная жизнь похожа на игру Pac-Man, не зная правила или карты игры. Как будто мы стоим в тумане.

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

Другими словами, MDP, о котором мы здесь говорили, полностью наблюдаема, а реальная жизнь — нет. Такие методы, как итерация политик и итерация значений, могут решить полностью наблюдаемую MDP. Напротив, если функция вознаграждения и переходная модель неизвестны, именно здесь подходит машинное обучение. Поскольку мы не знаем функцию вознаграждения и переходную модель, нам нужно каким-то образом обучитьсяиспользуя такие методы, как обучение с подкреплением. Мы перейдем к обучению с подкреплением в будущих историях. Следите за обновлениями!