Inteligență artificială
IA simbolică
Căutarea spațiului de stare Planificare automatizată Căutare combinatorială Sistem expert Reprezentarea cunoașterii Sistem bazat pe cunoaștere
Conecționism
Rețele neuronale
Viață artificială
IA distribuită Programare genetică Algoritm genetic Inteligență „roi” Ființă artificială
Metoda empirică Bayes
Rețea neurală Rețea bayesiană Învățare automată Recunoașterea tiparelor Învățare profundă
Sisteme Fuzzy
Logică fuzzy Electronică fuzzy
Filosofie
IA puternică IA slabă Conștiință artificială Test Turing Etică Risc existențial
Glosar
Glosar
Vezi și
IA generativă Listă de companii Xenoboți Singularitate tehnologică Legea întoarcerilor accelerate Vasiliscul lui Roko Inteligența artificială în ficțiune Superinteligența. Căi, pericole, strategii The Precipice: Existential Risk and the Future of Humanity
v d m

Q-learning este un algoritm de învățare prin recompensă (reinforcement learning) care antrenează un agent să atribuie valori acțiunilor posibile, în funcție de starea curentă, fără a necesita un model al mediului (este model-free). Poate gestiona probleme cu tranziții și recompense stocastice, fără a necesita adaptări suplimentare.

De exemplu, într-un labirint sub formă de grilă, un agent învață să ajungă la o ieșire care valorează 10 puncte. La o intersecție, Q-learning ar putea atribui o valoare mai mare acțiunii de a merge spre dreapta decât spre stânga, dacă dreapta duce mai repede la ieșire, îmbunătățindu-și astfel alegerea prin testarea ambelor direcții în timp.

Pentru orice proces decizional Markovian finit (finite Markov decision process), Q-learning găsește o politică optimă în sensul maximizării valorii așteptate a recompensei totale pe oricare și toate pașii succesivi, începând din starea curentă.[2] Q-learning poate identifica o politică optimă de selecție a acțiunilor pentru orice astfel de proces decizional finit, cu condiția unui timp de explorare infinit și a unei politici parțial aleatorii.

„Q” se referă la funcția pe care algoritmul o calculează: recompensa așteptată – adică calitatea – unei acțiuni efectuate într-o stare dată.^[1]

Învățarea prin întărire implică un agent, un set de stări S, și un set A de acțiuni posibile pentru fiecare stare. Prin executarea unei acțiuni a∈A, agentul face tranziții între stări. Realizarea unei acțiuni într-o stare anume oferă agentului o recompensă (un scor numeric).

Scopul agentului este să maximizeze recompensa totală. Pentru a face acest lucru, agentul adaugă recompensa obținută în starea curentă la recompensa maximă posibilă din stările viitoare, influențând astfel acțiunea actuală prin potențialele recompense viitoare. Această recompensă potențială este o sumă ponderată a valorilor așteptate ale recompenselor tuturor pașilor viitori, începând din starea actuală.^[2]

Să luăm ca exemplu procesul de îmbarcare într-un tren, unde recompensa este exprimată ca fiind negativul timpului total petrecut pentru îmbarcare (alternativ, costul îmbarcării este egal cu durata acesteia). O strategie este să intri imediat ce ușile trenului se deschid, minimizând timpul de așteptare inițial. Totuși, dacă trenul este aglomerat, vei înainta greu după ce ai intrat, deoarece alți pasageri vor încerca să coboare în același timp.

După un număr de pași Δt în viitor, agentul va decide următoarea acțiune. Ponderea acestei acțiuni se calculează ca γΔt, unde γ (factorul de reducere sau discount factor) este un număr între 0 și 1, adică 0≤γ≤1. Dacă γ<1, aceasta are efectul de a valora mai mult recompensele obținute mai devreme, reflectând importanța unui „început bun”. γ poate fi interpretat și ca probabilitatea de a reuși (sau de a supraviețui) la fiecare pas Δt.

Algoritmul utilizează o funcție care calculează calitatea unei combinații stare–acțiune:

${\displaystyle Q:{\mathcal {S}}\times {\mathcal {A}}\to \mathbb {R} }$.

Înainte de începerea procesului de învățare, funcția Q este inițializată cu o valoare fixă (aleasă de programator). Apoi, la fiecare moment de timp t, agentul:

1. Alege o acțiune At​

Linia 35 ⟶ 34:

1. Actualizează funcția Q

Actualizarea Q se face cu o variantă simplificată a ecuației Bellman, care folosește o medie ponderată între valoarea curentă și informația nouă:^[3]

${\displaystyle Q^{new}(S_{t},A_{t})\leftarrow (1-\underbrace {\alpha } _{\text{learning rate}})\cdot \underbrace {Q(S_{t},A_{t})} _{\text{current value}}+\underbrace {\alpha } _{\text{learning rate}}\cdot {\bigg (}\underbrace {\underbrace {R_{t+1}} _{\text{reward}}+\underbrace {\gamma } _{\text{discount factor}}\cdot \underbrace {\max _{a}Q(S_{t+1},a)} _{\text{estimate of optimal future value}}} _{\text{new value (temporal difference target)}}{\bigg )}}$

unde: Linia 42 ⟶ 41:

• α este rata de învățare, cuprinsă între ${\displaystyle (0<\alpha \leq 1)}$.

• (1−α)⋅Q(St​,At​): valoarea actuală, ponderată cu (1 - rata de învățare)
• α⋅Rt+1​: recompensa primită, ponderată cu rata de învățare
• α⋅γ⋅maxa​Q(St+1​,a): valoarea estimată maximă din starea următoare, ponderată cu rata de învățare și factorul de reducere

Un episod se încheie când agentul ajunge într-o stare finală St+1​. Totuși, Q-learning poate învăța și în sarcini ne-episodice, datorită proprietății de convergență a seriilor infinite. Dacă γ<1, valorile Q rămân finite, chiar dacă există bucle infinite în problemă.

Pentru toate stările finale sf​, valorile Q(sf​,a) nu sunt actualizate, ci sunt setate direct la valoarea recompensei r observate în acea stare. În majoritatea cazurilor, se poate considera că Q(sf​,a)=0.

Linia 75 ⟶ 74: Dacă γ≥1, valorile acțiunilor pot diverge.

Pentru γ=1, dacă nu există o stare finală sau agentul nu ajunge niciodată la una, toate traseele posibile devin infinit de lungi, iar utilitățile obținute din recompense aditive (nediscountate) devin, în general, infinite.^[4]

Chiar și cu un factor de reducere doar ușor mai mic decât 1, învățarea funcției Q poate duce la propagarea erorilor și instabilități, mai ales atunci când funcția de valoare este aproximată cu o rețea neuronală artificială.

În acest caz, pornirea cu un factor de reducere mai mic și creșterea sa progresivă accelerează procesul de învățare.^[5]

Deoarece Q-learning este un algoritm iterativ, el presupune implicit o condiție inițială înainte de prima actualizare.

Valori inițiale ridicate – cunoscute drept „condiții inițiale optimiste” – pot încuraja explorarea: indiferent de acțiunea selectată, regula de actualizare o va penaliza (va scădea valoarea), ceea ce face ca alte acțiuni să devină mai atractive în alegerile viitoare.^[6]

Prima recompensă r poate fi folosită pentru a reseta condițiile inițiale.^[7] Prima recompensă r poate fi folosită pentru a reseta condițiile inițiale.

Potrivit acestei idei, prima dată când o acțiune este aleasă, recompensa obținută este folosită pentru a seta valoarea funcției Q. Linia 92 ⟶ 91: Aceasta permite o învățare imediată în cazul în care recompensele sunt fixe și deterministe.

