Forsterkningslæring

En robotstøvsuger skal finne ladestasjonen i enden av en korridor. Ingen forteller den hva som er riktig i hver posisjon. Den kjører, ser hvor den havner, og får et tall tilbake: $-1$ for hvert steg, fordi strøm koster, og $+10$ når den når laderen. Det er hele oppsettet i forsterkningslæring.

Agent og miljø samhandler i en løkke. I hvert tidssteg $t$ observerer agenten en tilstand $S_t$ og velger en handling $A_t$. Miljøet svarer med en belønning $R_{t+1}$ og en ny tilstand $S_{t+1}$. En episode er én slik runde fra start til en terminaltilstand, her laderen. Til forskjell fra veiledet læring finnes ingen fasit per steg, bare belønninger, og de kan komme lenge etter handlingene som fortjente dem.

Formelt beskrives problemet som en Markov-beslutningsprosess (MDP) med tilstander, handlinger, overgangssannsynligheter, belønninger og en diskonteringsfaktor. Kjernen er Markov-egenskapen: neste tilstand og belønning avhenger bare av nåværende tilstand og handling, ikke av hvordan agenten kom dit (ƒMarkov-egenskapen).

Tilstanden må altså oppsummere alt som er relevant fra fortiden. I korridoren holder det med posisjonen. Men hvis en dør åpnes og lukkes, må dørens status inn i tilstanden. Ellers ser to forskjellige situasjoner like ut, og ingen tabell kan lære riktig handling for begge. Markov-egenskapen er det som lar oss regne verdier én tilstand om gangen.

Overgangene trenger ikke være deterministiske. Hjulene kan spinne på et glatt gulv, så «kjør høyre» av og til lar støvsugeren bli stående. Markov-egenskapen krever ikke at neste tilstand er sikker, bare at sannsynlighetene for den avhenger av nåværende tilstand og handling alene. Derfor snakker vi om forventet retur, og ett heldig forsøk sier lite om hvor god en handling er.

Belønningen er det eneste signalet agenten optimaliserer, og den er ofte sparsom. Får støvsugeren bare noe ved laderen, tar det mange episoder før den lærer hvilke tidlige trekk som hjalp.

En policy $\pi$ er agentens regel for å velge handling i hver tilstand. Den kan være deterministisk («kjør alltid mot høyre») eller stokastisk, altså en sannsynlighetsfordeling over handlingene. Policyen er agentens oppførsel. Den er ikke det samme som en verdifunksjon, som sier hvor bra det er å være i en tilstand. Vi kan utlede en policy fra verdier ved å velge handlingen med høyest verdi, men det er to ulike objekter.

Skill også mellom belønning og retur. Belønningen $R_{t+1}$ vurderer én overgang, mens returen summerer alt som kommer etterpå. Belønningen er dessuten det eneste agenten optimaliserer, så den må beskrive målet vi faktisk har. Gir vi poeng for å kjøre langt i stedet for å nå laderen, lærer agenten å kjøre i ring. Slike snarveier kommer vi tilbake til i kapittel 15.

Agenten skal ikke maksimere neste belønning, men summen av framtidige belønninger, returen (ƒdiskontert retur):

Diskonteringsfaktor $\gamma \in [0,1]$ bestemmer hvor sterkt framtidige belønninger teller. Med $\gamma =0$ teller bare neste belønning, og agenten blir kortsynt. Med $\gamma$ nær 1 teller belønninger langt fram nesten like mye som de nærmeste. Med $\gamma <1$ blir returen dessuten endelig selv om episoden aldri slutter.

Returen kan også skrives rekursivt, $G_t=R_{t+1}+\gamma G_{t+1}$ (ƒreturen rekursivt), og det er denne formen læringsalgoritmene bruker. De erstatter $G_{t+1}$ med et estimat av framtiden. Høy $\gamma$ betyr derfor at læringsmålet domineres av dette estimatet, mens den faktiske belønningen bare er en liten del. Det gir langsiktig oppførsel, men også tregere og mer ustabil læring så lenge estimatene er dårlige.

En verdifunksjon oppsummerer hva agenten kan forvente framover. Tilstandsverdien $V^{\pi }(s)$ er forventet retur fra $s$ når agenten følger $\pi$ (ƒtilstandsverdi). Handlingsverdien $Q^{\pi }(s,a)$ er forventet retur når agenten først tar handling $a$ i $s$ og deretter følger $\pi$. Q-verdier er praktiske fordi de sammenligner handlinger direkte: den grådige handlingen er den med høyest $Q(s,a)$.

Bellmans idé er å dele returen i to: belønningen nå pluss den diskonterte verdien av der du havner. For den optimale handlingsverdien gir det (ƒBellmans optimalitetsligning):

Verdien av et valg er altså umiddelbar belønning pluss verdien av å fortsette optimalt fra neste tilstand. Det er en konsistensbetingelse: kjenner vi verdiene i nabotilstandene, kan vi regne ut verdien her. Den forklarer også hvorfor en handling med lav umiddelbar belønning kan være best, nemlig når den fører til en tilstand med høy verdi. For en terminaltilstand finnes ingen fortsettelse, så verdien av det siste steget er bare belønningen.

De to verdifunksjonene henger sammen gjennom $V^{\ast }(s)={\max }_a{Q}^{\ast }(s,a)$: den beste tilstandsverdien er verdien av den beste handlingen. Kjenner vi $Q^{\ast }$, er den optimale policyen bare å velge $\arg {\max }_a{Q}^{\ast }(s,a)$ i hver tilstand. Derfor holder det å lære Q-verdier, policyen følger med på kjøpet.

