Q-learning

Привет.

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

В комментариях к прошлой статье поднялся вопрос про reinforcement learning. Почему бы и нет. Давайте подробнее рассмотрим что это такое.

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

Итак, reinforcement learning, или обучение с подкреплением - это такая группа методов машинного обучения, подходы которой сначала выглядят как методы обучения без учителя, но со временем (время обучения) становятся методами обучения с учителем, где учителем становится сама нейронная сеть. Скорее всего, ничего непонятно. Это не страшно, мы все рассмотрим на примере.

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

Наш условный лабиринт

Представляя эту картину, мы можем увидеть все основные составляющие любого проекта с использованием обучения с подкреплением.Во-первых, у нас есть крыса - Агент (agent), наша нейронная сеть, которая мыслит и принимает решения.Во-вторых, у нас есть Окружение или среда (environment) агента - лабиринт, который имеет свое Состояние (state), расположение проходов, мест с котами, финальный островок и так далее. Крыса может принимать решения и совершать определенные Действия (actions), которые могут приводить к разным последствиям. Крыса либо получает Вознаграждение (reward), либо Санкции (penalty or -reward) за свои действия.

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

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

Семейство методов обучения с подкреплением

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

Мы имеем некоторое кол-во состояний (s1, s2 ...), наш агент может находится в одном из этих состояний в каждый момент времени. Цель агента достичь финального состояния.

Пример конечного автомата

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

Но здесь появляется проблема, как только мы начнем изменять кол-во состояний, наша таблица становится бесполезной и мы должны заполнять ее заново. Здесь нам на помощь приходят нейронные сети. Зачем заполнять таблицы? Давайте просто предсказывать значение перехода.

В чем идея? Как нейронные сети нам помогут?

В прошлый раз мы условились, что будем воспринимать нейронные сети как черный ящик для простоты понимания. Давайте не будем нарушать эти условности.

Итак, мы имеем некоторые входные данные и знаем как должны выглядеть обработанные данные. Например, у нас есть картинка котика и мы точно знаем, что это котик. Допустим, у нас 1 000 разных картинок котиков. Мы отдаем это все в наш черный ящик и он возвращает нам некоторый алгоритм того, как определить что на картинке котик.

Получение алгоритма распознавания котиков

Далее, если мы достанем еще несколько картинок котиков, которые отличны от тех 1000 штук, возьмем наш алгоритм, и все это отправим в черный ящик, он вернет нам правильное название для этих картинок, хотя этих картинок нейронная сеть еще не видела. Это нейронные сети 101 (базовый курс).

Распознавание новых котиков

Так вот, с Q-обучением тоже самое. Зная только часть переходов между состояниями таблицы, используя нейронные сети, мы можем предсказывать новые состояния для новой таблицы с максимальным вознаграждением. Поэтому на свет появился Deep Q-learning алгоритм. Deep потому что deep neural networks, глубокие нейронные сети, глубокие - потому что много слоев.

Наверняка появились вопросы или я что-то упустил. Поэтому давайте перейдем к практической части.

Реализация окружения и агента

В этот раз мы также будем использовать р5 редактор, поскольку снова будем делать аркадный проект, поэтому р5 будет незаменим в этом.

Начнем мы с того, что определим наши объектные модели. Самыми главными классами для нас будут класс Environment и класс Agent.

class Agent {  constructor(b, r, s, w, h) {    this.network = b;    this.rect = r;    this.speed = s;    this.width = w;    this.height = h;  }}class Environment {  constructor(w, h, r, c, es, as) {    this.width = w;    this.height = h;    this.rows = r;    this.columns = c;    this.enemySpeed = es;    this.agentSpeed = as;    this.agent = this.resetAgent();    this.eps = Environment.MAX_EPS;    this.discount = Environment.DISCOUNT;  }}

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

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

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

Итак, давайте обозначим, что является состоянием. Я решил выбрать 9 параметров, которые могут изменяться в течение времени:

