Q-learning

Q(s, a) är ett löfte: «om du står i tillstånd s, gör handling a, och sedan spelar så bra du kan — så här mycket får du totalt».

I början är alla löften noll, och alla är fel. Varje gång agenten provar något rättar den ett löfte:

$Q(s,a) \leftarrow Q(s,a) + \alpha\left[\underbrace{r + \gamma \max_{a'} Q(s',a')}_{\text{bättre gissning}} - Q(s,a)\right]$

Läs den som: jag trodde Q(s,a). Jag fick faktiskt r, och hamnade i s′ där det bästa jag kan göra är värt max Q(s′,·). Min nya gissning är alltså r + γ·max Q(s′,·). Flytta mig en bit (α) åt det hållet.

Uttrycket inom hakparentesen kallas TD-felet — skillnaden mellan vad jag trodde och vad jag just lärde mig. Är det noll överallt är agenten färdiglärd.

Det anmärkningsvärda: agenten behöver aldrig veta hur världen fungerar. Den behöver bara prova, se vad som händer, och rätta sina löften.

Q-learning är off-policy. Uppdateringen använder $\max_{a'} Q(s',a')$ — värdet av det bästa nästa draget, inte det drag agenten faktiskt kommer att göra. Agenten lär sig alltså om den giriga policyn medan den beter sig utforskande.

Det är skillnaden mot SARSA, som använder den handling som faktiskt togs:

	Uppdatering	Lär sig	Beter sig som om
Q-learning	$r + \gamma \max_{a'} Q(s',a')$	optimala policyn	utforskningen inte fanns
SARSA	$r + \gamma\, Q(s',a')$	den policy den faktiskt följer	utforskningen finns kvar

Det ger en konkret skillnad: går det en smal stig längs ett stup väljer Q-learning stigen (optimalt om man aldrig gör fel), medan SARSA går en omväg (säkrare när man ibland råkar kliva åt sidan). Ingen av dem är «rätt» — de svarar på olika frågor.

Konvergens. Tabellbaserad Q-learning konvergerar till $Q^*$ om varje (s, a)-par besöks oändligt ofta och lärhastigheten avtar lagom ($\sum \alpha_t = \infty$, $\sum \alpha_t^2 < \infty$). I praktiken används konstant $\alpha$ och krympande $\varepsilon$.

Hyperparametrarna och vad de gör:

	Betyder	Typiskt	Symtom när fel
$\alpha$	hur mycket varje erfarenhet flyttar Q	0,1	för högt: Q hoppar och konvergerar aldrig
$\gamma$	hur långt fram agenten ser	0,9–0,99	för lågt: närsynt, hittar inte avlägsna mål
$\varepsilon$	hur ofta den utforskar	1 → 0,05	för lågt tidigt: fastnar i första lösningen

Begränsningen är tabellen. Ett schackbräde har fler tillstånd än det finns atomer i solsystemet, och du kan inte lagra en rad per tillstånd. Det är precis den luckan Deep Q-Networks fyller.

import random
from collections import defaultdict

def q_learning(miljo, episoder=5000, alfa=0.1, gamma=0.95, frö=0):
    Q = defaultdict(float)                     # (tillstånd, handling) -> värde
    rng = random.Random(frö)
    for e in range(episoder):
        eps = max(0.05, 1.0 - e / (0.6 * episoder))
        s, klar = miljo.aterstall(), False
        while not klar:
            handlingar = miljo.handlingar(s)
            if rng.random() < eps:
                a = rng.choice(handlingar)                                   # utforska
            else:
                a = max(handlingar, key=lambda x: Q[(s, x)])                 # utnyttja
            s2, r, klar = miljo.steg(a)
            basta_nasta = 0.0 if klar else max(Q[(s2, x)] for x in miljo.handlingar(s2))
            Q[(s, a)] += alfa * (r + gamma * basta_nasta - Q[(s, a)])        # TD-uppdatering
            s = s2
    return Q

# Två fallgropar som kostar timmar om man missar dem:
#
# 1. basta_nasta MÅSTE vara 0 i terminalt tillstånd. Annars bootstrappar agenten
#    på ett värde som inte finns, och Q växer obegränsat.
#
# 2. Q[(s, a)] på en defaultdict SKAPAR posten. Använd Q.get((s, a), 0.0) när du
#    bara vill läsa, annars fylls tabellen med nollor för allt du någonsin tittat på.

def girig_policy(Q, miljo):
    return {s: max(miljo.handlingar(s), key=lambda a: Q.get((s, a), 0.0))
            for s in miljo.tillstand()}

De två kommentarerna är de vanligaste felen i handskriven Q-learning. Den första ger Q-värden som växer mot oändligheten och en agent som verkar lära sig men aldrig gör det; den andra ger tyst minnesläckage i långa körningar.