Обучение с подкреплением

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
Текущая версия (07:47, 25 декабря 2008) (править) (отменить)
м (уточнение)
 
(11 промежуточных версий не показаны.)
Строка 1: Строка 1:
 +
{{TOCright}}
'''Обучение с подкреплением''', идея которого была почерпнута в смежной области психологии, является подразделом [[машинное обучение|машинного обучения]], изучающим, как ''агент'' должен ''действовать'' в ''окружении'', чтобы максимизировать некоторый долговременный ''выигрыш''.
'''Обучение с подкреплением''', идея которого была почерпнута в смежной области психологии, является подразделом [[машинное обучение|машинного обучения]], изучающим, как ''агент'' должен ''действовать'' в ''окружении'', чтобы максимизировать некоторый долговременный ''выигрыш''.
Алгоритмы с частичным обучением пытаются найти ''стратегию'', приписывающую ''состояниям'' окружающей среды действия, которые должен предпринять агент в этих состояниях.
Алгоритмы с частичным обучением пытаются найти ''стратегию'', приписывающую ''состояниям'' окружающей среды действия, которые должен предпринять агент в этих состояниях.
-
В экономике и теории игр обчение с подкреплением рассматривается в качестве интерпретации того, как может установиться равновесие.
+
В экономике и теории игр обучение с подкреплением рассматривается в качестве интерпретации того, как может установиться равновесие.
Окружение обычно формулируется как [http://en.wikipedia.org/wiki/Markov_decision_process марковский процесс принятия решений] (МППР) с конечным множеством состояний, и в этом смысле алгоритмы обучения с подкреплением тесно связаны с динамическим программированием.
Окружение обычно формулируется как [http://en.wikipedia.org/wiki/Markov_decision_process марковский процесс принятия решений] (МППР) с конечным множеством состояний, и в этом смысле алгоритмы обучения с подкреплением тесно связаны с динамическим программированием.
-
Вероятнности выигрышей и перехода состояний в МППР обычно являются величинами случайными, но стационарными в рамках задачи.
+
Вероятности выигрышей и перехода состояний в МППР обычно являются величинами случайными, но стационарными в рамках задачи.
-
Продолжение следует...
+
При обучении с подкреплением, в отличии от [[обучение с учителем|обучения с учителем]],не предоставляются верные пары „входные данные-ответ“, а принятие субоптимальнх решений (дающих локальный экстремум) не ограничивается явно.
-
{{UnderConstruction|[[Участник:Дорофеев Н.Ю.|Дорофеев Н.Ю.]] 12:31, 5 ноября 2008 (MSK)}}
+
Обучение с подкреплением пытается найти компромисс между исследованием неизученных областей и применением имеющихся знаний.
 +
Баланс изучения-применения при обучении с подкреплением исследовался в задаче [http://en.wikipedia.org/wiki/Multi-armed_bandit многорукого бандита].
 +
 
 +
Формально простейшая модель обучения с подкреплением состоит из:
 +
# множества состояний окружения <i>S</i>;
 +
# множества действий <i>A</i>;
 +
# множества вещественнозначных скалярных „выигрышей“.
 +
 
 +
В произвольный момент времени <i>t</i> агент характеризуется состоянием <tex>s_t \in S</tex> и множеством возможных действий <tex>A(s_t)</tex>.
 +
Выбирая действие <tex>a \in A(s_t)</tex>, он переходит в состояние <tex>s_{t+1}</tex> и получает выигрыш <tex>r_t</tex>.
 +
Основываясь на таком взаимодействии с окружающей средой, агент, обучающийся с подкреплением, должен выработать стратегию <tex>\pi: S \to A</tex>, которая максимизирует величину <tex>R=r_0 + r_1+\cdots+r_n</tex> в случае МППР, имеющего терминальное состояние, или величину <br />
 +
::<tex>R=\sum_t \gamma^t r_t</tex> <br />
 +
для МППР без терминальных состояний (где <tex>0 \leq \gamma \leq 1</tex> —- дисконтирующий множитель для „предстоящего выигрыша“).
 +
 
 +
Таким образом, обучение с подкреплением особенно хорошо подходит для решения задач, связанных с выбором между долгосрочной и краткосрочной выгодой.
 +
Оно успешно применялось в различных областях, таких как робототехника, управление лифтами, телекоммуникации,шашки и нарды (Sutton 1998, Глава 11).
 +
 
 +
== Алгоритмы ==
 +
 
 +
Теперь, когда была определена функция выигрыша, нужно определить алгоритм, который будет использоваться для нахождения стратегии, обеспечивающей наилучший результат.
 +
 
 +
Наивный подход к решению этой задачи подразумевает следующие шаги:
 +
#опробовать все возможные стратегии;
 +
#выбрать стратегию с наибольшим ожидаемым выигрышем.
 +
Первая проблема такого подхода заключается в том, что количество доступных стратегий может быть очень велико или же бесконечно.
 +
Вторая проблема возникает, если выигрыши стохастические — чтобы точно оценить выигрыш от каждой стратегии потребуется многократно применить каждую из них.
 +
Этих проблем можно избежать, если допустить некоторую структуризацию и, возможно, позволить результатам, полученным от пробы одной стратегии, влиять на оценку для другой.
 +
Двумя основными подходами для реализации этих идей являются оценка функций полезности и прямая оптимизация стратегий.
 +
 
 +
Подход с использованием функции полезности использует множество оценок ожидаемого выигрыша только для одной стратегии <tex>\pi</tex> (либо текущей, либо оптимальной).
 +
При этом пытаются оценить либо ожидаемый выигрыш, начиная с состояния <i>s</i>, при дальнейшем следовании стратегии <tex>\pi</tex>, <br />
 +
::<tex>V(s)=E[R|s,\pi]</tex>, <br />
 +
либо ожидаемый выигрыш, при принятии решения <i>a</i> в состоянии <i>s</i> и дальнейшем соблюдении <tex>\pi</tex>, <br />
 +
::<tex>Q(s,a)=E[R|s,\pi,a]</tex>. <br />
 +
Если для выбора оптимальной стратегии используется функция полезности <i>Q</i>, то оптимальные действия всегда можно выбрать как действия, максимизирующие полезность.
 +
Если же мы пользуемся функцией <i>V</i>, необходимо либо иметь модель окружения в виде вероятностей <i>P(s'|s,a)</i>, что позволяет построить функцию полезности вида <br />
 +
::<tex>Q(s,a)=\sum_{s'}V(s')P(s'|s,a)</tex>, <br />
 +
либо применить т.н. метод исполнитель-критик, в котором модель делится на две части: критик, оценивающий полезность состояния <i>V</i>, и исполнитель, выбирающий подходящее действие в каждом состоянии.
 +
 
 +
Имея фиксированную стратегию <tex>\pi</tex>, оценить <tex>E[R|\cdot]</tex> при <tex>\gamma=0</tex> можно просто усреднив непосредственные выигрыши.
 +
Наиболее очевидный способ оценки при <tex>\gamma>0</tex> — усреднить суммарный выигрыш после каждого состояния.
 +
Однако для этого требуется, чтобы МППР достиг терминального состояния (завершился).
 +
 
 +
Поэтому построение искомой оценки при <tex>\gamma>0</tex> неочевидно. Однако, можно заметить, что <i>R</i> образуют рекурсивное уравнение Беллмана: <br />
 +
::<tex>E[R|s_t]=r_t+\gamma E[R|s_{t+1}]</tex>. <br />
 +
Подставляя имеющиеся оценки, <i>V</i>, и применяя метод градиентного спуска с квадратичной функцией ошибок, мы приходим к алгоритму [http://en.wikipedia.org/wiki/Temporal_difference_learning обучения с временными воздействиями].
 +
В простейшем случае и состояния, и действия дискретны и можно придерживаться табличных оценок для каждого состояния.
 +
Другие похожие методы: Адаптивный эвристический критик (Adaptive Heuristic Critic, AHC), [http://en.wikipedia.org/wiki/SARSA SARSA] и Q-обучение ([http://en.wikipedia.org/wiki/Q-Learning Q-learning]).
 +
Все вышеупомянутые используют различные методы приближения, но в некоторых случаях сходимость не гарантируется.
 +
Для уточнения оценок используется метод градиентного спуска или [[метод наименьших квадратов]] в случае линейных приближений.
 +
 
 +
Указанные методы не только сходятся к корректной оценке для фиксированной стратегии, но и могут быть использованы для нахождения оптимальной стратегии
 +
Для этого в большинстве случаев принимают стратегию с максимальной оценкой, принимая иногда случайные шаги для исследования пространства.
 +
При выполнении некоторых дополнительных условий существуют доказательства сходимости упомянутых методов к оптимальной стратегии.
 +
Однако, эти доказательства гарантируют только асимптотическую сходимость, в то время как поведение алгоритмов обучения с подкреплением в задачах с малыми выборками мало изучено, не считая некоторых очень ограниченных случаев.
 +
 
 +
Альтернативный метод поиска оптимальной стратегии — искать непосредственно в пространстве стратегий.
 +
Таки методы определяют стратегию как параметрическую функцию <tex>\pi (s,\theta )</tex> с параметром <tex>\theta</tex>.
 +
Для настройки параметров применяются градиентные методы.
 +
Однако, применение градиентных методов осложняется тем, что отсутствует информация о градиенте.
 +
Более того, градиент тоже приходится оценивать через зашумлённые результаты выигрышей.
 +
Так как это существенно увеличивает вычислительные затраты, может быть выгоднее использовать более мощные градиентные методы, такие как метод скорейшего спуска.
 +
Алгоритмы, работающие напрямую с пространством стратегий привлекли значительное внимание в последние 5 лет и в данный момент достигли достаточно зрелой стадии, но до сих пор остаются активным полем для исследований.
 +
Существуют и другие подходы, такие как метод отжига, применяемые для исследования пространства стратегий.
 +
 
 +
== Современные исследования ==
 +
 
 +
В настоящее время ведутся исследования по Альтернативным представлениям (таких как Представление предсказывающих состояний), градиентный спуск в пространстве стратегий, сходимость для задач с малыми выборками, модулярное и иерархическое обучение с подкреплениями.
 +
В последнее время обучение с подкреплением использовалось в психологии для изучения процессов человеческого обучения и деятельности.
 +
В частности, исследовались когнитивные модели, симулирующие человеческое поведение в процессе решения задач и/или обретения навыков (Sun, Merril, & Peterson, 2001; Sun, Slusarz, & Terry, 2005; Gray, Sims, Fu, & Schoelles, 2006; Fu & Anderson, 2006).
 +
Обучение с подкреплением использовалось, чтобы предложить модель человеческой системы обработки ошибок.
 +
Многоагентное или распределённое обучение с подкреплением являются одним из направлений исследований в этой области.
 +
 
 +
== Ссылки ==
 +
 
 +
*[http://en.wikipedia.org/wiki/Reinforcement_learning Wikipedia: Reinforcement learning]
 +
 
 +
== Литература ==
 +
 
 +
*{{книга
 +
|автор = Sutton, Richard S.; Andrew G. Barto
 +
|заглавие = Reinforcement Learning: An Introduction.
 +
|год = 1998
 +
|издательство = MIT Press. refSutton1998
 +
|ссылка = http://www.cs.ualberta.ca/~sutton/book/ebook/the-book.html
 +
}}
 +
*{{книга
 +
|автор = Ron Sun, E. Merrill, and T. Peterson
 +
|часть = From implicit skills to explicit knowledge: A bottom-up model of skill learning.
 +
|заглавие = Cognitive Science
 +
|год = 2001
 +
|том = Vol.25, No.2
 +
|страницы = 203-244
 +
|ссылка = http://www.cogsci.rpi.edu/~rsun/sun.cs01.pdf
 +
}}
 +
*{{книга
 +
|автор = Ron Sun, P. Slusarz, and C. Terry
 +
|часть = The interaction of the explicit and the implicit in skill learning: A dual-process approach
 +
|заглавие = Psychological Review
 +
|год = 2005
 +
|том = Vol.112, No.1
 +
|страницы = 159-192
 +
|ссылка = http://www.cogsci.rpi.edu/~rsun/sun-pr2005-f.pdf
 +
}}
 +
*{{книга
 +
|автор = Gray, Wayne D.; Chris R. Sims; Wai-Tat Fu; Michael J. Schoelles
 +
|часть = The Soft Constraints Hypothesis: A Rational Analysis Approach to Resource Allocation for Interactive Behavior
 +
|заглавие = Psychological Review
 +
|год = 2006
 +
|том = 113 No.3
 +
|страницы = 461–482
 +
}}
 +
*{{книга
 +
|автор = Fu, Wai-Tat; John R. Anderson
 +
|часть = From Recurrent Choice to Skill Learning: A Reinforcement-Learning Model
 +
|заглавие = Journal of Experimental Psychology: General
 +
|год = 2006
 +
|том = 135 No.2
 +
|страницы = 184 –206
 +
|ссылка = http://www.humanfactors.uiuc.edu/Reports&PapersPDFs/JournalPubs/Fu&Anderson06-JEPG(published)(ReinforcementLearning).pdf
 +
}}
 +
 
 +
[[Категория:Машинное обучение]]
 +
[[Категория:Энциклопедия анализа данных]]

Текущая версия

Содержание

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

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

При обучении с подкреплением, в отличии от обучения с учителем,не предоставляются верные пары „входные данные-ответ“, а принятие субоптимальнх решений (дающих локальный экстремум) не ограничивается явно. Обучение с подкреплением пытается найти компромисс между исследованием неизученных областей и применением имеющихся знаний. Баланс изучения-применения при обучении с подкреплением исследовался в задаче многорукого бандита.

Формально простейшая модель обучения с подкреплением состоит из:

  1. множества состояний окружения S;
  2. множества действий A;
  3. множества вещественнозначных скалярных „выигрышей“.

В произвольный момент времени t агент характеризуется состоянием s_t \in S и множеством возможных действий A(s_t). Выбирая действие a \in A(s_t), он переходит в состояние s_{t+1} и получает выигрыш r_t. Основываясь на таком взаимодействии с окружающей средой, агент, обучающийся с подкреплением, должен выработать стратегию \pi: S \to A, которая максимизирует величину R=r_0 + r_1+\cdots+r_n в случае МППР, имеющего терминальное состояние, или величину

R=\sum_t \gamma^t r_t

для МППР без терминальных состояний (где 0 \leq \gamma \leq 1 —- дисконтирующий множитель для „предстоящего выигрыша“).

Таким образом, обучение с подкреплением особенно хорошо подходит для решения задач, связанных с выбором между долгосрочной и краткосрочной выгодой. Оно успешно применялось в различных областях, таких как робототехника, управление лифтами, телекоммуникации,шашки и нарды (Sutton 1998, Глава 11).

Алгоритмы

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

Наивный подход к решению этой задачи подразумевает следующие шаги:

  1. опробовать все возможные стратегии;
  2. выбрать стратегию с наибольшим ожидаемым выигрышем.

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

Подход с использованием функции полезности использует множество оценок ожидаемого выигрыша только для одной стратегии \pi (либо текущей, либо оптимальной). При этом пытаются оценить либо ожидаемый выигрыш, начиная с состояния s, при дальнейшем следовании стратегии \pi,

V(s)=E[R|s,\pi],

либо ожидаемый выигрыш, при принятии решения a в состоянии s и дальнейшем соблюдении \pi,

Q(s,a)=E[R|s,\pi,a].

Если для выбора оптимальной стратегии используется функция полезности Q, то оптимальные действия всегда можно выбрать как действия, максимизирующие полезность. Если же мы пользуемся функцией V, необходимо либо иметь модель окружения в виде вероятностей P(s'|s,a), что позволяет построить функцию полезности вида

Q(s,a)=\sum_{s'}V(s')P(s'|s,a),

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

Имея фиксированную стратегию \pi, оценить E[R|\cdot] при \gamma=0 можно просто усреднив непосредственные выигрыши. Наиболее очевидный способ оценки при \gamma>0 — усреднить суммарный выигрыш после каждого состояния. Однако для этого требуется, чтобы МППР достиг терминального состояния (завершился).

Поэтому построение искомой оценки при \gamma>0 неочевидно. Однако, можно заметить, что R образуют рекурсивное уравнение Беллмана:

E[R|s_t]=r_t+\gamma E[R|s_{t+1}].

Подставляя имеющиеся оценки, V, и применяя метод градиентного спуска с квадратичной функцией ошибок, мы приходим к алгоритму обучения с временными воздействиями. В простейшем случае и состояния, и действия дискретны и можно придерживаться табличных оценок для каждого состояния. Другие похожие методы: Адаптивный эвристический критик (Adaptive Heuristic Critic, AHC), SARSA и Q-обучение (Q-learning). Все вышеупомянутые используют различные методы приближения, но в некоторых случаях сходимость не гарантируется. Для уточнения оценок используется метод градиентного спуска или метод наименьших квадратов в случае линейных приближений.

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

Альтернативный метод поиска оптимальной стратегии — искать непосредственно в пространстве стратегий. Таки методы определяют стратегию как параметрическую функцию \pi (s,\theta ) с параметром \theta. Для настройки параметров применяются градиентные методы. Однако, применение градиентных методов осложняется тем, что отсутствует информация о градиенте. Более того, градиент тоже приходится оценивать через зашумлённые результаты выигрышей. Так как это существенно увеличивает вычислительные затраты, может быть выгоднее использовать более мощные градиентные методы, такие как метод скорейшего спуска. Алгоритмы, работающие напрямую с пространством стратегий привлекли значительное внимание в последние 5 лет и в данный момент достигли достаточно зрелой стадии, но до сих пор остаются активным полем для исследований. Существуют и другие подходы, такие как метод отжига, применяемые для исследования пространства стратегий.

Современные исследования

В настоящее время ведутся исследования по Альтернативным представлениям (таких как Представление предсказывающих состояний), градиентный спуск в пространстве стратегий, сходимость для задач с малыми выборками, модулярное и иерархическое обучение с подкреплениями. В последнее время обучение с подкреплением использовалось в психологии для изучения процессов человеческого обучения и деятельности. В частности, исследовались когнитивные модели, симулирующие человеческое поведение в процессе решения задач и/или обретения навыков (Sun, Merril, & Peterson, 2001; Sun, Slusarz, & Terry, 2005; Gray, Sims, Fu, & Schoelles, 2006; Fu & Anderson, 2006). Обучение с подкреплением использовалось, чтобы предложить модель человеческой системы обработки ошибок. Многоагентное или распределённое обучение с подкреплением являются одним из направлений исследований в этой области.

Ссылки

Литература

  • Sutton, Richard S.; Andrew G. Barto Reinforcement Learning: An Introduction.. — MIT Press. refSutton1998, 1998.
  • Ron Sun, E. Merrill, and T. Peterson From implicit skills to explicit knowledge: A bottom-up model of skill learning. // Cognitive Science. — 2001 T. Vol.25, No.2. — С. 203-244.
  • Ron Sun, P. Slusarz, and C. Terry The interaction of the explicit and the implicit in skill learning: A dual-process approach // Psychological Review. — 2005 T. Vol.112, No.1. — С. 159-192.
  • Gray, Wayne D.; Chris R. Sims; Wai-Tat Fu; Michael J. Schoelles The Soft Constraints Hypothesis: A Rational Analysis Approach to Resource Allocation for Interactive Behavior // Psychological Review. — 2006 T. 113 No.3. — С. 461–482.
  • Fu, Wai-Tat; John R. Anderson From Recurrent Choice to Skill Learning: A Reinforcement-Learning Model // Journal of Experimental Psychology: General. — 2006 T. 135 No.2. — С. 184 –206.
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D1%81_%D0%BF%D0%BE%D0%B4%D0%BA%D1%80%D0%B5%D0%BF%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5%D0%BC»
Личные инструменты