Q-навчання

Q-навча́ння (англ. Q-learning) — це алгоритм навчання з підкріпленням. Метою Q-навчання є навчитися стратегії, яка каже агентові, до якої дії вдаватися за яких обставин. Воно не вимагає моделі середовища (звідси уточнення «безмодельного»), і може розв'язувати задачі зі стохастичними переходами та винагородами, не вимагаючи пристосувань.

Для будь-якого скінченного марковського процесу вирішування (СМПВ, англ. finite Markov decision process, FMDP) Q-навчання знаходить стратегію, яка є оптимальною в тому сенсі, що вона максимізує очікуване значення повної винагороди над будь-якими та усіма послідовними кроками, починаючи з поточного стану. Q-навчання може визначати оптимальну стратегію обирання дій для довільного СМПВ за умови нескінченного часу на розвідування та частково випадкової стратегії. Символом Q позначають функцію, яка повертає винагороду, що використовують для забезпечення підкріплення, і про яку можливо сказати, що вона відповідає «якості» (англ. Quality) дії, обраної в поточному стані.

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

Докладніше: Навчання з підкріпленням

Навчання з підкріпленням включає агента, множину станів (англ. states) ${\displaystyle S}$, та множину дій за станами (англ. actions) ${\displaystyle A}$. Виконуючи дію ${\displaystyle a\in A}$, агент переходить зі стану до стану. Виконання дії в певному стані забезпечує агента винагородою (англ. reward, числовим балом).

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

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

• 0 секунд часу очікування + 15 секунд часу боротьби

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

• 5 секунд часу очікування + 0 секунд часу боротьби.

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

Алгоритм

Таблиця Q-навчання станів за діями, ініціалізована нулями, а потім кожну клітинку уточнено шляхом тренування.

Вага для кроку зі стану на ${\displaystyle \Delta t}$ кроків у майбутньому обчислюється як ${\displaystyle \gamma ^{\Delta t}}$, де ${\displaystyle \gamma }$ (коефіцієнт знецінювання, англ. discount-factor) є числом з 0 по 1 (${\displaystyle 0\leqslant \gamma \leqslant 1}$), і дає ефект оцінювання винагород, отриманих раніше, вище за отримані пізніше (відображаючи цінність «доброго початку»). ${\displaystyle \gamma }$ також можна тлумачити як імовірність досягнення успіху (або виживання) на кожному кроці ${\displaystyle \Delta t}$.

Цей алгоритм, отже, має функцію, що обчислює якість комбінації стан-дія:

${\displaystyle Q:S\times A\to \mathbb {R} }$.

Перед початком навчання ${\displaystyle Q}$ ініціалізують можливо довільним фіксованим значенням (що обирає програміст). Потім кожного моменту часу ${\displaystyle t}$ агент обирає дію ${\displaystyle a_{t}}$, спостерігає винагороду ${\displaystyle r_{t}}$, входить до нового стану ${\displaystyle s_{t+1}}$ (що може залежати як від попереднього стану ${\displaystyle s_{t}}$, так і від обраної дії), й ${\displaystyle Q}$ уточнюється. Ядром алгоритму є рівняння Беллмана як просте (уточнення з ітерацією за цінностями), що використовує зважене усереднення старої цінності та нової інформації:

${\displaystyle Q^{new}(s_{t},a_{t})\leftarrow \underbrace {Q(s_{t},a_{t})} _{\text{old value}}+\underbrace {\alpha } _{\text{learning rate}}\cdot \overbrace {{\bigg (}\underbrace {\underbrace {r_{t}} _{\text{reward}}+\underbrace {\gamma } _{\text{discount factor}}\cdot \underbrace {\max _{a}Q(s_{t+1},a)} _{\text{estimate of optimal future value}}} _{\text{new value (temporal difference target)}}-\underbrace {Q(s_{t},a_{t})} _{\text{old value}}{\bigg )}} ^{\text{temporal difference}}}$

де ${\displaystyle r_{t}}$ є винагородою (англ. reward), отримуваною при переході від стану ${\displaystyle s_{t}}$ до стану ${\displaystyle s_{t+1}}$, а ${\displaystyle \alpha }$ є темпом навчання (англ. learning rate, ${\displaystyle 0<\alpha \leqslant 1}$).

Епізод алгоритму закінчується тоді, коли стан ${\displaystyle s_{t+1}}$ є завершальним, або термінальним станом (англ. final, terminal state). Тим не менше, Q-навчання може також навчатися і в не епізодових завданнях.^[] Якщо коефіцієнт знецінювання (англ. discount factor) є меншим за 1, то цінності (англ. value) дій є скінченними, навіть якщо задача може містити нескінченні цикли.

