Q-učenje

S Vikipedije, slobodne enciklopedije

Q-učenje je bezmodelni algoritam učenja podsticajem za učenje vrednosti akcije u određenom stanju. Ne zahteva model okruženja (dakle „bezmodelni“), i može da se nosi sa problemima sa stohastičkim prelazima i nagradama bez potrebe za prilagođavanjem.

Za bilo koji proces konačnog Markovljevog odlučivanja (PKMO), Q-učenje pronalazi optimalnu politiku u smislu maksimiziranja očekivane vrednosti ukupne nagrade tokom bilo kojeg i svih uzastopnih koraka, počevši od trenutnog stanja. [1] Q-učenje može da identifikuje optimalnu politiku izbora akcije za bilo koji PKMO, dato beskonačno vreme istraživanja i delimično slučajnu politiku. [1] „Q“ se odnosi na funkciju koju algoritam izračunava – očekivane nagrade za akciju preduzetu u datom stanju. [2]

Učenje podsticajem[uredi | uredi izvor]

Učenje podsticajem uključuje agenta, skup stanja , i set akcija po stanju . Izvođenjem radnje , agent prelazi iz stanja u stanje. Izvršavanje radnje u određenom stanju daje agentu nagradu (brojčani rezultat).

Cilj agenta je da maksimizira svoju ukupnu nagradu. To čini tako što nagradi za postizanje trenutnog stanja dodaje maksimalnu nagradu koja se može postići iz budućih stanja, efektivno utičući na trenutnu akciju potencijalnom budućom nagradom. Ova potencijalna nagrada je ponderisani zbir očekivanih vrednosti nagrada svih budućih koraka počevši od trenutnog stanja.

Kao primer, razmotrite proces ukrcavanja u voz, u kome se nagrada meri minusom ukupnog vremena provedenog na ukrcavanje (alternativno, cena ulaska u voz je jednaka vremenu ukrcavanja). Jedna strategija je da uđete na vrata voza čim se otvore, minimizirajući početno vreme čekanja za sebe. Međutim, ako je u vozu gužva, onda ćete imati spor ulazak nakon početne akcije ulaska na vrata dok se ljudi bore da napustite voz dok pokušavate da se ukrcate. Ukupno vreme ukrcavanja ili cena je tada:

  • 0 sekundi vreme čekanja + 15 sekundi vreme borbe

Sledećeg dana, slučajno (istraživanje), odlučujete da sačekate i pustite druge ljude da odu prvi. Ovo u početku dovodi do dužeg vremena čekanja. Međutim, vreme borbe sa drugim putnicima je manje. Zaključujemo, ova staza ima veću nagradu od one prethodnog dana, pošto je ukupno vreme ukrcavanja sada:

  • Vreme čekanja 5 sekundi + vreme borbe 0 sekundi

Kroz istraživanje, uprkos početnoj akciji (strpljenje) koja rezultira većom cenom (ili negativnom nagradom) nego u prisilnoj strategiji, ukupni trošak je niži, što otkriva strategiju koja je isplativija.

Algoritam[uredi | uredi izvor]

Q-učenje tabela stanja po akcijama koja je inicijalizovana na nulu, a zatim se svaka ćelija ažurira kroz obuku.

Posle koraka u budućnost agent će odlučiti o nekom sledećem koraku. Težina za ovaj korak se izračunava kao , gde ( faktor popusta ) je broj između 0 i 1 ( ) i ima efekat da se nagrade primljene ranije vrednuju više od onih koje su primljene kasnije (što odražava vrednost „dobrog početka“). takođe se može tumačiti kao verovatnoća da se uspe (ili preživi) na svakom koraku .

Algoritam, dakle, ima funkciju koja izračunava kvalitet kombinacije stanje-akcija:

.

Pre nego što učenje počne, se inicijalizuje na eventualno proizvoljnu fiksnu vrednost (koju bira programer). Zatim, svakog trenutka agent bira akciju , posmatra nagradu , ulazi u novo stanje (to može zavisiti i od prethodnog stanja i izabranu radnju), i je ažuriran. Srž algoritma je Bellmanova jednačina kao jednostavna iteracija vrednosti, koristeći ponderisani prosek stare vrednosti i nove informacije:

gde je nagrada dobijena pri prelasku iz stanja u stanje , i je stopa učenja .

