Markovbeslissingsprocessen en bekrachtigingsleren

Een Markovbeslissingsproces, of MDP, beschrijft herhaalde beslissingen wanneer acties onzekere uitkomsten kunnen hebben. De agent neemt zijn huidige toestand waar, kiest een beschikbare actie, ontvangt een beloning en gaat naar een nieuwe toestand. Deze vier onderdelen beschrijven één overgang; een reeks overgangen beschrijft een traject.

Lees een overgangsmodel af

De toestandsverzameling is $S$ en $A(s)$ bevat de acties die in toestand $s$ zijn toegestaan. Het overgangsmodel $T(s,a,s^{\mathrm{\prime }})=P(s^{\mathrm{\prime }}\mid s,a)$ geeft de kans om $s^{\mathrm{\prime }}$ te bereiken na actie $a$ in $s$. Voor elk toestand-actiepaar zijn al deze kansen niet-negatief en tellen ze op tot 1. De beloning $R(s,a,s^{\mathrm{\prime }})$ hoort bij die overgang. Een negatieve beloning staat voor kosten of een straf.

Neem een bezorgrobot met de toestanden Hoog accuniveau, Laag accuniveau en Leeg. Leeg beëindigt de episode. Het model is:

De kansen in de twee rijen voor Werken tellen elk op tot 1. Voor Werken in Laag is de verwachte directe beloning $\mathrm{0,6}(4)+\mathrm{0,4}(-10)=-\mathrm{1,6}$. Dit gemiddelde is nuttig voor planning, maar een daadwerkelijke poging levert 4 of −10 op. Door Werken te kiezen, kies je de verdeling; je kiest niet de succesvolle uitkomst.

Neem het relevante verleden op in de toestand

De Markoveigenschap betekent dat de huidige toestand en actie de informatie bevatten die nodig is om de volgende toestand te voorspellen:

De wereld kan een lange geschiedenis hebben. Die geschiedenis telt mee via de variabelen die in de huidige toestand zijn opgenomen. Alleen de locatie van een robot kan onvoldoende zijn als de accu bepaalt of een opdracht slaagt. Door het accuniveau op te nemen, kan het model onderscheid maken tussen situaties met verschillende risico's.

Een standaard-MDP neemt aan dat de agent de toestand precies waarneemt. Als belangrijke delen van de toestand verborgen zijn, heeft de agent een kansinschatting van mogelijke toestanden nodig; dat leidt tot een gedeeltelijk waarneembaar MDP, of POMDP.

Herken eindpunten en toevallige bewegingen

Een eindtoestand heeft waarde 0 omdat er geen beloningen meer op volgen. De beloning bij het bereiken ervan telt nog steeds mee: de robot ontvangt −10 bij zijn laatste overgang naar Leeg. Episodische taken eindigen in een eindtoestand; voortdurende taken, zoals doorlopende temperatuurregeling, hebben geen eindtoestand nodig.

In een roosterwereld kan een bedoelde beweging met kans 0,8 slagen en met elk kans 0,1 afwijken naar een van de twee loodrechte richtingen. Als de agent tegen een muur probeert te bewegen, blijft hij op zijn plaats. Kansen van uitkomsten die hetzelfde vak bereiken, moet je optellen.

Deterministische overgangen zijn een speciaal geval: één opvolger heeft kans 1. Bij een bekend beginpunt en een geschikte taak waarbij een doel moet worden bereikt, kan een vast plan volstaan. Bij onzekere uitkomsten geeft een beleid aan hoe de agent reageert in welke toestand zich ook voordoet. Sommige teksten schrijven beloningen als $R(s)$ of $R(s,a)$; controleer de conventie voor het tijdstip voordat je een formule omzet.

Een beleid beschrijft hoe de agent handelt. Een deterministisch stationair beleid $\pi (s)$ kiest voor elke toestand één actie en behoudt die keuze in de tijd. Voor de robot is “Werk bij Hoog, laad op bij Laag” zo'n beleid. Een stochastisch beleid $\pi (a\mid s)$ kent kansen toe aan de beschikbare acties.

Bereken een cumulatieve beloning

De verdisconteerde cumulatieve beloning combineert de beloningen in een traject:

De eerste overgang levert $r_0$ op met gewicht 1. Elke latere beloning krijgt een extra factor van de disconteringsfactor $\gamma$. Voor de beloningen −1, −1, −1 en +10, gevolgd door beëindiging, geeft $\gamma =\mathrm{0,9}$

Met $\gamma =\mathrm{0,5}$ geeft hetzelfde traject $-1-\mathrm{0,5}-\mathrm{0,25}+10(\mathrm{0,125})=-\mathrm{0,5}$. De uitgestelde opbrengst verliest veel van haar gewicht. Discontering kan een voorkeur voor eerdere beloningen weergeven, of de kans dat het proces nog een stap doorgaat.

Je beoordeelt een beleid op de verwachte cumulatieve beloning, het gemiddelde over de mogelijke trajecten. Eén gelukkig traject bewijst niet dat een beleid goed is. Een optimaal beleid ${\pi }^{\ast }$ geeft vanuit elke toestand de grootste verwachte cumulatieve beloning. Een eindig MDP met discontering heeft een optimaal beleid dat deterministisch en stationair is.

Houd een oneindige toekomst eindig

Bij begrensde beloningen en $0\le \gamma <1$ begrenst de meetkundige reeks elke cumulatieve beloning. Als $\mathrm{\mid }{r}_t\mathrm{\mid }\le R_{\max }$, dan geldt

De grootste beloning van de robot heeft absolute waarde 10, dus $\gamma =\mathrm{0,9}$ geeft $\mathrm{\mid }U\mathrm{\mid }\le 100$. Omdat de grootste positieve beloning 4 is, kan de cumulatieve beloning ook niet groter zijn dan $4\mathrm{/}(1-\mathrm{0,9})=40$. Dit zijn grenzen, geen beweringen dat de robot ze kan bereiken.

De grootheid $1\mathrm{/}(1-\gamma )$ is een ruwe effectieve horizon: ongeveer 10 stappen bij $\gamma =\mathrm{0,9}$. Het is geen afkappunt. Een beloning 10 stappen later krijgt nog steeds gewicht ${\mathrm{0,9}}^{10}\approx \mathrm{0,35}$. Voortdurende taken zonder discontering vragen bijzondere aandacht: herhaalde positieve beloningen kunnen cumulatieve beloningen oneindig maken. Een vaste eindige horizon maakt de som eindig; ook bij episodische modellen moeten de episodelengtes zich geschikt gedragen om eindige verwachtingswaarden te krijgen.

