Это первая из серии статей, в которой я резюмирую лекции с CS285, проведенные профессором Сергеем Левиным, которому все заслуги. Все изображения взяты из его лекций.
С одной стороны, обучение с подкреплением предлагает математический формализм для разработки алгоритмов, ориентированных на принятие решений на основе обучения. С другой стороны, глубокое обучение предлагает чрезмерно параметризованные модели, которые сопоставляют сложные входные данные с выходными и позволяют нам справляться с неструктурированной и непредсказуемой природой реального мира.
Некоторая терминология обучения с подкреплением. Мы можем представить политику как распределение действий, обусловленное наблюдениями; состояние удовлетворяет марковскому свойству, что означает, что состояние в момент времени t + 1 не зависит от состояния в момент времени t — 1; с другой стороны, наблюдение является некоторой стохастической функцией состояния, которая может содержать или не содержать всю информацию, необходимую для вывода о полном состоянии, и не удовлетворяет свойству Маркова.
В обучении с подкреплением мы определяем цель с помощью так называемой функции вознаграждения: это скалярная функция состояния и действия, хотя иногда она может зависеть только от состояния. Важно отметить, что цель обучения с подкреплением состоит не только в том, чтобы предпринять действия, которые приносят большую награду прямо сейчас, но и в том, чтобы предпринять действия, которые позже приведут к более высокой награде. Вместе состояние, действие, вознаграждение и вероятности перехода определяют то, что мы называем марковским процессом принятия решений. Давайте двигаться к полному формальному определению марковских процессов принятия решений.
- Цепь Маркова имеет очень простое определение: она состоит из множества состояний s и функции перехода t. Пространство состояний — это просто множество, которое может быть либо дискретным, либо непрерывным. Функция перехода обозначает вероятность состояния в момент времени t + 1, обусловленную состоянием в момент времени t.
- Цепь Маркова сама по себе не позволяет нам конкретизировать проблему принятия решений, потому что в ней нет понятия действий. Итак, чтобы перейти к понятию действий, нам нужно превратить цепь Маркова в марковский процесс принятия решений, который добавляет пространство действия и функцию вознаграждения. Пространство действий, как и пространство состояний, также является дискретным или непрерывным множеством. Наши вероятности перехода теперь обусловлены как состояниями, так и действиями, поэтому оператор перехода теперь является тензором, потому что он имеет три измерения: следующее состояние, текущее состояние и текущее действие. Частично наблюдаемый марковский решающий процесс дополнительно дополняет определение двумя дополнительными объектами: пространством наблюдения o и вероятностью испускания e.
Давайте определим цель обучения с подкреплением. Мы будем изучать πθ, где π соответствует политике, а θ соответствует параметрам глубокой нейронной сети, которая действует как политика. Состояние переходит в политику, действие выходит, а затем состояние и действие переходят в вероятность перехода — по сути, физика, управляющая миром, которая порождает следующее состояние. В этом процессе мы можем записать распределение вероятностей по траекториям, которые представляют собой последовательности состояний и действий.
Если мы запишем совместное распределение наших состояний и действий, мы можем разложить его на множители, используя цепное правило в терминах уже определенных нами распределений вероятностей.
У нас есть начальное распределение состояний p(s1), а затем у нас есть произведение по всем временным шагам вероятности действия при заданном s(t) и вероятности перехода к следующему временному шагу s(t+1) при заданном s (t) и а(t). Определив распределение траекторий, мы можем фактически определить цель обучения с подкреплением, и мы можем определить эту цель как ожидаемое значение при распределении траекторий. Цель состоит в том, чтобы найти параметры θ, которые определяют нашу политику, чтобы максимизировать ожидаемое значение суммы вознаграждений по траектории; поэтому нам нужна политика, которая создает траектории с максимально возможным вознаграждением в ожидании, и ожидание, конечно, объясняет стохастичность политики, вероятности перехода и начальное распределение состояний.
Одна из вещей, которые мы могли бы заметить в этой факторизации структурного распределения, заключается в том, что, хотя она определяется в терминах объектов, которые у нас были в марковском процессе принятия решений, ее также можно интерпретировать как цепь Маркова. Для этого нам нужно определить своего рода расширенное пространство состояний. Наше исходное пространство состояний — s, но у нас также есть действия, которые делают этот процесс принятия решений марковским; мы знаем, что действие зависит от состояния, основанного на политике, поэтому политика, заданная состоянием, позволяет нам получить распределение наших действий, обусловленное состояниями. Таким образом, мы можем сгруппировать состояние и действие вместе в своего рода расширенное состояние, и теперь расширенные состояния фактически образуют цепь Маркова:
Таким образом, оператор перехода в этой расширенной цепи Маркова является просто произведением оператора перехода в марковском процессе принятия решений и политики.
Это может позволить нам определить цель немного другим способом, который будет удобно использовать в некоторых из наших более поздних выводов.
Случай конечного горизонта
До сих пор я определял цель как ожидаемое значение при траекторном распределении суммы вознаграждений, но помните, что наше распределение фактически следует цепи Маркова с этим расширенным пространством, и этот оператор перехода является продуктом переходов MDP. и политика. Таким образом, мы могли бы также записать цель по линейности ожидания как сумму ожидаемых значений во времени при маргинале состояния-действия в этой марковской цепи вознаграждения за этот временной шаг.
Это просто использование линейности ожидания, чтобы вывести сумму из ожидания, чтобы у вас была сумма над T ожидания. Затем, поскольку вещь внутри ожидания зависит только от состояния и действия, мы можем исключить все остальные переменные. Это оказывается весьма полезным, если мы хотим распространить это на случай бесконечного горизонта.
Случай бесконечного горизонта
Что произойдет, если T равно бесконечности? Первое, что происходит, это то, что ваша цель может стать нечеткой. Чтобы цель не стала бесконечной, есть несколько способов. Один из способов — использовать формулу среднего вознаграждения: вы берете эту сумму ожидаемых вознаграждений и делите ее на капитал T.
Сделать цель конечной довольно легко, но давайте поговорим о том, как мы можем на самом деле определить цель с бесконечным горизонтом. У нас есть наша цепь Маркова из предыдущего, и наша расширенная цепь Маркова имеет оператор перехода. Это означает, что мы можем записать векторное состояние (t+1), действие (t+1) как некоторый линейный оператор, примененный к состоянию и действию на временном шаге t. В более общем случае мы можем пропустить k временных шагов вперед и сказать, что:
Мы могли бы задать один вопрос: сходится ли маргинал состояния-действия p(s(t), a(t)) к стационарному распределению, когда малое k стремится к бесконечности? Если это так, это означает, что мы должны иметь возможность записать стационарное распределение μ равным t, умноженному на μ — при нескольких технических предположениях, а именно эргодичности (каждое состояние может быть достигнуто из любого другого состояния с ненулевой вероятностью) и поскольку цепочка апериодична, мы действительно можем показать, что существует стационарное распределение.
«Стационарное» означает, что распределение одинаково до и после перехода; если это верно, то применение линейного оператора достаточное количество раз в конечном итоге позволит вам его достичь.
Вы можете найти стационарное распределение, просто перестроив это уравнение, чтобы увидеть, что оно равно:
Один из способов найти μ — найти собственный вектор с собственным значением один для матрицы, определяемой T. Таким образом, μ — это собственный вектор T с собственным значением один, и он всегда существует при предположениях об эргодичности и апериодичности. Если мы знаем, что если запустить эту цепь Маркова вперед достаточное количество раз, то в конце концов она установится в μ, это означает, что по мере того, как t стремится к бесконечности, в этой сумме по ожиданиям маргиналов преобладают члены стационарного распределения. Итак, у вас есть некоторое конечное число членов, которые изначально не находятся в стационарном распределении, но затем у вас есть бесконечно много членов, которые очень и очень близки к стационарному распределению. Это означает, что как только вы введете случай среднего вознаграждения, а затем возьмете предел, поскольку t стремится к бесконечности, предел в основном будет ожидаемым значением вознаграждения при стационарном распределении. Это позволяет нам определить цель обучения с подкреплением в случае бесконечного горизонта, когда t стремится к бесконечности.
Ожидания и стохастические системы
Обучение с подкреплением на самом деле связано с оптимизацией ожиданий, поэтому, хотя мы говорим об обучении с подкреплением с точки зрения выбора действий, которые приводят к высоким вознаграждениям, мы всегда действительно обеспокоены ожидаемыми значениями вознаграждений. Интересная особенность ожидаемых значений заключается в том, что они могут быть непрерывными в параметрах соответствующих распределений, даже если функция, которую мы ожидаем, сама по себе сильно прерывиста. Это действительно важный факт для понимания того, почему алгоритмы обучения с подкреплением могут использовать методы плавной оптимизации, такие как градиентный спуск, для оптимизации целей, которые кажутся недифференцируемыми, таких как бинарные вознаграждения за победу или поражение в игре.
Пример: давайте представим, что вы едете по горной дороге, и ваша награда +1, если вы остаетесь на дороге, и -1, если вы падаете с дороги. Функция вознаграждения здесь кажется прерывистой, и если вы попытаетесь оптимизировать функцию вознаграждения в отношении, например, положения автомобиля, эту проблему оптимизации нельзя решить с помощью методов, основанных на градиенте, потому что вознаграждение не является непрерывная или, тем более, дифференцируемая функция положения автомобиля. Однако, если у вас есть случайная величина Бернулли с параметром θ (с вероятностью θ вы упадете, с вероятностью 1-θ вы не упадете), ожидаемое значение вознаграждения по отношению к πθ равно на самом деле гладкая по θ.
Это очень важное свойство, которое будет возникать снова и снова, и это действительно объясняет, почему алгоритмы подкрепления могут оптимизировать, казалось бы, негладкие и даже разреженные функции вознаграждения: ожидаемые значения негладких и недифференцируемых функций при дифференцируемой и гладкой вероятности. распределения сами по себе гладкие и дифференцируемые.
Функции ценности
Функции ценности — очень полезный математический объект как для разработки алгоритмов обучения с подкреплением, так и для концептуального осмысления цели обучения с подкреплением. Как я упоминал ранее, цель поощрения может быть определена как ожидание суммы вознаграждений по отношению к распределению траекторий или, что то же самое, сумма ожидаемого вознаграждения во времени для каждого предельного состояния-действия. Одна из вещей, которые мы могли бы сделать с этим ожиданием, это то, что мы можем записать его рекурсивно:
Мы можем применить цепное правило и записать ожидаемое значение по отношению к этому распределению в виде ряда вложенных ожиданий. Самое внешнее ожидание здесь будет связано с вероятностью s1; внутри него у нас есть ожидаемое значение относительно a1, распределенное в соответствии с политикой (вероятность a1 при заданном s1). Поскольку у нас есть ожидание как для s1, так и для a1, мы можем ввести первое вознаграждение r(s1, a1) и заметить, что это внутреннее ожидание, то есть ожидание, превышающее a1, обусловлено s1. Мы добавим к этому все остальные вознаграждения, но для этого нужно ввести другое ожидание по s2, распределенное в соответствии с p(s2|s1, a1); и внутри этого у нас есть другое ожидание относительно a2, распределенное в соответствии с политикой (вероятность a2 при заданном s2). Поскольку у нас есть и s2, и a2, мы можем добавить вознаграждение и продолжить другие ожидания.
Одна вещь, о которой мы могли бы подумать: что, если бы у нас была какая-то функция, которая сообщала бы нам, что входит во второе ожидание? Давайте определим для этого символ, скажем, Q(s1, a1):
Важным моментом в этом определении является то, что если бы вы знали Q(s1, a1), то оптимизировать политику на первом временном шаге было бы очень просто.
Эта основная идея может быть расширена до более общей концепции: функции Q.
Функция Q может быть определена на других временных шагах, а не только на первом временном шаге. И определение такое:
Тесно связанная величина, которую мы также можем определить, называется функцией ценности, которая определяется почти таким же образом, только она обусловлена только состоянием, а не состоянием и действием:
Функция ценности также может быть записана как ожидаемое значение по действиям функции Q, потому что, если функция Q сообщает вам ожидаемое общее вознаграждение, если вы начнете с (st, at), то принимая ожидание этого относительно по желанию дать вам ожидаемую общую награду, если вы начнете в st:
Одно наблюдение, которое мы могли бы сделать, заключается в том, что ожидаемая функция ценности в состоянии s1 представляет собой цель обучения с подкреплением.
Использование Q-функций и функций значений
Если у нас есть политика и мы можем вычислить ее полную Q-функцию, то мы можем улучшить политику, например, выбрав новую политику, которая присваивает вероятность 1 данному действию, если это действие является argmax функции Q .
Интуиция такова, что если функция Q больше, чем функция ценности, то действие лучше среднего. Следовательно, вы можете изменить политику, чтобы увеличить вероятность действий, значение которых в функции Q больше, чем значение в этом состоянии.
Типы алгоритмов
Алгоритмы RL, которые мы рассмотрим, обычно оптимизируют цель RL, которую я определил ранее:
Алгоритмы градиента политики пытаются напрямую вычислить производную этой цели относительно тета, а затем выполнить процедуру градиентного спуска, используя эту производную.
Методы, основанные на ценности, оценивают функции ценности или Q-функции для оптимальной политики, а затем используют эти функции ценности или Q-функции для улучшения политики. Часто чистые функции, основанные на значениях, даже не представляют политику напрямую, а скорее представляют ее неявно как что-то вроде argmax Q-функции.
Актерско-критические методы представляют собой нечто среднее между ними. Они изучают Q-функцию или функцию ценности, а затем используют ее для улучшения политики, как правило, используя их для расчета лучшего градиента политики.
Алгоритмы обучения с подкреплением на основе моделей будут оценивать модель перехода. Они оценят некоторую модель вероятностей перехода T, а затем будут либо использовать модель перехода для планирования напрямую без какой-либо явной политики, либо использовать модель перехода для улучшения политики.
Если учесть, что каждый алгоритм RL состоит из трех компонентов, вот как различные алгоритмы различаются по отношению к этим компонентам:
- Создание образцов (запуск политики)
- Подгонка модели / оценка возврата. Алгоритмы на основе моделей изучают некоторую модель вероятности состояния (t+1), заданного состояния (t) и действия (t). Алгоритмы, основанные на функции ценности, соответствуют некоторой оценке функции ценности или Q-функции. Алгоритмы градиента политики оценивают общее вознаграждение по каждой траектории путем сложения вознаграждений, полученных во время развертывания. Алгоритмы критики акторов также соответствуют функции ценности или Q-функции, просто как методы, основанные на ценности.
- Улучшить политику. Алгоритмы на основе моделей имеют разные параметры. Один из вариантов — просто использовать изученную модель для прямого планирования; другой вариант — использовать изученную модель для вычисления производных функции вознаграждения по отношению к политике посредством обратного распространения; другой вариант — использовать изученную модель для изучения функции ценности, а затем использовать эту функцию для улучшения политики. Алгоритмы на основе функции значения просто выбирают политику, которая будет argmax Q-функции. Алгоритмы политик-градиентов совершают шаг градиентного восхождения по тета, используя градиент ожидаемого значения вознаграждения. Алгоритмы, основанные на функции ценности, выполняют шаг градиентного подъема в политике, используя функцию ценности или Q-функцию для получения более точной оценки.
Компромисс между алгоритмами
Эти алгоритмы имеют ряд компромиссов, которые определяют, какой из них лучше всего подходит для вас в вашей конкретной ситуации.
Компромисс 1.Одним из важных компромиссов между различными алгоритмами является эффективность выборки, то есть: когда вы создаете выборки в среде, сколько образцов вам потребуется, прежде чем вы сможете получить хорошую политику?
Компромисс 2. Еще один компромисс — стабильность и простота использования: алгоритмы обучения с подкреплением могут быть довольно сложными и требуют компромисса между рядом различных параметров. Как вы собираете образцы, как вы исследуете, как вы подходите к своей модели, как вы соответствуете своей функции ценности, как вы обновляете свою политику. Каждый из этих компромиссов и каждый из этих вариантов часто вводят дополнительные гиперпараметры, которые иногда бывает сложно выбрать для конкретной задачи.
Различные методы также будут иметь разные предположения, например: они работают со стохастическими средами или они могут работать только с детерминированными средами? Обрабатывают ли они непрерывные состояния и действия или могут обрабатывать только дискретные действия и дискретные состояния? Обрабатывают ли они эпизодические проблемы или решают проблемы с бесконечным горизонтом, когда t стремится к бесконечности?
В некоторых условиях может быть проще представить политику, даже если физика среды очень и очень сложна, в то время как в других условиях может быть проще изучить модель, чем изучить политику напрямую. Каждый из этих компромиссов будет включать в себя выбор определенного набора вариантов дизайна. Например, вы можете выбрать алгоритм, который не очень эффективен для выборки, чтобы иметь что-то более простое в использовании или, может быть, чтобы иметь что-то, что может обрабатывать стохастические и частично наблюдаемые проблемы. Или вы можете выбрать очень эффективный алгоритм, потому что ваши образцы очень дороги, но при этом согласиться с некоторыми другими ограничениями, такими как, например, разрешение только дискретных действий.
Эффективность образца
Эффективность выборки относится к тому, сколько образцов нам нужно, чтобы получить хорошую политику, в основном, сколько раз мы должны сделать выборку из нашей политики, пока мы не сможем заставить ее работать хорошо. Один из наиболее важных вопросов при определении выборочной эффективности алгоритма заключается в том, является ли алгоритм так называемым алгоритмом вне политики или нет.
Алгоритм вне политики — это алгоритм, который может улучшить политику, используя ранее собранные выборки, в то время как алгоритм включения политики должен отбрасывать все свои выборки каждый раз, когда политика хоть немного изменяется, и генерировать новые выборки. По этой причине алгоритмы политики могут быть намного менее эффективными.
Зачем нам вообще использовать алгоритмы справа? Потому что возникают другие компромиссы. Например, время настенных часов, объем вычислений, необходимых алгоритму, не то же самое, что эффективность выборки. Так что, возможно, генерация выборок для вашего приложения на самом деле очень дешева, и в этом случае вы, вероятно, не так сильно заботитесь об эффективности выборки — достаточно интересно, что время настенных часов для этих алгоритмов часто переворачивается, поэтому, если ваша симуляция очень дешева, вы может на самом деле обнаружить, что вещи на правом конце спектра менее затратны в вычислительном отношении, а вещи на левой стороне спектра — намного дороже в вычислительном отношении.
Стабильность и простота использования
Когда дело доходит до стабильности и простоты использования, мы можем задать такие вопросы, как: сходится ли наш алгоритм, то есть, если мы будем запускать его достаточно долго, гарантированно ли он в конечном итоге сходится к фиксированному решению или он будет продолжать колебаться или расходиться? сходится, к чему сходится? Сходится ли она к локальному оптимуму цели RL или к локальному оптимуму любой другой четко определенной цели? И каждый раз сходится?
В обучении с подкреплением конвергентные алгоритмы являются редкой роскошью, и многие методы, которые мы используем на практике, не гарантируют сходимости в целом. Таким образом, причина этого в том, что обучение с подкреплением часто не является чистым градиентным спуском: многие алгоритмы с подкреплением на самом деле являются алгоритмами с фиксированной точкой, которые несут гарантии сходимости только при очень упрощенных табличных предположениях о дискретном состоянии, которые часто не выполняются на практике. И теоретически сходимость многих наиболее популярных алгоритмов RL, таких как алгоритмы Q-обучения, на самом деле является открытой проблемой.
Подгонка функции значения представляет собой итерацию с фиксированной точкой. В лучшем случае он сводит к минимуму подгонку ошибок и сводит к минимуму то, что называется ошибкой Беллмана, которая не совпадает с ожидаемым вознаграждением. В худшем случае он ничего не оптимизирует, и многие популярные алгоритмы подбора значений глубокого обучения с подкреплением не гарантируют сходимость к чему-либо в нелинейном случае (случай, когда вы используете нейронные сети).
В основанном на модели RL модель минимизирует ошибку соответствия, что определенно приведет к хорошей модели, но нет гарантии, что хорошая модель приведет к лучшей политике.
Градиент политики — единственный, который фактически выполняет градиентное восхождение к истинной цели, но, как я уже сказал, он наименее эффективен из всех.
Предположения
Одним из распространенных предположений, которые делают многие алгоритмы RL, является полная наблюдаемость, что означает, что у вас есть доступ к состояниям, а не к наблюдениям. Обычно это предполагается большинством методов подбора функции ценности. Это можно смягчить, добавив такие вещи, как повторение и память, но в целом это может быть проблемой.
Другим распространенным предположением является эпизодическое обучение: агент делает попытку, затем сбрасывает, а затем делает еще одну попытку. Таким образом, эта возможность многократного сброса и повторной попытки часто предполагается чистыми методами градиента политики, и хотя технически это не предполагается большинством методов, основанных на ценности, они, как правило, работают лучше всего, когда это предположение выполняется. Это также предполагается некоторыми алгоритмами RL на основе моделей.
Другим распространенным предположением является непрерывность или гладкость. Это предполагается некоторыми методами обучения функции непрерывного значения, и это часто предполагается методами RL, основанными на моделях, полученными из оптимального управления, которые действительно требуют непрерывности или плавности для хорошей работы.
Ознакомьтесь со следующей статьей о градиентах политик!
Отправьте мне сообщение или:
