09 · Wzmocnienie · 5 min czytania · aktualizacja 11 października 2026

Równanie Bellmana i iteracja wartości — jak policzyć optymalną strategię, gdy znamy model?

Co to jest

Równanie Bellmana mówi, ile wart jest stan, gdy dalej działamy najlepiej: V(s) = max po akcjach a z [R(s, a) + γ · Σ P(s′ | s, a) · V(s′)]. Słownie: wartość stanu to najlepsza z akcji, ocenianych jako nagroda za ten krok plus zdyskontowana średnia wartość miejsc, do których akcja prowadzi. Równanie sformułował Richard Bellman w latach 50. XX wieku w ramach programowania dynamicznego.

Iteracja wartości to najprostszy sposób rozwiązania tego równania, gdy znamy model procesu decyzyjnego Markowa: prawdopodobieństwa przejść i nagrody. Zaczynamy od dowolnych wartości, np. zer, i w każdym przebiegu podstawiamy je do prawej strony równania. Wartości stopniowo się poprawiają. Gdy przestają się zmieniać, w każdym stanie wybieramy akcję, która maksymalizuje prawą stronę — to strategia optymalna.

Intuicja: informacja o nagrodzie rozchodzi się od celu wstecz, jak fala. Po pierwszym przebiegu „wiedzą” o celu tylko pola sąsiednie, po drugim — pola dwa kroki dalej. Gdy fala dotrze do startu, kolejne przebiegi już tylko dopracowują liczby.

Mechanizm — dlaczego tak działa

Jeden przebieg iteracji wartości to zastosowanie operatora Bellmana T do całej tablicy wartości. Ten operator jest zwężający (kontrakcją): dla dowolnych dwóch tablic V i U największa różnica po zastosowaniu T jest co najwyżej γ razy największa różnica przed. Powód: nagroda R jest w obu tablicach ta sama i się odejmuje, średnia po następnikach ani maksimum po akcjach nie powiększają różnic, a przyszłość wchodzi pomnożona przez γ.

Z twierdzenia Banacha o punkcie stałym wynikają trzy rzeczy. Równanie ma dokładnie jedno rozwiązanie V*. Iteracja zbiega do niego z każdego punktu startowego. Błąd maleje co najmniej geometrycznie, γ razy na przebieg. Przy γ = 0,9 każde 22 przebiegi zmniejszają błąd co najmniej dziesięciokrotnie, bo 0,9²² ≈ 0,098. Przy γ = 0,99 potrzeba na to około 230 przebiegów — stąd wolniejsza zbieżność, gdy agent patrzy daleko.

Kryterium stopu też wynika z kontrakcji. Jeśli największa zmiana w przebiegu jest mniejsza niż ε, to nowe wartości dzielą od V* najwyżej ε·γ/(1 − γ). Strategia zachłanna względem nich traci najwyżej dwa razy tyle, a w praktyce zwykle jest dokładnie optymalna na długo przed ustabilizowaniem się wartości.

Bliską kuzynką jest iteracja polityki: na zmianę liczy dokładną wartość bieżącej strategii (układ równań liniowych) i poprawia ją zachłannie. Potrzebuje mniej przebiegów, ale każdy jest droższy.

Gdzie to się psuje. Każdy przebieg kosztuje tyle, ile stanów razy akcji razy możliwych następników. Liczba stanów rośnie wykładniczo z liczbą zmiennych opisu (dziesięć zmiennych po 10 wartości to 10¹⁰ stanów) i tablica przestaje się mieścić — to „przekleństwo wymiarowości”, jak nazwał je sam Bellman. Wtedy wartości przybliża się funkcją, np. siecią neuronową. Gdy model nie jest znany, iterację wartości zastępuje uczenie z próbek: Q-learning stosuje tę samą regułę Bellmana do pojedynczych obserwowanych przejść zamiast do pełnej średniej po modelu.

Na przykładzie

Ta sama śliska plansza 4 × 4 co w haśle o MDP (cel +10 w prawym górnym rogu, pułapka −10 w drugim wierszu i drugiej kolumnie, krok −1, γ = 0,9). Tam prosta strategia „w górę, potem w prawo” była warta −3,13 i w 34,7% przypadków kończyła w pułapce.