Laat tijd en stapbeloningen beslissingen beïnvloeden

Bij een deadline kan de beste actie afhangen van de resterende tijd. Neem een machine in de toestand Versleten. Draaien levert 6 op en laat de machine met gelijke kans Versleten of Kapot achter. Repareren levert −4 op en maakt de machine Goed. In Goed levert Draaien 10 op; in Kapot levert Repareren −20 op. Met één stap te gaan heeft Draaien in Versleten de voorkeur: $6>-4$. Met twee stappen te gaan en $\gamma =\mathrm{0,9}$ geeft Repareren $-4+\mathrm{0,9}(10)=5$. Draaien geeft $6+\mathrm{0,9}[\mathrm{0,5}(6)+\mathrm{0,5}(-20)]=-\mathrm{0,3}$. De extra tijd keert de keuze om.

De beloning voor voortzetting in een roosterwereld, die wordt ontvangen bij stappen die niet in een eindtoestand eindigen, verandert de kosten van uitstel. Negatieve stapbeloningen moedigen aan om een uitgang te bereiken; een grotere straf kan een nabijgelegen slechte uitgang aantrekkelijker maken dan een lange route. Een voldoende grote positieve stapbeloning kan ervoor zorgen dat in het rooster blijven de voorkeur krijgt. De precieze keuze hangt ook af van discontering, afstanden en uitwijkrisico's.

Door een MDP te formuleren zet je een praktisch doel om in beslissingen die een computer kan beoordelen. Bepaal eerst wanneer beslissingen plaatsvinden. Definieer vervolgens een waarneembare toestand, toegestane acties, overgangskansen, beloningen, eventuele eindtoestanden en een disconteringsfactor of horizon. De kwaliteit van het resulterende beleid hangt van deze keuzes af.

Modelleer machineonderhoud

Stel dat een machine eenmaal per beslissingsstap wordt geïnspecteerd. De toestand is Goed, Versleten of Kapot. Het model is:

Kapot is geen eindtoestand: na reparatie kan het werk doorgaan. De taak is voortdurend, met $\gamma =\mathrm{0,9}$. Merk op dat de beschikbare acties afhangen van de toestand; Draaien is niet beschikbaar in Kapot.

Het oplossen van dit model geeft optimale waarden van ongeveer 78,64 in Goed, 66,78 in Versleten en 50,78 in Kapot. In Versleten heeft Repareren waarde $-4+\mathrm{0,9}(\mathrm{78,64})\approx \mathrm{66,78}$. Draaien heeft waarde $6+\mathrm{0,9}[\mathrm{0,5}(\mathrm{66,78})+\mathrm{0,5}(\mathrm{50,78})]\approx \mathrm{58,90}$. De negatieve directe beloning voor reparatie verschaft toegang tot een productievere toekomst.

Kies voldoende toestandsinformatie

De toestand moet voorspellingen van zowel uitkomsten als beloningen mogelijk maken. De positie van een bewegende bal alleen laat de snelheid weg, zodat twee identieke posities verschillende volgende posities kunnen hebben. Bij een bordspel moet de toestand ook aangeven wie aan de beurt is. Als de resterende tijd verandert welke acties lonen, neem die dan op in een beslissingsregel met eindige horizon of breid de toestand ermee uit.

Extra variabelen vergroten de toestandsruimte. Tien ja-neevariabelen maken $2^{10}=1024$ combinaties mogelijk. Behoud informatie die voorspellingen of beloningen verandert; de hele geschiedenis opslaan kan een bruikbaar model onnodig groot maken. Het gebruikelijke stationaire MDP neemt aan dat de overgangs- en beloningsregels in de tijd gelijk blijven. Een verborgen toestand vraagt om een model van kansinschattingen, terwijl strategische tegenstanders om een spelmodel vragen.

Laat de beloning het doel uitdrukken

Een schoonmaakrobot die voor elk verzameld stukje vuil wordt beloond, kan voordeel halen uit het morsen en opnieuw oprapen van vuil. Dit is misbruik van de beloningsfunctie: succesvolle optimalisatie van een slechte maatstaf. Een beloning die gekoppeld is aan de gewenste schoonheid voorkomt die specifieke lus. Een sporadische doelbeloning geeft succes duidelijk aan, maar biedt weinig terugkoppeling tijdens een lange poging.

Beloningsvorming voegt terugkoppeling over voortgang toe. Willekeurige bonussen kunnen het doel veranderen. Twee nuttige vergelijkingen zijn:

• Als je alle beloningen met hetzelfde positieve getal vermenigvuldigt, blijft de rangorde van beleidsvormen behouden.
• Als je bij elke beloning een constante optelt, blijven optimale beleidsvormen bij een voortdurende taak met discontering behouden, omdat elk beleid dezelfde verdisconteerde constante erbij krijgt. Bij een episodische taak krijgen langere en kortere trajecten verschillende bedragen erbij, zodat de rangorde kan veranderen.

Een term voor beloningsvorming die het beleid behoudt, heeft de vorm $F(s,a,s^{\mathrm{\prime }})=\gamma \mathrm{\Phi }(s^{\mathrm{\prime }})-\mathrm{\Phi }(s)$. Hier kent $\mathrm{\Phi }$ aan elke toestand een potentiaal toe. Bij begrensde potentialen in een voortdurende taak met discontering vallen de toegevoegde verdisconteerde termen tegen elkaar weg, op een correctieterm voor de begintoestand na. Bij episodische taken verdwijnt de overgebleven eindterm als je elke eindpotentiaal op 0 stelt. Een eindpotentiaal ongelijk aan nul kan veranderen aan welk einde of welk stoptijdstip de voorkeur wordt gegeven.

Een waarde meet de cumulatieve beloning die vanuit een situatie beschikbaar is bij een bepaalde manier van handelen. Ze omvat toekomstige beloningen, gewogen naar hun kansen en tijdstip. Daardoor verschillen waarden van de beloning die bij één overgang wordt ontvangen.

Onderscheid de eerste keuze

