Q-учeње

С Википедије, слободне енциклопедије

Q-учење је безмоделни алгоритам учења подстицајем за учење вредности акције у одређеном стању. Не захтева модел окружења (дакле „безмоделни“), и може да се носи са проблемима са стохастичким прелазима и наградама без потребе за прилагођавањем.

За било који процес коначног Марковљевог одлучивања (ПКМО), Q-учење проналази оптималну политику у смислу максимизирања очекиване вредности укупне награде током било којег и свих узастопних корака, почевши од тренутног стања. [1] Q-учење може да идентификује оптималну политику избора акције за било који ПКМО, дато бесконачно време истраживања и делимично случајну политику. [1] „Q“ се односи на функцију коју алгоритам израчунава – очекиване награде за акцију предузету у датом стању. [2]

Учење подстицајем[уреди | уреди извор]

Учење подстицајем укључује агента, скуп стања , и сет акција по стању . Извођењем радње , агент прелази из стања у стање. Извршавање радње у одређеном стању даје агенту награду (бројчани резултат).

Циљ агента је да максимизира своју укупну награду. То чини тако што награди за постизање тренутног стања додаје максималну награду која се може постићи из будућих стања, ефективно утичући на тренутну акцију потенцијалном будућом наградом. Ова потенцијална награда је пондерисани збир очекиваних вредности награда свих будућих корака почевши од тренутног стања.

Као пример, размотрите процес укрцавања у воз, у коме се награда мери минусом укупног времена проведеног на укрцавање (алтернативно, цена уласка у воз је једнака времену укрцавања). Једна стратегија је да уђете на врата воза чим се отворе, минимизирајући почетно време чекања за себе. Међутим, ако је у возу гужва, онда ћете имати спор улазак након почетне акције уласка на врата док се људи боре да напустите воз док покушавате да се укрцате. Укупно време укрцавања или цена је тада:

  • 0 секунди време чекања + 15 секунди време борбе

Следећег дана, случајно (истраживање), одлучујете да сачекате и пустите друге људе да оду први. Ово у почетку доводи до дужег времена чекања. Међутим, време борбе са другим путницима је мање. Закључујемо, ова стаза има већу награду од оне претходног дана, пошто је укупно време укрцавања сада:

  • Време чекања 5 секунди + време борбе 0 секунди

Кроз истраживање, упркос почетној акцији (стрпљење) која резултира већом ценом (или негативном наградом) него у присилној стратегији, укупни трошак је нижи, што открива стратегију која је исплативија.

Алгоритам[уреди | уреди извор]

Q-учење табела стања по акцијама која је иницијализована на нулу, а затим се свака ћелија ажурира кроз обуку.

После корака у будућност агент ће одлучити о неком следећем кораку. Тежина за овај корак се израчунава као , где ( фактор попуста ) је број између 0 и 1 ( ) и има ефекат да се награде примљене раније вреднују више од оних које су примљене касније (што одражава вредност „доброг почетка“). такође се може тумачити као вероватноћа да се успе (или преживи) на сваком кораку .

Алгоритам, дакле, има функцију која израчунава квалитет комбинације стање-акција:

.

Пре него што учење почне, се иницијализује на евентуално произвољну фиксну вредност (коју бира програмер). Затим, сваког тренутка агент бира акцију , посматра награду , улази у ново стање (то може зависити и од претходног стања и изабрану радњу), и је ажуриран. Срж алгоритма је Беллманова једначина као једноставна итерација вредности, користећи пондерисани просек старе вредности и нове информације:

где је награда добијена при преласку из стања у стање , и је стопа учења .

Обратити пажњу да је збир три фактора:

  •  : тренутна вредност пондерисана стопом учења. Вредности стопе учења близу 1 чине промене у брже.
  •  : награда се добије ако се акција узима када је у стању (пондерисано стопом учења)
  •  : максимална награда која се може добити од стања (пондерисано стопом учења и фактором попуста)

Епизода алгоритма се завршава када стање је коначно или терминално стање . Међутим, Q -учење може да учи и у неепизодним задацима (као резултат својства конвергентних бесконачних серија). Ако је фактор попуста мањи од 1, вредности акције су коначне чак и ако проблем може да садржи бесконачне петље.

