Модуль 12. Среда, награда, политика¶

Чему вы научитесь в этом модуле

Записывать задачу в виде марковского процесса принятия решений: состояния, действия, награда, переходы.
Читать формулу отдачи и объяснять, что делает дисконт \(\gamma\) и почему он должен быть строго меньше единицы.
Отличать ценность состояния от награды и формулировать уравнение Беллмана словами.
Прогонять value iteration вручную и наблюдать, как ценность распространяется от цели, а из неё складывается политика.
Объяснять, почему закон эффекта Торндайка и оперантное обусловливание — это по сути тот же марковский процесс, сформулированный за сто лет до его математической записи.

Время: около двух недель. Пререквизиты: модуль 4 (понимание градиента и шага обновления понадобится в модуле 14). Ноутбук: открыть в Colab · notebooks/12-environment-reward-policy.ipynb

Зачем нужен этот модуль¶

Части I–III были посвящены предсказанию: по входу — ответ, по тексту — следующий токен. Обучение с подкреплением — про совершенно другое: действовать. Агент не получает правильных ответов — он получает награду за последствия своих действий и должен самостоятельно разобраться, что делать.

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

Цикл агента и среды¶

Всё обучение с подкреплением сводится к одному циклу. Агент, находясь в некотором состоянии, выбирает действие; среда отвечает новым состоянием и наградой; агент выбирает снова.

Четыре понятия, которыми это описывается строго, — марковский процесс принятия решений (MDP):