De toestandswaarde $V^{\pi }(s)$ is de verwachte verdisconteerde cumulatieve beloning als de agent in toestand $s$ begint en beleid $\pi$ volgt. De actiewaarde $Q^{\pi }(s,a)$ legt de eerste actie vast op $a$ en volgt daarna $\pi$. Dit betekent niet dat de agent bij elke latere stap $a$ uitvoert.

Optimale waarden vervangen dat vervolgbeleid door het best mogelijke gedrag. Zo is $V^{\ast }(s)$ de beste verwachte cumulatieve beloning vanuit $s$ en $Q^{\ast }(s,a)$ de beste verwachte cumulatieve beloning nadat de eerste actie is vastgelegd. Hun verband is

Het maximum is een getal; de argmax wijst een actie aan die dat maximum bereikt. Als meerdere acties gelijk eindigen, kan elk daarvan worden gekozen.

Lees de keuzes van de robot af

Voor de bezorgrobot met $\gamma =\mathrm{0,9}$ zijn de optimale Q-waarden:

Het maximum van elke rij is de optimale waarde van de toestand. In Hoog heeft Werken de voorkeur; in Laag Opladen. Opladen levert direct 0 op, maar geeft in Laag opnieuw toegang tot Hoog en de betere toekomstige mogelijkheden daar. Werken in Laag heeft nog steeds een positieve optimale Q-waarde omdat een robot die blijft werken daarna kan opladen.

Het vervolgbeleid doet ertoe. Onder “altijd Werken” dalen de toestandswaarden tot ongeveer 8,27 in Hoog en −3,48 in Laag. Het model is niet veranderd; de beslissingen na elke uitkomst zijn veranderd. Een getal met alleen het label “de waarde” is onvolledig, tenzij het bedoelde beleid of de optimaliteit duidelijk is.

Zie keuzes en toeval als afzonderlijke lagen

Een expectimaxboom wisselt twee soorten knopen af. In een toestand kiest de agent een actie; bij een toestand-actiepaar, ook wel q-toestand genoemd, kiest het toeval de volgende toestand volgens het overgangsmodel. De agent neemt het maximum over acties en het gemiddelde over hun uitkomsten.

Een cyclisch MDP herhaalt dezelfde toestanden op veel plaatsen in de boom. Dynamisch programmeren slaat voor elke toestand een waarde op en gebruikt die opnieuw. Zo hoeft hetzelfde vervolgprobleem niet opnieuw te worden berekend telkens wanneer een pad in de boom naar die toestand terugkeert.

Leid een beleid af uit de beschikbare waarden

Vergelijk met een Q-tabel de actiewaarden in de huidige rij. Daarvoor is geen overgangsmodel nodig. Bereken met alleen toestandswaarden eerst de verwachte beloning van een actie plus de verdisconteerde opvolgerwaarde:

Voor die berekening zijn overgangen en beloningen nodig. Als je alleen de actie kiest die de opvolger met de hoogste waarde kan bereiken, negeer je hoe waarschijnlijk die opvolger is en wat de actie kost. Een hoge verwachtingswaarde laat ook ruimte voor een ongelukkig traject: ze beschrijft een gemiddelde over uitkomsten, geen gegarandeerde beloning bij elke poging.

Je kunt de cumulatieve beloning van een traject na de eerste overgang splitsen: de directe beloning plus de verdisconteerde cumulatieve beloning vanuit de volgende toestand. Door een verwachtingswaarde te nemen ontstaat een Bellmanvergelijking. Die verbindt de waarde van een toestand met opvolgerwaarden, inclusief de mogelijkheid om naar dezelfde toestand terug te keren.

Evalueer een vast beleid

Voor een deterministisch beleid verschijnt alleen de gekozen actie:

Elke tak draagt zijn kans maal de directe beloning plus toekomstige waarde bij. Er is één vergelijking per toestand. In een eindig MDP met discontering zijn dit lineaire vergelijkingen met een unieke oplossing.

Begin voor het beleid “altijd Werken” van de robot in Laag. De twee mogelijke overgangen geven

Werk de haakjes uit en verzamel de onbekende: $V(L)=\mathrm{2,4}+\mathrm{0,54}V(L)-4$, dus $\mathrm{0,46}V(L)=-\mathrm{1,6}$. Daarom is $V(L)\approx -\mathrm{3,48}$. De beloning −10 blijft staan, ook al is de toekomstige waarde van Leeg 0.

In Hoog leveren beide uitkomsten 4 op, dus samen geven hun directe beloningen 4:

Termen verzamelen geeft $\mathrm{0,37}V(H)=4+\mathrm{0,27}V(L)$. Met de niet-afgeronde waarde van Laag krijg je $V(H)\approx \mathrm{8,27}$. Behoud de volledige nauwkeurigheid tijdens het invullen; rond de gerapporteerde waarden aan het einde af.

Voeg de keuze van een actie toe

Bereken voor optimale waarden de verwachtingswaarde van elke beschikbare actie en neem dan de beste:

De maximumbewerking staat buiten de som omdat de agent één actie kiest voordat hij de uitkomst ziet. Als hij voor elke mogelijke volgende toestand een andere huidige actie zou kiezen, zou hij beschikken over informatie die hij nog niet heeft.

De Q-vorm legt die eerste actie vast, maar staat de beste volgende actie toe nadat de opvolger is waargenomen:

Deze optimaliteitsvergelijkingen bevatten maxima, dus één lineaire oplossingsstap voor een vast beleid lost ze niet rechtstreeks op.

Controleer voorgestelde waarden

Gebruik de voorgestelde optimale waarden van de robot $V(H)\approx \mathrm{31,50}$ en $V(L)\approx \mathrm{28,35}$. In Hoog geeft Werken $4+\mathrm{0,9}[\mathrm{0,7}(\mathrm{31,50})+\mathrm{0,3}(\mathrm{28,35})]\approx \mathrm{31,50}$. Opladen geeft $\mathrm{0,9}(\mathrm{31,50})=\mathrm{28,35}$. De grootste uitkomst komt overeen met de voorgestelde waarde van Hoog.

In Laag geeft Werken $\mathrm{0,6}[4+\mathrm{0,9}(\mathrm{28,35})]+\mathrm{0,4}(-10)\approx \mathrm{13,71}$; Opladen geeft 28,35. Het maximum komt ook overeen met de voorgestelde waarde van Laag. Als je slechts één toestand controleert, blijft de andere vergelijking ongetest. Kleine verschillen zijn te verwachten als de voorgestelde waarden zijn afgerond.

