Обучение с подкреплением: Часть 4: Поиск оптимального решения — Динамическое программирование

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

Мы видели в предыдущем блоге, что

· Используя уравнение Беллмана, мы можем получить N уравнений для решения переменной N, но в реальном мире N может быть огромным (например, в шахматах), и для его вычисления потребуются годы.

· Оптимальная политика не может быть рассчитана с нелинейной настройкой.

Решение — динамическое программирование (DP)!

DP предоставит приблизительное решение, которое быстро обеспечит оптимальное решение.

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

Оценка политики и улучшение политики — это два шага в итеративном процессе решения проблемы обучения с подкреплением.

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

Оценка политики — это процесс определения функции ценности для данной политики. Он включает в себя оценку ожидаемого дохода или ценности каждого состояния при соблюдении определенной политики.

Цель состоит в том, чтобы оценить значение каждого состояния в соответствии с данной политикой.

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

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

· Мы повторяем этот процесс до тех пор, пока значения состояний не сойдутся или не достигнут определенного порога.

· Результирующая функция значения представляет собой оценочное значение каждого состояния в соответствии с данной политикой.

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

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

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

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

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

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

Допущения DP:

· Марковское свойство: MDP предполагает, что будущее состояние системы зависит только от текущего состояния и предпринятых действий, а не от истории предыдущих состояний и действий.

· Конечные пространства состояний и действий: DP предполагает, что и пространство состояний, и пространство действий конечны.

· Известная динамика: алгоритмы DP предполагают, что вероятность перехода и немедленное вознаграждение известны или могут быть точно оценены. Эта динамика описывает вероятность перехода в разные состояния при выполнении определенных действий. Знание динамики имеет решающее значение для обновления функции ценности или политики на этапах оценки политики и улучшения политики.

· Стационарность: DP предполагает, что MDP остается стационарным с течением времени. Это означает, что вероятность перехода и немедленное вознаграждение не меняются в процессе обучения.

Все еще нужно больше?

Итерация значения — еще один вариант достижения оптимальной политики.

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

Итерация ценности позволяет нам объединить оценку политики и улучшение политики в одном шаге.

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

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

Ссылка:

Обучение с подкреплением: введение - Ричард С. Саттон и Эндрю Дж. Барто