Обучение с подкреплением. Q-обучение. Понятное объяснение

Это моя первая статья на Хабре. Открыт к любой критике.

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

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

Что такое "обучение с подкреплением" ?

Обучение с подкреплением - подход к обучению нейронных сетей (возможно, не только их, но я рассматриваю обучение с подкреплением только в контексте нейронных сетей), когда нейросеть сама учится выполнять задачу. Причем изначально эта задача никак не ставится. Алгоритм может только выполнять какие-то действия и получать за эти действия награду (или штраф). Это подобно естественному обучению человека (или любого другого животного) без учителя, когда субъект выполняет какие-то действия и запоминает, приносят ли эти действия комфорт или дискомфорт. Например, однажды прикоснувшись к горячему чайнику, вы запомнили, что это действие приносит дискомфорт (или "штраф"), и более стараетесь избегать прикосновений к горячим предметам.

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

Формализуем задачу

Что необходимо сделать

Субъект, который будет принимать решения, назовем агентом. Агент будет взаимодействовать с некоторой средой. Эта среда в ответ на очередное действие агента будет давать ему награду (какое-нибудь число). Задача агента - построить такую стратегию, которая будет приводить к максимальной награде за какой-нибудь промежуток времени (этот промежуток будем называть эпизодом). То есть, для успешного обучения нашего агента, нам необходимо с одной стороны построить грамотную систему награждений - штрафов, а с другой - придумать алгоритм, который будет обучать агента действовать с единственной целью - набрать максимальное количество награды за эпизод.

Марковский процесс принятия решения

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

- множество состояний, в которых может находиться среда. Состояние среды $s \in S$ - это то, на основании чего наш агент будет принимать решение. Иными словами, это входные данные нашего агента;
- множество действий, которые может совершить агент;
$P: S \times A \rightarrow S$ - функция переходов, задающая следующее состояние среды после того, как в состоянии $s \in S$ было выбрано действие $a \in A$ . То есть, состояние среды в следующий момент времени $s_{t+1} = P(s_t, a_t)$ ;
$R: S \times A \rightarrow \mathbb{R}$ - функция награды, задающая полученную награду после того, как в состоянии $s \in S$ было выбрано действие $a \in A$ . То есть, награда, полученная за выполнение действия .

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

Пару слов о марковских процессах

В общем случае функция может иметь случайный характер и поэтому уместнее говорить не о функции, а о некоторой зависимости распределения вероятностей $\mathbb{P}(s,a)$ , которая будет задавать вероятность наступления любых доступных состояний среды при выборе действия в состоянии . Если для этой зависимости характерно марковское свойство (то есть, знание о прошлом системы $s_{t-1}, a_{t-1}, s_{t-2}, a_{t-2}, \: ...$ никак не влияет на распределение $\mathbb{P}(s_t,a_t)$ в текущем состоянии ), то данная система в некотором смысле "хорошая". Например, если рассматривать самый банальный случай, когда у нас нет множества действий , а есть лишь множество состояний и распределение вероятностей $\mathbb{P}(s)$ , задающее вероятности переходов между состояниями, то всю эту систему можно описать матрицей переходов. Матрица переходов - матрица, - й столбец которой является распределением вероятностей переходов из - го состояния во все остальные. То есть, $\mathrm{P}_{ij} = \mathbb{P}_i(s_j)$ - вероятность перейти из состояния в состояние . Понятно, что тогда $\textstyle \sum_i{\mathrm{P}_{ij}} = 1$ . Если нам известно распределение вероятностей для состояния, то найти распределение для $s_{t+1}$ можно простым умножением вектора распределения на матрицу $\mathrm{P}_{ij}$ . К данному выводу можно прийти, если рассуждать, каким образом получается распределение для следующего состояния. Например, если у нас есть 2 состояния: и и мы знаем вероятности переходов между ними, то для того, чтобы, например, узнать вероятность попасть в состояние находясь в за 2 перехода, мы должны сложить вероятности переходов $s_0 \rightarrow s_0 \rightarrow s_0$ и $s_0 \rightarrow s_1 \rightarrow s_0$ . Вероятности этих слагаемых будут определяться произведением соответствующих более мелких переходов. То есть, мы получим выражение :

