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 höger|miniatyr|250x250px|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, , en mängd av handlingar, , som agenten kan utföra, övergångssannolikheter , d.v.s. sannolikheten att gå från tillstånd till tillstånd vid handling , för varje kombination av tillståndspar och handling, omedelbar belöning , d.v.s. den erhållna belöningen vid en övergång från till efter handling , 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 erhåller agenten en observation som i regel inkluderar belöningen . Därefter väljer agenten en handling från mängden av tillgängliga handlingar, vilken sedan skickas till miljön. Miljön förändras till ett nytt tillstånd och belöningen kopplad till övergången 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 -giriga algoritmen (eng. epsilon-greedy), där är en parameter som styr mängden utforskande relativt mängden utnyttjande. Med sannolikheten 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 , 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:
Policyfunktionen ger sannolikheten för att utföra handling då man befinner sig i tillstånd . Som specialfall kan man ha en deterministisk (icke-stokastisk) policy.
Tillståndsvärdefunktion Värdefunktionen definieras som den förväntade avkastningen då man startar i tillstånd , d.v.s. , och därefter följer policyn . 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.
där den stokastiska variabeln betecknar avkastningen (eng. return), vilken definieras som summan av framtida reducerade belöningar
där är belöningen i steg och ä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 som
där står för avkastningen som erhålls då följs från begynnelsetillståndet . Vi definierar som det största möjliga värdet på , där får lov att ändras,
Ä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 , en handling och en policy så är definieras handlingsvärdet av paret för policyn som
där nu står för den slumpmässiga avkastningen som erhålls då man först utför handling i tillstånd och därefter följer .
Teorin för Markovbeslutsprocesser säger att ifall är en optimal policy så agerar vi optimalt (väljer den optimala handlingen) genom att i tillstånd välja den handling från som har störst värde. Handlingsvärdefunktionen för en sådan optimal policy () kallas den optimala handlingsvärdefunktionen och brukar betecknas med . Sammanfattningsvis är det tillräckligt att endast känna till handlingsvärdefunktionen för att avgöra hur man agerar optimalt.