Состояние \(s\) — где агент находится в данный момент. Действие \(a\) — что он может предпринять. Награда \(r\) — число, которое среда выдаёт за совершённый переход. Переход — правило, по которому из состояния \(s\) при действии \(a\) получается новое состояние \(s'\).

Слово «марковский» несёт в себе одно конкретное требование: будущее зависит только от текущего состояния, но не от того, каким путём агент в него попал. Если для принятия решения нужна история — значит, историю необходимо включить в описание состояния.

Отдача и дисконт¶

Награда за один шаг — это близорукая цель. Агент, который гонится исключительно за \(r_{t+1}\), съест конфету сейчас и пропустит обед через час. Правильная цель — отдача (return), то есть сумма всех будущих наград:

\[G_t = r_{t+1} + \gamma\, r_{t+2} + \gamma^2 r_{t+3} + \dots = \sum_{k=0}^{\infty} \gamma^k\, r_{t+k+1}\]

Коэффициент \(\gamma \in [0, 1)\) — дисконт. Он определяет, насколько агент ценит будущее: награда, полученная через \(k\) шагов, входит в цель с весом \(\gamma^k\). Вот как выглядят эти веса при \(\gamma = 0.9\):

Зачем нужно \(\gamma < 1\). Во-первых, без этого условия на бесконечном горизонте сумма наград разошлась бы — цель стала бы бесконечной для всех стратегий, и сравнивать их было бы невозможно. Во-вторых, дисконт кодирует нетерпение: награда сейчас ценнее той же самой награды в будущем. Значение \(\gamma\), близкое к единице, даёт дальновидного агента; значение, близкое к нулю, — агента, который живёт одним шагом.

Ценность и уравнение Беллмана¶

Награда описывает один переход. Ценность описывает всё будущее из данного состояния.

Ценность состояния \(V(s)\) — это ожидаемая отдача при старте из \(s\) и последующем действии в соответствии с политикой. Именно в этом заключается разница между «сколько дали прямо сейчас» и «насколько хорошо находиться в этом состоянии».

Ключевое свойство ценности — она рекурсивна. Ценность состояния равна награде за следующий шаг плюс дисконтированная ценность того состояния, в которое приведёт этот шаг. Для оптимального поведения это записывается как уравнение Беллмана:

\[V(s) = \max_a \Big[ r(s, a) + \gamma\, V(s') \Big]\]

Прочитайте словами: ценность клетки — это лучшее, что можно получить за один шаг, плюс дисконтированная ценность той соседней клетки, куда этот шаг ведёт. Уравнение связывает ценность каждого состояния с ценностями его соседей, и на этой связи держится всё, что пойдёт дальше.

Ценность и политика вручную¶

Уравнение Беллмана можно непосредственно использовать как правило пересчёта, применяя его итеративно до тех пор, пока значения не перестанут меняться. Это алгоритм value iteration: каждый проход обновляет ценность каждой клетки на основе ценностей её соседей.

Ниже — мир из клеток: цель \(+1\) в правом верхнем углу, яма \(-1\) под ней, две стены. За каждый шаг агент платит \(-0.03\), чтобы у него не было стимула бродить бесцельно. Нажимайте «Шаг» и наблюдайте, как ценность распространяется от цели наружу, а стрелки жадной политики складываются в маршрут — в обход ямы и стен.

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

Теперь сдвиньте \(\gamma\) к нулю. Ценность далёких клеток сжимается практически в одно и то же значение: далёкая награда \(+1\), обесцененная множителем \(\gamma^k\), до них едва доходит, и остаётся лишь одна плата за шаг. Градиент в сторону цели виден только в непосредственной близости от неё — агент становится близоруким. Дальновидность регулируется одним числом.

Торндайк и закон эффекта¶

А теперь — обещанное: тот же формализм, но за сто лет до его математической записи.

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

Переведите это на язык нашего модуля. Ситуация — это состояние. Нажать рычаг или метнуться в угол — это действия. Еда — это награда. «Закрепляется» — значит, ценность данного действия в данном состоянии возрастает. Это оперантное обусловливание Скиннера, и это же — обновление ценности в MDP. Психология описала процесс словами, математика — формулой, и описали они одно и то же.

Одна модель, две науки. Закон эффекта Торндайка — это уравнение Беллмана до всякой математики. В модуле 13 совпадение станет ещё более поразительным: сигнал ошибки предсказания награды, который мы выведем как алгоритм, окажется тем самым, что в 1997 году обнаружили в дофаминовых нейронах. Редкий случай, когда алгоритм предсказал нейробиологию, а не наоборот.

Различие тоже важно назвать честно. У Торндайка нет дисконта и нет модели переходов — кошка не планирует на пять шагов вперёд. Оперантное обусловливание — это RL без модели среды, ближе к методам, которые появятся в модуле 14, чем к value iteration из этого модуля. Совпадает суть — обучение действию по его последствиям, — а не каждая деталь реализации.

Практическая часть¶

Часть 1. Работа с ноутбуком¶

Откройте notebooks/12-environment-reward-policy.ipynb. Только numpy и matplotlib, вычисления мгновенны.

Что содержится внутри:

Gridworld как объект: состояния, действия, переходы, награда — в двадцать строк кода.
Value iteration с нуля. Карта ценности и стрелки политики — те же, что в интерактивной фигуре выше, но вычисленные программно.
Как \(\gamma\) меняет решение: агент стоит между близкой малой наградой и далёкой большой. Ниже определённого порога он хватает ближайшую, выше — проявляет терпение ради далёкой. Находим порог экспериментально, и он совпадает с аналитическим расчётом.
Закон эффекта на числах: агент в одном состоянии с двумя доступными действиями, ценность каждого действия обновляется по получаемой награде. Поведение смещается в сторону вознаграждаемого действия — закон Торндайка в пяти строках кода.
Проверка сходимости: value iteration сходится, потому что оператор Беллмана является сжимающим отображением. Наблюдаем, как максимальное изменение ценности между проходами убывает с каждой итерацией.

Часть 2. Собственная среда¶

Придумайте маленькую задачу из своей жизни и запишите её как MDP.

Выпишите состояния, действия, награду и правила переходов. Что здесь удовлетворяет марковскому свойству, а что требует учёта истории?
Что вы назначили наградой — и не окажется ли так, что модель будет оптимизировать не совсем то, что вы имели в виду? Запишите это опасение: в модуле 16 оно станет центральной темой.
Задайте значение \(\gamma\) и объясните словами, дальновидный у вас получился агент или близорукий.
Если количество состояний невелико — прогоните value iteration из ноутбука на своей задаче.

Задание¶

Выведите, почему при \(\gamma < 1\) и ограниченных наградах отдача всегда конечна. Достаточно одной строки с суммой геометрической прогрессии.
Реализуйте value iteration и постройте график того, как максимальное изменение ценности убывает от прохода к проходу. Это и есть сжатие из пункта 5 ноутбука.
Меняйте \(\gamma\) от 0.3 до 0.99 и постройте зависимость: при каком значении агент переключается с близкой малой награды на далёкую большую. Объясните найденный порог.
Замените плату за шаг с \(-0.03\) на \(0\) и на \(-0.2\). Что изменилось в маршруте агента и почему?
Сформулируйте эпизод Торндайка (кошка в ящике) как MDP и покажите, что обновление ценности действия воспроизводит «закрепление» без единого слова из психологии.

Проверка усвоения¶

Назовите четыре составные части MDP. Что означает слово «марковский»?
Чем награда отличается от ценности?
Что делает дисконт \(\gamma\) и что происходит с целью, если \(\gamma\) равен единице?
Прочитайте уравнение Беллмана словами, не называя ни одной буквы.
Почему в value iteration ценность появляется сначала рядом с целью, а не сразу везде?
Почему политика — это «тень ценности»?
Как закон эффекта Торндайка соотносится с MDP и в чём он от него отличается?

Что дальше¶

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

Обучение с подкреплением — это один цикл: состояние, действие, награда, новое состояние. Ценность описывает всё будущее, награда — один шаг, а политика — тень ценности.

Принцип

Агент не получает правильных ответов — только награду за последствия. Что вы назначили наградой, то он и будет добывать, включая тот случай, когда это не совсем то, что вы имели в виду.