$\mathbb{P} (s_0 \rightarrow \rightarrow s_0) = \mathbb{P} (s_0 \rightarrow s_0) \cdot \mathbb{P} (s_0 \rightarrow s_0) + \mathbb{P} (s_0 \rightarrow s_1) \cdot \mathbb{P} (s_1 \rightarrow s_0)$

А это есть ничто иное, как запись 1-й строчки результата умножения матрицы на вектор изначального распределения (распределения вероятностей переходов их состояния во все остальные):

$\begin{pmatrix} \mathbb{P}(s_0 \rightarrow s_0) & \mathbb{P}(s_1 \rightarrow s_0) \\ \mathbb{P}(s_0 \rightarrow s_1) & \mathbb{P}(s_1 \rightarrow s_a) \end{pmatrix} \cdot \begin{pmatrix} \mathbb{P}(s_0 \rightarrow s_0) \\ \mathbb{P}(s_0 \rightarrow s_1) \end{pmatrix}$

В случае более сложного процесса, когда $\mathbb{P}$ будет зависеть еще и от выбранного действия, для каждого $a \in A$ будет своя матрица переходов. А в целом, логика остается похожей.

Окей, я понял, что такое марковские процессы. А бывают ли вообще немарковские процессы?

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

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

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

Видно, что не выполняется марковское свойство. С другой стороны, мы можем просто добавить дополнительных состояний: первое состояние - вчера вытащили белый кубик, а сегодня черный, второе - вчера вытащили черный, а сегодня белый, и, наконец, третье - и вчера, и сегодня вытащили черные кубики. То есть, в текущее состояние мы включили всю прошлую историю. Теперь процесс, очевидно, будет обладать марковским свойством.

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

$\sum_t {R(s_t, a_t)} \rightarrow \mathrm{max}$

Учитывая, что поведение агента в среде можно выразить некоторой функцией стратегии: $\pi: S \rightarrow A$ , ставящей в соответствие каждому состоянию среды определенное действие агента, наша задача:

$\sum_t {R_{a_t = \pi(s_t)}(s_t, a_t)} \rightarrow \mathrm{max}$

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

Q-обучение

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

$Q_t(s_i,a_j) = \mathrm{max}\left [ \sum_{\tau = t+1} {R_{a_\tau = \pi(s_\tau)}(s_\tau, a_\tau)} \right ]$

где - временные отсчеты, - порядковые номера состояний и действий. То есть, функция полезности показывает максимально возможную сумму награды, которую мы можем получить за все последующие действия, если в состоянии $s_{it}$ выберем действие $a_{jt}$ . Тогда функция стратегии будет:

$\pi_t(s_t) = a_t = \mathrm{ItoE}_A\left ( \underset{j}{\mathrm{argmax}} (Q_t(s_i,a_j)) \right )$

где $\mathrm{ItoE}_A()$ - возвращает элемент по индексу из множества A. То есть, $a_i = \mathrm{ItoE}_A (i)$ , а

$\mathrm{argmax()}$ - индекс максимального элемента

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

Теперь необходимо понять, каким образом можно подобраться к истинному значению этой функции.

Для функции полезности будет выполняться следующее соотношение:

$Q_t(s,a) = \underset{j}{\mathrm{max}}\left [ \:Q_{t+1}(s_i,a_j) \right ]+ r_t$

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

Данное соотношение дает нам возможность итеративно подбираться к истинному значению функции полезности.

Почему оно дает возможность подбираться к истинной функции полезности?

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

Наблюдение достаточно занятное. В действительности, это соотношение будет определяющим функции полезности только в том случае, если мы задаем явное условие для конца нашего эпизода (например, таковым может быть нулевое значение функции в конце эпизода). Привести доказательства этого факта я не могу, но приведу простую иллюстрацию. Рассмотрим случай, когда такое условие не задано. Для простоты будем рассматривать самый тривиальный случай - когда есть всего 2 действия, а эпизод состоит из 2-х действий. Тогда все возможные траектории можно выразить двоичным деревом. Пусть изначально мы выбрали действие, значение функции для которого 1000. После выполнения действия мы получили +5 и перешли в следующее состояние. Далее, в соответствии с приведенным ранее соотношением максимальное значение функции для других возможных действий 1000 - 5 = 995.