Obratiti pažnju da je zbir tri faktora:

  •  : trenutna vrednost ponderisana stopom učenja. Vrednosti stope učenja blizu 1 čine promene u brže.
  •  : nagrada se dobije ako se akcija uzima kada je u stanju (ponderisano stopom učenja)
  •  : maksimalna nagrada koja se može dobiti od stanja (ponderisano stopom učenja i faktorom popusta)

Epizoda algoritma se završava kada stanje je konačno ili terminalno stanje . Međutim, Q -učenje može da uči i u neepizodnim zadacima (kao rezultat svojstva konvergentnih beskonačnih serija). Ako je faktor popusta manji od 1, vrednosti akcije su konačne čak i ako problem može da sadrži beskonačne petlje.

Za sva konačna stanja , se nikada ne ažurira, ali se postavlja na vrednost nagrade posmatrano za stanje . U većini slučajeva, za se može se uzeti da je jednako nuli.

Uticaj promenjivih[uredi | uredi izvor]

Stopa učenja[uredi | uredi izvor]

Stopa učenja ili veličina koraka određuju u kojoj meri novostečene informacije nadjačavaju stare informacije. Faktor 0 čini da agent ništa ne nauči (isključivo iskorišćavajući prethodno znanje), dok faktor 1 čini da agent razmatra samo najnovije informacije (zanemarujući prethodno znanje da bi istražio mogućnosti). U potpuno determinističkim okruženjima, stopa učenja od je optimalno. Kada je problem stohastički, algoritam konvergira pod nekim tehničkim uslovima na stopu učenja koji zahtevaju da se smanji na nulu. U praksi se često koristi konstantna stopa učenja, kao na primer za sve . [3]

Faktor popusta[uredi | uredi izvor]

Faktor popusta određuje važnost budućih nagrada. Faktor 0 učiniće agenta "kratkovidim" uzimajući u obzir samo trenutne nagrade, tj. (u pravilu ažuriranja iznad), dok će faktor koji se približava 1 naterati da teži dugoročnoj visokoj nagradi. Ako faktor popusta dostigne ili premaši 1, vrednosti akcija mogu divergirati. Za , bez terminalnog stanja, ili ako agent nikada ne dostigne jedno, sve istorije okruženja postaju beskonačno duge, a izrazi sa aditivnim, nediskontiranim nagradama generalno postaju beskonačne. [4] Čak i sa faktorom popusta koji je samo nešto manji od 1, učenje Q -funkcije dovodi do propagacije grešaka i nestabilnosti kada se funkcija vrednosti aproksimira veštačkom neuronskom mrežom . [5] U tom slučaju, počevši od nižeg popusnog faktora i povećavajući ga ka konačnoj vrednosti, ubrzava se proces učenje. [6]

Početni uslovi ( Q0 )[uredi | uredi izvor]

Q-učenje je iterativni algoritam, implicitno pretpostavlja početni uslov pre nego što se dogodi prvo ažuriranje. Visoke početne vrednosti, poznate i kao "optimistični početni uslovi"[7]. može stimulisati istraživanje: bez obzira koja je akcija izabrana, pravilo ažuriranja će dovesti do toga da ima niže vrednosti od druge alternative, čime se povećava verovatnoća njihovog izbora. Prva nagrada može se koristiti za resetovanje početnih uslova.[8] Prema ovoj ideji, kada prvi put izvršite radnju, nagrada se koristi za podešavanje vrednosti . Ovo omogućava trenutnu obuku u slučaju fiksnih determinističkih nagrada. Očekuje se da će model koji uključuje resetovanje početnih uslova (RPU), predviđaće ponašanje učesnika bolje od modela koji pretpostavlja bilo koje proizvoljno početno stanje (PPS).[8]Čini se da je RPU u skladu sa ljudskim ponašanjem u ponavljajućim eksperimentima binarnog izbora.[8]

Implementacija[uredi | uredi izvor]

Q-učenje u svom najjednostavnijem obliku skladišti podatke u tabele. Ovaj pristup posustaje sa sve većim brojem stanja/akcija jer je verovatnoća da agent poseti određeno stanje i izvrši određenu radnju sve manja.

Aproksimacija funkcije[uredi | uredi izvor]

Q-učenje se može kombinovati sa aproksimacijom funkcije. [9] Ovo omogućava primenu algoritma na veće probleme, čak i kada je prostor stanja kontinuiran.

