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

Частина з циклу
Машинне навчання та добування даних
Парадигми Кероване навчання Некероване навчання Інтерактивне навчання Пакетне навчання Метанавчання Напівкероване навчання Самокероване навчання Навчання з підкріпленням Навчання на основі правил Квантове машинне навчання
Задачі Класифікація Породжувальна модель Регресія Кластерування Знижування розмірності Оцінювання густини Виявляння аномалій Очищування даних^[en] АвтоМН Асоціативні правила Семантичний аналіз^[en] Структурове передбачування Конструювання ознак Навчання ознак Навчання ранжуванню Виведення граматик^[en] Навчання онтологій^[en] Мультимодальне навчання^[en]
Кероване навчання (класифікація • регресія) Ансамблі Випадковий ліс Бутстрепова агрегація Підсилювання Градієнтне підсилювання^[en] AdaBoost^[en] Дерева рішень MARS^[en] CART Доречно-векторна машина k-сусідів Лінійна регресія Логістична регресія Лінійний розділювальний аналіз Наївний баєсів класифікатор Перцептрон Підмайстрове навчання Опорно-векторна машина Штучні нейронні мережі
Кластерування BIRCH^[en] CURE Ієрархічне k-середніх Нечітке Очікування-максимізація DBSCAN OPTICS Спектральне Зсув середнього^[en]
Знижування розмірності Факторний аналіз Метод незалежних компонент^[en] Канонічна кореляція Дискримінантний аналіз Метод головних компонент Власний узагальнений розклад^[en] Розклад невід'ємних матриць t-розподілене вкладення стохастичної близькості Навчання розріджених словників^[en]
Структурове передбачування Графові моделі Баєсова мережа Прихована марковська модель Умовне випадкове поле
Виявляння аномалій RANSAC k-НС Коефіцієнт локального відхилення Відстань Кука Ізоляційний ліс^[en]
Штучна нейронна мережа Автокодувальник Когнітивні обчислення^[en] Глибоке навчання DeepDream Нейронна мережа прямого поширення Рекурентна нейронна мережа ДКЧП ВРВ МВС Резервуарне обчислення Обмежена машина Больцмана ГЗМ Дифузійна модель Самоорганізаційна карта Згорткова нейронна мережа U-Net Трансформер Зоровий Спайкова нейронна мережа^[en] Мемтранзистор Електрохімічна ПДД^[en] (ECRAM)
Навчання з підкріпленням Q-навчання SARSA Метод часових різниць Багатоагентне навчання з підкріпленням Гра проти себе^[en]
Навчання з людьми Активне навчання (машинне навчання)^[en] Краудсорсинг Людина-в-циклі
Діагностування моделей Крива спроможності навчатися^[en]
Математичні засади Ядрові машини Компроміс зсуву та дисперсії Ймовірнісно приблизно коректне навчання Мінімізація емпіричного ризику Оккамове навчання^[en] Регуляризація LASSO^[en] Тихонова Еластично-сіткова^[en] Статистичне навчання Теорія Вапника — Червоненкіса Теорія обчислювального навчання^[en]
Місця машинного навчання ECML PKDD^[en] NeurIPS^[en] ICML^[en] ICLR IJCAI ML JMLR
Пов'язані статті Глосарій штучного інтелекту^[en] Список наборів даних для досліджень з машинного навчання Перелік понять машинного навчання^[en]
п о р

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

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

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

Введення

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

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

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

Агент навчання з підкріпленням взаємодіє зі своїм середовищем у дискретні моменти часу. В кожен момент часу ${\displaystyle t}$ агент отримує спостереження ${\displaystyle o_{t}}$, яке зазвичай включає винагороду ${\displaystyle r_{t}}$. Потім він обирає дію ${\displaystyle a_{t}}$ з множини доступних дій, яка відтак відправляється до середовища. Середовище переходить до нового стану ${\displaystyle s_{t+1}}$, і визначається винагорода ${\displaystyle r_{t+1}}$, пов'язана з переходом (англ. transition) ${\displaystyle (s_{t},a_{t},s_{t+1})}$. Метою агента навчання з підкріпленням є збирати якомога більше винагороди. Агент може обирати будь-яку дію як функцію історії, і може навіть робити свій вибір дії випадковим.

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

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

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

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

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

Дослідження

Описана задача навчання з підкріпленням вимагає розумних механізмів дослідження. Відомо, що випадковий вибір дій без прив'язки до оцінюваного розподілу ймовірності викликає дуже погану продуктивність. Випадок (невеликих) скінченних МПВ в даний час є відносно добре вивченим. Проте через брак алгоритмів, які б добре масштабувалися з числом станів (або масштабувалися до задач з нескінченними просторами станів), на практиці люди вдаються до простих методів дослідження. Одним із таких методів є ${\displaystyle \varepsilon }$-жадібна стратегія, коли агент вибирає дію, яка за його переконанням має найкращий довготермінових ефект, з імовірністю ${\displaystyle 1-\varepsilon }$, а інші дії обирає рівномірно випадково. Тут ${\displaystyle 0<\varepsilon <1}$ є параметром налаштування, який іноді змінюється, або згідно фіксованого розкладу (роблячи так, що агент з плином часу досліджує менше), або адаптивно на основі якихось евристик^[3].

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

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

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

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

Таким чином, для заданого зафіксованого початкового розподілу ${\displaystyle \mu }$ ми можемо поставити у відповідність стратегії ${\displaystyle \pi }$ очікувану віддачу ${\displaystyle \rho ^{\pi }}$:

${\displaystyle \rho ^{\pi }=E[R|\pi ],}$

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

${\displaystyle R=\sum _{t=0}^{N-1}r_{t+1},}$

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

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

${\displaystyle R=\sum _{t=0}^{\infty }\gamma ^{t}r_{t+1},}$

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

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

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

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

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

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

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

Підходи функції цінності

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

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

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

${\displaystyle V^{\pi }(s)=E[R|s,\pi ],}$

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

${\displaystyle V^{*}(s)=\sup \limits _{\pi }V^{\pi }(s).}$

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

Хоч цінностей станів і достатньо для визначення оптимальності, виявиться корисним визначити й цінності дій. Для заданих стану ${\displaystyle s}$, дії ${\displaystyle a}$ та стратегії ${\displaystyle \pi }$ цінність дії пари ${\displaystyle (s,a)}$ за стратегії ${\displaystyle \pi }$ визначається як

${\displaystyle Q^{\pi }(s,a)=E[R|s,a,\pi ],\,}$

де тепер ${\displaystyle R}$ відповідає випадковій віддачі, пов'язаній зі спершу вчиненням дії ${\displaystyle a}$ в стані ${\displaystyle s}$, а потім слідуванням ${\displaystyle \pi }$.

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

Виходячи з повного знання МПВ, існують два основні підходи для обчислення оптимальної функції цінності дій, ітерація за цінностями та ітерація за стратегіями. Обидва ці алгоритми обчислюють послідовність функцій ${\displaystyle Q_{k}}$ (${\displaystyle k=0,1,2,\ldots }$), яка збігається до ${\displaystyle Q^{*}}$. Обчислення цих функцій включає обчислення математичних сподівань над усім простором станів, що є непрактичним для всіх, крім найменших (скінченних) МПВ, не кажучи вже про випадок, коли МПВ є невідомим. В методах навчання з підкріпленням математичні сподівання наближуються шляхом усереднення над зразками, а щоби впоратися з необхідністю представлення функцій цінності над великими просторами станів-дій, застосовуються методики наближення функцій.

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

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

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

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

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

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

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

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

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

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

${\displaystyle Q(s,a)=\sum \limits _{i=1}^{d}\theta _{i}\phi _{i}(s,a)}$.

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

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

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

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

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

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

${\displaystyle \rho (\theta )=\rho ^{\pi _{\theta }}.}$

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

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

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

Теорія

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

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

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

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

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

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

Реалізації

• RL-Glue [Архівовано 19 лютого 2009 у Wayback Machine.] пропонує стандартний інтерфейс, який дозволяє з'єднувати разом агентів, середовища та програми експериментів, навіть якщо їх написано різними мовами.
• Maja Machine Learning Framework [Архівовано 16 серпня 2016 у Wayback Machine.] (MMLF) — це універсальний каркас для задач області навчання з підкріпленням, написаний мовою Python.
• Програмні інструменти для навчання з підкріпленням [Архівовано 24 серпня 2016 у Wayback Machine.] (Matlab та Python)
• PyBrain [Архівовано 23 серпня 2016 у Wayback Machine.] (Python)
• TeachingBox [Архівовано 25 липня 2016 у Wayback Machine.] — це каркас навчання з підкріпленням на Java, який підтримує багато функцій, таких як мережі РБФ, методи навчання градієнтним спуском, …
• Реалізації мовами C++ та Python деяких добре відомих алгоритмів навчання з підкріпленням із первинним кодом. Архів оригіналу за 27 жовтня 2015 р.
• Orange^[en], безкоштовний програмний пакет добування даних, модуль orngReinforcement [Архівовано 7 жовтня 2007 у Wayback Machine.]
• Policy Gradient Toolbox [Архівовано 12 травня 2017 у Wayback Machine.] пропонує пакет для навчання підходів градієнту стратегії.
• BURLAP [Архівовано 9 січня 2015 у Wayback Machine.] — це відкрита бібліотека Java, яка пропонує широкий спектр методів одно- та поліагентного навчання й планування.

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

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

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

Див. також

• OpenAI
• Метод часових різниць
• Q-навчання
• Стан-дія-винагорода-стан-дія (англ. SARSA)
• Фіктивна гра^[en] (англ. Fictitious play)
• Система навчання класифікації^[en] (англ. Learning classifier system)
• Оптимальне керування
• Динамічний режим лікування^[en]
• Навчання, кероване похибками^[en] (англ. Error-driven learning)
• Багатоагентна система
• Розподілений штучний інтелект^[en]

Примітки

1. Sutton та Barto, 1998, §11. Case Studies.
2. Gosavi, 2003.
3. Tokic, Michel; Palm, Günther (2011), Value-Difference Based Exploration: Adaptive Control Between Epsilon-Greedy and Softmax (PDF), KI 2011: Advances in Artificial Intelligence, Lecture Notes in Computer Science, т. 7006, Springer, с. 335—346, ISBN 978-3-642-24455-1, архів оригіналу (PDF) за 23 листопада 2018, процитовано 22 вересня 2020
4. Sutton та Barto, 1998, §6.6 Actor-Critic Methods.
5. Sutton, 1984.
6. Sutton та Barto, 1998, §6. Temporal-Difference Learning.
7. Bradtke та Barto, 1996.
8. Watkins, 1989.
9. Williams, 1987.
10. наприклад, Peters, Vijayakumar та Schaal, 2003
11. Deisenroth, Neumann та Peters, 2013.
12. Докладніше про ці області дослідження див. http://webdocs.cs.ualberta.ca/~sutton/RL-FAQ.html#behaviorism [Архівовано 28 серпня 2016 у Wayback Machine.] (англ.)

Джерела

• Sutton, Richard S. (1984). Temporal Credit Assignment in Reinforcement Learning (Дипломна робота PhD). University of Massachusetts, Amherst, MA. Архів оригіналу за 28 серпня 2016. Процитовано 27 серпня 2016. (англ.)
• Williams, Ronald J. (1987). A class of gradient-estimating algorithms for reinforcement learning in neural networks. Proceedings of the IEEE First International Conference on Neural Networks. Архів оригіналу за 8 жовтня 2012. Процитовано 27 серпня 2016. (англ.)
• Sutton, Richard S. (1988). Learning to predict by the method of temporal differences. Machine Learning. Springer. 3: 9—44. doi:10.1007/BF00115009. Архів оригіналу за 28 серпня 2016. Процитовано 27 серпня 2016. (англ.)
• Watkins, Christopher J.C.H. (1989). Learning from Delayed Rewards (PDF) (Дипломна робота PhD). King’s College, Cambridge, UK. Архів оригіналу (PDF) за 9 вересня 2016. Процитовано 27 серпня 2016. (англ.)
• Bradtke, Steven J.; Barto, Andrew G. (1996). Learning to predict by the method of temporal differences. Machine Learning. Springer. 22: 33—57. doi:10.1023/A:1018056104778. Архів оригіналу за 8 жовтня 2012. Процитовано 27 серпня 2016. (англ.)
• Bertsekas, Dimitri P.; Tsitsiklis, John (1996). Neuro-Dynamic Programming. Nashua, NH: Athena Scientific. ISBN 1-886529-10-8. Архів оригіналу за 14 квітня 2017. Процитовано 27 серпня 2016. (англ.)
• Kaelbling, Leslie P.; Littman, Michael L.; Moore, Andrew W. (1996). Reinforcement Learning: A Survey. Journal of Artificial Intelligence Research. 4: 237—285. Архів оригіналу за 20 листопада 2001. Процитовано 27 серпня 2016. (англ.)
• Sutton, Richard S.; Barto, Andrew G. (1998). Reinforcement Learning: An Introduction. MIT Press. ISBN 0-262-19398-1. Архів оригіналу за 11 грудня 2013. Процитовано 27 серпня 2016. (англ.)
• Gosavi, Abhijit (2003). Simulation-based Optimization: Parametric Optimization Techniques and Reinforcement. Springer. ISBN 1-4020-7454-9. Архів оригіналу за 15 червня 2012. Процитовано 27 серпня 2016. (англ.)
• Peters, Jan; Vijayakumar, Sethu; Schaal, Stefan (2003). Reinforcement Learning for Humanoid Robotics (PDF). IEEE-RAS International Conference on Humanoid Robots. Архів оригіналу (PDF) за 12 травня 2013. Процитовано 27 серпня 2016. (англ.)
• Powell, Warren (2007). Approximate dynamic programming: solving the curses of dimensionality. Wiley-Interscience. ISBN 0-470-17155-3. Архів оригіналу за 31 липня 2016. Процитовано 27 серпня 2016. (англ.)
• Auer, Peter; Jaksch, Thomas; Ortner, Ronald (2010). Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research. 11: 1563—1600. Архів оригіналу за 28 серпня 2016. Процитовано 27 серпня 2016. (англ.)
• Szita, Istvan; Szepesvari, Csaba (2010). Model-based Reinforcement Learning with Nearly Tight Exploration Complexity Bounds (PDF). ICML 2010. Omnipress. с. 1031—1038. Архів оригіналу (PDF) за 14 липня 2010. Процитовано 27 серпня 2016. (англ.)
• Bertsekas, Dimitri P. (August 2010). Chapter 6 (online): Approximate Dynamic Programming. Dynamic Programming and Optimal Control (PDF). Т. II (вид. 3). Архів оригіналу (PDF) за 9 жовтня 2011. Процитовано 27 серпня 2016. (англ.)
• Busoniu, Lucian; Babuska, Robert; De Schutter, Bart; Ernst, Damien (2010). Reinforcement Learning and Dynamic Programming using Function Approximators. Taylor & Francis CRC Press. ISBN 978-1-4398-2108-4. Архів оригіналу за 29 жовтня 2011. Процитовано 27 серпня 2016. (англ.)
• Deisenroth, Marc Peter; Neumann, Gerhard; Peters, Jan (2013). A Survey on Policy Search for Robotics. Foundations and Trends in Robotics. Т. 2. NOW Publishers. с. 1—142. (англ.)