За сва коначна стања , се никада не ажурира, али се поставља на вредност награде посматрано за стање . У већини случајева, за се може се узети да је једнако нули.

Утицај промењивих[уреди | уреди извор]

Стопа учења[уреди | уреди извор]

Стопа учења или величина корака одређују у којој мери новостечене информације надјачавају старе информације. Фактор 0 чини да агент ништа не научи (искључиво искоришћавајући претходно знање), док фактор 1 чини да агент разматра само најновије информације (занемарујући претходно знање да би истражио могућности). У потпуно детерминистичким окружењима, стопа учења од је оптимално. Када је проблем стохастички, алгоритам конвергира под неким техничким условима на стопу учења који захтевају да се смањи на нулу. У пракси се често користи константна стопа учења, као на пример за све . [3]

Фактор попуста[уреди | уреди извор]

Фактор попуста одређује важност будућих награда. Фактор 0 учиниће агента "кратковидим" узимајући у обзир само тренутне награде, тј. (у правилу ажурирања изнад), док ће фактор који се приближава 1 натерати да тежи дугорочној високој награди. Ако фактор попуста достигне или премаши 1, вредности акција могу дивергирати. За , без терминалног стања, или ако агент никада не достигне једно, све историје окружења постају бесконачно дуге, а изрази са адитивним, недисконтираним наградама генерално постају бесконачне. [4] Чак и са фактором попуста који је само нешто мањи од 1, учење Q -функције доводи до пропагације грешака и нестабилности када се функција вредности апроксимира вештачком неуронском мрежом . [5] У том случају, почевши од нижег попусног фактора и повећавајући га ка коначној вредности, убрзава се процес учење. [6]

Почетни услови ( Q0 )[уреди | уреди извор]

Q-учење је итеративни алгоритам, имплицитно претпоставља почетни услов пре него што се догоди прво ажурирање. Високе почетне вредности, познате и као "оптимистични почетни услови"[7]. може стимулисати истраживање: без обзира која је акција изабрана, правило ажурирања ће довести до тога да има ниже вредности од друге алтернативе, чиме се повећава вероватноћа њиховог избора. Прва награда може се користити за ресетовање почетних услова.[8] Према овој идеји, када први пут извршите радњу, награда се користи за подешавање вредности . Ово омогућава тренутну обуку у случају фиксних детерминистичких награда. Очекује се да ће модел који укључује ресетовање почетних услова (РПУ), предвиђаће понашање учесника боље од модела који претпоставља било које произвољно почетно стање (ППС).[8]Чини се да је РПУ у складу са људским понашањем у понављајућим експериментима бинарног избора.[8]

Имплементација[уреди | уреди извор]

Q-учење у свом најједноставнијем облику складишти податке у табеле. Овај приступ посустаје са све већим бројем стања/акција јер је вероватноћа да агент посети одређено стање и изврши одређену радњу све мања.

Апроксимација функције[уреди | уреди извор]

Q-учење се може комбиновати са апроксимацијом функције. [9] Ово омогућава примену алгоритма на веће проблеме, чак и када је простор стања континуиран.

Једно решење је коришћење (прилагођене) вештачке неуронске мреже као апроксиматора функције. [10] Апроксимација функције може убрзати учење у коначним проблемима, због чињенице да алгоритам може генерализовати ранија искуства на претходно невидљива стања.

Квантизација[уреди | уреди извор]

Друга техника за смањење простора стања/акције квантизира могуће вредности. Размотрите пример учења балансирања штапа на прсту. Описивање стања у одређеном тренутку укључује положај прста у простору, његову брзину, угао штапа и угаону брзину штапа. Ово даје вектор са четири елемента који описује једно стање, тј. снимак једног стања кодиран у четири вредности. Проблем је што је присутно бесконачно много могућих стања. Да бисте смањили могући простор стања, више вредности се могу доделити сегменту. Тачна удаљеност прста од његове почетне позиције није позната, већ се зна да ли је далеко или не (близу, далеко).

Историја[уреди | уреди извор]

Q-учење је увео Крис Воткинс 1989. године [11] Доказ конвергенције изнели су Воткинс и Питер Дејан 1992. године. [12]

