Q-навчання

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

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

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

Навчання з підкріпленням включає агента, множину станів (Шаблон:Lang-en) Шаблон:Tmath, та множину дій за станами (Шаблон:Lang-en) Шаблон:Tmath. Виконуючи дію $a\in A$, агент переходить зі стану до стану. Виконання дії в певному стані забезпечує агента винагородою (Шаблон:Lang-en, числовим балом).

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

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

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

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

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

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

Алгоритм

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

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

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

$Q:S\times A\to ℝ$.

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

$Q^{new}(s_t,a_t)\leftarrow \underset{\text{old value}}{\underbrace{Q(s_t,a_t)}}+\underset{\text{learning rate}}{\underbrace{\alpha }}\cdot \stackrel{\text{temporal difference}}{\overbrace{(\underset{\text{new value (temporal difference target)}}{\underbrace{\underset{\text{reward}}{\underbrace{r_t}}+\underset{\text{discount factor}}{\underbrace{\gamma }}\cdot \underset{\text{estimate of optimal future value}}{\underbrace{\underset{a}{\max }Q(s_{t+1},a)}}}}-\underset{\text{old value}}{\underbrace{Q(s_t,a_t)}})}}$

де $r_t$ є винагородою (Шаблон:Lang-en), отримуваною при переході від стану $s_t$ до стану $s_{t+1}$, а $\alpha$ є темпом навчання (Шаблон:Lang-en, $0<\alpha ⩽1$).

Епізод алгоритму закінчується тоді, коли стан $s_{t+1}$ є завершальним, або термінальним станом (Шаблон:Lang-en). Тим не менше, Q-навчання може також навчатися і в не епізодових завданнях.Шаблон:Citation needed Якщо коефіцієнт знецінювання (Шаблон:Lang-en) є меншим за 1, то цінності (Шаблон:Lang-en) дій є скінченними, навіть якщо задача може містити нескінченні цикли.

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

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

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

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

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

Коефіцієнт знецінювання (Шаблон:Lang-en) Шаблон:Tmath визначає важливість майбутніх винагород. Коефіцієнт 0 зробить агента «короткозорим», що розглядатиме лише поточні винагороди, тобто, $r_t$ (в наведеному вище правилі уточнювання), тоді як коефіцієнт, що наближується до 1, зробить його таким, що прагне довготривалої високої винагороди. Якщо коефіцієнт знецінювання дорівнює або перевищує 1, цінності дій можуть розбігатися. Для Шаблон:Tmath без термінального стану, або якщо агент ніколи не досягає такого, всі історії середовища стають нескінченно довгими, і корисності з додатними винагородами без знецінювання в загальному випадку стають нескінченними. Навіть із коефіцієнтом знецінювання, лише трошки меншим за 1, навчання Q-функції веде до поширення похибок та нестабільностей, коли функція цінності наближують штучною нейронною мережею. В такому випадку початок із нижчого коефіцієнта знецінювання та збільшення його в напрямку його кінцевого значення прискорює навчання.

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

Оскільки Q-навчання є ітеративним алгоритмом, воно неявно передбачає якісь початкові умови перед тим, як станеться перше уточнення. Високі початкові цінності, відомі також як «оптимістичні початкові умови», можуть заохочувати розвідування (Шаблон:Lang-en): не важливо, яку дію обрано, правило уточнення призведе до того, що вона матиме нижчі цінності, ніж інші альтернативи, підвищуючи таким чином імовірність їхнього обрання. Для скидання початкових умов можливо застосовувати першу винагороду Шаблон:Tmath. Відповідно до цієї ідеї, при першому виконанні дії цю винагороду використовують для встановлення значення Шаблон:Tmath. Це робить можливим негайне навчання у випадку фіксованих детерміністичних винагород. Очікується, що модель, яка включає скидання початкових умов (СПУ, Шаблон:Lang-en) передбачуватиме поведінку учасника краще, ніж модель, яка допускає будь-які довільні початкові умови (ДПУ, Шаблон:Lang-en). СПУ видається відповідним людській поведінці в експериментах із повторюваним двійковим вибором.

Втілення

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

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

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

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

Квантування

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

Історія

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

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

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

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

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

Варіанти

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

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

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

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

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

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

$Q_{t+1}^A(s_t,a_t)=Q_t^A(s_t,a_t)+{\alpha }_t(s_t,a_t)(r_t+\gamma Q_t^B(s_{t+1},{\mathrm{arg~max}}_a{Q}_t^A(s_{t+1},a))-Q_t^A(s_t,a_t))$, та

$Q_{t+1}^B(s_t,a_t)=Q_t^B(s_t,a_t)+{\alpha }_t(s_t,a_t)(r_t+\gamma Q_t^A(s_{t+1},{\mathrm{arg~max}}_a{Q}_t^B(s_{t+1},a))-Q_t^B(s_t,a_t)).$

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

Цей алгоритм було пізніше видозміненоШаблон:Clarify 2015 року та поєднано з глибоким навчанням, як в алгоритмі глибокого Q-навчання (Шаблон:Lang-en), що дало в результаті алгоритм подвійного глибокого Q-навчання (Шаблон:Lang-en), який перевершує первинний алгоритм глибокого Q-навчання.

Інші

Затримане Q-навчання (Шаблон:Lang-en) є альтернативним втіленням алгоритму інтерактивного Q-навчання з імовірно приблизно правильним навчанням (Шаблон:Lang-en).

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

Див. також

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

Посилання

• Watkins, C.J.C.H. (1989). Learning from Delayed Rewards. PhD thesis, Cambridge University, Cambridge, England. Шаблон:Webarchive Шаблон:Ref-en
• Strehl, Li, Wiewiora, Langford, Littman (2006). PAC model-free reinforcement learning Шаблон:Ref-en
• Reinforcement Learning: An Introduction by Richard Sutton and Andrew S. Barto, an online textbook. See «6.5 Q-Learning: Off-Policy TD Control». Шаблон:Ref-en
• Piqle: a Generic Java Platform for Reinforcement Learning Шаблон:Webarchive Шаблон:Ref-en
• Reinforcement Learning Maze Шаблон:Webarchive, a demonstration of guiding an ant through a maze using Q-learning. Шаблон:Ref-en
• Q-learning work by Gerald Tesauro Шаблон:Webarchive Шаблон:Ref-en