Q-навча́ння (англ. Q-learning) — це алгоритм безмодельного[en] навчання з підкріпленням. Метою 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), отримуваною при переході від стану   до стану  , а   є темпом навчання[en] (англ. learning rate,  ).

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

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

Вплив зміннихРедагувати

Темп навчанняРедагувати

Темп навчання[en] (англ. 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-навчання можливо поєднувати з наближенням функцій[en].[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-навчання для застосування у поєднанні з (лінійним) наближенням функцій[en].[21] Перевагою жадібного GQ є те, що збіжність гарантовано навіть коли для оцінки цінності дій використовують наближення функції.

Див. такожРедагувати

ПриміткиРедагувати

  1. а б Melo Francisco S. Convergence of Q-learning: a simple proof. (англ.)
  2. а б Matiisen, Tambet (December 19, 2015). Demystifying Deep Reinforcement Learning. neuro.cs.ut.ee (en-US). Computational Neuroscience Lab. Процитовано 2018-04-06.  (англ.)
  3. Sutton, Richard; Barto, Andrew (1998). Reinforcement Learning: An Introduction. MIT Press.  (англ.)
  4. Russell, Stuart J.; Norvig, Peter (2010). Artificial Intelligence: A Modern Approach (вид. Third). Prentice Hall[en]. с. 649. ISBN 978-0136042594.  (англ.)
  5. Baird, Leemon (1995). Residual algorithms: Reinforcement learning with function approximation. 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. Архів оригіналу за 2013-09-08. Процитовано 2013-07-18.  (англ.)
  8. а б в Shteingart, Hanan; Neiman, Tal; Loewenstein, Yonatan (May 2013). The role of first impression in operant learning.. Journal of Experimental Psychology: General (en) 142 (2): 476–488. ISSN 1939-2222. PMID 22924882. doi:10.1037/a0029550.  (англ.)
  9. Hasselt, Hado van (5 March 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. Процитовано 2010-02-08.  (англ.)
  11. Watkins, C.J.C.H. (1989). Learning from Delayed Rewards (Ph.D. thesis). Cambridge University.  (англ.)
  12. Watkins and Dayan, C.J.C.H., (1992), 'Q-learning.Machine Learning' (англ.)
  13. Bozinovski, S. (15 July 1999). Crossbar Adaptive Array: The first connectionist network that solved the delayed reinforcement learning problem. У Dobnikar, Andrej; Steele, Nigel C.; Pearson, David W. та ін. 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 February 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. US Patent Office. 9 April 2015. Процитовано 28 July 2018.  (англ.)
  17. Mnih, Volodymyr; Kavukcuoglu, Koray; Silver, David; Rusu, Andrei A.; Veness, Joel; Bellemare, Marc G.; Graves, Alex; Riedmiller, Martin та ін. (Feb 2015). Human-level control through deep reinforcement learning. Nature (en) 518 (7540): 529–533. ISSN 0028-0836. PMID 25719670. doi:10.1038/nature14236.  (англ.)
  18. van Hasselt, Hado (2011). Double Q-learning (PDF). Advances in Neural Information Processing Systems 23: 2613–2622.  (англ.)
  19. van Hasselt, Hado; Guez, Arthur; Silver, David (2015). Deep reinforcement learning with double Q-learning (PDF). AAAI Conference on Artificial Intelligence: 2094–2100.  (англ.)
  20. Strehl, Alexander L.; Li, Lihong; Wiewiora, Eric; Langford, John; Littman, Michael L. (2006). Pac model-free reinforcement learning. Proc. 22nd ICML: 881–888.  (англ.)
  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. с. 719–726.  (англ.)

ПосиланняРедагувати