Вікіпедія

Q-навчання

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

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

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

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

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

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

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

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

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

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

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

Алгоритм ред.

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

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

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

 .

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

 

де   є винагородою (англ. reward), отримуваною при переході від стану   до стану  , а   є темпом навчання (англ. learning rate,  ).

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

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

Вплив змінних ред.

Темп навчання ред.

Темп навчання (англ. learning rate), або розмір кроку (англ. step size), визначає, якою мірою новоотримана інформація перевизначатиме стару. Коефіцієнт 0 зробить так, що агент не навчатиметься нічого (використовуючи виключно апріорне знання), тоді як коефіцієнт 1 зробить так, що агент розглядатиме лише найновішу інформацію (ігноруючи попереднє знання для розвідування можливостей). У повністю детермінованих середовищах оптимальним є темп навчання  . Коли задача є стохастичною, алгоритм все одно збігатиметься за деяких технічних умов на темп навчання, які вимагають, щоби він знижувався до нуля. На практиці часто застосовують незмінний темп навчання, такий як   для всіх  .[3]

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

Коефіцієнт знецінювання (англ. discount factor)   визначає важливість майбутніх винагород. Коефіцієнт 0 зробить агента «короткозорим», що розглядатиме лише поточні винагороди, тобто,   (в наведеному вище правилі уточнювання), тоді як коефіцієнт, що наближується до 1, зробить його таким, що прагне довготривалої високої винагороди. Якщо коефіцієнт знецінювання дорівнює або перевищує 1, цінності дій можуть розбігатися. Для   без термінального стану, або якщо агент ніколи не досягає такого, всі історії середовища стають нескінченно довгими, і корисності з додатними винагородами без знецінювання в загальному випадку стають нескінченними.[4] Навіть із коефіцієнтом знецінювання, лише трошки меншим за 1, навчання Q-функції веде до поширення похибок та нестабільностей, коли функція цінності наближують штучною нейронною мережею.[5] В такому випадку початок із нижчого коефіцієнта знецінювання та збільшення його в напрямку його кінцевого значення прискорює навчання.[6]

Початкові умови (Q0) ред.

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

Втілення ред.

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

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

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

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

Квантування ред.

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

Історія ред.

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

Воткінс розглядав «Навчання з затримуваних винагород», це назва його докторської дисертації. Вісьмома роками раніше, 1981 року, ту саму задачу, під назвою «Навчання з затримуваним підкріпленням» було розв'язано поперечинним адаптивним масивом (ПАМ, англ. Crossbar Adaptive Array, CAA) Божиновського.[13][14] Матриця пам'яті 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-навчання.[15]

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

Варіанти ред.

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

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

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

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

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

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

 , та
 

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

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

Інші ред.

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

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

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

Примітки ред.

  1. ↑ а б Melo Francisco S. Convergence of Q-learning: a simple proof. Архівовано з джерела 18 листопада 2017. Процитовано 23 лютого 2020. (англ.)
  2. ↑ а б Matiisen, Tambet (19 грудня 2015). Demystifying Deep Reinforcement Learning. neuro.cs.ut.ee (амер.). Computational Neuroscience Lab. Архів оригіналу за 7 квітня 2018. Процитовано 6 квітня 2018. (англ.)
  3. ↑ Sutton, Richard; Barto, Andrew (1998). Reinforcement Learning: An Introduction. MIT Press. Архів оригіналу за 20 лютого 2020. Процитовано 4 березня 2020. (англ.)
  4. ↑ Russell, Stuart J.; Norvig, Peter (2010). Artificial Intelligence: A Modern Approach (вид. Third). Prentice Hall. с. 649. ISBN 978-0136042594. (англ.)
  5. ↑ Baird, Leemon (1995). Residual algorithms: Reinforcement learning with function approximation (PDF). ICML: 30—37. (англ.)
  6. ↑ François-Lavet, Vincent; Fonteneau, Raphael; Ernst, Damien (2015-12-07). «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. Reinforcement Learning: An Introduction. Архів оригіналу за 8 вересня 2013. Процитовано 18 липня 2013. (англ.)
  8. ↑ а б в Shteingart, Hanan; Neiman, Tal; Loewenstein, Yonatan (May 2013). The role of first impression in operant learning (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 978-3-642-27645-3. (англ.)
  10. ↑ Tesauro, Gerald (March 1995). Temporal Difference Learning and TD-Gammon. Communications of the ACM. 38 (3): 58—68. doi:10.1145/203330.203343. Архів оригіналу за 9 лютого 2010. Процитовано 8 лютого 2010. (англ.)
  11. ↑ Watkins, C.J.C.H. (1989), Learning from Delayed Rewards (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 978-3-211-83364-3. (англ.)
  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 978-0-444-86488-8. (англ.)
  15. ↑ Barto, A. (24 лютого 1997). Reinforcement learning. У Omidvar, Omid; Elliott, David L. (ред.). Neural Systems for Control. Elsevier. ISBN 978-0-08-053739-9. (англ.)
  16. ↑ Methods and Apparatus for Reinforcement Learning, US Patent #20150100530A1 (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). Double Q-learning. Advances in Neural Information Processing Systems. 23: 2613—2622. Архів оригіналу (PDF) за 26 березня 2020. Процитовано 4 березня 2020. (англ.)
  19. ↑ van Hasselt, Hado; Guez, Arthur; Silver, David (2015). Deep reinforcement learning with double Q-learning. 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). Pac model-free reinforcement learning (PDF). Proc. 22nd ICML: 881—888. Архів оригіналу (PDF) за 14 квітня 2021. Процитовано 4 березня 2020. (англ.)
  21. ↑ Maei, Hamid; Szepesvári, Csaba; Bhatnagar, Shalabh; Sutton, Richard (2010). Toward off-policy learning control with function approximation in Proceedings of the 27th International Conference on Machine Learning (PDF). с. 719—726. Архів оригіналу (PDF) за 8 вересня 2012. Процитовано 25 січня 2016. (англ.)

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

Отримано з https://uk.wikipedia.org/w/index.php?title=Q-навчання&oldid=40697033