Iteracja wartości startuje od zer. Po 5 przebiegach start wciąż ma wartość −4,10: wie tylko o kosztach kroków, bo cel jest 6 ruchów dalej. Największe zmiany maleją: 7,8 w pierwszym przebiegu, 6,2 w drugim, 4,9 w trzecim — każda najwyżej 0,9 raza poprzednia, jak obiecuje kontrakcja. Po 33 przebiegach spadają poniżej 10⁻⁸, ale strategia zachłanna jest już ostateczna po 7. przebiegu.

Wynik: V*(start) = 0,019. Strategia optymalna idzie najpierw w prawo, z dala od pułapki: dwa razy w prawo, dwa w górę, w prawo i w górę — też 6 ruchów bez poślizgu. W pułapce kończy w 3,4% przypadków zamiast 34,7%. Jest lepsza od prostej strategii w każdym polu planszy, a na starcie o 3,15.

Porównanie z Q-learningiem, który nie zna modelu i uczy się z prób: 5000 epizodów, α = 0,1, ε = 0,1, 20 powtórzeń. Wyuczona strategia jest warta średnio −0,15 (od −0,30 do 0,007) — daleko lepiej niż prosta, ale w żadnym z 20 przebiegów nie jest dokładnie optymalna. Najczęściej myli się na dwóch polach, gdzie „w górę” i „w prawo” różnią się o 0,016 i 0,028 — szum próbek zasłania taką różnicę. Stałe α nie spełnia warunków zbieżności Q-learningu (Watkins i Dayan, 1992): każda para stan–akcja próbowana nieskończenie wiele razy, a kroki malejące tak, że Σα = ∞ i Σα² < ∞. Z malejącym α = 1/n^0,6 i 20 000 epizodów strategia jest warta średnio 0,001 i dokładnie optymalna w 2 z 20 przebiegów. Iteracja wartości zna model, więc liczy średnie dokładnie.

W praktyce

• Iteracja wartości to kilka linijek NumPy: Q = R + gamma * P @ V dla każdej akcji, V = Q.max(axis=1), powtarzaj do małej zmiany. Strategia: Q.argmax(axis=1).
• Stosuj, gdy model jest znany i stanów jest najwyżej kilka milionów: planowanie zapasów, kolejki, gry planszowe z małą przestrzenią stanów, sprawdzanie wyników algorytmów uczących się.
• Wersja asynchroniczna (aktualizacja pól na miejscu, jedno po drugim) często potrzebuje mniej przebiegów niż synchroniczna.
• Kryterium stopu dobieraj z wzoru ε·γ/(1 − γ): przy γ = 0,99 gwarantowany błąd to 99ε, a przy γ = 0,9 tylko 9ε — ta sama tolerancja daje 11 razy słabszą gwarancję.
• Gdy model nie jest znany, użyj Q-learningu albo naucz się modelu z danych i zaplanuj na nim (podejście „model-based”).
• Typowy błąd: γ = 1 w zadaniu, w którym niektóre strategie nigdy nie kończą epizodu — ich wartości są nieskończone, a gwarancja kontrakcji znika.

Najczęstsze pytania

Czym różni się iteracja wartości od Q-learningu?

Iteracja wartości zna prawdopodobieństwa przejść i liczy dokładne średnie po wszystkich następnikach. Q-learning nie zna modelu: wykonuje akcje, obserwuje jedno przejście naraz i przesuwa oszacowanie w jego stronę. Obie metody opierają się na tym samym równaniu Bellmana.

Skąd wiadomo, że iteracja wartości się zatrzyma?

Operator Bellmana przy γ < 1 jest kontrakcją: każdy przebieg zmniejsza największą odległość od rozwiązania co najmniej γ razy, więc po skończonej liczbie przebiegów zmiana spada poniżej dowolnego progu.

Czy strategia optymalna jest jedna?

Wartości optymalne V* są jedne, ale strategii osiągających je może być kilka, gdy dwie akcje mają w jakimś stanie dokładnie taką samą wartość. Zawsze istnieje strategia optymalna deterministyczna, bez losowania akcji.

Źródła

Zobacz też