Q-learning

În inteligența artificială , mai precis în învățarea automată , învățarea Q este o tehnică de învățare de consolidare . Această tehnică nu necesită niciun model inițial al mediului . Litera „Q” denotă funcția care măsoară calitatea unei acțiuni efectuate într-o anumită stare a sistemului.

Descriere

Această metodă de învățare vă permite să învățați o politică, care indică ce acțiune să efectuați în fiecare stare a sistemului. Funcționează învățând o funcție notată de valoare a acțiunii de stare, care vă permite să determinați câștigul potențial, adică recompensa pe termen lung , oferită prin efectuarea unei anumite acțiuni într-o anumită stare, urmând o politică optimă. Când această funcție de valoare acțiune-stare este cunoscută / învățată de agent, politica optimă poate fi construită prin selectarea acțiunii valorii maxime pentru fiecare stare, adică prin selectarea acțiunii care maximizează valoarea atunci când agentul este în stare . Î{\ displaystyle Q}Î(s,la){\ displaystyle Q (s, a)}la{\ displaystyle a}s{\ displaystyle s}la{\ displaystyle a}Î(s,la){\ displaystyle Q (s, a)}s{\ displaystyle s}

Unul dintre punctele forte ale învățării este că face posibilă compararea recompenselor probabile ale acțiunilor accesibile fără a avea cunoștințe inițiale despre mediu. Cu alte cuvinte, deși sistemul este modelat ca un proces de decizie Markov (finalizat), agentul învață nu știe și algoritmul - învățarea nu îl folosește. Î{\ displaystyle Q}Î{\ displaystyle Q}

Această noțiune de învățare a recompensei a fost introdusă inițial în teza lui Watkins în 1989. Este o variantă a învățării diferențelor temporale. Ulterior, s-a dovedit că - învățarea converge către o politică optimă, adică conduce la maximizarea recompensei totale a etapelor succesive. Î{\ displaystyle Q}

Algoritm

