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

Часть 1 | "Часть 2"

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

Чтобы помочь нам в этом процессе, давайте познакомимся с простой страной под названием gridworld.

В gridworld есть 14 состояний без завершения, а серые поля обозначают цели или конечные состояния. Возможны четыре действия: вверх, вниз, влево, вправо. Если в результате действия агент уходит за пределы сетки, он вообще не двигается, но все равно получает награду за свое действие. Вознаграждение отрицательное для каждого перехода, пока не будет достигнуто конечное состояние, в результате чего функция ожидаемого вознаграждения r (s, a, s ') = -1 для всех состояний s, s ' и действия a.

Мы будем использовать gridworld как своего рода средство для перевода динамического программирования в ... настоящее программирование.

Чтобы оптимизировать нашу политику, мы должны с чего-то начать. Мы вычисляем функцию ценности для определенной фиксированной стартовой политики (которая не является оптимальной). Затем мы улучшаем политику, используя одноэтапный просмотр вперед с функцией результирующего значения. Мы повторяем это до тех пор, пока политика не превратится в оптимальную. Этот процесс называется оценка / улучшение политики. Первый шаг этого процесса, оценка политики, может быть написан на Python следующим образом:
(Строка документации помогает объяснить использование среды gridworld OpenAI)

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

Когда у нас есть функция значения для этой политики случайного запуска, мы можем использовать ее для поиска лучших политик. Хитрость заключается в том, чтобы выполнить другое действие a в s, а затем следовать существующей политике π. Если значение выполнения этого конкретного действия в этом конкретном состоянии больше, чем существующее значение состояния, то определяется, что выбор действия a встречается каждый раз, когда s, а затем следование существующей политике было бы улучшением политики. Это можно выразить как:

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

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

Функция ценности, когда она сформирована в виде сетки нашего мира, выглядит так:

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

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

Возвращаясь к Части 2, в этом заключается разница между итерацией по уравнению ожидания Беллмана для нахождения функции значения для данной политики и повторением по уравнению оптимальности Беллмана для нахождения функция оптимальной стоимости… среди всех политик. Работает аналогично. Вы начинаете с начальных значений, просматриваете пространство состояний, а затем выполняете синхронное резервное копирование, обновляя функцию значения в каждом пространстве состояний во время каждой итерации, перестраивая функцию значения и, в конечном итоге, приближаясь к v⁎ . Приведенная ниже диаграмма должна показаться вам знакомой, поскольку на самом деле это уравнение оптимальности Беллмана, преобразованное в правило итеративного обновления.

Реализация этого алгоритма итерации значений в Python показывает небольшую разницу между итерацией политики и итерацией значения.

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

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

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

Ресурсы

Обучение с подкреплением: введение Саттон и Барто

Курс RL Дэвида Сильвера на YouTube

Подборка ресурсов / упражнений пользователя Github dennybritz