Przejdź do treści
coden

Procesy decyzyjne Markowa: stany, akcje, nagrody i równania Bellmana

MDP na świecie-siatce z klifem, zwrot i dyskonto, funkcja wartości i równanie Bellmana, iteracja wartości i iteracja polityki napisane od zera, jak dyskonto, poślizg i koszt kroku zmieniają optymalne zachowanie, oraz sprawdzenie symulacją.

11 minut Matěj Žalmánek 2026-10-16

Seria Podstawy AI Część 47 z 52
  1. Mapa sztucznej inteligencji: co jest czym i jak to do siebie pasuje
  2. Krótka historia sztucznej inteligencji: od Turinga do modeli językowych
  3. Dane, model, trening, inferencja: podstawowe pojęcia na jednym przykładzie
  4. Jak czytać zapis matematyczny: symbole, indeksy, sumy i kwantyfikatory
  5. Zbiory i relacje: klocki, z których składają się definicje w AI
  6. Funkcje i odwzorowania: dlaczego każdy model AI jest funkcją
  7. Logika i dowody: reguły, według których rozumuje AI
  8. Grafy i drzewa: struktura, na której opierają się przeszukiwanie i sieci neuronowe
  9. Algebra liniowa dla uczenia maszynowego: wektory, macierze i dlaczego AI głównie mnoży
  10. Pochodne, gradient i reguła łańcuchowa: jak model ustala, w którą stronę się uczyć
  11. Spadek gradientu: jak uczy się model
  12. Czym jest prawdopodobieństwo: od rzutu kostką do aksjomatów Kołmogorowa
  13. Prawdopodobieństwo warunkowe i twierdzenie Bayesa: jak zmienić ocenę, gdy dowiesz się czegoś nowego
  14. Zmienna losowa i dystrybuanta: jedna funkcja, która mówi o rozkładzie wszystko
  15. Funkcja gęstości i funkcja prawdopodobieństwa: dlaczego zmienna ciągła ma w punkcie prawdopodobieństwo zero
  16. Wartość oczekiwana, wariancja i kowariancja: gdzie leży rozkład, jak jest szeroki i co z czym się wiąże
  17. Przegląd rozkładów prawdopodobieństwa: Bernoulliego, dwumianowy, Poissona, jednostajny, normalny i wykładniczy
  18. Prawo wielkich liczb i centralne twierdzenie graniczne: dlaczego średnie zachowują się tak przewidywalnie
  19. Statystyka i estymacja parametrów: największa wiarygodność, MAP i przedziały ufności
  20. Teoria informacji: entropia, entropia krzyżowa i dywergencja KL — skąd się biorą funkcje straty
  21. Przeszukiwanie przestrzeni stanów: BFS, DFS, UCS i A* z animacjami
  22. Gry i przeciwnik: minimax, przycinanie alfa-beta i Monte Carlo tree search
  23. Spełnianie ograniczeń: backtracking, propagacja ograniczeń i AC-3 na sudoku i mapie czeskich krajów
  24. Logika i systemy z bazą wiedzy: wnioskowanie w przód i wstecz, rezolucja i systemy ekspertowe
  25. Planowanie: STRIPS, świat klocków, heurystyki z relaksacji i planowanie w agentach AI
  26. Przeszukiwanie lokalne i symulowane wyżarzanie: komiwojażer przez czeskie miasta wojewódzkie
  27. Algorytmy genetyczne: populacja, krzyżowanie, mutacja i selekcja na plecaku na wycieczkę
  28. Strategie ewolucyjne i programowanie genetyczne: od reguły jednej piątej do prawa Keplera
  29. Optymalizacja kolonią mrówek: jak ślad feromonowy znajduje krótką drogę
  30. Optymalizacja rojem cząstek: bezwładność, własne doświadczenie i doświadczenie roju
  31. Neuroewolucja: ewolucja wag i kształtu sieci neuronowych oraz algorytm NEAT
  32. Zbiory rozmyte i funkcje przynależności: jak zapisać „trochę ciepło”
  33. Logika rozmyta a prawdopodobieństwo: dlaczego „trochę ciepło” nie znaczy „prawdopodobnie ciepło”
  34. Logika rozmyta: t-normy, implikacje i reguły JEŻELI–TO
  35. Sterowanie rozmyte: Mamdani i Sugeno od wentylatora po wahadło na wózku
  36. Klasteryzacja rozmyta: algorytm fuzzy c-means i punkty między skupieniami
  37. Systemy neuro-rozmyte (ANFIS): reguły rozmyte, które uczą się z danych
  38. Łańcuchy Markowa: macierz przejścia, rozkład stacjonarny i PageRank
  39. Ukryte modele Markowa: algorytm Viterbiego i nieuczciwe kasyno
  40. Sieci bayesowskie: dlaczego trawa jest mokra i co z tego wynika dla zraszacza
  41. Filtr Kalmana: jak z niedokładnych pomiarów oszacować, gdzie jest samochód i jak szybko jedzie
  42. Rodzaje uczenia maszynowego: nadzorowane, nienadzorowane, półnadzorowane i inne
  43. Prompty, kontekst i RAG: jak dać modelowi właściwe informacje
  44. Wariacyjne autoenkodery (VAE): nowe obrazki z ciągłej przestrzeni latentnej
  45. Generatywne sieci przeciwstawne (GAN): fałszerz kontra detektyw
  46. Modele dyfuzyjne: jak z czystego szumu powstaje obraz
  47. Procesy decyzyjne Markowa: stany, akcje, nagrody i równania Bellmana
  48. Q-learning i DQN: uczenie się wartości akcji od tabeli po sieć neuronową
  49. Policy gradient i PPO: uczenie się bezpośrednio polityki
  50. Jak działa agent AI: model językowy w pętli z narzędziami
  51. Programowanie z agentami AI: zadanie, testy i kontrola
  52. Ocena i bezpieczeństwo systemów AI: jak mierzyć i jak pilnować

