Q-навчання і DQN: як навчитися цінності дій — від таблиці до нейронної мережі

Навчання за часовими різницями, Q-навчання і SARSA на прогулянці краєм урвища, ε-жадібне дослідження, on-policy та off-policy, DQN із пам’яттю досвіду й цільовою мережею на маятнику на візку, написане з нуля, і чому навчання DQN так легко розвалюється.

12 хвилин Matěj Žalmánek 2026-10-16

Серія Основи ШІ Частина 48 з 52

1. Мапа штучного інтелекту: що є що і як усе це пов’язано
2. Коротка історія штучного інтелекту: від Тюрінга до мовних моделей
3. Дані, модель, тренування, інференс: основні поняття на одному прикладі
4. Як читати математичний запис: символи, індекси, суми та квантори
5. Множини й відношення: конструктор, з якого складаються означення в ШІ
6. Функції й відображення: чому кожна модель у ШІ — це функція
7. Логіка й доведення: правила, за якими міркують у ШІ
8. Графи й дерева: структура, на якій тримаються пошук і нейронні мережі
9. Лінійна алгебра для машинного навчання: вектори, матриці й чому ШІ передусім множить
10. Похідні, градієнт і правило ланцюжка: як модель дізнається, у якому напрямку вчитися
11. Градієнтний спуск: як навчається модель
12. Що таке ймовірність: від кидка кубика до аксіом Колмогорова
13. Умовна ймовірність і теорема Баєса: як змінити оцінку, коли дізнаєтеся щось нове
14. Випадкова величина і функція розподілу: одна функція, яка каже про розподіл усе
15. Функція щільності та функція маси ймовірності: чому неперервна величина має в точці ймовірність нуль
16. Математичне сподівання, дисперсія і коваріація: де лежить розподіл, наскільки він широкий і що з чим пов’язано
17. Огляд розподілів ймовірностей: Бернуллі, біноміальний, Пуассона, рівномірний, нормальний і експоненційний
18. Закон великих чисел і центральна гранична теорема: чому середні поводяться так передбачувано
19. Статистика й оцінювання параметрів: максимальна правдоподібність, MAP і довірчі інтервали
20. Теорія інформації: ентропія, перехресна ентропія і KL-дивергенція — звідки беруться функції втрат
21. Пошук у просторі станів: BFS, DFS, UCS і A* з анімаціями
22. Ігри та суперник: мінімакс, альфа-бета відсікання і Monte Carlo tree search
23. Задоволення обмежень: бектрекінг, поширення обмежень і AC-3 на судоку та мапі чеських країв
24. Логіка й системи, засновані на знаннях: пряме і зворотне виведення, резолюція та експертні системи
25. Планування: STRIPS, світ кубиків, евристики з релаксації та планування в AI-агентах
26. Локальний пошук та імітація відпалу: комівояжер через обласні центри Чехії
27. Генетичні алгоритми: популяція, схрещування, мутація і добір на рюкзаку для походу
28. Еволюційні стратегії і генетичне програмування: від правила однієї п’ятої до закону Кеплера
29. Оптимізація мурашиною колонією: як феромоновий слід знаходить короткий шлях
30. Оптимізація роєм частинок: інерція, власний досвід і досвід рою
31. Нейроеволюція: еволюція ваг і форми нейронних мереж та алгоритм NEAT
32. Нечіткі множини й функції належності: як записати «трохи тепло»
33. Нечітка логіка та ймовірність: чому «трохи тепло» не означає «імовірно тепло»
34. Нечітка логіка: t-норми, імплікації та правила ЯКЩО–ТО
35. Нечітке керування: Мамдані та Суґено від вентилятора до маятника на візку
36. Нечітка кластеризація: алгоритм fuzzy c-means і точки між кластерами
37. Нейро-нечіткі системи (ANFIS): нечіткі правила, які навчаються з даних
38. Марковські ланцюги: матриця переходів, стаціонарний розподіл і PageRank
39. Приховані марковські моделі: алгоритм Вітербі й нечесне казино
40. Байєсівські мережі: чому трава мокра і що з цього випливає для дощувача
41. Фільтр Калмана: як за неточними вимірюваннями оцінити, де авто і як швидко воно їде
42. Види машинного навчання: з учителем, без учителя, з частковим залученням учителя та інші
43. Промпти, контекст і RAG: як дати моделі правильну інформацію
44. Варіаційні автокодувальники (VAE): нові зображення з неперервного латентного простору
45. Генеративні змагальні мережі (GAN): фальшувальник проти детектива
46. Дифузійні моделі: як із чистого шуму постає зображення
47. Марковські процеси ухвалення рішень: стани, дії, винагороди й рівняння Беллмана
48. Q-навчання і DQN: як навчитися цінності дій — від таблиці до нейронної мережі
49. Policy gradient і PPO: навчання безпосередньо політики
50. Як працює ШІ-агент: мовна модель у циклі з інструментами
51. Програмування з AI-агентами: завдання, тести й перевірка
52. Оцінювання і безпека систем ШІ: як вимірювати і як стежити

