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.

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

Læringsrate

Læringsraten bestemmer i hvor stor grad den nye tilegnede informasjonen skal erstatte den gamle informasjonen, og er . Dersom raten , skal ingenting av den nye versjonen erstatte den gamle, og agenten har derfor ikke lært noe. Derimot, dersom , 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  for alle .

Diskonteringsfaktor

Diskonteringsfaktoren  bestemmer viktigheten av fremtidige belønninger. Dersom  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 , 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 .

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.