Redigerer Q-læring (avsnitt)

== Algoritmen ==

=== Introduksjon ===
   
Problemmodellen, kalt ''Markov Decision Process'' (MDP), består av en agent, tilstander <math>S</math> og et sett med tilgjengelige handlinger <math>A</math> ved hver tilstand. Agenten kan endre tilstand ved å utføre en handling <math>a \in A</math>. Ved å utføre en handling i en spesifikk tilstand blir agenten belønnet med en verdi (et [[Reelt tall|reelt]] eller [[Naturlig tall|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: 
 
:<math>Q: S \times A \to \mathbb{R}</math>

=== 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: 
 
:<math>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]</math>
 
der ''<math>R_{t+1}</math>'' er den observerte belønningen etter å ha utført handling <math>a_{t}</math> i tilstand <math>s_{t}</math>, og der <math>\alpha_t(s, a)</math> (<math>0 < \alpha \le 1</math>) 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'') <math>\gamma</math> (<math>0 \le \gamma \le 1</math>) gir informasjon om viktigheten av fremtidige belønninger. 
 
En gjennomkjøring (kalt ''episode'') av algoritmen ender når tilstanden <math>s_{t+1}</math> 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