Verdisconteer alleen de toekomstige term. Als je $R+\gamma V$ vervangt door $\gamma (R+V)$, stel je de directe beloning ten onrechte één stap uit.

Beleidsevaluatie vraagt hoeveel verwachte cumulatieve beloning een vast beleid oplevert. Het model en het beleid zijn bekend. Tijdens deze berekening worden geen actiekeuzes verbeterd; de uitkomst is $V^{\pi }$, die later een afzonderlijke verbeteringsstap kan ondersteunen.

Los de vergelijkingen exact op

Neem het beleid “Werk bij Hoog, laad op bij Laag” en $\gamma =\mathrm{0,9}$. Opladen in Laag geeft geen directe beloning en bereikt altijd Hoog, dus $V(L)=\mathrm{0,9}V(H)$. Werken in Hoog geeft

Vul de eerste vergelijking in de tweede in:

Dan is $\mathrm{0,127}V(H)=4$, wat $V(H)=4\mathrm{/}\mathrm{0,127}\approx \mathrm{31,50}$ en $V(L)\approx \mathrm{28,35}$ geeft. Hiermee zijn de waarden van dat beleid vastgesteld. Om te bewijzen dat het optimaal is, moet je ook de andere acties controleren.

Exacte evaluatie lost één lineaire vergelijking per toestand die geen eindtoestand is op. Standaardeliminatie voor een dicht stelsel kost in de orde van $\mathrm{\mid }S{\mathrm{\mid }}^3$ bewerkingen. De methode is handig voor een klein model omdat je de verbanden rechtstreeks kunt bekijken.

Evalueer met herhaalde actualisatieronden

Een iteratief alternatief begint met $V_0(s)=0$ en past de actualisatie voor een vast beleid toe op elke toestand:

Elke nieuwe waarde gebruikt de oude array. Voor “altijd Werken” geven de eerste drie ronden, in de volgorde Hoog en dan Laag:

De tweede waarde voor Laag is bijvoorbeeld $\mathrm{0,6}[4+\mathrm{0,9}(-\mathrm{1,6})]+\mathrm{0,4}(-10)=-\mathrm{2,464}$. Hoog gebruikt in diezelfde ronde de oude waarde 4 voor Hoog en de oude waarde −1,6 voor Laag, wat $4+\mathrm{0,9}[\mathrm{0,7}(4)+\mathrm{0,3}(-\mathrm{1,6})]=\mathrm{6,088}$ geeft.

Bij een disconteringsfactor kleiner dan 1 convergeren de ronden naar ongeveer 8,27 en −3,48. Een ronde voor een dicht model met vast beleid kost in de orde van $\mathrm{\mid }S{\mathrm{\mid }}^2$ bewerkingen, omdat elke toestand over opvolgers sommeert. Bij ijle overgangsmodellen kun je opvolgers met kans 0 overslaan.

Interpreteer tussenliggende waarden

Als je bij nul begint, is $V_k(s)$ de verwachte verdisconteerde beloning over de volgende $k$ overgangen onder het vaste beleid, zonder waarde voorbij die horizon. De eerste ronde ziet alleen directe beloningen. De tweede omvat nog een overgang. Deze tussenliggende waarden hebben al vóór convergentie een duidelijke betekenis.

Bij directe actualisatie gebruik je binnen dezelfde ronde enkele pas berekende waarden. Onder de gebruikelijke voorwaarden met discontering kan ook dit convergeren, maar de tussenliggende arrays hoeven niet gelijk te zijn aan deze synchrone waarden met eindige horizon. Houd bij een handberekening oude en nieuwe arrays gescheiden als je synchrone ronden vergelijkt.

Voeg tijdens evaluatie geen maximum over acties toe. Dan zou de agent zijn gedrag kunnen veranderen en beantwoord je een andere vraag dan die van het vaste beleid.

Waarde-iteratie vraagt herhaaldelijk wat het beste is als één extra beslissing is toegestaan. De methode begint met $V_0=0$ en actualiseert elke toestand met de beste verwachte beloning plus de verdisconteerde opvolgerwaarde. Dezelfde berekening kan met cycli omgaan omdat opvolgerwaarden uit een opgeslagen array komen.

Voer één volledige ronde uit

Bereken voor elke toestand die geen eindtoestand is

In de eerste ronde voor de robot zijn alle toekomstige termen 0. In Hoog vergelijk je Werken met waarde 4 met Opladen met waarde 0, dus $V_1(H)=4$. In Laag vergelijk je Werken met waarde $\mathrm{0,6}(4)+\mathrm{0,4}(-10)=-\mathrm{1,6}$ met Opladen met waarde 0, dus $V_1(L)=0$.

De tweede ronde gebruikt deze hele oude array. In Hoog geeft Werken $4+\mathrm{0,9}[\mathrm{0,7}(4)+\mathrm{0,3}(0)]=\mathrm{6,52}$, terwijl Opladen $\mathrm{0,9}(4)=\mathrm{3,6}$ geeft. In Laag geeft Werken nog steeds −1,6, terwijl Opladen 3,6 geeft. Dus $V_2=(\mathrm{6,52};\mathrm{3,6})$. Een derde ronde geeft ongeveer $(\mathrm{9,08};\mathrm{5,87})$.

Als je de nieuwe waarde 6,52 voor Hoog direct zou gebruiken om Laag te actualiseren, zou de uitkomst anders zijn. Dat is een directe actualisatie, niet de zojuist getoonde synchrone tweede ronde.

Begrijp wat convergeert

Bij initialisatie op nul is $V_k$ de optimale verwachte cumulatieve beloning wanneer er precies $k$ beslissingsmogelijkheden over zijn, waarbij episodes in een eindtoestand eerder mogen eindigen. Elke ronde verlengt de bruikbare planningshorizon met één stap. De Bellmanoptimaliteitsoperator is een contractie bij $\gamma <1$: de grootste fout over toestanden krimpt per toepassing ten minste met een factor $\gamma$. De waarden convergeren vanuit elke eindige beginarray naar de unieke $V^{\ast }$.

