Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 280
Текст из файла (страница 280)
Такой подход оказался очень успешным, поскольку он равносилен подходу, в котором пространство состояний рассматривается с разными степенями детализации. Второе отличие состояло в том, что в программе Самюэла не использовались какие-либо наблюдаемые вознаграждения! Это означает, что значения терминальных состояний игнорировались.
Таким образом, сушест- 1032 Часть У!. Обучение вовала реальная возможность, что вычисления в программе не будут сходиться, или по крайней мере сходиться к стратегии, позволяющей выиграть, а не проиграть. Новатор программы сумел избежать подобного неблагоприятного развития событий, соблюдая такое требование, что вес материального преимушества должен всегда быть положительным.
Замечательно то, что этого оказалось достаточно, чтобы всегда направлять программу в область пространства весов, соответствующую успешной игре в шашки. Возможности методов обучения с подкреплением особенно наглядно показала система ТР-Оапнпоп Герри Тесауро !1499]. В одной из более ранних работ [1501! Тесауро попытался определить с помощью обучения некоторое представление функции Ц(а, я) в виде нейронной сети непосредственно на примерах ходов, которым были присвоены относительные значения экспертом-человеком.
Но, как оказалось, этот подход требовал исключительно высоких трудозатрат со стороны привлеченного эксперта. Применение такого подхода привело к созданию программы под названием Хецгоаапипоп, которая оказалась сильнее, чем другие программы игры в нарды, существовавшие в то время, но не выдерживала соревнования с опытными игроками в нарды. Проект ТР-Оапппоп стал попыткой обучения программы исключительно в игре с самой собой. Единственный сигнал вознаграждения предоставлялся в конце каждой игры.
Функция оценки была представлена в виде полно- связной нейронной сети с единственным скрытым слоем, содержащим 40 узлов. Программа ТР-Оапцпоп сумела в результате обучения достичь значительно более высокого уровня игры по сравнению с 14ецгояапппоп путем повторного применения уравнения 21.! 1, даже несмотря на то, что входное представление содержало только грубые оценки позиции на доске, без вычисленных характеристик. Для обучения программы потребовалось проведение около 200000 учебных игр и две недели машинного времени. Хотя такое количество игр может показаться очень большим, оно фактически составляет лишь исчезающе малую долю пространства состояний.
После того как к входному представлению были добавлены предварительно рассчитанные характеристики с применением сети, включающей 80 скрытых элементов, в результате 300 000 учебных игр удалось достичь уровня игры, сравнимого с уровнем трех ведущих людей-игроков во всем мире. Кит Вулси, ведущий игрок и аналитик, сказал; "У меня не бьщо малейшего повода, чтобы усомниться в том, что эта программа оценивает позицию гораздо лучше по сравнению со мной". Применение к управлению роботами Постановка знаменитой залачи поиска равновесия системы Жтележка — шест, известной также под названием задачи 'ек обратного маятника, показана на рис.
21.6. Задача состоит в том, чтобы обеспечить управление положением тележки в направлении оси х таким образом, чтобы шест стоял примерно вертикально (О = п22), а сама тележка оставалась в пределах длины пути, как показано на этом рисунке. Такой с виду простой задаче посвящено свыше двух тысяч статей по обучению с подкреплением и теории управления. Задача с тележкой и шестом отличается от описанных выше задач тем, что переменные состояния х, 0, х, и 0 являются непрерывными.
С другой стороны, действия обычно остаются дискретными: таковыми являются рывки тележки влево или вправо в так называемом режиме !ж релейного управления. 1034 Часть М. Обучение продолжать корректировать стратегию до тех пор, пока связанная с ней производительность увеличивается, а после этого останавливаться.
Начнем с анализа самих стратегий. Напомним, что стратегией я называется функция, которая отображает состояния на действия. Нас прежде всего интересуют параметризованные представления я, которые имеют намного меньше параметров по сравнению с количествол1 состояний в пространстве состояний (как и в предыдушем разделе). Например, можно представить стратегию я в виде коллекции параметризованных О-функций, по одной для каждого действия, и каждый раз предпринимать действие с наивысшим прогнозируемым значением: (21.
13) п(в) = мах Де(а, в) а Каждая О-функция может представлять собой линейную функцию от параметров О, как показано в уравнении 21Э, или может быть и нелинейной функцией, например, представленной в виде нейронной сети. В таком случае поиск стратегии сводится к корректировке параметров О в целях улучшения стратегии. Следует отметить, что если стратегия представлена с помощью О-функций, то поиск стратегии приводит к процессу определения О-функций с помощью обучения. оу- Эват процесс не следует рассматривать как (')-абучелие! При О-обучении с помощью функциональной аппроксимации алгоритм находит такое значение О, что функция Оь становится "близкой" к функции О* — оптимальной О-функции.
При поиске стратегии, с другой стороны, отыскивается значение О, которое приводит к достижению высокой производительности; найденные значения могут отличаться весьма существенно'. Еще одним примером, четко иллюстрирующим это различие, является случай, в котором я( э) вычисляется, допустим, с помощью опережающего поиска на глубину 1О с приближенной функцией полезности ()е Значение О, позволяющее обеспечить качественное ведение игры, может быть получено задолго до того, как удастся получить приближение ()е, напоминающее истинную функцию полезности. Одним из недостатков представления стратегий в том виде, как показано в уравнении 21.13, является то, что в случае дискретных действий стратегия не является непрерывной функцией своих параметров'.
Это означает, что существуют такие значения О, при которых бесконечно малые изменения О вызывают резкое переключение стратегии с одного действия на другое, Вследствие этого могут также происходить не являющиеся непрерывными изменения значения стратегии, в результате чего поиск на основе градиента становится затруднительным. По этой причине в методах поиска стратегии часто используется ся стохастическое представление стратегии яе ( э, а), которое задает вероятность выбора действия а в состоянии э.
Одним из широко применяемых представлений такого типа является Ъ. функция яойшах: пь(в,а) =ехр(мо(а, в) ) / ~ ехр(0ь(а',в) ) а' ь Стало тривиальным такое замечание, что приближенная О-функция, определяемая соотношением (.Ь(а, в) =О* (а, в) /10, обеспечивает оптимальную производительность, даже несмотря на то, чго она весьма далека от Д*. У В случае непрерывного пространства действий стратегия может быть гладкой функцией от ее параметров. 1035 Глава 21. Обучение с подкреплением Функция войтах становится почти детерминированной, если одно действие намного лучше по сравнению с другими, но она всегда позволяет получить дифференцируемую функцию от О, поэтому ценность стратегии (которая связана непрерывной зависимостью с вероятностями выбора действий) определяется дифференцируемой функцией О.
Теперь рассмотрим методы улучшения стратегии. Начнем с простейшего случая — детерминированной стратегии и детерминированной среды. В этом случае задача вычисления стратегии становится тривиальной — просто выполняется эта стратегия и регистрируются накопленные вознаграждения; полученные данные определяют Ж ценность стратегии р (О) .
В таком случае улучшение стратегии представляет собой стандартную задачу оптимизации, как описано в главе 4. В частности, можно проследить за вектором Ж градиента стратегии '7ар (О), при условии, что значение р (О) является дифференцируемым. Другой вариант состоит в том, что можно проследовать за эмпирическим градиентом путем восхождения к вершине, т.е. вычисления изменений в стратегии в ответ на небольшие прирашения в значениях каждого параметра. При соблюдении обычных предосторожностей такой процесс сходится к локальному оптимуму в пространстве стратегий. Если же среда или стратегия является стохастической, задача становится более сложной. Предположим, что предпринимается попытка применить метод восхождения к вершине, для чего требуется сравнить р(О) и р(О+ЛО) при некотором небольшом значении АО.
Проблема состоит в том, что суммарное вознаграждение при каждой попытке может существенно изменяться, поэтому оценки значения стратегии на основе небольшого количества попыток могут оказаться совершенно ненадежными, а еше более ненадежными становятся результаты, полученные при попытке сравнить две такие оценки. Одно из решений состоит в том, чтобы предпринять много попыток, измеряя дисперсию выборок и используя ее для определения того, лостаточно ли много было сделано попыток, чтобы получить надежные данные о направлении улучшения для р (О) .
К сожалению, такой подход является практически не применимым во многих реальных задачах, когда каждая попытка может оказаться дорогостояшей, требуюшей больших затрат времени, и, возможно, даже опасной. В случае стохастической стратегии яа(э, а) сушествует возможность получить несмешенную оценку для градиента О, 57ар (О), соответствующего параметрам О, непосредственно по результатам попыток, выполненных при таких значениях параметра О.
Для упрошения задачи выведем формулу такой оценки для простого случая непоследовательной среды, в которой вознаграждение предоставляется непосредственно после осушествления действия в начальном состоянии вя В таком случае значение стратегии является просто ожидаемым значением вознаграждения, поэтому имеет место следуюшее: 7ер(О) =~7в ~ яв(эо, а) л(а) = ) (~ветс~(зо, а) ) д(а) Теперь можно применить простой пример, позволявший аппроксимировать результаты этого суммирования с помощью выборок, сформированных на основании распределения вероятностей, определенного стратегией яа(эг д). Предположим, Часть т>1. Обучение !036 что общее количество попыток равно >>>, а действием, предпринятым в >-и попытке, является а,.
В таком случае получим следующее: \ (ь" (, )) () т ~(~ (, )) ( ) ))) р!Е> =~ 1, а>. дс ( ас, а > тт~ н дс ! ас, а, > Поэтому истинный градиент значения стратегии аппроксимируется суммой термов, включаюшей градиент вероятности выбора действия при каждой попытке. Для последовательного случая это соотношение можно обобгцить до такого соотношения для каждого посешенного состояния ш где а, — действие, выполненное в состоянии э при 1-й попытке; >гз ! э> — суммарное вознаграждение, полученное, начиная от состояния э и дальше, при 3-и попытке. Полученный в результате алгоритм называется Ке!пГогсе [1597[; обычно он является гораздо более эффективным по сравнению с восхождением к вершине, при котором используется большое количество попыток в расчете на каждое значение О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
