Curs 12 - Reinforcement Learning II PDF (January 9, 2024)

Curs 12 - Reinforcement learning II January 9, 2024 Curs 12 - IA January 9, 2024 1 / 28 Curpins 1 Reinforcement learning activ 2 Aproximarea reinforcement learning 3 Studii de caz Curs 12 - IA January 9, 2024 2 / 28...

Curs 12 - Reinforcement learning II January 9, 2024 Curs 12 - IA January 9, 2024 1 / 28 Curpins 1 Reinforcement learning activ 2 Aproximarea reinforcement learning 3 Studii de caz Curs 12 - IA January 9, 2024 2 / 28 Setupul problemelor rezolvate cu RL suntem in situatia problemelor MDP un set de stari s ∈ S un set A de actiuni (in fiecare stare) un model (probabilistic) T (s, a, s ′ ) o functie de castig (reward) R(s, a, s ′ ) deci cautam o politica π(s) dar nu cunoastem T sau R nu stim care stari sunt cele favorabile si nici actiunile pe care sa le alegem trebuie sa incercam actiuni si stari pentru a invata Idee de baza: sa calculam valorile medii peste modelul probabilistic T folosind iesirea rezultata din actiuni Curs 12 - IA January 9, 2024 3 / 28 Rezolvare cu MDP si RL (pasiv) MDP cu informatie completa (cunoscuta) Obiectiv Tehnica Calculul V ∗ , Q ∗ , π ∗ iterarea valorilor / politicii Evaluarea unei politici (fixate) π Evaluarea politicii MDP fara informatie completa - rezolvare cu estimarea modelului Obiectiv Tehnica Calculul V ∗ , Q ∗ , π ∗ iterarea valorilor / politicii pentru MDP-ul estimat Evaluarea unei politici π Evaluarea politicii pentru MDP-ul estimat MDP fara informatie completa - rezolvare fara model Obiectiv Tehnica Calculul V ∗ , Q ∗ , π ∗ Q-learning Evaluarea unei politici π invatarea valorilor Curs 12 - IA January 9, 2024 4 / 28 MDP cu informatie incompleta - rezolvare fara model Temporal-difference learning Se primeste la intrare o secventa de experiente din mediu (s, a, r , s ′ , a′ , r ′ , s ′′ , a′′ , r ′′ , s ′′′ ,...) Se actualizeaza estimarile pentru fiecare tranzitie (s, a, r , s ′ ) Curs 12 - IA January 9, 2024 5 / 28 MDP cu informatie incompleta - rezolvare fara model Temporal-difference learning Se primeste la intrare o secventa de experiente din mediu (s, a, r , s ′ , a′ , r ′ , s ′′ , a′′ , r ′′ , s ′′′ ,...) Se actualizeaza estimarile pentru fiecare tranzitie (s, a, r , s ′ ) In timp, actualizarile vor replica actualizarile Bellman Curs 12 - IA January 9, 2024 5 / 28 Q-learning Q-iteration: facem actualizarea valorilor Q pentru fiecare stare Q initializam Q0 (s, P a) = 0 si apoi iteram Qk+1 (s, a) ← s ′ T (s, a, s ′ ) [R(s, a, s ′ ) + γ maxa′ Qk (s ′ , a′ )] dar nu putem face actualizarile fara sa cunoastem T si R Q-learning : calculam mediile valorilor pe masura ce avansam facem o tranzitie oarecare (s, a, r , s ′ ) pentru aceasta tranzitie Q(s, a) ≈ r + γ maxa′ Q(s ′ , a′ ) dar dorim sa face o medie pentru rezultatele obtinute din tranzitia (s, a) deci vom face media in felul urmator: Q(s, a) ← (1 − α)Q(s, a) + α [r + γ maxa′ Q(s ′ , a′ )] Curs 12 - IA January 9, 2024 6 / 28 Proprietati Q-learning Q-learning converge la politica optimala chiar daca actiunile sunt alese sub-optimal !!! Astfel obtinem un mod optim de a actiona π ∗ = argmaxa Q(s, a) acest mod de actiune se numeste off-policy learning neajunsuri trebuie sa exploram destul de multe actiuni si stari trebuie sa facem rata de invatare suficient de mica (dar sa nu descrestem destul de rapid) la limita, nu conteaza cum selectam actiunile ! Curs 12 - IA January 9, 2024 7 / 28  Reinforcement learning activ Curpins 1 Reinforcement learning activ 2 Aproximarea reinforcement learning 3 Studii de caz Curs 12 - IA January 9, 2024 8 / 28  Reinforcement learning activ Explorare vs. exploatare Curs 12 - IA January 9, 2024 9 / 28  Reinforcement learning activ Cum facem explorare? Sunt disponibile cateva modalitati de a face explorare: Cea mai simpla: alegerea aleatorie a actinilor (ϵ-greedy) la fiecare moment de timp dam cu banul cu o probabilitate mica ϵ, alegem o actiune aleatorie cu o probabilitate mare 1 − ϵ actionam conform politicii curente probleme cu aceasta strategie: vom explora spatiul disponibil, dar aruncam experienta la gunoi pe masura ce invatarea evolueaza solutie: sa diminuam ϵ pe masura ce timpul trece solutie alternativa: o functie de explorare Curs 12 - IA January 9, 2024 10 / 28  Reinforcement learning activ Functii de explorare Cand sa exploram? actiuni aleatorii: exploram intr-o masura fixata o idee mai buna ar fi sa exploram in spatii care nu au fost evaluate ca si defavorabile, si eventual sa oprim explorarea Functii de explorare luam o valoare estimata u si un numar de vizite n si returnam o utilitate optimistica: f (u, n) = u + k/n actualizarea obisnuita a valorii Q: Q(s, a) ←α R(s, a, s ′ ) + γ maxa′ Q(s ′ , a′ ) actualizarea modificata a valorii Q: Q(s, a) ←α R(s, a, s ′ ) + γ maxa′ f (Q(s ′ , a′ ), N(s ′ , a′ )) prin x ←α v am notat x ← (1 − α)x + αv Curs 12 - IA January 9, 2024 11 / 28  Reinforcement learning activ Evaluarea metodelor de explorare - Regret chiar daca in final invatam o politica optima, pe parcursul invatarii facem greseli regretul este o masura costului total al greselilor diferenta dintre toate bonificatiile (asteptate), incluzandu-le pe cele mai recente bonificatii suboptime si pe cele optime (asteptate) Minimizarea regretului inseamna mai mult decat a face invatarea optimala: necesita ca metoda de invatare sa devina optima De exemplu: explorarea aleatorie si cea cu o functie de explorare amandoua vor conduce la o politica optima, doar ca explorarea aleatorie va rezulta intr-un regret mai mare Curs 12 - IA January 9, 2024 12 / 28  Reinforcement learning activ Este poblema rezolvata? in principiu, da, daca am gasit o functie de explorare optima dar ce facem in cazul spatiilor de cautare mari si complexe? Curs 12 - IA January 9, 2024 13 / 28  Aproximarea reinforcement learning Curpins 1 Reinforcement learning activ 2 Aproximarea reinforcement learning 3 Studii de caz Curs 12 - IA January 9, 2024 14 / 28  Aproximarea reinforcement learning Generalizam peste starile problemei Q-learning necesita memorarea unei tabele cu toate valorile q dar in situatii realistice nu putem sa invatam valoarea fiecarei stari prea multe stari pentru a fi vizitate in pasul de invatare prea multe stari pentru a fi pastrate in memorie in tabela cu valorile q in locul unei astfel de tabele dorim sa generalizam invatam despre un numar mic de stari din experienta generalizam aceasta experienta la stari noi, similare cu cele invatate aceasta este o proprietate fundamentala a machine learning Curs 12 - IA January 9, 2024 15 / 28  Aproximarea reinforcement learning Marimea spatiului de stari Proprietati ale mediului: pozitii ale agentului: 120 numar de puncte (mancare): 30 pozitii ale strigoilor: 12 directii ale agentului: NSEW Cate stari? Stari ale lumii: 120x(230 )x(122 )x4 stari pentru problema de cale: 120 stari pentru problema eat-all-dots: 120x(230 ) Curs 12 - IA January 9, 2024 16 / 28  Aproximarea reinforcement learning Pacman - exemplu am descoperit prin experienta ca starea e rea: Curs 12 - IA January 9, 2024 17 / 28  Aproximarea reinforcement learning Pacman - exemplu am descoperit prin in q-learning nu experienta ca starea stim nimic despre e rea: aceasta stare: Curs 12 - IA January 9, 2024 17 / 28  Aproximarea reinforcement learning Pacman - exemplu am descoperit prin in q-learning nu si nici despre experienta ca starea stim nimic despre aceasta stare: e rea: aceasta stare: Curs 12 - IA January 9, 2024 17 / 28  Aproximarea reinforcement learning Reprezentare bazata pe proprietati (features) reprezentam spatiul de stari folosind un vector de proprietati (features) f1 , f2 ,... proprietatile sunt functii care mapeaza starile la numere reale (sau la 0/1), astfel incat se reprezinta aspecte importante ale starii respective exemple de proprietati: distanta fata de strigoiul cel mai apropiat distanta fata de punctul cel mai apropiat numarul de strigoi 1 / patratul distantei la punct este Pacman intr-un tunel (0 sau 1)? etc putem descrie si o q-stare cu o proprietate: de exemplu actiunea care muta agentul mai aproape de mancare Curs 12 - IA January 9, 2024 18 / 28  Aproximarea reinforcement learning Functii liniare pentru valori folosind o reprezentare cu proprietati f1 , f2 ,..., putem scrie o q-functie (sau functie de valoare) pentru orice stare folosind un set de ponderi w1 , w2 ,...: V (s) = w1 f1 (s) + w2 f2 (s) +... + wn fn (s) Q(s, a) = w1 f1 (s, a) + w2 f2 (s, a) +... + wn fn (s, a) avantaj: experienta este sumarizata de setul de ponderi w! , w2 ,... dezavantaj: starile pot sa partajeze proprietati, dar in realitate ele pot sa aiba valori diferite Exemplu: cele 2 stari pot avea aceasi valoare daca nu includem pozitia strigoilor ca si proprietate Curs 12 - IA January 9, 2024 19 / 28  Aproximarea reinforcement learning Q-learning aproximat presupunem Q(s, a) = w1 f1 (s, a) + w2 f2 (s, a) +... + wn fn (s, a) Q-learning cu functie liniara pentru valorile Q: fie o tranzitie = (s, a, r , s ′ ) diferenta = [r + γ maxa′ Q(s ′ , a′ )] − Q(s, a) Q(s, a) ← Q(s, a) + α × diferenta wi = wi + α × diferenta × fi (s, a) reprezentare intuitiva: ajustam ponderile proprietatilor active daca apare o situatie nefavorabila, vom penaliza proprietatile care au fost active: vom evita toate starile cu acele proprietati justificare teoretica (formala): metoda celor mai mici patrate, scaderea gradientului Curs 12 - IA January 9, 2024 20 / 28  Aproximarea reinforcement learning Exemplu: Q-Pacman Curs 12 - IA January 9, 2024 21 / 28  Aproximarea reinforcement learning Cautarea politicii Problema: de cele mai multe ori politici bazate pe proprietati functioneaza bine in situatii multi-agent (castiga jocuri, maximizeaza utilitati), dar acestea nu sunt cele care aproximeaza valorile V si Q cel mai bine prioritatea Q-learning: sa se obtina q-values (sarcina de modelare) prioritatea selectiei actiunii: sa se obtina o ordonare potrivita a q-values (sarcina de predictie) Solutie: invatam politica π care maximizeaza bonificatia, si nu valorile Q care prezic aceasta bonificatie Cautarea politicii: pornim cu o solutie ok (de exemplu prin Q-learning). Facem rafinare (fine tuning) cu hill-climbing pe ponderile proprietatilor Curs 12 - IA January 9, 2024 22 / 28  Aproximarea reinforcement learning Cea mai simpla cautare a politicii Cea mai simpla cautare a politicii pornim cu o functie liniara pentru valori sau o q-functie mutam fiecare pondere a unei proprietati in sus sau in joc pentru a vedea daca obtinem o politica mai buna decat inainte Problema: cum determinam daca politica e mai buna? e nevoie sa executam multe episoade daca sunt foarte multe proprietati, poate deveni ne-fezabil Metode mai bune exploateaza o structura cunoscuta a mediului, extrage stari in mod inteligent, sau schimba mai multi parametri deodata Curs 12 - IA January 9, 2024 23 / 28  Studii de caz Curpins 1 Reinforcement learning activ 2 Aproximarea reinforcement learning 3 Studii de caz Curs 12 - IA January 9, 2024 24 / 28  Studii de caz Jocuri Atari MDP: stare: imaginea unui joc 25684×84 stari posibile starile sunt procesate cu un vector de proprietati bine proiectat sau cu o retea neuronala actiune: combinatie intre tastele sageti si celelalte butoane tranzitie: este specifica jocului (nu avem acces) bonificatie: este scorul jocului (nu avem acces) similar cu MDP Pacman se foloseste Q-learning aproximat impreuna cu o retea neuronala si explorare ϵ-greedy Curs 12 - IA January 9, 2024 25 / 28  Studii de caz Miscarea robotilor MDP: Stare: imaginea camerei robotului + N unghiuri + accelerometru +... Actiune: comenzi la motorul robotului (N). vectori de valori continue este dificil sa se calculeze maxa Q(s, a) daca a este continua se pot folosi tehnici de cautare a politicii sau adapta q-learning pentru actiuni continue Tranzitie: lumea reala Bonificatie: proiectata a-priori robotul sta drept in picioare, robotul mentine viteza de deplasare inainte invatarea in lumea reala poate fi inceata si nesigura se poate construi un simulator in care sa se faca invatarea, si apoi se poate face relocare in lumea reala Curs 12 - IA January 9, 2024 26 / 28  Studii de caz Asistenti lingvistici (chatboti) Pas 1: invatam un LLM (large language model) pentru a reproduce text uman Pas 2: facem rafinare (fine tuning) pentru a produce text util se poate folosi reinforcement learning in pasul 2 Curs 12 - IA January 9, 2024 27 / 28  Studii de caz Asistenti lingvistici (chatboti) MDP: Stare: secventa de cuvinte intalnita pana in momentul respectiv 1000001000 stari posibile spatiu imens de stari, poate fi procesaru cu un vector de proprietati sau cu o retea neuronala Actiune: cuvantul urmator dificil sa se calculeze maxa Q(s ′ , a) pt ca max se face peste 100k actiuni Tranzitie: usoara, se concaterneaza cuvantul urmator la cuvintele din stare Bonificatie: pozitiva daca rapsunsul e corect, se poate invata un model R̂ Se face cautarea politicii (Proximal policy optimization) si Q-learning Curs 12 - IA January 9, 2024 28 / 28