Situația constă dintr-un agent, un set de stări și acțiuni . Prin efectuarea unei acțiuni , agentul se mută dintr-o stare într-o nouă stare și primește o recompensă (este o valoare numerică). Scopul agentului este de a maximiza recompensa sa totală. Acest lucru se realizează prin învățarea acțiunii optime pentru fiecare stat. Acțiunea optimă pentru fiecare stat este cea cu cea mai mare recompensă pe termen lung. Această recompensă este suma ponderată a așteptării matematice a recompenselor fiecărui pas viitor din starea actuală. Ponderea fiecărui pas poate fi unde este întârzierea dintre pasul curent și viitor și un număr între 0 și 1 (adică ) numit factorul de reducere . S{\ displaystyle S}LA{\ displaystyle A}la∈LA{\ displaystyle a \ în A}s{\ displaystyle s}s′{\ displaystyle s '}r{\ displaystyle r}γΔt{\ displaystyle \ gamma ^ {\ Delta t}}Δt{\ displaystyle \ Delta t}γ{\ displaystyle \ gamma}0≤γ≤1{\ displaystyle 0 \ leq \ gamma \ leq 1}

Algoritmul calculează o funcție de valoare acțiune-stare:

Î:S×LA→R{\ displaystyle Q: S \ times A \ to \ mathbb {R}}

Înainte de a începe învățarea, funcția este inițiată în mod arbitrar. Apoi, cu fiecare alegere a acțiunii, agentul observă recompensa și noua stare (care depinde de starea anterioară și de acțiunea curentă). Inima algoritmului este o actualizare a funcției de valoare . Definiția funcției de valoare este actualizată la fiecare pas după cum urmează: Î{\ displaystyle Q}

Î[s,la]: =(1-α)Î[s,la]+α(r+γmaxla′Î[s′,la′]){\ displaystyle Q [s, a]: = (1- \ alpha) Q [s, a] + \ alpha \ left (r + \ gamma \ max _ {a '} Q [s', a '] \ right )}}

unde este noua stare, este starea anterioară, este acțiunea aleasă, este recompensa primită de agent, este un număr între 0 și 1, numit factor de învățare și este factorul de actualizare . s′{\ displaystyle s '}s{\ displaystyle s}la{\ displaystyle a}r{\ displaystyle r}α{\ displaystyle \ alpha}γ{\ displaystyle \ gamma}

Un episod al algoritmului se încheie când este o stare finală. Cu toate acestea, - învățarea poate fi aplicată și sarcinilor neepisodice. Dacă factorul de reducere este mai mic de 1, valoarea stării acțiunii este finită chiar și pentru infinit. st+1{\ displaystyle s_ {t + 1}}Î{\ displaystyle Q}Δt{\ displaystyle \ Delta t}

NB: Pentru fiecare stare finală , valoarea lui nu este niciodată actualizată și își menține valoarea inițială. De obicei, este inițializat la zero. sf{\ displaystyle s_ {f}}Î(sf,la){\ displaystyle Q (s_ {f}, a)}Î(sf,la){\ displaystyle Q (s_ {f}, a)}

Pseudo cod

Iată pseudo-codul Q-learning.

initialiser Q[s, a] pour tout état s, toute action a de façon arbitraire, mais Q(état terminal, a) = 0 pour toute action a répéter //début d'un épisode initialiser l'état s répéter //étape d'un épisode choisir une action a depuis s en utilisant la politique spécifiée par Q (par exemple ε-greedy) exécuter l'action a observer la récompense r et l'état s' Q[s, a] := Q[s, a] + α[r + γ maxa' Q(s', a') - Q(s, a)] s := s' a := a' jusqu'à ce que s soit l'état terminal

Influența variabilelor asupra algoritmului

Factorul de învățare

Factorul de învățare determină cât de mult depășesc noile informații calculate pe cele vechi. Dacă = 0, agentul nu învață nimic. În schimb, dacă = 1, agentul ignoră întotdeauna tot ce a învățat și va lua în considerare doar ultima informație. α{\ displaystyle \ alpha}α{\ displaystyle \ alpha}α{\ displaystyle \ alpha}

Într-un mediu determinist, viteza de învățare este optimă. Când problema este stocastică, algoritmul converge în anumite condiții, în funcție de viteza de învățare. În practică, adesea această viteză corespunde pentru întreaga durată a procesului. αt(s,la)=1{\ displaystyle \ alpha _ {t} (s, a) = 1}αt(s,la)=0,1{\ displaystyle \ alpha _ {t} (s, a) = 0.1}

Factor de reducere

Factorul de reducere γ determină mărimea recompenselor viitoare. Un factor 0 ar face agentul miopic luând în considerare doar recompensele actuale, în timp ce un factor apropiat de 1 ar aduce și recompensele mai îndepărtate. Dacă factorul de reducere este apropiat sau egal cu 1, valoarea lui poate fi diferită. Î{\ displaystyle Q}

Extensii și variante

Dublu Q- învățare

Deoarece Q- learning folosește estimatorul maxim, Q- learning supraestimează valoarea acțiunilor și, prin urmare, în medii zgomotoase, învățarea este lentă. Această problemă este rezolvată în varianta numită învățare dublă Q, care folosește două funcții de evaluare și este învățată pe două seturi diferite de experiențe. Actualizarea se face transversal: ÎLA{\ displaystyle Q ^ {A}}ÎB{\ displaystyle Q ^ {B}}

Ît+1LA(st,lat)=ÎtLA(st,lat)+αt(st,lat)(rt+γ ÎtB(st+1,larg mlaXla⁡ÎtLA(st+1,la))-ÎtLA(st,lat)){\ displaystyle Q_ {t + 1} ^ {A} (s_ {t}, a_ {t}) = Q_ {t} ^ {A} (s_ {t}, a_ {t}) + \ alpha _ {t } (s_ {t}, a_ {t}) \ left (r_ {t} + \ gamma ~ Q_ {t} ^ {B} \ left (s_ {t + 1}, \ mathop {\ operatorname {arg ~ max }} _ {a} Q_ {t} ^ {A} (s_ {t + 1}, a) \ right) -Q_ {t} ^ {A} (s_ {t}, a_ {t}) \ right) }, și Ît+1B(st,lat)=ÎtB(st,lat)+αt(st,lat)(rt+γ ÎtLA(st+1,larg mlaXla⁡ÎtB(st+1,la))-ÎtB(st,lat)).{\ displaystyle Q_ {t + 1} ^ {B} (s_ {t}, a_ {t}) = Q_ {t} ^ {B} (s_ {t}, a_ {t}) + \ alpha _ {t } (s_ {t}, a_ {t}) \ left (r_ {t} + \ gamma ~ Q_ {t} ^ {A} \ left (s_ {t + 1}, \ mathop {\ operatorname {arg ~ max }} _ {a} Q_ {t} ^ {B} (s_ {t + 1}, a) \ right) -Q_ {t} ^ {B} (s_ {t}, a_ {t}) \ right) .}

Deoarece valoarea estimată este evaluată utilizând o altă politică, problema supraestimării este rezolvată. Învățarea algoritmului setat se poate face folosind tehnici de învățare profundă, rezultând DQN-uri ( rețele Q profunde ). Apoi putem avea Double DQN, pentru a obține performanțe mai bune decât cu algoritmul DQN original.

Note și referințe

• (fr) Acest articol este preluat parțial sau în totalitate din articolul Wikipedia din limba engleză intitulat „  Q-Learning  ” ( vezi lista autorilor ) .

1. Tambet Matiisen , „  Demystifying Deep Reinforcement Learning | Laboratorul de Neuroștiințe Computaționale  ” , pe neuro.cs.ut.ee ,19 decembrie 2015(accesat la 6 aprilie 2018 )
2. CJ Watkins, Învățând din recompense întârziate , Kings College, Cambridge, mai 1989
3. (în) George F Luger, Inteligența artificială: structuri și strategii pentru rezolvarea problemelor complexe. Ediția a 5-a. , Addison Wesley,2005, 903  p. ( ISBN  0-321-26318-9 , citit online ) , p. 448
4. Watkins și Dayan, Q-learning. Machine Learning , 1992
5. (în) David L. Poole și Alan K. Mackworth , Inteligență artificială , Cambridge University Press ,2009( ISBN  978-0-511-79479-7 , DOI  10.1017 / CBO9780511794797 , citit online ) , p. 469
6. Reinforcement Learning: An Introduction , Richard Sutton și Andrew Barto, MIT Press, 1998.
7. (în) Stuart J. Russell și Peter Norvig , Inteligența artificială: o abordare modernă , Prentice Hall ,2010, A treia  ed. , 1132  p. ( ISBN  978-0-13-604259-4 ) , p.  649
8. Hado van Hasselt , „  Învățarea dublă Q  ”, Progrese în sistemele de procesare a informațiilor neuronale , vol.  23,2011, p.  2613–2622 ( citiți online [PDF] )
9. Hado van Hasselt , Arthur Guez și David Silver , „  Învățare profundă prin întărire cu dublă învățare Q  ”, Conferința AAAI privind inteligența artificială ,2015, p.  2094–2100 ( citiți online [PDF] )

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">