Повна програма серії Готово: 52 з 83 тем

У минулій частині ми обчислили найкращу політику точно, бо знали правила світу: куди яка дія з якою ймовірністю веде і що агент за неї отримає. Справжній агент їх не знає. Робот не знає, як саме в нього прослизне колесо, програма, що грає гру, не бачить нутрощів гри. Він мусить пробувати й навчатися з того, що сталося. У цій частині ми напишемо два такі алгоритми: Q-навчання (Q-learning) з таблицею і DQN, де таблицю замінить нейронна мережа, — саме ту комбінацію, з якою DeepMind 2015 року навчив комп’ютер грати в десятки ігор Atari з екрана.

Продовжує частини Марковські процеси ухвалення рішень та Нейронна мережа з нуля.

1. Навчання з досвіду

Означення — навчання за часовими різницями (TD)

Замість середнього за всіма можливими наступними станами (як у рівнянні Беллмана) використовують один справді пережитий перехід (s, a, r, s′). Оцінка зсувається на невеликий крок у бік TD-цілі r + γ · (оцінка цінності s′): оцінка ← оцінка + α (ціль − оцінка). Різницю ціль − оцінка називають TD-похибкою, α — швидкість навчання. Отже, оцінку виправляють за іншою оцінкою (bootstrapping).

V(s) ← V(s) + α [r + γ V(s′) − V(s)]

V(s)

дотеперішня оцінка цінності стану, з якого ми вийшли, — її ми виправляємо; усередині дужок вона віднімається, щоб виправлення було пропорційне похибці, а не всій цінності

α

швидкість навчання, 0 < α ≤ 1 — яку частку похибки ми приймаємо; один перехід — це випадкова вибірка, тож ми не довіряємо йому повністю

r

справді отримана винагорода — єдина частина цілі, яку виміряно, а не оцінено

γ

дисконт — цінність наступного стану надходить на крок пізніше, так само як у рівнянні Беллмана

V(s′)

оцінка цінності стану, куди ми справді потрапили, — вона заступає все решту майбутнього, якого ми ще не пережили (bootstrapping); замість середнього ∑ P(s′ | …) одна-єдина вибірка

Приклад — дорога на роботу в числах

Оцінка з дому V(дім) = 30 хвилин. Після r = 10 хвилин їзди ви в заторі, і оцінка звідси V(затор) = 35. Час не дисконтується (γ = 1), а замість винагороди ми додаємо хвилини, тож TD-ціль дорівнює 10 + 35 = 45, а TD-похибка 45 − 30 = 15.

• з α = 0,5: нова оцінка 30 + 0,5 · 15 = 37,5 хвилини,
• з α = 0,1: 30 + 0,1 · 15 = 31,5 хвилини,
• з α = 1: одразу 45 — останній досвід повністю переписав би весь попередній.

Теорема — зі сталим α оцінка є ковзним середнім цілей

Якщо оцінка починає з Q₀ і отримує цілі c₁, c₂, …, c_n, то після n виправлень Q_n = (1 − α)ⁿ Q₀ + ∑_k=1ⁿ α (1 − α)^n−k c_k.

