Markovbeslutsprocesser

En Markovbeslutsprocess är den formella ramen för sekventiellt beslutsfattande. Fem delar:

Symbol	Betyder
$S$	tillstånd — allt agenten behöver veta
$A$	handlingar
$P(s'\mid s,a)$	övergångssannolikheter
$R(s,a)$	belöning
$\gamma$	diskonteringsfaktor, 0 ≤ γ < 1

Markovegenskapen: framtiden beror bara på nuvarande tillstånd, inte på hela historien. Om det inte stämmer har du valt fel tillståndsrepresentation — inte fel algoritm.

Diskonteringen γ gör oändliga summor ändliga och uttrycker att belöning nu är värd mer än belöning sedan. γ = 0,9 ger en effektiv horisont på ungefär 10 steg; γ = 0,99 ungefär 100.

Avkastning: $G_t = \sum_{k=0}^{\infty}\gamma^k R_{t+k+1}$.

Värdefunktioner för en policy $\pi$: $V^\pi(s) = \mathbb E_\pi[G_t \mid S_t = s], \qquad Q^\pi(s,a) = \mathbb E_\pi[G_t\mid S_t=s, A_t=a]$

Bellmanekvationen — hela fältet vilar på den: $V^\pi(s) = \sum_a \pi(a|s)\sum_{s'} P(s'|s,a)\big[R(s,a) + \gamma V^\pi(s')\big]$

Värdet nu = omedelbar belöning + diskonterat värde av nästa tillstånd. Rekursionen är vad som gör det lösbart.

Optimalitet: $V^*(s) = \max_a \sum_{s'}P(s'|s,a)[R(s,a)+\gamma V^*(s')], \qquad \pi^*(s) = \arg\max_a Q^*(s,a)\ .$

Två klassiska lösningsmetoder när modellen är känd: värdeiteration (uppdatera V tills den konvergerar) och policyiteration (växla mellan att utvärdera och förbättra policyn). Båda konvergerar garanterat för ändliga MDP med $\gamma<1$.

När $P$ och $R$ är okända — vilket är normalfallet — används i stället inlärning ur erfarenhet: Q-learning, policy gradient, actor-critic.

import numpy as np

# 4×4-rutnät: mål i (3,3) ger +1, hål i (1,1) ger -1, varje steg -0,04
N, GAMMA = 4, 0.9
MAL, HAL = (3, 3), (1, 1)
HANDLINGAR = [(-1,0), (0,1), (1,0), (0,-1)]

def nasta(s, a):
    r, c = s[0] + a[0], s[1] + a[1]
    return s if not (0 <= r < N and 0 <= c < N) else (r, c)

def belaning(s):
    return 1.0 if s == MAL else (-1.0 if s == HAL else -0.04)

def vardeiteration(tol=1e-6):
    V = {(r, c): 0.0 for r in range(N) for c in range(N)}
    while True:
        delta = 0.0
        for s in V:
            if s in (MAL, HAL):
                continue
            nytt = max(belaning(nasta(s, a)) + GAMMA * V[nasta(s, a)] for a in HANDLINGAR)
            delta = max(delta, abs(nytt - V[s])); V[s] = nytt
        if delta < tol:
            return V

V = vardeiteration()
for r in range(N):
    print(" ".join(f"{V[(r,c)]:6.2f}" for c in range(N)))
#  0.28  0.42  0.58  0.76
#  0.42 -1.00  0.76  0.96
#  0.58  0.76  0.96  1.18
#  0.76  0.96  1.18  0.00

Värdena växer mot målet och sjunker mot hålet — policyn läses av genom att i varje ruta gå mot grannen med högst värde.