Обучение с подкреплением. Уравнение Беллмана в C++.
В следующей статье я кратко расскажу об основной концепции обучения с подкреплением, уделяя особое внимание уравнению Беллмана, которое считается фундаментальным уравнением в этой области. Мы будем играть в упрощенную игру-лабиринт на C++, мой код вы найдете здесь.
Обратите внимание, что следующая статья не исчерпывает обсуждаемую проблему, но дает вам хорошее начало для понимания принципа (интуиции) и SW. Я также указал некоторые ценные ссылки, с которыми я считаю чрезвычайно важным ознакомиться, если вы хотите углубиться в эту чрезвычайно увлекательную область.
Концепция обучения с подкреплением
Обучение с подкреплением является неотъемлемой частью машинного обучения (МО), которое определяет агента (робота, машину, процесс и т. д.) и среду (место, где агент выполняет определенные действия). Среда представлена состояниями — набором переменных, которые полностью описывают среду. Агенты могут иметь или не иметь доступ к фактическому состоянию среды. Набор переменных, которые агент воспринимает в любой момент времени, называется наблюдением.
Агент в каждом состоянии взаимодействует со средой, может выполнять определенные действия (например, двигаться влево, двигаться вправо, останавливаться или двигаться вперед) — в соответствии с политикой — которые могут быть связаны со стратегией агент решает, какое действие предпринять в определенном состоянии. Мы можем рассматривать политику как мозг агента.
Агент взаимодействует со средой (выполняя определенные действия) получает, агент получает от среды награды (которые могут быть положительными или отрицательными).
Целью агента, когда агент взаимодействует с окружающей средой, является максимизация совокупного вознаграждения, называемого отдачей. «Мозг» агента узнает о действиях, которые необходимо предпринять для достижения этой цели. Это основной принцип RL .
Агент, выполняющий действия, воздействует на среду, которая реагирует на действие агента, переводя агента из одного состояния в другое. Функция, отвечающая за этот переход, называется функция перехода. Все вместе действия, состояния, функция перехода и вознаграждения определяют марковские процессы принятия решений (MDP), фундаментальную структуру RL.
Пожалуйста, рассмотрите рисунок ниже, который дает вам общее представление о том, как вышеприведенные концепции включены в стек RL.
Марковский процесс принятия решений
Как мы обсуждали в предыдущем абзаце, фундаментальная структура RL напрямую связана с Марковским процессом принятия решений (причинно-следственным процессом).
Рассмотрим агента, который пытается достичь цели. Выполняя действия, агент переходит между состоянием и обучением («мозгом»). Под обучением мы подразумеваем, что агент изучает политики (как выполнять действие в определенном состоянии, чтобы максимизировать совокупное вознаграждение).
Пока агент взаимодействует с окружающей средой, агент сам обнаруживает оптимальную политику (стратегию). ) как достичь поставленной цели. Нам не нужно программировать действия агента. Мы поставляем только алгоритм, который определяет, как агент взаимодействует с окружающей средой. Существует значительный диапазон алгоритмов RL, выбор которых зависит от приложения, среды, политики, которой должен следовать агент, цели и т. д. Помимо огромного количества применимых алгоритмов, все они основаны на уравнении Беллмана
Среда, в которой действует агент, определяется (как вы уже знаете) набором переменных. Здесь мы можем назвать это: состояние среды в определенное время, действие, которое может предпринять агент, вознаграждение и переход. Для заданных переменных мы можем определить MDP, граф состояний агента, переходы (между состояниями) и определенные «условия» для этих переходов. Можно сказать (см. рисунок ниже), что агент с вероятностью 0,8 перейдет в состояние B. Из состояния B агент может перейти в состояния C и D с той же вероятностью, равной 0,3. Из состояния C или D агент с вероятностью 1,0 может перейти только в состояние B и т. д.
Коэффициент дисконтирования, скорость обучения, коэффициенты исследования.
Когда мы обсуждаем обучение с подкреплением, важно учитывать текущие факторы, которые можно настроить.
Коэффициент скидки для вознаграждений, которые агент получает за выполнение действий. По сути, этот фактор определяет, насколько агент заботится о вознаграждении в отдаленном будущем по сравнению с вознаграждением в ближайшем будущем. Если γ=0, это означает, что агент предпочитает получить вознаграждение раньше, чем позже. Объяснение этого явления связано со случаем неопределенности будущего вознаграждения, которое может получить агент. Математически это выражается гаммой коэффициента дисконтирования, который экспоненциально затухает со временем.
Скорость обучения считается насколько (как фактор) агент принимает новое значение состояния по сравнению со старым значением.
Эпсилон-фактор, который напрямую соответствует дилемме разведка — эксплуатация. Эпсилон-фактор определяет, как агент принимает решение. Агент вычисляет первое случайное число (равное или меньше 1,0), если это число больше эпсилон-фактора, агент следует подходу исследование — агент выбирает случайное действие. Агент исследует окружающую среду и имеет шанс «обнаружить» возможности для достижения цели.
С другой стороны, если вычисленное случайное число меньше эпсилон-фактора, агент следует эксплуатации и выбирает действие на основе полученных знаний. В этом случае агент выбирает «лучшее действие».
Подход уравнения Беллмана
Мы понимаем, что цель агентов — найти оптимальный путь к цели. Взаимодействуя с окружающей средой, агент изучает политику (стратегию), чтобы добиться успеха (максимизировать вознаграждение, которое агент может получить от среды). Как вы помните, у агента в каждом состоянии среды есть набор действий на выбор. Политику (стратегию) можно рассматривать как функцию сопоставления состояния с действием агента.
Функция значения состояния
Когда агент изучает политику, наиболее важным для агента является оценка значения состояния, которое указывает, «насколько хорошо» для агента находиться в определенном состоянии с политикой 𝜋. Как вы помните, агент пытается максимизировать общее вознаграждение (доход). Функция возврата, которая не является функцией состояния или действия, зависит только от времени и коэффициента дисконтирования.
Теперь мы можем объединить эти два компонента (значение состояния и вознаграждение) и определить следующую функцию сопоставления (помимо упомянутой выше политики), называемую функция значения состояния, которая определяет значение значения состояния. s, когда агент следует политике 𝜋. Обычно функция значения состояния измеряет, насколько хорошо для агента находиться в этом состоянии.
Функция «действие-значение» (Q-функция)
Помимо того, что агент может оценить значение состояния, агент также должен знать о принятии правильных действий a в состоянии s в соответствии с политикой 𝜋. Функция значения состояния, которую мы определили выше, помогает различать значение каждого состояния в среде, однако она не предоставляет механизмов для оптимального действия агента.
Мы вводим функцию значения действия, который указывает, насколько хорошо для агента выполнять действие a в конкретном состоянии s с политикой (стратегией) 𝜋. Функция «действие-ценность» также известна как Q — функция.
Уравнение Беллмана
Следуя статье «стратегия», основанной только на интуиции, мы можем сказать, что уравнение Беллмана — это уравнение, которое рекурсивно вычисляет функции состояние-значение и действие-значение. Имея эти два значения, агент может следовать оптимальной политике к цели. Это означает, что агент всегда будет принимать наилучшее решение, чтобы перейти в состояние с наибольшей отдачей.
Наконец, уравнение (без описания утомительного процесса вывода) должно быть сформулировано следующим образом (это уравнение реализовано в коде C++). Чтобы понять, как происходит обновление Q-функции, взгляните на реализацию.
Агент обучается и запускает игру. Реализация C++
Я решил реализовать уравнение Беллмана на C++ (код здесь). Для простоты агент находит решение в стандартной задаче о лабиринте. Определяем окружение — лабиринт: матрица 4х4, 6х6 или другого размера (в моем репозитории есть эти два варианта). Каждое место в лабиринте рассматривается как состояние агента. Цель агента — изучить политику, чтобы найти оптимальный путь от старта к цели, минуя препятствия (дыры). Вы можете свободно настроить расположение начала, цели и отверстий. Когда агент выбирает действие, которое переводит его в дыру, агент получает отрицательное вознаграждение -1. Процесс обучения можно наблюдать на терминале (Linux), но у вас должна быть установлена библиотека Eigen.
git clone https://gitlab.com/libeigen/eigen.git sudo ln -s /usr/include/eigen3/Eigen /usr/local/include/ /usr/include/eigen3/Eigen -- location of your clone library
Вы можете работать без Eigen, но вы должны прокомментировать код, в котором используются матрицы Eigen.
Вы можете настроить обсуждаемые параметры по своему усмотрению. Надеюсь код понятен.
Я действительно рекомендую следующую книгу, которая уникальна:
