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

Для спрощення на хвилинку припустімо, що досліджувана задача є епізодичною (англ. 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. Вибрати стратегію з найбільшою очікуваною віддачею

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

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

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

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

Щоби визначити оптимальність формальним чином, визначмо цінність (англ. 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)}$.

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

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

Проблема з методами, які використовують цінності дій, в тому, що вони можуть потребувати дуже точних оцінок цінностей порівнюваних дій, що може бути важко отримувати при зашумлених віддачах. І хоч ця проблема й пом'якшується до деякої міри методами часових різниць та застосуванням так званого методу сумісного наближення функції (англ. compatible function approximation method), належить зробити ще більше роботи для підвищення універсальності та ефективності. Ще одна проблема, властива методам часових різниць, випливає з їхньої залежності від рекурсивного рівняння Беллмана. Більшість методів часових різниць мають так званий параметр ${\displaystyle \lambda }$ ${\displaystyle (0\leq \lambda \leq 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] Проблема багатьох із цих методів у тому, що вони можуть застрягати в локальних оптимумах (оскільки вони ґрунтуються на локальному пошукові).

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

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

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