Q-læring

Q-læring er en algoritme som brukes i kunstig intelligens og maskinlæring, mer spesifikt forsterkende læring, til å lære en agent handling-nytte-funksjonen, som gir informasjon om nytteverdien til en gitt handling i en gitt tilstand i et delvis eller helt ukjent miljø. Handlingen som gir den høyeste verdien til denne funksjonen representerer en regel som agenten skal følge neste gang den havner i samme tilstand. Denne regelen kalles en politikk (eng. policy). Når en slik handling-nytte verdi er lært, kan den optimale politikken konstrueres ved å velge handlingen som gir høyest nytteverdi i hver tilstand på vei mot målet. En av Q-lærings styrker er at teknikken er i stand til å sammenligne forventet nytte av de handlingene som er tilgjengelig, uten kunnskap om miljøet. I tillegg kan algoritmen håndtere problemer med stokastiske overganger og belønninger, uten å kreve noen tilpasninger.

Algoritmen

Introduksjon

Problemmodellen, kalt Markov Decision Process (MDP), består av en agent, tilstander $S$ og et sett med tilgjengelige handlinger $A$ ved hver tilstand. Agenten kan endre tilstand ved å utføre en handling $a\in A$ . Ved å utføre en handling i en spesifikk tilstand blir agenten belønnet med en verdi (et reelt eller naturlig tall). Målet for agenten er å maksimere dens totale belønning. Dette gjøres ved å lære hvilken handling som er optimal for hver tilstand. Denne læringsprosessen benytter et estimat for total belønning av alle fremtidige handlingsvalg fra gjeldende tilstand, ikke bare den umiddelbare belønningen agenten får ved valgt handling i tilstanden den er i.

Algoritmen har derfor en funksjon som kalkulerer kvaliteten (eng. Quality) av en kombinasjon av tilstand og handling:

Q:S\times A\to \mathbb {R}

Definisjon

Før læringsprosessen starter, returnerer Q en tilfeldig verdi. Deretter velger agenten en handling, og observerer en belønning og en ny tilstand som kan påvirkes av forrige tilstand og den valgte handlingen. Algoritmens kjerne er en enkel oppdatering av verdier den returnerer av gitte tilstander og handlinger. Den betrakter den gamle verdien og utfører en korrigering basert på den nye informasjonen:

Q_{t+1}(s_{t},a_{t})=\underbrace {Q_{t}(s_{t},a_{t})} _{\rm {gammel~verdi}}+\underbrace {\alpha _{t}(s_{t},a_{t})} _{\rm {learning~verdi}}\times \left[\overbrace {\underbrace {R_{t+1}} _{\rm {reward}}+\underbrace {\gamma } _{\rm {diskonteringsfaktor}}\underbrace {\max _{a}Q_{t}(s_{t+1},a_{t})} _{\rm {estimat~av~optimal~fremtidig~verdi}}} ^{\rm {learned~verdi}}-\underbrace {Q_{t}(s_{t},a_{t})} _{\rm {gammel~verdi}}\right]

der $R_{t+1}$ er den observerte belønningen etter å ha utført handling $a_{t}$ i tilstand $s_{t}$ , og der $\alpha _{t}(s,a)$ ( $0<\alpha \leq 1$ ) er læringssraten som gir informasjon om hvor stor grad den nye informasjonen skal overskrive den gamle informasjonen. Læringsraten kan være identisk for alle par i læringsprosessen. Diskonteringsfaktoren (eng. Discount factor) $\gamma$ ( $0\leq \gamma \leq 1$ ) gir informasjon om viktigheten av fremtidige belønninger.

En gjennomkjøring (kalt episode) av algoritmen ender når tilstanden $s_{t+1}$ er i måltilstanden.

Formell beskrivelse

   Gitt: Tilstandsdiagram med et mål tilstand (representert ved matrise R)
   Finn: Minste sti fra enhver opprinnelige tilstand til måltilstand (representert ved matrisen Q)
   Fremgangsmåte:
   1. Sett parameter γ og miljøbelønning matrise R
   2. Initialiser matrise Q som nullmatrise
   3. For hver episode:
   Velg en tilfeldig opprinnelig tilstand
   Gjør mens måltilstand ikke er nådd
   Velg ett blant alle mulige tiltak for den nåværende tilstanden
   Bruke denne mulige handlingen, vurder å gå til neste tilstand
   Få maks Q-verdi av denne neste stat basert på alle mulige tiltak
   Q (stat, action) = R (stat, action) + γ * Max [Q (neste tilstand, handlinger)]
   Sett neste tilstand som den nåværende tilstand

Algoritmens variabler