Een ronde voor een dicht model bekijkt toestanden, acties en opvolgers en kost in de orde van $\mathrm{\mid }S{\mathrm{\mid }}^2\mathrm{\mid }A\mathrm{\mid }$ bewerkingen. Een disconteringsfactor dicht bij 1 vertraagt de convergentie meestal omdat verre beloningen meer gewicht behouden.

Stop met een foutgrens

Stel ${\mathrm{\Delta }}_k={\max }_s\mathrm{\mid }{V}_{k+1}(s)-V_k(s)\mathrm{\mid }$. Voor $0<\gamma <1$ wordt de maximale fout van de nieuwe array begrensd door $\gamma {\mathrm{\Delta }}_k\mathrm{/}(1-\gamma )$. Om een fout kleiner dan een gekozen tolerantie $\epsilon$ te garanderen, volstaat

Voor $\gamma =\mathrm{0,9}$ en tolerantie 0,01 is de drempel ongeveer 0,00111. Een verandering kleiner dan 0,01 alleen garandeert geen waardefout kleiner dan 0,01. Bij $\gamma =0$ geeft één actualisatie de optimale directe beloningen, dus is delen door de disconteringsfactor niet nodig.

Lees het beleid af

Vergelijk na het stoppen de verwachtingswaarden van acties met de uiteindelijke waardenarray. Dit één stap vooruitkijken geeft een gulzig beleid. Het beleid kan eerder stabiel worden dan de waarden: het gulzige beleid van de robot uit $V_1$ zegt al “Werk bij Hoog, laad op bij Laag”, maar de waarden hebben 77 ronden nodig om tot op 0,01 van het optimale paar $(\mathrm{31,50};\mathrm{28,35})$ te komen.

Een stabiel ogend beleid en nauwkeurige waarden zijn verschillende controles. De actualisatie moet verwachte uitkomsten voor elke actie vergelijken; als je de afzonderlijke mogelijke opvolger met de hoogste waarde kiest, laat je zowel risico als directe beloning buiten beschouwing.

Beleidsiteratie wisselt twee taken af: een beleid meten en vervolgens de acties ervan verbeteren met die meting. Begin met een willekeurig deterministisch beleid. Een goede eerste gok kan werk besparen, maar is in een eindig MDP met discontering niet vereist voor een correcte uitkomst.

Scheid evaluatie van verbetering

Bereken eerst $V^{{\pi }_i}$, de waarden van het huidige beleid. Vergelijk vervolgens voor elke toestand alle acties met dezelfde waarden:

Evaluatie beschrijft het oude gedrag. Verbetering vraagt of het veranderen van de eerste actie de cumulatieve beloning zou verbeteren als daarna het oude beleid werd gevolgd. Als je al zulke acties verandert, krijg je een beleid dat in elke toestand minstens zo goed is. Als het oude beleid niet optimaal is, is de verbetering in ten minste één toestand strikt.

Behoud de huidige actie telkens als die even goed is als de beste. Anders kunnen even goede acties een beleid ogenschijnlijk laten veranderen terwijl de waarde niet verbetert.

Verbeter het beleid van de robot

Begin met “altijd Werken”. Exacte evaluatie geeft voor Hoog ongeveer 8,27 en voor Laag ongeveer −3,48. In Hoog geeft Werken behouden 8,27; overstappen op Opladen geeft $\mathrm{0,9}(\mathrm{8,27})\approx \mathrm{7,45}$. Behoud Werken. In Laag geeft Werken −3,48 en Opladen ongeveer 7,45. Stap in Laag over op Opladen.

Evalueer nu het nieuwe beleid “Werk bij Hoog, laad op bij Laag”. De waarden zijn ongeveer 31,50 en 28,35. Verbeter opnieuw:

Geen actie verandert, dus beleidsiteratie stopt. De waarden van het vaste beleid voldoen ook aan de optimaliteitsvergelijkingen, waarmee vaststaat dat dit beleid optimaal is. De robot had vanuit dit startbeleid twee volledige evaluaties nodig.

Leg uit waarom het proces eindigt

Een eindig MDP heeft slechts eindig veel deterministische beleidsvormen. Als elk van de $\mathrm{\mid }S\mathrm{\mid }$ toestanden $\mathrm{\mid }A\mathrm{\mid }$ keuzes heeft, zijn er $\mathrm{\mid }A{\mathrm{\mid }}^{\mathrm{\mid }S\mathrm{\mid }}$ van zulke beleidsvormen. De robot heeft twee toestanden die geen eindtoestand zijn, met elk twee acties, wat $2^2=4$ beleidsvormen geeft. Met strikte verbetering wanneer dat nodig is en een consequente afhandeling van gelijke waarden kan het proces niet naar een slechter beleid terugkeren en moet het eindigen.

Vergelijk de planningsmethoden

Volledige evaluaties maken ronden van beleidsiteratie duurder, maar vaak zijn minder ronden nodig. De 77 ronden waarde-iteratie en twee beleidsevaluaties van de robot zijn verschillende eenheden werk, dus de aantallen alleen tonen niet aan welke methode sneller is. Gebruik tijdens elke verbetering waarden die bij het huidige beleid horen; als je die mengt met waarden van een eerder beleid, gaat de betekenis van die stap verloren.

Bij bekrachtigingsleren leert een agent uit ervaring in een beslissingsprobleem. Hij neemt een toestand waar, kiest een beschikbare actie en ontvangt een steekproef $(s,a,r,s^{\mathrm{\prime }})$: de vorige toestand, de actie, de beloning en de volgende toestand. Het doel blijft een hoge verwachte cumulatieve beloning, maar overgangskansen en beloningen moeten worden geleerd.

Onderscheid leren van plannen

Planning gebruikt een MDP-model om waarden of beleidsvormen te berekenen. Dat kan gebeuren voordat de agent handelt of terwijl hij tijdens het handelen opnieuw plant. Leren gebruikt waargenomen ervaring, uit voortdurende interactie of uit een eerder verzamelde dataset. Ook offline bekrachtigingsleren leert uit ervaring; het gebruikt daarbij vastgelegde ervaring.

Bij passief leren staat een beleid vast en is het de taak om te schatten hoe goed het presteert. Bij actief leren kiest de agent ook acties om beter gedrag te ontdekken. Die keuzes beïnvloeden zowel de verzamelde beloning als de informatie die voor toekomstige actualisaties beschikbaar is.

Schat overgangen met tellingen

Een modelgebaseerde lerende agent houdt bij hoe vaak elke actie in elke toestand wordt geprobeerd. Laat $N(s,a)$ die pogingen tellen en $N(s,a,s^{\mathrm{\prime }})$ de pogingen die in een bepaalde opvolger eindigen. Dan geldt

De tellingen in de teller verdelen de pogingen in de noemer over de mogelijke opvolgers, zodat hun geschatte kansen optellen tot 1. Een niet-geprobeerd paar heeft noemer 0 en vereist meer ervaring of een expliciete modelkeuze; het heeft nog geen empirische overgangsverdeling.

Bij de robot werd Werken in Hoog 20 keer geprobeerd: 13 overgangen bleven in Hoog en 7 bereikten Laag. De schattingen zijn $13\mathrm{/}20=\mathrm{0,65}$ en $7\mathrm{/}20=\mathrm{0,35}$. Werken in Laag werd 10 keer geprobeerd: 7 keer viel de accu niet uit en 3 keer bereikte de robot Leeg, wat 0,7 en 0,3 geeft. De tweede schatting onderschat de werkelijke kans van 0,4 om leeg te raken.

Leg ook de beloningen voor elke overgang vast. De robot heeft vaste beloningen voor zijn uitkomsten. Als herhaalde identieke overgangen beloningen met ruis hebben, schat dan hun voorwaardelijke gemiddelde beloning uit de waargenomen steekproeven.

Plan met het geleerde model

Gebruik de geschatte overgangen en beloningen in waarde-iteratie of beleidsiteratie. Voor deze tellingen van de robot, met bekende overgangen voor Opladen en $\gamma =\mathrm{0,9}$, zijn de geschatte optimale waarden ongeveer $(\mathrm{30,42};\mathrm{27,38})$. De optimale actiekeuzes komen nog steeds overeen met die van het werkelijke model: Werken in Hoog, Opladen in Laag. Vergelijkbare beleidsvormen kunnen dus uit verschillende waardeschattingen voortkomen.

Weinig steekproeven kunnen onnauwkeurige modellen geven. Meer representatieve ervaring verbetert de schattingen, maar als je alleen onder één beperkt beleid gegevens verzamelt, kunnen nuttige acties onuitgeprobeerd blijven. Ook een modelgebaseerde lerende agent heeft exploratie nodig.

Vergelijk twee leerroutes

Een geleerd model kan steekproeven hergebruiken voor veel planningsactualisaties en opnieuw plannen ondersteunen als doelen veranderen. Het kost ook opslagruimte en rekenwerk, en modelfouten kunnen het plan vertekenen. Modelvrije methoden vermijden het bouwen van een overgangstabel, maar hebben meestal aanzienlijke ervaring nodig om hun waardeschattingen betrouwbaar te maken.

Je kunt een vast beleid evalueren zonder het overgangsmodel te kennen. Directe evaluatie middelt volledige cumulatieve beloningen uit steekproeven. TD-leren actualiseert op basis van één beloning en een geschatte opvolgerwaarde. Beide leren de waarden van het beleid uit ervaring.

Middel cumulatieve beloningen van volledige episodes

Volg “altijd Werken” met $\gamma =\mathrm{0,9}$. Een episode van de robot is Hoog → Hoog (+4), Hoog → Laag (+4), Laag → Leeg (−10). De cumulatieve beloningen vanaf de bezoeken aan Hoog zijn $4+\mathrm{0,9}(4)+\mathrm{0,81}(-10)=-\mathrm{0,5}$ en $4+\mathrm{0,9}(-10)=-5$. De cumulatieve beloning vanaf Laag is −10.

Een tweede episode is Hoog → Laag (+4), Laag → Laag (+4), Laag → Leeg (−10). De cumulatieve beloning vanaf Hoog is −0,5; die vanaf de bezoeken aan Laag zijn −5 en −10. De gemiddelden op basis van elk bezoek zijn dus $(-\mathrm{0,5}-5-\mathrm{0,5})\mathrm{/}3=-2$ voor Hoog en $(-10-5-10)\mathrm{/}3\approx -\mathrm{8,33}$ voor Laag. Een methode op basis van het eerste bezoek zou alleen het eerste bezoek aan een toestand in elke episode meetellen.

Deze schattingen verschillen sterk van de werkelijke beleidswaarden $(\mathrm{8,27};-\mathrm{3,48})$ omdat beide episodes snel eindigden. Volledige cumulatieve beloningen vertonen steekproefvariatie. Met voldoende representatieve voltooide episodes naderen hun gemiddelden de verwachte cumulatieve beloningen van het beleid. Directe evaluatie wacht totdat de benodigde cumulatieve beloning aan het einde van de episode beschikbaar is en schat toestanden afzonderlijk.

Actualiseer na één overgang

TD gebruikt de huidige schatting van wat volgt:

De doelwaarde is $r+\gamma V(s^{\mathrm{\prime }})$. De TD-fout is de doelwaarde min de huidige schatting. De leersnelheid $\alpha$ bepaalt welk deel van die fout in de actualisatie wordt gebruikt.

Stel $V(H)=10$, $V(L)=8$, $\gamma =\mathrm{0,9}$ en $\alpha =\mathrm{0,5}$. Na Hoog → Laag met beloning 4 is de doelwaarde $4+\mathrm{0,9}(8)=\mathrm{11,2}$. De fout is $\mathrm{11,2}-10=\mathrm{1,2}$, dus de nieuwe schatting voor Hoog is $10+\mathrm{0,5}(\mathrm{1,2})=\mathrm{10,6}$. De opgeslagen waarde van Laag blijft bij deze actualisatie 8. Een volgende toestand die een eindtoestand is, draagt geen toekomstige term bij.

TD gebruikt bootstrapping: het gebruikt een schatting om een andere schatting te verbeteren. Zo wordt informatie doorgegeven via verbonden toestanden en zijn actualisaties in voortdurende taken mogelijk, maar vroege doelwaarden kunnen door slechte opvolgerschattingen vertekend zijn.

Bepaal hoe zwaar nieuwe informatie meetelt

Een grote leersnelheid reageert sterk op elke doelwaarde. Bij $\alpha =1$ wordt de oude schatting vervangen door de nieuwste doelwaarde. Een vaste positieve leersnelheid blijft doorgaans de ruis van steekproeven volgen. Geschikt afnemende leersnelheden ondersteunen, bij herhaalde bezoeken en de gebruikelijke aannamen van eindigheid en discontering, de convergentie van TD met een tabel. Een leersnelheid $1\mathrm{/}N(s)$ middelt de reeks waargenomen TD-doelwaarden; die doelwaarden veranderen zelf naarmate opvolgerschattingen verbeteren.