Доведення. Правило можна переписати як Q_n = (1 − α) Q_n−1 + α c_n і підставляти багаторазово. ∎

Ваги спадають геометрично: з α = 0,5 остання ціль має вагу 0,5, передостання 0,25, наступна 0,125… Старіший досвід, отже, поступово забувається — це допомагає, коли цілі змінюються (а в TD-навчанні вони змінюються, бо обчислені з оцінок, які самі навчаються), але у випадковому світі оцінка коливається. Тому для гарантованої збіжності теорія вимагає поступово зменшувати α.

2. Q-навчання

Означення — Q-навчання і SARSA

Q-навчання (Q-learning; Крістофер Воткінс, 1989) веде таблицю Q(s, a) і після кожного кроку її виправляє:

Q(s, a) ← Q(s, a) + α [r + γ · max_a′ Q(s′, a′) − Q(s, a)].

За розумних умов (кожну пару стан–дія пробують нескінченно багато разів, α належно спадає) воно збігається до оптимальної Q*. SARSA відрізняється лише ціллю: замість максимуму використовує Q(s′, a′) для дії a′, яку агент справді виконає. Q-навчання, отже, вивчає цінність найкращої поведінки, SARSA — цінність того, як агент насправді поводиться, разом із пробуванням.

Q(s, a) ← Q(s, a) + α [r + γ · max_a′ Q(s′, a′) − Q(s, a)]

Q(s, a)

клітинка таблиці для щойно випробуваної дії — виправляють лише її; інші дії в s не змінилися, бо цей крок нічого про них не сказав

α

швидкість навчання — у нас 0,5: світ на урвищі детермінований, тож нової цілі нам боятися нічого

r

винагорода за крок: −1 або −100 за падіння

γ

дисконт — на урвищі γ = 1, бо епізод завжди закінчується і кожен крок коштує −1, тож коротший шлях кращий і без дисконту

max_a′ Q(s′, a′)

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

# Q-навчання (і SARSA) на прогулянці краєм урвища
Q(s, a) = 0 для всіх станів і дій
для кожного епізоду:
    s = старт
    a = ε-жадібна дія за Q в s
    поки s не фініш:
        виконай a, спостерігай r і s′     # падіння: r = −100, s′ = старт
        a′ = ε-жадібна дія за Q в s′
        ціль = max за b Q(s′, b)         # Q-навчання
        ціль = Q(s′, a′)                 # SARSA (замість рядка вище)
        якщо s′ фініш: ціль = 0
        Q(s, a) = Q(s, a) + α · (r + γ · ціль − Q(s, a))
        s = s′;  a = a′

Приклад — перші падіння (α = 0,5, γ = 1, таблиця починається з нулів)

Агент одразу на старті пробує крок праворуч і падає: r = −100, s′ = старт, де поки що всі значення 0. Нове значення Q(старт, →) = 0 + 0,5 · (−100 + 1 · 0 − 0) = −50.

Потім пробує крок угору: r = −1, нова клітинка має самі нулі, Q(старт, ↑) = 0 + 0,5 · (−1 + 0 − 0) = −0,5.

Коли він на старті впаде вдруге, найбільше значення на старті все ще 0 (дії ↓ і ← він ще не пробував), тож Q(старт, →) = −50 + 0,5 · (−100 + 0 − (−50)) = −75. З кожним наступним падінням воно наближається до −100 і далі.

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

Означення — ε-жадібна політика

З імовірністю 1 − ε обери дію з найбільшим Q(s, a), з імовірністю ε — випадкову дію. Без випадкових дій агент ніколи не спробував би нічого, що поки не здається йому найкращим, і міг би застрягнути на першому пристойному шляху, який знайде. Це найпростіше розв’язання дилеми дослідження чи використання (exploration vs. exploitation).

Приклад — імовірності дій при ε = 0,1

Випадкову дію вибирають з усіх |A| = 4 дій, тобто і з найкращої. Тому