Pełny program serii Gotowe: 52 z 83 tematów

Czego się dowiesz
  • Jak opisać zadanie uczenia ze wzmocnieniem jako MDP.
  • Czym jest wartość stanu i jak oblicza ją równanie Bellmana.
  • Dlaczego drobiazgi w nagrodach i dyskoncie całkowicie zmieniają zachowanie agenta.

Warto wiedzieć wcześniej: Łańcuchy Markowa: macierz przejścia, rozkład stacjonarny i PageRank, Wartość oczekiwana, wariancja i kowariancja: gdzie leży rozkład, jak jest szeroki i co z czym się wiąże, Rodzaje uczenia maszynowego: nadzorowane, nienadzorowane, półnadzorowane i inne

Dotąd modele w serii uczyły się z przykładów z poprawną odpowiedzią albo szukały struktury w danych. Uczenie ze wzmocnieniem to trzecia droga: agent działa, świat daje mu za to nagrody i kary, a agent ma odkryć, jak działać, żeby zebrać ich jak najwięcej. Zanim zabierzemy się do uczenia, potrzebujemy języka, którym takie zadanie dokładnie opiszemy. Jest nim proces decyzyjny Markowa. W tej części zbudujemy go na małym świecie z klifem i dokładnie obliczymy najlepsze zachowanie — przy założeniu, że znamy reguły świata.

Nawiązuje do części Łańcuchy Markowa, Wartość oczekiwana, wariancja i kowariancja oraz Rodzaje uczenia maszynowego.

1. Agent, środowisko, nagroda

Definicja — proces decyzyjny Markowa (MDP)

MDP to piątka (S, A, P, R, γ): zbiór stanów S, zbiór akcji A, prawdopodobieństwa przejścia P(s′ | s, a), nagroda R(s, a, s′) i współczynnik dyskontowy γ ∈ [0, 1). W każdym kroku agent w stanie s wybiera akcję a, świat losowo zgodnie z P przenosi go do s′, a agent dostaje nagrodę. Własność Markowa: następny stan zależy tylko od bieżącego stanu i akcji, nie od historii.

Mówiąc prościej

Gra planszowa z kostką: wiesz, na którym jesteś polu (stan), wybierasz ruch (akcja), kostka decyduje, gdzie naprawdę się przesuniesz (przejście), a za niektóre pola dostajesz punkty (nagroda). To, jak dotarłeś na pole, nie ma znaczenia — ważne jest tylko, gdzie stoisz teraz.

Nasz świat to siatka 6 × 5. Agent zaczyna po lewej (S), może iść w górę, w prawo, w dół albo w lewo. Cały dolny wiersz to klif: kto w niego wpadnie, dostaje −10 i gra się kończy. Niedaleko startu jest mały cel za +1, daleko po prawej duży cel za +10. Dwie ściany zamykają krótszą drogę górą. A podłoga może być śliska: z prawdopodobieństwem p agent zamiast w zamierzonym kierunku ześlizguje się w jeden z dwóch kierunków prostopadłych.

P(s′ | s, a) = (1 − p) · [s′ = krok w kierunku a] + p/2 · [s′ = krok prostopadle w lewo] + p/2 · [s′ = krok prostopadle w prawo]

P(s′ | s, a)
z jakim prawdopodobieństwem agent po akcji a skończy na polu s′ — cały rozkład, a nie tylko „dokąd ma iść”, bo wartość ruchu będzie liczona jako średnia po wszystkich możliwych miejscach lądowania
(1 − p) · […]
zamierzony ruch — dostaje większość prawdopodobieństwa; przy p = 0 zostaje tylko ten składnik i świat jest deterministyczny
p/2 · […]
poślizg w bok, po równo w lewo i w prawo — przez niego pole obok klifu jest niebezpieczne, nawet gdy idziemy wzdłuż niego, a nie w niego
[warunek] wynosi 1, gdy warunek jest spełniony, w przeciwnym razie 0. Jeśli ruch trafi w ścianę lub krawędź, to s′ = s i odpowiednie składniki się sumują — suma po wszystkich s′ zawsze wynosi 1. Rozkład 0,8 / 0,1 / 0,1 (tzn. p = 0,2) ma też klasyczny świat-siatka z podręcznika Russella i Norviga.
Przykład — krok w prawo wzdłuż klifu

Agent stoi na polu na prawo od startu (nad nim jest ściana, pod nim klif) i wybiera „w prawo”, p = 0,2:

  • 0,8 — kolejne pole w prawo,
  • 0,1 — klif (nagroda −10, koniec),
  • 0,1 — pole na prawo od startu (ześlizguje się w górę na ścianę i zostaje na miejscu),

razem 0,8 + 0,1 + 0,1 = 1. Oczekiwana natychmiastowa nagroda za ten ruch wynosi 0,8 · 0 + 0,1 · (−10) + 0,1 · 0 = −1: średnio co dziesiąty taki krok kończy się upadkiem.

2. Zwrot, dyskonto i polityka

Definicja — zwrot i polityka

Zwrot od chwili t to zdyskontowana suma przyszłych nagród Gt = rt+1 + γ rt+2 + γ² rt+3 + …. Polityka (policy) π mówi, jaką akcję wybrać w którym stanie — deterministycznie π(s) = a albo jako rozkład π(a | s). Celem jest polityka o największym oczekiwanym zwrocie.

Mówiąc prościej

Dyskonto γ mówi, o ile nagroda jutro jest mniej warta niż dziś. Przy γ = 0,9 nagroda za dziesięć kroków ma wagę 0,9¹⁰ ≈ 0,35, przy γ = 0,5 tylko 0,001. Małe γ czyni agenta niecierpliwym, γ bliskie 1 cierpliwym. Polityka to wtedy po prostu ściągawka: „na tym polu idź w prawo, na tamtym w górę”.

