Q-учeње

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

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

Учење подстицајем

Учење подстицајем укључује агента, скуп стања S {\displaystyle S} , и сет акција по стању A {\displaystyle A} . Извођењем радње a ∈ A {\displaystyle a\in A} , агент прелази из стања у стање. Извршавање радње у одређеном стању даје агенту награду (бројчани резултат).

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

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

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

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

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

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

Алгоритам

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

После Δ t {\displaystyle \Delta t} корака у будућност агент ће одлучити о неком следећем кораку. Тежина за овај корак се израчунава као γ Δ t {\displaystyle \gamma ^{\Delta t}} , где γ {\displaystyle \gamma } ( фактор попуста ) је број између 0 и 1 ( 0 ≤ γ ≤ 1 {\displaystyle 0\leq \gamma \leq 1} ) и има ефекат да се награде примљене раније вреднују више од оних које су примљене касније (што одражава вредност „доброг почетка“). γ {\displaystyle \gamma } такође се може тумачити као вероватноћа да се успе (или преживи) на сваком кораку Δ t {\displaystyle \Delta t} .

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

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

Пре него што учење почне, Q {\displaystyle Q} се иницијализује на евентуално произвољну фиксну вредност (коју бира програмер). Затим, сваког тренутка t {\displaystyle t} агент бира акцију a t {\displaystyle a_{t}} , посматра награду r t {\displaystyle r_{t}} , улази у ново стање s t + 1 {\displaystyle s_{t+1}} (то може зависити и од претходног стања s t {\displaystyle s_{t}} и изабрану радњу), и Q {\displaystyle Q} је ажуриран. Срж алгоритма је Беллманова једначина као једноставна итерација вредности, користећи пондерисани просек старе вредности и нове информације:

Q n o v o ( s t , a t ) ← Q ( s t , a t ) ⏟ stara vrednost + α ⏟ stopa učenja ⋅ ( r t ⏟ nagrada + γ ⏟ faktor popusta ⋅ max a Q ( s t + 1 , a ) ⏟ estimacija optimalne buduće vrednosti ⏟ nova vrednost − Q ( s t , a t ) ⏟ stara vrednost ) ⏞ privremena razlika {\displaystyle Q^{novo}(s_{t},a_{t})\leftarrow \underbrace {Q(s_{t},a_{t})} _{\text{stara vrednost}}+\underbrace {\alpha } _{\text{stopa učenja}}\cdot \overbrace {{\bigg (}\underbrace {\underbrace {r_{t}} _{\text{nagrada}}+\underbrace {\gamma } _{\text{faktor popusta}}\cdot \underbrace {\max _{a}Q(s_{t+1},a)} _{\text{estimacija optimalne buduće vrednosti}}} _{\text{nova vrednost}}-\underbrace {Q(s_{t},a_{t})} _{\text{stara vrednost}}{\bigg )}} ^{\text{privremena razlika}}}

где је r t {\displaystyle r_{t}} награда добијена при преласку из стања s t {\displaystyle s_{t}} у стање s t + 1 {\displaystyle s_{t+1}} , и α {\displaystyle \alpha } је стопа учења ( 0 < α ≤ 1 ) {\displaystyle (0<\alpha \leq 1)} .

Обратити пажњу да је Q n o v o ( s t , a t ) {\displaystyle Q^{novo}(s_{t},a_{t})} збир три фактора:

  • ( 1 − α ) Q ( s t , a t ) {\displaystyle (1-\alpha )Q(s_{t},a_{t})}  : тренутна вредност пондерисана стопом учења. Вредности стопе учења близу 1 чине промене у Q {\displaystyle Q} брже.
  • α r t {\displaystyle \alpha \,r_{t}}  : награда r t = r ( s t , a t ) {\displaystyle r_{t}=r(s_{t},a_{t})} се добије ако се акција a t {\displaystyle a_{t}} узима када је у стању s t {\displaystyle s_{t}} (пондерисано стопом учења)
  • α γ max a Q ( s t + 1 , a ) {\displaystyle \alpha \gamma \max _{a}Q(s_{t+1},a)}  : максимална награда која се може добити од стања s t + 1 {\displaystyle s_{t+1}} (пондерисано стопом учења и фактором попуста)

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

