Indargarri bidezko ikaskuntza

eskuinera|thumb|250x250px| Ikaskuntza indartuko (IA) agertoki baten irudikapen tipikoa: agente batek ingurune batean hartzen ditu ekintzak, eta ingurune horretatik sari bat eta egoeraren irudikapen bat interpretatuko da, eta ekintza horiek eragileari elikatzen zaizkio.axiim
**Indargarri bidezko ikaskuntza** edo **ikaskuntza indartua** (ingelesez: *reinforcement learning*) ikaskuntza automatikoaren (AA) arlo bat da, psikologia konduktistan inspiratua. Haren zeregina software-agente batek ingurune jakin batean aukeratuko dituen ekintzak zehaztea da, "sari" edo irabazi metatu bat maximizatzeko helburuarekin. Arazoa orokorra denez, beste diziplina askotan aztertzen da, hala nola joko-teoria, kontrolaren teoria, ikerkuntza eragilea, informazio-teoria, simulazioetan oinarritutako optimizazioa, estatistika eta algoritmo genetikoak. Beste ikerketa-eremu batzuetan, non indargarri bidezko ikaskuntzako metodoak aztertzen diren, *programazio dinamiko gerturatua* esaten zaio. Arazoa kontrol optimoaren teorian aztertu da, baina ikerketa gehienak soluzio optimoen existentzian eta horien karakterizazioan zentratzen dira, ez ikasketa edo hurbilketa alderdietan. Ekonomian eta joko-teorian, indargarri bidezko ikaskuntza erabil daiteke arrazionaltasun mugatuko baldintzetan oreka nola sor daitekeen azaltzeko. Makinaren ikaskuntzan, ingurumena Markoven erabaki-prozesu (MDP) gisa formulatzen da normalean, eta indargarri bidezko ikasketako algoritmo askok lotura estua dute programazio dinamikoko teknikekin. Teknika klasikoen eta indargarri bidezko ikaskuntzako algoritmoen arteko alde nagusia da azken horietan ez dela beharrezkoa MDPak ezagutzea, eta MDP handietara zuzentzen direla, non metodo zehatzak ez-bideragarri bihurtzen diren. Indargarri bidezko ikaskuntza ez dator bat ikasketa gainbegiratuaren estandarrarekin, non sarrera / irteera pare zuzenak ez diren inoiz agertzen, eta ekintza suboptimoak ez diren esplizituki zuzentzen. Gainera, lineako errendimenduan ikuspegi bat dago, esplorazioaren (lurralde ezezagunena) eta explotazioaren (oraingo ezagunena) arteko oreka aurkitzea dela helburu.

## Sarrera 
Indargarri bidezko ikaskuntzaren oinarrizko eredua honakoa da:

# Inguruneko egoeren S multzo bat;
# Ekintzen A multzo bat;
# Egoeren arteko trantsizioaren arauak;
# Trantsizio baten *berehalako saria* zehazten duten arauak;
# Agenteak sumatzen duena deskribatzen duten arauak.

