Навчання з підкріпленням () — це галузь машинного навчання, натхнена біхевіористською психологією, що вивчає питання про те, які дії () повинні виконувати програмні агенти в певному середовищі () задля максимізації деякого уявлення про сукупну винагороду (). Через її універсальність, дану задачу вивчають і багато інших дисциплін, таких як теорія ігор, теорія керування, дослідження операцій, теорія інформації, оптимізація на основі моделювання, поліагентні системи, колективний інтелект, статистика та генетичні алгоритми. В літературі про дослідження та керування операціями галузь, що займається навчанням з підкріпленням, називається наближеним динамічним програмуванням (). Задача навчання з підкріпленням досліджувалася у теорії оптимального керування, проте більшість досліджень стосувалися саме існування оптимальних рішень та їх характеристики, а не аспектів навчання чи наближення. В економіці та теорії ігор навчання з підкріпленням може використовуватись для пояснення того, як може виникати рівновага за обмеженої раціональності.
В машинному навчанні середовище зазвичай розглядається як марковський процес вирішування (МПВ, ), оскільки багато алгоритмів навчання з підкріпленням для цього контексту використовують методики динамічного програмування. Основна відмінність між класичними методиками й алгоритмами навчання з підкріпленням полягає в тому, що останні не потребують знання про МПВ, і вони орієнтовані на великі МПВ, в яких точні методи стають нездійсненними.
Навчання з підкріпленням відрізняється від стандартного керованого навчання тим, що пари правильних входів/виходів ніколи не представляються, а недостатньо оптимальні дії явно не виправляються. Крім того, є акцент на інтерактивній продуктивності, який включає знаходження балансу між дослідженням (незвіданої території, ) та використанням (поточного знання, ). Компроміс між дослідженням та використанням у навчанні з підкріпленням найретельніше вивчався через задачу багаторукого бандита та скінченні МПВ.
Введення
Базова модель навчання з підкріпленням складається з:
множини станів середовища ; множини дій ; правил переходу між станами; правил, які визначають скалярну безпосередню винагороду () переходу; і правил, які описують, що спостерігає агент.
Ці правила часто є стохастичними. Спостереження зазвичай включає в себе скалярну безпосередню винагороду, пов'язану з крайнім переходом. У багатьох працях також вважають, що агент спостерігає поточний стан середовища, в разі чого говорять про повну спостережуваність (), тоді як в іншому разі говорять про часткову спостережуваність (). Іноді множина доступних агентові дій є обмеженою (наприклад, ви не можете витрачати більше грошей, ніж маєте).
Агент навчання з підкріпленням взаємодіє зі своїм середовищем у дискретні моменти часу. В кожен момент часу агент отримує спостереження , яке зазвичай включає винагороду . Потім він обирає дію з множини доступних дій, яка відтак відправляється до середовища. Середовище переходить до нового стану , і визначається винагорода , пов'язана з переходом () . Метою агента навчання з підкріпленням є збирати якомога більше винагороди. Агент може обирати будь-яку дію як функцію історії, і може навіть робити свій вибір дії випадковим.
Коли продуктивність агента порівнюється з продуктивністю агента, який діє оптимально від початку, то різниця в продуктивності призводить до поняття смутку (). Зверніть увагу, що, щоби діяти майже оптимально, агент мусить розуміти довготермінові наслідки своїх дій: щоби максимізувати свій майбутній дохід, мені краще зараз піти до школи, хоча пов'язана з цим безпосередня грошова винагорода може бути від'ємною.
Таким чином, навчання з підкріпленням є особливо добре пристосованим для задач, які включають компроміс між довготерміновою та короткотерміновою винагородою. Його було успішно застосовано до різноманітних задач, включно з , розкладами для ліфтів, телекомунікаціями, нардами, шашками та ґо (AlphaGo).
Потужним навчання з підкріпленням роблять дві складові: використання зразків для оптимізації продуктивності, та застосування наближень функцій, щоби мати справу з великими середовищами. Завдяки цим двом складовим навчання з підкріпленням можливо застосовувати у великих середовищах в будь-яких із наступних ситуацій:
Модель середовища є відомою, але аналітичний розв'язок відсутній; Задано лише імітаційну модель середовища (предмет оптимізації на основі імітації); Єдиним способом збирання інформації про середовище є взаємодія з ним.
Перші дві з цих задач можливо розглядати як задачі планування (оскільки модель в якомусь вигляді існує), тоді як останню можливо розглядати як справжню задачу навчання. Проте за методології навчання з підкріпленням обидві задачі планування може бути перетворено на задачі машинного навчання.
Дослідження
Описана задача навчання з підкріпленням вимагає розумних механізмів дослідження. Відомо, що випадковий вибір дій без прив'язки до оцінюваного розподілу ймовірності викликає дуже погану продуктивність. Випадок (невеликих) скінченних МПВ в даний час є відносно добре вивченим. Проте через брак алгоритмів, які б добре масштабувалися з числом станів (або масштабувалися до задач з нескінченними просторами станів), на практиці люди вдаються до простих методів дослідження. Одним із таких методів є -жадібна стратегія, коли агент вибирає дію, яка за його переконанням має найкращий довготермінових ефект, з імовірністю , а інші дії обирає рівномірно випадково. Тут є параметром налаштування, який іноді змінюється, або згідно фіксованого розкладу (роблячи так, що агент з плином часу досліджує менше), або адаптивно на основі якихось евристик.
Алгоритми для навчання керуванню
Навіть якщо питання дослідження не береться до уваги, і навіть якщо стан можна було спостерігати (що ми припускаємо, з цього моменту), лишається задача з'ясування на основі попереднього досвіду, які дії є добрими.
Критерій оптимальності
Для спрощення на хвилинку припустімо, що досліджувана задача є епізодичною (), із завершенням епізоду при досягненні деякого завершального стану (). Припустімо далі, що незалежно від того, який план дій обирає агент, завершення є неминучим. За деяких додаткових м'яких умов закономірності математичне сподівання повної винагороди є добре визначеним для будь-якої стратегії та будь-якого початкового розподілу над станами. Тут стратегія () позначає відображення, яке призначає деякий розподіл імовірності над діями всім можливим історіям.
Таким чином, для заданого зафіксованого початкового розподілу ми можемо поставити у відповідність стратегії очікувану віддачу :
де випадкова величина позначає віддачу (), і визначається як
де є винагородою, отриманою після -того переходу, початковий стан вибирається випадково з , а дії обираються стратегією . Тут позначає (випадковий) час досягнення завершального стану, тобто, час, коли завершується епізод.
У випадку не епізодичних задач віддачу часто знецінюють (),
породжуючи критерій загальної очікуваної знеціненої винагороди. Тут є так званим коефіцієнтом знецінювання (). Оскільки незнецінена віддача є окремим випадком знеціненої віддачі, від цього моменту ми розглядатимемо знецінювання. Хоч це й виглядає безневинним, знецінювання насправді є проблематичним, якщо турбуватися про інтерактивну продуктивність. Це пояснюється тим, що знецінювання робить початкові моменти часу важливішими. Оскільки для агента, що навчається, найправдоподібніше робити помилки протягом перших кількох кроків після початку його «життя», жоден непоінформований алгоритм навчання не може досягти майже оптимальної продуктивності за знецінювання, навіть якщо клас середовищ обмежено скінченними МПВ. (Проте це не означає, що, маючи достатньо часу, агент, що навчається, не зможе з'ясувати, як діяти майже оптимально, якби час було перезапущено.)
То задачею є вказати алгоритм, який можна використовувати для знаходження стратегії з максимальною очікуваною віддачею. З теорії МПВ відомо, що без втрати універсальності пошук може бути обмежено множиною так званих постійних () стратегій. Стратегія називається постійною, якщо розподіл дій, який вона повертає, залежить лише від крайнього відвіданого стану (який є частиною історії спостережень агента, згідного нашого спрощувального припущення). Насправді, пошук може бути додатково обмежено детерміністичними () постійними стратегіями. Детерміністична постійна стратегія — це така, яка обирає дії на основі поточного стану детерміністично. Оскільки будь-яку таку стратегію може бути ідентифіковано відображенням з множини станів на множину дій, ці стратегії може бути ідентифіковано такими відображенням без втрати універсальності.
Повний перебір
Підхід повного перебору спричиняє наступні два кроки:
Для кожної можливої стратегії повертається зразок при слідуванні їй Вибрати стратегію з найбільшою очікуваною віддачею
Однією з проблем із цим є те, що число стратегій може бути надзвичайно великим, або навіть нескінченним. Іншою є те, що дисперсія віддач може бути великою, в разі чого для точної оцінки віддачі кожної зі стратегій буде необхідним велике число зразків.
Ці проблеми може бути полегшено, якщо ми припустимо деяку структуру, і, можливо, дозволимо зразкам, породженим з однієї стратегії, впливати на оцінки, зроблені для іншої. Двома головними підходами для досягнення цього є оцінка функції цінності та прямий пошук стратегії.
Підходи функції цінності
Підходи функції цінності намагаються знайти стратегію, яка максимізує віддачу шляхом підтримки множини оцінок очікуваних віддач для деякої стратегії (зазвичай або «поточної» (), або оптимальної ()).
Ці методи покладаються на теорію МПВ, де оптимальність визначається в сенсі, який є суворішим за наведений вище: стратегія називається оптимальною, якщо вона досягає найкращої очікуваної віддачі від будь-якого початкового стану (тобто початкові розподіли в цьому визначенні не грають ролі). Знов-таки, завжди можна знайти оптимальну стратегію серед постійних стратегій.
Щоби визначити оптимальність формальним чином, визначмо цінність () стратегії як
де відповідає випадковій віддачі, пов'язаній зі слідуванням з початкового стану . Визначмо як максимально можливу цінність , де дозволено змінюватися:
Стратегія, яка досягає цих оптимальних цінностей в кожному зі станів, називається оптимальною. Очевидно, що стратегія, яка є оптимальною в цьому суворому сенсі, є також оптимальною й у сенсі того, що вона максимізує очікувану віддачу , оскільки , де є станом, який вибирається випадковим чином з розподілу .
Хоч цінностей станів і достатньо для визначення оптимальності, виявиться корисним визначити й цінності дій. Для заданих стану , дії та стратегії цінність дії пари за стратегії визначається як
де тепер відповідає випадковій віддачі, пов'язаній зі спершу вчиненням дії в стані , а потім слідуванням .
З теорії МПВ добре відомо, що якщо хтось дасть нам для оптимальної стратегії, то ми можемо завжди обирати оптимальні дії (і відтак діяти оптимально), просто обираючи в кожному стані дію з найвищою цінністю. Функція цінності дій такої оптимальної стратегії називається оптимальною функцією цінності дій, і позначається через . В підсумку, знання самої лише оптимальної функції цінності дій достатнє для того, щоби знати, як діяти оптимально.
Виходячи з повного знання МПВ, існують два основні підходи для обчислення оптимальної функції цінності дій, ітерація за цінностями та ітерація за стратегіями. Обидва ці алгоритми обчислюють послідовність функцій (), яка збігається до . Обчислення цих функцій включає обчислення математичних сподівань над усім простором станів, що є непрактичним для всіх, крім найменших (скінченних) МПВ, не кажучи вже про випадок, коли МПВ є невідомим. В методах навчання з підкріпленням математичні сподівання наближуються шляхом усереднення над зразками, а щоби впоратися з необхідністю представлення функцій цінності над великими просторами станів-дій, застосовуються методики наближення функцій.
Методи Монте-Карло