Воткинс је говорио о наслову његове докторске тезе „Учење из одложених награда“. Осам година раније, 1981. године, исти проблем, под називом „Одложено учење са подстицајем“, решиla је Божиновска "Crossbar Adaptive Array" (CAA) архитектура. [13] [14] Матрица меморије била је иста као осам година касније Q-табела Q-учења. Архитектура је увела термин „евалуација стања“ у учењу са подстицајем. Алгоритам за учење укрштених трака, написан математичким псеудокодом у раду, у свакој итерацији обавља следеће прорачуне:

  • У стању s врши акцију a ;
  • Стање последице примања s' ;
  • Израчунати процену стања ;
  • Ажурирајте вредност "crossbar" .

Термин „секундарно подстицање“ је позајмљен из теорије учења животиња, за моделовање вредности стања путем пропагације уназад : вредност стања ситуационе последице се преноси на претходно наишле ситуације. CAA израчунава вредности стања вертикално и акције хоризонтално („crossbar“). Демонстрациони графикони који показују одложено учење са подстицајем садржали су стања (пожељна, непожељна и неутрална стања), која су израчуната функцијом евалуације стања. Овај систем учења је био претеча алгоритма Q-учења. [15]

Године 2014. "DeepMind" је патентирао [16] апликацију Q-учења за дубоко учење, под називом „учење са дубоким подстицајем“ или „дубоко Q-учење“ које може да игра велики број Атари 2600 игара на нивоу стручњака.

Варијанте[уреди | уреди извор]

Дубоко Q-учење[уреди | уреди извор]

Систем "DeepMind"-а је користио дубоку конволуциону неуронску мрежу, са слојевима поплочаних конволуционих филтера да опонашају ефекте рецептивних поља. Учење са подстицајем је нестабилно или дивергентно када се апроксиматор нелинеарне функције као што је неуронска мрежа користи за представљање Q. Ова нестабилност долази од корелација присутних у низу посматрања, чињенице да мала ажурирања Q могу значајно променити политику агента и дистрибуцију података, и корелације између Q и циљних вредности.

Техника је користила понављање искуства, биолошки инспирисан механизам који користи насумични узорак претходних радњи уместо последње акције за наставак. [2] Ово уклања корелације у секвенци посматрања и изравњава промене у дистрибуцији података. Итеративно ажурирање прилагођава Q према циљним вредностима које се само периодично ажурирају, додатно смањујући корелације са циљем. [17]

Двоструко Q-учење[уреди | уреди извор]

Пошто се будућа максимална приближна вредност радње у Q-учењу процењује коришћењем исте Q функције као у тренутној политици избора радњи, у окружењима са јаким шумом Q-учење понекад може преценити вредности акције, успоравајући учење. Предложена је варијанта под називом двоструко Q-учење да се овај проблем реши. Двоструко Q-учење [18] је алгоритам учења ван политике, где се за процену вредности користи другачија политика од оне која се користи за избор следеће акције.

У пракси, две одвојене функције вредности се обучавају на међусобно симетричан начин користећи одвојена искуства, и . Корак двоструког ажурирања Q-учења је тада следећи:

, и

Сада се процењена вредност дисконтоване будућности процењује коришћењем другачије политике, што решава проблем прецењивања.

Овај алгоритам је касније модификован 2015. године и комбинован са дубоким учењем, као у DQN алгоритму, што резултира двоструким DQN-ом (DDQN), који надмашује оригинални DQN алгоритам. [19]

Остало[уреди | уреди извор]

Одложено Q-учење је алтернативна имплементација онлајн алгоритма Q-учења, са вероватно приближно тачним (ВПТ) учењем. [20]

Похлепни GQ (greedy Q) је варијанта Q -учења која се користи у комбинацији са (линеарном) апроксимацијом функцијe. [21] Предност GQ-a је у томе што је конвергенција загарантована чак и када се апроксимација функције користи за процену вредности акције.

Дистрибутивно Q-учење је варијанта Q -учења које настоји да моделира дистрибуцију награда, а не очекивану награду сваке акције. Примећено је да олакшава процену дубоким неуронским мрежама и може да омогући алтернативне методе контроле, као што је контрола осетљива на ризик. [22]

