Навчання з підкріпленням: вступ до Q-навчання

1. Марковські процеси прийняття рішень

Задачі навчання з підкріпленням формалізують як марковський процес прийняття рішень (MDP): кортеж (S, A, P, R, γ), де S — множина станів, A — множина дій, P(s'|s,a) — ймовірність переходу в стан s' після виконання дії a у стані s, R(s,a,s') — отримана винагорода, а γ ∈ [0,1) — коефіцієнт дисконтування, що визначає баланс між миттєвою та майбутньою винагородою.

Визначальна властивість — марковська властивість: майбутнє залежить лише від поточного стану, а не від історії, що до нього призвела. Наступна позиція агента в сітковому світі залежить лише від того, де він зараз, і яку дію він виконує — а не від шляху, яким він туди прийшов. Ця «безпам'ятність» і робить задачу розв'язною: агенту ніколи не потрібно пам'ятати більше, ніж теперішній стан.

Поведінка агента — це стратегія (policy) π(a|s), відображення станів на дії (або розподіл ймовірностей над діями). Мета навчання з підкріпленням — знайти стратегію π*, яка максимізує очікувану сумарну дисконтовану винагороду — віддачу (return):

2. Функції цінності та рівняння Беллмана

Замість оцінювання цілих траєкторій, алгоритми RL розкладають задачу за допомогою функцій цінності. Функція цінності стану V^π(s) — це очікувана віддача, починаючи зі стану s і слідуючи стратегії π надалі. Ще корисніша для керування — функція цінності дії, або Q-функція:

Q(s,a) відповідає на дуже конкретне питання: «якщо я виконаю дію a прямо зараз, а потім слідуватиму стратегії π назавжди, скільки сумарної дисконтованої винагороди я очікую отримати?» Щойно відома Q для оптимальної стратегії, діяти оптимально тривіально — просто обрати argmax_a Q*(s,a) у кожному стані. Це і є вся суть Q-навчання: вивчити Q* напряму, а оптимальна стратегія випливає безкоштовно.

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

Для оптимальної Q-функції стратегія всередині рекурсії замінюється на максимум, що дає рівняння оптимальності Беллмана:

Це рівняння — математичне серце Q-навчання. Воно стверджує, що оптимальна цінність виконання дії a у стані s дорівнює миттєвій винагороді плюс дисконтованій цінності оптимальної поведінки з будь-якого наступного стану.

3. Правило оновлення Q-навчання

Рівняння оптимальності Беллмана — це рівняння з нерухомою точкою, що включає (зазвичай невідомі) ймовірності переходів P і функцію винагороди R. Q-навчання обходить необхідність мати модель середовища взагалі — це безмодельний (model-free) метод часових різниць (temporal-difference, TD), який вчить Q* напряму з вибіркових переходів (s, a, r, s').

Спостерігши один перехід, агент підштовхує свою поточну оцінку Q(s,a) до кращої оцінки — спостереженої винагороди плюс дисконтованої цінності найкращої дії в наступному стані:

Тут α ∈ (0,1] — швидкість навчання, що визначає, наскільки сильно кожен новий досвід перезаписує стару оцінку. Величина в дужках r + γ max_a' Q(s',a') − Q(s,a) — це TD-помилка: розбіжність між тим, що агент передбачив, і тим, що він фактично спостеріг на наступному кроці. Q-навчання — позаполітичний (off-policy) метод: оновлення використовує max_a' Q(s',a'), цінність найкращої наступної дії, незалежно від того, яку дію агент насправді виконає далі. Агент може поводитися дослідницьки, водночас навчаючись жадібній, оптимальній стратегії.

4. Повний алгоритм

У табличній формі Q-навчання підтримує таблицю Q[s][a] з одним записом на кожну пару «стан-дія», ініціалізовану довільно (зазвичай нулями або малими випадковими значеннями):

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

5. Дослідження проти використання

Якщо агент завжди обирає дію з найвищою поточною оцінкою Q (використання), він може назавжди застрягти на посередній стратегії просто тому, що жодного разу не спробував кращу дію достатньо, щоб дізнатися її справжню цінність. Якщо ж він завжди діє випадково (дослідження), він ніколи не використає те, чого навчився. Це напруження і є компромісом «дослідження проти використання», і кожен практичний алгоритм RL потребує стратегії для його балансування.

ε-жадібна стратегія

Найпростіша і найпоширеніша стратегія: з ймовірністю ε виконати рівномірно випадкову дію; з ймовірністю 1−ε — жадібну дію argmax_a Q(s,a). ε зазвичай починається високою (наприклад, 1.0 — чисте дослідження) і поступово знижується до невеликого порогу (наприклад, 0.05) протягом навчання, зсуваючи агента від відкриття до використання по мірі того, як його оцінки стають надійнішими.

Softmax / дослідження Больцмана

Замість жорсткого поділу випадково/жадібно, дії вибираються пропорційно exp(Q(s,a)/τ), де τ — параметр температури. Висока τ робить розподіл майже рівномірним (дослідження); низька τ — різко зосередженим на найкращій дії (використання). На відміну від ε-жадібної стратегії, це природно уникає марнування дослідження на дії, які вже відомо як значно гірші за найкращу.

Оптимістична ініціалізація

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

6. Чому Q-навчання збігається

Воткінс і Дейан довели у 1992 році, що табличне Q-навчання збігається до Q* з ймовірністю 1 за виконання двох умов:

• Кожна пара «стан-дія» відвідується нескінченно часто (що гарантує будь-яка розумна стратегія дослідження зі стійким ε > 0 протягом нескінченного часу)
• Швидкість навчання α спадає належним чином, задовольняючи Σα_t = ∞ і Σα_t² < ∞ (наприклад, α_t = 1/t) — достатньо сумарного навчання, щоб перезаписати погані початкові оцінки, але спадання достатньо швидке, щоб шум окремих вибірок зрештою усереднився

Інтуїція пов'язана з теорією нерухомої точки: оператор оптимальності Беллмана є стискаючим відображенням у max-нормі, тобто повторне застосування геометрично скорочує відстань до справжнього Q* незалежно від початкової точки. Кожне оновлення Q-навчання — це стохастична апроксимація застосування цього оператора, тож за виконання зазначених умов зашумлені оновлення збігаються до тієї ж нерухомої точки, якої досяг би точний оператор.

7. Q-навчання проти SARSA

SARSA (State-Action-Reward-State-Action) — найближчий родич Q-навчання, що відрізняється рівно одним рядком у правилі оновлення:

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

8. Масштабування: глибокі Q-мережі

Таблиця Q[s][a] чудово підходить, коли простір станів невеликий — кілька тисяч клітинок сітки. Вона безнадійна для сирих пікселів (кадр Atari має більше можливих станів, ніж атомів у видимому Всесвіті) або неперервних сенсорних вхідних даних. Глибока Q-мережа (Deep Q-Network, DQN), представлена DeepMind у 2015 році, замінює таблицю нейронною мережею Q(s,a; θ), яка бере стан і видає Q-значення для кожної дії, навчаючись градієнтним спуском мінімізувати квадрат TD-помилки:

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

• Реплей досвіду (experience replay) — зберігати переходи (s,a,r,s') у буфері й тренуватися на випадково вибраних міні-пакетах, розриваючи сильну часову кореляцію між послідовними вибірками та ефективніше повторно використовуючи дані
• Цільова мережа (target network) — θ⁻ у формулі втрат вище — це повільно оновлювана (або періодично заморожувана) копія θ, що запобігає зсуву бутстрап-цілі на кожному кроці градієнта й «гонитві за власним хвостом»

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

9. Практичні пастки

Зміщення переоцінки

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

Розрідженість винагороди

Якщо винагорода надходить лише наприкінці довгого епізоду (наприклад, «перемога» або «поразка» після 500 кроків), TD-сигналу практично нема чого поширювати назад протягом більшої частини навчання. Формування винагороди (додавання невеликих проміжних винагород, що спрямовують поведінку), заохочувальні бонуси на основі цікавості та реплей досвіду заднім числом (hindsight experience replay) — усі вони по-різному вирішують цю проблему.

Смертельна тріада

Саттон і Барто виділяють три складники, які в поєднанні можуть спричинити розбіжність замість збіжності: апроксимація функції (нейронна мережа замість таблиці), бутстрапінг (оновлення оцінок на основі інших оцінок, як це робить рівняння Беллмана) і позаполітичне навчання (навчання про стратегію, відмінну від тієї, що генерує дані — саме те, що робить член max_a' у Q-навчанні). Усі три окремо цінні й спільно ризиковані; цільові мережі та буфери реплею DQN — це, по суті, інженерні контрзаходи проти цієї нестабільності.

Дискретизація станів і дій

Табличне Q-навчання вимагає скінченного дискретного простору станів-дій. Неперервні задачі потрібно або дискретизувати (грубі кошики втрачають точність, дрібні — вибухають розміром таблиці — прокляття розмірності), або обробляти апроксимацією функції (DQN), або алгоритмами, спроєктованими нативно для неперервних дій, такими як DDPG чи SAC.