Toestandswaarden alleen laten zonder informatie over overgangen en beloningen voor een vooruitblik niet zien wat de beste actie is. Passief TD evalueert het gedrag dat de steekproeven oplevert. Actiewaarden leren geeft een agent een directe manier om acties te vergelijken zonder eerst een model te leren.

Q-leren leert actiewaarden uit waargenomen overgangen. De doelwaarde gaat uit van de beste volgende actie, ook terwijl de agent explorerende acties kiest. Zo kan hij leren goed te handelen zonder een overgangsmodel te schatten.

Vervang een verwachte actualisatie door een steekproef

Een modelgebaseerde Q-actualisatie middelt over alle mogelijke opvolgers:

Q-leren ziet telkens één opvolger. Na een steekproef $(s,a,r,s^{\mathrm{\prime }})$ berekent de methode

en actualiseert ze $Q(s,a)\leftarrow Q(s,a)+\alpha [y-Q(s,a)]$. Als de opvolger een eindtoestand is, wordt $y=r$. Het maximum gaat over acties die in de volgende toestand beschikbaar zijn, niet in de zojuist verlaten toestand.

Initialiseer de Q-tabel, kies een actie met een exploratieregel, neem het resultaat waar, actualiseer de gekozen invoer en ga verder vanuit de volgende toestand. Begin na beëindiging opnieuw. Om het geleerde beleid te gebruiken, kies je een actie die de grootste Q-waarde in de huidige rij bereikt.

Werk twee actualisaties uit

Neem $\gamma =\mathrm{0,9}$ en $\alpha =\mathrm{0,5}$. Aanvankelijk is $Q(L,\text{Werken})=5$. De robot probeert Werken in Laag en raakt leeg met beloning −10. De doelwaarde is −10, dus de nieuwe waarde is $5+\mathrm{0,5}(-10-5)=-\mathrm{2,5}$. Na Leeg is er geen toekomstige cumulatieve beloning.

Stel vervolgens dat $Q(H,\text{Werken})=6$ en dat de robot in Hoog werkt, 4 verdient en Laag bereikt. In Laag zijn de schattingen −2,5 voor Werken en 3 voor Opladen. De beste volgende waarde is 3, zodat de doelwaarde $4+\mathrm{0,9}(3)=\mathrm{6,7}$ is. De geactualiseerde waarde voor Hoog en Werken is $6+\mathrm{0,5}(\mathrm{6,7}-6)=\mathrm{6,35}$. Deze steekproef actualiseert alleen die invoer in de tabel.

Onderscheid doelgedrag van werkelijk gedrag

Q-leren is leren voor een afwijkend doelbeleid: het vervolg in de doelwaarde is gulzig, ook als de actieselectieregel exploreert. SARSA leert voor het gevolgde beleid: het gebruikt $r+\gamma Q(s^{\mathrm{\prime }},a^{\mathrm{\prime }})$ voor de werkelijk gekozen volgende actie.

Naast een afgrond kan een explorerende agent per ongeluk gevaarlijke stappen zetten. SARSA houdt rekening met die toekomstige explorerende acties en kan een voorzichtiger route leren. Q-leren richt zich op het gulzige vervolg en kan de voorkeur geven aan een kortere route langs de rand, ook al maakt exploratie de trajecten tijdens het trainen riskant.

Formuleer de garantie voor de tabel precies

In een eindig stationair MDP met begrensde beloningen en $\gamma <1$ convergeert Q-leren met een tabel met kans 1 naar $Q^{\ast }$ wanneer elk toestand-actiepaar oneindig veel actualisaties krijgt en de bijbehorende leersnelheden voldoen aan

Een leersnelheid per paar $1\mathrm{/}N(s,a)$ heeft deze vorm. Een leersnelheid $1\mathrm{/}N(s,a{)}^2$ neemt te snel af: de totale som is eindig, zodat mogelijk te weinig aanpassing overblijft om een beginfout te verwijderen. Oneindige totale aanpassing voorkomt dat het leren te vroeg stopt; eindige gekwadrateerde aanpassing beheerst de opgetelde ruis. Constante leersnelheden behouden bij stochastische taken doorgaans schommelingen. Dit zijn voorwaarden voor de limiet, dus een eindige trainingsperiode moet je nog steeds evalueren.

Exploitatie kiest de actie die op dat moment het beste lijkt. Exploratie verzamelt informatie die een betere keuze kan onthullen. Als de robot door een vroege ongelukkige poging tot Werken in Hoog de voorkeur geeft aan Opladen, kan zuivere exploitatie hem eindeloos laten opladen en de schatting voor Werken ongecorrigeerd laten.

Tel de willekeurige tak correct mee

Een epsilon-gulzige regel exploreert uniform met kans $\epsilon$ en kiest anders een gulzige actie. Stel dat er één gulzige actie is onder vier acties en $\epsilon =\mathrm{0,2}$. De kans dat die wordt gekozen is $\mathrm{0,8}+\mathrm{0,2}\mathrm{/}4=\mathrm{0,85}$. Elke andere actie heeft kans 0,05. De willekeurige tak omvat ook de gulzige actie.

Weinig exploratie vroeg in de training kan nuttige acties ongetest laten; veel exploratie laat in de training blijft beloning kosten. Een schema kan in de limiet gulzig worden en toch elk relevant paar oneindig vaak proberen. Deze GLIE-eigenschap is sterker dan alleen epsilon verlagen, en bereikbaarheid is van belang voor de vraag of alle toestanden worden bezocht.

Geef de voorkeur aan acties met weinig informatie

Een exploratiefunctie kan een bonus aan een waardeschatting toevoegen. Kies bij $f(u,n)=u+k\mathrm{/}n$ voor een uitgeprobeerde actie de actie met de hoogste score. Geef niet-geprobeerde acties voorrang, bijvoorbeeld met score $+\mathrm{\infty }$. Bij $k=10$ scoort een waarde van 5 die 20 keer is geprobeerd 5,5; een waarde van 4 die twee keer is geprobeerd scoort 9. De minder vaak geprobeerd​​e actie wordt gekozen ondanks de lagere huidige schatting.