Gt = rt+1 + γ · Gt+1

Gt
zwrot od teraz do końca — liczba, którą agent chce mieć jak największą
rt+1
nagroda zaraz za następny krok — jedyna, którą dostaje bez czekania, dlatego bez dyskonta
γ
dyskonto — wszystko, co przyjdzie później, tanieje o jeden czynnik γ; w ten sposób „później” zamienia się na „mniej”
Gt+1
zwrot od następnego kroku — ta sama wielkość o krok dalej; rekurencja, z której za chwilę wyrośnie równanie Bellmana
Wystarczy wyłączyć γ przed nawias ze wszystkich składników oprócz pierwszego: rt+1 + γ (rt+2 + γ rt+3 + …).
Twierdzenie — przy γ < 1 zwrot jest zawsze skończony

Gdy każda nagroda ma wartość bezwzględną co najwyżej Rmax, to |Gt| ≤ Rmax (1 + γ + γ² + …) = Rmax / (1 − γ), nawet gdyby epizod nigdy się nie skończył.

Dowód. Nierówność trójkąta daje |Gt| ≤ ∑k ≥ 0 γk |rt+k+1| ≤ Rmax ∑k ≥ 0 γk, a szereg geometryczny o ilorazie 0 ≤ γ < 1 ma sumę 1/(1 − γ). ∎

U nas Rmax = 10 i γ = 0,9, więc |G| ≤ 10 / 0,1 = 100. Bez kosztu kroku jest to jeszcze dużo mniej: niezerową nagrodę daje tylko wejście do celu albo w klif, i to najwyżej raz na epizod, więc |G| ≤ 10. Dlatego γ = 1 można użyć tylko tam, gdzie epizod na pewno się skończy.

Przykład — zwrot najkrótszej drogi do dużego celu

Na stabilnej podłodze najkrótsza droga do celu +10 prowadzi przez 6 kroków. Pierwszych pięć kroków daje nagrodę 0, szósty (wejście do celu) +10. Przy γ = 0,9:

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

Na stabilnej podłodze nic losowego się nie dzieje, więc to jest wprost wartość startu — i obliczenie iteracją wartości w sekcji o politykach daje rzeczywiście 5,90. Mały cel +1 nawet za 3 kroki dałby tylko 0,9² · 1 = 0,81.

3. Wartość i równania Bellmana

Definicja — funkcja wartości i równanie optymalności Bellmana

Wartość stanu przy polityce π to oczekiwany zwrot, gdy agent zaczyna w s i kieruje się π: Vπ(s) = Eπ[Gt | st = s]. Wartość akcji Qπ(s, a) to to samo, gdy pierwszą akcję wybieramy sami. Wartości optymalne spełniają równanie Bellmana (Richard Bellman, 1957):

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

a polityka optymalna to π*(s) = argmaxa Q*(s, a), gdzie Q*(s, a) to wyrażenie wewnątrz maksimum.

Mówiąc prościej

Wartość pola = ile najwięcej z niego wycisnę. A to da się policzyć rekurencyjnie: z każdego ruchu dostanę natychmiastową nagrodę plus (trochę przecenioną) wartość pola, na które mnie ruch zaprowadzi — uśrednioną po tym, gdzie może mnie rzucić kostka. Wybieram ruch, przy którym wychodzi najwięcej.

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

