мини|десно|Типичан оквир сценарија учења поткрепљењем (RL): агент предузима акције у окружењу, које се тумаче као награда и репрезентација стања, које се враћају агенту.
У машинском учењу и оптималној контроли, учење поткрепљењем (RL; ) бави се тиме како интелигентни агент треба да предузима акције у динамичком окружењу како би максимизовао сигнал награде. Учење поткрепљењем је једна од три основне парадигме машинског учења, поред надгледаног учења и ненадгледаног учења.
Док алгоритми надгледаног учења и ненадгледаног учења покушавају да открију обрасце у означеним и неозначеним подацима, учење поткрепљењем подразумева обуку агента кроз интеракције са његовим окружењем. Да би научио да максимизује награде из ових интеракција, агент доноси одлуке између испробавања нових акција како би сазнао више о окружењу (истраживање) или коришћења тренутног знања о окружењу за предузимање најбоље акције (искоришћавање). Потрага за оптималном равнотежом између ове две стратегије позната је као дилема истраживања и искоришћавања.
Окружење се обично наводи у облику Марковљевог процеса одлучивања (MDP), јер многи алгоритми учења поткрепљењем користе технике динамичког програмирања. Главна разлика између класичних метода динамичког програмирања и алгоритама учења поткрепљењем је у томе што ови други не претпостављају познавање тачног математичког модела Марковљевог процеса одлучивања и циљају на велике Марковљеве процесе одлучивања где тачне методе постају неизводљиве.
Принципи Због своје општости, учење поткрепљењем се проучава у многим дисциплинама, као што су теорија игара, теорија контроле, операциона истраживања, теорија информације, оптимизација заснована на симулацији, мултиагентни системи, интелигенција роја и статистика. У литератури о операционим истраживањима и контроли, RL се назива апроксимативно динамичко програмирање или неуро-динамичко програмирање. Проблеми од интереса у RL-у су такође проучавани у теорији оптималне контроле, која се углавном бави постојањем и карактеризацијом оптималних решења и алгоритмима за њихово тачно израчунавање, а мање учењем или апроксимацијом (посебно у одсуству математичког модела окружења).
Основно учење поткрепљењем се моделује као Марковљев процес одлучивања:
Скуп стања окружења и агента (простор стања), ; Скуп акција (простор акција), , агента; , вероватноћа прелаза (у времену ) из стања у стање под акцијом . , тренутна награда након преласка из у под акцијом .
Сврха учења поткрепљењем је да агент научи оптималну (или скоро оптималну) политику која максимизује функцију награђивања или други кориснички дефинисан сигнал поткрепљења који се акумулира из тренутних награда. Ово је слично процесима који се јављају у психологији животиња. На пример, биолошки мозгови су ожичени да тумаче сигнале као што су бол и глад као негативна поткрепљења, а задовољство и унос хране као позитивна поткрепљења. У неким околностима, животиње уче да усвоје понашања која оптимизују ове награде. Ово сугерише да су животиње способне за учење поткрепљењем.
Основни агент учења поткрепљењем комуницира са својим окружењем у дискретним временским корацима. У сваком временском кораку , агент прима тренутно стање и награду . Затим бира акцију из скупа доступних акција, која се потом шаље окружењу. Окружење прелази у ново стање и одређује се награда повезана са прелазом . Циљ агента учења поткрепљењем је да научи политику:
која максимизује очекивану кумулативну награду.
Формулисање проблема као Марковљевог процеса одлучивања претпоставља да агент директно посматра тренутно стање окружења; у овом случају, каже се да проблем има пуну опсервабилност. Ако агент има приступ само подскупу стања, или ако су посматрана стања оштећена шумом, каже се да агент има делимичну опсервабилност, и формално се проблем мора формулисати као делимично опсервабилни Марковљев процес одлучивања. У оба случаја, скуп акција доступних агенту може бити ограничен. На пример, стање стања на рачуну може бити ограничено да буде позитивно; ако је тренутна вредност стања 3, а прелаз стања покушава да смањи вредност за 4, прелаз неће бити дозвољен.
Када се перформансе агента пореде са перформансама агента који делује оптимално, разлика у перформансама даје појам жаљења. Да би деловао скоро оптимално, агент мора размишљати о дугорочним последицама својих акција (тј. максимизовати будуће награде), иако тренутна награда повезана са тим може бити негативна. Дакле, учење поткрепљењем је посебно погодно за проблеме који укључују компромис између дугорочне и краткорочне награде. Успешно је примењено на различите проблеме, укључујући складиштење енергије, контролу робота, фотонапонске генераторе, бекгемон, даму, го (AlphaGo) и аутономне системе вожње.
Два елемента чине учење поткрепљењем моћним: употреба узорака за оптимизацију перформанси и употреба апроксимације функција за рад са великим окружењима. Захваљујући овим двема кључним компонентама, RL се може користити у великим окружењима у следећим ситуацијама:
Модел окружења је познат, али аналитичко решење није доступно; Дат је само симулациони модел окружења (предмет оптимизације засноване на симулацији); Једини начин за прикупљање информација о окружењу је интеракција са њим.
Прва два проблема могу се сматрати проблемима планирања (пошто је неки облик модела доступан), док се последњи може сматрати правим проблемом учења. Међутим, учење поткрепљењем претвара оба проблема планирања у проблеме машинског учења.
Истраживање Компромис између истраживања и искоришћавања најтемељније је проучен кроз проблем вишероруког бандита и за Марковљеве процесе одлучивања са коначним простором стања у раду Бурнетаса и Катехакиса (1997).
Учење поткрепљењем захтева паметне механизме истраживања; насумично бирање акција, без позивања на процењену расподелу вероватноће, показује лоше перформансе. Случај (малих) коначних Марковљевих процеса одлучивања је релативно добро схваћен. Међутим, због недостатка алгоритама који се добро скалирају са бројем стања (или скалирају на проблеме са бесконачним просторима стања), једноставне методе истраживања су најпрактичније.
Једна таква метода је -похлепна (енгл. -greedy), где је параметар који контролише количину истраживања наспрам искоришћавања. Са вероватноћом , бира се искоришћавање, и агент бира акцију за коју верује да има најбољи дугорочни ефекат (нерешени резултати између акција се прекидају равномерно насумично). Алтернативно, са вероватноћом , бира се истраживање, и акција се бира равномерно насумично. је обично фиксни параметар, али се може прилагођавати или према распореду (чинећи да агент истражује прогресивно мање), или адаптивно на основу хеуристике.
Алгоритми за учење контроле Чак и ако се занемари питање истраживања и чак и ако је стање било опсервабилно (претпостављено у даљем тексту), проблем остаје да се искористи прошло искуство како би се открило које акције воде до већих кумулативних награда.
Критеријум оптималности Политика Избор акције агента се моделује као мапа која се назива политика:
Мапа политике даје вероватноћу предузимања акције када је у стању . Постоје и детерминистичке политике за које означава акцију коју треба одиграти у стању .
Функција вредности стања Функција вредности стања се дефинише као очекивани дисконтовани повраћај почевши од стања , тј. , и сукцесивно пратећи политику . Дакле, грубо говорећи, функција вредности процењује „колико је добро” бити у датом стању.
где случајна променљива означава дисконтовани повраћај, и дефинисана је као збир будућих дисконтованих награда:
где је награда за прелазак из стања у је стопа дисконта. је мање од 1, тако да се награде у далекој будућности вреднују мање од награда у непосредној будућности.
Алгоритам мора пронаћи политику са максималним очекиваним дисконтованим повраћајем. Из теорије Марковљевих процеса одлучивања познато је да се, без губитка општости, претрага може ограничити на скуп стационарних политика. Политика је стационарна ако расподела акција коју враћа зависи само од последњег посећеног стања (из историје посматрања агента). Претрага се може даље ограничити на детерминистичке стационарне политике. Детерминистичка стационарна политика детерминистички бира акције на основу тренутног стања. Пошто се свака таква политика може идентификовати са мапирањем из скупа стања у скуп акција, ове политике се могу идентификовати са таквим мапирањима без губитка општости.
Груба сила Приступ грубе силе подразумева два корака: За сваку могућу политику, узорковати повраћаје док се она прати Одабрати политику са највећим очекиваним дисконтованим повраћајем
Један проблем са овим је тај што број политика може бити велики, или чак бесконачан. Други је тај што варијанса повраћаја може бити велика, што захтева много узорака да би се тачно проценио дисконтовани повраћај сваке политике.
Ови проблеми се могу ублажити ако претпоставимо неку структуру и дозволимо узорцима генерисаним из једне политике да утичу на процене направљене за друге. Два главна приступа за постизање овога су процена функције вредности и директна претрага политике.
Функција вредности
Приступи функције вредности покушавају да пронађу политику која максимизује дисконтовани повраћај одржавањем скупа процена очекиваних дисконтованих повраћаја за неку политику (обично или „тренутну” [на политици / on-policy] или оптималну [ван политике / off-policy]).
Ове методе се ослањају на теорију Марковљевих процеса одлучивања, где је оптималност дефинисана у смислу јачем од оног изнад: Политика је оптимална ако постиже најбољи очекивани дисконтовани повраћај из било ког почетног стања (тј. почетне расподеле не играју никакву улогу у овој дефиницији). Опет, оптимална политика се увек може наћи међу стационарним политикама.
Да би се оптималност дефинисала на формалан начин, дефинишите вредност стања политике помоћу
где представља дисконтовани повраћај повезан са праћењем из почетног стања . Дефинисањем као максималне могуће вредности стања , где је дозвољено да се мења,
Политика која постиже ове оптималне вредности стања у сваком стању назива се оптимална. Јасно је да је политика која је оптимална у овом смислу такође оптимална у смислу да максимизује очекивани дисконтовани повраћај, пошто , где је стање насумично узорковано из расподеле почетних стања (тако да
Иако су вредности стања довољне за дефинисање оптималности, корисно је дефинисати вредности акција. За дато стање , акцију и политику , вредност акције пара под дефинисана је помоћу
где сада представља насумични дисконтовани повраћај повезан са првим предузимањем акције у стању и праћењем након тога.
Теорија Марковљевих процеса одлучивања каже да ако је оптимална политика, делујемо оптимално (предузимамо оптималну акцију) бирањем акције из са највишом вредношћу акције у сваком стању, . Функција вредности акције такве оптималне политике () назива се оптимална функција вредности акције и обично се означава са . Укратко, познавање оптималне функције вредности акције само по себи је довољно да се зна како деловати оптимално. Под претпоставком потпуног познавања Марковљевог процеса одлучивања, два основна приступа за израчунавање оптималне функције вредности акције су итерација вредности и итерација политике. Оба алгоритма израчунавају низ функција () које конвергирају ка . Израчунавање ових функција подразумева израчунавање очекивања преко целог простора стања, што је непрактично за све осим за најмање (коначне) Марковљеве процесе одлучивања. У методама учења поткрепљењем, очекивања се апроксимирају усредњавањем преко узорака и коришћењем техника апроксимације функција како би се носило са потребом за представљањем функција вредности преко великих простора стања-акција.
Монте Карло методе