Для всіх завершальних станів ${\displaystyle s_{f}}$, ${\displaystyle Q(s_{f},a)}$ ніколи не уточнюється, а встановлюється у значення винагороди ${\displaystyle r}$, спостережене для стану ${\displaystyle s_{f}}$. У більшості випадків ${\displaystyle Q(s_{f},a)}$ може бути взято рівним нулеві.

Вплив змінних

Темп навчання

Темп навчання (англ. learning rate), або розмір кроку (англ. step size), визначає, якою мірою новоотримана інформація перевизначатиме стару. Коефіцієнт 0 зробить так, що агент не навчатиметься нічого (використовуючи виключно апріорне знання), тоді як коефіцієнт 1 зробить так, що агент розглядатиме лише найновішу інформацію (ігноруючи попереднє знання для розвідування можливостей). У повністю (детермінованих) середовищах оптимальним є темп навчання ${\displaystyle \alpha _{t}(s,a)=1}$. Коли задача є стохастичною, алгоритм все одно збігатиметься за деяких технічних умов на темп навчання, які вимагають, щоби він знижувався до нуля. На практиці часто застосовують незмінний темп навчання, такий як ${\displaystyle \alpha _{t}=0.1}$ для всіх ${\displaystyle t}$.

Коефіцієнт знецінювання

Коефіцієнт знецінювання (англ. discount factor) ${\displaystyle \gamma }$ визначає важливість майбутніх винагород. Коефіцієнт 0 зробить агента «короткозорим», що розглядатиме лише поточні винагороди, тобто, ${\displaystyle r_{t}}$ (в наведеному вище правилі уточнювання), тоді як коефіцієнт, що наближується до 1, зробить його таким, що прагне довготривалої високої винагороди. Якщо коефіцієнт знецінювання дорівнює або перевищує 1, цінності дій можуть розбігатися. Для ${\displaystyle \gamma =1}$ без термінального стану, або якщо агент ніколи не досягає такого, всі історії середовища стають нескінченно довгими, і корисності з додатними винагородами без знецінювання в загальному випадку стають нескінченними. Навіть із коефіцієнтом знецінювання, лише трошки меншим за 1, навчання Q-функції веде до поширення похибок та нестабільностей, коли функція цінності наближують штучною нейронною мережею. В такому випадку початок із нижчого коефіцієнта знецінювання та збільшення його в напрямку його кінцевого значення прискорює навчання.

Початкові умови (Q₀)

Оскільки Q-навчання є ітеративним алгоритмом, воно неявно передбачає якісь початкові умови перед тим, як станеться перше уточнення. Високі початкові цінності, відомі також як «оптимістичні початкові умови», можуть заохочувати розвідування (англ. exploration): не важливо, яку дію обрано, правило уточнення призведе до того, що вона матиме нижчі цінності, ніж інші альтернативи, підвищуючи таким чином імовірність їхнього обрання. Для скидання початкових умов можливо застосовувати першу винагороду ${\displaystyle r}$. Відповідно до цієї ідеї, при першому виконанні дії цю винагороду використовують для встановлення значення ${\displaystyle Q}$. Це робить можливим негайне навчання у випадку фіксованих детерміністичних винагород. Очікується, що модель, яка включає скидання початкових умов (СПУ, англ. reset of initial conditions, RIC) передбачуватиме поведінку учасника краще, ніж модель, яка допускає будь-які довільні початкові умови (ДПУ, англ. arbitrary initial condition, AIC). СПУ видається відповідним людській поведінці в експериментах із повторюваним двійковим вибором.

Втілення

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

Наближення функцій

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

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

Квантування

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

Історія

Q-навчання було введено 1989 року. Доведення збіжності було представлено Воткінсом та Даяном 1992 року.

Воткінс розглядав «Навчання з затримуваних винагород», це назва його докторської дисертації. Вісьмома роками раніше, 1981 року, ту саму задачу, під назвою «Навчання з затримуваним підкріпленням» було розв'язано поперечинним адаптивним масивом (ПАМ, англ. Crossbar Adaptive Array, CAA) Божиновського. Матриця пам'яті W =||w(a,s)|| була такою же, як і Q-таблиця Q-навчання вісім років по тому. Ця архітектура ввела до навчання з підкріпленням термін «оцінювання стану» (англ. state evaluation). Алгоритм поперечинного навчання, записаний математичним псевдокодом у тій праці, на кожній ітерації виконує наступне обчислення:

• У стані s виконати дію a;
• Отримати наслідковий стан s’;
• Обчислити оцінку стану v(s’);
• Уточнити поперечинну цінність w’(a,s) = w(a,s) + v(s’).

Термін «вторинне підкріплення» (англ. secondary reinforcement) запозичено з теорії тваринного навчання, щоби моделювати стани через зворотне поширення: цінність стану v(s’) наслідкової ситуації поширюється зворотно до попередньо зустрінутих ситуацій. ПАМ обчислює цінності станів вертикально, а дій — горизонтально («поперечина»). Демонстраційні діаграми, які показували навчання з затримуваним підкріпленням, містили стани (бажані, небажані та нейтральні), які обчислювалися функцією оцінювання стану. Ця система навчання була предтечею алгоритму Q-навчання.

2014 року Google DeepMind запатентувала застосування Q-навчання до глибокого навчання, назване «глибоким навчанням з підкріпленням» (англ. deep reinforcement learning), або «глибоким Q-навчанням» (англ. deep Q-learning, DQN), яке може грати в ігри Atari 2600 на рівні людей-експертів.

Варіанти

Глибоке Q-навчання

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

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

Подвійне Q-навчання

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

На практиці дві окремі функції цінності, ${\displaystyle Q^{A}}$ та ${\displaystyle Q^{B}}$, тренують взаємно симетричним чином, використовуючи окремі досвіди. Відтак, крок уточнення подвійного Q-навчання є таким:

${\displaystyle Q_{t+1}^{A}(s_{t},a_{t})=Q_{t}^{A}(s_{t},a_{t})+\alpha _{t}(s_{t},a_{t})\left(r_{t}+\gamma Q_{t}^{B}\left(s_{t+1},\mathop {\operatorname {arg~max} } _{a}Q_{t}^{A}(s_{t+1},a)\right)-Q_{t}^{A}(s_{t},a_{t})\right)}$, та

${\displaystyle Q_{t+1}^{B}(s_{t},a_{t})=Q_{t}^{B}(s_{t},a_{t})+\alpha _{t}(s_{t},a_{t})\left(r_{t}+\gamma Q_{t}^{A}\left(s_{t+1},\mathop {\operatorname {arg~max} } _{a}Q_{t}^{B}(s_{t+1},a)\right)-Q_{t}^{B}(s_{t},a_{t})\right).}$

Тепер оцінювана цінність знецінюваного майбутнього оцінюється із застосуванням відмінної стратегії, що розв'язує проблему переоцінювання.

Цей алгоритм було пізніше видозмінено^[] 2015 року та поєднано з глибоким навчанням, як в алгоритмі глибокого Q-навчання (англ. DQN), що дало в результаті алгоритм подвійного глибокого Q-навчання (англ. Double DQN), який перевершує первинний алгоритм глибокого Q-навчання.

Інші

Затримане Q-навчання (англ. Delayed Q-learning) є альтернативним втіленням алгоритму інтерактивного Q-навчання з (імовірно приблизно правильним навчанням) (англ. probably approximately correct learning, PAC).

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

Див. також

• Метод часових різниць
• (Стан-дія-винагорода-стан-дія) (англ. SARSA)
• Ітеративна дилема в'язня
• Теорія ігор

Примітки

