Что такое обучение с подкреплением и как алгоритм RL работает на практике?
В 2014 году Google приобрел британский стартап DeepMind за полмиллиарда долларов. Дорогая цена, но инвестиции, похоже, окупились во много раз только благодаря той рекламе, которую генерирует DeepMind. Исследователи машинного обучения знают DeepMind за частые прорывы в области глубокого обучения с подкреплением. Но компания также привлекла внимание широкой публики, особенно благодаря своим успехам в создании алгоритма игры в го. Учитывая частоту, с которой DeepMind добивается прогресса в этой области - AlphaGo, AlphaGo Zero и AlphaZero за последние пару лет - становится трудно отслеживать, что именно происходит, как на техническом уровне, так и с точки зрения последствий. . Я планирую сделать именно это - дать общее представление об успехах DeepMind в Go и объяснить различия между различными версиями AlphaGo, которые они создали.
Что такое RL?
Машинное обучение - это область, которая созрела для сравнений с человеческим познанием. Конечно, это не совпадение. Многие из самых популярных задач в этой области (зрение, речь и обработка естественного языка), как правило, были областью человеческого (или естественного) интеллекта. Поскольку «то, что» алгоритм делает, имитирует людей, естественно думать о том, «как» алгоритм работает, также как и подражая людям. Отсюда обилие утверждений вроде «Нейронные сети вдохновлены человеческим мозгом» (по правде говоря, это утверждение так же верно, как «Самолеты вдохновлены птицами»)
Обучение с подкреплением особенно подходит для таких сравнений. По сути, любая задача обучения с подкреплением определяется тремя вещами - состояниями, действиями и наградами. Состояния - это представление текущего мира или среды выполнения задачи. Действия - это то, что агент RL может делать для изменения этих состояний. А вознаграждение - это полезность, которую получает агент за выполнение «правильных» действий. Таким образом, состояния сообщают агенту, в какой ситуации он находится в настоящее время, а награды сигнализируют состояниям, к которым он должен стремиться. Таким образом, цель состоит в том, чтобы изучить «политику», что-то, что говорит вам, какие действия следует предпринять в каждом состоянии, чтобы попытаться максимизировать вознаграждение. Это широкое определение можно использовать для множества разнообразных задач, которые мы выполняем каждый день.
Когда вы едете, состояние - это положение и скорость вашего автомобиля и соседних автомобилей. Вы можете выполнять такие действия, как поворот рулевого колеса и нажатие педали газа или тормоза. Награда зависит от того, насколько быстро вы доберетесь до пункта назначения при соблюдении правил дорожного движения.
Когда вы играете в видеоигру (скажем, в The Legend of Zelda), состояние - это любая информация, отображаемая на экране - ваше местоположение, присутствие ближайших персонажей или монстров, оружие и предметы, которыми вы владеете. Ваши действия могут включать движение или нападение. Ваша награда зависит от количества оставшихся у вас жизней и любых денег или предметов, которые вы получаете от победы над врагом.
Давайте посмотрим на более абстрактный пример - поступление в аспирантуру. Ваше состояние - это ваш текущий исследовательский / рабочий профиль, а также имеющаяся у вас информация о программах и преподавателях в разных школах. Возможно, вы решите, к кому обратиться за рекомендательным письмом, на что надеть SoP и в какие школы подать заявление. Наградой, конечно же, является письмо о принятии (или отрицательное вознаграждение из-за письма с отказом).
Эти примеры показывают, что часто можно сформулировать множество задач на разных уровнях конкретности в терминах настройки обучения с подкреплением. Однако важно отметить, что объем состояния, действия и набора наград может сильно отличаться для разных задач. Например, действие, установленное в игре Zelda, хоть и обширно, но явно на порядок меньше, чем действие, установленное для поступления в аспирантуру. Это говорит о том, что представление задач как обучения с подкреплением хорошо работает, когда вы четко определили состояния, награды и ограниченные наборы действий. Это видно по типам задач, в которых RL успешно справляется.
Решение задач RL
Один из распространенных подходов к решению задач RL называется «ценностно-ориентированным». Мы пытаемся присвоить номер каждому состоянию (или каждой паре (состояние, следующее действие)) в зависимости от того, какие состояния могут привести к высоким вознаграждениям. Этот объект, связывающий каждое состояние с определенным числовым значением, называется функцией значения. Если мы изучим подходящую функцию значения таким образом, то из определенного состояния мы можем просто выбрать действие, которое, вероятно, приведет к следующему состоянию с высоким значением. Итак, мы свели нашу задачу к проблеме изучения этой функции ценности.
Чтобы понять, как может выглядеть этот процесс обучения, давайте рассмотрим более конкретный пример - крестики-нолики. Состояние - это текущая позиция на доске, действия - это разные места, в которые вы можете поместить X или O, а награда составляет +1 или -1 в зависимости от того, выиграете вы или проиграете игру. Пространство состояний - это общее количество возможных состояний в конкретной настройке RL. Крестики-нолики имеют достаточно маленькое пространство состояний (одна разумная оценка - 593), поэтому мы можем фактически запомнить значение для каждого отдельного состояния, используя таблицу. По этой причине этот метод называется табличным. Это непрактично для большинства приложений (представьте, что вы перечисляете все возможные конфигурации шахматной доски и присваиваете значение каждой из них), но я вернусь к тому, как с этим справиться позже.
Мы начинаем с присвоения некоторых начальных значений каждому состоянию, скажем, 0 для всех состояний (есть лучшие стратегии инициализации, но пока это подойдет). Итак, изначально наша таблица выглядит так (допустим, у нас есть способ нумерации или индексации состояний):
Затем мы начинаем играть в игры в крестики-нолики против оппонента, следуя общему правилу, согласно которому действие, предпринимаемое в текущем состоянии, ведет к следующему состоянию с как можно более высоким значением. Вначале, поскольку все состояния имеют равные значения, это означало бы просто случайный выбор из набора допустимых ходов. Но после нескольких игр вы замечаете, что, достигнув этой позиции (вы - «X»):
Вы получаете награду +1. Тогда значение, связанное с этим конечным состоянием, должно быть +1. Итак, вы обновляете свою таблицу (скажем, окончательная выигрышная позиция имеет произвольный индекс 123):
Теперь, в следующих нескольких играх, вы увидите, что позиции, которые приведут вас к 123 (скажем, это 121 и 122 соответственно), также могут закончиться с высокой наградой, если вы сделаете правильный ход:
Итак, вы снова обновляете таблицу, отмечая, что это предпоследнее состояние не обязательно дает полную награду +1, поскольку все еще возможно сделать неправильный ход и закончить с проигрышем или ничьей:
Я не буду вдаваться в фактические задействованные уравнения, но на высоком уровне мы видим, что награда как бы «перетекает» в обратном направлении от конечного (конечного) состояния и дает конкретное значение состояниям, которые к нему приводят. . Таким образом, эти конечные состояния чрезвычайно важны для обеспечения того, чтобы алгоритм учил правильную функцию значения. Однажды у меня была ошибка, из-за которой все работало, как ожидалось, кроме флага, указывающего на эти состояния терминала, и в итоге алгоритм почти ничего не узнал.
Итак, при наличии достаточного количества тренировочных игр награда будет возвращаться к самым первым состояниям, и у вас будет хорошая стратегия от начала до конца! Например, один из распространенных способов выполнения этой начальной загрузки, когда значение одного состояния узнается из значений состояний, следующих сразу за ним, называется Обучение временной разнице.
Расширение до шахмат
Насколько хорошо эта стратегия работает, скажем, в шахматах? Крестики-нолики имеют около 600 состояний. Хотя в шахматах сложно подсчитать точное количество состояний, хорошей верхней оценкой кажется 10⁴⁵. На всех компьютерах мира не хватает памяти для хранения такого количества состояний, поэтому помещать все значения в таблицу - не лучшая идея. Как мы справляемся с этой проблемой?
Давайте подумаем, мы играем в шахматы. По мере того, как мы больше практикуем, мы начинаем интуитивно понимать, насколько «хороши» определенные состояния. Например, попробуйте оценить это состояние (белые играют):
Вы, наверное, можете сказать, что у белых лучшая позиция. Скорее всего, вы никогда раньше в жизни не видели такого точного состояния доски. Тем не менее, у вас есть интуиция относительно того, что составляет «доброту» государства в шахматах. Вы, вероятно, посчитали количество фигур, которые остались у каждой стороны, и заметили, что, хотя у черных есть 2 лишние пешки, у белых есть лишние конь и ладья, дающие этой стороне преимущество. Если вы более опытный игрок, вы могли бы изучить возможные следующие ходы (например, белый слон может взять черного слона) и участки доски, контролируемые каждой стороной.
Таким образом, вы определенно не запоминаете потенциальную ценность каждой возможной шахматной позиции - вы изучили некую общую функцию, отображающую состояние доски на ценность игры для каждого игрока. Это именно то, что мы хотели бы, чтобы интеллектуальный шахматный алгоритм для RL выполнял также идею, называемую приближение функции ценности.
Во-первых, мы выясняем способ представления игрового состояния. Для крестиков-ноликов мы могли просто перечислить все состояния, что означает, что каждое игровое состояние было представлено одним числом. В шахматах один простой способ сделать это - представить каждую фигуру числом (пешка → 1, ладья → 2…), а затем иметь список длиной 64, который кодирует наличие определенной фигуры в каждой позиции (с, скажем, 0 для пустых позиций). Мы могли бы передать это в функцию значения, которую изучил наш алгоритм RL, и она выдаст число (представляющее «значение») или, возможно, вероятность (представляющую шанс на победу черных).
Фактическая часть RL очень похожа на то, что мы делали для крестиков-ноликов. Мы играем во множество игр, награждаем алгоритм за победу и наказываем его за проигрыш, и со временем (надеюсь) он научится хорошей функции, представляющей ценность состояния. Единственное изменение заключается в том, что вместо поиска значения в таблице мы передаем вход через нашу функцию и получаем соответствующее значение в качестве выхода. Имея это, мы можем вывести политику игры в шахматы, посмотрев, какого состояния мы достигли бы, сделав каждый возможный ход, и пропустив каждое из этих состояний через нашу функцию, чтобы увидеть, какое из них имеет наибольшее значение!
Это был довольно наивный способ решения шахматной задачи с помощью RL, и есть несколько сложных идей, которые мы можем использовать для ускорения вычислений, улучшения обучения и, в конечном итоге, для улучшения ходов. Это будет особенно важно в случае Го, где пространство состояний для игры даже больше, чем для шахмат! Наверное, все это потребовало большого внимания, поэтому я остановлюсь на этом и обсудим некоторые из этих интересных идей в контексте Go в следующем сообщении в блоге. Спасибо за прочтение!
Первоначально опубликовано на https://deepakdilipkumar.github.io 3 марта 2018 г.
