Markovianske beslutningsprosess

I beslutningsteori og sannsynlighetsteori er en Markov-beslutningsprosess (på engelsk Markov beslutningsprosess , CDM) en modell som er stokastisk der en agent tar beslutninger og hvor resultatene av hans handlinger er tilfeldige. MDP brukes til å studere optimaliseringsproblemer ved hjelp av dynamiske programmeringsalgoritmer eller forsterkningslæring . MDP har vært kjent siden 1950. Et stort bidrag kommer fra arbeidet til Ronald A. Howard med sin bok fra 1960, Dynamic Programming and Markov Processes . De brukes i mange fagområder, inkludert robotikk , automatisering , økonomi og produksjon .

En Markovian beslutningsprosess er en diskret stokastisk kontrollprosess . Ved hvert trinn er prosessen i en viss tilstand, og agenten velger en handling . Sannsynligheten for at prosessen ankommer staten bestemmes av den valgte handlingen. Mer presist er det beskrevet av tilstandsovergangsfunksjonen . Så staten avhenger av den nåværende tilstanden og handlingen valgt av beslutningstakeren. For en og en er den neste staten imidlertid uavhengig av tidligere handlinger og stater. Vi sier da at prosessen tilfredsstiller Markov-eiendommen . s{\ displaystyle s}på{\ displaystyle a}s′{\ displaystyle s '}T(s,på,s′){\ displaystyle T (s, a, s ')}s′{\ displaystyle s '}s{\ displaystyle s}på{\ displaystyle a}s{\ displaystyle s}på{\ displaystyle a}

Når prosessen går fra stat til stat med handling , tjener agenten en belønning . s{\ displaystyle s}s′{\ displaystyle s '}på{\ displaystyle a}R(s,på,s′){\ displaystyle R (s, a, s ')}

MDP er en utvidelse av Markov-kjeder . Forskjellen er summen av handlingene valgt av agenten og belønningen oppnådd av agenten. Hvis det bare er en handling å gjøre i hver stat og belønningene er like, er den Markovianske beslutningsprosessen en Markov-kjede.

Intuitiv definisjon

For å forstå hva en MDP er, anta at vi har et system som utvikler seg over tid som en sannsynlig automat . For hvert øyeblikk er systemet i en gitt tilstand, og det er en viss sannsynlighet for at systemet vil utvikle seg mot en slik eller annen tilstand i det følgende øyeblikk ved å gjøre en overgang.

Anta nå at vi trenger å kontrollere dette black box- systemet på en best mulig måte. Målet er å bringe det til en tilstand som anses som gunstig , ved å unngå å få den til å gå gjennom skadelige stater . For dette har vi et sett med mulige handlinger på systemet. For å komplisere ting vil vi anta at effekten av disse handlingene på systemet er sannsynlig: handlingen som utføres kan ha ønsket effekt eller annen effekt. Effektiviteten av kontrollen måles i forhold til gevinsten eller straffen som mottas gjennom hele eksperimentet.

Dermed kan resonnement basert på MDP reduseres til følgende diskurs: å være i et slikt tilfelle og velge en slik og en slik handling, det er så stor sjanse for at jeg befinner meg i en slik ny sak med en slik gevinst.

For å illustrere MDP tar vi ofte eksempler fra mobil robotikk (med posisjoner for stater, kommandoer som handlinger, bevegelser som overganger og fullføring / svikt i oppgaver som gevinster / straffer).

Markov-hypotese

I MDP antas utviklingen av systemet å tilsvare en Markovian-prosess. Med andre ord følger systemet en rekke forskjellige stater over tid, og dette som en funksjon av sannsynligheter for overganger. Den Markov hypotese består i å si at sannsynligheten for overganger avhenger bare av de n tidligere tilstander. Generelt tar vi rekkefølgen n = 1 , som lar oss bare vurdere den nåværende tilstanden og den følgende tilstanden.

Formell definisjon

En MDP er en firdobling som definerer: {S,PÅ,T,R}{\ displaystyle \ {S, A, T, R \} \,}

