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

MDP на сітковому світі з урвищем, віддача і дисконт, функція цінності й рівняння Беллмана, ітерація цінності та ітерація політики, написані з нуля, як дисконт, посковзування і ціна кроку змінюють оптимальну поведінку, і перевірка симуляцією.

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

Серія Основи ШІ Частина 47 з 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 тем

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

Продовжує частини Марковські ланцюги, Математичне сподівання, дисперсія і коваріація та Види машинного навчання.

1. Агент, середовище, винагорода

Означення — марковський процес ухвалення рішень (MDP)

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

Наш світ — це сітка 6 × 5. Агент починає ліворуч (S) і може йти вгору, праворуч, униз або ліворуч. Увесь нижній рядок — урвище: хто в нього впаде, отримує −10, і гра закінчується. Недалеко від старту є мала ціль за +1, далеко праворуч — велика ціль за +10. Дві стіни закривають коротший шлях угору. А підлога може бути слизькою: з ймовірністю p агент замість задуманого напрямку посковзнеться в один із двох перпендикулярних напрямків.

P(s′ | s, a) = (1 − p) · [s′ = крок у напрямку a] + p/2 · [s′ = крок перпендикулярно ліворуч] + p/2 · [s′ = крок перпендикулярно праворуч]

P(s′ | s, a)

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

(1 − p) · […]

задуманий рух — отримує більшу частину ймовірності; при p = 0 лишається тільки цей доданок, і світ детермінований

p/2 · […]

посковзування вбік, порівну ліворуч і праворуч — через нього клітинка поруч з урвищем небезпечна, навіть коли ми йдемо вздовж нього, а не в нього

Приклад — крок праворуч уздовж урвища

Агент стоїть на клітинці праворуч від старту (над ним стіна, під ним урвище) і обирає «праворуч», p = 0,2:

• 0,8 — наступна клітинка праворуч,
• 0,1 — урвище (винагорода −10, кінець),
• 0,1 — клітинка праворуч від старту (посковзнеться вгору в стіну й залишиться на місці),

разом 0,8 + 0,1 + 0,1 = 1. Очікувана миттєва винагорода цього ходу становить 0,8 · 0 + 0,1 · (−10) + 0,1 · 0 = −1: у середньому кожен десятий такий крок закінчиться падінням.

2. Віддача, дисконт і політика

Означення — віддача і політика

Віддача від моменту t — це дисконтована сума майбутніх винагород G_t = r_t+1 + γ r_t+2 + γ² r_t+3 + …. Політика (policy) π визначає, яку дію обрати в якому стані — детерміновано π(s) = a або як розподіл π(a | s). Мета — політика з найбільшою очікуваною віддачею.

G_t = r_t+1 + γ · G_t+1

G_t

віддача від цієї миті до кінця — число, яке агент хоче мати якомога більшим

r_t+1

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

γ

дисконт — усе, що прийде пізніше, дешевшає на один множник γ; так «пізніше» перетворюється на «менше»

G_t+1

віддача від наступного кроку — та сама величина на крок далі; рекурсія, з якої незабаром виросте рівняння Беллмана

Теорема — при γ < 1 віддача завжди скінченна

Якщо кожна винагорода за абсолютним значенням не перевищує R_max, то |G_t| ≤ R_max (1 + γ + γ² + …) = R_max / (1 − γ), навіть якби епізод ніколи не закінчився.

Доведення. Нерівність трикутника дає |G_t| ≤ ∑_{k ≥ 0} γ^k |r_t+k+1| ≤ R_max ∑_{k ≥ 0} γ^k, а геометричний ряд зі знаменником 0 ≤ γ < 1 має суму 1/(1 − γ). ∎

У нас R_max = 10 і γ = 0,9, тож |G| ≤ 10 / 0,1 = 100. Без ціни за крок це ще набагато менше: ненульову винагороду дає лише вхід у ціль або в урвище, і то щонайбільше раз за епізод, тож |G| ≤ 10. Тому γ = 1 можна використати лише там, де епізод напевно закінчиться.

Приклад — віддача найкоротшого шляху до великої цілі

На твердій підлозі найкоротший шлях до цілі +10 веде через 6 кроків. Перші п’ять кроків дають винагороду 0, шостий (вхід у ціль) +10. При γ = 0,9:

G₀ = 0 + 0,9 · 0 + 0,9² · 0 + 0,9³ · 0 + 0,9⁴ · 0 + 0,9⁵ · 10 = 0,59049 · 10 = 5,9049.

На твердій підлозі нічого випадкового не відбувається, тож це безпосередньо цінність старту — і обчислення ітерацією цінності в розділі про політики справді дає 5,90. Мала ціль +1 навіть за 3 кроки дала б лише 0,9² · 1 = 0,81.

3. Цінність і рівняння Беллмана

Означення — функція цінності й рівняння оптимальності Беллмана

Цінність стану за політики π — це очікувана віддача, коли агент починає в s і дотримується π: V^π(s) = E_π[G_t | s_t = s]. Цінність дії Q^π(s, a) — те саме, коли першу дію визначаємо самі. Оптимальні цінності задовольняють рівняння Беллмана (Річард Беллман, 1957):

V*(s) = max_a ∑_s′ P(s′ | s, a) [R(s, a, s′) + γ V*(s′)],

а оптимальна політика — π*(s) = argmax_a Q*(s, a), де Q*(s, a) — вираз під максимумом.

V*(s) = max_a ∑_s′ P(s′ | s, a) [R(s, a, s′) + γ V*(s′)]

V*(s)

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

max_a

вибір агента — дію він обирає сам, тож бере найкращу; саме тут рівняння «оптимальності» відрізняється від рівняння для фіксованої політики π, де замість максимуму стоїть π(s)

∑_s′ P(s′ | s, a) […]

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

R(s, a, s′)

миттєва винагорода за цей перехід (+1, +10, −10 або ціна кроку)

γ

дисконт — майбутнє на крок далі, тому один множник γ (так само, як у формулі G_t = r_t+1 + γ G_t+1)

V*(s′)

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

Приклад — рівняння Беллмана на старті (посковзування 20 %, γ = 0,9)

Готові оптимальні цінності сусідів старту: клітинка над стартом V* = 3,325, клітинка праворуч V* = 2,260, сам старт V* = 2,854; урвище термінальне (цінність 0, винагорода −10). Підставимо в праву частину для кожної дії:

• ↑: 0,8 · (0 + 0,9 · 3,325) + 0,1 · (0 + 0,9 · 2,260) + 0,1 · (0 + 0,9 · 2,854) = 2,854,
• →: 0,8 · (0 + 0,9 · 2,260) + 0,1 · (−10 + 0,9 · 0,000) + 0,1 · (0 + 0,9 · 3,325) = 0,926,
• ↓: 0,8 · (−10 + 0,9 · 0,000) + 0,1 · (0 + 0,9 · 2,854) + 0,1 · (0 + 0,9 · 2,260) = −7,540,
• ←: 0,8 · (0 + 0,9 · 2,854) + 0,1 · (0 + 0,9 · 3,325) + 0,1 · (−10 + 0,9 · 0,000) = 1,354,

Найбільша — ↑ з 2,854, і це саме V*(старт) — рівняння виконується (різниця в останній цифрі — округлення). Дія «вгору» має цінність, попри 10-відсотковий шанс, що агент посковзнеться ліворуч, наткнеться на край і залишиться на старті: тому V*(старт) з’являється і праворуч. Дія «вниз» на 80 % веде в урвище й виходить глибоко від’ємною.

4. Ітерація цінності

Означення — ітерація цінності

Почни з V₀ = 0 і повторюй для всіх станів V_k+1(s) = max_a ∑_s′ P(s′ | s, a) [R + γ V_k(s′)], доки цінності змінюються. Оператор Беллмана при γ < 1 є стисканням: max_s |V_k+1 − V*| ≤ γ · max_s |V_k − V*|, тож похибка спадає щонайменше як γ^k.

