Dyp forsterkningslæring: DQN

Q-learning fra kapittel 14 lagrer én verdi per tilstand–handling-par. Det fungerer så lenge tilstandsrommet er lite og diskret, men det bryter sammen av to grunner. Den første er størrelse: hver ny tilstandsvariabel multipliserer antall celler, og med et kamerabilde som tilstand finnes det langt flere mulige bilder enn atomer i universet. Den andre er verre: en tabell generaliserer ikke. En celle som aldri blir besøkt, får aldri en oppdatering, og to tilstander som er nesten like, deler ingenting. Agenten må lære hver situasjon på nytt, selv om den har sett tusen lignende.

Løsningen er funksjonsapproksimasjon: i stedet for å slå opp $Q(s,a)$ i en tabell regner vi den ut med en funksjon $Q(s,a;\theta )$ med parametre $\theta$. Funksjonen ser på features i tilstanden, så tilstander som ligner, får lignende verdier, også tilstander den aldri har sett. Antall parametre er fast og mye mindre enn antall tilstander.

I praksis er funksjonen et Q-nettverk. Tilstanden går inn som en vektor eller et bilde, og utgangslaget har ett nevron per handling. Ett forward pass gir dermed alle Q-verdiene for tilstanden, og grådig valg er bare $\arg \max$ over utgangene. Utgangene er forventet avkastning, ikke sannsynligheter, så det er ingen softmax på slutten. Q-learning med et slikt nettverk og to stabiliseringsgrep som kommer senere i kapitlet, kalles DQN (Deep Q-Network).

Tilstanden må fortsatt være Markov. Ett stillbilde fra et spill viser ikke om ballen er på vei opp eller ned, så DQN-agenter for spill får gjerne de siste fire bildene stablet som input.

I en tabell er hver celle uavhengig: oppdaterer du $Q(s,a)$, står alle andre celler stille. I et Q-nettverk regnes alle Q-verdiene ut med de samme vektene $\theta$. Det kalles vektdeling, og det er både styrken og svakheten til DQN.

Ett gradientsteg på én overgang endrer $\theta$, og dermed endres Q-verdiene for alle tilstander som deler features med den vi trente på. Med tapet $\frac{1}{2}(y-Q_{\theta }(s,a){)}^2$ er steget

Styrken er generalisering. Lærer agenten at det lønner seg å bremse foran én våt kurve, flytter den samme oppdateringen verdiene for andre våte kurver også. Med langt færre parametre enn tilstander er det den eneste måten å lære noe om tilstander som aldri er besøkt.

Svakheten er at oppdateringen ikke spør om lov. Tilstander som ligner i input, men som burde ha helt forskjellig verdi, blir dratt med. Trener nettet lenge på en smal del av tilstandsrommet, kan det skrive over det det lærte et annet sted, såkalt katastrofal glemsel. Og fordi Q-learning lager målene sine fra egne estimater, flytter en vektendring også målene. Kombinasjonen av funksjonsapproksimasjon, mål fra egne estimater og off-policy-læring er kjent for å kunne gi ustabil og til og med divergerende trening. DQN fjerner ikke problemet, men demper det med grepene i de neste stegene.

I kapittel 14 flyttet Q-learning én tabellcelle en andel $\alpha$ mot målet $r+\gamma {\max }_{a^{\prime }}Q(s^{\prime },a^{\prime })$. Et nettverk har ingen celle å flytte. DQN gjør derfor hver overgang om til et lite regresjonsproblem: målet blir en fasit $y$, og nettet trenes med gradient descent til å treffe den. Målet er ƒDQN-målet, og tapet over en minibatch $B$ er ƒDQN-tapet:

Tre detaljer er verdt å feste. For det første tar målet maksimum over handlingene i neste tilstand, ikke gjennomsnittet og ikke handlingen agenten faktisk tok etterpå. Det er det som gjør metoden off-policy. For det andre er $d$ et ferdig-flagg: når episoden slutter i $s^{\prime }$, finnes det ingen fortsettelse, og målet er bare $r$. Glemmer du $(1-d)$, tror agenten at det finnes verdi etter at spillet er over. For det tredje behandles $y$ som en konstant fasit. Gradienten går bare gjennom $Q_{\theta }(s_i,a_i)$, og bare utgangen for handlingen som faktisk ble tatt, får feil fra denne overgangen. De andre utgangene endres bare indirekte, gjennom vektdelingen.

Vektene ${\theta }^{-}$ i målet tilhører target-nettverket, som kommer om to steg. Foreløpig holder det å vite at det er en kopi av Q-nettverket.

import numpy as np

gamma = 0.9  # @param 0..1 0.05
bruk_ferdig = 1  # @param 0..1
r = np.array([0.0, 1.0, -1.0, 0.5])            # minibatch med fire overganger
er_slutt = np.array([0, 1, 0, 0])               # 1 = episoden sluttet i s'
ferdig = er_slutt * bruk_ferdig                 # 0 = vi glemmer å gjenkjenne slutten
q_target_neste = np.array([[1.0, 2.0],         # target-nettets Q(s', ·)
                           [4.0, 3.0],
                           [0.5, -0.5],
                           [3.0, 3.5]])
q_online = np.array([1.5, 2.0, 0.0, 3.0])      # online-nettets Q(s, a)

y = r + gamma * (1 - ferdig) * q_target_neste.max(axis=1)
feil = y - q_online
for i in range(4):
    status = "terminal" if er_slutt[i] else "ikke terminal"
    print(f"overgang {i} ({status}): r = {r[i]:4.1f} -> mål y = {y[i]:5.2f}, TD-feil = {feil[i]:5.2f}")
print(f"MSE-tap: {np.mean(feil ** 2):.4f}")

En agent opplever verden som en film, ikke som en stokket kortstokk. Steg $t$ og steg $t+1$ ligner nesten alltid hverandre: samme rom, samme fart, samme situasjon. Trener nettet på overgangene i den rekkefølgen de kommer, blir gradientstegene korrelerte. Det er som å øve til eksamen ved å regne 500 like oppgaver om ett tema og så 500 om et annet: nettet tilpasser seg det siste det har sett og glemmer resten, og vektdelingen gjør det verre. I tillegg brukes hver erfaring bare én gang før den kastes, selv om erfaring kan være dyr å samle.

En replay buffer løser begge problemene. Hver overgang $(s,a,r,s^{\prime },d)$ legges i et minne med fast kapasitet $N$. Når minnet er fullt, skrives den eldste overgangen over, ofte som en ringbuffer med en skrivepeker som går rundt: $\text{pos}\leftarrow (\text{pos}+1)\mathrm{mod}N$. I hvert treningssteg trekkes en tilfeldig minibatch, for eksempel med random.sample(buffer, 32), som trekker uten tilbakelegging.

Det gir to gevinster. Minibatchen blander overganger fra ulike episoder og tidspunkter, så eksemplene blir tilnærmet uavhengige, slik veiledet læring forutsetter. Og hver overgang kan brukes i mange oppdateringer. At overgangene ble samlet inn av eldre versjoner av policyen, er ikke noe problem, fordi målet i Q-learning bruker $\max$ og ikke avhenger av hvem som valgte handlingen.

Uten noe ekstra ville DQN regnet målet med de samme vektene som trenes: $y=r+\gamma {\max }_{a^{\prime }}{Q}_{\theta }(s^{\prime },a^{\prime })$. Da er fasitsvaret selv en output fra nettet. Neste tilstand $s^{\prime }$ ligner som regel $s$, så når et gradientsteg dytter $Q_{\theta }(s,a)$ opp, dytter vektdelingen $Q_{\theta }(s^{\prime },\cdot )$ opp også, og målet følger etter. Det er som å rette sin egen prøve mot en fasit man skriver om hver gang man endrer et svar: en del av hver forbedring forsvinner fordi fasiten flyttet seg. Regneeksempelet lenger ned viser hvor stor del av steget som går tapt, og hva som skjer når målet flytter seg mer enn prediksjonen.