Видно, что для всех возможных траекторий выполняется соотношение, и в данном случае выбирая максимальное значение функции на каждом шаге мы пойдем по оптимальной стратегии - соберем максимальную награду (5+4=9).

Но так как у нас не задано конечное условие (конечные значения функции не одинаковые), то мы можем сделать вот так:

Мы подменили узлы и сохранили соотношение, но функция полезности уже не функция полезности - выбирая на каждом шаге действия, соответствующие максимальному значению функции мы уже не будем следовать оптимальной стратегии. Вместо изначальной награды 9 мы соберем всего 5+1=6.

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

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

Причем тут нейросети?

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

Решение о действии агента будет принимать нейросеть. Соответственно, на вход она принимает состояние среды , а на выходе выдает значения Q-функции. Получается, что если у агента возможных действий, то и выходов нейронной сети тоже будет ;
В зависимости от выхода нейросети, мы совершаем действие, которому соответствует наибольшее значение выхода. Кроме этого, крайне желательно, чтобы с некоторой долей вероятности выполнялось случайное действие для того, чтобы агент изучал среду. Каждый сделанный шаг, предыдущее и текущее состояния среды и полученную награду мы записываем в память, чтобы потом сформировать из этого набора данных выборку;
Далее обучаем нейросеть методом обратного распространения ошибки, взяв целевыми значениями выходов $Q_{target_{i}} = \underset{j}{\mathrm{max}}\left [ \:Q_{t+1}(s_i,a_j) \right ]+ r_t$ . Функция потери формируется на всех шагах из эпизода. Например, такой может быть среднеквадратичная ошибка: $\textstyle loss = \frac{1}{N}\sum_i^N{ \left [ Q_{{target}_i} - Q_i \right]^2 }$

Нейросеть играет в змейку

Попробуем применить все это на практике. Использую Pytorch. Код самой игры (среды) я взял у henniedeharder (snake_env). Весь мой код можно найти тут.

Состояние среды представляется в виде 12-мерного вектора с флагами. Флаги определяют позицию яблока и стен относительно змейки. Возможные действия змейки - пойти вперед, вправо, вниз и влево. Соответственно, выходов у нейросети будет 4.

Награду я немного модифицировал, теперь:

Змейка съела яблоко: +60
Змейка умерла: -100
Расстояние между змейкой и яблоком сократилось: +50
Расстояние между змейкой и яблоком увеличилось: +25

Используем простейшую архитектуру - перцептрон с одним скрытым слоём:

def __init__(self, LearningRate=0.01, Epsilon=0.3):

        super().__init__()

        # Слои
        self.inp = nn.Linear(12, 1024)
        self.hidden1 = nn.Linear(1024, 1024)
        self.out = nn.Linear(1024, 4)
        
        # Инициализация слоев
        init.uniform_(self.inp.weight, -1, 1)
        init.uniform_(self.hidden1.weight, -1, 1)
        init.uniform_(self.out.weight, -1, 1)

        
        # Память
        self.memory_states = []
        self.memory_actions = []
        self.memory_rewards = []
        self.memory_next_states = []
        self.memory_isdones = []
        self.memory_len = 0
        self.loses = []
        self.rewards_per_epoch = []

        self.optimizer = optim.Adam(self.parameters(), lr=LearningRate)
        self.criterion = nn.MSELoss()
        self.epsilon = Epsilon
        self.activation = nn.LeakyReLU()

Обучение:

def train_snake(self):
        if (self.memory_len == 0):
            return
        memory_len = self.memory_len
        states, actions, rewards, next_states, isdones = self.samplebatch()

        NeuroNowAnswer = self.forward(states)
        NeuroNextAnswer = self.forward(next_states)
        predicted_now_value = NeuroNowAnswer[range(memory_len), actions]
        predicted_future_value = t.max(NeuroNextAnswer, dim=1)[0]
        predict_target = rewards + predicted_future_value*isdones
        loss = self.criterion(predict_target, predicted_now_value)
        self.loses.append(loss.cpu().item())
        self.rewards_per_epoch.append(t.sum(rewards.cpu()).item())
        self.optimizer.zero_grad()
        loss.backward()
        if (self.inp.weight.grad.norm() < 0.0001):
            self.inp.weight.grad.data += t.FloatTensor([0.001]).cuda()
        self.optimizer.step()
        print(f"Ошибка: {loss}")