Література

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

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

Посилання

• Murphy, Kevin (2024). Reinforcement Learning: An Overview (англ.). с. 144.
• Вебсайт книги Reinforcement Learning: An Introduction (1998) Річа Саттона та Ендрю Барто, MIT Press, включає посилання на html-версію цієї книги. (англ.)
• Reinforcement Learning Repository [Архівовано 24 серпня 2016 у Wayback Machine.] (англ.)
• Reinforcement Learning and Artificial Intelligence [Архівовано 31 серпня 2019 у Wayback Machine.] (RLAI, лабораторія Річа Саттона в Альбертському університеті) (англ.)
• Autonomous Learning Laboratory [Архівовано 2 вересня 2016 у Wayback Machine.] (ALL, лабораторія Ендрю Барто в Массачусетському університеті в Емгерсті) (англ.)
• RL-Glue [Архівовано 19 лютого 2009 у Wayback Machine.]
• Програмні інструменти для навчання з підкріпленням [Архівовано 24 серпня 2016 у Wayback Machine.] (Matlab та Python)
• The Reinforcement Learning Toolbox. Архів оригіналу за 22 липня 2012 р. Від технічного університету Грацу.
• Гібридне навчання з підкріпленням [Архівовано 18 серпня 2019 у Wayback Machine.] (англ. Hybrid reinforcement learning) (англ.)
• Piqle: a Generic Java Platform for Reinforcement Learning [Архівовано 6 січня 2019 у Wayback Machine.]
• Коротке введення до деяких алгоритмів навчання з підкріпленням. Архів оригіналу за 8 листопада 2015 р. (англ.)
• Застосування навчання з підкріпленням до гри в хрестики-нулики [Архівовано 28 серпня 2016 у Wayback Machine.] (Perl)
• Scholarpedia Reinforcement Learning [Архівовано 4 вересня 2016 у Wayback Machine.] (англ.)
• Scholarpedia Temporal Difference Learning [Архівовано 19 серпня 2016 у Wayback Machine.] (англ.)
• Стендфордський курс із навчання з підкріпленням. Архів оригіналу за 21 березня 2012 р. (англ.)
• Реальні експерименти з навчання з підкріпленням в Делфтському технічному університеті
• Інструменти машинного навчання для Matlab [Архівовано 1 травня 2012 у Wayback Machine.]
• Ленція Ендрю Ина з навчання з підкріпленням у Стендфордському університеті [Архівовано 27 листопада 2016 у Wayback Machine.] (англ.)