Навчання з підкріпленням

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

Введення[ред.ред. код]

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

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

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

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

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

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

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

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

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

Дослідження[ред.ред. код]

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

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

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

Критерій оптимальності[ред.ред. код]

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

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

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

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

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

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

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

Повний перебір[ред.ред. код]

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

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

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

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

Підходи функції цінності[ред.ред. код]

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

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

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

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

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

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

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

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

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

Методи Монте-Карло[ред.ред. код]

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

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

Теорія[ред.ред. код]

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

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

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

Поточні дослідження[ред.ред. код]

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

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

Реалізації[ред.ред. код]

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

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

У підмайстровому навчанні[en] (англ. apprenticeship learning) припускають, що експерт, який демонструє поведінку, намагається максимізувати функцію винагороди, і намагаються розкрити невідому функцію винагороди експерта.

Див. також[ред.ред. код]

Примітки[ред.ред. код]

Джерела[ред.ред. код]

Література[ред.ред. код]

Конференції, журнали[ред.ред. код]

Більшість праць із навчання з підкріпленням публікуються на головних конференціях (ICML[en], NIPS[en], AAAI, IJCAI, UAI, AI and Statistics) та в журналах (JAIR, JMLR, Machine learning journal, IEEE T-CIAIG) з машинного навчання та ШІ. Деякі теоретичні праці публікуються на COLT та 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) є двома регулярними зустрічами, на яких зустрічаються дослідники навчання з підкріпленням.

Посилання[ред.ред. код]