# ітерація цінності
V = 0 у всіх станах
повторюй:
    для кожного нетермінального стану s:
        для кожної дії a:
            Q[a] = ∑ по s′ ( P(s′ | s, a) · (R(s, a, s′) + γ · V(s′)) )
        V_нове(s) = max(Q)
    зміна = max по s |V_нове(s) − V(s)|
    V = V_нове
доки зміна ≥ 10⁻⁶
π(s) = дія з найбільшим Q[a] (обчисленим із кінцевого V)

Приклад — перші три раунди (посковзування 20 %, γ = 0,9)

Стежимо за двома клітинками в середньому рядку: A одразу ліворуч від великої цілі +10 і B на клітинку далі, одразу праворуч від малої цілі +1. Над B стіна, над A вільно, під обома звичайна підлога.

раунд k	Vk(A)	найкраща дія в A	Vk(B)	найкраща дія в B
1	8,000	→	0,800	←
2	8,000	→	5,832	→
3	9,166	→	6,343	→

Раунд 1 (усюди V₀ = 0): з A крок праворуч з ймовірністю 0,8 веде в ціль, тобто 0,8 · 10 = 8,000. З B поки нічого далекого не видно, найкраще — крок ліворуч до малої цілі: 0,8 · 1 = 0,800.

Раунд 2: з B праворуч потрапляємо в A, яка вже має цінність 8: 0,8 · 0,9 · 8 = 5,76, до того 0,1 · 0,9 · 0,8 = 0,072 за посковзування вгору (стіна, агент лишається в B з V₁ = 0,8) і 0 за посковзування вниз — разом 5,832. Найкраща дія в B перекинулася з ← на →: інформація про велику ціль просунулася на клітинку далі.

max_s |V_k+1(s) − V_k(s)| ≤ γ^k · max_s |V₁(s) − V₀(s)|

max |V_k+1 − V_k|

найбільша зміна в раунді k + 1 — те, за чим обчислення стежить і за чим зупиняється; на графіку нижче зелена (γ = 0,9) і синя (γ = 0,99) лінія

γ^k

кожен раунд зменшує різницю двох оцінок щонайменше в γ разів (стискання); після k раундів отже в γ^k разів — звідси повільна збіжність для γ, близьких до 1

max |V₁ − V₀|

величина першої зміни; при V₀ = 0 це найбільша очікувана винагорода за один крок, у нас щонайбільше 10 — звідси пунктирна межа 10 · γ^k на графіку

При γ = 0,9 цінності усталюються (зміна менша за 10⁻⁶) після 50 ітерацій, при γ = 0,99 — після 77. Похибка спадає швидше, ніж гарантує межа γ^k, — вона виконується завжди, але для конкретного світу зазвичай песимістична. Що ближче γ до одиниці, то далі в майбутнє має поширитися інформація і то довше триває обчислення.

5. Що змінюють дисконт, посковзування і ціна кроку

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

На твердій підлозі найкоротший шлях до великої цілі веде впритул уздовж урвища: 6 кроків і цінність старту 5,90. Коли підлога слизька, край урвища небезпечний — кожен крок там означає 10-відсотковий шанс упасти. Тому оптимальна політика обходить стіни згори: 10 кроків замість 6, але в урвище падає лише в 0,7 % епізодів. Якби ми на слизькій підлозі застосували ризиковану політику, агент падав би в 30 % випадків, а цінність старту знизилася б до 0,64 замість 2,85.

При γ = 0,5 велика ціль настільки далеко, що не окупається — +10 через 10 кроків має сьогодні вагу лише 10 · 0,5¹⁰ ≈ 0,01. Агент обережно йде згори до малої цілі. Коли ж кожен крок коштує −1, ризикувати вигідно: агент іде до великої цілі краєм урвища і в 27 % епізодів падає. Довгий безпечний шлях коштував би йому більше, ніж середня втрата від падіння.

Стовпець «симуляція» — це перевірка: середня віддача з 10 000 епізодів за знайденою політикою, з випадковим посковзуванням. Середня віддача відрізняється від обчисленої цінності старту щонайбільше на кілька сотих — рівняння Беллмана справді обчислює очікувану віддачу.

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