1. Melo Francisco S. Convergence of Q-learning: a simple proof. з джерела 18 листопада 2017. Процитовано 23 лютого 2020. (англ.)
2. Matiisen, Tambet (19 грудня 2015). . neuro.cs.ut.ee (амер.). Computational Neuroscience Lab. Архів оригіналу за 7 квітня 2018. Процитовано 6 квітня 2018. (англ.)
3. Sutton, Richard; Barto, Andrew (1998). . MIT Press. Архів оригіналу за 20 лютого 2020. Процитовано 4 березня 2020. (англ.)
4. ; (Norvig, Peter) (2010). Artificial Intelligence: A Modern Approach (вид. Third). Prentice Hall. с. 649. ISBN . (англ.)
5. Baird, Leemon (1995). Residual algorithms: Reinforcement learning with function approximation (PDF). ICML: 30—37. (англ.)
6. François-Lavet, Vincent; Fonteneau, Raphael; Ernst, Damien (7 грудня 2015). How to Discount Deep Reinforcement Learning: Towards New Dynamic Strategies. arXiv:1512.02011 [cs.LG]. (англ.)
7. Sutton, Richard S.; Barto, Andrew G. 2.7 Optimistic Initial Values. . Архів оригіналу за 8 вересня 2013. Процитовано 18 липня 2013. (англ.)
8. Shteingart, Hanan; Neiman, Tal; Loewenstein, Yonatan (May 2013). (PDF). Journal of Experimental Psychology: General (англ.). 142 (2): 476—488. doi:10.1037/a0029550. ISSN 1939-2222. PMID 22924882. Архів оригіналу (PDF) за 26 січня 2021. Процитовано 25 лютого 2020. (англ.)
9. Hasselt, Hado van (5 березня 2012). Reinforcement Learning in Continuous State and Action Spaces. У Wiering, Marco; Otterlo, Martijn van (ред.). Reinforcement Learning: State-of-the-Art. Springer Science & Business Media. с. 207—251. ISBN . (англ.)
10. Tesauro, Gerald (March 1995). . Communications of the ACM. 38 (3): 58—68. doi:10.1145/203330.203343. Архів оригіналу за 9 лютого 2010. Процитовано 8 лютого 2010. (англ.)
11. Watkins, C.J.C.H. (1989), (PDF) (Ph.D. thesis), Cambridge University, архів оригіналу (PDF) за 9 вересня 2016, процитовано 4 березня 2020 (англ.)
12. Watkins and Dayan, C.J.C.H., (1992), 'Q-learning.Machine Learning' (англ.)
13. Bozinovski, S. (15 липня 1999). Crossbar Adaptive Array: The first connectionist network that solved the delayed reinforcement learning problem. У Dobnikar, Andrej; Steele, Nigel C.; Pearson, David W.; Albrecht, Rudolf F. (ред.). Artificial Neural Nets and Genetic Algorithms: Proceedings of the International Conference in Portorož, Slovenia, 1999. Springer Science & Business Media. с. 320—325. ISBN . (англ.)
14. Bozinovski, S. (1982). A self learning system using secondary reinforcement. У Trappl, Robert (ред.). Cybernetics and Systems Research: Proceedings of the Sixth European Meeting on Cybernetics and Systems Research. North Holland. с. 397—402. ISBN . (англ.)
15. Barto, A. (24 лютого 1997). Reinforcement learning. У Omidvar, Omid; Elliott, David L. (ред.). Neural Systems for Control. Elsevier. ISBN . (англ.)
16. (PDF). US Patent Office. 9 квітня 2015. Архів оригіналу (PDF) за 29 липня 2018. Процитовано 28 липня 2018. (англ.)
17. Mnih, Volodymyr; Kavukcuoglu, Koray; Silver, David; Rusu, Andrei A.; Veness, Joel; Bellemare, Marc G.; Graves, Alex; Riedmiller, Martin; Fidjeland, Andreas K. (Feb 2015). Human-level control through deep reinforcement learning. Nature (англ.). 518 (7540): 529—533. doi:10.1038/nature14236. ISSN 0028-0836. PMID 25719670. (англ.)
18. van Hasselt, Hado (2011). . Advances in Neural Information Processing Systems. 23: 2613—2622. Архів оригіналу (PDF) за 26 березня 2020. Процитовано 4 березня 2020. (англ.)
19. van Hasselt, Hado; Guez, Arthur; Silver, David (2015). . AAAI Conference on Artificial Intelligence: 2094—2100. Архів оригіналу (PDF) за 6 лютого 2020. Процитовано 4 березня 2020. (англ.)
20. Strehl, Alexander L.; Li, Lihong; Wiewiora, Eric; Langford, John; Littman, Michael L. (2006). (PDF). Proc. 22nd ICML: 881—888. Архів оригіналу (PDF) за 14 квітня 2021. Процитовано 4 березня 2020. (англ.)
21. Maei, Hamid; Szepesvári, Csaba; Bhatnagar, Shalabh; Sutton, Richard (2010). (PDF). с. 719—726. Архів оригіналу (PDF) за 8 вересня 2012. Процитовано 25 січня 2016. (англ.)

Посилання

• Watkins, C.J.C.H. (1989). Learning from Delayed Rewards. PhD thesis, Cambridge University, Cambridge, England. [ 14 вересня 2018 у Wayback Machine.] (англ.)
• Strehl, Li, Wiewiora, Langford, Littman (2006). PAC model-free reinforcement learning (англ.)
• by Richard Sutton and Andrew S. Barto, an online textbook. See . (англ.)
• Piqle: a Generic Java Platform for Reinforcement Learning [ 6 січня 2019 у Wayback Machine.] (англ.)
• Reinforcement Learning Maze [ 27 вересня 2011 у Wayback Machine.], a demonstration of guiding an ant through a maze using Q-learning. (англ.)
• Q-learning work by Gerald Tesauro [ 4 червня 2011 у Wayback Machine.] (англ.)