Un model care include resetarea condițiilor inițiale (RIC) se așteaptă să prezică mai bine comportamentul participanților decât un model care presupune condiții inițiale arbitrare (AIC).^[7]

RIC pare a fi consisten cu comportamentul uman observat în experimente repetate cu alegeri binare.^[7]

Linia 102 ⟶ 101:

Q-learning poate fi combinat cu aproximarea funcțiilor.^[8] Q-learning poate fi combinat cu aproximarea funcțiilor.

Aceasta permite aplicarea algoritmului la probleme mai mari, chiar și atunci când spațiul stărilor este continuu.^[9]

• O soluție este folosirea unei rețele neuronale artificiale adaptate ca aproximator de funcție.
• O altă posibilitate este integrarea Interpolării Regulilor Fuzzy (FRI) și utilizarea de baze de reguli fuzzy rare, în locul tabelelor Q discrete sau rețelelor neuronale. Avantajul acestei metode este că oferă o formă de reprezentare a cunoștințelor ușor de înțeles pentru oameni.^[10]

Aproximarea funcțiilor poate accelera învățarea în probleme finite, deoarece algoritmul poate generaliza experiențele anterioare la stări nevizitate anterior. Linia 121 ⟶ 120:

• viteza acestuia,
• unghiul bățului,
• viteza unghiulară a bățului.

Acestea formează un vector cu patru elemente, care codifică o fotografie a stării în acel moment. Problema este că există infinit de multe stări posibile. Linia 127 ⟶ 126: Pentru a reduce spațiul de căutare, valorile pot fi împărțite în intervale (bucket-uri).

De exemplu, distanța exactă a degetului față de poziția inițială (de la -∞ la +∞) nu este stocată, ci doar dacă este departe sau aproape (Aproape, Departe).^[11]

Q-learning a fost introdus de Chris Watkins în 1989.^[12]

O demonstrație de convergență a fost prezentată de Watkins și Peter Dayan în 1992.^[13]

Watkins aborda problema „Învățării din recompense întârziate”, titlul tezei sale de doctorat. Cu opt ani mai devreme, în 1981, aceeași problemă — sub denumirea de „învățare prin întărire întârziată” — fusese rezolvată prin sistemul Crossbar Adaptive Array (CAA) al lui Bozinovski.^[14][15]

Matricea de memorie W=‖w(a,s)‖ era echivalentă cu ceea ce avea să devină mai târziu tabela Q în Q-learning. Linia 140 ⟶ 139: Arhitectura CAA a introdus pentru prima dată termenul de „evaluare a stării” în învățarea prin întărire.

Algoritmul de învățare crossbar, exprimat în pseudocod matematic în articolul original, efectua următorii pași la fiecare iterație:

1. În starea s, se execută acțiunea a;

Linia 147 ⟶ 146:

1. Se actualizează valoarea în rețea: w′(a,s)=w(a,s)+v(s′).

Termenul „întărire secundară” este împrumutat din teoria învățării la animale, fiind utilizat pentru a modela valorile stărilor prin propagare inversă:

Valoarea stării v(s′) a unei situații rezultate este propagată înapoi la stările anterioare. Linia 155 ⟶ 154: Graficele de demonstrare a învățării prin întărire întârziată conțineau stări dezirabile, nedorite și neutre, evaluate prin funcția de evaluare a stării.

Acest sistem de învățare a fost un predecesor direct al algoritmului Q-learning.^[16]

În 2014, Google DeepMind a patentat^[17] o aplicație a Q-learning în învățarea profundă (deep learning), intitulată „deep reinforcement learning” sau „deep Q-learning”, capabilă să joace jocuri Atari 2600 la un nivel comparabil cu cel al experților umani.

Sistemul DeepMind a folosit o rețea neuronală convoluțională profundă, cu straturi de filtre convoluționale distribuite (tiled), pentru a imita efectele câmpurilor receptive.

