Förstärkningsinlärning

Förstärkningsinlärning (eng. reinforcement learning) är ett område inom maskininlärning som behandlar hur en mjukvaruagent bör agera för att maximera någon typ av sammanräknad belöning. Förstärkningsinlärning är en av tre grundläggande paradigmer inom maskininlärning, tillsammans med vägledd inlärning (eng. supervised learning) och ickevägledd inlärning (eng. unsupervised learning).

Tillvägagångssättet skiljer sig från vägledd maskininlärning genom att man inte behöver tillhandahålla märkt data, d.v.s. data som för varje indatapunkt innehåller en utdatapunkt som används för att träna algoritmen att förutse korrekt utdata då den matas med ny indata. En annan skillnad är att suboptimalt agerande inte behöver korrigeras explicit. Istället ligger fokus på att hitta en balans mellan utforskning (av outforskat territorium) och utnyttjande (av aktuell kunskap).

Miljön beskrivs typiskt i form av en markovbeslutsprocess (eng. Markov decision process, MDP) eftersom många förstärkningsinlärningsalgoritmer utnyttjar metoder från dynamisk programmering. Den huvudsakliga skillnaden mellan klassiska metoder baserade på dynamisk programmering och förstärkningsinlärningsalgoritmer är att de senare inte antar att en exakt matematisk modell av MDP:n är känd, samt att de riktar sig mot stora MDP:er för vilka exakta metoder blir otillämpbara.

Inledning

Den typiska formuleringen av ett förstärkningsinlärningsscenario: en agent utför handlingar i en miljö, vilket leder till ett nytt tillstånd, och vars konsekvenser kvantifieras i form av en belöning. Tillståndet och belöningen matas sedan tillbaka till agenten och kan utnyttjas för beslut om framtida handlingar.

Till följd av sin generalitet studeras förstärkningsinlärning inom många andra discipliner, såsom spelteori, självkörande bilar, människors upp- och nedröstning av chattbotars svar, reglerteori, operationsanalys, informationsteori, simuleringsbaserad optimering, multiagentsystem, svärmintelligens, statistik, samt genetiska algoritmer. I operationsanalys- och reglertekniklitteratur kallas förstärkningsinlärning approximativ dynamisk programmering eller neurodynamisk programmering. De problem som är av intresse i förstärkningsinlärning har också studerats inom teorin för optimal reglering. Denna teori fokuserar huvudsakligen på att undersöka existensen av och att karaktärisera optimala lösningar, samt algoritmer för exakt beräkning av dessa, och mindre på inlärning och approximering, speciellt vid avsaknad av en matematisk modell för miljön. Inom ekonomi och spelteori kan förstärkningsinlärning användas för att förklara hur jämvikt kan uppstå vid begränsad rationalitet.

Grundläggande förstärkningsinlärning modelleras som en markovbeslutsprocess med följande komponenter:

• en mängd av tillstånd för miljön och agenten, S,
• en mängd av handlingar, A, som agenten kan utföra,
• övergångssannolikheter $P_{a}(s,s')=\Pr(s_{t+1}=s'\mid s_{t}=s,a_{t}=a)$, d.v.s. sannolikheten att gå från tillstånd $s$ till tillstånd $s'$ vid handling $a$, för varje kombination av tillståndspar och handling,
• omedelbar belöning $R_{a}(s,s')$, d.v.s. den erhållna belöningen vid en övergång från $s$ till $s'$ efter handling $a$,
• regler som beskriver vad agenten observerar.

Reglerna är ofta stokastiska. Observationen involverar typiskt den skalära omedelbara belöningen kopplad till den senaste övergången. I många arbeten antar man att agenten kan observera det aktuella miljötillståndet (fullständig observerbarhet). I annat fall har agenten ofullständig (eller partiell) observerbarhet. Mängden av handlingar kan ibland vara begränsad.

En förstärkningsinlärningsagent interagerar med sin miljö i diskreta tidssteg. Vid varje tidpunkt t erhåller agenten en observation $o_{t}$ som i regel inkluderar belöningen $r_{t}$. Därefter väljer agenten en handling $a_{t}$ från mängden av tillgängliga handlingar, vilken sedan skickas till miljön. Miljön förändras till ett nytt tillstånd $s_{t+1}$ och belöningen $r_{t+1}$ kopplad till övergången $(s_{t},a_{t},s_{t+1})$ bestäms. Målet för förstärkningsinlärningsagenten är att samla så stor sammanlagd belöning som möjligt. Agenten kan välja sina handlingar (eventuellt slumpmässigt) som en funktion av historien, d.v.s. tidigare observationer. Funktionen enligt vilken agenten väljer sin nästa handling baserat på det aktuella tillståndet och den aktuella kunskapen om miljön kallas för en policy.

Skillnaden mellan agentens sammanlagda belöning givet en viss policy och den sammanlagda belöningen vid en optimal policy (d.v.s. en policy som maximerar den sammanlagda belöningen) kallas på engelska regret. För att välja en policy som leder till nära optimalt agerande så måste agenten resonera om de långsiktiga konsekvenserna av dess handlingar (d.v.s. maximera den framtida vinsten). Detta kan leda till att agenten väljer handlingar som riskerar att ge en låg omedelbar belöning, men som tros leda till kunskap som kan användas för att få större framtida belöningar (som kompenserar för den låga omedelbara belöningen).

Förstärkningsinlärning är således väl lämpat för problem som involverar en avvägning mellan långsiktiga och kortsiktiga belöningar. Metodiken har framgångsrikt tillämpats på vitt skilda problem, såsom robotreglering, schemaläggning för hissar, telekommunikation, backgammon, damspel och brädspelet Go (AlphaGo).

Det finns två element som gör förstärkningsinlärning kraftfullt: användningen av sampling för att optimera prestandan, samt användningen av funktionsapproximering för att hantera stora miljöer. Tack vare dessa nyckelkomponenter kan förstärkningsinlärning användas i stora miljöer i följande situationer:

• då en modell för miljön är känd men ingen analytisk lösning finns att tillgå,
• då endast en simuleringsmodell för miljön är tillgänglig (det fall som behandlas i simuleringsbaserad optimering),
• då det enda sättet att samla information om miljön är att interagera med den.

De två första av dessa problem skulle kunna ses som planeringsproblem (eftersom någon form av modell är tillgänglig), medan det sista kan ses som ett rent inlärningsproblem. Förstärkningsinlärning behandlar emellertid även de båda planeringsproblemen som maskininlärningsproblem.

Utforskning

Avvägningen mellan att utforska och att utnyttja har studerats mest ingående för problemet med flerarmade banditer och för markovbeslutsprocesser (MDP:er) med ändliga tillståndsrum i Burnetas och Katehakis (1997).

Förstärkningsinlärning kräver noggrant uttänkta utforskningsmekanismer. Att välja handlingar slumpmässigt, utan att ta hänsyn till skattade sannolikhetsfördelningar, leder till dålig prestanda. Fallet med en (liten) ändlig markovbeslutsprocess är relativt väl förstått. Eftersom det saknas algoritmer som skalar väl med antalet tillstånd (eller skalar till problem med oändliga tillståndsrum), är emellertid enkla utforskningsmetoder mest praktiska.

En sådan metod är den $\epsilon$-giriga algoritmen (eng. epsilon-greedy), där $0<\epsilon <1$ är en parameter som styr mängden utforskande relativt mängden utnyttjande. Med sannolikheten $1-\epsilon$ väljer agenten att utnyttja, vilket innebär att agenten utnyttjar sin aktuella kunskap för att välja den handling som tros leda till störst sammanlagd belöning på lång sikt (ifall flera likvärdiga handlingar finns så väljs en av dem slumpmässigt). I annat fall, med sannolikhet $\epsilon$, väljer agenten att utforska, och handlingen väljs då slumpmässigt med likformig sannolikhetsfördelning.

Algoritmer för policyinlärning

Även om man bortser från utforskningsproblemet och även ifall tillståndet är observerbart (vilket hädanefter antas) så återstår problemet att utnyttja tidigare erfarenheter för att bestämma fördelaktiga handlingar.

Optimalitetskriterium

Policy

Agentens val av handling modelleras som en funktion som kallas för policy:

$\pi :A\times S\rightarrow [0,1]$

$\pi (a,s)=\Pr(a_{t}=a\mid s_{t}=s)$

Policyfunktionen ger sannolikheten för att utföra handling $a$ då man befinner sig i tillstånd $s$. Som specialfall kan man ha en deterministisk (icke-stokastisk) policy.

Tillståndsvärdefunktion

Värdefunktionen $V_{\pi }(s)$ definieras som den förväntade avkastningen då man startar i tillstånd $s$, d.v.s. $s_{0}=s$, och därefter följer policyn $\pi$. Man kan alltså i princip säga att värdefunktionen ger en skattning av "hur bra" det är att vara i ett visst tillstånd.

$V_{\pi }(s)=\operatorname {E} [R]=\operatorname {E} \left[\sum _{t=0}^{\infty }\gamma ^{t}r_{t}\mid s_{0}=s\right],$

där den stokastiska variabeln $R$ betecknar avkastningen (eng. return), vilken definieras som summan av framtida reducerade belöningar

$R=\sum _{t=0}^{\infty }\gamma ^{t}r_{t},$

där $r_{t}$ är belöningen i steg $t$ och $\gamma \in [0,1]$ är reduktionsfaktorn. Reduktionsfaktorn är en designparameter som avgör hur högt framtida belöningar viktas relativt belöningar i närtid. Ifall faktorn är nära 0 så optimerar man främst belöningar i närtid, medan en faktor nära 1 (t.ex. 0.999), värderar förväntade belöningar långt fram i tiden nästan lika högt som belöningar i närtid.

Algoritmens mål är att hitta en policy som maximerar den förväntade avkastningen. Från teorin för markovbeslutsprocesser (MDP:er) är det känt att policysökningen kan begränsas till mängden av så kallade stationära policyer. En policy är stationär ifall handlingsfördelningen som den returnerar bara beror på det senast besökta tillståndet (från agentens observationshistoria). Sökningen kan vidare inskränkas till deterministiska stationära policyer. En deterministisk stationär policy bestämmer handlingar deterministiskt baserat på det aktuella tillståndet. Eftersom varje sådan policy kan beskrivas som en avbildning från tillståndsmängden till handlingsmängden så kan dessa policyer identifieras med sådana avbildningar utan minskad generalitet.

Totalsökning (brute force)

Totalsökningsmetoden består av två steg:

• För varje möjlig policy, följ policyn och beräkna resulterande avkastningar (detta utgör en sampling av avkastningen)
• Välj den policy som har störst förväntad avkastning

Ett problem med denna metod är att antalet policyer kan vara stort eller till och med oändligt. Ett annat problem är att variansen för avkastningen kan vara stor, vilket gör att man måste sampla många gånger för att kunna ge en noggrann skattning av avkastningen från varje policy.

Dessa problem kan mildras ifall vi antar en viss struktur och tillåter sampel som genererats av en viss policy att påverka skattningarna även för andra policyer. De två huvudsakliga tillvägagångssätten för att åstadkomma detta är värdefunktionsskattning och direkt policysökning.

Värdefunktion

Värdefunktionsmetoder försöker hitta en policy som maximerar avkastningen genom att spara en mängd skattningar av förväntade avkastningar för någon policy (vanligtvis antingen den aktuella eller optimala policyn).

Dessa metoder bygger på teorin för Markovbeslutsprocesser, där optimalitet definieras i en starkare mening än den beskriven ovan: En policy kallas optimal ifall den åstadkommer den högsta förväntade avkastningen från vilket begynnelsetillstånd som helst (d.v.s. initiala fördelningar spelar ingen roll i denna definition). Återigen kan en optimal policy alltid hittas bland stationära policyer.

För att ge en formell definition av optimalitet så definierar vi värdefunktionen för en policy $\pi$ som

$V^{\pi }(s)=E[R\mid s,\pi ],$

där $R$ står för avkastningen som erhålls då $\pi$ följs från begynnelsetillståndet $s$. Vi definierar $V^{*}(s)$ som det största möjliga värdet på $V^{\pi }(s)$, där $\pi$ får lov att ändras,

$V^{*}(s)=\max _{\pi }V^{\pi }(s).$

Även om värdefunktionen är tillräcklig för att definiera optimalitet är det också användbart att definiera handlingsvärden. Givet ett tillstånd $s$, en handling $a$ och en policy $\pi$ så är definieras handlingsvärdet av paret $(s,a)$ för policyn $\pi$ som

$Q^{\pi }(s,a)=\operatorname {E} [R\mid s,a,\pi ],\,$

där $R$ nu står för den slumpmässiga avkastningen som erhålls då man först utför handling $a$ i tillstånd $s$ och därefter följer $\pi$.

Teorin för Markovbeslutsprocesser säger att ifall $\pi ^{*}$ är en optimal policy så agerar vi optimalt (väljer den optimala handlingen) genom att i tillstånd $s$ välja den handling från $Q^{\pi ^{*}}(s,\cdot )$ som har störst värde. Handlingsvärdefunktionen för en sådan optimal policy ($Q^{\pi ^{*}}$) kallas den optimala handlingsvärdefunktionen och brukar betecknas med $Q^{*}$. Sammanfattningsvis är det tillräckligt att endast känna till handlingsvärdefunktionen för att avgöra hur man agerar optimalt.

Om man antar att Markovbeslutsprocessen är helt känd så finns det två grundläggande tillvägagångssätt för att beräkna den optimala handlingsvärdefunktionen: värdeiterering och policyiterering. Båda algoritmerna beräknar en följd av funktioner $Q_{k}$ ($k=0,1,2,\ldots$) som konvergerar mot $Q^{*}$. Vid beräkning av dessa funktioner måste man beräkna väntevärden för hela tillståndsrummet, vilket är opraktiskt förutom för små (ändliga) Markovbeslutsprocesser. I förstärkningsinlärningsmetoder approximerar man väntevärden genom att beräkna medelvärden över sampel och använda funktionsapproximationstekniker för att kunna representera värdefunktioner för stora tillståndshandlingsrum.

Monte Carlo-metoder

Monte Carlo-metoder kan användas för algoritmer som imiterar policyiterering. Policyitering består av två steg: policyutvärdering och policyförbättring.

Monte Carlo-metoder används för policyutvärderingssteget. I detta steg är vi givna en stationär deterministisk policy $\pi$ och målet är att beräkna handlingsvärdena $Q^{\pi }(s,a)$ (eller en bra approximation av dessa) för alla par av tillstånd och handlingar $(s,a)$. Vi antar (för enkelhets skull) att Markovbeslutsprocessen är ändlig, att tillräckligt minne finns tillgängligt för att lagra handlingsvärdena samt att problemet är episodiskt och att efter varje episod så startar en ny från ett slumpmässigt begynnelsevärde. Då kan skattningen av värdet av ett visst par av tillstånd och handling $(s,a)$ beräknas genom att räkna ut medelvärdet över tid av de samplade avkastningarna med ursprung i $(s,a)$. Efter tillräckligt lång tid kan denna procedur alltså ge en precis skattning $Q$ av handlingsvärdefunktionen $Q^{\pi }$. Detta avslutar beskrivningen av policyutvärderingssteget.

I policyförbättringssteget erhålls nästa policy genom att beräkna en girig policy med avseende på $Q$: Givet ett tillstånd $s$ så returnerar denna policy en handling som maximerar $Q(s,\cdot )$. I praktiken kan lat evaluering skjuta upp beräkningen av de maximerande handlingarna tills de behövs.

Några problem med denna procedur är:

• Proceduren kan lägga för mycket tid på att utvärdera en suboptimal policy.
• Den utnyttjar sampel ineffektivt genom att en lång bana bara leder till en förbättrad skattning för det enda par av tillstånd och handling som inledde banan.
• När avkastningarna längs banorna har hög varians så är konvergensen långsam.
• Den fungerar bara för episodiska problem.
• Den fungerar bara för små ändliga Markovbeslutsprocesser.

Tidsskillnadsmetoder

Det första problemet löses genom att man tillåter proceduren att ändra policy (för något eller alla tillstånd) innan värdena är exakt bestämda. Detta kan också vara problematiskt eftersom det kan förhindra konvergens. De flesta aktuella algoritmer gör detta, vilket leder till en klass av generaliserade policyiterationsalgoritmer. Många aktör-kritiker-metoder tillhör denna kategori.

Det andra problemet kan lösas genom att tillåta banor att bidra till värdeberäkningen för alla par av tillstånd och värden som förekommer i banan. Detta kan också i viss utsträckning mildra det tredje problemet, men en bättre lösning när avkastningen har hög varians är att använda Suttons tidsskillnadsmetoder (temporal difference methods, TD) som bygger på den rekursiva Bellmanekvationen. Beräkningen i TD-metoder kan göras inkrementellt (efter övergången ändras minnet och övergången kastas bort) eller ihop (när övergångerna hopas och skattningarna beräknas en gång baserat på hopen). Hopmetoder, som minsta kvadrat-tidsskillnadsmetoden kan utnyttja information i samplen bättre medan inkrementella metoder är det enda valet när hopmetoder är oapplicerbara på grund av deras höga beräknings- eller minneskomplexitet. Vissa metoder försöker kombinera de två tillvägagångssätten. Metoder som baseras på tidsskillnader löser även det fjärde problemet.

För att hantera det femte problemet används funktionsapproximeringsmetoder. Linjär funktionsapproximering börjar med en avbildning $\phi$ som till varje par av tillstånd och handling tilldelar en ändligtdimensionell vektor. Handlingsvärdena för ett par av tillstånd och handling $(s,a)$ erhålls sedan genom att linjärt kombinera komponenterna av $\phi (s,a)$ med några vikter $\theta$:

$Q(s,a)=\sum _{i=1}^{d}\theta _{i}\phi _{i}(s,a).$

Algoritmerna justerar sedan vikterna, istället för att justera värdena kopplade till de enskilda paren av tillstånd och handling.

Värdeiteration kan också användas som startpunkt, vilket ger upphov till Q-inlärningsalgoritmen och dess många varianter.

Problemet med att använda handlingsvärden är att det kan behövas väldigt exakta skattningar av konkurrerande handlingsvärden, vilket kan vara svårt att erhålla ifall avkastningarna är brusiga. Detta problemet mildras dock i viss utsträckning med tidsskillnadsmetoder. Att använda den så kallade kompatibla funktionsapproximationsmetoden kompromissar generalitet och effektivitet. Ett annat problem som är specifikt för TD-metoder kommer från att de förlitar sig på den rekursiva Bellmanekvationen. De flesta TD-metoder har en så kallad $\lambda$-parameter $(0\leq \lambda \leq 1)$ som tillåter kontinuerlig interpolering mellan Monte Carlo-metoder som inte bygger på Bellmanekvationer och de grundläggande TD-metoderna som helt bygger på Bellmanekvationer. Detta kan vara effektivt för att lindra detta problem.

Direkt policysökning

En alternativ metod är att direkt söka en policy i (någon delmängd av) policyrummet. I detta fall blir problemet ett fall av stokastisk optimering. De två tillvägagångssätt som finns tillgängliga är gradientbaserade och gradientfria metoder.

Gradientbaserade metoder (policygradientmetoder) börjar med en avbildning från en ändligtdimensionell (parameter)rymd till policyrummet: givet parametervektorn $\theta$, låt $\pi _{\theta }$ beteckna policyn associerad med $\theta$. Prestandafunktionen definieras som

$\rho (\theta )=\rho ^{\pi _{\theta }}$.

Under milda antaganden är denna funktion deriverbar som en funktion av parametervektorn $\theta$. Om gradienten för $\rho$ vore känd så skulle man kunna använda gradientstigningsmetoden. Eftersom inget analytiskt uttryck för gradienten är tillgängligt har vi bara en brusig skattning att tillgå. En sådan skattning kan konstrueras på många sätt, vilket ger upphov till algoritmer såsom Williams REINFORCE metod (vilken är känd som sannolikhetsförhållandemetoden i litteratur om simuleringsbaserad optimering). Policysökningsmetoder har använts i robotiksammanhang. Många policysökningsmetoder kan fastna i lokala optima (eftersom de bygger på lokal sökning).

En stor klass av metoder undviker att förlita sig på gradientinformation. Dessa innefattar simulerad glödgning, korsentropisökning eller metoder från evolutionär beräkning. Många gradientfria metoder kan (i teorin eller i gränsövergången) uppnå globalt optimum.

Policysökningsmetoder kan konvergera långsamt givet brusig data. Detta händer till exempel i episodiska problem när banorna är långa och avkastningsvariansen är stor. Värdefunktionsbaserade metoder som bygger på tidsskillnader kan hjälpa i detta fall. Under senare år har aktör-kritiker-metoder föreslagits och presterat väl på diverse problem.