Curs 11-12 - Reinforcement learning PDF

Curs 11-12 - Reinforcement learning December 18, 2023 Curs 11-12 - IA December 18, 2023 1 / 27 Curpins 1 Reinforcement learning pasiv 2 Reinforcement learning activ 3 Aproximarea reinforcement learning 4 Studii de caz Cur...

Curs 11-12 - Reinforcement learning December 18, 2023 Curs 11-12 - IA December 18, 2023 1 / 27 Curpins 1 Reinforcement learning pasiv 2 Reinforcement learning activ 3 Aproximarea reinforcement learning 4 Studii de caz Curs 11-12 - IA December 18, 2023 2 / 27 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 Curs 11-12 - IA December 18, 2023 3 / 27 Offline (MDP) vs. online (RL) Solutie online: politica se calculeaza Solutie offline: politica se pe masura ce se acumuleaza calculeaza inaintea jocului experienta Curs 11-12 - IA December 18, 2023 4 / 27  Reinforcement learning pasiv Curpins 1 Reinforcement learning pasiv 2 Reinforcement learning activ 3 Aproximarea reinforcement learning 4 Studii de caz Curs 11-12 - IA December 18, 2023 5 / 27  Reinforcement learning pasiv RL pasiv - sumar se rezolva o sarcina simplificata: evaluarea unei politici input: o politica fixata π(s) nu cunoastem tranzitiile T (s, a, s ′ ) nu cunoastem castigurile R(s, a, s ′ ) cunoastem o secventa de tranzitii: (s, π(s), s ′ , R), (s ′ , π(s ′ ), s ′′ , R ′ ), (s ′′ , π(s ′′ ), s ′′′ , R ′′ ),... obiectiv: sa invatam valorile fiecarei stari functioneaza dupa cum urmeaza: invatarea se face pe masura evolutiei jocului nu avem de facut alegeri cu privire la ce actiuni sa luam doar se executa politica (fixata) si se invata din experienta este diferit de planificarea Offline: de fapt executam actiunile din mediu Curs 11-12 - IA December 18, 2023 6 / 27  Reinforcement learning pasiv Invatarea unui model ideea de invatare a unui model: invatam un model aproximativ pe baza experientei rezolvam problema pentru determinarea valorilor, ca si cum modelul invatat este cel corect Pas 1: Invatam un model MDP empiric numaram iesirile s ′ pentru fiecare stare s si actiune a normalizam pentru a obtine o estimare T̂ (s, a, s ′ ) descoperim fiecare R̂(s, a, s ′ ) atunci cand avem experienta (s, a, s ′ ) Pas 2: rezolvam problema MDP astfel obtinuta folosim un algoritm cunoscut pentru rezolvarea MDP, precum iterarea valorilor Curs 11-12 - IA December 18, 2023 7 / 27  Reinforcement learning pasiv Exemplu de model-based learning Politica de input: π(s). presupunem γ = 1 Curs 11-12 - IA December 18, 2023 8 / 27  Reinforcement learning pasiv Exemplu de model-based learning Politica de input: π(s). Tranzitiile observate (s, a, s ′ , R) presupunem γ = 1 Curs 11-12 - IA December 18, 2023 8 / 27  Reinforcement learning pasiv Exemplu de model-based learning Politica de input: π(s). Tranzitiile observate (s, a, s ′ , R) presupunem γ = 1 Modelul invatat Curs 11-12 - IA December 18, 2023 8 / 27  Reinforcement learning pasiv Analogie: varsta asteptata Obiectiv: calcularea varstei asteptate a studentilor din clasa Curs 11-12 - IA December 18, 2023 9 / 27  Reinforcement learning pasiv Analogie: varsta asteptata Obiectiv: calcularea varstei asteptate a studentilor din clasa se stie P(A) - frecventa de aparitie a varstei A P E [A] = a P(a) · a = 0.35 × 20 +... Curs 11-12 - IA December 18, 2023 9 / 27  Reinforcement learning pasiv Analogie: varsta asteptata Obiectiv: calcularea varstei asteptate a studentilor din clasa se stie P(A) - frecventa de aparitie a varstei A P E [A] = a P(a) · a = 0.35 × 20 +... Fara sa cunoastem P(a): colectam un esantion [a1 , a2 ,... , aN ] Curs 11-12 - IA December 18, 2023 9 / 27  Reinforcement learning pasiv Analogie: varsta asteptata Obiectiv: calcularea varstei asteptate a studentilor din clasa se stie P(A) - frecventa de aparitie a varstei A P E [A] = a P(a) · a = 0.35 × 20 +... Fara sa cunoastem P(a): colectam un esantion [a1 , a2 ,... , aN ] P(A) necunoscut: estimare model-based num(a) P̂(a) = N P E [A] ≈ a P̂(a) ·a Curs 11-12 - IA December 18, 2023 9 / 27  Reinforcement learning pasiv Analogie: varsta asteptata Obiectiv: calcularea varstei asteptate a studentilor din clasa se stie P(A) - frecventa de aparitie a varstei A P E [A] = a P(a) · a = 0.35 × 20 +... Fara sa cunoastem P(a): colectam un esantion [a1 , a2 ,... , aN ] P(A) necunoscut: estimare model-based P(A) necunoscut: estimare fara num(a) model P̂(a) = N E [A] ≈ N1 i ai P P E [A] ≈ a P̂(a) ·a Curs 11-12 - IA December 18, 2023 9 / 27  Reinforcement learning pasiv Invatare fara model - evaluare directa (Monte Carlo) Obiectiv: sa calculam valorile pentru fiecare stare sub o anumita politica π Idee: sa facem media valorilor observate din esantion: actionam in concordanta cu politica π la fiecare vizitare a unei stari memoram suma beneficiilor reduse (rewarded) pe care le-am intalnit pornind de la acceea stare pana la finalul episodului samplei (s) = R(s) + γR(s ′ ) + γ 2 R(s ′′ ) +... facem mediaXacestor valori V (s) ← N1 samplesi (s) i Aceasta metoda se numeste evaluare directa sau Monte-Carlo Curs 11-12 - IA December 18, 2023 10 / 27  Reinforcement learning pasiv Exemplu de evaluare directa Politica de input: π(s). presupunem γ = 1 Curs 11-12 - IA December 18, 2023 11 / 27  Reinforcement learning pasiv Exemplu de evaluare directa Politica de input: π(s). Tranzitiile observate (s, a, s ′ , R) presupunem γ = 1 Curs 11-12 - IA December 18, 2023 11 / 27  Reinforcement learning pasiv Exemplu de evaluare directa Politica de input: π(s). Tranzitiile observate (s, a, s ′ , R) presupunem γ = 1 Valorile de iesire Curs 11-12 - IA December 18, 2023 11 / 27  Reinforcement learning pasiv Exemplu de evaluare directa Politica de input: π(s). Tranzitiile observate (s, a, s ′ , R) presupunem γ = 1 Valorile de iesire V (s) este suma castigurilor reduse pornind din starea s pana la final, calculate prin medie peste toate aparitiile starii s Curs 11-12 - IA December 18, 2023 11 / 27  Reinforcement learning pasiv Probleme cu evaluarea directa Valorile de iesire avantajele evaluarii directe este usor de inteles nu necesita cunoasterea lui T si R in caz fericit calculeaza valorile medii corecte folosind tranzitiile aparute prin esantionare dezavantajele evaluarii directe risipeste informatiile despre connexiunile dintre In politica fixata, daca din stari starile B si E se poate are nevoie ca toate episoadele sa fie generate merge in C, atunci cum inainte de executie s-ar putea ca valorile acestor stari sa fie diferite? Curs 11-12 - IA December 18, 2023 12 / 27  Reinforcement learning pasiv Probleme cu evaluarea directa Tranzitiile observate (s, a, s ′ , R) Este B o stare rea? Curs 11-12 - IA December 18, 2023 13 / 27  Reinforcement learning pasiv De ce sa nu folosim evaluarea politicii? formulele lui Bellman iterate permit calcularea lui V pentru o politica fixa la fiecare iteratie, inlocuim V cu V-ul obtinut prin calcul pe nivelul cu un pas inainte V0π = 0 P π Vk+1 ← s ′ T (s, π(s), s ′ )[R(s, π(s), s ′ ) + γVkπ (s ′ )] aceasta abordare exploateaza toate conexiunile dintre stari dar avem nevoie sa cunoastem T si R (pentru a putea face calculele) intrebare fundamentala: cum putem face acest calcul iterativ a lui V fara sa cunoastem T si R? in alte cuvinte, cum putem calcula media ponderata fara sa cunoastem ponderile? Curs 11-12 - IA December 18, 2023 14 / 27  Reinforcement learning pasiv Evaluarea politicii pe baza esantionului dorim sa imbunatatim estimarea lui V pe baza calculului mediilor folosind formula lui Bellman π ← s ′ T (s, π(s), s ′ )[R(s, π(s), s ′ ) + γVkπ (s ′ )] P Vk+1 Idee: facem actiunile, luam iesirile obtinute si facem media acestor valori sample1 = R(s, π(s), s1′ ) + γVkπ (s1′ ) sample2 = R(s, π(s), s2′ ) + γVkπ (s2′ )... samplen = R(s, π(s), sn′ ) + γVkπ (sn′ ) π 1 P Vk+1 ← n i samplei Curs 11-12 - IA December 18, 2023 15 / 27  Reinforcement learning pasiv Temporal difference learning Idee majora: sa invatam din toate experientele (dupa actiuni) actualizam V (s) de fiecare data cand intalnim o tranzitie (s,a,s’,r) iesirile cele mai frecvente pornind de la s vor contribui mai mult la actualizari invatarea valorilor prin diferenta temporala politica ramane fixata, si in continuare, facem evaluare mutam valorile catre valoarea oricarui succesor care apare, de fapt facem medie V (s) la o tranzitie: sample = R(s, π(s), s ′ ) + γV π (s ′ ) modificarea lui V (s): V π (s) ← (1 − α)V π (s) + (α)sample, cu 0