Læringsrate

Læringsraten bestemmer i hvor stor grad den nye tilegnede informasjonen skal erstatte den gamle informasjonen, og er $0<\alpha \leq 1$ . Dersom raten $\alpha =0$ , skal ingenting av den nye versjonen erstatte den gamle, og agenten har derfor ikke lært noe. Derimot, dersom $\alpha =1$ , skal all gammel informasjon erstattes av den nye, og agenten har da fått maksimalt læringsutbytte. Derfor er en læringsrate på 1 optimal i fullt deterministiske miljøer. I praksis er vanligvis en læringsrate av en konstant verdi benyttet, for eksempel $\alpha _{t}(s,a)=0.1$ for alle $t$ .^[1]

Diskonteringsfaktor

Diskonteringsfaktoren $\gamma$ bestemmer viktigheten av fremtidige belønninger. Dersom $\gamma =0$ vil agenten ha en oppførsel liknende en grådig algoritme, hvor kun de umiddelbare belønningene evalueres i bestemmelse av optimal handling i en tilstand. Derimot, dersom $\gamma =1$ , vil agenten heller ønske en maksimal langsiktig total belønning. Dersom dette er tilfellet, og agenten ikke befinner seg i et miljø med en terminaltilstand (sluttilstand), eller at agenten aldri når en slik tilstand, vil alle episoder av algoritmen være uendelig lange. Dette fordi agenten får høyere belønning jo flere tilstander den besøker.

Initielle forhold

Når algoritmen først starter, har ikke den lært noe. Derfor må Q-learning ha noen initielle verdier å benytte i de første kalkuleringene. Den forventer et initielt forhold før den første oppdateringen foretas. Et høyt initielt forhold fremmer utforskning: uansett hvilken handling som foretas, vil den nye kalkulerte verdien av Q-funksjonen erstatte gammel informasjon. Dermed, første gang en handling blir gjort, vil belønningen bli brukt til å sette den nye verdien til $Q$ .^[2]

Implementasjon

En enkel implementasjon av Q-learning algoritmen benytter tabeller for å lagre data. Problemet med denne tilnærmingen er raskt tap av levedyktighet med økning av kompleksiteten til systemet den kontrollerer. En løsning er å bruke et nevralt nettverk som en funksjonsapproksimator. Mer generelt kan Q-learning kombineres med funksjonsapproksimering. Dette gjør det mulig å anvende algoritmen til større problemer, som for eksempel NP-komplette problemer med eksponentiell kjøretid. Samtidig kan den forbedre hastigheten til problemer med polynomisk kjøretid, grunnet algoritmens evne til å generalisere tidligere erfaringer til tidligere usette tilstander.^[3]

Eksempel

Miljøet i figuren betraktes. Miljøet består av seks rom, hvor hvert av rommene har innganger til alle motstående naborom. Hver av disse inngangene har blitt tildelt samme initielle verdi. Denne verdien er satt til 0 fordi agenten som skal orientere seg i miljøet i starten av algoritmen ikke enda har lært noe om hvilke innganger som er mest gunstig å velge i et rom for å raskest nå terminaltilstanden G. Målet er å tildele hver av disse inngangene/utgangene en verdi som gir informasjon om hvor gunstig det er å velge akkurat den inngangen i et rom, i prosessen av å nå målet G ved færrest mulige besøk av rom. I dette eksempelet benytter vi diskonteringsfaktoren $\gamma =0.8$ .

Algoritmen tar i bruk verdier definert i en matrise $R$ , som for hver tilstand $S$ _y gir informasjon om den umiddelbare belønningen agenten får ved å velge handling $H$ og deretter havne i tilstand $S$ _x (i dette tilfellet ved å velge inngang til et rom). Rom som ikke er forbundet med en inngang/utgang tildeles den tomme verdien $-$ .

R={\begin{pmatrix}-&0&0&-&-&-\\0&-&-&0&-&100\\0&-&-&0&-&-\\-&0&0&-&0&-\\-&-&-&0&-&100\\-&-&-&-&-&100\\\end{pmatrix}}

Under læringsprosessen skal algoritmen oppdatere og korrigere Q-verdiene som er tildelt hver handling $H$ tilgjengelig i hver tilstand $S$ . Disse verdiene lagres i en matrisen $Q$ , som gir informasjon om nyttigheten av å velge en bestemt handling i en bestemt tilstand.

For hver tilstand, kalkulerer algoritmen Q-verdien av å velge handling $A$ i tilstand $S$ :

Q(S,A)=R(S,A)+{\gamma }*{\max \left[Q(nesteS,alleA)\right]}