V*(s)
najlepszy oczekiwany zwrot z pola s — to, czego szukamy; stoi po obu stronach, więc równanie jest warunkiem, który wartości muszą spełnić wszystkie naraz
maxa
wybór agenta — akcję wybiera sam, więc bierze najlepszą; tu równanie „optymalności” różni się od równania dla ustalonej polityki π, gdzie zamiast maksimum stoi π(s)
∑s′ P(s′ | s, a) […]
średnia po tym, dokąd świat naprawdę rzuci agenta — o tym agent nie decyduje, dlatego wartość oczekiwana, a nie maksimum
R(s, a, s′)
natychmiastowa nagroda za to przejście (+1, +10, −10 albo koszt kroku)
γ
dyskonto — przyszłość jest o krok dalej, dlatego jeden czynnik γ (tak samo jak we wzorze Gt = rt+1 + γ Gt+1)
V*(s′)
najlepszy zwrot z miejsca lądowania — cała przyszłość zebrana w jedną liczbę, więc nie trzeba przechodzić wszystkich długich dróg
Wyrażenie za maksimum to Q*(s, a): wartość akcji a na polu s, gdy potem gra się już najlepiej.
Przykład — równanie Bellmana na starcie (poślizg 20 %, γ = 0,9)

Gotowe optymalne wartości sąsiadów startu: pole nad startem V* = 3,325, pole na prawo V* = 2,260, sam start V* = 2,854; klif jest końcowy (wartość 0, nagroda −10). Podstawiamy do prawej strony dla każdej akcji:

  • ↑: 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,

Największa jest ↑ z 2,854, i to jest dokładnie V*(start) — równanie zachodzi (różnica na ostatniej cyfrze to zaokrąglenie). Akcja „w górę” ma swoją cenę mimo 10% szansy, że agent ześlizgnie się w lewo, uderzy w krawędź i zostanie na starcie: dlatego V*(start) pojawia się też po prawej stronie. Akcja „w dół” prowadzi w 80 % przypadków w klif i wychodzi głęboko ujemna.

4. Iteracja wartości

Definicja — iteracja wartości

Zacznij od V0 = 0 i powtarzaj dla wszystkich stanów Vk+1(s) = maxa ∑s′ P(s′ | s, a) [R + γ Vk(s′)], dopóki wartości się zmieniają. Operator Bellmana jest dla γ < 1 kontrakcją: maxs |Vk+1 − V*| ≤ γ · maxs |Vk − V*|, więc błąd maleje co najmniej jak γk.

Mówiąc prościej

W pierwszej rundzie wartość znają tylko pola tuż obok celów. W drugiej informacja przesuwa się o pole dalej, w trzeciej o kolejne. Jak wiadomość, która rozchodzi się od sąsiada do sąsiada — po kilku rundach każde pole wie, dokąd opłaca się iść.

# iteracja wartości
V = 0 we wszystkich stanach
powtarzaj:
    dla każdego niekońcowego stanu s:
        dla każdej akcji a:
            Q[a] = ∑ po s′ ( P(s′ | s, a) · (R(s, a, s′) + γ · V(s′)) )
        V_nowe(s) = max(Q)
    zmiana = max po s |V_nowe(s) − V(s)|
    V = V_nowe
dopóki zmiana ≥ 10⁻⁶
π(s) = akcja o największym Q[a] (obliczonym z końcowego V)
Przykład — pierwsze trzy rundy (poślizg 20 %, γ = 0,9)

Śledzimy dwa pola w środkowym wierszu: A tuż na lewo od dużego celu +10 i B o pole dalej, tuż na prawo od małego celu +1. Nad B jest ściana, nad A wolne pole, pod oboma zwykła podłoga.

runda kVk(A)najlepsza akcja w AVk(B)najlepsza akcja w B
18,000→0,800←
28,000→5,832→
39,166→6,343→

Runda 1 (wszędzie V0 = 0): z A krok w prawo prowadzi z prawdopodobieństwem 0,8 do celu, czyli 0,8 · 10 = 8,000. Z B nic dalekiego jeszcze nie widać, najlepszy jest krok w lewo do małego celu: 0,8 · 1 = 0,800.

Runda 2: z B w prawo dochodzi się do A, które ma już wartość 8: 0,8 · 0,9 · 8 = 5,76, do tego 0,1 · 0,9 · 0,8 = 0,072 za poślizg w górę (ściana, zostaje w B z V1 = 0,8) i 0 za poślizg w dół — razem 5,832. Najlepsza akcja w B przeskoczyła z ← na →: informacja o dużym celu dotarła o pole dalej.