Jedno rešenje je korišćenje (prilagođene) veštačke neuronske mreže kao aproksimatora funkcije. [10] Aproksimacija funkcije može ubrzati učenje u konačnim problemima, zbog činjenice da algoritam može generalizovati ranija iskustva na prethodno nevidljiva stanja.

Kvantizacija[uredi | uredi izvor]

Druga tehnika za smanjenje prostora stanja/akcije kvantizira moguće vrednosti. Razmotrite primer učenja balansiranja štapa na prstu. Opisivanje stanja u određenom trenutku uključuje položaj prsta u prostoru, njegovu brzinu, ugao štapa i ugaonu brzinu štapa. Ovo daje vektor sa četiri elementa koji opisuje jedno stanje, tj. snimak jednog stanja kodiran u četiri vrednosti. Problem je što je prisutno beskonačno mnogo mogućih stanja. Da biste smanjili mogući prostor stanja, više vrednosti se mogu dodeliti segmentu. Tačna udaljenost prsta od njegove početne pozicije nije poznata, već se zna da li je daleko ili ne (blizu, daleko).

Istorija[uredi | uredi izvor]

Q-učenje je uveo Kris Votkins 1989. godine [11] Dokaz konvergencije izneli su Votkins i Piter Dejan 1992. godine. [12]

Votkins je govorio o naslovu njegove doktorske teze „Učenje iz odloženih nagrada“. Osam godina ranije, 1981. godine, isti problem, pod nazivom „Odloženo učenje sa podsticajem“, rešila je Božinovska "Crossbar Adaptive Array" (CAA) arhitektura. [13] [14] Matrica memorije bila je ista kao osam godina kasnije Q-tabela Q-učenja. Arhitektura je uvela termin „evaluacija stanja“ u učenju sa podsticajem. Algoritam za učenje ukrštenih traka, napisan matematičkim pseudokodom u radu, u svakoj iteraciji obavlja sledeće proračune:

  • U stanju s vrši akciju a ;
  • Stanje posledice primanja s' ;
  • Izračunati procenu stanja ;
  • Ažurirajte vrednost "crossbar" .

Termin „sekundarno podsticanje“ je pozajmljen iz teorije učenja životinja, za modelovanje vrednosti stanja putem propagacije unazad : vrednost stanja situacione posledice se prenosi na prethodno naišle situacije. CAA izračunava vrednosti stanja vertikalno i akcije horizontalno („crossbar“). Demonstracioni grafikoni koji pokazuju odloženo učenje sa podsticajem sadržali su stanja (poželjna, nepoželjna i neutralna stanja), koja su izračunata funkcijom evaluacije stanja. Ovaj sistem učenja je bio preteča algoritma Q-učenja. [15]

Godine 2014. "DeepMind" je patentirao [16] aplikaciju Q-učenja za duboko učenje, pod nazivom „učenje sa dubokim podsticajem“ ili „duboko Q-učenje“ koje može da igra veliki broj Atari 2600 igara na nivou stručnjaka.

Varijante[uredi | uredi izvor]

Duboko Q-učenje[uredi | uredi izvor]

Sistem "DeepMind"-a je koristio duboku konvolucionu neuronsku mrežu, sa slojevima popločanih konvolucionih filtera da oponašaju efekte receptivnih polja. Učenje sa podsticajem je nestabilno ili divergentno kada se aproksimator nelinearne funkcije kao što je neuronska mreža koristi za predstavljanje Q. Ova nestabilnost dolazi od korelacija prisutnih u nizu posmatranja, činjenice da mala ažuriranja Q mogu značajno promeniti politiku agenta i distribuciju podataka, i korelacije između Q i ciljnih vrednosti.

Tehnika je koristila ponavljanje iskustva, biološki inspirisan mehanizam koji koristi nasumični uzorak prethodnih radnji umesto poslednje akcije za nastavak. [2] Ovo uklanja korelacije u sekvenci posmatranja i izravnjava promene u distribuciji podataka. Iterativno ažuriranje prilagođava Q prema ciljnim vrednostima koje se samo periodično ažuriraju, dodatno smanjujući korelacije sa ciljem. [17]

Dvostruko Q-učenje[uredi | uredi izvor]

