Invatarea cu intarire - Q-learning

Invatarea cu intarire

~ Q-learning ~

1. Introducere

Faptul ca noi invatam prin interactiunea cu mediul inconjurator este primul lucru la care ne gandim atunci cand luam in considerare modul de invatare. Cand un copil se joaca sau da din maini, el nu are un profesor anume, dar are o legatura directa cu mediul inconjurator de tip senzor-motor. Exersarea acestei legaturi produce o cantitate mare de informatii de tip cauza-efect, despre consecintele actiunilor si ceea ce trebuie sa faca astfel incat sa isi atinga scopul. Pe parcursul vietii, aceste interactiuni sunt fara indoiala o sursa majora de cunostinte asupra mediului inconjurator si asupra oamenilor. Fie ca invatam sa conducem o masina sau sa purtam o conversatie, suntem deplin constienti de modul in care mediul inconjurator reactioneaza la ceea ce facem, si cautam sa influentam acest lucru prin comportamentul nostru. Invatarea prin interactiune este ideea fundamentala ce sta la baza tuturor teoriilor despre invatare si inteligenta.

1.1. Invatarea cu intarire

Invatarea cu intarire este invatarea a ceea ce trebuie sa facem - cum sa facem legatura intre situatii si actiuni - astfel incat sa maximizam un semnal numeric "recompensa"("premiu"). Celui ce invata nu i se spune ce actiuni anume sa faca, ca in majoritatea formelor de invatare a masinilor, ci trebuie sa descopere ce actiuni ii ofera "recompensa" cea mai mare prin incercarea acestora. In cele mai interesante si solicitante cazuri, actiunea poate influenta nu numai "recompensa" imediata, dar si situatiile urmatoare, si prin acestea si toate "premiile" urmatoare. Aceste doua caracteristici - cautarea incercare-si-eroare si "premiile" intarziate - sunt cele mai importante aspecte particulare ale invatarii cu intarire.

Invatarea cu intarire nu este definita prin caracterizarea algoritmilor de invatare, ci prin caracterizarea problemei de invatare. Orice algoritm potrivit pentru rezolvarea acelei probleme este considerat un algoritm de invatare cu intarire. Ideea de baza este perceperea celor mai importante aspecte ale problemei reale pe care o intampina un agent in interactiunea cu mediul sau inconjurator pentru a atinge scopul urmarit. Evident, acest agent trebuie sa poata detecta starea sistemului sau intr-o anumita masura si trebuie sa poata realiza actiuni astfel incat sa schimbe acea stare. Agentul, de asemenea, trebuie sa aiba unul sau mai multe scopuri privind starea sistemului. Cele mai importante aspecte ale invatarii sunt : senzorul, actiunea si scopul.

Invatarea cu intarire este diferita de invatarea supravegheata, tipul de invatare cel mai studiat in invatarea masinilor, recunoasterea formelor si retele neuronale. Invatarea supravegheata este invatarea din exemplele prezentate de un supraveghetor experimentat extern. Aceasta este o metoda importanta de invatare dar singura, nu este potrivita in invatarea prin interactiune. In problemele interactive este deseori nepotrivita obtinerea exemplelor de comportare dorita care sa fie atat corecta cat si reprezentativa in toate situatiile in care agentul trebuie sa interactioneze. Un agent trebuie sa poata invata din propria sa experienta.

Una din provocarile care apar in invatare cu intarire si care nu apare in alte tipuri de invatare este negocierea explorare-exploatare. Pentru a obtine o "recompensa" cat mai mare, un agent trebuie sa aleaga actiunile cunoscute si care s-au dovedit a fi eficiente. Dar pentru a descoperi asemenea actiuni, el trebuie sa aleaga actiuni pe care nu le-a mai incercat pana atunci. Agentul trebuie sa exploateze ceea ce cunoaste pentru a obtine "recompensa", dar trebuie de asemenea sa exploreze pentru a face selectii mai bune a actiunilor in viitor. Dilema este ca nici una din cele doua - exploatarea si explorarea - nu trebuie folosita in mod exclusiv. Agentul trebuie sa incerce o varietate de actiuni si progresiv sa le prefere pe cele ce par a fi mai bune. Intr-o sarcina aleatoare, fiecare actiune trebuie incercata de mai multe ori pentru a estima cu incredere "recompensa". Dilema explorare-exploatare a fost studiata intens de matematicieni de zeci de ani. Pentru moment observam doar ca problema echilibrului explorare-exploatare nici macar nu apare in invatare supravegheata.