maxs |Vk+1(s) − Vk(s)| ≤ γk · maxs |V1(s) − V0(s)|

max |Vk+1 − Vk|
największa zmiana w rundzie k + 1 — to, co obliczenie śledzi i według czego się zatrzymuje; na wykresie niżej zielona (γ = 0,9) i niebieska (γ = 0,99) linia
γk
każda runda zmniejsza różnicę dwóch oszacowań co najmniej γ-krotnie (kontrakcja); po k rundach więc γk-krotnie — stąd powolna zbieżność dla γ bliskiego 1
max |V1 − V0|
wielkość pierwszej zmiany; przy V0 = 0 to największa oczekiwana nagroda za jeden krok, u nas najwyżej 10 — stąd przerywana granica 10 · γk na wykresie
Wynika z kontrakcji: |Vk+1 − Vk| = |BVk − BVk−1| ≤ γ |Vk − Vk−1|, gdzie B to jedna runda iteracji (operator Bellmana); i tak dalej aż do pierwszej rundy. Na przykład dla γ = 0,9 i k = 50 granica wynosi 10 · 0,9⁵⁰ ≈ 0,05.
10-610-410-2100 020406080 iteracja k (numer) max |V_k+1 − V_k| (nagroda, log.)
Iteracja wartości na śliskiej podłodze (p = 0,2): największa zmiana wartości w każdej iteracji γ = 0,9 (50 iteracji)γ = 0,99 (77 iteracji) 10 · γ^k

Przy γ = 0,9 wartości ustalają się (zmiana poniżej 10⁻⁶) po 50 iteracjach, przy γ = 0,99 po 77. Błąd maleje szybciej, niż gwarantuje granica γk — ona obowiązuje zawsze, ale dla konkretnego świata bywa pesymistyczna. Im bliżej jedynki jest γ, tym dalej w przyszłość musi się informacja rozprzestrzenić i tym dłużej trwa obliczenie.

5. Co zmienia dyskonto, poślizg i koszt kroku

Teraz to, co najciekawsze. Ten sam świat, tylko inne ustawienia — a polityka optymalna wygląda zupełnie inaczej.

→ 5,3 → 5,9 → 6,6 → 7,3 → 8,1 ↓ 9,0 ↑ 4,8 ↑ 5,9 → 9,0 ↓ 10,0 ↓ 5,3 +1 → 9,0 → 10,0 +10 → 5,9 S → 6,6 → 7,3 ↑ 8,1 ↑ 9,0 ↑ 10,0 −10−10−10−10−10−10 podłoga nie jest śliska → 4,3 → 5,0 → 5,7 → 6,5 → 7,5 ↓ 8,4 ↑ 3,8 ↑ 5,0 ↓ 8,5 ↓ 9,6 ↑ 3,3 +1 → 8,2 → 9,5 +10 ↑ 2,9 S ↑ 2,3 → 4,2 ↑ 7,0 ↑ 8,4 ↑ 9,6 −10−10−10−10−10−10 poślizg 20 %
Bez poślizgu i z poślizgiem (γ = 0,9): wartości pól, optymalne akcje i najbardziej prawdopodobna droga

Na stabilnej podłodze najkrótsza droga do dużego celu prowadzi tuż wzdłuż klifu: 6 kroków i wartość startu 5,90. Gdy podłoga jest śliska, krawędź klifu jest niebezpieczna — każdy krok tam oznacza 10 % szansy na upadek. Polityka optymalna dlatego obchodzi ściany górą: 10 kroków zamiast 6, ale w klif spada tylko 0,7 % epizodów. Gdybyśmy na śliskiej podłodze użyli ryzykownej polityki, agent spadłby w 30 % przypadków, a wartość startu spadłaby do 0,64 zamiast 2,85.