Învățarea prin întărire devine instabilă sau divergentă atunci când se folosește un aproximator de funcție neliniar, cum este o rețea neuronală, pentru a reprezenta Q.

Această instabilitate apare din cauza:

• corelațiilor prezente în secvența de observații;
• faptului că modificări mici ale lui Q pot schimba semnificativ politica agentului și distribuția datelor;
• existenței de corelații între Q și valorile-țintă.

Această metodă poate fi utilizată pentru căutare stocastică în diverse domenii și aplicații.^[2][18] Această metodă poate fi utilizată pentru căutare stocastică în diverse domenii și aplicații.

Tehnica a utilizat replay al experienței (experience replay) — un mecanism inspirat biologic, care selectează aleatoriu acțiuni anterioare în loc să folosească doar cea mai recentă acțiune.

Aceasta elimină corelațiile din secvențele de observații și netezește schimbările din distribuția datelor. Actualizările iterative ajustează Q către valori-țintă care sunt actualizate periodic, reducând astfel corelațiile cu valoarea-țintă.^[19]

În Q-learning clasic, valoarea acțiunii maxime viitoare este evaluată folosind aceeași funcție Q ca și cea utilizată pentru selectarea acțiunii curente.

În medii zgomotoase, acest lucru poate duce la supraestimarea valorilor acțiunilor, ceea ce încetinește învățarea.

Pentru a corecta acest comportament, a fost propusă o variantă numită Double Q-learning.

Double Q-learning^[20] este un algoritm off-policy de învățare prin întărire, în care separarea politicii de evaluare a valorii față de politica de alegere a acțiunii reduce erorile de estimare.

În practică, se antrenează două funcții de valoare separate, notate:

• Q^A
• QA
• Q^B
• QB

Acestea sunt antrenate simetric și independent, folosind experiențe separate.

Pasul de actualizare în Double Q-learning este astfel modificat pentru a reduce părtinirile din estimarea valorilor maxime. Linia 198 ⟶ 197:

și

${\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).}$

Acum, valoarea estimată a viitorului (atenuat prin factorul de reducere) este evaluată folosind o politică diferită, ceea ce rezolvă problema supraestimării. Acest algoritm a fost ulterior modificat în 2015 și combinat cu învățarea profundă (deep learning),^[21] așa cum se întâmplă în algoritmul DQN, rezultând Double DQN, care depășește performanțele algoritmului DQN original.^[22]

Delayed Q-learning este o implementare alternativă a algoritmului Q-learning online, cu învățare probabil aproximativ corectă (PAC – Probably Approximately Correct).^[23] Greedy GQ este o variantă a Q-learning destinată utilizării în combinație cu aproximația funcțională (liniară).^[24] Avantajul Greedy GQ este că convergența este garantată, chiar și atunci când aproximația funcțională este folosită pentru a estima valorile acțiunilor. Distributional Q-learning este o variantă a Q-learning care caută să modeleze distribuția recompenselor (returns) în loc de valoarea așteptată a fiecărei acțiuni. S-a observat că această metodă facilitează estimarea prin rețele neuronale profunde și poate permite metode alternative de control, cum ar fi controlul sensibil la risc.^[25]

Q-learning a fost propus și în contextul multi-agent (vezi Secțiunea 4.1.2 din "^[26]"). O abordare constă în a presupune că mediul este pasiv.^[27] Littman propune algoritmul minimax Q-learning.^[28]

Algoritmul Q-learning standard (folosind un Q-table) se aplică doar pentru spații de acțiuni și stări discrete. Discretizarea acestor valori duce la învățare ineficientă, în mare parte din cauza blestemului dimensionalității (curse of dimensionality). Totuși, există adaptări ale Q-learning care încearcă să rezolve această problemă, cum ar fi Wire-fitted Neural Network Q-Learning.^[29]

• Convoluție
• Învățarea profundă
• Teoria jocurilor (Game theory)

---