Запускаем, немного ждем и:

Не похоже на то, что агент играет в змейку. Да, он научился не врезаться и сразу не умирать (я установил лимит максимум на 100 шагов). Но почему он не ест яблоко? Потому что у него мало мотивации выходить из своей "зоны комфорта". Мы и так за каждый ход поощряем его 25-ю или 50-ю баллами. Вот он и научился просто ходить по полю и не умирать. Исправить это дело может коррекция системы наград. Давайте теперь за ход в направлении, увеличивающем расстояние до яблока, забирать у агента 25 баллов (награда -25), а за съедание яблока давать 100 баллов:

Теперь агент начал играть.

В коде при действиях объекта я выводил текущие значения выхода нейросети, и заметил нечто странное:

tensor([-0.3429, -0.3077, -0.6071, -0.4754], device='cuda:0',
       grad_fn=<LeakyReluBackward0>)
tensor([-0.3332, -0.2352, -0.5149, -0.3973], device='cuda:0',
       grad_fn=<LeakyReluBackward0>)
tensor([-0.3332, -0.2352, -0.5149, -0.3973], device='cuda:0',
       grad_fn=<LeakyReluBackward0>)
tensor([-0.3332, -0.2352, -0.5149, -0.3973], device='cuda:0',

Значения выходов совсем не похожи на приближенные значения функции полезности. Мало того, они вообще отрицательные! Почему это вообще работает?

Ранее я упомянул некоторую особенность используемого подхода: "Оптимальная стратегия может быть выведена не из конкретной функции полезности". Так и произошло. Фактические значения можно интерпретировать как некоторое приближение (достаточно точное, потому что агент научился играть) к функции плюс какая-то константа. В данном случае эта константа получилась отрицательной. Вероятно, значения весов для ряда функций, задающих искомую оптимальную стратегию, в некотором смысле похожи, поэтому в ходе градиентного спуска мы наткнулись на другую функцию, задающую ту же стратегию, что и истинная функция полезности (точнее, приближение к этой функции).

Небольшое улучшение

Мы применяли простое рекуррентное соотношение, при помощи которого искали стратегию, максимизирующую суммарную награду за эпизод:

$\sum_t {R(s_t, a_t)} \rightarrow \mathrm{max}$

Как показывает практика, более эффективным является подход, в котором максимизируется другая сумма:

$\sum_t {\beta^t R(s_t, a_t)} \rightarrow \mathrm{max},\: \beta \lt 1$

где $\beta$ - коэффициент дисконтирования. Фактически, он задает обесценивание награды с течением времени. То есть, с этим коэффициентом агент будет стараться собрать больше награды в начале эпизода. Рекуррентное соотношение тогда запишется следующим образом:

$Q_t(s,a) = \beta \:\underset{j}{\mathrm{max}}\left [ \:Q_{t+1}(s_i,a_j) \right ]+ r_t$

Если использовать этот коэффициент, то агент научиться играть в змейку даже при старой системе наград. Уменьшим лимит на максимальное число шагов за эпизод (теперь 1000) и посмотрим, что получится:

Агент опять научился играть в змейку. Только теперь обучение произошло быстрее и эффективнее.

Источник: https://habr.com/ru/articles/789218/

Вернуться к списку

Интересные статьи

Машинное обучение помогает классическому моделированию квантовых систем

Используя «классические тени», обычные компьютеры могут превзойти квантовые компьютеры в сложной задаче понимания квантового поведения. Понять квантовую вселенную — задача непростая. Интуитивные ...

Геолоцировать пользователя по Tweet-у: машинное обучение, часть I

Модели машинного обучения давно тренируются на постах в соцсетях. Самые большие текстовые корпусы созданы на основе Твиттера — они обогащают тысячи компаний сервисами, а библиотеки — академическими ст...

Стучимся в дверь к Тьюрингу: квантовые компьютеры и машинное обучение

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

Анонс книги «Машинное обучение без лишних слов»

Привет, Хаброжители! Готовится к сдаче в типографию полноцветная новинка «Машинное обучение без лишних слов» #1 in Data Mining #2 in Programming Algorithms #3 in Machine Theory Эту кн...

Книга «Машинное обучение: алгоритмы для бизнеса»

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