Arauak estokastikoak dira askotan. Behaketak, normalean, azken trantsizioarekin lotutako berehalako saria esan nahi du. Ereduetan, agenteak pentsatuko du ingurunearen egungo egoera osoa behatzen duela; kasu horretan, erabateko behagarritasunaz hitz egiten da, eta, kontrako kasuetan, berriz, partzialki *behagarritasunaz;* adibidez, xake partida batean agentea bere inguruneko osagai guztitaz ageri da, baina karta partida batean, agenteak ez daki bere etsaiek zein karta dituzten. Batzuetan, agentearentzat eskuragarri dauden ekintza batzuk mugatuta daude; adibidez, ezin dugu gastatu duguna baino diru gehiago gastatu. Ikaskuntza indartuko agente batek bere ingurunearekin denbora-pauso diskretuetan elkarreragingo du. Agenteak t denbora-tarte bakoitzean o_t behaketa bat jasotzen du, normalean r_t saria barne edukiko duena. Orduan, ekintza-multzoko a_t ekintza bat aukeratzen da, eta, ondoren, ingurunera bidaltzen da. s_{t+1} egoera berri batera mugitzen da ingurunea, eta (s_t,a_t,s_{t+1})trantsizioarekin lotutako r_{t+1} saria zehaztu egiten da. Indargarri bidezko ikaskuntzako agente baten helburua ahalik eta sari gehien jasotzea da. Agenteak edozein ekintza aukeratu dezake bere ekintza istorioaren arabera, eta ausaz ere egin dezake bere ekintzen hautaketa. Agentearen errendimendua hasiera-hasieratik modu optimoan jarduten duen agente batenarekin alderatzen denean, agente horien arteko aldeak *damua*ren nozioa sortzen du. Kontuan izan behar da, era optimoan jardun ahal izateko, agenteak bere ekintzen epe luzerako ondorioei buruz arrazoitu behar duela: «etorkizuneko diru-sarrerak maximizatzeko asmoz, hobe litzateke eskolara orain joatea, ekintza horrekin lortutako  diru-sarrera negatiboa izan daitekeen arren». Beraz, indargarri bidezko ikaskuntza bereziki egokia da epe luzeko eta epe laburreko arrazoiketak barne hartzen dituzten arazoetarako. Arrakastaz aplikatu da hainbat arazotan, besteak beste, robot-en kontrolean, telekomunikazioetan, backgammon-en eta dametan. Bi osagaik egiten dute indargarri bideko ikaskuntza irismen handikoa: laginen erabilera errendimendua optimizatzeko eta hurbiltze-funtzioaren erabilera tamaina handiko inguruneei aurre egiteko. Funtsezko bi osagai horiei esker, indargarri bidezko ikaskuntza tamaina handiko inguruneetan erabil daiteke, ondorengo ingurune edozeinetan:

* Ingurunearen eredua ezaguna da, baina soluzio analitiko bat ez dago eskuragarri;
* Ingurunearen simulazio-eredu bakarra ematen da (simulazioan oinarritutako optimizazioaren gaia);
* Inguruneari buruzko informazioa biltzeko modu bakarra harekin elkarrekintzan aritzea da.

Lehenengo bi inguruneak plangintza-problematzat har daitezke (moduren batean edo bestean, eredua eskuragarri badago), eta azkena, berriz, ikaskuntza klasikoko problematzat. Hala ere, indargarri bidezko ikaskuntza metodologiaren menpean, plangintza-arazoak ikasketa automatikoko (AA) arazo bihurtzen dira.

## Esplorazioa 
Ikaskuntza indartuaren arazoa, deskribatu den bezala, esplorazio adimenduneko mekanismoak eskatzen dituela da. Ekintzak ausaz hautatzeak, ezagutzen den probabilitate-banaketa estimatu bat oinarri gisa erabili gabe, oso errendimendu eskasa ematen du. MDP (txiki) finituen kasua nahiko ondo ulertzen da oraingoz. Hala ere, egoera kopuruarekin ondo eskalatzen duten algoritmorik ez dagoenez, praktikan jendeak esplorazio metodo sinpleetara jotzen du. Metodo horietako bat \epsilon-greedy deiturikoa da, agenteak epe luzerako irabazi onena duen ekintza aukeratuko du 1-\epsilon probabilitate batekin, eta, bestalde, \epsilon probabiltateariekin, uniformeki ausazkoa den ekintza bat aukeratuko du. Hemen, 0 balioa doikuntza parametro bat da, batzuetan aldatu egiten dena, bai ordutegi finko baten arabera (beraz, agenteak gutxiago esploratuko du denbora pasatzen joaten den bitartean), bai modu moldakor batean, heuristiko batzuetan oinarrituta (Tokic eta Palma, 2011).

## Ikaskuntza kontrolatzeko algoritmoak 
Esplorazioaren gaia kontuan hartuta, eta egoera behagarria izanda ere (hemendik aurrera asumituko duguna), zain ekintza hartu iraganean edukitako esperientzien arabera da oraindik gure arazo nagusia, honetarako, hainbat algoritmo proposatu dira arazoari soluzioa emateko:

### Optimotasun-irizpidea 
Sinplifikatzeko, esango dugu aztertzen ari garen arazoa egoerakakoa dela, egoera terminal batera iristean amaituko dena. Demagun, gainera, agenteak egiten dituen ekintzak ez diotela axola, egoera terminal batean bei bukatuko duela. Erregulartasun gehigarriko baldintza jakin batzuetan, ongi definituta dago sari osoaren itxaropena edozein politikarentzat eta egoeren gaineko hasierako edozein banaketarentzat. Sentzu horretan, politika bat egoera posible guztiei ekintzen gaineko probabilitate-banaketa jakin bat esleitzea da. Beraz, hasierako \mu banaketa finkoa emanda,  espero dugun \rho^\pi itzulera eslei diezaiokegu \pi:\rho^\pi = E[R|\pi], politikari non zorizko R aldagaiak *irabazia* adierazten duen eta honela definitzen den:R=\sum_{t=0}^{N-1} r_{t+1},non  r_{t+1} t-garren pausoaren ondoren jasotako saria den tokian, hasierako egoera \mu banaketaren zorizko laginketa bidez egiten da eta ekintzak \pi politikak aukeratzen ditu. Hemen, N-k egoera terminal batera iristeko behar den  ausazko denbora adierazten du, hau da, arazoa amaitzen den unea. Episodikoak ez diren arazoen kasuan, itzulera *deskontatu* egiten da maiz honela: R=\sum_{t=0}^\infty \gamma^t r_{t+1},  eta honela deskontu totalerako espero den sariaren irizpidea sortzen da. 0 \le \gamma \le 1 balioari *deskontu-faktorea* deitzen zaio. Honek nahiko xaloa dirudien arren, deskontua arazo bat da lineako errendimenduaz arduratzen bazara. Izan ere, deskontuaren ondorioz, garrantzia hasierako urratsen denboran jartzen baita. Ikaskuntza-agente batek "bizitza" hasi ondorengo lehen urratsetan akatsak egin ditzakeenez, informaziorik gabeko ikaskuntza-algoritmo batek ezin du errendimendu optimorik lortu deskontuan, ezta inguruneen klasea PDM finituen klasera mugatuta badago ere. (Horrek ez du esan nahi, hala ere, denbora nahikoa emanik, ikaskuntzako agente batek ezin duela ikasi nola jokatu modu ia optimoan, denbora berrabiarazi bada). Orduan, arazoa da algoritmo bat zehaztea, eta algoritmo horrek espero den etekinik handiena duen politika bat aurkitzea. PDM-ren teoriatik badakigu, orokortasunik galdu gabe, politika *geldikor* deritzen multzora murriztu daitekeela. Politika bat *geldikor* deitzen da, itzultzen duen ekintza-banaketa bisitatutako azken egoeraren araberakoa bada (agentearen behaketaren historiaren zati bat dena, gure sinplifikazio honetan). Gainera, bilaketa are gehiago murritz daiteke politika *geldikor* determinista bada. Politika *geldikor* determinista egungo egoeran oinarritutako ekintzak modu deterministan aukeratzen dituena da.

### Indar gordina 
Indar gordin bidezko ikuspegiak bi etapa hauek ditu:

# Politika posible bakoitzerako, emaitzen laginketa egin.
# Irabazi handiena espero duen politikia hautatu.

Ikuspegi honen arazo bat da politika kopurua izugarri handia izan daitekeela, edo amaigabea ere bai. Beste kontu bat da errendimenduaren bariantza handia izan litekeela; kasu horretan, lagin kopuru handia behar da politika bakoitzaren itzulera zehaztasunez zenbatesteko. Arazo horiek arindu egin daitezke egituraren bat erabiliz, eta laginak politika batetik abiatuta sortzea ahalbidetu, beste batek egindako estimazioetan eragiteko. Hori lortzeko bi ikuspegi nagusiak balioaren funtzioen estimazioa eta politika zuzenen bilaketa dira.

### Balioaren funtzioen estimazioa 
Balio-funtzioak irabazia maximizatzen duen politika bat bilatzen saiatzen dira, politikaren batek espero dituen etekinen estimazio bat mantentzean (bai oraingo poltika, edo politika alternatibo bat). Metodo horiek PDM-en teorian oinarritzen dira, non optimotasuna aurrekoak baino indartsuagoa den zentzu batean definitzen den: Politika bat optimoa deitzen da edozein hasierako egoeratan espero den errendimendu hoberena lortzen bada (hau da, hasierako egoeren banaketek ez dute inolako zerikusirik definizio horretan). Aurretik esan bezala, politika *geldikorren* artean beti aurki daiteke politika optimoa. Optimotasuna modu formal batean definitzeko, \pipolitika baten balioa honela definitu behar da: V^{\pi} (s) = E[R|s,\pi], non R-k s hasierako egoeratik hurrengo egoerei lotutako ausazko irabazia esan nahi duen. V^*(s) balioa V^\pi(s)-k artu ahal duen balio maximo posible gisa definitzen da, non \pi politikari aldatzeko aukera ematen zaion: V^*(s) = \sup \limits_\pi V^{\pi}(s). Egoera bakoitzean balio optimo horiek lortzen dituen politikari *optimoa* deritzo. Balio funtzio bat ere ekintzen baitan kalkula daiteke: s egoera, a ekintza eta \pi politika emanda, (s,a) bikotearen balio-funtzioa \pi politikaren menpean honela definitzen da:Q^\pi(s,a) = E[R|s,a,\pi],\,non R balioak a ekintzak s egoeran itzuliko deun irabazia esan nahi duen. PDMen teoriatik abiatuta ezaguna da norbaitek politika optimorako Q ematen badigu, beti aukera dezakegula ekintza optimoak egoera bakoitzean Q balio altuena duen ekintza aukeratuz. Politika optimoaren *ekintza-balio funtzioari* ekintza-balio funtzio optimoa deitzen zaio, eta honela adierazten da: Q^*. MDP.a erabat ezagutzen dela jota, oinarrizko bi algoritmo daude balio optimoa kalkulatzeko: balio iterazioa eta politika iterazioa. Bi algoritmoek Q_k funtzioen (k=0,1,2,\ldots,) sekuentzia bat kalkulatzen dute, Q^* balioan bat egiten dutenak

#### MonteCarlo metodoa 
MonteCarlo Metodo sinpleenak iterazio politikak imitatzen dituen algoritmo batean erabil daitezke. Politika iterazioa bi fasez osatuta dago: ebaluazioa eta hobetzea. MonteCarlo Metodoak ebaluazio fasean erabiltzen dira. Fase honetan, π politika determinista estatikoa emanda, helburua Q^π (s,a) funtzioaren balioak (edo ongi hurbildutako balioa) kalkulatzea da estatu-ekintzako bikote guztientzat (s,a). Suposatuko dugu (sinpleago egiteko), MDP finitua dela eta egoeren arabera ekintzen taula memorian dagoela suposatuko dugu. Horrez gain, arazoa episodikoa dela suposatzen da, eta episodo bakoitzaren ondoren, episodio berri bat hasten da egoera hasierako aleatorio batetik. Beraz, (s,a) estatu-ekintzako bikote baten balioaren estimazioa (s,a), sor daiteken lagin errendimenduen batez bestekoa kalkulatuz lor daiteke. Denbora nahikoa emanda, prozedura honek Q ekintza-balio funtzioaren estimazio zehatza eraiki dezake. Hemen amaitzen da politikaren ebaluazio fasearen deskribapena. Politiken hobetze fasean, iterazio algoritmoan egiten den bezala, hurrengo politika Q araberako greedy politika bat erabiliz lortzen da: egoera s emanda, politika berri honek Q(s,⋅) maximizatzen duen ekintza bat itzultzen du. Praktikan, askotan, politika berriaren kalkulua eta biltegiratzea saihesten da, baina ekintzak maximizatzen dituztenak benetan kalkulatzea behar denean, ebaluazio nagia erabiltzen da. Prozedura honek honako arazo batzuk ekar ditzake:

* Politika suboptimo baten ebaluazioan denbora asko galdu daiteke;
* Laginen erabilera ez da eraginkorra;
* Ibilbideek bariantza handia dutenean, konbergentzia motelagoa izango da;
* Arazo episodikoetan bakarrik funtzionatzen du;
* MDP txiki eta finituetan bakarrik funtzionatzen du.

#### Denbora-aldeen metodoak 
Lehen arazoa erraz konpon daiteke, prozedurak politika aldatu ahal izatea baimenduz (egoera guztietan edo batzuetan) balioak ezarri aurretik. Onegia dirudien arren, arriskutsua izan daiteke, konbergentzia galaraz dezakeelako. Hala ere, egungo algoritmo gehienek ideia hori ezartzen dute, politika-iterazio orokortuaren algoritmo klaseari bide emanez. Pasadan ohartarazten gara, kritikoak diren aktore metodoak kategoria honetan sartzen direla. Bigarren arazoa algoritmoan konpon daiteke, ibilbideei estatuko-ekintzako bikote bakoitzari laguntzen uzten zaienean. Honek, neurri batean, hirugarren arazoari ere lagun diezaioke, nahiz eta errendimenduak bariantza handia dutenean, soluzio hobe bat Sutton-en denbora-diferentziaren (TD) metodoak erabiltzea izan daiteke, Bellman-en ekuazio errekurtsiboan oinarritzen dena. Kontuan izan TD metodoen kalkulua inkrementala (memoria trantsizio bakoitzaren ondoren aldatzen da eta trantsizioa baztertu egiten da) edo multzoetan (trantsizioak jasotzen dira eta estimazioak behin kalkulatzen dira trantsizio kopuru handi batean oinarrituta) izan daitekeela. Multzo-metodoak, zeinetan adibide bikaina Bradtke eta Barto-k (1996) proposatutako karratu minimoen denbora-diferentzia metodoa den, laginen informazioa hobeto erabil dezakete, metodo inkrementalak aukera bakarra diren arren, prozesu-batch metodoak bideraezinak bihurtzen direnean konplexutasun handia edo memoria eskatzen dutelako. Gainera, bi ikuspegien abantailak bateratzen saiatzen diren metodoak daude. Aurreko paragrafoan aipatutako azken gaiari heltzeko, funtzioak hurbiltzeko metodoak erabiltzen dira. Funtzio linealaren hurbilketa batean, dimentsio finituko bektore bat egoera-ekintza bikote bakoitzari esleitzen zaio. Orduan, egoera-ekintza bikote baten ekintza-balioak lortzen dira ϕ bektorearen osagaiak konbinatuz ϕ(s,a) pisu batzuekin θ:  

:Q(s,a) = \sum_{i=1}^d \theta_i \phi_i(s,a).

Funtzioaren hurbilketa lineala ez da aukera bakarra. Gertuago, estatistika ez-parametrikoaren ideietan oinarritutako metodoak aztertu dira (zeintzuk beren ezaugarriak eraikitzen dituztela ikus daitezke). Orain arte, eztabaida politikaren iterazioa erabiltzeko moduaz mugatu da, ikasketa indargarriaren algoritmoak diseinatzeko oinarri bezala. Garrantzitsua da ere, balioaren iterazioa abiapuntutzat har daitekeela, Q-ikaskuntza algoritmoa (Watkins 1989) eta bere hainbat aldaera sortuz. Ekintza-balioak erabiltzen dituzten metodoen arazoa da litekeena dela ekintza-lehiakidearen balioaren estimazio zehatzak behar izatea, eta zaila izan daiteke errendimenduak zaratatsuak direnean lortzea. Arazo hori, nolabait, denbora-diferentzia metodoek arintzen dute, eta bateragarriak diren funtzioak hurbiltzeko metodoa erabiltzen bada, asko dago egiteko orokortasuna eta eraginkortasuna handitzeko. Denbora-diferentzia metodoen arazo espezifiko bat Bellman-en ekuazio errekurtsiboarekiko duten menpekotasunetik dator. Denbora-diferentzia metodo gehienek λ parametroa dute (0≤λ≤1), Monte-Carlo metodoen (Bellman-en ekuazioetan oinarritzen ez direnak) eta oinarrizko denbora-diferentzia metodoen artean jarraian interpolatu ahal izateko aukera ematen duena (ekintza horiek Bellman-en ekuazioetan soilik oinarritzen dira), beraz, arazo hau arintzeko eraginkorra izan daiteke.

