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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle Q^{novo}(s_t,a_t)\leftarrow \underset{\text{stara vrednost}}{\underbrace{Q(s_t,a_t)}}+\underset{\text{stopa učenja}}{\underbrace{\alpha }}\cdot \stackrel{\text{privremena razlika}}{\overbrace{(\underset{\text{nova vrednost}}{\underbrace{\underset{\text{nagrada}}{\underbrace{r_t}}+\underset{\text{faktor popusta}}{\underbrace{\gamma }}\cdot \underset{\text{estimacija optimalne buduće vrednosti}}{\underbrace{\underset{a}{max}Q(s_{t+1},a)}}}}-\underset{\text{stara vrednost}}{\underbrace{Q(s_t,a_t)}})}}}$

где је${\displaystyle r_t}$ награда добијена при преласку из стања${\displaystyle s_t}$ у стање${\displaystyle s_{t+1}}$, и${\displaystyle \alpha }$ је стопа учења .

Обратити пажњу да је${\displaystyle Q^{novo}(s_t,a_t)}$ збир три фактора:

• ${\displaystyle (1-\alpha )Q(s_t,a_t)}$ : тренутна вредност пондерисана стопом учења. Вредности стопе учења близу 1 чине промене у${\displaystyle Q}$ брже.
• ${\displaystyle \alpha r_t}$ : награда${\displaystyle r_t=r(s_t,a_t)}$ се добије ако се акција${\displaystyle a_t}$ узима када је у стању${\displaystyle s_t}$ (пондерисано стопом учења)
• ${\displaystyle \alpha \gamma \underset{a}{max}Q(s_{t+1},a)}$ : максимална награда која се може добити од стања${\displaystyle s_{t+1}}$ (пондерисано стопом учења и фактором попуста)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\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},\underset{a}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}}{Q}_t^A(s_{t+1},a)\right)-Q_t^A(s_t,a_t)\right)}$, и

${\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},\underset{a}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}}{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-учења (користећи${\displaystyle Q}$ табелу) важи само за дискретне радње и просторе стања. Дискретизација ових вредности доводи до неефикасног учења, углавном због проклетства димензионалности. Међутим, постоје адаптације Q-учења које покушавају да реше овај проблем, као што је Q-учење путем неуронске мреже.^[23]

• Учење подстицајем
• Учење тренутном разликом
• SARSA
• Затвореникова дилема
• Теорија игара

• 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Архивирано на веб-сајтуWayback Machine (27. септембар 2011), a demonstration of guiding an ant through a maze usingQ-learning
• Q-learning work by Gerald Tesauro

• Алгоритми машинског учења

• CS1 одржавање: Формат датума
• CS1 извори на језику — енглески (en)
• Pages with single-entry sister bar
• Шаблон:Подножје/на ћирилици
• Шаблон:Подножје/без портала