O alta particularitate a invatarii cu intarire este ca aceasta considera in mod expicit intreaga problema a agentului care isi urmareste scopul si interactioneaza cu un mediu necunoscut. Aceasta este in contrast cu multe abordari care se ocupa de subprobleme fara sa tina cont de ansamblul problemei. De exemplu, o buna parte din cercetarea invatarii masinilor se ocupa de invatarea supravegheata fara sa specifice cum ar putea fi util acest lucru. Alti cercetatori au dezvoltat teorii de planificare cu scopuri generale fara sa considere rolul planificarii in probleme de decizie in timp real. Desi aceste abordari au dat multe rezultate, concentrarea acestora pe subprobleme izolate reprezinta o limitare signifianta.

Invatarea cu intarire urmareste firul invers, incepand cu un agent complet, interactiv, condus de un scop. In invatarea cu intarire, toti agentii au scopuri clare, pot detecta aspecte ale mediului inconjurator, si poate alege actiuni care sa influenteze mediul lor. In plus, se presupune de la inceput faptul ca agentul trebuie sa opereze in ciuda incertitudinii semnificative asupra mediului in care opereaza. Atunci cand invatarea cu intarire implica planificare, acesta trebuie sa tina cont si de interdependenta dintre planificare si selectie a actiunii in timp real, cat si de problema cum sunt obtinute modelele mediului si cum pot fi acestea imbunatatite. Daca invatarea cu intarire implica invatare supravegheata, atunci motivul este bine intemeiat, si anume determinarea caror aptitudini sunt critice sau nu.

. Exemple

O buna metoda de a intelege invatarea cu intarire este prezentara unor exemple si aplicatii posibile care au fost utilizate la dezvoltarea acesteia.:

- un jucator de sah face o mutare. Alegerea acestuia este facuta in functie atat de planificare - anticipand replici posibile ale adversarului si ale sale - dar si de hotararea daca anumite pozitii si mutari sunt dezirabile sau nu.

- un controler adaptiv ajusteaza parametrii unei operatiuni dintr-o rafinarie in timp real. Controlerul optimizeaza rapoartele productie/cost/calitate bazandu-se pe costuri marginale specificate, dar fara sa se limiteze exact la setul de valori indicate de ingineri.

- un pui de gazela abia se tine pe picioare in primele minute de la nastere. O jumatate de ora mai tarziu, alearga cu 30 mile pe ora.

- un robot mobil decide daca sa intre intr-o noua camera in cautarea obiectelor sau sa caute calea pana la punctul de incarcare a bateriilor. El ia aceasta decizie tinand cont de cat de repede a gasit calea pana la incarcator in incercarile anterioare.

Toate aceste exemple au in comun caracteristici care sunt fundamentale, dar care sunt usor de trecut cu vederea. Toate presupun interactiune intre agent care ia decizii si mediul sau, mediu in care fiecare agent incearca sa isi atinga scopul in ciuda incertitudinii asupra spatiului de lucru. Actiunile agentului afecteaza starile viitoare ale mediului, deci afecteaza optiunile si oportunitatile agentului dintr-un moment viitor. O alegere corecta presupune luarea in considerarea consecintele indirecte, intarziate ale actiunilor, ceea ce necesita anticipare si planificare.

In acelasi timp, in toate aceste exemple, efectele actiunilor nu pot fi prevazute integral si deci agentul trebuie sa monitorizeze frecvent mediul sau si sa reactioneze corespunzator. Toate aceste exemple implica scopuri clare, in sensul ca agentul poate evalua progresul sau catre scop pe baza unor masuratori directe. Jucatorul de sah stie daca castiga sau nu, controlerul rafinariei stie cat petrol este produs, robotul mobil stie cand bateriile sale s-au terminat.

In toate aceste cazuri, agentul poate folosi experienta sa pentru a-si imbunatati performata in timp. Jucatorul de sah isi rafineaza intuitia cu care evalueaza pozitiile, imbunatatindu-si astfel jocul. Puiul de gazela isi imbunatateste eficienta alergarii. Cunostintele pe care le detine agentul la inceperea sarcinii - fie din experiente anterioare, fie incluse prin design sau evolutie - influenteaza ceea trebuie invatat, dar interactiunea cu mediul este esentiala pentru ajustarea comportamentului pentru a exploata diferite aspecte ale sarcinii.