Et target-nettverk holder fasiten i ro. Vi lagrer en kopi ${\theta }^{-}$ av vektene og regner alle mål med den. Kopien trenes ikke, men oppdateres ved at vi kopierer vektene fra online-nettet med jevne mellomrom, ƒsynkronisering av target-nettet. Mellom to synkroniseringer er treningen vanlig regresjon mot faste fasitsvar. Etter en synkronisering får nettet et nytt og bedre regresjonsproblem.

Intervallet $C$ er en avveining. Er $C$ veldig lite, flytter målene seg nesten like mye som uten target-nett. Er $C$ veldig stort, bygger målene på gammel kunnskap, og læringen går tregt. Typiske verdier er fra noen hundre til noen titusen steg. En variant er myk oppdatering, der ${\theta }^{-}$ flyttes en liten andel $\tau$ mot $\theta$ i hvert steg.

Hold rollene fra hverandre. Online-nettet velger handlinger med $\epsilon$-greedy og er det som trenes. Target-nettet gjør bare én ting: det regner ut ${\max }_{a^{\prime }}{Q}_{{\theta }^{-}}(s^{\prime },a^{\prime })$ i målet.

Et nytt Q-nettverk har tilfeldige vekter, så Q-verdiene i starten er meningsløse. Velger agenten grådig fra første steg, låser den seg til tilfeldige vaner, og replay bufferet fylles med bare dem. Derfor starter $\epsilon$ i $\epsilon$-greedy gjerne på 1, altså rent tilfeldige handlinger, og senkes gradvis mot en liten minsteverdi som 0,05. Det kalles ε-annealing, og den enkleste varianten er lineær, ƒlineær ε-annealing. En liten $\epsilon$ beholdes hele tiden, fordi noen tilstander fortsatt er dårlig kjent. Når agenten evalueres, brukes en grådig eller nesten grådig policy.

Det andre som avgjør hva agenten lærer, er belønningen. Agenten optimerer tallet vi gir den, ikke intensjonen vår. Finner den en billigere vei til høy belønning enn den vi hadde i tankene, tar den den. Det kalles reward hacking eller specification gaming: agenten finner et smutthull i måten vi har formulert belønningen på. Jo sterkere optimeringen er, jo større er sjansen, og DQN finner strategier mennesker ikke har tenkt på. Noen eksempler:

• •En lagerrobot får belønning per strekkodeskanning og lærer å skanne den samme pakken om og om igjen.
• •En agent i et bilspill får poeng for hver sjekkpost den passerer, og kjører i ring rundt én sjekkpost i stedet for å fullføre løpet.
• •En kundeservice-bot belønnes for korte samtaler og lærer å avslutte chatten før problemet er løst.
• •En simulert robot belønnes for fart framover og finner en feil i fysikkmotoren som lar den skli av gårde på ryggen.

Tiltakene er å belønne det faktiske målet i stedet for en proxy, legge inn straff og begrensninger for uønsket atferd, teste i varierte miljøer og se på hva agenten faktisk gjør. En belønningskurve som stiger, beviser ingenting: den ser akkurat slik ut når agenten hacker belønningen.

T = 120   # tidssteg i ett skift
r_gjentatt = 1.0  # @param -0.5..1 0.05

def belonning(ny_pakke):
    return 1.0 if ny_pakke else r_gjentatt   # dagens design: +1 for hver skanning

def skift(strategi):
    t, sum_r, sett, pakke = 0, 0.0, set(), 0
    while t < T:
        if strategi == "hent ny pakke":
            pakke += 1      # hente og skanne en ny pakke tar 4 steg
            t += 4
        else:
            t += 1          # skanne samme pakke igjen tar 1 steg
        sum_r += belonning(pakke not in sett)
        sett.add(pakke)
    return sum_r, len(sett)

resultater = {s: skift(s) for s in ["hent ny pakke", "skann samme igjen"]}
for s, (sum_r, ulike) in resultater.items():
    print(f"{s:18s} belønning = {sum_r:6.1f}   ulike pakker = {ulike}")
print("en belønningsmaksimerende agent velger:", max(resultater, key=lambda s: resultater[s][0]))