π(a | s) = 1 − ε + ε/|A| = 1 − 0,1 + 0,025 = 0,925 для найкращої дії та ε/|A| = 0,1/4 = 0,025 для кожної з трьох інших.

Кожна конкретна «погана» дія — скажімо, крок униз в урвище — отже, трапляється в одному кроці із 40.

3. Прогулянка краєм урвища: Q-навчання проти SARSA

Класичний експеримент із підручника Річарда Саттона та Ендрю Барто (cliff walking). Сітка 12 × 4, старт ліворуч унизу, фініш праворуч унизу, а між ними урвище. Кожен крок коштує −1, падіння в урвище −100 і повернення на старт. Без дисконту. Найкоротший шлях пролягає впритул уздовж урвища (13 кроків). Обидва алгоритми навчаються 500 епізодів з ε = 0,1 і α = 0,5, кожен у 50 незалежних прогонах.

Q-навчання в усіх 50 з 50 прогонів вивчило найкоротший шлях уздовж урвища. SARSA у 41 прогонах обрала шлях верхнім краєм сітки, якомога далі від урвища (17 кроків), в одному — ще на два кроки довший, а в 8 прогонах жадібна політика після 500 епізодів до фінішу ще не доходить — зациклюється в місцях, куди агент під час навчання майже не потрапляв.

А тепер парадокс: під час навчання краще почувається SARSA. За останні сто епізодів вона отримує в середньому −25,1, Q-навчання −51,1. Q-навчання ходить краєм урвища, і оскільки кожен десятий крок випадковий, падає в середньому 0,34 разу за епізод; SARSA лише 0,04 разу. Q-навчання вивчило, що найкраще без пробування; SARSA — що найкраще із пробуванням. Що з цього нам потрібно, залежить від того, чи пробуватиме агент і в реальній роботі, — робот, який навчається на справжній машині, мав би думати як SARSA.

Приклад — скільки разів падає Q-навчання (спрощена оцінка)

Вивчений шлях Q-навчання веде від старту вгору, а потім десять клітинок впритул над урвищем. На старті й на кожній із цих десяти клітинок в урвище веде крок униз (на старті крок праворуч), тобто одна конкретна дія — при ε = 0,1 з імовірністю 0,025. Пройти 11 таких клітинок без падіння:

0,975¹¹ = 0,757, тож падіння за один прохід має ймовірність q = 1 − 0,757 = 0,243.

Після падіння агент починає знову зі старту, тож кількість падінь до успішного проходу має геометричний розподіл із математичним сподіванням q / (1 − q) = 0,243 / 0,757 = 0,32 падіння за епізод. Виміряно 0,34 — трохи більше, бо оцінка нехтує випадковими кроками ліворуч, після яких агент проводить над урвищем ще кілька кроків. SARSA ходить верхнім краєм, три рядки над урвищем: туди її могли б скинути лише кілька випадкових кроків униз поспіль. Ризикує вона переважно на старті, і це саме по собі дає 0,025 / 0,975 = 0,026 падіння за епізод; виміряно 0,04.

Означення — навчання за власною і чужою політикою (on-policy / off-policy)

Метод є on-policy, коли вивчає цінність тієї політики, за якою саме діє (SARSA). Він off-policy, коли діє за однією політикою (скажімо, ε-жадібною), а вивчає цінність іншої (Q-навчання вивчає жадібну). Методи off-policy можуть навчатися й з досвіду, зібраного раніше або кимось іншим.

4. Коли таблиця не вміщається: DQN

Таблиці потрібен рядок для кожного стану. Маятник на візку з частини про нейроеволюцію має стан із чотирьох дійсних чисел (положення й швидкість візка, кут і кутова швидкість жердини); гра на Atari має стан з екрана 210 × 160 пікселів. Жодна таблиця. Замість неї Q(s, a) оцінюють нейронною мережею.

Означення — Deep Q-Network (DQN)