. Elemente ale invatarii cu intarire

In afara de agent si mediul sau, se pot indentifica patru sub-elemente ale invatarii cu intarire: o tactica, o functie de "recompensa", o functie "valoare" si optional, un model al mediului.

O tactica defineste modul de comportare al agentului la un moment dat. O tactica este asocierea dintre starile cunoscute ale mediului si actiunile preferate din acele stari. Aceasta corespunde la ceea ce in psihologie se numeste asocierea stimul-raspuns. In unele cazuri tactica poate fi o functie simpla sau o tabela de cautare, pe cand in altele poate implica calcule vaste cum ar fi un proces de cautare. Tactica este nucleul unui agent cu invatare cu intarire in sensul ca aceasta singura este suficienta pentru a determina modul de comportarea a agentului. In general, tacticile pot fi aleatoare.

O functie de "recompensa" defineste scopul intr-o problema cu invatare cu intarire. Aceasta ascociaza starile (sau perechile stare-actiune) cunoscute cu un singur numar, o "recompensa", indicand dezirabilitatea proprie starii. Unicul obiectiv al agentului este maximizarea recompenselor pe care le primeste in timp. Functia recompensa defineste care sunt evenimentele "bune" pentru agent si care sunt cele "rele". Intr-un sistem biologic putem identifica recompensa cu "placerea" si "durerea". Acestea sunt caracteristicile imediate si definitorii ale problemei cu care se confrunta agentul. Din acest motiv, functia recompensa trebuie fixata. Aceasta poate fi, totusi, folosita ca o baza pentru modificarea tacticii. De exemplu, daca o actiune selectata de tactica produce o recompensa scazuta, atunci tactica poate fi schimbata astfel incat sa selecteze o alta actiune in viitor. In general, functiile recompensa pot fi stohastice.

In timp ce funtia recompensa indica ce este bine in viitorul imediat, o functie valoarei specifica ce este bine in timp mai indelungat. Valoarea unei stari este recompensa totala la care se poate astepta agentul in viitor incepand cu acea stare. In timp ce recompensa indica dezirabilitatea imediata a starii mediului, valorile indica dezirabilitatea pe termen lung a starii luand in considerare si starile probabile ce pot aparea dupa aceasta si recompensele corespunzatoare acestor stari. De exemplu, o stare poate implica o recompensa mica imediata, dar poate avea o valoare mare deoarece este urmata de obicei de alte stari care implica recompense mai mari. Sau inversul poate fi valabil. Facand o analogie cu omul, recompensa este placerea (atunci cand are valoare mare) sau este durerea (atunci cand are valoare mica), unde valorile corespund unei judecati mai rafinate si prevazatoare despre cat de placut sau neplacut va fi daca mediul va fi intr-o anumita stare.

Recompensa este, intr-un fel, primara, pe cand valoarea, ca predictie a recompenselor, este secundara. Fara recompense nu ar putea fi valori, si unicul scop de a estima valoarea este pentru a primi mai multe recompense. Cu toate acestea, valorile sunt cele luate in calcul la evaluarea si luarea deciziilor. Alegerea actiunilor este facuta pe baza valorilor. Cautam actiuni care ne aduc in stari cu valori cat mai mari, nu cu recompense cat mai mari, deoarece aceste actiuni ne aduc recompense mai mari in decursul timpului. In luarea deciziilor si in planificare, cantitatea derivata numita valoare este cea care luata in calcul. Din pacate, este mult mai greu de determinat valorile decat recompensele. Recompensele sunt de fapt, date direct de catre mediul inconjurator, dar valorile trebuie estimate si reestimate din secventa de observatii pe care agentul le face de-a lungul intregii lui "vieti". De fapt, cea mai importanta componenta din aproape toti algoritmii de invatare cu intarire este o metoda de a calcula eficient si corect valoarea. Importanta si pozitia centrala pe care o are estimarea valorii este, probabil cel mai important lucru descoperit in ultimele doua decade in invatarea cu intarire.

