Хотя я бы порекомендовал вам сначала прочитать эту статью. Если вы хотите сразу перейти к примеру с Python, посетите здесь.

Самые простые случаи обучения с подкреплением можно представить с помощью набора состояний и действий. Я объясню это на наглядном примере. Допустим, вы играете в такую ​​игру, как Flappy Bird, но с тремя элементами управления: вы можете идти «вверх», «вниз» или «оставаться посередине». Чтобы играть в эту игру, давайте создадим среду. Для простоты мы создаем матричную диаграмму для определения нашей Env:

На изображении выше у нас есть сетка 3x5, где первый столбец — это начальная позиция для птицы (отмечена синим цветом), а последний столбец — это выигрышная точка (кроме 1-й строки). У нас есть трубы (отмечены красным) в случайных местах сетки, которых птица должна избегать, чтобы выиграть игру.

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

Чтобы математически представить приведенную выше сетку и игру, нам понадобится набор переменных, а именно — состояния (S), действия (A), политика (pi) и вознаграждения (R).

В нашем случае состояния — это ячейки сетки. У нас есть сетка 3*5 и, таким образом, всего 15 состояний. Действия, которые мы можем предпринять, просты: в каждом случае в следующем столбце сетки мы можем либо перейти вниз, остаться всередине, либо перейти в top (как показано на рисунке). Таким образом, состояния S=›{0,1,…,15} и действия A=›[‘вверх’, ‘посередине’, ‘вниз’].

Награды

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

Политика

Политика формально определяется как отображение состояний в действия.

Политика похожа на «руководство» или «карту», ​​которая говорит нам, какие действия следует предпринять в определенном состоянии. Это наиболее важный аспект проблемы обучения с подкреплением. Когда мы говорим, что агент научился решать задачу, мы обычно имеем в виду, что он изучил оптимальную политику или «руководство по навигации» для каждого отдельного состояния в среде, т.е. агент знает, какое действие предпринять в каждом отдельном состоянии. где он может существовать. Чтобы найти оптимальную политику, мы должны сначала узнать, насколько хорошо определенное состояние и полезно ли переход в это состояние в долгосрочной перспективе или нет. Здесь в игру вступает функция ценности.

Значение Функция

Функция значения — это одно скалярное значение, которое существует для каждого состояния в среде. Он количественно определяет состояние или, говоря простыми словами, говорит нам, насколько полезно находиться в определенном состоянии, совершая определенные действия. Математически это можно определить как:

Цель здесь состоит в том, чтобы найти оптимальное значение для каждого состояния, чтобы знать, следует ли посещать определенное состояние или нет. Это значение будет определять политику для агента. Чтобы понять это, рассмотрим сетку оптимальных значений для каждого состояния:

Очевидно, что чем ниже отрицательные значения, тем больше агент должен избегать этого состояния. В нашем примере с игрой Flappy — это состояния с препятствиями, которые приведут к провалу задачи (если их коснуться). Таким образом, политика говорит нам предпринимать действия таким образом, чтобы не только немедленное вознаграждение было высоким, но и чтобы агент достиг своей цели (общее высокое вознаграждение/доход). Поиск оптимальной функции ценности является основой большинства методов обучения с подкреплением.

Конечный MDP и оптимальная оценка политик

Большинство простых вещей, которые мы делаем в жизни, — это марковские процессы принятия решений, также известные как MDP. Проблема называется марковским процессом решения, если она соответствует свойству Маркова.

Неформально свойство Маркова говорит нам, что будущие состояния и действия агента зависят только от текущего состояния и предпринятого действия, а не от прошлой истории агента.

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

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

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

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

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

Для выполнения оценки политики и итерации значения используется следующий алгоритм:

Я постараюсь разобрать это для вас. Сначала мы инициализируем массив или матрицу для V, функцию значений для хранения значений всех состояний s=>S. Затем мы определяем переменную Δ и присваиваем ей значение 0.

V(s) даст нам общий ожидаемый доход/вознаграждение всей задачи от следующего состояния s’ до последнего конечного состояния. Этот процесс выполняется рекурсивно для создания зависимости между различными состояниями.

Затем мы определяем правило обновления для V(s) для каждого состояния в наборе состояний. Это делается с помощью уравнения Беллмана:

В этом уравнении p(s’,r|s,a) — это вероятность достижения состояния s’ и вознаграждения r при текущем состоянии s и действии a. Переменная гамма является коэффициентом дисконтирования. Мы умножаем это на старую функцию значения. Это делается для того, чтобы снизить будущие вознаграждения до более низкого значения, а немедленные вознаграждения — до более высокого значения. Чтобы получить более формальное определение и вывод этого уравнения, обратитесь к этой книге.

Это правило обновления выполняется несколько раз, пока V(s) не сойдется к оптимальному значению для всех s=›S и всех действий a=›A. Мы останавливаем цикл, когда разница между старым значением V и новым очень мала (задается последней строкой). Это дает нам функцию оптимального значения, которая, в свою очередь, дает нам наилучшую политику.

Краткое содержание

Процесс решения МДП идет в следующем порядке:

  1. определить вознаграждение, состояния, действия и другие переменные среды.
  2. инициализируйте политику и функцию значения 0 или None или фиктивным значением.
  3. повторить несколько эпизодов
  4. во время каждого эпизода обновляйте V(s) с помощью уравнения Беллмана, которое будет использовать значение V предыдущей итерации состояния V(S’) рекурсивным образом. (Подробнее см. в этой книге).
  5. останавливать цикл при сходимости (когда разница между новыми и старыми значениями очень мала)
  6. обновить массив политик действиями, соответствующими функции оптимального значения для каждого состояния.

Чтобы понять это на примере кода, ознакомьтесь со второй частью этой статьи — https://medium.com/@manikantan.srinivasan2001/reinforcement-learning-basics-solving-a-finite-mdp-using-python-61f2c0d96bb0

Подробности по математике см. в этой книге — https://www.andrew.cmu.edu/course/10-703/textbook/BartoSutton.pdf