• положение агента по оси Х

• положение агента по оси У

• наличие врага впереди на оси Х

• наличие врага впереди на оси У

• дистанция до врага по оси Х

• дистанция до врага по оси У

• наличие цели на оси Х

• наличие цели на оси У

• дистанция до цели

Параметры состояния окружения агента

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

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

const ACTIONS = [MOVE_RIGHT, MOVE_DOWN, MOVE_LEFT, MOVE_UP];chooseAction(state, eps) {  if (random(0, 1) < eps) {    return ACTIONS[random([0, 1, 2, 3])]; // рандомный шаг  } else {    return tf.tidy(() => {      // сеть возвращает массив из 4 значений      const probs = this.network.predict(state).dataSync();// шаг с максимальным значением      return ACTIONS[probs.indexOf(Math.max(...probs))];     });  }}

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

Это, так называемый, коэффициент исследования.

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

Почему? Это называется проблемой компромисса исследования и использования (не знаю как правильно перевести exploration-exploition trade-off).

Давайте рассмотрим на примере.

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

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

Вернемся обратно к агенту.

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

update(action) {  switch (action) {    case MOVE_UP:    this.rect.top = this.rect.top - this.speed;    break;    case MOVE_DOWN:    this.rect.top = this.rect.top + this.speed;    break;    case MOVE_RIGHT:    this.rect.left = this.rect.left + this.speed;    break;    case MOVE_LEFT:    this.rect.left = this.rect.left - this.speed;    break;  }}

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

createModel(inputShape) {  const model = tf.sequential();  model.add(tf.layers.dense({ inputShape: [inputShape], units: 36, activation: 'relu' }));  model.add(tf.layers.dense({ units: 36, activation: 'relu' }));  model.add(tf.layers.dropout({ rate: 0.20 }));  model.add(tf.layers.dense({ units: Agent.ACTIONS.length }));  model.compile({ optimizer: 'adam', loss: 'meanSquaredError' });  return model;}

У нас появился необычный слой (5 строка), который называется dropout. Его советуют использовать, если есть возможность того, что нейронка может перетренероваться (явление, когда сеть не предсказывает выходные данные, а просто запоминает связки инпут-аутпут из тренировочных данных). Но также нашел на хабре статью, в комментариях которой говорят, что у этого слоя куда больше применений, хотя их автор не упомянул. Не суть. Что делает этот слой? Он просто игнорирует некоторые нейроны с заданной вероятностью, то есть обнуляет их веса, чтобы те не влияли на ответ.

И вторая строчка, которая нас будет интересовать чуть позже (8 строка), метод компиляции модели. Здесь мы указываем то, как нейронка будет обрабатывать свои ошибки (разницы между предсказанными значениями и теми, которые должны быть). Оставим настройку этих параметров интернету и будем воспринимать их как черный ящик.

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

Обучение агента

Каков наш алгоритм обучения? На самом деле, в интеренете очень много примеров и реализаций DQN алгоритма, в частности на js, но, чтобы понять этот алгоритм мне пришлось потратить пару дней непрерывного чтения различных статей и обрывков книг, чтобы просто прочитать код. Я даже отчаялся и пошел просить помощи на stackoverflow. В итоге я не уверен, что полностью понимаю, что я сделал. Наверное, поэтому и пишу эту статью, но эй! Мы за этим здесь и собрались - учиться на ошибках. Поэтому буду очень рад обратной связи.

Итак, как же мы научим агента искать сыр?

Во-первых, мы разобьем наше обучение на несколько игр, 60-100 должно хватить. Установим кол-во шагов в каждой игре, пусть будет 1000, чтобы игра не шла вечно и агент не крутился на месте. Если агент израсходует свои шаги, игра начинается заново. Если агент натыкается на кота или находит сыр, игра начинается заново. Чтобы мотивировать агента избегать котов и искать сыр введем метод подсчета его вознаграждения и штрафов. За каждый шаг будем бить агента током, мотивируя его быстрее добраться до цели, причем, чем ближе агент к цели, тем меньше он получит разряд (в числах это от -0.2 до 0). Если агент натыкается на кота то умирает и получает -10. Если находит сыр, то его награда +100.

calcReward() {  // находим нормализованную дистанцию до цели (от 0 до 1) и умножаем на -0.2  let reward = distance(  this.agent.rect.left,  this.width,  this.agent.rect.top,  this.height) / distance(0, this.width, 0, this.height) * -0.2;  const agentRect = toRect(this.agent.rect);  const enemiesRects = this.enemies.map(e => toRect(e));  const goalRect = toRect(this.goal);  const intersected = enemiesRects.filter(e => rectsIntersected(e, agentRect));  reward += intersected.length && -10;  if (rectsIntersected(agentRect, goalRect)) reward = 100;  return reward;}

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

В-третьих, соберем все вместе.

Мы инициализируем игру и наше хранилище.

function setup() {  mem = new ReplayMemory();  env = new Environment(450, 300, 4, 6, 4, 2);  createCanvas(...env.dims);}

Реализуем отрисовку всех составляющих игры на каждой итерации игрового цикла.

async function draw() {  CURRENT_STEP++;  background(220);  drawGoal(env.goal);  drawNet(env.net);  drawEnemies(env.enemies);  drawAgent(env.agent.rect);  ...

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

// environmentupdateAgent(STATE = this.getStateTensor()) {  const action = this.agent.chooseAction(STATE, this.eps);  this.agent.update(action);  const nextState = this.getStateTensor();  return [nextState, action, this.isDone()];}

Далее мы считаем награду за шаг агента и добавляем все эти данные в нашу память. Они нам потом понадобятся.

// draw in sketch fileconst [nextState, action, done] = env.updateAgent(STATE);const reward = env.calcReward();mem.append([STATE, action, reward, nextState, done]);STATE = nextState;...

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

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

Теперь к самой реализации. Думаю, я довольно потомил вас в ожидании, вот эта формула - уравнение Беллмана. Что же она нам говорит?

Если попробовать прочитать что тут написано, то получится нечно следующее: одно кольцо, чтоб править всеми максимально возможное вознаграждение (Q) агента в состоянии s равно сумме моментального вознаграждения r за его шаг а и максимально возможноного вознаграждения агента из состояния s помноженное на коэффициент понижения gamma. На слух - это точно эльфийский.

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

Допустим, у нас есть начальное состояние агента s1, далее агент имеет возможность перейти в состояние s2 и s3 при помощи действий (шагов) а1 и а2, после этого вариации выбора еще раз расширяются. И из состояния s2, все еще при помощи а1 и а2, агент может попасть в состояния s4 и s5, а из состояния s3 в состояния s6 и s7. За каждый переход агент будет получать моментальное вознаграждение, ну или штраф, а чтобы посчитать долгосрочное вознаграждение из состояния s1 нам нужно проверить все ветви нашего автомата. Собственно, становится понятно, что max Q для состояния s1 == 99 (-1 + 100), а для состояния s3 == 100 (100 - финальный переход) и логично отсюда вывести, что max Q для s1 равно вознаграждение за переход a2 плюс max Q из состояния, в которое мы попали (s3).

Но что это значит? Это значит, что нам вручную нужно ходить туда-сюда по состояниям и правильно настраивать Q значения - заполнять нашу таблицу, как мы уже поняли. И как мы уже решили, мы не будем этого делать, пусть нейронка сама нам считает эти значения. Поэтому вот так уравнение Беллмана выглядит на javascript.

async function replay() {  let miniBatch = mem.sample(500);  const filtered = miniBatch.filter(Boolean);  // фильтруем если очень мало шагов сделали  if (!filtered.length) return;  let currentStates = filtered.map((dp) => { return dp[0].dataSync() });  // предсказываем Q для каждого текущего состояния s в памяти  let currentQs = await env.agent.network.predict(tf.tensor(currentStates)).array();    let newCurrentStates = filtered.map((dp) => { return dp[3].dataSync() });  // предсказываем Q для каждого состояния s', в которое мы попали из s  let futureQs = await env.agent.network.predict(tf.tensor(newCurrentStates)).array();  let X = [];  let Y = [];  for (let index = 0; index < filtered.length; index++) {    // берем один слайс    const [state, action, reward, newState, done] = filtered[index];    let newQ;    let currentQ;    // уравнение Беллмана    if (!done) {      let maxFutureQ = Math.max(...futureQs[index]);      // находим максимальный Q для следующего состояния (s')       // и складываем с моментальным вознаграждением (r)      newQ = reward + (env.discount * maxFutureQ);    }    // если финальный переход, просто учитываем сам переход    else { newQ = reward }    currentQ = currentQs[index];    // корректируем текущее значение Q на то, которое посчитали    currentQ[action] = newQ;    X.push(state.dataSync()); // 9 параметров нашего состояния    Y.push(currentQ); // массив из 4 значений Q для наших шагов (вправо, вниз, влево, вверх)  }  // учим нашу сеть скорректированными данными  await env.agent.network.fit(tf.tensor(X), tf.tensor(Y), { verbose: 0 });}

Когда мы попадаем в реплай игры мы берем небольшой слайс записей наших шагов.

Мы достаем все стартовые состояния из этих записей. И просим нашу нейронку посчитать значение Q для каждого состояния.

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

Теперь мы считаем разницу между тем, что нам подсказала нейронка и тем, что мы сами посчитали.

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

После этого вызываем специальный метод fit, который помогает нейронке переосмыслить свои шаги с нашими корректировками.

И чуть не забыл, зачем нам вообще нужен коэффициент понижения? Нам нужен еще один пример.

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

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

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

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

Давайте уже запускать симуляцию.

Первые несколько игр Джери тупит в углу либо суицидиться об котов.

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

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

PS. если есть желание поконтрибьютить, welcome to PRs или напишите мне в твиттер: v_hadoocken

Этой весной Питерская Вышка и JetBrains впервые провели проектную смену для старшеклассников Школу по практическому программированию и анализу данных. В течение пяти дней 50 участников со всей страны работали над групповыми проектами по машинному обучению, NLP, мобильной и web-разработке.

Первое место заняла команда Deep Q-Mario ребята создали нейронную сеть, которая использует reinforcement learning для обучения агента играть в Super Mario Bros. В этом посте они рассказывают, какие алгоритмы использовали и с какими проблемами столкнулись (например, в какой-то момент Марио просто отказался прыгать).

О нас

Мы Владислав и Дмитрий Артюховы, Артём Брежнев, Арсений Хлытчиев и Егор Юхневич учимся в 10-11 классах в разных школах Краснодара. С программированием каждый из нас знаком довольно давно, мы писали олимпиады на С++. Однако почти все члены команды раньше не работали на Python, а для написания проекта в короткий пятидневный срок он был необходим. Поэтому первым испытанием для нас стало преодоление слабой типизации Python и незнакомого синтаксиса. Но обо всем по порядку.

Немного теории

На школе Питерской Вышки нам предстояло создать нейронную сеть, которая использует reinforcement learning для обучения агента играть в Super Mario Bros.

Reinforcement Learning

В основе RL алгоритмов лежит принцип взаимодействия агента и среды. Обучение происходит примерно так: агент совершает в среде действие и получает награду (в нашем случае Марио умеет прыгать и перемещаться вправо); среда переходит в следующее состояние; агент опять совершает действие и получает награду; подобное повторяется, пока агент не попадет в терминальное состояние (например, смерть в игре).

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

Q-learning

В основу нашей модели лег алгоритм Q-learning. Q-learning это модель, которая обучает некоторую функцию полезности (Q-функцию). Эта функция на основании текущего состояния и конкретного действия агента вычисляет прогнозируемую награду за весь эпизод (Q-value).Агент совершает действия на основании некоторого свода правил политики. Политика нашего агента называется Epsilon-Greedy: с некоторой вероятностью агент совершает случайное действие, иначе он совершает действие, которое соответствует максимальному значению Q-функции.

# implementation of Epsilon-Greedy Policy:def act(state):rand_float = random.random() # returns random float in range: [0, 1)if rand_float <= EPS:action = random_action()else:action = model.get_action(state) # returns action that brings max Q-valuereturn action

В классической реализации алгоритма Q-learning формируется таблица из всех возможных состояний среды и всех возможных действий. Задача заключается в том, чтобы посчитать значения Q-values для каждой пары состояние действие.

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

Где Q(s, a) значение Q-функции для состояния и действия;

Q_target(s, a) это оптимальное, по нашему предположению, значение Q-функции, к которому мы пытаемся свести текущее значение Q-функции;

s_t, a_t состояние среды и выбранное действие в момент времени $t$;

r_t(s_t, a_t) награда за текущее состояние среды и совершенное действие;

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

коэффициент обучения. Он определяет насколько сильно мы изменим текущее значение Q-функции.

Deep Q-Learning

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

Deep Q-learning

Experience Replay Buffer

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

# implementation of transition collecting:transition = (state, action, next_state, reward, done)replay_buffer.append(transition)  

Target network

Для того, чтобы весь алгоритм обучения работал, необходимо иметь вторую нейронную сеть target model, которая определяет оптимальное значение Q-функции (Q-target) и является копией модели, взаимодействующей со средой (online model). Единственное отличие этих сетей друг от друга заключается в том, что веса target model обновляются несколько реже, чем у online model у нас это примерно каждый 500-й эпизод. Это нужно для корректного обучения модели: если online model будет производить вычисления Q-target и Q-функций самостоятельно, при изменении весов сети следующие значения Q-target и Q-функций изменятся примерно одинаково, то есть разница между ними останется такой же, и мы не будем сводиться к оптимальному значению.

Существуют два метода обновления весов target model: hard update и soft update. Первый копирует online model в target model каждую n-ую итерацию обучения. Во втором методе веса target model также пересчитываются при обучении, но медленнее, как взвешенное среднее весов двух сетей

Работа над проектом

Стоит отметить, что до школы никто из нашей команды не делал проекты по машинному обучению. За несколько недель нам сообщили тему проекта, и мы заранее, еще в Краснодаре, начали готовиться. Мы читали статьи, смотрели видео по машинному обучению и нейронным сетям, изучали математику, которая нам может пригодиться. Поэтому можно сказать, что на смену приехали уже подготовленными. Конечно, мы не знали нюансов, но во время школы наш куратор Дмитрий Иванов каждый день давал задания, благодаря которым мы смогли разобраться с деталями.Первые дни после начала школы мы занимались тем, что изучали необходимую теорию по нейронным сетям и обучению с подкреплением вместе с Дмитрием. После настало время кодинга: первая наша попытка реализовать DQN (Deep Q-learning Network) алгоритм и научить агента играть в Марио успехом не увенчалась. После девяти часов обучения прогресса не было, и мы не знали, в чем, собственно, дело. После тщетных попыток дебаггинга на питоне, командой было принято единственное разумное решение переписать код с нуля, что принесло свои плоды. Имея рабочую реализацию DQN, мы решили на этом не останавливаться, а написать модификацию Dueling DQN, сравнить ее со стандартным алгоритмом и посмотреть, какой агент лучше покажет себя в игре после обучения.

Dueling DQN

Основная идея Dueling DQN заключается в том, что нейронная сеть предсказывает не значения Q для всех действий, а отдельно средневзвешенное значение Q-функции по всем действиям (так называемое V-value), а также преимущества для каждого действия, которые определяются как разность между Q-функцией и средневзвешенным значением (подробнее можно почитать здесь).

Визуализация архитектуры модели Dueling DQN (где-то на просторах интернета)

Дополнительный функционал

Помимо алгоритмов обучения, нам необходимо было сделать еще несколько полезных вспомогательных фич: saver, logger, plotting, visualization.

Saver

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

Logger and Plotting

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

Visualization

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

Возникшие проблемы

На самом деле проблем во время работы над проектом была масса. Бороться с ними команде помогал куратор. Однако одна проблема заставила нас поломать головы над ее решением на определенном этапе вычислений Марио стал упираться в трубы, не пытаясь их перепрыгнуть.

Возникшая проблема с трубами

Мы считаем, что эта особенность поведения связана с тем, что отрицательная награда от исхода времени на прохождение эпизода была меньше, чем отрицательная награда от смерти Марио при ударе с врагом. Другими словами, Марио "считал", что завершить уровень из-за истечения времени для него более предпочтительно, чем смерть.Эта проблема действительно поставила нас в тупик: мы не знали, как заставить агента проходить уровень. Мы бились над решением в течение многих часов, пока Арсений Хлытчиев не придумал модификацию функции награды, названную Punishment-оптимизацией (за что мы всей командой выражаем Арсению благодарность!) Он предложил добавлять отрицательную награду за "простой" Марио, чтобы восстановить значимость передвижения агента вперед по уровню. Это улучшение оказало сильное влияние на поведение агента в среде: Марио больше не застревал перед трубами.

Решение проблемы с трубами

Результаты

К окончанию школы мы получили агента, который неплохо справлялся с частичным прохождением первого уровня игры: Марио сумел пройти около 50%. При этом каждый член команды сумел одолеть Марио, дойдя до второго уровня.

Лучший gameplay Марио

Оба алгоритма DQN и Dueling DQN после обучения проходили примерно равную часть уровня. Но в силу того, что обычный DQN имел больше времени для обучения, его результат был немного лучше.Так как нашей целью было сравнить обычный алгоритм DQN с его модификацией, давайте проанализируем графики, которые мы получили.

Функция потери

DQN (слева) и Dueling DQN (справа)

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

Функция награды

DQN (слева) и Dueling DQN (справа)

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

Заключение

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

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

(Q-learning, SARSA, DQN, DDPG)

Обучение с подкреплением (RL далее ОП) относится к разновидности метода машинного обучения, при котором агент получает отложенное вознаграждение на следующем временном шаге, чтобы оценить свое предыдущее действие. Он в основном использовался в играх (например, Atari, Mario), с производительностью на уровне или даже превосходящей людей. В последнее время, когда алгоритм развивается в комбинации с нейронными сетями, он способен решать более сложные задачи.

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

1. Обучение с подкреплением

Типичное ОП состоит из двух компонентов, Агента и Окружения.

Окружение это среда или объект, на который воздействует Агент (например игра), в то время как Агент представляет собой алгоритм ОП. Процесс начинается с того, что Окружение отправляет свое начальное состояние (state = s) Агенту, который затем, на основании своих значений, предпринимает действие (action = a ) в ответ на это состояние. После чего Окружение отправляет Агенту новое состояние (state = s) и награду (reward = r) Агент обновит свои знания наградой, возвращенной окружением, за последнее действие и цикл повторится. Цикл повторяется до тех пор, пока Окружение не отправит признак конца эпизода.

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

Определения:

1. Action (A, a): все возможные команды, которые агент может передать в Окружение (среду)

2. State (S,s): текущее состояние возвращаемое Окружением

3. Rewrd (R,r): мгновенная награда возвращаемое Окружением, как оценка последнего действия

4. Policy ( ): Политика - стратегия, которую использует Агент, для определения следующего действия (a) на основе текущего состояния среды.

5. Value (V) или Estimate (E) : ожидаемая итоговая (награда) со скидкой, в отличии от мгновенной награды R, является функцией политики E(s) и определяется, как ожидаемая итоговая награда Политики в текущем состоянии s. (Встречается в литературе два варианта Value значение, Estimate оценка, что в контексте предпочтительней использовать E оценка. Прим. переводчика)

6. Q-value (Q): оценка Q аналогична оценки V, за исключением того, что она принимает дополнительный параметр a (текущее действие). Q(s, a) является итоговой оценкой политики от состояния s и действия a

* MCTS (Монте-Карло тайм степ модель), on-policy (алгоритм, где Агент включен в политику, т.е. обучается на основе действий, производных от текущей политики), off-policy (Агент обучается на основе действий, полученных от другой политики

Безмодельные алгоритмы против алгоритмов базирующихся на моделях

Модель предназначена для моделирования динамики Окружения. То есть модель изучает вероятность перехода T(s₁|(s₀, a)) из пары состояния S₀ и действия a в следующее состояние S₁ . Если эта вероятность успешно изучена, то Агент будет знать, насколько вероятно получить определённое состояние, если выполнить действие a в текущем состоянии. Однако алгоритмы, построенные на моделях, становятся непрактичными по мере роста пространства состояний и действий (S*S*A для табличного представления)

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

2. Разбор Алгоритмов

2.1. Q-learning

Q-learning это не связанный с политикой без модельный алгоритм ОП, основанный на хорошо известном уравнении Беллмана:

E в приведенном выше уравнении относится к математическому ожиданию, а - это коэффициент дисконтирования.

Мы можем переписать это уравнение в форме Q-value:

Оптимальное значение Q, обозначенное как Q*, может быть выражено как:

Цель состоит в том, чтобы максимизировать Q-значение. Прежде чем углубиться в метод оптимизации Q-value, я хотел бы обсудить два метода обновления значений, которые тесно связаны с Q-learning.

Итерация политики

Итерация политики представляет собой цикл между оценкой политики и ее улучшением.

Оценка политики оценивает значения функции V с помощью жадной политики полученной в результате последнего улучшения политики. С другой стороны, улучшение политики обновляет политику, генерирующую действия (action a), что максимизирует значения V для каждого состояния (окружения). Уравнения обновления основаны на уравнении Беллмана. Итерации продолжаются до схождения.

Итерация Оценок (V)

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

После того, как итерация сходится, оптимальная политика напрямую выводится путем применения функции максимального аргумента для всех состояний.

Обратите внимание, что эти два метода требуют знания вероятности перехода p, что указывает на то, что это алгоритм на основе модели. Однако, как я упоминал ранее, алгоритм, основанный на модели, страдает проблемой масштабируемости. Так как же Q-Learning решает эту проблему?

Здесь a (альфа) скорость обучения (т.е. как быстро мы приближаемся к цели) Идея Q-learning во многом основана на итерациях оценок (v). Однако уравнение обновления заменяется приведенной выше формулой. В результате нам больше не нужно думать о вероятности перехода (p).

Обратите внимание, что следующее действие a выбирается для максимизации Q-значения следующих состояний вместо того, чтобы следовать текущей политике. В результате Q-learning относится к категории вне политики (off-Policy).

2.2. State-Action-Reward-State-Action (SARSA)

SARSA очень напоминает Q-learning. Ключевое отличие SARSA от Q-learning заключается в том, что это алгоритм с политикой (on-policy). Это означает, что SARSA оценивает значения Q на основе действий, выполняемых текущей политикой, а не жадной политикой.

Уравнения ниже показывают разницу между рассчетом значений Q

Q-learning: Q(s_t,a_t)Q(s_t,a_t)+[r_t+1+maxaQ(s_t+1,a)Q(s_t,a_t)]

SARSA: Q(s_t,a_t)Q(s_t,a_t)+[r_t+1+Q(s_t+1,a_t+1)Q(s_t,a_t)]

Где действие a_t+1 это действие выполняемое в следующем состоянии s_t+1 в соответствии с текущей политикой.

Они выглядят в основном одинаково, за исключением того, что в Q- learning мы обновляем нашу Q-функцию, предполагая, что мы предпринимаем действие a, которое максимизирует нашу Q-функцию в следующем состоянии Q (s_{t + 1}, a).

В SARSA мы используем ту же политику (например, epsilon-greedy), которая сгенерировала предыдущее действие a, чтобы сгенерировать следующее действие, a + 1, которое мы запускаем через нашу Q-функцию для обновлений, Q (s_{t + 1}, a_t+1). (Вот почему алгоритм получил название SARSA, State-Action-Reward-State-Action).

Интуитивно понятно, что SARSA это on-policy алгоритм , потому что мы используем одну и ту же политику для генерации текущего действия в точке и следующего действия в точке +1. Затем мы оцениваем выбранные действия нашей политики и улучшаем их, улучшая оценки Q-функции.

В Q-learning у нас нет ограничений на то, как выбирается следующее действие a, у нас есть только оптимистичный взгляд на то, что все последующие выборы действий a в каждом состоянии s будут оптимальными, поэтому мы выбираем действие a, чтобы максимизировать оценку Q (s_t+1, a). Это означает, что с помощью Q-learning мы можем генерировать данные политикой с любым поведением (обученной, необученной, случайной и даже плохой), при наличии достаточной выборки мы получим оптимальные значения Q

Из псевдокода выше вы можете заметить, что выполняется выбор двух действий, которые всегда соответствуют текущей политике. Напротив, Q-learning не имеет ограничений для следующего действия, пока оно максимизирует значение Q для следующего состояния. Следовательно, SARSA - это алгоритм, действующий в соответствии с политикой (on-policy).

2.3. Deep Q Network (DQN)

Хотя Q-learning - очень мощный алгоритм, его главная слабость - отсутствие общности. Если вы рассматриваете Q- learning, как обновление чисел в двумерном массиве (пространство действий * пространство состояний (action space * state space)), оно фактически напоминает динамическое программирование. Это указывает на то, что для состояний, которые агент Q-Learning не видел раньше, он не знает, какое действие предпринять. Другими словами, агент Q-Learning не имеет возможности оценивать значение для невидимых состояний. Чтобы справиться с этой проблемой, DQN избавляется от двумерного массива, введя нейронную сеть.

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

аваВ 2013 году DeepMind применил DQN к игре Atari, как показано на рисунке выше. Входными данными является необработанное изображение текущей игровой ситуации. Оно проходит через несколько сверхточных слоев, а затем через полно связный слой. Результатом является Q-значение для каждого действия, которое может предпринять агент.

Вопрос сводится к следующему: как мы обучаем сеть?

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

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

Еще два метода также важны для обучения DQN:

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

2. Отдельная целевая сеть: целевая сеть Q имеет ту же структуру, что и сеть, которая оценивает значение. Каждый шаг C, в соответствии с приведенным выше псевдокодом, целевая сеть принимает значения основной сети. Таким образом, колебания становятся менее сильными, что приводит к более стабильным тренировкам.

2.4. Deep Deterministic Policy Gradient (DDPG)

Хотя DQN добилась огромных успехов в задачах более высокой размерности, таких как игра Atari, пространство действий по-прежнему остается дискретным. Однако для многих задач, представляющих интерес, особенно для задач физического контроля, пространство действий непрерывно. Если вы слишком дискретизируете пространство действия, вы получите слишком большой объем. Например, предположим, что степень свободной случайной системы равна 10. Для каждой степени вы делите пространство на 4 части. У вас будет 4 = 1048576 действий. Чрезвычайно сложно получить схождение для такого большого пространства действий, а это еще не предел.

DDPG реализует архитектуру актор-критик с двумя одноименными элементами - актором и критиком. Актор используется для настройки параметра