DQN (Володимир Мних та ін., DeepMind, 2015) оцінює Q(s, ·) мережею з параметрами θ і мінімізує (r + γ max_a′ Q(s′, a′; θ⁻) − Q(s, a; θ))². Два доповнення є ключовими: пам’ять досвіду (replay buffer) — переходи зберігаються, і навчання йде на випадкових пакетах, а не на останніх кроках поспіль; і цільова мережа (target network) θ⁻ — копія мережі, яку оновлюють лише час від часу, щоб ціль не зсувалася з кожним кроком навчання.

L(θ) = E_{(s, a, r, s′) ~ D} [(r + γ max_a′ Q(s′, a′; θ⁻) − Q(s, a; θ))²]

E_{… ~ D}

середнє за випадковими переходами з пам’яті досвіду D — перемішує старий і новий досвід, тож послідовні, дуже схожі кроки не тягнуть мережу в один бік

r

винагорода — на візку +1 за кожен крок, коли жердина стоїть

γ

дисконт 0,99 — мережа «бачить» приблизно на 1/(1 − γ) = 100 кроків уперед

max Q(s′, a′; θ⁻)

ціль із цільової мережі із замороженими параметрами θ⁻ — той самий максимум, що й у табличному Q-навчанні, тільки під час кроку навчання він не рухається; коли стан s′ означає падіння, цей член дорівнює 0

Q(s, a; θ)

оцінка мережі, що навчається, для дії, яку справді виконали, — єдине, що під час кроку навчання змінюється (градієнт іде лише через θ)

Означення — функція втрат Губера

Наше DQN замість квадрата похибки d = Q(s, a; θ) − ціль використовує (як і оригінальна стаття, що обрізає похибку до ±1) функцію втрат Губера H(d) = d²/2 для |d| ≤ 1 і |d| − 1/2 інакше. Її похідна дорівнює d посередині й ±1 назовні: малі похибки виправляються як у квадрата, велика похибка (скажімо, коли ціль стрибне після копіювання цільової мережі) дає щонайбільше одиничний градієнт, і один дивний перехід мережу не розладнає.

# DQN на маятнику на візку
мережа Q(·; θ) 4 → 64 → 64 → 2, цільова мережа θ⁻ = θ, пам’ять D порожня
s = випадковий старт
для t = 1 … 30 000:
    ε = max(0,05; 1 − 0,95 · t / 10 000)
    a = випадкова дія з імовірністю ε, інакше argmax Q(s, ·; θ)
    виконай a, спостерігай s′ і чи впала жердина
    збережи (s, a, r = 1, s′, впала) у D     # найстаріший випадає понад 20 000
    s = новий старт, якщо жердина впала або протрималася 500 кроків, інакше s′
    вибери з D випадковий пакет 32 переходів, для кожного:
        ціль = r,                          якщо впала
        ціль = r + γ · max Q(s′, ·; θ⁻),   інакше
    один крок Adam на середній втраті Губера (Q(s, a; θ) − ціль)
    кожні 500 кроків: θ⁻ = θ

Приклад — дослідження і величина цінностей

Дослідження спадає лінійно: ε₀ = 1 (самі випадкові дії), на кроці 5 000 ε = 1 − 0,95 · 0,5 = 0,525, а від кроку 10 000 лишається 0,05.

Наскільки великих цінностей має навчитися мережа? Якби жердина стояла вічно, цінність була б 1 + 0,99 + 0,99² + … = 1/(1 − 0,99) = 100; для епізоду, обмеженого 500 кроками, це (1 − 0,99⁵⁰⁰)/(1 − 0,99) = 99,3. На початку мережа повертає числа, близькі до нуля, тож цілі під час навчання мусять зрости на два порядки — і разом із ними постійно зсуваються.

Наше DQN: мережа 4 → 64 → 64 → 2 (дві дії: штовхати ліворуч або праворуч), винагорода +1 за кожен крок, коли жердина стоїть, γ = 0,99, пам’ять на 20 000 переходів, пакет 32, цільова мережа копіюється кожні 500 кроків, ε спадає від 1 до 0,05 протягом перших 10 000 кроків. Загалом 30 000 кроків. Кожні 2 500 кроків ми вимірюємо, скільки кроків протримається жадібна політика (середнє з чотирьох стартів, щонайбільше 500, тобто 10 секунд).