Når overgangene er kjent, kan vi bruke Bellman-ligningen direkte og oppdatere alle verdiene om og om igjen til de slutter å endre seg (verdi-iterasjon, en form for dynamisk programmering). Verdien fra målet sprer seg da ett steg bakover per runde.

I praksis kjenner agenten ikke overgangssannsynlighetene. Q-learning lærer Q-verdiene direkte fra erfaring. Etter hver overgang $(s,a,r,s^{\prime })$ flyttes $Q(s,a)$ litt mot det Bellman sier den burde være (ƒQ-learning-oppdatering):

Uttrykket i hakeparentesen er TD-feil (ƒTD-feil): målet minus det vi trodde. Positiv TD-feil betyr at det gikk bedre enn ventet, og da øker $Q(s,a)$. Læringsraten $\alpha$ bestemmer hvor langt vi flytter. Med $\alpha =1$ erstattes den gamle verdien med målet, mens en liten $\alpha$ midler over mange erfaringer, noe som trengs når miljøet er tilfeldig.

Tre detaljer går ofte galt. Bare cellen $Q(s,a)$ for paret som faktisk ble besøkt, endres. Er $s^{\prime }$ terminal, er målet bare $r$, fordi det ikke finnes noen framtid. Og målet bruker $\max$ over neste handling, uansett hvilken handling agenten faktisk tar neste gang. Det siste gjør Q-learning off-policy: den lærer verdien av den grådige policyen selv om dataene samles inn med en utforskende policy. SARSA, som bruker handlingen agenten faktisk velger, er on-policy.

Legg merke til at målet selv inneholder et estimat, ${\max }_{a^{\prime }}Q(s^{\prime },a^{\prime })$. Q-learning lærer altså en gjetning fra en annen gjetning, såkalt bootstrapping. Det virker fordi den observerte belønningen $r$ hele tiden trekker estimatene mot virkeligheten. I en tabell konvergerer Q-learning mot $Q^{\ast }$ så lenge alle tilstand–handling-par besøkes mange nok ganger og $\alpha$ avtar passe sakte.

TD-feilen er parentesen i oppdateringen: målet minus gammel verdi.

Velger agenten alltid handlingen med høyest Q-verdi, kan den låse seg fast. Tidlig i læringen er Q-verdiene nesten tilfeldige, og en handling som tilfeldigvis ga litt belønning første gang, kan bli valgt for alltid mens en bedre aldri blir prøvd. Dette er dilemmaet utforskning–utnyttelse: utnytte det du vet, eller utforske for å vite mer.

ε-greedy er den enkleste løsningen (ƒepsilon-greedy policy). Med sannsynlighet $1-\epsilon$ velges den grådige handlingen, og med sannsynlighet $\epsilon$ en tilfeldig handling blant alle $|A|$, også den grådige. Derfor får den grådige handlingen totalt

og hver av de andre får $\frac{\epsilon }{|A|}$. Økes $\epsilon$, utforsker agenten mer: $\epsilon =0$ er ren grådighet, og $\epsilon =1$ er helt tilfeldig. Vanlig praksis er å starte høyt, for eksempel på $1,0$, og senke $\epsilon$ gradvis mot rundt $0,05$. Da utforsker agenten mye når den vet lite og utnytter mer etter hvert. Faller $\epsilon$ for raskt, blir deler av miljøet aldri besøkt.

Ved like Q-verdier bør valget mellom dem være tilfeldig. En argmax som alltid tar første indeks, gir agenten en skjult preferanse, og det merkes tydelig i starten når alle verdiene er 0. I håndregning og i kodeøvingen bruker vi likevel første indeks som fast konvensjon. Siden Q-learning er off-policy, lærer den riktige Q-verdier selv med mye utforskning, men oppførselen under trening blir dårligere jo høyere $\epsilon$ er.

Under trening er det fristende å følge TD-tapet, gjennomsnittet av kvadrerte TD-feil. Men tapet måler bare hvor godt Q-verdiene treffer sine egne mål, ikke hvor god policyen er. En agent som nesten aldri utforsker, kan forutsi returen av sin dårlige oppførsel svært presist og få lavt tap uten å bli bedre. Tapet kan også øke mens agenten blir bedre, fordi den oppdager nye tilstander der estimatene er dårlige. Framgang måles med returen per episode. Evaluer gjerne med en grådig policy ($\epsilon =0$) over mange episoder og flere frø, siden treningspolicyen med vilje tar tilfeldige valg.

Sparsomme belønninger gjør læringen treg. Får agenten bare belønning i måltilstanden, sprer verdien seg bakover ett steg per vellykket oppdatering, og i lange kjeder kan det ta mange episoder før starttilstanden «vet» noe. Utforskning er da avgjørende, ellers finner agenten kanskje aldri målet.

Til slutt: Q-tabellen har én celle per tilstand–handling-par. Det går fint med noen titalls tilstander, men ikke når tilstanden er et kamerabilde eller kontinuerlige målinger. Da erstattes tabellen med en funksjonsapproksimator, typisk et nevralt nettverk som tar tilstanden som input og gir Q-verdier ut. Det kalles Deep Q-Network (DQN), trenger nye triks for å bli stabilt og er tema i kapittel 15.