6. Ітерація політики

Означення — ітерація політики

Ітерація політики (Рональд Говард, 1960) чергує два кроки. Оцінювання: для фіксованої політики π обчисли V^π, розв’язавши систему V^π(s) = ∑_s′ P(s′ | s, π(s)) [R + γ V^π(s′)]. Покращення: у кожному стані обери дію з найбільшою цінністю згідно з V^π. Коли політика перестає змінюватися, вона оптимальна.

# ітерація політики
π = «усюди вгору»
повторюй:
    # оцінювання: V^π розв’язанням системи (у нас повторним підставлянням)
    V = 0
    повторюй, доки V змінюється більше ніж на 10⁻⁹:
        V(s) = ∑ по s′ ( P(s′ | s, π(s)) · (R + γ · V(s′)) )   для кожного s
    # покращення: у кожному стані найкраща дія згідно з V^π
    π_нова(s) = argmax по a  ∑ по s′ ( P(s′ | s, a) · (R + γ · V(s′)) )
    змінених = кількість станів, де π_нова(s) ≠ π(s)
    π = π_нова
доки змінених > 0

Теорема — про покращення політики

Якщо нова політика π′ у кожному стані обирає дію з найбільшим Q^π(s, a), то V^π′(s) ≥ V^π(s) в усіх станах. Якщо π′ не відрізняється від π, то V^π задовольняє рівняння оптимальності Беллмана, а отже, π оптимальна.

Ескіз доведення. З вибору π′ маємо V^π(s) = Q^π(s, π(s)) ≤ Q^π(s, π′(s)) = E[r + γ V^π(s′)]. У V^π(s′) підставимо ту саму нерівність, потім знову… Після розгортання залишиться очікувана віддача політики, яка грає π′ на всіх кроках, тобто V^π′(s). ∎

Детермінованих політик скінченно багато — у нас 4 дії в 19 нетермінальних клітинках, тобто 4¹⁹ ≈ 2,7 · 10¹¹. Жодна не може повторитися (кожен раунд цінність покращує або завершується), тож ітерація політики завжди закінчується. Насправді раундів вистачає напрочуд мало: у нас 6.

На слизькій підлозі з γ = 0,9 і політикою «усюди вгору» на початку:

Після 6 раундів політика така сама, як з ітерації цінності. Раундів мало, але кожен містить повне оцінювання (у нас від десятків до сотень проходів світом). Який із двох методів швидший, залежить від задачі; на практиці їх поєднують.

7. Коли правила світу невідомі

Усе вище припускає, що ми знаємо P і R — можемо «зазирнути в правила». Це планування (динамічне програмування). У справжньому навчанні з підкріпленням агента кинуто у світ, правил якого він не знає: він мусить пробувати, збирати досвід і оцінювати цінності з нього. Рівняння Беллмана проте лишається серцем майже всіх методів — лише замість точного середнього за P використовується вибірка з одного реального кроку. Це Q-learning, тема наступної частини.

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

8. Підсумок

• MDP = стани, дії, випадкові переходи, винагороди й дисконт; наступний стан залежить лише від поточного стану й дії.
• Цінність стану — це очікувана дисконтована віддача; оптимальні цінності задовольняють рівняння Беллмана.
• Ітерація цінності повторює рівняння Беллмана; похибка спадає щонайменше як γ^k (у нас 50 ітерацій для γ = 0,9).
• Посковзування відсуває шлях від урвища (падіння 0,7 % замість 30 %), мале γ веде до малої близької цілі, ціна за крок — до ризику.
• Ітерація політики чергує оцінювання й покращення; у нас 6 раундів.
• Без знання правил світу цінності доводиться вивчати з досвіду — це і є навчання з підкріпленням.

Хочете спробувати самі? Доручіть ШІ-агенту запрограмувати цей світ з урвищем і інтерактивно змінювати γ, посковзування й ціну кроку — і стежте, коли політика «перекинеться» з одного шляху на інший.

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