Grunnet det faktum at Q-læring benytter sin egen definisjon i kalkuleringene, gjør algoritmen rekursiv. Dette betyr at for å kalkulere en Q-verdi av handlingen $H$ i en tilstand $S$ , må først de nødvendige Q-verdier tilhørende fremtidige tilstander kalkuleres. Algoritmen starter i en tilfeldig rom $S$ og kalkulerer Q-verdien av å velge alle tilgjengelige utgangene fra dette rommet etter tur. Deretter kalkuleres Q-verdien av valg av utganger fra disse rommene. Denne prosessen gjentas helt til agenten er i rommet representert av terminaltilstanden (målet) G.

For illustrative formål, er det nyttig å observere en metode for kalkulering av Q-verdiene til utganger tilhørende et rom raskest mulig. Da plasseres agenten først i tilstanden $S=G$ og Q-verdien til dette rommet kalkuleres. Deretter kalkuleres verdien til rommene $S=S2$ og $S=S5$ , så verdien tilhørende rommene som er naboene til $S2$ og $S5$ . Denne prosessen fortsetter helt til alle innganger har blitt tildelt en verdi som forblir uendret ved videre utforsking. Nytteverdien av å velge inngangen til rom $S$ _y fra et rom $S$ _x er definert i matrisen $Q$ :

Q={\begin{pmatrix}0&80&51.2&0&0&0\\64&0&0&64&0&100\\64&0&0&64&0&0\\0&80&51.2&0&80&0\\0&0&0&64&0&100\\0&0&0&0&0&100\\\end{pmatrix}}

Algoritmens læringsprosess er nå fullført, og algoritmen avslutter. Ved å benytte verdiene gitt i matrise $Q$ , kan agenten nå i et rom observere Q-verdiene tilhørende hver inngang gitt i matrisen $Q$ , og enkelt velge den utgangen med høyest verdi. Det er nettopp denne utgangen som bringer agenten raskest målet $S=G$ . Dersom to eller flere utganger har samme Q-verdi, bringer de agenten til målet like raskt, og agenten kan da tilfeldig velge én av disse.

Referanser

^ Reinforcement Learning: An Introduction Arkivert 4. september 2009 hos Wayback Machine.. Richard Sutton and Andrew Barto. MIT Press, 1998.
^ Artificial Intelligence: A Modern Approach (PDF) (Third utg.). Prentice Hall. 2010. s. 649. ISBN 978-0136042594. Arkivert fra originalen (PDF) 20. oktober 2014. Besøkt 17. oktober 2014. «Arkivert kopi» (PDF). Archived from the original on 20. oktober 2014. Besøkt 6. november 2014. CS1-vedlikehold: Uheldig URL (link)
^ The Role of First Impression in Operant Learning. Shteingart H, Neiman T, Loewenstein Y. J Exp Psychol Gen. 2013 May; 142(2):476-88. doi: 10.1037/a0029550. Epub 2012 Aug 27.

Eksterne lenker

Watkins, C.J.C.H. (1989). Learning from Delayed Rewards. PhD thesis, Cambridge University, Cambridge, England.
Strehl, Li, Wiewiora, Langford, Littman (2006). PAC model-free reinforcement learning
Reinforcement Learning: An Introduction by Richard Sutton and Andrew S. Barto, an online textbook. See "6.5 Q-Learning: Off-Policy TD Control".
Piqle: a Generic Java Platform for Reinforcement Learning
Reinforcement Learning Maze, a demonstration of guiding an ant through a maze using Q-learning.
Q-learning work by Gerald Tesauro
Q-learning work by Tesauro Citeseer Link
Q-learning algorithm implemented in processing.org language
Q-learning with lambda and a feed-forward-neural-net implementation in JavaScript for a martial arts game^{[død lenke]}

Autoritetsdata

[1] Reinforcement Learning: An Introduction Arkivert 4. september 2009 hos Wayback Machine.. Richard Sutton and Andrew Barto. MIT Press, 1998.

[2] Artificial Intelligence: A Modern Approach (PDF) (Third utg.). Prentice Hall. 2010. s. 649. ISBN 978-0136042594. Arkivert fra originalen (PDF) 20. oktober 2014. Besøkt 17. oktober 2014. «Arkivert kopi» (PDF). Archived from the original on 20. oktober 2014. Besøkt 6. november 2014. CS1-vedlikehold: Uheldig URL (link)

[3] The Role of First Impression in Operant Learning. Shteingart H, Neiman T, Loewenstein Y. J Exp Psychol Gen. 2013 May; 142(2):476-88. doi: 10.1037/a0029550. Epub 2012 Aug 27.

[1]

[2]

[3]