Q-навчання

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Алгоритм[ред.ред. код]

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

Алгоритм, отже, має функцію, що обчислює величину (англ. Quantity) поєднання стан-дія:

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

де є винагородою (англ. reward), що спостерігається після виконання в , () є темпом навчання (англ. learning rate, може бути однаковим для усіх пар), англ. old value — стара цінність, англ. discount factor — коефіцієнт знецінювання, англ. estimate of optimal future value — оцінка оптимальної майбутньої цінності, англ. learned value — навчена цінність.

Епізод алгоритму закінчується тоді, коли стан є завершальним станом (або «поглинальним станом», англ. absorbing state). Тим не менше, Q-навчання може також навчатися і в не епізодичних завданнях. Якщо коефіцієнт знецінювання є меншим за 1, то цінності дій є скінченними, навіть якщо задача може містити нескінченні цикли.

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

Вплив змінних на алгоритм[ред.ред. код]

Темп навчання[ред.ред. код]

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

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

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

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

Оскільки Q-навчання є ітеративним алгоритмом, воно неявно припускає якісь початкові умови перед тим, як станеться певне уточнення. Високі початкові цінності, також відомі як «оптимістичні початкові умови»,[5] можуть заохочувати дослідження: не важливо, яку дію обрано, правило уточнення призведе до того, що вона матиме нижчі цінності, ніж інші альтернативи, підвищуючи таким чином імовірність їхнього вибору. Нещодавно було запропоновано, що для скидання початкових умов могла би застосовуватися перша винагорода .[джерело?] Згідно цієї ідеї, при першому виконанні дії ця винагорода використовується для встановлення значення . Це уможливлюватиме негайне навчання у випадку фіксованих детерміністичних винагород. Дивно, але цей підхід скидання початкових умов (англ. resetting-of-initial-conditions, RIC) здається відповідним людській поведінці в експериментах із двійковим вибором.[6]

Реалізація[ред.ред. код]

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

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

Ранні етапи дослідження[ред.ред. код]

Q-навчання було вперше представлено Уоткінзом 1989 року.[9] Доведення збіжності було представлено пізніше Уоткінзом та Даяном 1992 року.[10]

Варіанти[ред.ред. код]

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

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

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

Q-навчання може страждати від низького темпу збіжності, особливо коли коефіцієнт знецінювання є близьким до одиниці.[14] Швидке Q-навчання (англ. Speedy Q-learning), новий варіант алгоритму Q-навчання, розправляється з цією проблемою, і отримує довідно такий самий темп збіжності, як і методи на основі моделей, такі як ітерація за цінностями.[15]

Нещодавнє застосування Q-навчання до глибинного навчання компанією Google DeepMind, назване «глибинним навчанням із підкріпленням» (англ. deep reinforcement learning) або «глибинними Q-мережами» (англ. deep Q-networks), досягло успіху в грі у деякі ігри Atari 2600 на експертних для людей рівнях. Попередні результати було представлено 2014 року, а працю опубліковано в лютому 2015 року в Nature.[16]

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

Примітки[ред.ред. код]

  1. Reinforcement Learning: An Introduction. Richard Sutton and Andrew Barto. MIT Press, 1998. (англ.)
  2. Stuart J. Russell[en]; Peter Norvig (2010). Artificial Intelligence: A Modern Approach (вид. Third). Prentice Hall[en]. с. 649. ISBN 978-0136042594.  (англ.)
  3. Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. ICML, pages 30–37, 1995 (англ.)
  4. François-Lavet Vincent, Raphael Fonteneau, Damien Ernst. "How to Discount Deep Reinforcement Learning: Towards New Dynamic Strategies". NIPS, Deep RL workshop 2015. (англ.)
  5. http://webdocs.cs.ualberta.ca/~sutton/book/ebook/node21.html (англ.)
  6. Shteingart, H; Neiman, T; Loewenstein, Y (May 2013). The Role of First Impression in Operant Learning. J Exp Psychol Gen. 142 (2). с. 476–88. PMID 22924882. doi:10.1037/a0029550.  (англ.)
  7. Tesauro, Gerald (March 1995). Temporal Difference Learning and TD-Gammon. Communications of the ACM 38 (3). doi:10.1145/203330.203343. Процитовано 2010-02-08.  (англ.)
  8. Hado van Hasselt. Reinforcement Learning in Continuous State and Action Spaces. In: Reinforcement Learning: State of the Art, Springer, pages 207-251, 2012 (англ.)
  9. Watkins, C.J.C.H., (1989), Learning from Delayed Rewards. Ph.D. thesis, Cambridge University. (англ.)
  10. Watkins and Dayan, C.J.C.H., (1992), 'Q-learning.Machine Learning' (англ.)
  11. Alexander L. Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael L. Littman. Pac model-free reinforcement learning. In Proc. 22nd ICML 2006, pages 881–888, 2006. (англ.)
  12. van Hasselt, Hado (2011). Double Q-learning (PDF). Advances in Neural Information Processing Systems 23. с. 2613–2622.  (англ.)
  13. Hamid Maei, and Csaba Szepesvári, Shalabh Bhatnagar and Richard Sutton. Toward off-policy learning control with function approximation. In proceedings of the 27th International Conference on Machine Learning, pages 719-726, 2010. (англ.)
  14. Csaba Szepesva ́ri. The asymptotic convergence-rate of Q-learning. Advances in Neural Information Processing Systems 10, Denver, Colorado, USA, 1997. (англ.)
  15. Gheshlaghi Azar, Mohammad; Munos, Remi; Ghavamzadeh, Mohammad; Kappen, Hilbert J. (2011). Speedy Q-Learning (PDF). Advances in Neural Information Processing Systems 24. с. 2411–2419.  (англ.)
  16. Mnih, Volodymyr (2015). Human-level control through deep reinforcement learning 518. с. 529–533.  (англ.)

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