ПОИСК СТРАТЕГИИ
Последний подход к решению задач обучения с подкреплением, который рассматривается в этой главе, носит название поиска стратегии. В определенных отношениях метод, основанный на поиске стратегии, является самым простым из всех методов, рассматриваемых в данной главе; его идея состоит в том, что необходимо
продолжать корректировать стратегию до тех пор, пока связанная с ней производительность увеличивается, а после этого останавливаться.
Начнем с анализа самих стратегий. Напомним, что стратегией п называется функция, которая отображает состояния на действия. Нас прежде всего интересуют параметризованные представления я, которые имеют намного меньше параметров по сравнению с количеством состояний в пространстве состояний (как и в предыдущем разделе). Например, можно представить стратегию п в виде коллекции параметризованных Q-функций, по одной для каждого действия, и каждый раз предпринимать действие с наивысшим прогнозируемым значением:
Каждая Q-функция может представлять собой линейную функцию от параметров Э, как показано в уравнении 21.9, или может быть и нелинейной функцией, например, представленной в виде нейронной сети. В таком случае поиск стратегии сводится к корректировке параметров Э в целях улучшения стратегии. Следует отметить, что если стратегия представлена с помощью Q-функций, то поиск стратегии приводит к процессу определения Q-функций с помощью обучения, сж* Этот процесс не следует рассматривать как Q-обучение! При Q-обучении с помощью функциональной аппроксимации алгоритм находит такое значение Э, что функция QQ становится "близкой" к функции Q* — оптимальной Q-функции. При поиске стратегии, с другой стороны, отыскивается значение Э, которое приводит к достижению высокой производительности; найденные значения могут отличаться весьма существенно6. Еще одним примером, четко иллюстрирующим это различие, является случай, в котором n(s) вычисляется, допустим, с помощью опережающего поиска на глубину 10 с приближенной функцией полезности UQ. Значение Э, позволяющее обеспечить качественное ведение игры, может быть получено задолго до того, как удастся получить приближение UQ, напоминающее истинную функцию полезности.
Одним из недостатков представления стратегий в том виде, как показано в уравнении 21.13, является то, что в случае дискретных действий стратегия не является непрерывной функцией своих параметров7. Это означает, что существуют такие значения Э, при которых бесконечно малые изменения Э вызывают резкое переключение стратегии с одного действия на другое. Вследствие этого могут также происходить не являющиеся непрерывными изменения значения стратегии, в результате чего поиск на основе градиента становится затруднительным. По этой причине в методах поиска стратегии часто используется стохастическое представление стратегии Tie (s, a), которое задает вероятность выбора действия а в состоянии s. Одним из широко применяемых представлений такого типа является функция softmax:
Функция softmax становится почти детерминированной, если одно действие намного лучше по сравнению с другими, но она всегда позволяет получить дифференцируемую функцию от Э, поэтому ценность стратегии (которая связана непрерывной зависимостью с вероятностями выбора действий) определяется дифференцируемой функцией Э.
Теперь рассмотрим методы улучшения стратегии. Начнем с простейшего случая — детерминированной стратегии и детерминированной среды. В этом случае задача вычисления стратегии становится тривиальной — просто выполняется эта стратегия и регистрируются накопленные вознаграждения; полученные данные определяют ценность стратегии р (Э). В таком случае улучшение стратегии представляет собой стандартную задачу оптимизации, как описано в главе 4. В частности, можно проследить за вектором градиента стратегии V0p(0), при условии, что значение р (Э) является дифференцируемым. Другой вариант состоит в том, что можно проследовать за эмпирическим градиентом путем восхождения к вершине, т.е. вычисления изменений в стратегии в ответ на небольшие приращения в значениях каждого параметра. При соблюдении обычных предосторожностей такой процесс сходится к локальному оптимуму в пространстве стратегий.
Если же среда или стратегия является стохастической, задача становится более сложной. Предположим, что предпринимается попытка применить метод восхождения к вершине, для чего требуется сравнить р(Э) и р(Э+АЭ) при некотором небольшом значении АЭ. Проблема состоит в том, что суммарное вознаграждение при каждой попытке может существенно изменяться, поэтому оценки значения стратегии на основе небольшого количества попыток могут оказаться совершенно ненадежными, а еще более ненадежными становятся результаты, полученные при попытке сравнить две такие оценки. Одно из решений состоит в том, чтобы предпринять много попыток, измеряя дисперсию выборок и используя ее для определения того, достаточно ли много было сделано попыток, чтобы получить надежные данные о направлении улучшения для р (Э). К сожалению, такой подход является практически не применимым во многих реальных задачах, когда каждая попытка может оказаться дорогостоящей, требующей больших затрат времени, и, возможно, даже опасной.
В случае стохастической стратегии nQ (s, а) существует возможность получить несмещенную оценку для градиента Э, Vep (Э), соответствующего параметрам Э, непосредственно по результатам попыток, выполненных при таких значениях параметра Э. Для упрощения задачи выведем формулу такой оценки для простого случая непоследовательной среды, в которой вознаграждение предоставляется непосредственно после осуществления действия в начальном состоянии s0. В таком случае значение стратегии является просто ожидаемым значением вознаграждения, поэтому имеет место следующее:
Теперь можно применить простой пример, позволяющий аппроксимировать результаты этого суммирования с помощью выборок, сформированных на основании распределения вероятностей, определенного стратегией 7ie(s0,a). Предположим, что общее количество попыток равно N, а действием, предпринятым в j-й попытке, является aj. В таком случае получим следующее:
Поэтому истинный градиент значения стратегии аппроксимируется суммой термов, включающей градиент вероятности выбора действия при каждой попытке. Для последовательного случая это соотношение можно обобщить до такого соотношения для каждого посещенного состояния s:
где aj — действие, выполненное в состоянии s при j-й попытке; Rj{s) — суммарное вознаграждение, полученное, начиная от состояния s и дальше, при j-й попытке. Полученный в результате алгоритм называется Reinforce [1597]; обычно он является гораздо более эффективным по сравнению с восхождением к вершине, при котором используется большое количество попыток в расчете на каждое значение Э. Тем не менее он все еще действует гораздо медленнее, чем абсолютно необходимо.
Рассмотрим следующее задание: даны две программы игры в очко8; необходимо определить, какая из них лучше. Один из способов выполнения этого задания состоит в организации игры каждой программы против стандартной программы, "сдающей карты", в течение определенного количества раздач, с последующим сравнением выигрышей этих программ. Но этот подход связан с определенными проблемами, поскольку, как уже было сказано, выигрыш каждой программы изменяется в широких пределах в зависимости от того, получала ли она после каждой раздачи хорошие или плохие карты. Очевидным решением является заблаговременная выработка определенного количества раздач и сЖ3 множества карт, выдаваемых на руки. Благодаря этому устраняется ошибка измерения, связанная с различиями в полученных картах. Именно эта идея лежит в основе алгоритма Pegasus [1134]. Такой алгоритм является применимым в таких проблемных областях, для которых предусмотрен эмулятор, позволяющий повторно вырабатывать "случайные" результаты действий. Алгоритм функционирует по принципу заблаговременного формирования N последовательностей случайных чисел, каждая из которых может использоваться для прогона одного варианта опробования любой стратегии. Поиск стратегии осуществляется путем оценки каждой потенциальной стратегии с помощью одного и того же множества случайных последовательностей для определения результатов действия. Можно показать, что количество случайных последовательностей, требуемых для обеспечения качественной оценки значения любой стратегии, зависит только от сложности пространства стратегий, а не от сложности соответствующей проблемной области. Алгоритм Pegasus использовался для разработки эффективных стратегий в нескольких проблемных областях, включая автономный полет вертолета (рис. 21.7).
РЕЗЮМЕ
В данной главе рассматривалась задача обучения с подкреплением, решение которой позволяет агенту добиться успеха в неизвестной среде, пользуясь только полученными им результатами восприятия, а изредка также вознаграждениями. Обучение с подкреплением может рассматриваться как микроскопическая модель всей проблематики искусственного интеллекта, но для решения этой задачи применяется целый ряд упрощений, позволяющих быстрее добиться успеха. Основные идеи, изложенные в этой главе, перечислены ниже.
• Характер информации, которая должна быть получена в результате обучения, зависит от общего проекта агента. В данной главе рассматривались три основных проекта: проект, основанный на модели, в котором используется модель Т и функция полезности и; проект без модели, в котором применяется функция "действие—значение", или Q-функния. и рефлексный проект, в котором используется стратегия п.
• Для определения полезностей с помощью обучения могут использоваться три перечисленных ниже подхода.
1. При непосредственной оценке полезности применяется суммарное прогнозируемое наблюдаемое вознаграждение для заданного состояния в качестве прямого свидетельства, позволяющего определить полезность данного состояния с помощью обучения.
2. В адаптивном динамическом программировании (Adaptive Dynamic Programming — ADP) с помощью обучения определяются модель и функция вознаграждения на основании наблюдений, а затем используется итерация по значениям или по стратегиям для получения полезностей или выявления оптимальной стратегии. В методе ADP обеспечивается оптимальное использование локальных ограничений, налагаемых на полезности состояний под влиянием структуры отношений соседства в рассматриваемой среде.
3. В методах временной разности (Temporal Difference — TD) обновляются оценки полезности для их согласования с состояниями-преемниками. Подход, основанный на использовании этих методов, может рассматриваться как простая аппроксимация подхода ADP, в котором не требуется модель для процесса обучения. Однако применение определенной в процессе обучения модели для выработки псевдорезультатов опытов способствует ускорению обучения.
• Определение с помощью обучения функций "действие—значение", или Q-функций, может быть организовано на основе подхода ADP или TD. При использовании метода TD в процессе Q-обучения не требуется модель ни на этапе обучения, ни на этапе выбора действия. Это позволяет упростить задачу обучения, но в принципе может привести к ограничению способности проводить обучение в сложных вариантах среды, поскольку агент не сможет моделировать результаты применения возможных стратегий.
• Если от обучающегося агента требуется, чтобы он выбирал действия, пока еще продолжается обучение, то агенту приходится искать компромисс между оцениваемым значением этих действий и перспективами определения с помощью обучения новой полезной информации. Задача поиска точного решения такой проблемы исследования является неосуществимой, но некоторые простые эвристики позволяют добиться приемлемых результатов.
• Если пространство состояний велико, то в алгоритмах обучения с подкреплением необходимо использовать приближенное функциональное представление для обобщения сведений о состояниях. Для обновления параметров таких представлений, как нейронные сети, можно непосредственно использовать информацию о временной разности.
• Методы поиска стратегии применяются непосредственно к представлению стратегии в попытке улучшить ее с учетом наблюдаемой производительности. Изменчивость производительности в стохастической проблемной области представляет собой серьезную проблему; в случае моделируемых проблемных областей эту сложность можно преодолеть, заранее формируя случайные выборки.
• Обучение с подкреплением позволяет избавиться от необходимости разрабатывать вручную стратегии управления, поэтому продолжает оставаться одной из наиболее активных областей исследований машинного обучения. Особенно ценными могут стать приложения этих подходов в робототехнике; для этого потребуются методы обеспечения действий в непрерывных, многомерных, частично наблюдаемых вариантах среды, в которых успешное поведение может складываться из тысяч или даже миллионов примитивных действий.