Cel de-al patrulea element al sisemelor cu invatare cu intarire este modelul mediului. Acesta modeleaza comportarea mediului. De exemplu, data o stare si o actiune, modelul poate prezice starea rezultanta si recompensa urmatoare. Modelele sunt folosite pentru planificare, prin planificare intelegand orice mod de a decide cursul actiunii considerand situatii viitoare posibile inainte de a le experimenta. Incorporarea modelelor si planificarii in sistemele de invatare cu intarire este o directie relativ noua. Primele sisteme cu invatare cu intarire au fost sisteme doar cu incercare-si-eroare, fiind privite ca fiind opusul planificarii. Oricum, treptat, a devenit clar ca metodele de invatare cu intarire sunt in stransa legatura cu metode de programare dinamica, care folosesc modele, si care sunt la randul lor in stransa legatura cu metodele stare-spatiu de planificare.

O exemplificare simpla

Pentru a ilustra ideea generala a invatarii cu intarire, vom considera un exemplu detaliat: jocul X si 0 (tic-tac-toe)

Regulile sunt cunoscute de multi: un jucator pune X pe tabla de joc, o tabla de 3 x 3 casute, iar celalalt jucator pune 0. Jucatorii au muta pe rand. Scopul jocului este ca un jucator sa aseze in linie 3 piese de ale sale (pe linie, pe coloana sau pe diagonala). Primul care realizeaza acest lucru este castigator. Daca tabla se umple inainte ca vre-un jucator sa castige, atunci este remiza.

Abordarile clasice ale acestei probleme nu dau rezultate satisfacatoare. Metoda "minimax" este corecta pentru o strategie a adversarului. O abordare evolutionista a acestei probleme ar cauta in spatiul strategiilor, strategia corecta. Pentru aceasta ar fi nevoie de cunoasterea tuturor strategiilor, pentru a putea fi comparate acestea.

In exemplul nostru, vom aborda problema utilizand invatarea cu intarire si o functie valoarea aproximativa. Vom utiliza o functie valoare care va reprezenta probabilitatea de castig din acea starea. Aceasta functie va reprezenta cunostintele "invatate" de agent. Pentru inceput, initializam valorile functiei cu 1 in starile castigatoare, cu 0 in starile de remiza sau pierdere si cu 0.5 in celelalte stari. (0.5 reprezentand sanse egale de castig)

In acest moment putem incepe jocul impotriva unui alt jucator (fie el un jucator care muta la intamplare). Pentru a alege mutarea din toate mutarile posibile dintr-o anumita stare, vom cauta in valorile mutarilor posibile si o vom alege pe cea care ne duce intr-o stare cu valoarea mai mare, adica ne vom plasa intr-o stare care are probabilitatea mai mare de castig. Acesta mutare este de tip greedy. Din cand in cand, vom alege o mutare la intamplare, pentru a putea explora si alte stari. Daca aceste mutari nu au loc, procesul de invatare este limitat, si exista riscul sa nu experimentam niciodata anumite stari. Acest tip de mutare se numeste exploratoare.    In timpul jocului, vom modifica valorile starilor in care ne aflam. In acest fel, incercam sa evaluam valorile starilor cat mai precis. Valoare unei stari este modificata astfel incat sa se apropie de valoarea starii urmatoare: V(s) = V(s) + step_size*(V(s') - V(s) ) . step_size este un parametru subunitar, care influenteaza rata de invatare. Aceasta metoda de modificare a functiei valoare este un exemplu de invatare cu diferente-temporale deoarece este bazata pe diferenta V(s')-V(s) - estimarea starii la doua momente diferite de timp.

Aceasta metoda descrisa mai sus are rezultate destul de bune. Daca parametrul step_size este redus in timp, aceasta metoda converge, pentru un jucator fix, la o functie valoarea care estimeaza corect probabilitatile de castig. In alte cuvinte, aceasta metoda converge la o strategie corecta impotriva unui anumit jucator. Daca parametrul nu este redus la zero, atunci jucatorul va putea juca bine si impotriva unor jucatori care isi schimba incet strategia de joc.

Cu ajutorul programului realizat, putem observa modificare valorilor starilor, catre o estimare corecta a probabilitatilor de castig. Putem face observatia ca luarea in considerare a starilor simetrice va reduce de cateva ori numarul de stari, scazand timpul de invatare.