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

Примечание: эта статья изначально была размещена на веб-сайте Луки Палмьери по адресу https://www.lpalmieri.com/posts/rl-introduction-00/ и была размещена здесь с его разрешения. Этот пост является частью серии из трех статей, посвященных обучению с подкреплением, которые мы настоятельно рекомендуем вам прочитать!

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

Все началось в мае 2016 года: компьютерная программа AlphaGo, разработанная Google, выиграла 4 игры в го (из пяти) у Ли Седола, действующего чемпиона мира (см. Статью Guardian о матче здесь).

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

Тем не менее, нам удалось найти свой путь в этом огромном лабиринте возможностей, установив новую веху для ИИ раньше, чем ожидалось. Как Google этого добился?

Объединение глубокого обучения и обучения с подкреплением в одной из самых популярных лабораторий искусственного интеллекта в мире - DeepMind, купленной Google в 2014 году за 400 миллионов долларов.

Неудовлетворенные, они улучшили свои собственные результаты, выпустив AlphaGoZero в октябре 2017 года (ссылка) и AlphaZero в декабре 2017 года (ссылка) - быстрый спойлер: AlphaGo в определенной степени использовала некоторую эвристику, обученную людьми; его дети со сверхспособностями распоряжаются всем, что связано с людьми.

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

Вероятно, мне понадобится 6 или больше сообщений, чтобы хотя бы начать касаться интересных и тонких способов, найденных исследователями для объединения глубокого обучения и обучения с подкреплением до того, как AlphaGo появилась на свет.

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

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

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

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

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

Что ж, мы можем прекратить любезности и, наконец, приступить к работе!

Основные идеи

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

Примеров множество:

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

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

Если наша цель в задаче кубика Рубика состоит в том, чтобы найти кратчайшую последовательность действий, ведущих к решению, тогда мы можем просто смоделировать состояние окружающей среды как массив из 6 матриц 3x3, по одной для каждой грани куба, где каждая запись соответствует первая буква соответствующего цвета плитки.

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

Немного другие цели, существенно разные формулировки.

Обозначим через 𝑺 множество возможных состояний нашей системы. Для простейшей постановки задачи кубика Рубика имеем:

Мы будем обозначать через 𝑨 (𝑠) набор действий, доступных агенту, если текущее состояние системы равно 𝑠 ∈ 𝑺 - я не буду формализовать пространство действий в корпус кубика Рубика. Кубики Рубика милые, простые, и все их знают, но я не слишком о них забочусь, чтобы не вспотеть - не обижайтесь на профессионалов Рубика.

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

Мы всегда будем предполагать, если не указано иное, что время дискретно: агент имеет возможность выполнить действие для каждого 𝑡 ∈ ℕ = {1,2,…}.

Повторяя эту процедуру, мы получаем траекторию или историю нашего моделирования:

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

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

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

Цель агента - максимизировать общую сумму вознаграждений, которые он собирается собрать.

В нашем примере кубика Рубика, например, мы можем предоставить агенту награду −𝟏, если состояние, следующее за его последним действием, не является решенным кубом, в то время как мы предоставляем + 𝟏 награда, если его последнее действие разобрало куб.

Действительно ли это указывает агенту правильное направление?

Да! Ожидаемое общее вознаграждение нашего агента составляет

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

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

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

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

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

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

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

Вот почему мы рассматриваем систему обучения с подкреплением как случайный процесс - последовательность случайных величин.

Какие случайные величины?

Среда становится полностью известной после того, как мы правильно укажем:

  • вероятность получения вознаграждения 𝑟 в момент 𝑡 + 1, зная историю системы до этого момента:

  • вероятность попасть в состояние 𝑠 в момент 𝑡 + 1, зная историю системы до этого момента:

Мы всегда будем предполагать, что награды являются марковскими - они зависят только от последней пары состояние-действие. Формально:

В большинстве случаев мы предполагаем маркованность также для случайной величины состояния StSt - в этом случае математическая формулировка задачи обучения с подкреплением принимает название Марковский процесс принятия решений (MDP).
Мы собираемся подробно изучить их в течение оставшейся части нашего путешествия.

Как мы уже говорили, среда отвечает за поведение состояний и вознаграждений. агент, напротив, полностью определяется вероятностью принятия действия 𝑎 в момент 𝑡, зная историю системы до этого момента:

для каждого 𝑡 ∈ ℕ.

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

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

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

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

Ссылки и предварительные условия

Большая часть этой серии будет основана на:

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

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

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

Указатель серии обучения с подкреплением

  • Часть 0 (этот пост)
  • Часть 1
  • "Часть 2"
  • Скоро ... Следите за обновлениями на веб-сайте Луки Палмьери, чтобы увидеть последующие публикации https://www.lpalmieri.com/