Pošto se buduća maksimalna približna vrednost radnje u Q-učenju procenjuje korišćenjem iste Q funkcije kao u trenutnoj politici izbora radnji, u okruženjima sa jakim šumom Q-učenje ponekad može preceniti vrednosti akcije, usporavajući učenje. Predložena je varijanta pod nazivom dvostruko Q-učenje da se ovaj problem reši. Dvostruko Q-učenje [18] je algoritam učenja van politike, gde se za procenu vrednosti koristi drugačija politika od one koja se koristi za izbor sledeće akcije.

U praksi, dve odvojene funkcije vrednosti se obučavaju na međusobno simetričan način koristeći odvojena iskustva, i . Korak dvostrukog ažuriranja Q-učenja je tada sledeći:

, i

Sada se procenjena vrednost diskontovane budućnosti procenjuje korišćenjem drugačije politike, što rešava problem precenjivanja.

Ovaj algoritam je kasnije modifikovan 2015. godine i kombinovan sa dubokim učenjem, kao u DQN algoritmu, što rezultira dvostrukim DQN-om (DDQN), koji nadmašuje originalni DQN algoritam. [19]

Ostalo[uredi | uredi izvor]

Odloženo Q-učenje je alternativna implementacija onlajn algoritma Q-učenja, sa verovatno približno tačnim (VPT) učenjem. [20]

Pohlepni GQ (greedy Q) je varijanta Q -učenja koja se koristi u kombinaciji sa (linearnom) aproksimacijom funkcije. [21] Prednost GQ-a je u tome što je konvergencija zagarantovana čak i kada se aproksimacija funkcije koristi za procenu vrednosti akcije.

Distributivno Q-učenje je varijanta Q -učenja koje nastoji da modelira distribuciju nagrada, a ne očekivanu nagradu svake akcije. Primećeno je da olakšava procenu dubokim neuronskim mrežama i može da omogući alternativne metode kontrole, kao što je kontrola osetljiva na rizik. [22]

Ograničenja[uredi | uredi izvor]

Standardni algoritam Q-učenja (koristeći tabelu) važi samo za diskretne radnje i prostore stanja. Diskretizacija ovih vrednosti dovodi do neefikasnog učenja, uglavnom zbog prokletstva dimenzionalnosti. Međutim, postoje adaptacije Q-učenja koje pokušavaju da reše ovaj problem, kao što je Q-učenje putem neuronske mreže. [23]

Vidi još[uredi | uredi izvor]