• et sett med stater , som kan være endelige, tellbare eller kontinuerlige ; dette settet definerer miljøet som agenten oppfatter (i tilfelle en robot kan vi se dette når settet produserer verdier fra de forskjellige sensorene);S{\ displaystyle S}
• et sett med handlinger , som kan være endelige, tellbare eller kontinuerlige, og hvor agenten velger samspillet den utfører med miljøet (i tilfelle av en robot kan vi se dette når settet produserer parametere for dets forskjellige ordrer);PÅ{\ displaystyle A}
• en overgangsfunksjon ; denne funksjonen definerer effekten av agentens handlinger på miljøet: representerer sannsynligheten for å være i staten ved å utføre handlingen , vel vitende om at vi var i staten før .T:S×PÅ×S→[0;1]{\ displaystyle T: S \ times A \ times S \ to [0; 1]}T(s,på,s′){\ displaystyle T (s, a, s ')}s′{\ displaystyle s '}på{\ displaystyle a}s{\ displaystyle s}

T{\ displaystyle T}således definert representerer det mest generelle tilfellet; i et deterministisk miljø, vil vi heller ha . T:S×PÅ→S{\ displaystyle T: S \ ganger A \ til S}

• en belønningsfunksjon ; den definerer belønningen (positiv eller negativ) som mottas av agenten: er sannsynligheten for å oppnå belønning for å ha gått fra staten til å ha utført aksjonen . Også her er denne definisjonen veldig generell, ofte vil vi være fornøyd med for eksempel følgende tilfeller: R:S×PÅ×S×R→[0;1]{\ displaystyle R: S \ times A \ times S \ times \ mathbb {R} \ to [0; 1]}R(s,på,s′,v){\ displaystyle R (s, a, s ', v)}v{\ displaystyle v}s{\ displaystyle s}s′{\ displaystyle s '}på{\ displaystyle a}
  • R:S×PÅ×S→R{\ displaystyle R: S \ times A \ times S \ to \ mathbb {R}} (deterministisk belønning, dette er valget vi vil vedta i det følgende);
  • R:S×PÅ→R{\ displaystyle R: S \ ganger A \ til \ mathbb {R}} (deterministisk belønning knyttet til handlingen som ignorerer resultatet);
  • R:S→R{\ displaystyle R: S \ to \ mathbb {R}} (deterministisk belønning knyttet til en gitt tilstand).

I litteraturen blir belønningsfunksjonen noen ganger erstattet av en kostnadsfunksjon .

NB: vi ser bare her på modellene der tiden blir diskretisert, det vil si at "banen" til agenten i miljøet er beskrevet av en rekke tilstander ( ), og ikke av en funksjon med . Likeledes vil sekvensen av handlinger tatt av agenten bli notert . Man kan konsultere for en beskrivelse av kontinuerlig MDP. st{\ displaystyle s_ {t}}t∈IKKE{\ displaystyle t \ in \ mathbb {N}} s(t){\ displaystyle s (t)}t∈R{\ displaystyle t \ in \ mathbb {R}}påt{\ displaystyle a_ {t}}

Eksempel på CDM

Eksemplet som er gitt her representerer en Markovian beslutningsprosess med tre forskjellige stater representert i grønt. Fra hver av statene kan vi utføre en handling av settet . De røde nodene representerer derfor en mulig beslutning (valget av en handling i en gitt tilstand). Tallene som vises på pilene er sannsynligheten for å gjøre overgangen fra avgjørelsesnoden. Endelig kan overganger generere belønninger (tegnet her i gult). {s0,s1,s2}{\ displaystyle \ {s_ {0}, s_ {1}, s_ {2} \}}{på0,på1}{\ displaystyle \ {a_ {0}, a_ {1} \}}

• Overgangsmatrisen assosiert med handlingen er som følger:på0{\ displaystyle a_ {0}}

(0,5000,500,700,100,200,4000,60){\ displaystyle {\ begin {pmatrix} 0,50 & 0 & 0,50 \\ 0,70 & 0,10 & 0,20 \\ 0,40 & 0 & 0,60 \ slutt {pmatrix}}}

• Overgangsmatrisen assosiert med handlingen er som følger:på1{\ displaystyle a_ {1}}

(001.000,950,050,300,300,40){\ displaystyle {\ begin {pmatrix} 0 & 0 & 1.0 \\ 0 & 0.95 & 0.05 \\ 0.30 & 0.30 & 0.40 \ end {pmatrix}}}

Når det gjelder belønningene,

• vi oppfatter en belønning på +5 når vi går fra stat til stat ved å utføre handlingens1{\ displaystyle s_ {1}}s0{\ displaystyle s_ {0}}på0{\ displaystyle a_ {0}}
• vi oppfatter en belønning på -1 (også kalt straff) når vi går fra stat til stat ved å utføre handlingens2{\ displaystyle s_ {2}}s0{\ displaystyle s_ {0}}på1{\ displaystyle a_ {1}}

Merknader

MDP-modellen som presenteres her antas å være stabil over tid, dvs. at komponentene i firdyret antas å være uforanderlige. Det er derfor ikke aktuelt som for et system som utvikler seg, for eksempel å modellere et system som lærer mot en annen agent.

Politikk, verdifunksjoner og Bellmans ligninger

Politikk

En policy beskriver valg av handlinger som agenten skal ta i hver stat. Formelt er det derfor en funksjon når det gjelder en deterministisk politikk eller i det stokastiske tilfellet . Noen ganger betegner vi sannsynligheten for å spille a i tilstand s, dvs. sannsynligheten for å spille a på tidspunktet t å vite at tilstanden på tidspunktet t er s. Denne verdien er uavhengig av t: vi snakker om en stasjonær politikk. Gitt en MDP og en policy, får vi en belønnet Markov-kjede. Vi plasserer oss i det deterministiske tilfellet. π:S→PÅ{\ displaystyle \ pi: S \ til A}π:S×PÅ→[0;1]{\ displaystyle \ pi: S \ ganger A \ til [0; 1]}π(på|s){\ displaystyle \ pi (a | s)}P[PÅt=på∣St=s]{\ displaystyle \ mathbb {P} [A_ {t} = a \ mid S_ {t} = s]}

Kriterium

Agenten velger en policy ved å bruke belønningsfunksjonen . Legg merke til den faktiske belønningen som oppnås etter at agenten har utført handlingen i henhold til retningslinjene . Her er flere kriterier av interesse som agenten kan søke å maksimere: R{\ displaystyle R}rt=R(st,π(st),st+1){\ displaystyle r_ {t} = R (s_ {t}, \ pi (s_ {t}), s_ {t + 1})}π(st){\ displaystyle \ pi (s_ {t})}π{\ displaystyle \ pi}

• E(∑t=0hrt){\ displaystyle E \ left (\ sum _ {t = 0} ^ {h} r_ {t} \ right)}: forventning om summen av belønningene ved en fast endelig horisont  ;h{\ displaystyle h}
• lim infh→+∞E(1h∑t=0hrt){\ displaystyle \ liminf _ {h \ to + \ infty} E \ left ({1 \ over h} \ sum _ {t = 0} ^ {h} r_ {t} \ right)}eller : langsiktig gjennomsnittlig belønning;lim suph→+∞E(1h∑t=0hrt){\ displaystyle \ limsup _ {h \ to + \ infty} E \ left ({1 \ over h} \ sum _ {t = 0} ^ {h} r_ {t} \ right)}
• E(∑t=0∞γtrt){\ displaystyle E \ left (\ sum _ {t = 0} ^ {\ infty} \ gamma ^ {t} r_ {t} \ right)}: forventet (eller amortisert) belønning over en uendelig horisont hvor .0≤γ<1{\ displaystyle 0 \ leq \ gamma <1}

Det siste kriteriet er vanlig, og det er det vi vedtar i det følgende. Verdien av definerer viktigheten vi gir fremtiden. Når vi står overfor en "pessimistisk" agent som bare søker å optimalisere sin umiddelbare gevinst. Tvert imot hvis agenten er "optimistisk" siden han tar mer og mer seriøst hensyn til den fjerne fremtiden (ja , agenten tar hensyn til den fjerne fremtiden like mye som den umiddelbare gevinsten). γ{\ displaystyle \ gamma}γ=0{\ displaystyle \ gamma = 0}γ→1{\ displaystyle \ gamma \ til 1}γ=1{\ displaystyle \ gamma = 1}

Verdifunksjoner

Når en policy og et kriterium er bestemt, kan to sentrale funksjoner defineres:

• Vπ:S→R{\ displaystyle V ^ {\ pi}: S \ til \ mathbb {R}}: det er statens verdifunksjon; representerer gevinsten (i henhold til det kriteriet som er vedtatt) oppnådd av agenten hvis den starter i staten og deretter bruker ad infinitum policy .Vπ(s){\ displaystyle V ^ {\ pi} (s)}s{\ displaystyle s}π{\ displaystyle \ pi}
• Qπ:S×PÅ→R{\ displaystyle Q ^ {\ pi}: S \ ganger A \ til \ mathbb {R}}: det er verdifunksjonen til handlingstilstandene; representerer gevinsten påløpt av agenten hvis den starter i staten og begynner med å utføre handlingen før den deretter bruker ad infinitum policy .Qπ(s,på){\ displaystyle Q ^ {\ pi} (s, a)}s{\ displaystyle s}på{\ displaystyle a}π{\ displaystyle \ pi}

Bellmans ligning

De to funksjonene er nært knyttet sammen. Vi har alltid, og i tilfelle av dempet gevinst ved uendelig horisont, kan vi også skrive at: Vπ(s)=Qπ(s,π(s)){\ displaystyle V ^ {\ pi} (s) = Q ^ {\ pi} (s, \ pi (s))}

Qπ(s,på)=∑s′∈S[R(s,på,s′)+γVπ(s′)]T(s,på,s′).{\ displaystyle Q ^ {\ pi} (s, a) = \ sum _ {s '\ in S} [R (s, a, s') + \ gamma V ^ {\ pi} (s ')] T (s, a, s ').}

Dette siste forholdet viser at funksjonen tilfredsstiller et forhold av gjentakelse kalt Bellman- ligningen : Vπ{\ displaystyle V ^ {\ pi}}

Vπ(s)=∑s′∈S[R(s,π(s),s′)+γVπ(s′)]T(s,π(s),s′).{\ displaystyle V ^ {\ pi} (s) = \ sum _ {s '\ in S} [R (s, \ pi (s), s') + \ gamma V ^ {\ pi} (s ') ] T (s, \ pi (s), s ').}

Bellman-ligningen er skrevet som følgende lineære ligning i Markov-kjeden med "flatede" belønninger fra den Markovianske beslutningsprosessen og politikken  : π{\ displaystyle \ pi}

Vπ=Rπ+γPπVπ{\ displaystyle V ^ {\ pi} = R ^ {\ pi} + \ gamma P ^ {\ pi} V ^ {\ pi}}

hvor er vektoren som inneholder verdiene for hver tilstand, er belønningsmatrisen, er sannsynlighetsmatrisen. Vπ{\ displaystyle V ^ {\ pi}}Rπ{\ displaystyle R ^ {\ pi}}Pπ{\ displaystyle P ^ {\ pi}}

Mulige problemer

• Planlegging: gitt en CDM , finn ut hva som er en policy som maksimerer forventningen om belønningen.{S,PÅ,T,R}{\ displaystyle \ {S, A, T, R \}}π{\ displaystyle \ pi}
• Forbedre en kjent policy: gitt en policy , finn en bedre policy.π0{\ displaystyle \ pi _ {0}}

Dette problemet er spesielt kjernen i optimale algoritmer for policy-søk.

• Lære en policy uten å kjenne modellen:
  • fra utførelsesspor: dette er problemet med offline forsterkningslæring .
  • under eksperimenter på modellen blir dette referert til som online forsterkningslæring .

Algoritmer

En politikk som er løst, kan Bellman-ligningen løses på minst to måter, slik at det blir mulig å bestemme verdiene til og følgelig også verdiene til . Vπ{\ displaystyle V ^ {\ pi}}Qπ{\ displaystyle Q ^ {\ pi}}

• Vi kan allerede legge merke til at i tilfelle hvor antallet stater er endelig, skjuler Bellman-ligningen faktisk et lineært ligningssystem med ukjente.ikke{\ displaystyle n}ikke{\ displaystyle n}ikke{\ displaystyle n}

Man kan dermed løse det, en gang oversatt til en matriksligning, ved hjelp av en teknikk som den Gaussiske svingeren .

• det kan vi også legge merke til ved å stille

K(f)(s)=∑s′∈S[R(s,π(s),s′)+γf(s′)]T(s,π(s),s′),{\ displaystyle K (f) (s) = \ sum _ {s '\ in S} [R (s, \ pi (s), s') + \ gamma f (s ')] T (s, \ pi (s), s '),}

vi definerer en operatør , kalt Bellman-operatøren, som er et fast punkt. Vi kan vise at det er en sammentrekning , som garanterer på den ene siden eksistensen av et unikt fast punkt , og på den andre siden at gjentagelsessekvensen konvergerer raskt mot dette faste punktet. K{\ displaystyle K}Vπ{\ displaystyle V ^ {\ pi}}K{\ displaystyle K}Vikke+1=K(Vikke){\ displaystyle V_ {n + 1} = K (V_ {n})}

Bellman Optimality Equations

Målet med agenten er å finne den optimale politikken som gjør at han kan maksimere sin gevinst, det vil si den som verifiserer for enhver stat , uansett hvilken annen politikk . Vi kan vise at den optimale verdifunksjonen tilfredsstiller Bellmans optimalitetsligning: π∗{\ displaystyle \ pi ^ {*}}s∈S{\ displaystyle s \ in S}Vπ∗(s)≥Vπ(s){\ displaystyle V ^ {\ pi ^ {*}} (s) \ geq V ^ {\ pi} (s)}π{\ displaystyle \ pi}V∗{\ displaystyle V ^ {*}}

V∗(s)=makspå∈PÅ∑s′∈S[R(s,π(s),s′)+γV∗(s′)]T(s,på,s′).{\ displaystyle V ^ {*} (s) = \ max _ {a \ i A} \ sum _ {s '\ i S} [R (s, \ pi (s), s') + \ gamma V ^ {*} (s ')] T (s, a, s').}

Tilsvarende tilfredsstiller funksjonen også en optimalitetsligning: Q{\ displaystyle Q}

Q∗(s,på)=∑s′∈S[R(s,på,s′)+γmakspå′∈PÅQ∗(s′,på′)]T(s,på,s′).{\ displaystyle Q ^ {*} (s, a) = \ sum _ {s '\ in S} [R (s, a, s') + \ gamma \ max _ {a '\ in A} Q ^ { *} (s ', a')] T (s, a, s ').}

Løse Bellmans optimalitetsligninger

Bellmans optimalitetsligninger er ikke lineære , så vi må forlate ideen om å løse dem algebraisk. På den annen side definerte Bellman-operatøren av K∗{\ displaystyle K ^ {*}}

K∗(f)(s)=makspå∈PÅ∑s′∈S[R(s,på,s′)+γf(s′)]T(s,på,s′),{\ displaystyle K ^ {*} (f) (s) = \ max _ {a \ in A} \ sum _ {s '\ in S} [R (s, a, s') + \ gamma f (s ')] T (s, a, s'),}

definerer igjen en sammentrekning som er et fast punkt. Den optimale verdifunksjonen kan derfor nærme seg igjen ved en iterativ prosess med eksponentiell konvergens. V∗{\ displaystyle V ^ {*}}

Bestem den optimale politikken: Iterasjon over verdialgoritme (VI)

Den iterative metoden som vi nettopp har sett for Bellman-optimalitetsligningene, gir en første algoritme, kalt iterasjon på verdien (VI: Value-Iteration) som gjør det mulig å bestemme . Det er tilstrekkelig å bestemme med en gitt presisjon, og vi kan utlede den optimale politikken ved å: π∗{\ displaystyle \ pi ^ {*}}V∗{\ displaystyle V ^ {*}}

π(s)=arg⁡makspå∈PÅQ∗(s,på)=arg⁡makspå∈PÅ∑s′∈S[R(s,på,s′)+γV∗(s′)]T(s,på,s′).{\ displaystyle \ pi (s) = \ arg \ max _ {a \ in A} Q ^ {*} (s, a) = \ arg \ max _ {a \ in A} \ sum _ {s '\ in S} [R (s, a, s ') + \ gamma V ^ {*} (s')] T (s, a, s ').}

Et problem i denne algoritmen er å bestemme nøyaktigheten som skal beregnes for å være sikker på å faktisk utlede den optimale politikken. V∗{\ displaystyle V ^ {*}}

Bestem optimal policy: Policy Iteration Algorithm (PI)

En annen algoritme, kalt Policy Iteration (PI), prøver å oppnå den optimale policyen uten nødvendigvis å beregne ”til slutten” verdier av . Tanken er å starte fra en hvilken som helst policy , deretter å alternere en evalueringsfase der funksjonen bestemmes (med en av teknikkene som er sett ovenfor), og en forbedringsfase, der vi definerer følgende policy ved: V∗{\ displaystyle V ^ {*}}π0{\ displaystyle \ pi _ {0}}Vπikke{\ displaystyle V ^ {\ pi _ {n}}}πikke+1{\ displaystyle \ pi _ {n + 1}}

πikke+1(s)=arg⁡makspå∈PÅ∑s′∈S[R(s,på,s′)+γVπikke(s′)]T(s,på,s′).{\ displaystyle \ pi _ {n + 1} (s) = \ arg \ max _ {a \ i A} \ sum _ {s '\ i S} [R (s, a, s') + \ gamma V ^ {\ pi _ {n}} (s ')] T (s, a, s').}.

Denne algoritmen slutter når ingen policyendringer blir observert, dvs. når for alt . πikke+1(s)=πikke(s){\ displaystyle \ pi _ {n + 1} (s) = \ pi _ {n} (s)}s{\ displaystyle s}

Hvis det i den forrige algoritmen brukes en iterativ metode for å evaluere , oppstår spørsmålet om å vite med hvilken presisjon du skal stoppe. Dette problemet er faktisk ikke ett, fordi vi kan vise at selv om vi avkorter evalueringen av , konvergerer algoritmen fremdeles mot det optimale. I ytterste konsekvens, det vil si når en enkelt iterasjon brukes til å evaluere , og etter å ha kombinert forbedringsfasen og evalueringsfasen i et enkelt beregningstrinn, faller man tilbake på algoritmen VI. Vπ{\ displaystyle V ^ {\ pi}}Vπ{\ displaystyle V ^ {\ pi}}Vπ{\ displaystyle V ^ {\ pi}}

PI-algoritmen kan også formuleres i form av funksjonen til handlingstilstander i stedet for . Vi kan derfor se at et stort antall varianter kan tenkes, men alle dreier seg om det samme generelle prinsippet som er skjematisk vist i figuren motsatt. Q{\ displaystyle Q}V{\ displaystyle V}

Relaterte artikler

• Markov-kjeden, hvor MDP-er er avledet
• Delvis observerbare Markovianske beslutningsprosesser (POMDP), som gjør det mulig å modellere usikkerheten om tilstanden vi befinner oss i
• Stokastisk kalkulus , som er grunnlaget for stokastiske modeller
• Forsterkningslæring , en metode for å løse Markovianske beslutningsprosesser
• Metaheuristikk , metoder som noen ganger bruker Markovian-prosesser

Bibliografi

• (Puterman 1994) ML Puterman, Markov beslutningsprosesser. Diskret stokastisk dynamisk programmering. , Wiley-Interscience, New York 1994, 2005.
• (Sutton og Barto 1998) RS Sutton og AG Barto Reinforcement Learning: En introduksjon , MIT Press, Cambridge, MA, 1998.

Referanser

1. (in) Richard Bellman, "  A Markovian Decision Process  " , Journal of Mathematics and Mechanics , vol.  6, n o  5,1957, s.  679–684 ( ISSN  0095-9057 , leses online , åpnes 26. mars 2019 ).
2. (i) Xianping Guo, Onesimo Hernandez-Lerma, kontinuerlig tid Markovbeslutningsprosesser: Theory and Applications , Springer-Verlag Berlin Heidelberg, 2009, ( ISBN  978-3-642-02546-4 )

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">