De bonus kan ook in een actualisatiedoelwaarde komen: $r+\gamma {\max }_{a^{\mathrm{\prime }}}f(Q(s^{\mathrm{\prime }},a^{\mathrm{\prime }}),N(s^{\mathrm{\prime }},a^{\mathrm{\prime }}))$. Dit laat de aantrekkelijkheid van niet-geëxploreerde acties doorwerken naar eerdere toestanden. Optimistische initiële Q-waarden kunnen ook aanmoedigen om acties te proberen waarvan de schattingen nog niet door ervaring zijn gecorrigeerd.

Gebruik een betrouwbaarheidsgrens voor bandieten

Een meerarmige bandiet heeft één beslissingstoestand en meerdere armen met onbekende vaste gemiddelde beloningen. Elke trekking leert de agent iets over de beloningsverdeling van een arm. UCB1 gaat uit van begrensde onafhankelijke trekkingen van beloningen met een vaste verdeling per arm; herschaal beloningen naar het bereik van 0 tot 1. Trek één keer aan elke arm en kies daarna de hoogste score

Hier is ${\bar{x}}_j$ het steekproefgemiddelde van arm $j$, $n_j$ het aantal trekkingen van die arm en $N$ het totale aantal over alle armen. De bonus groeit voor armen waarvan weinig steekproeven zijn genomen. Bij gemiddelden van 0,6 en 0,5 na 10 en 2 trekkingen is $N=12$. De scores zijn ongeveer 1,30 en 2,08, dus wordt de tweede arm gekozen. De score kan hoger zijn dan 1, ook al kunnen waargenomen beloningen dat niet: het is een beslissingsindex, geen waargenomen beloning.

Meet de kosten van leren

Cumulatief beloningsverlies vergelijkt de verzamelde beloning met wat optimale keuzes zouden hebben opgeleverd. Bij een stationaire bandiet met een werkelijk slechtere arm blijft een vaste positieve epsilon die arm met een positieve frequentie kiezen, wat lineair verwacht cumulatief beloningsverlies oplevert. Onder de aannamen voor stochastische bandieten heeft UCB1 logaritmisch verwacht cumulatief beloningsverlies. Een zorgvuldig afgestemd schema met afnemende epsilon kan ook die orde bereiken; een willekeurige afname kan dat niet garanderen.

De doelwaarde van Q-leren voor een afwijkend beleid laat explorerende steekproeven toe zonder de optimale waarden die het zoekt opnieuw te definiëren. Exploratie beïnvloedt nog steeds de beloning die tijdens de training wordt verzameld. Gebruik bij fysieke systemen simulatie, vastgelegde ervaring of beperkingen op toegestane acties om schade door exploratie te voorkomen.

Een Q-tabel slaat voor elk toestand-actiepaar één getal op. Bij een groot probleem worden veel paren mogelijk nooit bezocht. Afzonderlijke invoeren delen bovendien geen informatie tussen vergelijkbare situaties. Benaderend Q-leren vervangt de tabel door een functie van kenmerken.

Geef waarden weer met een gewogen som

Een kenmerk $f_i(s,a)$ is een getal dat een aspect van de toestand en actie beschrijft. Voor een bezorgrobot kunnen kenmerken het accuniveau, de afstand tot een oplader en wachtende pakketten beschrijven. Een lineaire benadering schrijft

De gewichten $w_i$ beschrijven hoe sterk elk kenmerk bijdraagt. Kenmerken kunnen zowel van de actie als van de toestand afhangen, zodat verschillende keuzes in dezelfde toestand verschillende waarden kunnen hebben.

Actualiseer elk gewicht met één fout

Bereken de huidige Q-waarde en daarna de doelwaarde $y=r+\gamma {\max }_{a^{\mathrm{\prime }}}Q(s^{\mathrm{\prime }},a^{\mathrm{\prime }})$. Het verschil $\delta =y-Q(s,a)$ stuurt elke actualisatie:

Alle waarden die voor de doelwaarde en de fout worden gebruikt, komen uit de gewichten van vóór de actualisatie. Een kenmerk met waarde nul verandert zijn gewicht niet. Een kenmerk ongelijk aan nul schaalt de aanpassing, inclusief het teken.

Voor gewichten $(1;-\mathrm{0,5})$ en huidige kenmerken $(1,2)$ is de schatting $1(1)+(-\mathrm{0,5})(2)=0$. Stel dat de beloning 4 is, de beste volgende Q-waarde 4 en $\gamma =\mathrm{0,9}$. De doelwaarde is $4+\mathrm{0,9}(4)=\mathrm{7,6}$, dus $\delta =\mathrm{7,6}$. Met $\alpha =\mathrm{0,1}$:

De nieuwe schatting voor dezelfde kenmerken wordt $\mathrm{1,76}+\mathrm{1,02}(2)=\mathrm{3,8}$. Een actualisatie van gedeelde gewichten is niet hetzelfde als één onafhankelijke tabelinvoer door de doelwaarde vervangen.

Begrijp het bereik en de grenzen van delen

Eén gewicht neemt deel aan veel voorspellingen. Als je het actualiseert, veranderen de waarden voor elk paar met een waarde ongelijk aan nul voor dat kenmerk. Dit is generalisatie en kan de agent helpen verstandig te handelen in ongeziene toestanden. Het kan ook een foutieve actualisatie verspreiden.

Als twee situaties voor elke overeenkomstige actie identieke kenmerkvectoren hebben, moet het model ze identieke actiewaarden geven. Als ze verschillende acties vereisen, kan geen enkele afstemming van gewichten beide beslissingen correct weergeven. Daarvoor zijn betere kenmerken of een rijkere functie nodig. Leren met een tabel is het speciale geval met één indicatorkenmerk voor elk toestand-actiepaar, dat alleen voor dat paar actief is.

De convergentiegarantie voor Q-leren met een tabel geldt niet voor willekeurige functiebenadering. Bootstrapping voor een afwijkend doelbeleid met gedeelde voorspellingen kan schommelen of divergeren, dus evalueer het geleerde beleid in afzonderlijke proeven. Diepe Q-netwerken leren kenmerken uit invoer zoals pixels van een spelscherm; zoeken in de beleidsruimte past daarentegen rechtstreeks een beleid aan om de cumulatieve beloning te verhogen.