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