Навчання з підкріпленням: відмінності між версіями

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Інтерактивний перегляд історії
[неперевірена версія][перевірена версія]
← Попереднє редагуванняНаступне редагування →
Вилучено вміст Додано вміст
ВізуальнийВікірозмітка
м +перекласти, уточнення доробити
перекладено en:Reinforcement learning: https://en.wikipedia.org/w/index.php?title=Reinforcement_learning&oldid=736484845
Рядок 1: Рядок 1:
{{Hatnote|Про підкріплення в психології див. {{нп|Підкріплення|||Reinforcement}} та {{нп|Навчання методом проб, помилок|||Operant conditioning}}}}
{{Машинне навчання}}
{{Машинне навчання}}


'''Навчання з підкріпленням''' (англ. ''Reinforcement learning'') — це галузь [[Машинне навчання|машинного навчання]] натхненна [[Біхевіоризм|біхевіористською психологією]], що займається питанням про те, які дії мають виконувати [[Програмний агент|програмні агенти]] в певному середовищі задля максимізації деякого уявлення про сукупну винагороду. Через свою загальність, дана проблема вивчається, вивчається багатьма іншими дисциплінами, такими як [[теорія ігор]], [[теорія управління]], [[дослідження операцій]], [[теорія інформації]], [[оптимізація на основі моделювання]], [[Багатоагентна система|багатоагентні системи]], [[колективний інтелект]], [[статистика]] та [[генетичні алгоритми]]. В літературі про дослідження та управління операціями, галузь, що займається навчанням з підкріпленням, називається наближеним динамічним програмуванням. Попри те, що проблема навчання з підкріпленням, вивчалась [[Теорія оптимального управління|теорією оптимального управління]], більшість досліджень стосувались саме існування оптимальних рішень та їх характеристики, а не навчання чи наближених аспектів. В [[Економіка|економіці]] та [[Теорія ігор|теорії ігор]], навчання з підкріпленням може використовуватись для пояснення того, як при [[Обмежена раціональність|обмеженій раціональності]] може виникати рівновага.
'''Навчання з підкріпленням''' ({{lang-en|reinforcement learning}}) — це галузь [[Машинне навчання|машинного навчання]], натхнена [[Біхевіоризм|біхевіористською психологією]], що займається питанням про те, які {{нп|Вибір дій|''дії''||Action selection}} ({{lang-en|actions}}) повинні виконувати [[Програмний агент|програмні агенти]] в певному ''середовищі'' ({{lang-en|environment}}) задля максимізації деякого уявлення про сукупну ''винагороду'' ({{lang-en|reward}}). Через її універсальність, дану задачу вивчають і багато інших дисциплін, таких як [[теорія ігор]], [[теорія керування]], [[дослідження операцій]], [[теорія інформації]], {{нп|оптимізація на основі моделювання|||Simulation-based optimization}}, [[Поліагентна система|поліагентні системи]], [[колективний інтелект]], [[статистика]] та [[генетичні алгоритми]]. В літературі про дослідження та керування операціями галузь, що займається навчанням з підкріпленням, називається ''наближеним динамічним програмуванням'' ({{lang-en|approximate dynamic programming}}). Задачу навчання з підкріпленням було досліджувано [[Теорія оптимального керування|теорією оптимального керування]], проте більшість досліджень стосувалися саме існування оптимальних рішень та їх характеристики, а не аспектів навчання чи наближення. В [[Економіка|економіці]] та [[Теорія ігор|теорії ігор]] навчання з підкріпленням може використовуватись для пояснення того, як може виникати рівновага за {{нп|Обмежена раціональність|обмеженої раціональності||Bounded rationality}}.


В машинному навчанні середовище зазвичай формулюється як {{нп|марковський процес ухвалення рішень|||Markov decision process}} (МПУР, {{lang-en|Markov decision process, MDP}}), оскільки багато алгоритмів навчання з підкріпленням для цього контексту використовують методики [[Динамічне програмування|динамічного програмування]]. Основна відмінність між класичними методиками й алгоритмами навчання з підкріпленням полягає в тому, що останні не потребують знання про МПУР, і вони орієнтовані на великі МПУР, в яких точні методи стають нездійсненними.
== Вступ ==

Навчання з підкріпленням відрізняється від стандартного [[навчання з учителем]] тим, що пари правильних входів/виходів ніколи не представляються, а недостатньо оптимальні дії явно не виправляються. Крім того, є акцент на інтерактивній продуктивності, який включає знаходження балансу між [[Територіальне дослідження|дослідженням]] (незвіданої території, {{lang-en|exploration}}) та використанням (поточного знання, {{lang-en|exploitation}}). Компроміс між дослідженням та використанням у навчанні з підкріпленням найретельніше вивчався через задачу {{нп|Багаторукий бандит|багаторукого бандита||Multi-armed bandit}} та скінченні МПУР.

== Введення ==

Базова модель навчання з підкріпленням складається з:

# множини станів середовища <math>S</math>;
# множини дій <math>A</math>;
# правил переходу між станами;
# правил, які визначають ''скалярну безпосередню винагороду'' ({{lang-en|scalar immediate reward}}) переходу; і
# правил, які описують, що спостерігає агент.

Ці правила часто є [[Стохастичність|стохастичними]]. Спостереження зазвичай включає в себе скалярну безпосередню винагороду, пов'язану з крайнім переходом. У багатьох працях також вважають, що агент спостерігає поточний стан середовища, в разі чого говорять про ''повну спостережуваність'' ({{lang-en|full observability}}), тоді як в іншому разі говорять про ''часткову спостережуваність'' ({{lang-en|partial observability}}). Іноді множина доступних агентові дій є обмеженою (наприклад, ви не можете витрачати більше грошей, ніж маєте).

Агент навчання з підкріпленням взаємодіє зі своїм середовищем у дискретні моменти часу. В кожен момент часу <math>t</math> агент отримує спостереження <math>o_t</math>, яке зазвичай включає винагороду <math>r_t</math>. Потім він обирає дію <math>a_t</math> з множини доступних дій, яка відтак відправляється до середовища. Середовище переходить до нового стану <math>s_{t+1}</math>, і визначається винагорода <math>r_{t+1}</math>, пов'язана з ''переходом'' ({{lang-en|transition}}) <math>(s_t,a_t,s_{t+1})</math>. Метою агента навчання з підкріпленням є збирати якомога більше винагороди. [[Програмний агент|Агент]] може обирати будь-яку дію як функцію історії, і може навіть робити свій {{нп|вибір дії|||Action selection}} випадковим.

Коли продуктивність агента порівнюється з продуктивністю агента, який діє оптимально від початку, то різниця в продуктивності призводить до поняття ''жалю'' ({{lang-en|regret}}). Зверніть увагу, що, щоби діяти майже оптимально, агент мусить розуміти довготермінові наслідки своїх дій: щоби максимізувати свій майбутній дохід, мені краще зараз піти до школи, хоча пов'язана з цим безпосередня грошова винагорода може бути від'ємною.