Reference[uredi | uredi izvor]

  1. ^ a b Melo, Francisco S. „Convergence of Q-learning: a simple proof” (PDF). 
  2. ^ a b Matiisen, Tambet (19. 12. 2015). „Demystifying Deep Reinforcement Learning”. neuro.cs.ut.ee (na jeziku: engleski). Computational Neuroscience Lab. Pristupljeno 2018-04-06. 
  3. ^ Sutton, Richard; Barto, Andrew (1998). Reinforcement Learning: An Introduction. MIT Press. 
  4. ^ Russell, Stuart J.; Norvig, Peter (2010). Artificial Intelligence: A Modern Approach (Third izd.). Prentice Hall. str. 649. ISBN 978-0136042594. 
  5. ^ Baird, Leemon (1995). „Residual algorithms: Reinforcement learning with function approximation” (PDF). ICML: 30—37. 
  6. ^ François-Lavet, Vincent; Fonteneau, Raphael (2015-12-07). „How to Discount Deep Reinforcement Learning: Towards New Dynamic Strategies”. arXiv:1512.02011 Slobodan pristup [cs.LG]. 
  7. ^ Sutton, Richard S.; Barto, Andrew G. „2.7 Optimistic Initial Values”. Reinforcement Learning: An Introduction. Arhivirano iz originala 2013-09-08. g. Pristupljeno 2013-07-18. 
  8. ^ a b v Shteingart, Hanan; Neiman, Tal; Loewenstein, Yonatan (maj 2013). „The role of first impression in operant learning.” (PDF). Journal of Experimental Psychology: General (na jeziku: engleski). 142 (2): 476—488. ISSN 1939-2222. PMID 22924882. doi:10.1037/a0029550. Arhivirano iz originala (PDF) 26. 01. 2021. g. Pristupljeno 14. 04. 2022. 
  9. ^ Hasselt, Hado van (5. 3. 2012). „Reinforcement Learning in Continuous State and Action Spaces”. Ur.: Wiering, Marco; Otterlo, Martijn van. Reinforcement Learning: State-of-the-Art. Springer Science & Business Media. str. 207—251. ISBN 978-3-642-27645-3. 
  10. ^ Tesauro, Gerald (mart 1995). „Temporal Difference Learning and TD-Gammon”. Communications of the ACM. 38 (3): 58—68. doi:10.1145/203330.203343. Pristupljeno 2010-02-08. 
  11. ^ Watkins, C.J.C.H. Learning from Delayed Rewards (PDF) (Teza). University of Cambridge. 
  12. ^ Watkins, Chris; Dayan, Peter (1992). „Q-learning”. Machine Learning. 8 (3–4): 279—292. doi:10.1007/BF00992698 Slobodan pristup. 
  13. ^ Bozinovski, S. (15. 7. 1999). „Crossbar Adaptive Array: The first connectionist network that solved the delayed reinforcement learning problem”. Ur.: Dobnikar, Andrej; Steele, Nigel C.; Pearson, David W.; Albrecht, Rudolf F. Artificial Neural Nets and Genetic Algorithms: Proceedings of the International Conference in Portorož, Slovenia, 1999. Springer Science & Business Media. str. 320—325. ISBN 978-3-211-83364-3. 
  14. ^ Bozinovski, S. (1982). „A self learning system using secondary reinforcement”. Ur.: Trappl, Robert. Cybernetics and Systems Research: Proceedings of the Sixth European Meeting on Cybernetics and Systems Research. North Holland. str. 397—402. ISBN 978-0-444-86488-8. 
  15. ^ Barto, A. (24. 2. 1997). „Reinforcement learning”. Ur.: Omidvar, Omid; Elliott, David L. Neural Systems for Control. Elsevier. ISBN 978-0-08-053739-9. 
  16. ^ „Methods and Apparatus for Reinforcement Learning, US Patent #20150100530A1” (PDF). US Patent Office. 9. 4. 2015. Pristupljeno 28. 7. 2018. 
  17. ^ Mnih, Volodymyr; Kavukcuoglu, Koray; Silver, David; Rusu, Andrei A.; Veness, Joel; Bellemare, Marc G.; Graves, Alex; Riedmiller, Martin; Fidjeland, Andreas K. (februar 2015). „Human-level control through deep reinforcement learning”. Nature (na jeziku: engleski). 518 (7540): 529—533. Bibcode:2015Natur.518..529M. ISSN 0028-0836. PMID 25719670. doi:10.1038/nature14236. 
  18. ^ van Hasselt, Hado (2011). „Double Q-learning” (PDF). Advances in Neural Information Processing Systems. 23: 2613—2622. 
  19. ^ van Hasselt, Hado; Guez, Arthur; Silver, David (2015). „Deep reinforcement learning with double Q-learning”. AAAI Conference on Artificial Intelligence: 2094—2100. arXiv:1509.06461 Slobodan pristup. Arhivirano iz originala (PDF) 06. 02. 2020. g. Pristupljeno 14. 04. 2022. 
  20. ^ Strehl, Alexander L.; Li, Lihong; Wiewiora, Eric; Langford, John; Littman, Michael L. (2006). „Pac model-free reinforcement learning” (PDF). Proc. 22nd ICML: 881—888. 
  21. ^ Maei, Hamid; Szepesvári, Csaba; Bhatnagar, Shalabh; Sutton, Richard (2010). „Toward off-policy learning control with function approximation in Proceedings of the 27th International Conference on Machine Learning” (PDF). str. 719—726. Arhivirano iz originala (PDF) 2012-09-08. g. Pristupljeno 2016-01-25. 
  22. ^ Hessel, Matteo; Modayil, Joseph; van Hasselt, Hado; Schaul, Tom; Ostrovski, Georg; Dabney, Will; Horgan, Dan; Piot, Bilal; Azar, Mohammad (februar 2018). „Rainbow: Combining Improvements in Deep Reinforcement Learning”. AAAI Conference on Artificial Intelligence. arXiv:1710.02298 Slobodan pristup. Pristupljeno 16. 9. 2021. 
  23. ^ Gaskett, Chris; Wettergreen, David; Zelinsky, Alexander (1999). „Q-Learning in Continuous State and Action Spaces” (PDF). 

Spoljašnje veze[uredi | uredi izvor]

Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Q-учeње&oldid=27063651”