Ограничења[уреди | уреди извор]

Стандардни алгоритам Q-учења (користећи табелу) важи само за дискретне радње и просторе стања. Дискретизација ових вредности доводи до неефикасног учења, углавном због проклетства димензионалности. Међутим, постоје адаптације Q-учења које покушавају да реше овај проблем, као што је Q-учење путем неуронске мреже. [23]

Види још[уреди | уреди извор]

Референце[уреди | уреди извор]

  1. ^ а б Melo, Francisco S. „Convergence of Q-learning: a simple proof” (PDF). 
  2. ^ а б Matiisen, Tambet (19. 12. 2015). „Demystifying Deep Reinforcement Learning”. neuro.cs.ut.ee (на језику: енглески). Computational Neuroscience Lab. Приступљено 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 изд.). Prentice Hall. стр. 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Слободан приступ [cs.LG]. 
  7. ^ Sutton, Richard S.; Barto, Andrew G. „2.7 Optimistic Initial Values”. Reinforcement Learning: An Introduction. Архивирано из оригинала 2013-09-08. г. Приступљено 2013-07-18. 
  8. ^ а б в Shteingart, Hanan; Neiman, Tal; Loewenstein, Yonatan (мај 2013). „The role of first impression in operant learning.” (PDF). Journal of Experimental Psychology: General (на језику: енглески). 142 (2): 476—488. ISSN 1939-2222. PMID 22924882. doi:10.1037/a0029550. Архивирано из оригинала (PDF) 26. 01. 2021. г. Приступљено 14. 04. 2022. 
  9. ^ Hasselt, Hado van (5. 3. 2012). „Reinforcement Learning in Continuous State and Action Spaces”. Ур.: Wiering, Marco; Otterlo, Martijn van. Reinforcement Learning: State-of-the-Art. Springer Science & Business Media. стр. 207—251. ISBN 978-3-642-27645-3. 
  10. ^ Tesauro, Gerald (март 1995). „Temporal Difference Learning and TD-Gammon”. Communications of the ACM. 38 (3): 58—68. doi:10.1145/203330.203343. Приступљено 2010-02-08. 
  11. ^ Watkins, C.J.C.H. Learning from Delayed Rewards (PDF) (Теза). University of Cambridge. 
  12. ^ Watkins, Chris; Dayan, Peter (1992). „Q-learning”. Machine Learning. 8 (3–4): 279—292. doi:10.1007/BF00992698Слободан приступ. 
  13. ^ Bozinovski, S. (15. 7. 1999). „Crossbar Adaptive Array: The first connectionist network that solved the delayed reinforcement learning problem”. Ур.: 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. стр. 320—325. ISBN 978-3-211-83364-3. 
  14. ^ Bozinovski, S. (1982). „A self learning system using secondary reinforcement”. Ур.: Trappl, Robert. Cybernetics and Systems Research: Proceedings of the Sixth European Meeting on Cybernetics and Systems Research. North Holland. стр. 397—402. ISBN 978-0-444-86488-8. 
  15. ^ Barto, A. (24. 2. 1997). „Reinforcement learning”. Ур.: 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. Приступљено 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. (фебруар 2015). „Human-level control through deep reinforcement learning”. Nature (на језику: енглески). 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Слободан приступ. Архивирано из оригинала (PDF) 06. 02. 2020. г. Приступљено 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). стр. 719—726. Архивирано из оригинала (PDF) 2012-09-08. г. Приступљено 2016-01-25. 
  22. ^ Hessel, Matteo; Modayil, Joseph; van Hasselt, Hado; Schaul, Tom; Ostrovski, Georg; Dabney, Will; Horgan, Dan; Piot, Bilal; Azar, Mohammad (фебруар 2018). „Rainbow: Combining Improvements in Deep Reinforcement Learning”. AAAI Conference on Artificial Intelligence. arXiv:1710.02298Слободан приступ. Приступљено 16. 9. 2021. 
  23. ^ Gaskett, Chris; Wettergreen, David; Zelinsky, Alexander (1999). „Q-Learning in Continuous State and Action Spaces” (PDF). 

Спољашње везе[уреди | уреди извор]