### Politika bilaketa zuzena 
Politika on bat aurkitzeko metodo alternatibo bat politika espazioaren (submultzo baten) barruan bilatzea da, kasu honetan arazoa optimizazio estokastiko baten adibide bihurtzen delako. Eskuragarri dauden bi hurbilketak, gradienteetan eta gradiente libreko metodoetan oinarritzen dira. Gradienteetan oinarritutako metodoek (politika gradiente metodoak deitzen direnak) dimentsio mugatuko (parametro) espazio bat politikaren espazioari esleitzen diote: Parametro bektorea θ emanda, π_θ​ erabiliz θ-ri loturiko politika adierazteko. Errendimendu funtzioa honela definitzen da: ρ(θ) = ρ^(π_θ). Baldintza leunetan funtzio hau diferentziagarria izango da parametroen bektorearen funtzio gisa. ρ-ren gradientea ezagutzen bada, gradiente igoera erabil daiteke. Gradientea zehazki eskuratzeko adierazpen analitikorik ez dagoenez, estimazio zaratatsu baten menpe egon behar da. Estimazio hori era askotara eraiki daiteke, Williams' Reinforce metodoa bezalako algoritmoak emanez. Metodoen klase handi batek gradiente informazioaren menpe egotea saihesten du. Horien artean simulatutako erretzea, entropia gurutzatuko bilaketa edo eboluzio konputazionaleko metodoak daude. Gradiente libreko metodo askok (teorian eta muga batean) optimo globala lortu dezakete. Kasu batzuetan, benetan errendimendu nabarmena erakutsi dute. Bilaketa metodoen arazoa da informazio zaratatsuari jarraitzen badio, poliki konbergitzen direla. Adibidez, hori arazo episodikoetan gertatzen da, ibilbideak luzerakoak direnean eta irabazien aldagaitza handia denean. Lehenago adierazi den bezala, denbora aldagaietan oinarritutako balio funtzioetan oinarritutako metodoek lagundu dezakete kasu honetan. Azken urteetan ideia honen inguruan hainbat algoritmo aktore eta kritiko proposatu dira, eta arazo desberdinetan errendimendu ona erakutsi dute.

## Teoria 
MDP txikien teoria, finitua denean, nahiko heldua dago. Algoritmo gehienen portaera asintotikoa zein lagin finituko portaera ondo ulertuta daude. Aurretik aipatu bezala, linea bidezko errendimendu ona duten algoritmoak ezagunak dira. MDP handien teoria gehiago landu behar da. Azterketa eraginkorra ia ukitu gabe dago (bandidoen arazoak salbu). Azken urteotan, denbora finituko errendimendu mugak dituzten algoritmo asko agertu diren arren, espero da mugak hobetzea, nahiko zehaztugabeak baitira, eta, beraz, gehiago lan egin behar da algoritmo hauen abantaila erlatiboak eta mugak hobeto ulertzeko. Algoritmo inkrementalentzat, asintotikoen bategite arazoak konpondu dira. Azkenaldian, denborazko diferentzietan oinarritutako algoritmo inkremental berriak agertu dira, eta baldintza askoz zabalagoetan bategiten dute lehen baino.

## Erreferentziak 
## Bibliografia 
* 
* 
* 
* 
* 
* 

## Ikus, gainera 
* Adimen artifizial
* Ikaskuntza sakon
* Datu handiak

## Kanpo estekak 
* Reinforcement Learning and Artificial Intelligence (Sutton's lab at the University of Alberta) (ingelesez)
* Autonomous Learning Laboratory (Barto's lab at the University of Massachusetts Amherst) (ingelesez)
* RL-Glue (ingelesez)
* Software Tools for Reinforcement Learning (Matlab and Python) (ingelesez)
* The UofA Reinforcement Learning Library (texts) (ingelesez)
* The Reinforcement Learning Toolbox from the (Graz University of Technology) (ingelesez)
* Hybrid reinforcement learning (ingelesez)
* Piqle: a Generic Java Platform for Reinforcement Learning (ingelesez)
* A Short Introduction To Some Reinforcement Learning Algorithms (ingelesez)
* Reinforcement Learning applied to Tic-Tac-Toe Game (ingelesez)
* Scholarpedia Reinforcement Learning (ingelesez)
* Scholarpedia Aldi Baterako Difference Learning (ingelesez)
* Stanford Reinforcement Learning Course (ingelesez)
* Real-world reinforcement learning experiments at Delft University of Technology (ingelesez)
* Reinforcement Learning Tools for Matlab (ingelesez)
* Stanford University Andrew Ng Lecture on Reinforcement Learning (ingelesez)
* Relative Entropy Policy Search (ingelesez)