→ 0,1 → 0,2 ↓ 0,4 → 0,8 ↓ 1,8 ↓ 3,7 ↑ 0,0 ↓ 0,9 ↓ 4,0 ↓ 8,6 ↑ 0,0 +1 → 3,6 → 8,4 +10 ↑ 0,0 S ↑ 0,1 ↑ 0,9 ↑ 1,7 ↑ 3,9 ↑ 8,6 −10−10−10−10−10−10 γ = 0,5, poślizg 20 % → −1,3 → 0,0 → 1,4 → 3,1 → 4,9 ↓ 6,7 ↑ −2,4 ↓ 0,7 ↓ 7,0 ↓ 9,3 ↑ −3,3 +1 → 6,5 → 9,0 +10 → −2,9 S → −0,9 → 1,5 ↑ 4,4 ↑ 6,7 ↑ 9,2 −10−10−10−10−10−10 γ = 0,9, poślizg 20 %, krok −1
Niecierpliwy agent i agent, którego każdy krok kosztuje

Przy γ = 0,5 duży cel jest tak daleko, że się nie opłaca — +10 za 10 kroków ma dziś wagę tylko 10 · 0,5¹⁰ ≈ 0,01. Agent idzie ostrożnie górą do małego celu. Gdy natomiast każdy krok kosztuje −1, opłaca się ryzykować: agent idzie do dużego celu krawędzią klifu i w 27 % epizodów spada. Długa bezpieczna droga kosztowałaby go więcej, niż wynosi średnia strata przez upadek.

γpoślizgkrokdroga prowadziV(start)symulacjaupadekkroków
0,90 %0do +105,905,900,0 %6,0
0,920 %0do +102,852,840,7 %13,1
0,520 %0do +10,010,010,0 %9,5
0,920 %−1do +10−2,86−2,9026,9 %6,0
0,50 %−1do +1−1,25−1,250,0 %3,0

Kolumna „symulacja” to kontrola: średni zwrot z 10 000 epizodów według znalezionej polityki, z losowym poślizgiem. Średni zwrot różni się od obliczonej wartości startu najwyżej o kilka setnych — równanie Bellmana naprawdę liczy oczekiwany zwrot.

Nauka dla prawdziwych zastosowań: zachowania agenta nie wyznacza tylko „co jest celem”, ale też drobiazgi takie jak dyskonto i koszt kroku. Kto projektuje nagrody, projektuje zachowanie — także to, którego nie chciał.

6. Iteracja polityki

Definicja — iteracja polityki

Iteracja polityki (Ronald Howard, 1960) przeplata dwa kroki. Ewaluacja: dla ustalonej polityki π oblicz Vπ, rozwiązując układ Vπ(s) = ∑s′ P(s′ | s, π(s)) [R + γ Vπ(s′)]. Ulepszenie: w każdym stanie wybierz akcję o największej wartości według Vπ. Gdy polityka przestaje się zmieniać, jest optymalna.

Mówiąc prościej

Biorę jakąś ściągawkę, uczciwie liczę, jak dobrze z nią wypadnę z każdego pola, a potem poprawiam ściągawkę wszędzie tam, gdzie inny ruch wyszedłby lepiej. Powtarzam. Ściągawka poprawia się z każdą rundą i po kilku rundach już się nie zmienia.

# iteracja polityki
π = „wszędzie w górę”
powtarzaj:
    # ewaluacja: V^π przez rozwiązanie układu (u nas wielokrotnym podstawianiem)
    V = 0
    powtarzaj, dopóki V zmienia się o więcej niż 10⁻⁹:
        V(s) = ∑ po s′ ( P(s′ | s, π(s)) · (R + γ · V(s′)) )   dla każdego s
    # ulepszenie: w każdym stanie najlepsza akcja według V^π
    π_nowa(s) = argmax po a  ∑ po s′ ( P(s′ | s, a) · (R + γ · V(s′)) )
    zmienionych = liczba stanów, gdzie π_nowa(s) ≠ π(s)
    π = π_nowa