Таким чином, навчання з підкріпленням є особливо добре пристосованим для задач, які включають компроміс між довготерміновою та короткотерміновою винагородою. Його було успішно застосовувано до різноманітних задач, включно з {{нп|Керування роботами|керуванням роботами||Robot control}}, розкладами для ліфтів, [[Телекомунікації|телекомунікаціями]], [[Нарди|нардами]], [[Шашки|шашками]]{{sfn|Sutton|Barto|1998|loc=[https://webdocs.cs.ualberta.ca/~sutton/book/ebook/node107.html §11. Case Studies]}} та [[Ґо (гра)|ґо]] ([[AlphaGo]]).

Потужним навчання з підкріпленням роблять дві складові: використання зразків для оптимізації продуктивності, та застосування наближень функцій, щоби мати справу з великими середовищами. Завдяки цим двом складовим навчання з підкріпленням можливо застосовувати у великих середовищах в будь-яких із наступних ситуацій:

* Модель середовища є відомою, але аналітичний розв'язок відсутній;
* Задано лише імітаційну модель середовища (предмет {{нп|Оптимізація на основі імітації|оптимізації на основі імітації||Simulation-based optimization}});{{sfn|Gosavi|2003}}
* Єдиним способом збирання інформації про середовище є взаємодія з ним.

Перші дві з цих задач можливо розглядати як задачі планування (оскільки модель в якомусь вигляді існує), тоді як останню можливо розглядати як справжню задачу навчання. Проте за методології навчання з підкріпленням обидві задачі планування може бути перетворено на задачі [[Машинне навчання|машинного навчання]].


== Дослідження ==
== Дослідження ==

== Алгоритми управління навчанням ==
Описана задача навчання з підкріпленням вимагає розумних механізмів дослідження. Відомо, що випадковий вибір дій без прив'язки до оцінюваного розподілу ймовірності викликає дуже погану продуктивність. Випадок (невеликих) скінченних МПУР в даний час є відносно добре вивченим. Проте через брак алгоритмів, які б довідно добре масштабувалися з числом станів (або масштабувалися до задач з нескінченними просторами станів), на практиці люди вдаються до простих методів дослідження. Одним із таких методів є <math>\epsilon</math>-жадібний, коли агент вибирає дію, яка за його переконанням має найкращий довготермінових ефект, з імовірністю <math>1-\epsilon</math>, а інакше вибирає дію рівномірно випадково. Тут <math>0<\epsilon<1</math> є параметром налаштування, який іноді змінюється, або згідно фіксованого розкладу (роблячи так, що агент з плином часу досліджує менше), або адаптивно на основі якихось евристик.

== Алгоритми для навчання керуванню ==

Навіть якщо питання дослідження не береться до уваги, і навіть якщо стан можна було спостерігати (що ми припускаємо, з цього моменту), лишається задача з'ясування на основі попереднього досвіду, які дії є добрими.


=== Критерій оптимальності ===
=== Критерій оптимальності ===

Для спрощення на хвилинку припустімо, що досліджувана задача є ''епізодичною'' ({{lang-en|episodic}}), із завершенням епізоду при досягненні деякого ''завершального стану'' ({{lang-en|terminal state}}). Припустімо далі, що незалежно від того, який план дій обирає агент, завершення є неминучим. За деяких додаткових м'яких умов закономірності математичне сподівання повної винагороди є добре визначеним для ''будь-якої'' стратегії та будь-якого початкового розподілу над станами. Тут стратегія ({{lang-en|policy}}) позначає відображення, яке призначає деякий розподіл імовірності над діями всім можливим історіям.

Таким чином, для заданого зафіксованого початкового розподілу <math>\mu</math> ми можемо поставити у відповідність стратегії <math>\pi</math> [[Математичне сподівання|очікувану]] віддачу <math>\rho^\pi</math>:

: <math>\rho^\pi = E[R|\pi],</math>

де випадкова величина <math>R</math> позначає ''віддачу'' ({{lang-en|return}}), і визначається як

: <math>R=\sum_{t=0}^{N-1} r_{t+1},</math>

де <math>r_{t+1}</math> є винагородою, отриманою після <math>t</math>-того переходу, початковий стан вибирається випадково з <math>\mu</math>, а дії обираються стратегією <math>\pi</math>. Тут <math>N</math> позначає (випадковий) час досягнення завершального стану, тобто, час, коли завершується епізод.

У випадку не епізодичних задач віддачу часто ''знецінюють'' ({{lang-en|discount}}),

: <math>R=\sum_{t=0}^\infty \gamma^t r_{t+1},</math>

породжуючи критерій загальної очікуваної знеціненої винагороди. Тут <math>0 \le \gamma \le 1</math> є так званим ''коефіцієнтом знецінювання'' ({{lang-en|discount-factor}}). Оскільки незнецінена віддача є окремим випадком знеціненої віддачі, від цього моменту ми розглядатимемо знецінювання. Хоч це й виглядає безневинним, знецінювання насправді є проблематичним, якщо турбуватися про інтерактивну продуктивність. Це пояснюється тим, що знецінювання робить початкові моменти часу важливішими. Оскільки для агента, що навчається, найправдоподібніше робити помилки протягом перших кількох кроків після початку його «життя», жоден непоінформований алгоритм навчання не може досягти майже оптимальної продуктивності за знецінювання, навіть якщо клас середовищ обмежено скінченними МПУР. (Проте це не означає, що, маючи достатньо часу, агент, що навчається, не зможе з'ясувати, як діяти майже оптимально, якби час було перезапущено.)

То задачею є вказати алгоритм, який можна використовувати для знаходження стратегії з максимальною очікуваною віддачею. З теорії МПУР відомо, що без втрати універсальності пошук може бути обмежено множиною так званих ''постійних'' ({{lang-en|stationary}}) стратегій. Стратегія називається постійною, якщо розподіл дій, який вона повертає, залежить лише від крайнього відвіданого стану (який є частиною історії спостережень агента, згідного нашого спрощувального припущення). Насправді, пошук може бути додатково обмежено ''детерміністичними'' ({{lang-en|deterministic}}) постійними стратегіями. Детерміністична постійна стратегія&nbsp;— це така, яка обирає дії на основі поточного стану детерміністично. Оскільки будь-яку таку стратегію може бути ідентифіковано відображенням з множини станів на множину дій, ці стратегії може бути ідентифіковано такими відображенням без втрати універсальності.

=== Повний перебір ===
=== Повний перебір ===


Підхід {{нп|Пошук повним перебором|повного перебору||Brute-force search}} спричиняє наступні два кроки:
{{Перекласти|en|Reinforcement learning}}

# Для кожної можливої стратегії повертається зразок при слідуванні їй
# Вибрати стратегію з найбільшою очікуваною віддачею

Однією з проблем із цим є те, що число стратегій може бути надзвичайно великим, або навіть нескінченним. Іншою є те, що дисперсія віддач може бути великою, в разі чого для точної оцінки віддачі кожної зі стратегій буде необхідним велике число зразків.

Ці проблеми може бути полегшено, якщо ми припустимо деяку структуру, і, можливо, дозволимо зразкам, породженим з однієї стратегії, впливати на оцінки, зроблені для іншої. Двома головними підходами для досягнення цього є [[#Підходи функції значення|оцінка функції значення]] та [[#Прямий пошук стратегії|прямий пошук стратегії]].

=== Підходи функції значення ===

Підходи функції значення намагаються знайти стратегію, яка максимізує віддачу шляхом підтримки множини оцінок очікуваних віддач для деякої стратегії (зазвичай або «поточної», або оптимальної).

Ці методи покладаються на теорію МПУР, де оптимальність визначається в сенсі, який є суворішим за наведений вище: стратегія називається оптимальною, якщо вона досягає найкращої очікуваної віддачі від ''будь-якого'' початкового стану (тобто початкові розподіли в цьому визначенні не грають ролі). Знов-таки, завжди можна знайти оптимальну стратегію серед постійних стратегій.

Щоби визначити оптимальність формальним чином, визначмо значення стратегії <math>\pi</math> як

: <math> V^{\pi} (s) = E[R|s,\pi],</math>

де <math>R</math> відповідає випадковій віддачі, пов'язаній зі слідуванням <math>\pi</math> з початкового стану <math>s</math>. Визначмо <math>V^*(s)</math> як максимально можливе значення <math>V^\pi(s)</math>, де <math>\pi</math> дозволено змінюватися:

: <math>V^*(s) = \sup \limits_\pi V^{\pi}(s).</math>

Стратегія, яка досягає цих ''оптимальних значень'' в ''кожному'' зі станів, називається ''оптимальною''. Очевидно, що стратегія, яка є оптимальною в цьому суворому сенсі, є також оптимальною й у сенсі того, що вона максимізує очікувану віддачу <math>\rho^\pi</math>, оскільки <math>\rho^\pi = E[ V^\pi(S) ]</math>, де <math>S</math> є станом, який вибирається випадковим чином з розподілу <math>\mu</math>.

Хоч стано-значень і достатньо для визначення оптимальності, виявиться корисним визначити й діє-значення. Для заданих стану <math>s</math>, дії <math>a</math> та стратегії <math>\pi</math> діє-значення пари <math>(s,a)</math> за стратегії <math>\pi</math> визначається як

: <math>Q^\pi(s,a) = E[R|s,a,\pi],\,</math>

де тепер <math>R</math> відповідає випадковій віддачі, пов'язаній зі спершу вчиненням дії <math>a</math> в стані <math>s</math>, а потім слідуванням <math>\pi</math>.

З теорії МПУР добре відомо, що якщо хтось дасть нам <math>Q</math> для оптимальної стратегії, то ми можемо завжди обирати оптимальні дії (і відтак діяти оптимально), просто обираючи в кожному стані дію з найбільшим значенням. ''Функція діє-значення'' такої оптимальної стратегії називається ''оптимальною функцією діє-значення'', і позначається через <math>Q^*</math>. В підсумку, знання ''самої лише'' оптимальної функції діє-значення достатнє для того, щоби знати, як діяти оптимально.

Виходячи з повного знання МПУР, існують два основні підходи для обчислення оптимальної функції діє-значення, {{нп|ітерація за значеннями|||Value iteration}} та {{нп|ітерація за стратегіями|||Policy iteration}}. Обидва ці алгоритми обчислюють послідовність функцій <math>Q_k</math> (<math>k=0,1,2,\ldots</math>), яка збігається до <math>Q^*</math>. Обчислення цих функцій включає обчислення математичних сподівань над усім простором станів, що є непрактичним для всіх, крім найменших (скінченних) МПУР, не кажучи вже про випадок, коли МПУР є невідомим. В методах навчання з підкріпленням математичні сподівання наближуються шляхом усереднення над зразками, а щоби впоратися з необхідністю представлення функцій значень над великими просторами станів-дій, застосовуються методики наближення функцій.

==== Методи Монте-Карло ====

В алгоритмі, який імітує ітерацію за стратегіями, можуть застосовуватися найпростіші [[Метод Монте-Карло|методи Монте-Карло]]. Ітерація за стратегіями складається з двох кроків: ''оцінки стратегії'' ({{lang-en|policy evaluation}}) та ''вдосконалення стратегії'' ({{lang-en|policy improvement}}).

Методи Монте-Карло використовуються на кроці оцінки стратегії. На цьому кроці метою є для заданої постійної детерміністичної стратегії <math>\pi</math> обчислити значення функції <math>Q^\pi(s,a)</math> (або їхнє добре наближення) для всіх пар стан-дія <math>(s,a)</math>. Припустімо (для спрощення), що МПУР є скінченним, і що таблиця, яка представляє діє-значення, фактично вміщається до пам'яті. Далі, припустімо, що ця задача є епізодичною, і що після кожного епізоду починається новий, з якогось випадкового початкового стану. Тоді оцінку значення заданої пари стан-дія <math>(s,a)</math> може бути обчислено просто усередненням над часом вибраних віддач, породжених з <math>(s,a)</math>. За достатньої кількості часу ця процедура може відтак побудувати точну оцінку <math>Q</math> функції діє-значення <math>Q^\pi</math>. Це завершує опис кроку оцінки стратегії.

На кроці вдосконалення стратегії, як це робиться й у стандартному алгоритмі ітерації за стратегіями, наступну стратегію отримують обчисленням ''жадібної'' ({{lang-en|greedy}}) стратегії з урахуванням <math>Q</math>: для заданого стану <math>s</math> ця нова стратегія повертає дію, яка максимізує <math>Q(s,\cdot)</math>. На практиці часто уникають обчислення та зберігання цієї нової стратегії, застосовуючи натомість [[ліниві обчислення]], щоби відкласти обчислення максимізувальних дій до того моменту, коли вони дійсно стануть потрібні.

Ця процедура має деякі перелічені нижче проблеми:

* Ця процедура може марнувати забагато часу на оцінку недооптимальної стратегії;
* Вона використовує зразки неефективно, оскільки використовує довгу траєкторію для поліпшення оцінки лише ''однієї'' пари стан-дія, яка почала цю траєкторію;
* Якщо віддачі вздовж траєкторій мають ''високу дисперсію'', то збіжність буде повільною;
* Вона працює ''лише на епізодичних задачах'';
* Вона працює ''лише на невеликих скінченних МПУР''.

==== Методи часових різниць ====

Перша проблема легко виправляється, якщо дозволити процедурі змінювати стратегію (взагалі, або на деяких станах) до встановлення значення. Проте, як добре б це не звучало, це може бути проблематичним, оскільки воно може перешкоджати збіганню. Тим не менше, більшість поточних алгоритмів реалізують цю ідею, породжуючи клас алгоритмів ''узагальненої ітерації за стратегіями'' ({{lang-en|generalized policy iteration}}). Зауважимо принагідно, що до цієї категорії належать {{нп|Метод критика діяча|методи критика діяча||Actor critic}}.{{sfn|Sutton|Barto|1998|loc=[https://webdocs.cs.ualberta.ca/~sutton/book/ebook/node66.html §6.6 Actor-Critic Methods]}}

Другу проблему можна виправити в алгоритмі, дозволивши траєкторіям робити внесок до будь-якої пари стан-дія в них. Це також може допомогти певною мірою і з третьою проблемою, хоча кращим рішенням в разі великої дисперсії віддач є застосування методів {{нп|Метод часових різниць|часових різниць||Temporal difference learning}} (ЧР, {{lang-en|temporal difference, TD}}) {{нп|Річард Саттон|Саттона||Richard S. Sutton}}{{sfn|Sutton|1984}}{{sfn|Sutton|Barto|1998|loc=[https://webdocs.cs.ualberta.ca/~sutton/book/ebook/node60.html §6. Temporal-Difference Learning]}}, які ґрунтуються на рекурсивному {{нп|Рівняння Беллмана|рівнянні Беллмана||Bellman equation}}. Зауважте, що обчислення в методах ЧР можуть бути інкрементними ({{lang-en|incremental}}, коли після кожного переходу пам'ять змінюється, а перехід викидається) або пакетними ({{lang-en|batch}}, коли переходи збираються, а потім оцінки обчислюються один раз на основі великого числа переходів). Пакетні методи, яскравим прикладом яких є {{нп|метод найменших квадратів часових різниць|||least-squares temporal difference method}} {{нп|Стівен Брадтке|Брадтке||Steven J. Bradtke}} та {{нп|Ендрю Барто|Барто||Andrew Barto}},{{sfn|Bradtke|Barto|1996}} можуть краще використовувати інформацію в зразках, тоді як інкрементні методи є єдиним вибором, коли пакетні методи стають нездійсненними з причини своєї високої обчислювальної складності або вимог до пам'яті. Крім того, існують методи, які намагаються поєднувати переваги цих двох підходів. Методи на основі часових різниць також долають другу, але не останню проблему.

Для розв'язання останньої проблеми, згаданої в попередньому розділі, застосовуються ''методи наближення функцій'' ({{lang-en|function approximation methods}}). В ''лінійному наближенні функції'' починають з відображення <math>\phi</math>, яке ставить у відповідність кожній парі стан-дія скінченновимірний вектор. А потім значення дій пари стан-дія <math>(s,a)</math> отримуються шляхом лінійного об'єднання складових <math>\phi(s,a)</math> з деякими ''вагами'' ({{lang-en|weights}}) <math>\theta</math>:

: <math>Q(s,a) = \sum \limits_{i=1}^d \theta_i \phi_i(s,a)</math>.

Потім алгоритми підлаштовують ці ваги, замість підлаштовувати значення, пов'язані з конкретними парами стан-значення. Проте лінійне наближення функції не є єдиним вибором. Зовсім недавно було досліджено методи, засновані на ідеях {{нп|Непараметрична статистика|непараметричної статистики||Nonparametric statistics}} (яку можна розглядати як таку, яка будує свої власні ознаки).

Досі обговорення було обмежено тим, як в якості основи проектування алгоритмів навчання з підкріпленням можна застосовувати ітерацію за стратегіями. Не менш важливим є те, що в якості відправної точки можна застосовувати й ітерацію за значеннями, що веде до алгоритму [[Q-навчання|''Q''-навчання]]{{sfn|Watkins|1989}} та багатьох його варіантів.

Проблема з методами, які використовують діє-значення, в тому, що вони можуть потребувати дуже точних оцінок значень порівнюваних дій, що може бути важко отримувати при зашумлених віддачах. І хоч ця проблема й пом'якшується до деякої міри методами часових різниць та застосуванням так званого методу сумісного наближення функції ({{lang-en|compatible function approximation method}}), належить зробити ще більше роботи для підвищення універсальності та ефективності. Ще одна проблема, властива методам часових різниць, випливає з їхньої залежності від рекурсивного рівняння Беллмана. Більшість методів часових різниць мають так званий параметр <math>\lambda</math> <math>(0\le \lambda\le 1)</math>, який дозволяє здійснювати безперервну інтерполяцію між методами Монте-Карло (які не залежать від рівнянь Беллмана) та базовими методами часових різниць (які повністю покладаються на рівняння Беллмана), що, відтак, може бути ефективним для пом'якшення цієї проблеми.

=== Прямий пошук стратегії ===

Альтернативним методом пошуку доброї стратегії може бути прямий пошук у (деякій підмножині) простору стратегій, і в цьому випадку задача стає прикладом {{нп|Стохастична оптимізація|стохастичної оптимізації||Stochastic optimization}}. Двома доступними підходами є методи на основі градієнту та безградієнтні методи.

Методи на основі градієнту (які породжують так звані ''методи градієнту стратегії'', {{lang-en|policy gradient methods}}) починаються з відображення зі скінченновимірного простору (параметрів) на простір стратегій: для заданого вектору параметрів <math>\theta</math> нехай <math>\pi_\theta</math> позначає стратегію, пов'язану з <math>\theta</math>. Визначмо функцію продуктивності як

: <math>\rho(\theta) = \rho^{\pi_\theta}.</math>

За м'яких умов ця функція буде диференційовною як функція вектору параметрів <math>\theta</math>. Якби градієнт <math>\rho</math> був відомим, то можна було би застосовувати [[градієнтний спуск]]. Оскільки аналітичний вираз градієнту відсутній, мусимо покладатися на зашумлену оцінку. Таку оцінку може бути побудовано багатьма способами, що породжують такі алгоритми, як метод ''REINFORCE'' {{нп|Рональд Вільямс|Вільямса||Ronald J. Williams}}{{sfn|Williams|1987}} (що також відомий в літературі з {{нп|Оптимізація на основі імітації|оптимізації на основі імітації||Simulation-based optimization}} як {{нп|метод відношення правдоподібностей|||likelihood ratio method}}). Методи градієнту стратегії отримали багато уваги в останні пару років,<ref>наприклад, {{harvnb|Peters|Vijayakumar|Schaal|2003}}</ref> але продовжують залишатися полем активної діяльності. Огляд методів градієнту стратегії було запропоновано Дайзенротом, Нейманом та Петерсом.{{sfn|Deisenroth|Neumann|Peters|2013}} Проблема багатьох із цих методів у тому, що вони можуть застрягати в локальних оптимумах (оскільки вони ґрунтуються на [[Локальний пошук (оптимізація)|локальному пошукові]]).

Існує великий клас методів, які уникають покладання на інформацію про градієнт. Вони включають [[Імітація відпалу|імітацію відпалу]], [[метод перехресної ентропії]] та методи [[Еволюційне моделювання|еволюційного обчислення]]. Багато безградієнтних методів можуть досягати глобального оптимуму (в теорії та на границі). В ряді випадків вони дійсно показали визначну продуктивність.

Проблема методів пошуку стратегії в тому, що вони можуть збігатися повільно, якщо інформація, на основі якої вони діють, є зашумленою. Наприклад, це відбувається тоді, коли в епізодичних задачах траєкторії є довгими, а дисперсія віддач є великою. Як було зазначено вище, в такому випадку можуть допомогти методи на основі функції значення, які покладаються на часові різниці. В останні роки було запропоновано декілька алгоритмів діяча&nbsp;— критика, які слідують цій ідеї, і було показано, що вони працюють добре на різних задачах.

== Теорія ==

Теорія для невеликих скінченних МПУР є цілком зрілою. Поведінка як асимптотичних алгоритмів, так і алгоритмів зі скінченною вибіркою, є добре вивченою. Як було зазначено вище, алгоритми з довідно доброю інтерактивною продуктивністю (спрямовані на розв'язання задачі дослідження) є відомими.

Теорія великих МПУР потребує подальшої праці. Дієве дослідження є здебільшого недосягнутим (крім випадку задач бандита). І хоча останніми роками для багатьох алгоритмів з'явилися скінченно-часові обмеження виконання, ці обмеження, як очікується, є доволі слабкими, і відтак для кращого розуміння як відносних переваг, так і обмежень цих алгоритмів, необхідна подальша праця.

Питання асимптотичної збіжності для інкрементних алгоритмів було розв'язано. Нещодавно з'явилися нові інкрементні алгоритми на основі часових різниць, які збігаються за значно ширшого набору умов, ніж було можливо раніше (наприклад, при застосуванні з довільним гладким наближенням функції).

== Поточні дослідження ==

Актуальні теми дослідження включають:
адаптивні методи, які працюють з меншою кількістю (або без) параметрів за великого числа умов,
спрямування на задачу дослідження у великих МПУР,
великомасштабні емпіричні оцінки,
навчання та дію за {{нп|Частково спостережувані марковські процеси ухвалення рішень|часткової інформації||Partially observable Markov decision process}} (наприклад, із застосуванням {{нп|Передбачувальне представлення стану|передбачувального представлення стану||Predictive state representation}}),
модульне та ієрархічне навчання з підкріпленням,
вдосконалення наявних методів функції значення та пошуку стратегії,
алгоритми, які працюють добре з великими (або безперервними) просторами дій,
{{нп|передавальне навчання|||transfer learning}},
безперервне навчання ({{lang-en|lifelong learning}}),
ефективне планування на основі зразків (наприклад, на основі {{нп|Деревний пошук Монте-Карло|деревного пошуку Монте-Карло||Monte Carlo tree search}}).
Предметом зацікавлення в сучасних дослідженнях також є поліагентне ({{lang-en|Multiagent}}) або розподілене навчання з підкріпленням ({{lang-en|Distributed Reinforcement Learning}}). Також зростає зацікавлення до застосувань навчання з підкріпленням в реальному житті. Успіхи навчання з підкріпленням збирають [http://umichrl.pbworks.com/Successes-of-Reinforcement-Learning/ тут] і [http://rl-community.org/wiki/Successes_Of_RL тут].

Алгоритми навчання з підкріпленням, такі як ЧР, було також досліджувано як модель навчання в мозку на основі [[дофамін]]у. В цій моделі дофамінергійні проекції з {{нп|Чорна субстанція|чорної субстанції||Substantia nigra}} на [[базальні ганглії]] діють як похибка передбачення. Навчання з підкріпленням також використовували як частину моделі набування навичок людиною, особливо у відношенні взаємодії між неявним та явним навчанням при набуванні навичок (перша публікація про це застосування була в 1995—1996 роках, і було багато наступних досліджень).<ref>Докладніше про ці області дослідження див. http://webdocs.cs.ualberta.ca/~sutton/RL-FAQ.html#behaviorism {{ref-en}}</ref>

== Реалізації ==

* [http://glue.rl-community.org/ RL-Glue] пропонує стандартний інтерфейс, який дозволяє з'єднувати разом агентів, середовища та програми експериментів, навіть якщо їх написано різними мовами.
* [http://mmlf.sourceforge.net/ Maja Machine Learning Framework] (MMLF)&nbsp;— це універсальний каркас для задач області навчання з підкріпленням, написаний мовою [[Python]].
* [http://jamh-web.appspot.com/download.htm Програмні інструменти для навчання з підкріпленням] ([[Matlab]] та Python)
* [http://www.pybrain.org/ PyBrain] (Python)
* [http://servicerobotik.hs-weingarten.de/en/teachingbox.php TeachingBox]&nbsp;— це каркас навчання з підкріпленням на [[Java]], який підтримує багато функцій, таких як {{нп|Мережа радіально-базисних функцій|мережі РБФ||Radial basis function network}}, методи навчання градієнтним спуском, …
* [http://webdocs.cs.ualberta.ca/~vanhasse/code.html Реалізації мовами C++ та Python] деяких добре відомих алгоритмів навчання з підкріпленням із первинним кодом.
* {{нп|Orange (програмне забезпечення)|Orange||Orange (software)}}, безкоштовний програмний пакет добування даних, модуль [http://www.ailab.si/orange/doc/modules/orngReinforcement.htm orngReinforcement]
* [http://www.ias.informatik.tu-darmstadt.de/Research/PolicyGradientToolbox Policy Gradient Toolbox] пропонує пакет для навчання підходів градієнту стратегії.
* [http://burlap.cs.brown.edu BURLAP]&nbsp;— це відкрита бібліотека Java, яка пропонує широкий спектр методів одно- та поліагентного навчання й планування.

== Зворотне навчання з підкріпленням ==

У зворотному навчанні з підкріпленням ({{lang-en|inverse reinforcement learning, IRL}}) функція винагороди не надається. Натомість намагаються добути стратегію із заданої спостережуваної поведінки, щоби наслідувати спостережувану поведінку, яка є часто оптимальною або близькою до оптимальної. Оскільки агент, який навчається зворотним навчанням з підкріпленням, щойно він відхилився від шляху, яким слідує спостережувана поведінка, часто потребує якогось способу повернутися назад на цей шлях, щоби його власна поведінка була {{нп|Теорія стійкості|стійкою||Stability theory}}, то іноді необхідно продемонструвати поведінку декілька разів із невеликими збуреннями кожного разу.

У {{нп|Підмайстрове навчання|підмайстровому навчанні||Apprenticeship learning}} припускають, що експерт, який демонструє поведінку, намагається максимізувати функцію винагороди, і намагаються розкрити невідому функцію винагороди експерта.

== Див. також ==

* {{нп|Метод часових різниць|||Temporal difference learning}}
* [[Q-навчання|''Q''-навчання]]
* {{нп|Стан-дія-винагорода-стан-дія|||State-Action-Reward-State-Action}} ({{lang-en|SARSA}})
* {{нп|Фіктивна гра|||Fictitious play}} ({{lang-en|Fictitious play}})
* {{нп|Система навчання класифікації|||Learning classifier system}} ({{lang-en|Learning classifier system}})
* [[Оптимальне керування]]
* {{нп|Динамічний режим лікування|||Dynamic treatment regime}}
* {{нп|Навчання, кероване похибками|||Error-driven learning}} ({{lang-en|Error-driven learning}})
* [[Поліагентна система]]
* {{нп|Розподілений штучний інтелект|||Distributed artificial intelligence}}

== Примітки ==
{{Примітки}}

== Джерела ==
{{more footnotes|date=серпень 2016}}
* {{cite thesis
| last = Sutton | first = Richard S. | authorlink = Річард Саттон
| degree= PhD
| title= Temporal Credit Assignment in Reinforcement Learning
| year= 1984
| publisher = University of Massachusetts, Amherst, MA
| url= http://webdocs.cs.ualberta.ca/~sutton/publications.html#PhDthesis
| ref= harv}} {{ref-en}}
* {{cite conference
| last = Williams | first = Ronald J. | authorlink = Рональд Вільямс
| title = A class of gradient-estimating algorithms for reinforcement learning in neural networks
| booktitle = Proceedings of the IEEE First International Conference on Neural Networks
| year = 1987
| url = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.129.8871
| ref = harv}} {{ref-en}}
* {{cite journal
| doi = 10.1007/BF00115009
| last = Sutton | first = Richard S. | authorlink = Річард Саттон
| title = Learning to predict by the method of temporal differences
| journal = Machine Learning
| volume = 3
| pages = 9–44
| publisher = Springer
| year = 1988
| url = http://webdocs.cs.ualberta.ca/~sutton/publications.html#TD_paper
| ref = harv}} {{ref-en}}
* {{cite thesis
| last = Watkins | first = Christopher J.C.H. | authorlink = Крістофер Воткінс
| degree= PhD
| title= Learning from Delayed Rewards
| year= 1989
| publisher = King’s College, Cambridge, UK
| url= http://www.cs.rhul.ac.uk/~chrisw/new_thesis.pdf
| ref = harv}} {{ref-en}}
* {{cite journal
| doi = 10.1023/A:1018056104778
| last1 = Bradtke | first1 = Steven J. | authorlink1 = Стівен Брадтке
| last2 = Barto | first2 = Andrew G. | authorlink2 = Ендрю Барто
| title = Learning to predict by the method of temporal differences
| journal = Machine Learning
| volume = 22
| pages = 33–57
| publisher = Springer
| year = 1996
| url = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.143.857
| ref = harv}} {{ref-en}}
* {{cite book
| last1 = Bertsekas | first1 = Dimitri P. | authorlink1 = Дімітрі Берцекас
| last2 = Tsitsiklis | first2 = John | authorlink2 = Джон Цицикліс
| title = Neuro-Dynamic Programming
| publisher = Athena Scientific
| year = 1996
| location = Nashua, NH
| isbn = 1-886529-10-8
| url = http://www.athenasc.com/ndpbook.html
| ref = harv}} {{ref-en}}
* {{cite journal
| last1 = Kaelbling | first1 = Leslie P. | authorlink1 = Леслі Келблін
| last2 = Littman | first2 = Michael L. | authorlink2 = Майкл Літман
| last3 = Moore | first3 = Andrew W. | authorlink3 = Ендрю Мур
| title = Reinforcement Learning: A Survey
| journal = Journal of Artificial Intelligence Research
| volume = 4
| pages = 237–285
| publisher =
| year = 1996
| url = http://www.cs.washington.edu/research/jair/abstracts/kaelbling96a.html
| ref = harv}} {{ref-en}}
* {{cite book
| last1 = Sutton | first1 = Richard S. | authorlink1 = Річард Саттон
| last2 = Barto | first2 = Andrew G. | authorlink2 = Ендрю Барто
| title = Reinforcement Learning: An Introduction
| publisher = MIT Press
| year = 1998
| isbn = 0-262-19398-1
| pages =
| url = http://webdocs.cs.ualberta.ca/~sutton/book/the-book.html
| ref = harv}} {{ref-en}}
* {{cite book
| last = Gosavi | first = Abhijit | authorlink = Абгіджіт Госаві
| title = Simulation-based Optimization: Parametric Optimization Techniques and Reinforcement
| publisher = Springer
| year = 2003
| isbn = 1-4020-7454-9
| pages =
| url = http://www.springer.com/mathematics/applications/book/978-1-4020-7454-7
| ref = harv}} {{ref-en}}
* {{cite conference
| last1 = Peters | first1 = Jan | authorlink1 = Ян Петерс (дослідник)
| last2 = Vijayakumar | first2 = Sethu | authorlink2 = Сету Віджаякумар
| last3 = Schaal | first3 = Stefan | authorlink3 = Стефан Шааль
| title = Reinforcement Learning for Humanoid Robotics
| booktitle = IEEE-RAS International Conference on Humanoid Robots
| year = 2003
| url = http://www-clmc.usc.edu/publications/p/peters-ICHR2003.pdf
| ref = harv}} {{ref-en}}
* {{cite book
| last = Powell | first = Warren
| title = Approximate dynamic programming: solving the curses of dimensionality
| year = 2007
| publisher = Wiley-Interscience
| isbn = 0-470-17155-3
| url = http://www.castlelab.princeton.edu/adp.htm
| ref = harv}} {{ref-en}}
* {{cite journal
| last1 = Auer | first1 = Peter | authorlink1 = Петер Ауер
| last2 = Jaksch | first2 = Thomas | authorlink2 = Томас Якш
| last3 = Ortner | first3 = Ronald | authorlink3 = Рональд Ортнер
| title = Near-optimal regret bounds for reinforcement learning
| journal = Journal of Machine Learning Research
| volume = 11
| pages = 1563–1600
| publisher =
| year = 2010
| url = http://jmlr.csail.mit.edu/papers/v11/jaksch10a.html
| ref = harv}} {{ref-en}}
* {{cite conference
| last1 = Szita | first1 = Istvan | authorlink1 = Іштван Сіта
| last2 = Szepesvari | first2 = Csaba | authorlink2 = Чаба Сепешварі
| title = Model-based Reinforcement Learning with Nearly Tight Exploration Complexity Bounds
| year = 2010
| publisher = Omnipress
| booktitle = ICML 2010
| pages = 1031–1038
| url = http://www.icml2010.org/papers/546.pdf
| ref = harv}} {{ref-en}}
* {{cite book
| last = Bertsekas | first = Dimitri P. | authorlink = Дімітрі Берцекас
| title= Dynamic Programming and Optimal Control
|date=August 2010
| edition = 3
| volume = II
| chapter = Chapter 6 (online): Approximate Dynamic Programming
| url= http://web.mit.edu/dimitrib/www/dpchapter.pdf
| ref = harv}} {{ref-en}}
* {{cite book
| last1 = Busoniu | first1 = Lucian | authorlink1 = Лучіан Бушон'ю
| last2 = Babuska | first2 = Robert | authorlink2 = Роберт Бабушка
| last3 = De Schutter | first3 = Bart | authorlink3 = Барт де Шутер
| last4 = Ernst | first4 = Damien | authorlink4 = Дам'єн Ернст
| title = Reinforcement Learning and Dynamic Programming using Function Approximators
| publisher = Taylor & Francis CRC Press
| year = 2010
| isbn = 978-1-4398-2108-4
| pages =
| url = http://www.dcsc.tudelft.nl/rlbook/
| ref = harv}} {{ref-en}}
* {{Cite book
| publisher = NOW Publishers
| volume = 2
| pages = 1–142
| last1 = Deisenroth | first1 = Marc Peter | authorlink1 = Марк Петер Дайзенрот
| last2 = Neumann | first2 = Gerhard | authorlink2 = Герхард Нейман
| last3 = Peters | first3 = Jan | authorlink3 = Ян Петерс (дослідник)
| title = A Survey on Policy Search for Robotics
| series = Foundations and Trends in Robotics
| url = http://hdl.handle.net/10044/1/12051
| year = 2013
| ref = harv}} {{ref-en}}

== Література ==

=== Конференції, журнали ===

Більшість праць із навчання з підкріпленням публікуються на головних конференціях ({{нп|ICML}}, {{нп|NIPS}}, [[AAAI]], [[IJCAI]], {{нп|UAI|||Uncertainty in Artificial Intelligence}}, AI and Statistics) та в журналах ([http://www.jair.org JAIR], [http://www.jmlr.org JMLR], [http://www.springer.com/computer/ai/journal/10994 Machine learning journal], [http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=4804728 IEEE T-CIAIG]) з машинного навчання та [[ШІ]]. Деякі теоретичні праці публікуються на {{нп|COLT|||Conference on Learning Theory}} та {{нп|ALT|||Association for Learning Technology}}. Тим не менше, багато праць з'являються на конференціях із робототехніки ({{нп|IROS}}, {{нп|ICRA|||International Conference on Robotics and Automation}}) та на «агентній» конференції {{нп|AAMAS}}. Дослідники операцій публікують свої праці на конференції {{нп|INFORMS}} і, наприклад, в журналах [http://or.pubs.informs.org Operation Research] та [http://mor.pubs.informs.org Mathematics of Operations Research]. Дослідники керування публікують свої праці на конференціях CDC та ACC, або, наприклад, у журналах [http://www.nd.edu/~ieeetac/ IEEE Transactions on Automatic Control] та [http://www.elsevier.com/locate/automatica Automatica], хоча прикладні праці тяжіють до публікації в більш спеціалізованих журналах. [http://www.wintersim.org/ Winter Simulation Conference] також публікує багато відповідних документів. Крім цього, праці також публікуються на головних конференціях спільнот із нейронних мереж, нечітких та еволюційних обчислень. Щорічний симпозіум IEEE під назвою Approximate Dynamic Programming and Reinforcement Learning (ADPRL) та щодворічний семінар European Workshop on Reinforcement Learning ([http://ewrl.wordpress.com/ EWRL]) є двома регулярними зустрічами, на яких зустрічаються дослідники навчання з підкріпленням.


== Посилання ==
{{Statistics-stub}}
* [http://webdocs.cs.ualberta.ca/~sutton/book/the-book.html Веб-сайт книги ''Reinforcement Learning: An Introduction''] (1998) {{нп|Річард Саттон|Річа Саттона||Richard S. Sutton}} та {{нп|Ендрю Барто|||Andrew Barto}}, MIT Press, включає посилання на html-версію цієї книги. {{ref-en}}
{{AI-stub}}
* [http://www-anw.cs.umass.edu/rlr/ Reinforcement Learning Repository] {{ref-en}}
* [http://spaces.facsci.ualberta.ca/rlai/ Reinforcement Learning and Artificial Intelligence] (RLAI, лабораторія Річа Саттона в [[Альбертський університет|Альбертському університеті]]) {{ref-en}}
* [http://www-all.cs.umass.edu/ Autonomous Learning Laboratory] (ALL, лабораторія Ендрю Барто в {{нп|Університет Массачусетса в Амхерсті|Університеті Массачусетса в Амхерсті||University of Massachusetts Amherst}}) {{ref-en}}
* [http://glue.rl-community.org RL-Glue]
* [http://jamh-web.appspot.com/download.htm Програмні інструменти для навчання з підкріпленням] (Matlab та Python)
* [http://www.igi.tugraz.at/ril-toolbox The Reinforcement Learning Toolbox] від {{нп|Грацський технічний університет|Грацського технічного університету||Graz University of Technology}}
* [http://www.cogsci.rpi.edu/~rsun/hybrid-rl.html Гібридне навчання з підкріпленням] ({{lang-en|Hybrid reinforcement learning}}) {{ref-en}}
* [http://sourceforge.net/projects/piqle/ Piqle: a Generic Java Platform for Reinforcement Learning]
* [http://webdocs.cs.ualberta.ca/~vanhasse/rl_algs/rl_algs.html Коротке введення до деяких алгоритмів навчання з підкріпленням] {{ref-en}}
* [http://www.lwebzem.com/cgi-bin/ttt/ttt.html Застосування навчання з підкріпленням до гри в хрестики-нулики] ([[Perl]])
* [http://www.scholarpedia.org/article/Reinforcement_Learning Scholarpedia Reinforcement Learning] {{ref-en}}
* [http://www.scholarpedia.org/article/Temporal_difference_learning Scholarpedia Temporal Difference Learning] {{ref-en}}
* [http://www.troovoo.com/vid.php?a=Stanford&c=Machine+Learning&l=Applications+of+Reinforcement+Learning Стендфордський курс із навчання з підкріпленням] {{ref-en}}
* [http://www.dcsc.tudelft.nl/~robotics/media.html Реальні експерименти з навчання з підкріпленням] в [[Делфтський технічний університет|Делфтському технічному університеті]]
* [http://busoniu.net/repository.php Інструменти машинного навчання для Matlab]
* [https://www.youtube.com/watch?v=RtxI449ZjSc&feature=relmfu Ленція Ендрю Ина з навчання з підкріпленням у Стендфордському університеті] {{ref-en}}


[[Категорія:Статистичні моделі]]
[[Категорія:Статистичні моделі]]

Версія за 22:04, 27 серпня 2016

Про підкріплення в психології див. Підкріплення[en] та Навчання методом проб, помилок[en]
Частина з циклу
Машинне навчання
та добування даних
Ілюстрація нейронної мережі з темним

Навчання з підкріпленням (англ. reinforcement learning) — це галузь машинного навчання, натхнена біхевіористською психологією, що займається питанням про те, які дії● (англ. actions) повинні виконувати програмні агенти в певному середовищі (англ. environment) задля максимізації деякого уявлення про сукупну винагороду (англ. reward). Через її універсальність, дану задачу вивчають і багато інших дисциплін, таких як теорія ігор, теорія керування, дослідження операцій, теорія інформації, оптимізація на основі моделювання●, поліагентні системи, колективний інтелект, статистика та генетичні алгоритми. В літературі про дослідження та керування операціями галузь, що займається навчанням з підкріпленням, називається наближеним динамічним програмуванням (англ. approximate dynamic programming). Задачу навчання з підкріпленням було досліджувано теорією оптимального керування, проте більшість досліджень стосувалися саме існування оптимальних рішень та їх характеристики, а не аспектів навчання чи наближення. В економіці та теорії ігор навчання з підкріпленням може використовуватись для пояснення того, як може виникати рівновага за обмеженої раціональності●.

В машинному навчанні середовище зазвичай формулюється як марковський процес ухвалення рішень● (МПУР, англ. Markov decision process, MDP), оскільки багато алгоритмів навчання з підкріпленням для цього контексту використовують методики динамічного програмування. Основна відмінність між класичними методиками й алгоритмами навчання з підкріпленням полягає в тому, що останні не потребують знання про МПУР, і вони орієнтовані на великі МПУР, в яких точні методи стають нездійсненними.

Навчання з підкріпленням відрізняється від стандартного навчання з учителем тим, що пари правильних входів/виходів ніколи не представляються, а недостатньо оптимальні дії явно не виправляються. Крім того, є акцент на інтерактивній продуктивності, який включає знаходження балансу між дослідженням (незвіданої території, англ. exploration) та використанням (поточного знання, англ. exploitation). Компроміс між дослідженням та використанням у навчанні з підкріпленням найретельніше вивчався через задачу багаторукого бандита● та скінченні МПУР.

Введення

Базова модель навчання з підкріпленням складається з:

  1. множини станів середовища ;
  2. множини дій ;
  3. правил переходу між станами;
  4. правил, які визначають скалярну безпосередню винагороду (англ. scalar immediate reward) переходу; і
  5. правил, які описують, що спостерігає агент.

Ці правила часто є стохастичними. Спостереження зазвичай включає в себе скалярну безпосередню винагороду, пов'язану з крайнім переходом. У багатьох працях також вважають, що агент спостерігає поточний стан середовища, в разі чого говорять про повну спостережуваність (англ. full observability), тоді як в іншому разі говорять про часткову спостережуваність (англ. partial observability). Іноді множина доступних агентові дій є обмеженою (наприклад, ви не можете витрачати більше грошей, ніж маєте).

Агент навчання з підкріпленням взаємодіє зі своїм середовищем у дискретні моменти часу. В кожен момент часу агент отримує спостереження , яке зазвичай включає винагороду . Потім він обирає дію з множини доступних дій, яка відтак відправляється до середовища. Середовище переходить до нового стану , і визначається винагорода , пов'язана з переходом (англ. transition) . Метою агента навчання з підкріпленням є збирати якомога більше винагороди. Агент може обирати будь-яку дію як функцію історії, і може навіть робити свій вибір дії● випадковим.

Коли продуктивність агента порівнюється з продуктивністю агента, який діє оптимально від початку, то різниця в продуктивності призводить до поняття жалю (англ. regret). Зверніть увагу, що, щоби діяти майже оптимально, агент мусить розуміти довготермінові наслідки своїх дій: щоби максимізувати свій майбутній дохід, мені краще зараз піти до школи, хоча пов'язана з цим безпосередня грошова винагорода може бути від'ємною.

Таким чином, навчання з підкріпленням є особливо добре пристосованим для задач, які включають компроміс між довготерміновою та короткотерміновою винагородою. Його було успішно застосовувано до різноманітних задач, включно з керуванням роботами[en], розкладами для ліфтів, телекомунікаціями, нардами, шашками[1] та ґо (AlphaGo).

Потужним навчання з підкріпленням роблять дві складові: використання зразків для оптимізації продуктивності, та застосування наближень функцій, щоби мати справу з великими середовищами. Завдяки цим двом складовим навчання з підкріпленням можливо застосовувати у великих середовищах в будь-яких із наступних ситуацій:

  • Модель середовища є відомою, але аналітичний розв'язок відсутній;
  • Задано лише імітаційну модель середовища (предмет оптимізації на основі імітації●);[2]
  • Єдиним способом збирання інформації про середовище є взаємодія з ним.

Перші дві з цих задач можливо розглядати як задачі планування (оскільки модель в якомусь вигляді існує), тоді як останню можливо розглядати як справжню задачу навчання. Проте за методології навчання з підкріпленням обидві задачі планування може бути перетворено на задачі машинного навчання.

Дослідження

Описана задача навчання з підкріпленням вимагає розумних механізмів дослідження. Відомо, що випадковий вибір дій без прив'язки до оцінюваного розподілу ймовірності викликає дуже погану продуктивність. Випадок (невеликих) скінченних МПУР в даний час є відносно добре вивченим. Проте через брак алгоритмів, які б довідно добре масштабувалися з числом станів (або масштабувалися до задач з нескінченними просторами станів), на практиці люди вдаються до простих методів дослідження. Одним із таких методів є -жадібний, коли агент вибирає дію, яка за його переконанням має найкращий довготермінових ефект, з імовірністю , а інакше вибирає дію рівномірно випадково. Тут є параметром налаштування, який іноді змінюється, або згідно фіксованого розкладу (роблячи так, що агент з плином часу досліджує менше), або адаптивно на основі якихось евристик.

Алгоритми для навчання керуванню

Навіть якщо питання дослідження не береться до уваги, і навіть якщо стан можна було спостерігати (що ми припускаємо, з цього моменту), лишається задача з'ясування на основі попереднього досвіду, які дії є добрими.

Критерій оптимальності

Для спрощення на хвилинку припустімо, що досліджувана задача є епізодичною (англ. episodic), із завершенням епізоду при досягненні деякого завершального стану (англ. terminal state). Припустімо далі, що незалежно від того, який план дій обирає агент, завершення є неминучим. За деяких додаткових м'яких умов закономірності математичне сподівання повної винагороди є добре визначеним для будь-якої стратегії та будь-якого початкового розподілу над станами. Тут стратегія (англ. policy) позначає відображення, яке призначає деякий розподіл імовірності над діями всім можливим історіям.

Таким чином, для заданого зафіксованого початкового розподілу ми можемо поставити у відповідність стратегії очікувану віддачу :

де випадкова величина позначає віддачу (англ. return), і визначається як

де є винагородою, отриманою після -того переходу, початковий стан вибирається випадково з , а дії обираються стратегією . Тут позначає (випадковий) час досягнення завершального стану, тобто, час, коли завершується епізод.

У випадку не епізодичних задач віддачу часто знецінюють (англ. discount),

породжуючи критерій загальної очікуваної знеціненої винагороди. Тут є так званим коефіцієнтом знецінювання (англ. discount-factor). Оскільки незнецінена віддача є окремим випадком знеціненої віддачі, від цього моменту ми розглядатимемо знецінювання. Хоч це й виглядає безневинним, знецінювання насправді є проблематичним, якщо турбуватися про інтерактивну продуктивність. Це пояснюється тим, що знецінювання робить початкові моменти часу важливішими. Оскільки для агента, що навчається, найправдоподібніше робити помилки протягом перших кількох кроків після початку його «життя», жоден непоінформований алгоритм навчання не може досягти майже оптимальної продуктивності за знецінювання, навіть якщо клас середовищ обмежено скінченними МПУР. (Проте це не означає, що, маючи достатньо часу, агент, що навчається, не зможе з'ясувати, як діяти майже оптимально, якби час було перезапущено.)

То задачею є вказати алгоритм, який можна використовувати для знаходження стратегії з максимальною очікуваною віддачею. З теорії МПУР відомо, що без втрати універсальності пошук може бути обмежено множиною так званих постійних (англ. stationary) стратегій. Стратегія називається постійною, якщо розподіл дій, який вона повертає, залежить лише від крайнього відвіданого стану (який є частиною історії спостережень агента, згідного нашого спрощувального припущення). Насправді, пошук може бути додатково обмежено детерміністичними (англ. deterministic) постійними стратегіями. Детерміністична постійна стратегія — це така, яка обирає дії на основі поточного стану детерміністично. Оскільки будь-яку таку стратегію може бути ідентифіковано відображенням з множини станів на множину дій, ці стратегії може бути ідентифіковано такими відображенням без втрати універсальності.

Повний перебір

Підхід повного перебору[en] спричиняє наступні два кроки:

  1. Для кожної можливої стратегії повертається зразок при слідуванні їй
  2. Вибрати стратегію з найбільшою очікуваною віддачею

Однією з проблем із цим є те, що число стратегій може бути надзвичайно великим, або навіть нескінченним. Іншою є те, що дисперсія віддач може бути великою, в разі чого для точної оцінки віддачі кожної зі стратегій буде необхідним велике число зразків.

Ці проблеми може бути полегшено, якщо ми припустимо деяку структуру, і, можливо, дозволимо зразкам, породженим з однієї стратегії, впливати на оцінки, зроблені для іншої. Двома головними підходами для досягнення цього є оцінка функції значення та прямий пошук стратегії.

Підходи функції значення

Підходи функції значення намагаються знайти стратегію, яка максимізує віддачу шляхом підтримки множини оцінок очікуваних віддач для деякої стратегії (зазвичай або «поточної», або оптимальної).

Ці методи покладаються на теорію МПУР, де оптимальність визначається в сенсі, який є суворішим за наведений вище: стратегія називається оптимальною, якщо вона досягає найкращої очікуваної віддачі від будь-якого початкового стану (тобто початкові розподіли в цьому визначенні не грають ролі). Знов-таки, завжди можна знайти оптимальну стратегію серед постійних стратегій.

Щоби визначити оптимальність формальним чином, визначмо значення стратегії як

де відповідає випадковій віддачі, пов'язаній зі слідуванням з початкового стану . Визначмо як максимально можливе значення , де дозволено змінюватися:

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

Хоч стано-значень і достатньо для визначення оптимальності, виявиться корисним визначити й діє-значення. Для заданих стану , дії та стратегії діє-значення пари за стратегії визначається як

де тепер відповідає випадковій віддачі, пов'язаній зі спершу вчиненням дії в стані , а потім слідуванням .

З теорії МПУР добре відомо, що якщо хтось дасть нам для оптимальної стратегії, то ми можемо завжди обирати оптимальні дії (і відтак діяти оптимально), просто обираючи в кожному стані дію з найбільшим значенням. Функція діє-значення такої оптимальної стратегії називається оптимальною функцією діє-значення, і позначається через . В підсумку, знання самої лише оптимальної функції діє-значення достатнє для того, щоби знати, як діяти оптимально.

Виходячи з повного знання МПУР, існують два основні підходи для обчислення оптимальної функції діє-значення, ітерація за значеннями[en] та ітерація за стратегіями●. Обидва ці алгоритми обчислюють послідовність функцій (), яка збігається до . Обчислення цих функцій включає обчислення математичних сподівань над усім простором станів, що є непрактичним для всіх, крім найменших (скінченних) МПУР, не кажучи вже про випадок, коли МПУР є невідомим. В методах навчання з підкріпленням математичні сподівання наближуються шляхом усереднення над зразками, а щоби впоратися з необхідністю представлення функцій значень над великими просторами станів-дій, застосовуються методики наближення функцій.

Методи Монте-Карло

В алгоритмі, який імітує ітерацію за стратегіями, можуть застосовуватися найпростіші методи Монте-Карло. Ітерація за стратегіями складається з двох кроків: оцінки стратегії (англ. policy evaluation) та вдосконалення стратегії (англ. policy improvement).

Методи Монте-Карло використовуються на кроці оцінки стратегії. На цьому кроці метою є для заданої постійної детерміністичної стратегії обчислити значення функції (або їхнє добре наближення) для всіх пар стан-дія . Припустімо (для спрощення), що МПУР є скінченним, і що таблиця, яка представляє діє-значення, фактично вміщається до пам'яті. Далі, припустімо, що ця задача є епізодичною, і що після кожного епізоду починається новий, з якогось випадкового початкового стану. Тоді оцінку значення заданої пари стан-дія може бути обчислено просто усередненням над часом вибраних віддач, породжених з . За достатньої кількості часу ця процедура може відтак побудувати точну оцінку функції діє-значення . Це завершує опис кроку оцінки стратегії.

На кроці вдосконалення стратегії, як це робиться й у стандартному алгоритмі ітерації за стратегіями, наступну стратегію отримують обчисленням жадібної (англ. greedy) стратегії з урахуванням : для заданого стану ця нова стратегія повертає дію, яка максимізує . На практиці часто уникають обчислення та зберігання цієї нової стратегії, застосовуючи натомість ліниві обчислення, щоби відкласти обчислення максимізувальних дій до того моменту, коли вони дійсно стануть потрібні.

Ця процедура має деякі перелічені нижче проблеми:

  • Ця процедура може марнувати забагато часу на оцінку недооптимальної стратегії;
  • Вона використовує зразки неефективно, оскільки використовує довгу траєкторію для поліпшення оцінки лише однієї пари стан-дія, яка почала цю траєкторію;
  • Якщо віддачі вздовж траєкторій мають високу дисперсію, то збіжність буде повільною;
  • Вона працює лише на епізодичних задачах;
  • Вона працює лише на невеликих скінченних МПУР.

Методи часових різниць

Перша проблема легко виправляється, якщо дозволити процедурі змінювати стратегію (взагалі, або на деяких станах) до встановлення значення. Проте, як добре б це не звучало, це може бути проблематичним, оскільки воно може перешкоджати збіганню. Тим не менше, більшість поточних алгоритмів реалізують цю ідею, породжуючи клас алгоритмів узагальненої ітерації за стратегіями (англ. generalized policy iteration). Зауважимо принагідно, що до цієї категорії належать методи критика діяча●.[3]

Другу проблему можна виправити в алгоритмі, дозволивши траєкторіям робити внесок до будь-якої пари стан-дія в них. Це також може допомогти певною мірою і з третьою проблемою, хоча кращим рішенням в разі великої дисперсії віддач є застосування методів часових різниць● (ЧР, англ. temporal difference, TD) Саттона●[4][5], які ґрунтуються на рекурсивному рівнянні Беллмана●. Зауважте, що обчислення в методах ЧР можуть бути інкрементними (англ. incremental, коли після кожного переходу пам'ять змінюється, а перехід викидається) або пакетними (англ. batch, коли переходи збираються, а потім оцінки обчислюються один раз на основі великого числа переходів). Пакетні методи, яскравим прикладом яких є метод найменших квадратів часових різниць[en] Брадтке[en] та Барто●,[6] можуть краще використовувати інформацію в зразках, тоді як інкрементні методи є єдиним вибором, коли пакетні методи стають нездійсненними з причини своєї високої обчислювальної складності або вимог до пам'яті. Крім того, існують методи, які намагаються поєднувати переваги цих двох підходів. Методи на основі часових різниць також долають другу, але не останню проблему.

Для розв'язання останньої проблеми, згаданої в попередньому розділі, застосовуються методи наближення функцій (англ. function approximation methods). В лінійному наближенні функції починають з відображення , яке ставить у відповідність кожній парі стан-дія скінченновимірний вектор. А потім значення дій пари стан-дія отримуються шляхом лінійного об'єднання складових з деякими вагами (англ. weights) :

.

Потім алгоритми підлаштовують ці ваги, замість підлаштовувати значення, пов'язані з конкретними парами стан-значення. Проте лінійне наближення функції не є єдиним вибором. Зовсім недавно було досліджено методи, засновані на ідеях непараметричної статистики[en] (яку можна розглядати як таку, яка будує свої власні ознаки).

Досі обговорення було обмежено тим, як в якості основи проектування алгоритмів навчання з підкріпленням можна застосовувати ітерацію за стратегіями. Не менш важливим є те, що в якості відправної точки можна застосовувати й ітерацію за значеннями, що веде до алгоритму Q-навчання[7] та багатьох його варіантів.

Проблема з методами, які використовують діє-значення, в тому, що вони можуть потребувати дуже точних оцінок значень порівнюваних дій, що може бути важко отримувати при зашумлених віддачах. І хоч ця проблема й пом'якшується до деякої міри методами часових різниць та застосуванням так званого методу сумісного наближення функції (англ. compatible function approximation method), належить зробити ще більше роботи для підвищення універсальності та ефективності. Ще одна проблема, властива методам часових різниць, випливає з їхньої залежності від рекурсивного рівняння Беллмана. Більшість методів часових різниць мають так званий параметр , який дозволяє здійснювати безперервну інтерполяцію між методами Монте-Карло (які не залежать від рівнянь Беллмана) та базовими методами часових різниць (які повністю покладаються на рівняння Беллмана), що, відтак, може бути ефективним для пом'якшення цієї проблеми.

Прямий пошук стратегії

Альтернативним методом пошуку доброї стратегії може бути прямий пошук у (деякій підмножині) простору стратегій, і в цьому випадку задача стає прикладом стохастичної оптимізації●. Двома доступними підходами є методи на основі градієнту та безградієнтні методи.

Методи на основі градієнту (які породжують так звані методи градієнту стратегії, англ. policy gradient methods) починаються з відображення зі скінченновимірного простору (параметрів) на простір стратегій: для заданого вектору параметрів нехай позначає стратегію, пов'язану з . Визначмо функцію продуктивності як

За м'яких умов ця функція буде диференційовною як функція вектору параметрів . Якби градієнт був відомим, то можна було би застосовувати градієнтний спуск. Оскільки аналітичний вираз градієнту відсутній, мусимо покладатися на зашумлену оцінку. Таку оцінку може бути побудовано багатьма способами, що породжують такі алгоритми, як метод REINFORCE Вільямса[en][8] (що також відомий в літературі з оптимізації на основі імітації● як метод відношення правдоподібностей[en]). Методи градієнту стратегії отримали багато уваги в останні пару років,[9] але продовжують залишатися полем активної діяльності. Огляд методів градієнту стратегії було запропоновано Дайзенротом, Нейманом та Петерсом.[10] Проблема багатьох із цих методів у тому, що вони можуть застрягати в локальних оптимумах (оскільки вони ґрунтуються на локальному пошукові).

Існує великий клас методів, які уникають покладання на інформацію про градієнт. Вони включають імітацію відпалу, метод перехресної ентропії та методи еволюційного обчислення. Багато безградієнтних методів можуть досягати глобального оптимуму (в теорії та на границі). В ряді випадків вони дійсно показали визначну продуктивність.

Проблема методів пошуку стратегії в тому, що вони можуть збігатися повільно, якщо інформація, на основі якої вони діють, є зашумленою. Наприклад, це відбувається тоді, коли в епізодичних задачах траєкторії є довгими, а дисперсія віддач є великою. Як було зазначено вище, в такому випадку можуть допомогти методи на основі функції значення, які покладаються на часові різниці. В останні роки було запропоновано декілька алгоритмів діяча — критика, які слідують цій ідеї, і було показано, що вони працюють добре на різних задачах.

Теорія

Теорія для невеликих скінченних МПУР є цілком зрілою. Поведінка як асимптотичних алгоритмів, так і алгоритмів зі скінченною вибіркою, є добре вивченою. Як було зазначено вище, алгоритми з довідно доброю інтерактивною продуктивністю (спрямовані на розв'язання задачі дослідження) є відомими.

Теорія великих МПУР потребує подальшої праці. Дієве дослідження є здебільшого недосягнутим (крім випадку задач бандита). І хоча останніми роками для багатьох алгоритмів з'явилися скінченно-часові обмеження виконання, ці обмеження, як очікується, є доволі слабкими, і відтак для кращого розуміння як відносних переваг, так і обмежень цих алгоритмів, необхідна подальша праця.

Питання асимптотичної збіжності для інкрементних алгоритмів було розв'язано. Нещодавно з'явилися нові інкрементні алгоритми на основі часових різниць, які збігаються за значно ширшого набору умов, ніж було можливо раніше (наприклад, при застосуванні з довільним гладким наближенням функції).

Поточні дослідження

Актуальні теми дослідження включають: адаптивні методи, які працюють з меншою кількістю (або без) параметрів за великого числа умов, спрямування на задачу дослідження у великих МПУР, великомасштабні емпіричні оцінки, навчання та дію за часткової інформації[en] (наприклад, із застосуванням передбачувального представлення стану[en]), модульне та ієрархічне навчання з підкріпленням, вдосконалення наявних методів функції значення та пошуку стратегії, алгоритми, які працюють добре з великими (або безперервними) просторами дій, передавальне навчання●, безперервне навчання (англ. lifelong learning), ефективне планування на основі зразків (наприклад, на основі деревного пошуку Монте-Карло[en]). Предметом зацікавлення в сучасних дослідженнях також є поліагентне (англ. Multiagent) або розподілене навчання з підкріпленням (англ. Distributed Reinforcement Learning). Також зростає зацікавлення до застосувань навчання з підкріпленням в реальному житті. Успіхи навчання з підкріпленням збирають тут і тут.

Алгоритми навчання з підкріпленням, такі як ЧР, було також досліджувано як модель навчання в мозку на основі дофаміну. В цій моделі дофамінергійні проекції з чорної субстанції● на базальні ганглії діють як похибка передбачення. Навчання з підкріпленням також використовували як частину моделі набування навичок людиною, особливо у відношенні взаємодії між неявним та явним навчанням при набуванні навичок (перша публікація про це застосування була в 1995—1996 роках, і було багато наступних досліджень).[11]

Реалізації

  • RL-Glue пропонує стандартний інтерфейс, який дозволяє з'єднувати разом агентів, середовища та програми експериментів, навіть якщо їх написано різними мовами.
  • Maja Machine Learning Framework (MMLF) — це універсальний каркас для задач області навчання з підкріпленням, написаний мовою Python.
  • Програмні інструменти для навчання з підкріпленням (Matlab та Python)
  • PyBrain (Python)
  • TeachingBox — це каркас навчання з підкріпленням на Java, який підтримує багато функцій, таких як мережі РБФ●, методи навчання градієнтним спуском, …
  • Реалізації мовами C++ та Python деяких добре відомих алгоритмів навчання з підкріпленням із первинним кодом.
  • Orange[en], безкоштовний програмний пакет добування даних, модуль orngReinforcement
  • Policy Gradient Toolbox пропонує пакет для навчання підходів градієнту стратегії.
  • BURLAP — це відкрита бібліотека Java, яка пропонує широкий спектр методів одно- та поліагентного навчання й планування.

Зворотне навчання з підкріпленням

У зворотному навчанні з підкріпленням (англ. inverse reinforcement learning, IRL) функція винагороди не надається. Натомість намагаються добути стратегію із заданої спостережуваної поведінки, щоби наслідувати спостережувану поведінку, яка є часто оптимальною або близькою до оптимальної. Оскільки агент, який навчається зворотним навчанням з підкріпленням, щойно він відхилився від шляху, яким слідує спостережувана поведінка, часто потребує якогось способу повернутися назад на цей шлях, щоби його власна поведінка була стійкою●, то іноді необхідно продемонструвати поведінку декілька разів із невеликими збуреннями кожного разу.

У підмайстровому навчанні● припускають, що експерт, який демонструє поведінку, намагається максимізувати функцію винагороди, і намагаються розкрити невідому функцію винагороди експерта.

Див. також

Примітки

  1. ↑ Sutton та Barto, 1998, §11. Case Studies.
  2. ↑ Gosavi, 2003.
  3. ↑ Sutton та Barto, 1998, §6.6 Actor-Critic Methods.
  4. ↑ Sutton, 1984.
  5. ↑ Sutton та Barto, 1998, §6. Temporal-Difference Learning.
  6. ↑ Bradtke та Barto, 1996.
  7. ↑ Watkins, 1989.
  8. ↑ Williams, 1987.
  9. ↑ наприклад, Peters, Vijayakumar та Schaal, 2003
  10. ↑ Deisenroth, Neumann та Peters, 2013.
  11. ↑ Докладніше про ці області дослідження див. http://webdocs.cs.ualberta.ca/~sutton/RL-FAQ.html#behaviorism (англ.)

Джерела

Ця стаття містить перелік посилань, але походження окремих тверджень залишається незрозумілим через брак внутрішньотекстових джерел-виносок. Будь ласка, допоможіть поліпшити цю статтю, перетворивши джерела з переліку посилань на джерела-виноски у самому тексті статті. Зверніться на сторінку обговорення за поясненнями та допоможіть виправити недоліки. (серпень 2016)

Література

Конференції, журнали

Більшість праць із навчання з підкріпленням публікуються на головних конференціях (ICML[en], NIPS[en], AAAI, IJCAI, UAI[en], AI and Statistics) та в журналах (JAIR, JMLR, Machine learning journal, IEEE T-CIAIG) з машинного навчання та ШІ. Деякі теоретичні праці публікуються на COLT[en] та ALT[en]. Тим не менше, багато праць з'являються на конференціях із робототехніки (IROS[en], ICRA[en]) та на «агентній» конференції AAMAS[en]. Дослідники операцій публікують свої праці на конференції INFORMS[en] і, наприклад, в журналах Operation Research та Mathematics of Operations Research. Дослідники керування публікують свої праці на конференціях CDC та ACC, або, наприклад, у журналах IEEE Transactions on Automatic Control та Automatica, хоча прикладні праці тяжіють до публікації в більш спеціалізованих журналах. Winter Simulation Conference також публікує багато відповідних документів. Крім цього, праці також публікуються на головних конференціях спільнот із нейронних мереж, нечітких та еволюційних обчислень. Щорічний симпозіум IEEE під назвою Approximate Dynamic Programming and Reinforcement Learning (ADPRL) та щодворічний семінар European Workshop on Reinforcement Learning (EWRL) є двома регулярними зустрічами, на яких зустрічаються дослідники навчання з підкріпленням.

Посилання

Отримано з https://uk.wikipedia.org/w/index.php?title=Навчання_з_підкріпленням&oldid=18705369