За сва коначна стања s f {\displaystyle s_{f}} , Q ( s f , a ) {\displaystyle Q(s_{f},a)} се никада не ажурира, али се поставља на вредност награде r {\displaystyle r} посматрано за стање s f {\displaystyle s_{f}} . У већини случајева, за Q ( s f , a ) {\displaystyle Q(s_{f},a)} се може се узети да је једнако нули.

Утицај промењивих

Стопа учења

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

Фактор попуста

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

Почетни услови ( Q0 )

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

Имплементација

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

Апроксимација функције

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

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

Квантизација

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

Историја

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

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

  • У стању s врши акцију a ;
  • Стање последице примања s' ;
  • Израчунати процену стања v ( s ′ ) {\displaystyle v(s')} ;
  • Ажурирајте вредност "crossbar" w ′ ( a , s ) = w ( a , s ) + v ( s ′ ) {\displaystyle w'(a,s)=w(a,s)+v(s')} .

Термин „секундарно подстицање“ је позајмљен из теорије учења животиња, за моделовање вредности стања путем пропагације уназад : вредност стања v ( s ′ ) {\displaystyle v(s')} ситуационе последице се преноси на претходно наишле ситуације. 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 A {\displaystyle Q^{A}} и Q B {\displaystyle Q^{B}} . Корак двоструког ажурирања Q-учења је тада следећи:

Q t + 1 A ( s t , a t ) = Q t A ( s t , a t ) + α t ( s t , a t ) ( r t + γ Q t B ( s t + 1 , a r g   m a x a ⁡ Q t A ( s t + 1 , a ) ) − Q t A ( s t , a t ) ) {\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)} , и
Q t + 1 B ( s t , a t ) = Q t B ( s t , a t ) + α t ( s t , a t ) ( r t + γ Q t A ( s t + 1 , a r g   m a x a ⁡ Q t B ( s t + 1 , a ) ) − Q t B ( s t , a t ) ) . {\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).}

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

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

Остало

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

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

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

Ограничења

Стандардни алгоритам Q-учења (користећи Q {\displaystyle 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. CS1 одржавање: Формат датума (веза)
  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. CS1 одржавање: Формат датума (веза)
  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. CS1 одржавање: Формат датума (веза)
  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. CS1 одржавање: Формат датума (веза)
  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. CS1 одржавање: Формат датума (веза)
  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. CS1 одржавање: Формат датума (веза)
  16. ^ „Methods and Apparatus for Reinforcement Learning, US Patent #20150100530A1” (PDF). US Patent Office. 9. 4. 2015. Приступљено 28. 7. 2018. CS1 одржавање: Формат датума (веза)
  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. CS1 одржавање: Формат датума (веза)
  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. CS1 одржавање: Формат датума (веза)
  23. ^ Gaskett, Chris; Wettergreen, David; Zelinsky, Alexander (1999). „Q-Learning in Continuous State and Action Spaces” (PDF). 

Спољашње везе

  • Watkins, C.J.C.H. (1989). Learning from Delayed Rewards. PhD thesis, Cambridge University, Cambridge, England.
  • Strehl, Li, Wiewiora, Langford, Littman (2006). PAC model-free reinforcement learning
  • Reinforcement Learning: An Introduction by Richard Sutton and Andrew S. Barto, an online textbook. See "6.5 Q-Learning: Off-Policy TD Control".
  • Piqle: a Generic Java Platform for Reinforcement Learning
  • Reinforcement Learning Maze, a demonstration of guiding an ant through a maze using Q-learning
  • Q-learning work by Gerald Tesauro