dopóki zmienionych > 0
Twierdzenie — o ulepszaniu polityki

Gdy nowa polityka π′ w każdym stanie wybiera akcję o największym Qπ(s, a), to Vπ′(s) ≥ Vπ(s) we wszystkich stanach. Gdy π′ nie różni się od π, Vπ spełnia równanie optymalności Bellmana, a więc π jest optymalna.

Szkic dowodu. Z wyboru π′ mamy Vπ(s) = Qπ(s, π(s)) ≤ Qπ(s, π′(s)) = E[r + γ Vπ(s′)]. Do Vπ(s′) podstawiamy tę samą nierówność, potem znowu… Po rozwinięciu zostaje oczekiwany zwrot polityki, która gra π′ we wszystkich krokach, czyli Vπ′(s). ∎

Polityk deterministycznych jest skończenie wiele — u nas 4 akcje na 19 niekońcowych polach, czyli 419 ≈ 2,7 · 1011. Żadna nie może się powtórzyć (każda runda poprawia wartość albo kończy), więc iteracja polityki zawsze się kończy. W rzeczywistości wystarcza zaskakująco mało rund: u nas 6.

Na śliskiej podłodze z γ = 0,9, z polityką „wszędzie w górę” na początku:

rundaV(start) politykikroków ewaluacjizmienionych akcji
10,03667
20,111377
30,161418
40,491513
52,85421
62,85770

Po 6 rundach polityka jest taka sama jak z iteracji wartości. Rund jest mało, ale każda zawiera całą ewaluację (u nas od kilkudziesięciu do kilkuset przejść przez świat). Która z obu metod jest szybsza, zależy od zadania; w praktyce się je łączy.

7. Gdy nie znamy reguł świata

Wszystko powyżej zakłada, że znamy P i R — potrafimy „zajrzeć do reguł”. To jest planowanie (programowanie dynamiczne). W prawdziwym uczeniu ze wzmocnieniem agent zostaje wrzucony do świata, którego reguł nie zna: musi próbować, zbierać doświadczenia i z nich szacować wartości. Równanie Bellmana pozostaje jednak sercem niemal wszystkich metod — tylko zamiast dokładnej średniej po P używa się próbki z jednego prawdziwego kroku. To jest Q-learning, temat następnej części.

Te same ramy opisują robota, który uczy się chodzić, zarządzanie zapasami w magazynie, system rekomendacyjny i model językowy uczony z ludzkich preferencji w części o RLHF — tam stanem jest dotychczasowy tekst, akcją kolejny token, a nagrodą ocena odpowiedzi.

8. Podsumowanie

  • MDP = stany, akcje, losowe przejścia, nagrody i dyskonto; następny stan zależy tylko od bieżącego stanu i akcji.
  • Wartość stanu to oczekiwany zdyskontowany zwrot; wartości optymalne spełniają równanie Bellmana.
  • Iteracja wartości powtarza równanie Bellmana; błąd maleje co najmniej jak γk (u nas 50 iteracji dla γ = 0,9).
  • Poślizg odsuwa drogę dalej od klifu (upadek 0,7 % zamiast 30 %), małe γ prowadzi do małego bliskiego celu, koszt kroku do ryzykowania.
  • Iteracja polityki przeplata ewaluację i ulepszenie; u nas 6 rund.
  • Bez znajomości reguł świata wartości trzeba wyuczyć z doświadczenia — to jest uczenie ze wzmocnieniem.

Chcesz to wypróbować na własnej skórze? Poproś agenta AI, żeby zaprogramował ten świat z klifem i pozwolił interaktywnie zmieniać γ, poślizg i koszt kroku — i obserwuj, kiedy polityka „przeskoczy” z jednej drogi na inną.

Masz inne zdanie? Napisz na support@coden-app.com.

Agent na twoim komputerze, sterowany z telefonu