Повне DQN навчається утримувати жердину всі 500 кроків — у прогоні із зерном 1 уперше на кроці 17 500. Але одразу ж знову забуває: наприкінці навчання тримає лише 110 кроків. Другий прогін коливається схоже. Без пам’яті досвіду (навчається лише з останніх 32 кроків) мережа не підніметься вище 192. А без цільової мережі навчання зовсім розвалюється: політика весь час протримується лише 9 кроків — рівно стільки, скільки протримається візок, який ви весь час штовхаєте праворуч. Мережа «вивчила» одну-єдину дію.

5. Чому DQN таке примхливе

Означення — смертельна тріада (deadly triad)

Так Саттон і Барто називають поєднання трьох складників: апроксимації функції (мережа замість таблиці), bootstrapping (ціль обчислюють із власної оцінки) та навчання off-policy. Кожен окремо безпечний; разом навчання може коливатися або розбігатися. DQN містить усі три — пам’ять досвіду й цільова мережа небезпеку лише пом’якшують.

Тому на практиці додають цілу низку вдосконалень: Double DQN (Гадо ван Гасселт та ін., 2015) відокремлює вибір найкращої дії від її оцінювання і гасить систематичне завищення, яке приносить максимум у цілі; далі пріоритизована пам’ять, розділення на цінність і перевагу (dueling) та інші — їхнє поєднання називається Rainbow (2017). І зовсім практична порада: під час навчання зберігайте мережу з найкращого вимірювання, а не останню.

y = r + γ Q(s′, argmax_a′ Q(s′, a′; θ); θ⁻)

r

винагорода, без змін

γ

дисконт, без змін

argmax Q(s′, a′; θ)

вибір дії мережею, що навчається, — яку дію ми обрали б у s′

Q(s′, …; θ⁻)

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

Приклад — чому максимум переоцінює (спрощено)

Дві дії мають справжню цінність 0, але оцінка кожної обтяжена незалежною похибкою +1 або −1 (обидві з імовірністю 1/2). Чотири однаково ймовірні варіанти дають максимум оцінок 1, 1, 1 і −1, тож

E[max(Q̂₁, Q̂₂)] = (1 + 1 + 1 − 1)/4 = 0,5 > 0 = max(Q₁, Q₂).

Максимум за зашумленими оцінками в середньому більший за максимум справжніх цінностей, а оскільки ціль із максимумом підставляють знову і знову, переоцінка поширюється. Коли дію вибирає одна оцінка, а оцінює друга, незалежна, математичне сподівання оцінювання дорівнює 0 — похибка другої оцінки вже не пов’язана з вибором.

Ціннісні методи на кшталт DQN добре працюють, коли дій мало (штовхати ліворуч або праворуч; кнопки на геймпаді). Для неперервних дій — з якою силою повернути суглоб робота — вигідніше навчати безпосередньо політику. Це тема наступної частини — про policy gradient і PPO.

6. Підсумок

• Не знаючи правил світу, цінності вивчають із пережитих переходів: оцінка зсувається до цілі r + γ · оцінка наступного стану.
• Q-навчання вивчає цінність найкращої поведінки (off-policy), SARSA — цінність поведінки з пробуванням (on-policy).
• На урвищі: Q-навчання знаходить найкоротший шлях (13 кроків), але при ε = 0,1 падає 0,34 разу за епізод; SARSA йде безпечніше й під час навчання отримує більше (−25,1 проти −51,1).
• DQN замінює таблицю мережею; без пам’яті досвіду і без цільової мережі воно не навчається (щонайбільше 192 і 9 кроків відповідно).
• Навіть повне DQN коливається: утримує жердину 500 кроків, а потім знову це забуває — смертельна тріада.

Хочете спробувати самі? Попросіть ШІ-агента навчити DQN у середовищі CartPole з бібліотеки Gymnasium і намалювати криву навчання для п’яти зерен. Потім нехай додасть Double DQN і порівняє.

Маєте іншу думку? Напишіть на support@coden-app.com.