MagistrskodeloMentor:doc.dr.AleksanderSadikovLjubljana,2021 MEDMREŽNOMERILNOOKOLJEZAVEČAGENTNOSPODBUJEVALNOUČENJE UNIVERZAVLJUBLJANIFAKULTETAZAMATEMATIKOINFIZIKOFAKULTETAZARAČUNALNIŠTVOININFORMATIKORačunalništvoinmatematika–2.stopnjaJernejPuc

UNIVERZA V LJUBLJANI

FAKULTETA ZA MATEMATIKO IN FIZIKO

FAKULTETA ZA RAČUNALNIŠTVO IN INFORMATIKO Računalništvo in matematika – 2. stopnja

Jernej Puc

MEDMREŽNO MERILNO OKOLJE ZA VEČAGENTNO SPODBUJEVALNO UČENJE

Magistrsko delo

Mentor: doc. dr. Aleksander Sadikov

Ljubljana, 2021

Zahvala

V prvi vrsti izrekam zahvalo vsem, ki so mi omogočili prehod na novo adakemsko področje. Posebej se zahvaljujem prof. dr. Marjetki Knez za izvorno vzbuditev zanimanja in prof. dr. Sergiu Cabellu Justu za prijazne nasvete.

Nadalje se zahvaljujem članom EOResearch ekipe podjetja Sinergise za nauke, zglede in izkušnje v praktičnem okolju. Poleg tega gre zahvala Lojzetu Žustu za koristne pogovore o vsebini dela.

Hvaležen sem prijateljem Živi Bratkovič, Gregorju Bukovcu, Anžetu Dovžanu Peroviču, Urški Henigman, Žanu Hrovatu, Martinu Lindiču, Janu Pogačarju, Svitu Šmajdku, Mateju Tomcu in Juretu Vidmarju za pomoč pri preizkušanju nastale igre in zbiranju demonstracij.

Mentorju, doc. dr. Aleksandru Sadikovu, se zahvaljujem za omogočanje obrav- navane teme, pripravljenost, uporabna priporočila in povezave ter asist. dr. Matjažu Pančurju za dostop in koriščenje zmogljivih procesorskih enot.

Nazadnje se zahvaljujem staršem za spodbudo, razumevanje in olajševanje oko- liščin ter partnerki Gaji Žumer za vsebinska mnenja, predvsem pa za potrpežljivost, bodrenje in vztrajno stanje ob strani čez napore zadnjih let.

Kazalo

Program dela vii

1 Uvod 1

1.1 Pregled področja globokega spodbujevalnega učenja . . . 1

1.2 Negotovost obsežnih podvigov . . . 2

1.3 Primerno okolje za vrednotenje agentov . . . 3

1.4 Struktura magistrskega dela . . . 4

2 Globoko spodbujevalno učenje 5 2.1 Osnove . . . 5

2.1.1 Optimizacija modela . . . 5

2.1.2 Optimizacija rekurenčnega modela . . . 8

2.2 Posnemovalno predučenje . . . 11

2.3 Večagentne interakcije . . . 13

2.3.1 Samo-igranje . . . 13

2.3.2 Učenje populacije . . . 15

2.3.3 Možnosti sporazumevanja . . . 16

2.4 Porazdeljeno procesiranje . . . 17

3 Predstavitev okolja 20 3.1 Zgled . . . 20

3.1.1 Counter-Strike . . . 20

3.1.2 Ustreznost kot merilo umetne inteligence . . . 22

3.1.3 Predhodna dela . . . 23

3.1.4 Obrazložitev pristopa . . . 24

3.2 Implementacija . . . 25

3.2.1 Zasnova . . . 26

3.2.2 Grafični sistem . . . 31

3.2.3 Zvočni sistem . . . 32

3.2.4 Omrežna arhitektura . . . 33

3.2.5 Posredovalni strežnik . . . 37

3.2.6 Snemalna orodja . . . 38

3.3 Izvajanje . . . 39

4 Rešitve za uporabo okolja 41 4.1 Arhitektura globoke nevronske mreže . . . 41

4.1.1 Glavni vizualni vhod . . . 41

4.1.2 Osredotočeni vizualni vhod . . . 44

4.1.3 Zvočni vhod . . . 45

4.1.4 Stanjski vhod . . . 48

4.1.5 Rekurenčno jedro . . . 48

4.1.6 Motorični izhodi . . . 49

4.1.7 Vrednostni izhod . . . 50

4.2 Aktivacija rekurenčnih elementov . . . 50

4.3 Paralelizacija klicev z zakasnitvijo . . . 52

4.4 Posnemovalno učenje . . . 55

4.4.1 Neravnovesje razredov . . . 55

4.4.2 Označevanje pogleda . . . 55

4.5 Spodbujevalno učenje . . . 56

4.5.1 Raziskovanje okolja . . . 57

4.5.2 Uveljavljanje dejanj . . . 57

4.5.3 Prenašanje podatkov . . . 57

4.5.4 Ponovljivost poskusov . . . 58

4.6 Porazdeljeno procesiranje . . . 58

5 Rezultati 60 5.1 Zmogljivost okolja . . . 60

5.2 Snemanje demonstracij . . . 61

5.3 Poskus posnemovalnega učenja . . . 64

6 Razprava 68 6.1 Ustreznost zbirke demonstracij . . . 68

6.2 Težavnost spodbujevalnega učenja . . . 68

6.3 Predlogi nadaljnjih raziskav . . . 69

6.4 Možne razširitve okolja . . . 69

7 Zaključek 72

Literatura 73

Program dela

Samo-igranje je dobilo v zadnjih letih kar nekaj zanimivih zgledov, kot sta OpenAI Five in DeepMind-ov AlphaStar [7, 109], vendar sta ta po obsegu precej zapletena in ni jasno, kaj pomenita za širšo skupnost. Da bi se lotili teme, bi se morale ob preučevanju sorodne literature najti priložnosti za posebno obravnavo. Na primer, učno okolje SC2LE [108] nakazuje, da je imel AlphaStar nekaj zelo drugačnih pogo- jev že po zasnovi in da bi bilo morda vredno za raziskave uporabiti bolj primerno okolje. Če takega ni na voljo, bi se ustrezno okolje moralo implementirati. OpenAI Gym [10] je na tem področju standarden okvir, vsebinsko dosti dela poteka na osnovi igralnega pogona Unity [8, 110], kot dober zgled pri tem pa je lahko DeepMind-ov FTW [36, 5]. Potem se lahko začne eksperimentirati z modelom nevronske mreže in spodbujevalnim učenjem. Če pride do konkretnih rezultatov, bi bila zanimiva interpretacija modela in učenja.

Osnovna literatura

[7] C. Berner in dr., Dota 2 with large scale deep reinforcement learning, CoRR abs/1912.06680 (2019)

[109] O. Vinyals in dr.,Grandmaster level in StarCraft II using multi-agent reinfor- cement learning, Nature575(7782) (2019) 350–354, doi:10.1038/s41586-019-1724-z [108] O. Vinyals in dr., StarCraft II: A new challenge for reinforcement learning, CoRR abs/1708.04782 (2017)

[10] G. Brockman in dr.,OpenAI Gym, CoRR abs/1606.01540 (2016)

[8] J. Booth in J. Booth, Marathon environments: Multi-agent continuous control benchmarks in a modern video game engine, CoRR abs/1902.09097 (2019) [110] T. Ward in dr.,Using Unity to help solve intelligence, CoRRabs/2011.09294 (2020)

[36] M. Jaderberg in dr.,Human-level performance in first-person multiplayer games with population-based deep reinforcement learning, CoRR abs/1807.01281 (2018) [5] C. Beattie in dr.,DeepMind Lab, CoRR abs/1612.03801 (2016)

Podpis mentorja:

Medmrežno merilno okolje za večagentno spodbujevalno učenje Povzetek

Zmožnost delovanja (in zmagovanja) v igrah se pri umetni inteligenci pogosto uporablja kot pokazatelj oz. merilo splošnejše sposobnosti. S stopnjevanjem izzi- vov pa so zaradi tehničnih ovir odmevni podvigi primorani sklepati kompromise - vmesniki simulacijskih okolij so lahko za umetne agente neskladno prirejeni, kar vzbuja negotovosti v primerjavah z ljudmi. Pregled izbranih del na področju globo- kega spodbujevalnega učenja v realnočasnih strateških igrah poudarja potrebo po novem merilnem okolju, ki z omogočanjem enakovrednejših vmesnikov bolje izpo- stavlja vlogo strateških elementov in je hkrati primerno za poskuse na porazdelje- nih sistemih. Slednje je izvedeno kot skupinska tekmovalna igra, v opisu katere se obravnavajo določeni tehnični in teoretični problemi na primerih posnemovalnega in spodbujevalnega učenja.

Online benchmark environment for multi-agent reinforcement learning Abstract

Capability of acting (and winning) in games is often used in artificial intelligence as an indicator or measure of more general ability. However, as challenges escalate, notable efforts are forced to compromise due to technical limitations - interfaces of simulated environments can be inconsistently adapted for artificial agents, which induces uncertainty in comparisons with humans. Review of select works in the field of deep reinforcement learning in real-time strategy games highlights necessity for a new benchmark environment, which better emphasises the role of strategic elements by enabling more equivalent interfaces and is also suitable for experiments on distributed systems. The latter is realised as a team-based competitive game, in description of which specific technical and theoretical problems are examined on the cases of imitation and reinforcement learning.

Math. Subj. Class. (2020): 68T05, 68T07

Ključne besede: simulacijsko okolje, večagentni sistem, večigralske igre, medmre- žne igre, razvoj iger, umetna inteligenca, umetne nevronske mreže, globoko učenje, posnemovalno učenje, spodbujevalno učenje, samo-igranje

Keywords: simulation environment, multi-agent system, multiplayer games, on- line games, game development, artificial intelligence, artificial neural networks, deep learning, imitation learning, reinforcement learning, self-play

1 Uvod

1.1 Pregled področja globokega spodbujevalnega učenja

Nedavni napredek na področjih, kot so računalniški vid [48, 25, 76], prepoznavanje govora [1], procesiranje naravnega jezika [107, 11], napovedovanje strukture prote- inov [89], robotska manipulacija [72] in dokazovanje matematičnih izrekov [82], je prevladujoče pogojen z razvojem globokega učenja [54].

Na tej poti napredka so bile igre deležne posebne pozornosti kot način preizku- šanja in vrednotenja pristopov na standardiziranih nalogah, predvsem pa kot jasen prikaz njihovega potenciala. Začenši s klasičnimi namiznimi igrami so se sistemi, kot so TD-Gammon [102], AlphaGo [91] in AlphaZero [93, 92], do rezultatov poslužili posebej elegantnih in zmožnih konceptov: spodbujevalnega učenja in samo-igranja.

Namesto predpisanih pravil ali hevristik so igrali proti različicam samih sebe, se učili iz poskusov in napak, dokler niso bili konkurenčni in nazadnje zmagovalni proti naj- boljšim človeškim igralcem.

Vseeno je dolgoročni cilj umetne inteligence reševati izzive pravega sveta, ki med drugim zahtevajo realnočasne odločitve med kombinatorično veliko možnostmi z nepopolnimi informacijami v zahtevnih, zveznih prostorih. Tu se video igre po- kažejo kot primerno merilo novih rešitev, saj v primerjavi s predhodnimi mejniki začnejo posegati v omenjeno zapletenost naravnih okolij. Tudi v teh je globoko spodbujevalno učenje že doseglo znatne uspehe, od starih konzolnih [65] in prvoo- sebnih [50, 36] do modernih RTS (ang.real-time strategy) iger ter izpeljank [7, 109], pogosto z nadčloveškimi rezultati.

Zadnja primera, t. i. OpenAI Five in AlphaStar, sta posebej vredna obravnave.

Igri, v katerih sta se pomerjala, StarCraft II in Dota 2, sta bili posebej izbrani zaradi domnevne nepremostljivosti, misleč da bo podvig zahteval uporabo naprednih algoritmičnih idej, kot je npr. hierarhično spodbujevalno učenje [49], ali ustvarjanje novih. Nasprotno se je izkazalo, da so obstoječe metode učenja že dovolj sposobne – vsaj s širitvijo na računsko nezaslišane razsežnosti.

Za referenco naj se omeni, da je bil OpenAI Five učen na do 1.536 GPU-jih (ang.

graphics processing unit) in do 172.800 CPU-jih (ang. central processing unit) 180 dni čez 10 mesecev realnega časa. Glede na raven paralelizacije okolij, simulacijsko hitrost in dolžino iger je to naneslo na povprečje 250 let samo-igranja na dan oz.

skupno 45.000 let igralnih izkušenj.

Domnevno se po obsegu do sedaj lahko primerja samo AlphaStar, ki je vključeval sočasno učenje populacije agentov na množici namensko posebej zmogljivih TPU- jev [37] (ang. tensor processing unit). Po 44 dneh in približno 10 milijonih iger je vsak od približno 900 različnih agentov izkusil do 200 realnočasnih let igranja.

K polni porabi časa in sredstev prispevajo tudi učenje preteklih različic, ponovni zagoni in ablacijske študije, kar naredi omenjena projekta še toliko bolj zajetna.

S kopičenjem tovrstnih spoznanj se področje odmika od napredka na algoritmični fronti proti izkoriščanju čedalje bolj porazdeljene in čedalje zmogljivejše strojne opreme [97].

1.2 Negotovost obsežnih podvigov

Končno je AlphaStar v igri StarCraft II, ki je prepoznana med najtežjimi RTS igrami in med najstarejšimi e-športi, premagal vrhunskega profesionalnega igralca in bil uvrščen nad 99,8% uradno rangiranih igralcev na evropskem strežniku. Kljub zagovarjanju rezultatov s strani avtorjev pa je splošno mnenje StarCraft privržencev, da je bil AlphaStar uspešen poglavitno zaradi hitrejših in natančnejših dejanj in odzivov v odločilnih trenutkih igre [44, 81, 47, 17]. Pred tem so neskladnosti med človeškim in za AlphaStar prirejenim vmesnikom prepoznali že avtorji sami (slika 1), a so se nadalje sklicevali na posvetovanje s profesionalnimi igralci (slika 2).

Slika 1: Primer neskladnosti vmesnikov: nekatera dejanja, ki jih mora človek izvesti neposredno s premiki miške in pritiskanjem gumbov, lahko umetni agent izvede skupaj in glede na natančno podane točke. Slikovni vir: [108, Vinyals in dr.]

Slika 2: Porazdelitvi števila dejanj na minuto in odzivnega časa v igri Starcraft II za agenta AlphaStar in dva profesionalna igralca prikazujeta, da sklicevanje na povpre- čja vrednosti ne odpravi spornosti ekstremov. V tem primeru so bili avtorji deležni kritik tudi zaradi izpustitve omembe, da je eden izmed igralcev uporabljal skripto za ponavljanje dejanj, rekoč da se nepoznavalce igre zavaja z vtisom sprejemljivosti [81].

Slikovni vir: [101, Ekipa AlphaStar]

Podobno je OpenAI Five v Doti 2, ki si deli določene zahtevnosti z RTS igrami, kot je StarCraft, a je igrana v skupinah po 5 igralcev, kot ekipa kopij istega agenta premagal takratne svetovne prvake in zmagal 99,4% iger mešanih ekip, kot soigralec in nasprotnik ljudem. Na podlagi komentarjev avtorjev in ogleda demonstracijskih iger se lahko naredi sorodne ugotovitve neskladnosti [7, 74, 73].

Primerjava ljudi in umetnih agentov ni enostavna (tudi v primeru šaha se lahko razpravlja o učinku izčrpanosti), vendar je pri razumevanju rezultatov pomembno priznati bistvene razlike in omejitve v zaznavno-motorični sposobnosti. Razlog za omejevanje umetnih agentov leži v tem, da so obravnavane igre same okrnjene s po- polnostjo spretnosti. Razvijalci jih namreč razvijajo za ljudi in strateške elemente previdno ohranjajo v ravnovesju glede na povratne podatke. Vidiki igre pod nad- človeško spretnostjo tako ostanejo neraziskani oz. nekompenzirani in ob porušenju predpostavk pravila igre preprosto ne veljajo več. Tudi če so agenti zmožni zmago- vati s posluževanjem globljih strategij, lahko te ob takih pogojih postanejo odveč, saj je izkoriščanje prednosti zelo verjetno najboljši način zmagovanja.

S tem ni rečeno, da so omenjeni rezultati brez vsakršne vrednosti, vendar je za tehten prispevek k področju umetne inteligence potrebno imeti bolj zanesljivo merilo od premagovanja igralcev pod neenakimi pogoji.

1.3 Primerno okolje za vrednotenje agentov

Avtorji sami poudarjajo, da je pravi izziv pomeriti agente v človeških okolišči- nah [108, 36], a so za obravnavo omenjenih iger primorani sklepati kompromise [108, 7] zaradi npr. računsko potratnega izrisovanja slike in praktično neobvladljivega pro- stora potez.

Iskanje primera, ki bi hkrati imel dovolj strateške globine (npr. nepopolnost in- formacij, dolg časovni okvir in izredno dinamična stanja), zaledje tekmovalnih igral- cev, omogočal uporabo enakovrednega vmesnika in bil razpoložljiv raziskovalcem umetne inteligence, ni obetavno. Moderne video igre brez podpore razvijalcev ne omogočajo programskega dostopa in niso namenjene za množično paralelizacijo oko- lij [79], standardna merilna okolja pa so bodisi preenostavna (npr. Arcade Learning Environment [6]) bodisi neuporabljena za igranje izven raziskav oz. za ta namen neenostavno priredljiva (npr. MuJoCo [103], RLLab [18] in DeepMind Lab [5]).

Kot možna rešitev je bilo zastavljeno združenje določenih lastnosti modernih video iger in standardnih merilnih okolij. V nadaljevanju tega dela se določi primer skupinske prvoosebne video igre kot primerno izhodišče, ki je bilo reimplementirano kot enostavnejše simulacijsko okolje ob zahtevi ohranitve ključnih pravil in strateških elementov. Pri tem je bilo nujno zagotoviti ogrodje za medmrežno povezovanje, da bi se z možnostjo oddaljenega igranja povečalo verjetnost zanimanja človeških igralcev, omogočilo paralelizirano učenje in olajšalo preizkušanje umetnih agentov. Tako se lahko slednji čezcelinsko pomerijo proti ljudem ali drugim agentom brez predhodnega deljenja lastnega programa, kar podpira množično učenje in vrednotenje. Okolje je v celoti odprtokodno: prosto dostopno¹, razumljivo in prilagodljivo.

1https://github.com/JernejPuc/sidegame-py

1.4 Struktura magistrskega dela

V poglavju 2 se pregleda teoretične komponente globokega spodbujevalnega učenja.

Definira se osnovni problem agenta v okolju in njegovo reševanje z optimizacijo pa- rametrov umetne nevronske mreže, kompenzacijo težavnosti začetnega raziskovanja s predučenjem preko posnemanja človeških demonstracij ter pristope za večagentne interakcije in porazdeljeno procesiranje.

Poglavje 3 predstavi ustrezno izhodišče za merilo spodbujevalnega učenja in opiše nastalo simulacijsko okolje s poudarkom na grafičnem in zvočnem sistemu, omrežni zasnovi ter sistemih, ki podpirajo posnemovalno in spodbujevalno učenje.

S poglavjem 4 se splošno obravnava izzive nastalega okolja: sestavne dele reku- renčne nevronske mreže, ki omogoča polno interakcijo z okoljem in ukrepe zoper določene težavnosti posnemovalnega in spodbujevalnega učenja v njem. Dodatno se predstavi predlog za široko porazdeljeno procesiranje, ki temelji na njegovi med- mrežni lastnosti.

Opisana rekurenčna mreža je bila implementirana in učena s posnemovalnim učenjem na podlagi zbranih demonstracij. Lastnosti demonstracijskih posnetkov s poudarkom na njihovem vplivu na učenje navaja poglavje 5 poleg pogojev in rezultatov samega učenja.

Razprava v poglavju 6 nadalje komentira problematiko zbranih demonstracij in praktične težavnosti širokega spodbujevalnega učenja. Predstavijo se predlogi za nadaljevanje raziskav, ablacije improviziranih ukrepov in razširitve implementacije okolja. Delo zaključujeta retrospektiva dela in povzetek doprinosov.

2 Globoko spodbujevalno učenje

V nadaljevanju je narejen pregled teoretičnih konceptov, ki so bili merodajni pri nastajanju merilnega okolja. Slednje jih mora podpirati oz. upoštevati, določene metode pa so tudi del ponazoritvene implementacije.

2.1 Osnove

Spodbujevalno učenje je osnovano na dveh osnovnih pojmih: okolju, ki predstavlja resnični ali virtualni svet, in agentu, t. j. algoritem oz. program, ki v tem okolju deluje. Agent ob danem časut∈[0, T], kjer jeT dolžina epizode (npr. ene ponovitve igre), iz okolja pridobi opazovanjeo_t∈O globalnega stanjas_t∈S in v njem uveljavi dejanje a_t ∈ A, kot odziv strategije (ang. policy), π : O → A (slika 3). Igra je odigrana s posodabljanjem stanja okolja ob periodičnih ponovitvah tega cikla² dokler se ne zaključi z nekim izidom r_T.

o^t+1, r^t+1 o^t, r^t

a^t

s^t, s^t+1 π

Slika 3: Cikel posodobitve stanja okolja.

V tej definiciji se je predpostavilo, da je prehajanje med stanji okolja forma- lizirano kot delno opazovani Markovski odločitveni proces [38], kjer ima agent le delne (nepopolne) informacije o celem okolju, in da je bistvena vrednotna informa- cija obravnavanega okolja ena sama – zmaga, poraz ali neodločen izid ob končnem času T:

r_t =R(s_t)∈

{︄{−1,0,1}, t =T

{0}, t < T (2.1)

S spodbujevalnim učenjem se nanašamo na proučevanje učenja agentov na po- skusih in napakah ob ideji, da bo agent z nagrajevanjem ali kaznovanjem glede na njegovo vedenje v prihodnje to vedenje verjetneje ponovil ali opustil.

2.1.1 Optimizacija modela

Nadalje strategijo modeliramo z globoko nevronsko mrežo s parametrizacijo θ³.

2Odvisno od implementacije okolja se to lahko posodobi tudi neodvisno od agentovega delovanja.

3Parametri, opazovanja, dejanja idr. so načeloma nabor več tenzorjev različnih dimenzij. Zavoljo enostavnosti so ohranjene oznake navadne debeline.

V bolj specifičnem opisu cikla na sliki 3 se opazovanje o_t obdela z operacijami, ki lahko med koraki ohranjajo spomin, in proizvede dejanje z vzorčenjem porazdelitve, ki je izhod stohastične strategije: a_t ∼π_θ(·|o₀, . . . , o_t) oz. krajše a_t∼π_θ(·|o_t).

Dopustimo tudi, da se nagradno funkcijoR dopolni s pomožnimi funkcijami, ki nagrajujejo pogostejše vedenjske vzorce v sicer daljši epizodi: r_t =R(st−1, a_t, s_t)oz.

krajše r_t = R(s_t, a_t). Primer je t. i. oblikovanje nagrad (ang. reward shaping) [68], kjer se nagrajuje oz. kaznuje posamezna dejanja, ki jih človeški izvedenci razumejo kot dobra oz. slaba. To lahko očitno vodi do pristranskosti in nepričakovanih po- sledic, a je v praksi pogosto zadovoljivo. V igrah z ničelno vsoto (ang. zero-sum) je posebej nujno poskrbeti, da ne more priti do situacije, ko lahko nasprotujoči si agenti hkrati prejmejo pozitivno nagrado in zaobidejo glavni cilj igre, podan z enačbo 2.1.

Cilj spodbujevalnega učenja je najti parametre θ^∗, pri katerih bo maksimiziran pričakovan seštevek nagrad (ang. cumulative reward), če bo agent v okolju deloval v skladu s strategijo π_θ^∗:

θ^∗ = arg max

θ E

τ∼πθ

[R(τ)], (2.2)

kjer je R(τ) seštevek nagrad za zaporedje parov stanja in dejanja (s_t, a_t)v časovno omejeni epizodi τ = ((s₀, a₀), . . . ,(s_T, a_T)):

R(τ) =

T

∑︂

t= 0

γ^tr_t (2.3)

γ ∈ (0,1] v enačbi 2.3 je popustni faktor (ang. discount factor), ki eksponentno manjša poznejše nagrade. Izbiraγ <1zagotavlja, da je skupna nagrada omejena za T → ∞, vendar ni samoumevno, da se v časovno omejenih epizodah daje prednost zgodnjim nagradam: tudi v primeru dolgega časovnega okvira (reda ene ure) v literaturi obstaja precedens [109], kjer se popustni faktor izpusti oz. izbere γ = 1.

Za učenje strategije π_θ izberemo ustrezen algoritem spodbujevalnega učenja, npr. PPO (ang. proximal policy optimisation) [88] po obliki družine metod igralec- ocenjevalec [45], ki je bil med drugim uporabljen pri OpenAI Five. PPO se namesto neposrednih nagrad zanaša na t. i. koristi, zato je najprej potrebno navesti nekaj definicij.

Definicija 2.1. Q-vrednost trenutne strategije Q^π je funkcija, ki vrne pričakovan seštevek nagrad v epizodi τ, ko začne agent v stanju s, izvede dejanje a in nadalje deluje v skladu s strategijo π:

Q^π(s, a) = E

τ∼π[R(τ)|s0 =s, a0 =a] (2.4) Definicija 2.2. Vrednost trenutne strategije V^π je funkcija, ki vrne pričakovan seštevek nagrad v epizodiτ, ko začne agent v stanjusin deluje v skladu s strategijo π:

V^π(s) = E

τ∼π[R(τ)|s₀ =s] (2.5)

Med Q-vrednostjo in vrednostjo strategije velja naslednja zveza:

V^π(s) = E

a∼π[Q^π(s, a)] (2.6)

Dokaz.

V^π(s) = E

τ∼π[R(τ)|s₀ =s] (2.7)

= ∑︂

a∈A

P(a|s)· E

τ∼π[R(τ)|s₀ =s, a₀ =a]

= ∑︂

a∈A

π(a|s)·Q^π(s, a)

= E

a∼π[Q^π(s, a)]

Sledi:

Definicija 2.3. Korist trenutne strategije A^π je funkcija, ki vrne razliko med pri- čakovanim seštevkom nagrad v epizodi τ, če v začetnem stanju s izvede dejanje a namesto naključno izbranega dejanja in nato deluje v skladu s strategijo π:

A^π(s, a) = Q^π(s, a)−V^π(s) (2.8) PPO na danem optimizacijskem korakuk za vzorce ob časutoptimizira ciljnemu izrazu 2.2 nadomestni izraz, ki primerja strategijo π_θ s trenutno strategijoπ_θk, in je sorodna naslednjemu nadomestku [86]:

θ_k+1 = arg max

θ

t∼τ, τ∼D

Eˆ︁

at, st∼π_θk

[︃πθ(at|st)

π_θk(a_t|s_t)Aˆ︁^πθk(s_t, a_t) ]︃

, (2.9)

kjer jeAˆ︁^πθ ocena koristi, ki po igralec-ocenjevalec modelu posredno izhaja iz samega modela θ, Eˆ︁ pa označuje oceno pričakovane vrednosti glede na empirično povprečje čez nabor vzorcev, ki ga tvori nabor epizodD.

Specifično, PPO definira naslednjo izgubno funkcijo strategije:

L^π(s, a, θ_k, θ) = min

(︃ π_θ(a|s)

π_θk(a|s)Aˆ︁^πθk(s, a), clip

(︃π_θ(a|s)

π_θk(a|s),1−ϵ,1 +ϵ )︃

Aˆ︁^πθk(s, a) )︃

, (2.10) kjer je ϵ majhen hiperparameter, ki določa, kako daleč od stare strategije se lahko nova oddalji. Namen te omejitve je omogočanje večkratne uporabe obstoječih po- datkov za optimizacijo, ne da bi se pri tem naredilo škodljivo veliko posodobitev.

Ocena koristi Aˆ︁^πθ se določa po predpisu GAE (ang. generalised advantage esti- mation) [87]:

Aˆ︁^π_t^θ =δ_t+ (γλ)δ_t+1+· · ·+ (γλ)^T−t+1δ_T−1, (2.11) δ_t=r_t+γVˆ︁^πθ(s_t+1)−Vˆ︁^πθ(s_t),

kjer je Vˆ︁^πθ eden izmed izhodov modela s parametri θ, ki aproksimira dejansko vre- dnost strategije V^πθ (izraz 2.5). Za seštevek nagradR_tdo časa tje izgubna funkcija za slednjo aproksimacijo preprosto kvadratna napaka:

L^V(s_t, R_t, θ) =(︂

Vˆ︁^πθ(s_t)−R_t)︂2

(2.12) Skupna izgubna funkcija, utežena po členih z w_π, w_V ∈ R+ in povprečena čez vzorce v naboru epizod D, tako postane:

L^{P P O}(D, θ_k, θ) = 1

|D|

∑︂

τ∈D

1

|τ|

∑︂

s, a, R∈τ

(︁w_πL^π(s, a, θ_k, θ)−w_V L^V(s, R, θ))︁

(2.13) Končno se s hitrostnim faktorjemα parametri θ_k posodobijo npr. z gradientnim vzponom (ang. gradient ascent):

θ_k+1=θ_k+α∇_θL^{P P O}|_D,θk (2.14)

ali drugim izbranim algoritmom za optimizacijo, kot sta Adam [43] ali AdamW, ki že vključuje regularizacijo [61]. Gradient izgubne funkcije je v praksi računan s programom za avtomatično odvajanje (npr. PyTorch autograd [78]).

Do te točke je bila narejena predpostavka, da se optimizacija izvaja na podlagi celotnih epizod. V primeru dolgega časovnega okvira to ne pride v poštev, pa tudi s stališča stabilnosti ni najbolj idealno zaradi velikih korelacij med vzorci. Če bi optimizirali vse vzorce skupaj, ne bi mogli zadostiti potrebam po delovnem spo- minu, in če bi optimizirali po krajših odsekih zbranih epizod, vzorčni pari po nekaj posodobitvah ne bi več ustrezali aktualnemu modelu. Praktično se zato model poso- dabljamed igranjem epizode: podatki se shranjujejo in po krajših odsekih uporabijo za optimizacijo, nakar so novi podatki pridobljeni s posodobljenim modelom. GAE označevanje pri tem upošteva oceno zadnjega koraka. Do neke mere bi se sicer lahko uporabilo tudi stare vzorce, vendar bi za to potrebovali t. i. off-policy algoritem oz.

popravek, npr. po [22, Espeholt in dr.]

2.1.2 Optimizacija rekurenčnega modela

Ker se je predpostavilo, da so stanja delno opazovana, mora imeti agent za primerno delovanje sposobnost pomnenja. V ta namen se uporabi različico rekurenčnih ne- vronskih mrež [59], katerih izhod je odvisen od predhodne aktivacije (slika 4).

xt

Lt

ht ht ht+1

xt xt+1

Lt Lt+1

∂Lt

∂ht

∂Lt

∂ht

∂Lt+1

∂ht+1

∂ht+1

∂ht

∂ht

∂ht-1 ∂ht+1

∂ht+2

Slika 4: Razvoj osnovne rekurenčne celice po času.

Vpeljava rekurenčnih elementov ima zanimivo in problematično posledico: gradi- enti tečejo skozi predhodne korake, kar pomeni, da se morajo ohranjati v delovnem spominu vse aktivacije do začetnega koraka. Vzvratno širjenje napake skozi čas (ang.

backpropagation through time) na dolgih nizih tako ni praktično izvedljivo, ampak v praksi niti ni v celoti potrebno, saj gradienti s stopnjevanjem zamrejo [77]:

Trditev 2.4 (Pascanu, Mikolov in Bengio). Če je največja lastna vrednost matrike rekurenčnih uteži absolutno manjša od 1, |λ^max_W

h|<1, je to zadostni pogoj, da gradi- enti med korakoma i in j, ^∂h_∂hⁱ

j, izginejo, ko število korakov narašča, i−j → ∞.

Dokaz. Za vektorje spomina h, vhoda x in pristranskih utežib, matriki uteži Wh in W_x ter aktivacijsko funkcijo f:

h_t =f(W_hht−1+W_xx_t+b) (2.15)

∂h_t

∂ht−1

= diag (f^′(W_hht−1+W_xx_t+b))W_h

je po verižnem pravilu za ovrednotenje izgubne funkcijeL nai-tem koraku glede na spominski vektor koraka j:

∂L_i(θ)

∂h_j = ∂L_i(θ)

∂h_i

∂h_i

∂h_j

= ∂L_i(θ)

∂h_i

∏︂

j < t≤i

∂h_t

∂ht−1

= ∂L_i(θ)

∂h_i W_h^i−j ∏︂

j < t≤i

diag (f^′(Whht−1 +Wxxt+b)) Za običajne aktivacijske funkcije, katerih odvodi so absolutno omejeni z 1:

σ(x) = 1

1 +e^−x, tanh(x) = e^x−e^−x

e^x+e^−x, ReLU =

{︄x, x≥0 0, x <0 velja:

⃦

⃦

⃦

⃦

∂ht+1

∂h_t

⃦

⃦

⃦

⃦

≤ ∥W_h∥∥diag (f^′(W_hht−1+W_xx_t+b))∥ ≤ |λ^max_Wh|<1, ∀t in torej:

i−jlim→ ∞

∂L_i(θ)

∂h_j = lim

i−j→ ∞

∂L_i(θ)

∂h_i W_h^i−j ∏︂

j < t≤i

diag (f^′(Whht−1+Wxxt+b))

≤ lim

i−j→ ∞

∂L_i(θ)

∂h_i ∥W_h∥^i−j ∏︂

j < t≤i

∥diag (f^′(W_hht−1+W_xx_t+b))∥

= ∂Li(θ)

∂h_i lim

i−j→ ∞|λ^max_Wh|^i−j

= 0

Tako si lahko privoščimo aproksimacijo gradienta z omejitvijo globine gradien- tov do obvladljivega števila korakov z okrajšanim vzvratnim širjenjem skozi čas (ang. truncated backpropagation through time, kraj. TBPTT) [115]. Sicer je iz- gubljanje in razletanje⁴ gradientov (ang.vanishing/exploding gradients) neželeno in problematično za učenje dolgoročnih povezav, saj tudi izboljšave, kot je LSTM (ang.

long-short term memory) [32], ne morejo povsem preprečiti teh pojavov.

Glede na način omejevanja globine širjenja v nizu izpostavimo dve praktični obliki krajšanja, prikazani na slikah 5 in 6:

h

h

h

h

h

h

h

x

x

x

x

x

x

L

L

L

L

L

L

Slika 5: Pravo okrajšano vzvratno širjenje skozi čas: Po določeni točki ima vsako širjenje enako globino in vsak korak prispeva k enakemu številu napak. Tako so gradienti konsistentni, vendar je za implementacijo potrebna prekinitev računskega grafa (spomina aktivacij in povezav med njimi) na vmesnih točkah, kar moderna orodja otežujejo.

h

h

h

h

h

h

h

h

x

x

x

x

x

x

L

L

L

L

L

L

Slika 6: Epohalno vzvratno širjenje skozi čas: Nizi so razdeljeni na epohe, ki dolo- čajo globino najglobljega širjenja. Ker posamezni koraki nimajo enakih prispevkov, so gradienti manj konsistentni, vendar je postopek računsko in spominsko učinkovi- tejši (po epohi se ohrani le zadnje stanje celice, preostali spomin pa se sprosti) ter implementacija dosti lažja. Ko se v literaturi omenja okrajšano vzvratno širjenje skozi čas, se zato navadno misli prav epohalno različico.

Pri tem je pomembna opomba, da se GAE (izraz 2.11) navadno izvede na podlagi daljšega okna, kot je uporabljen za omejitev globine širjenja napake – idealno na polnem nizu, sicer se podobno za začetno vrednost nekega okna uporabi zadnjo oceno prejšnjega.

4Če je|λ^max|>1, po podobnem dokazu.

2.2 Posnemovalno predučenje

Za stohastično strategijoa_t∼π(·|o_t), kjer agent napreduje z naključnim vzorčenjem dejanj, je lahko obsežen prostor dejanj A ob dolgem časovnem okviru velika težava pri raziskovanju okolja, predvsem na začetku učenja. Namreč verjetnost, da agent čez tisoče korakov naključno izvede ustrezno zaporedje, ki bi ga privedlo do sredi- šča dogajanja in nakazalo približno pravilno ravnanje, je lahko izrazito majhna, za raznolikost strategij pa se mora to storiti še na več načinov.

Možna rešitev je, da se agent najprej priuči osnov igre in različnih pristopov igranja s posnemanjem človeških demonstracij in nato le izpopolni svojo strategijo s spodbujevalnim učenjem. Gre za obliko prenesenega učenja (ang.transfer learning), ki je bila v preteklosti že uporabljena pri igrah Atari [28], za AlphaGo [91], agente AlphaStar [109] in v robotiki [2].

Vedenjsko kloniranje (ang. behavioural cloning) je med osnovnejšimi metodami posnemovalnega učenja (ang. imitation learning) [104]. Učenje sloni na zbirki po- datkov D= {{o₁, a₁}, . . . ,{o_N, a_N}}, kjer so vzorci pari opazovanj o ∈ O in dejanj a ∈ A, kot jih je ustvaril predhodni agent (recimo izkušen človek). Učeni agent s parametrizacijoθ mora za vsako opazovanjeoi predvideti tako dejanjeaˆi, da zadosti naslednjemu optimizacijskemu problemu:

θ^∗ = arg min

θ N

∑︂

i= 1

L^DIST(ai, aˆi), (2.16) kjer je L^DIST izgubna funkcija odvisna od oblike prostora dejanj A, ki služi kot merilo razdalje med proizvedenim dejanjem aˆ_i in oponašanim dejanjem a_i. Tako stremi k temu, da so odzivi agenta v posnetih situacijah čim bolj podobni odzivom demonstratorja.

V literaturi se za primer diskretiziranih dejanj najde omembo minimizacije Kull- back-Leibler (KL) divergence [109] ali križne entropije [79] med dejanjema, ki sta predstavljena kot kategorični porazdelitvi. Lahko pokažemo, da je možno vedno izbrati enega od teh, denimo bolj standardno križno entropijo, saj sta pripadajoča odvoda povezana oz. enaka:

Dokaz. Ob definiciji KL divergence D_KL za diskretni verjetnostni porazdelitvi P in Q nad zbirko vzorcev X:

D_KL(P∥Q) = H(P, Q)−H(P), (2.17) kjer je H(P)oz. H(P, P) entropija, H(P, Q) pa križna entropija:

H(P, Q) =− ∑︂

x∈X

P(x) logQ(x),

bo D_KL za dani primer, kjer nabor tarčnih dejanj označimo z A^′ ⊂A, D=O^′◦A^′:

D_KL(A^′∥π_θ) =−

N

∑︂

i= 1

a_i logπ_θ(a_i|o_i) +

N

∑︂

i= 1

a_iloga_i,

odvod pa enak odvodu same križne entropije:

∂D_KL

∂θ (A^′∥π_θ) =− ∂

∂θ (︄ _N

∑︂

i= 1

a_i logπ_θ(a_i|o_i) )︄

= ∂H

∂θ(A^′, π_θ)

Po drugi strani za primer zveznih dejanj tipično minimiziramo povprečno kva- dratno napako: ∑︁N

i=1(a_i−aˆ_i)². Tako lahko posnemovalno učenje razumemo kot navadno razvrščanje ali regresijo z nadzorovanim učenjem, za posodabljanje para- metrov pa se lahko uporabi npr. že omenjeni Adam [43].

Predstavljena metoda je uporabna za učenje delovanja v okolju brez potrebe po dejanskih interakcijah z okoljem. Lahko je tudi pokazatelj smotrnosti in usmerja izbiro ali prilagajanje komponent uporabljene arhitekture nevronske mreže, saj bi ta morala biti sposobna priti s posnemanjem do zadovoljive ravni, da bi sploh imela možnost uspeha pri sledečem spodbujevalnem učenju.

Pri nekaterih AlphaStar agentih se je posnemanje uporabilo tudi med samim spodbujevalnim učenjem v obliki dodatnih členov v izgubni funkciji z namenom ohra- nitve vtisnjene strateške raznolikosti in da je bilo nadaljnje raziskovanje pristransko v prid bolj “človeškim” strategijam. Tu je morda bolj od natančnega posnemanja zanimiva uporaba statističnih vzorcev, ki predstavljajo nek vidik trenutnega stanja in so lahko pridobljeni iz istih demonstracij: tako je agent naučen, kako naj bi pri- bližno ravnal, podrobnosti izvedbe pa so prepuščene njemu. Pri tem se za L^DIST uporabi primerne metrike, npr. število razlik v zaporedju kategoričnih dejanj ali naboru seštevkov vrednosti (ang. edit distance) [109].

Uporaba človeških podatkov za predučenje ima tudi določene pomanjkljivosti:

• Razpoložljivost podatkov: Odvisno od področja podatke morda ni možno ali ni enostavno pridobiti v zadostnih količinah. Pri video igrah je to navadno pogojeno s podporo razvijalca [79], pri realnih problemih pa je lahko logistično nemogoče. Ob nezadostni količini posnetkov agent ne vidi dovolj situacij – namesto vzročnosti se nauči soodvisnosti in s kopičenjem napak v zaporedju novih stanj lahko nepomogljivo odpove [16, 52].

• Kakovost posnetkov: Igralci v posnetkih so lahko neizkušeni. Poleg ko- ristnih nagnjenj lahko tudi suboptimalna ali nevtralna preostanejo skozi vso nadaljnje učenje [109].

• Nesoglasje demonstrantov: Igralci v podobnih stanjih delujejo različno in so različno sposobni. V primeru AlphaStar se je zgodilo, da je bil s posne- manjem naučeni agent približno na ravni najslabših demonstrantov, dokler ga niso doučili le na boljših [109]. V določenih primerih je lahko učenje zgolj z boljšimi igralci boljše od učenja na večji zbirki mešanih igralcev [40].

• Seznanjenost s področjem: Domensko posebne podatke je potrebno (znati) obdelati v obliko, ki ustreza kasnejši uporabi v učenju.

Da spodbujevalno učenje na zapleteni nalogi ne bi moglo uspeti brez človeških demonstracij, bi bila težka kritika. Morda ni presenetljivo, da se proti tej najde primer, ki zoper majhne verjetnosti nastopi le z velikim računskim obsegom, da do zadostnih izkušenj vseeno pride in se težava samodejno premosti [7].

2.3 Večagentne interakcije

Že igra z dvema nasprotujočima si agentoma predstavlja večagentno okolje, v kate- rem učenje poteka dinamično zaradi vztrajnega prilagajanja obeh strani. Nadalje so zanimive skupinske igre (z več soigralci), ki se morajo naučiti delovati sami od sebe in po lastnih ciljih, a hkrati sodelovati z drugimi agenti v skupnem okolju.

Zapletenost in pristopanje k reševanju takih nalog sta posebej vredna obravnave.

2.3.1 Samo-igranje

Samo-igranje (ang. self-play) agentu v tekmovalni igri omogoča učenje proti spon- tano izboljšujočemu se nasprotniku, tako da ta igra proti samemu sebi. Izpostavljena zanimivost učenja brez nujne vpeljave človeškega znanja je zmožnost odkritja prese- netljivih taktičnih vzorcev v domnevno že skrajno raziskanih domenah [91, 109, 7].

Pri tem se predpostavlja, da izboljšanje v igri proti (trenutnemu) nasprotniku vodi do izboljšanja v igri na splošno. Ko to približno drži, samo-igranje res ustvari zaporedje agentov povečujoče se sposobnosti. V primeru cikličnih iger, kot je kamen- škarje-papir, kjer ni prevladujoče strategije, pa ni več jasnega cilja, za katerega bi optimizirali. Ker vedno prevlada le ozek nabor strategij, ki premaga zadnjo različico, nikoli ne pride do pravega napredka in območje potencialnih strategij ostane povečini neraziskano.

Definicija 2.5. Naj bo W množica agentov. Asimetrična igra z ničelno vsoto v funkcijski obliki (ang. functional-form game) je asimetrična funkcija, Φ(v, w) =

−Φ(w, v), ki vrednoti pare agentov:

Φ :W ×W →R (2.18)

Višje vrednosti Φ(v, w) pomenijo boljše ovrednotenje agenta v, kjer primeri Φ>0, Φ<0 inΦ = 0 predstavljajo zmago, poraz in neodločen izid.

Definicija 2.6. Igra je tranzitivna, če obstaja taka (ocenjevalna) funkcija f, da je ovrednotenje igre med agentoma razlika njunih ocen:

Φ(v, w) =f(v)−f(w). (2.19) Definicija 2.7. Igra je ciklična, če je zmaga proti določenim agentom nujno urav- novešena s porazi proti drugim:

∫︂

W

Φ(v, w)dw= 0, ∀v ∈W (2.20)

Trditev 2.8 (Hodgeova dekompozicija). Vsaka asimetrična igra z ničelno vsoto v funkcijski obliki se razstavi na tranzitivno in ciklično igro.

Za dokaz je bralec napoten k [4, Balduzzi in dr.]

Le redke igre so povsem tranzitivne ali povsem ciklične. Uspeh optimizacije v samo-igranju je pogojen s ponavljanjem take lokalne posodobitve, ki izboljša tran- zitivno merilo.

Primer je maksimizirati zmagovanje oz. uspešnost proti mešani skupini naspro- tnikov, npr. v igranju proti preteklim različicam – praktična razlaga je, da se tako izognemo pozabljanju strategij (ang.strategy collapse) in zahtevamo robustnost. To je izpeljano iz namišljenega samo-igranja (ang. fictitious self-play) [27] in pogosto mišljeno, ko se v literaturi navaja samo-igranje. Iz praktičnih razlogov se proti sta- rim različicam navadno igra redkeje oz. več sredstev namenja trenutni, saj se stare ne učijo več.

Če bi pretekle različice vzorčili enakomerno, bi se precej iger zapravilo proti igralcem, ki so zlahka premagani. Namesto tega se je smiselno ravnati po priori- tetnem mehanizmu (ang. prioritised fictitious self-play) [109], kjer imajo pretekli igralci znano oceno sposobnosti, glede na katero so izbrani po določenem kriteriju.

Privzemimo, da se lahko izračuna ali oceni verjetnost zmage agenta v nad agen- tom w, P(v ≻ w). Tu se lahko obrnemo na sistem Elo [21], razširjen v šahu in drugod:

P(v ≻w) =σ(f(v)−f(w)) (2.21)

σ = 1

1 +e^−α·x

kjer je α >0, navadno α= ^log(10)₄₀₀ , ocene f pa so t. i. Elo ratingi.

Za uporabo Elo ratingov potrebujemo začetne vrednosti in načine posodobitve.

Če začenjamo z enim samim agentom, je dovolj, da se mu pripiše arbitrarno re- ferenčno vrednost, običajno 0 ali 1000. V primeru več agentov enemu pripišemo referenčno vrednost, za ostale pa ocenimo ratinge na podlagi zaporedja iger. Naj- prej so zgornje verjetnosti empirično ocenjene kot deleži zmag, nakar se uporabijo pri rešitvi optimizacijskih problemov naslednje oblike:

E_v = arg max

E∈N N

∏︂

i= 1

P(r_i|E, E_i), (2.22) kjer so r_i ∈ {−1,0,1} rezultati posamezne igre med danim agentom v in nasprotni- kom v igri i ter Ei ratingi agentov.

Nadalje so vrednosti (učenega agenta) posodobljene z:

E_vⁿ⁺¹ =E_vⁿ+K(max(r,0)−P(r = 1)). (2.23) in zamrznjene, ko je periodično shranjena pretekla različica. Vrednost K določa velikost posodobitve in ni konsistentno določena [114]. Intuitivno je večja za manj zanesljive ratinge in reda 10¹.

Z znanimi ratingi se nato za učenega agenta v vzorči nasprotnika u iz množice W z verjetnostjo:

f(P(v ≻u))

∑︁

w∈W

f(P(v ≻w)) (2.24)

z utežno funkcijo f : [0,1]→[0,∞).

Izbira f(x) = (1 −x)^p, kjer p ∈ R+ določa enakomernost porazdelitve, daje prednost težjim nasprotnikom, kar je v izrazito netranzitivnih igrah zaželeno, saj lahko povprečna uspešnost skriva velike pomanjkljivosti. Alternativno se lahko iz- beref(x) =x(1−x), ki je osredinjena pri ravni učenega agenta.

Formule se lahko ob rahli dopolnitvi uporabijo tudi za skupinske igre, s predpo- stavko da se lahko rating ekipe razstavi na vsoto ratingov njenih pripadnikov:

P(V ≻U) =σ (︄

∑︂

v∈V

f(v)− ∑︂

u∈U

f(u) )︄

(2.25) Ob ustrezni formulaciji je dosledno povečevanje Elo ratinga znak, da učenje napreduje v pravo smer, medtem ko sami signali iz okolja niso nujno dober pokazatelj v tekmovalnih igrah.

2.3.2 Učenje populacije

V igrah, ki dopuščajo obsežen nabor cikličnih strategij, lahko tudi igranje proti preteklim nasprotnikom ne zadošča za robustno učenje, saj se ne pokrije dovolj strateškega prostora.

Če si lahko privoščimo deliti sredstva, lahko pristopimo z učenjem populacije (ang.population-based training) oz. lige (ang.league training), ki skupaj optimizira populacijo modelov. V tej ima vsak član populacije bolj ali manj edinstven cilj oz.

nagradno funkcijo, da se doseže raznolikost med igralci in razvitimi strategijami ter stabilno učenje ob prisotnosti ciklov [35, 36].

Raznolikost se lahko nadalje spodbuja s posebnim izbiranjem nasprotnikov glede na strukturiranje igralcev po vzoru AlphaStar lige [109]: namesto, da bi se vsi agenti učili zmagovati proti vsem možnim igralcem, se določeni učijo izpostaviti šibke točke trenutne populacije ali le določene podmnožice agentov:

• Glavni agenti: Manjši nabor agentov z mešanim režimom učenja, ki daje pri- merljivo prednost samo-igranju in igranju proti populaciji.

• Izkoriščevalci glavnih agentov: Agenti, ki se učijo proti glavnim agentom in njihovim preteklim različicam, da jih naredijo bolj robustne.

• Izkoriščevalci populacije: Agenti, ki se učijo proti vsem predstavnikom po- pulacije. Njihov namen je izpostaviti luknje v globalnem naboru strategij s posluževanjem takih, ki jih nihče v trenutni populaciji ne more premagati, ampak niso nujno dolgoročno/splošno robustne.

Populacija se razvija po zgledu evolucijskih algoritmov: glavni agenti inicializi- rajo populacijo, potem pa se novi igralci periodično dodajo kot odcepitve obstoječih.

Pri tem se lahko spremeni njihova nagradna funkcija, prednostna izbira nasprotni- kov ali celo mutira hiperparametre učenja⁵. Populacija se s tem poveča, razen če je zavoljo namembe več sredstev bolj obetavnim agentom želeno najslabše nadomestiti.

5Mutacija skalarjev bi bila npr. pomnožitev z naključnim faktorjem v omejenem intervalu, muta- cija kategoričnih vrednosti pa naključno vzorčenje. Podrobnejša obravnava evolucijskih algoritmov je izven obsega tega dela in tudi povzeti viri [35, 36, 109] se ne spuščajo v podrobnosti.

Tekom učenja se je potrebno zavedati, da v netranzitivnih igrah Elo rating ne more napovedati izid določenega para – agenta s primerljivim ratingom lahko na- mreč pokrivata zelo različni strateški niši. Poleg tega je odvisen od nasprotnikov:

v trivialnem primeru je lahko pretiran zaradi sestave populacije iz kopij zlahka pre- magljivega agenta ali obratno.

Po [3, Balduzzi in dr.] se na primeru nakaže osnutek rešitve preko Nashovega ravnovesja. Zamislimo si meta-igro, kjer meta-igralca izbirata ekipe (utežene kom- binacije) agentov glede na njihove medsebojne verjetnosti zmage, povračilo pa je verjetnost zmage njunih ekip. Ko je na voljo dominanten agent, ki večinoma pre- maga ostale, ga bosta vedno izbrala oba meta-igralca, v primeru igralcev po shemi škarje-kamen-list pa je edina v povprečju nepremagljiva ekipa enakomerna porazde- litev. V splošnem je vrednost meta-igre 0 in Nashovo ravnovesje predstavljajo ekipe, ki so po pričakovanju nepremagljive.

Končni rezultat učenja populacije torej sestoji iz ansambla agentov zastopanih v Nashovem ravnovesju te meta-igre – najbolj učinkovita in robustna porazdelitev strategij, ki so bile odkrite glede na uspešnost agentov proti vsem ostalim, iz katere se vzorči določenega predstavnika.

2.3.3 Možnosti sporazumevanja

Do sedaj se je predpostavilo neodvisno obliko večagentnega učenja, kjer posamezni agenti med seboj niso povezani drugače kot preko deljenega okolja, v katerem de- lujejo posamezno – interakcije so omejene na opazovanja in dejanja [51]. Izjemoma naj se omeni pomislek pri oblikovanju nagrad v skupinskih igrah, kjer je lahko agent nagrajen za delovanje drugega.

Berner in dr. [7] v ta namen za OpenAI Five definirajo t. i. “moštveni duh”

(ang. team spirit), ki določa, v kolikšni meri si agenti delijo skupinske nagrade. Če vsakemu pripada osnovna nagrada ri, je dejanska nagrada rˆi določena v konveksni kombinaciji s povprečjem skupine r:

r

ˆ_i = (1−λ)r_i+λr, λ∈[0,1] (2.26) Končnemu cilju pritiče optimizacija za λ = 1, ki odraža dobrobit ekipe, ven- dar avtorji omenjajo, da se na začetku učenja bolje izkažejo nižje vrednosti, ker je nagradni signal jasnejši.

Zanimivo je, da OpenAI Five za zmago proti svetovnim prvakom v Doti 2 ni uporabljal neposrednega sporazumevanja. To se zdi neintuitivno, saj je v popularnih skupinskih e-športih komunikacija videna kot ključen del uspešnosti oz. je pogosto faktor, ki ločuje dobre ekipe od najboljših [31]. Namesto sklepa, da je komunikacija brezpredmetna, je tu pod vprašajem že sama potreba po izrecnem usklajevanju, saj si prijateljske entitete v Doti 2 pasivno delijo pogled ter druge informacije (torej jih ni potrebno izmenjati) in ker ekipo OpenAI Five tvorijo kopije – več instanc istega agenta, ki le upravljajo različne like. Po 45.000 letih skupnega igranja je očitno lahko prišlo do implicitne koordinacije glede na deljena opazovanja – naučili so se pozornosti na stanja soigralcev in iz tega razpoznati, kaj narediti. Morda je celo bolj zanimivo, da so v mešanih ekipah s človeškimi soigralci OpenAI Five agenti še vedno delovali, čeprav opazno bolj pasivno [73].

V splošnem se ne more predpostaviti, da bi se enako lahko doseglo v drugih igrah. Posebej v egocentričnih, kjer je pogled osredotočen na lastno entiteto, je deljivost informacij znatno manjša ali celo izključno omejena na prvoosebni pogled, kar naravno izkazuje potrebo po komunikaciji.

K razmišljanju, kako agentom omogočiti komunikacijo, se lahko pristopi dokaj splošno:

• Namembnost komunikacijskega kanala:

– za komunikacijo z naslovljeno entiteto, – za komunikacijo z več ali vsemi entitetami,

– za interakcijo z okoljem z možnostjo komunikacije.

• Kapaciteta komunikacijskega kanala za razločevanje pomenskih enot:

– možno vzporedno razločevanje iz enega sporočila, – potrebna interpretacija časovnega zaporedja sporočil.

• Sporočilni medij:

– slika (matrika ali trodimenzionalni tenzor), – zvok (par skalarjev ali vektorjev),

– abstraktni n-dimenzionalni tenzor.

• Interpretabilnost pojavljajočih se vzorcev;

• Univerzalnost oz. uporabnost med različnimi vmesniki;

• Enostavnost uveljavitve komunikacijskega sistema.

Naloga je lahko dodatno zahtevna, če jezik ni prizemljen, torej si ga morejo agenti izmisliti in se uskladiti pri skupnem standardu, s čimer je interpretabilnost še toliko težja [67, 29, 39, 96]. Za konkreten pregled komunikacije na področju spodbujevalnega učenja je bralec napoten k [53, Lazaridou in dr.]

2.4 Porazdeljeno procesiranje

Kot je bilo omenjeno v uvodu, se raziskovanje področja vedno bolj osredotoča na razvoj metod za učinkovito uporabo računskih zmogljivosti. V literaturi tudi ni nenavadno, da so algoritmi predstavljeni za ali skupaj z določeno konfiguracijo pro- cesov [22, 66].

Izpostavimo splošno konfiguracijo za en sam model agenta, kjer so lahko procesi, ki sodelujejo pri spodbujevalnem učenju – igralci, optimizatorji, prediktorji in drugi – porazdeljeni med različnimi napravami.⁶ Ko je definirana procesna arhitektura za en model agenta, se lahko naredi posplošitev za populacijo agentov s ponovitvijo arhitekture za vsakega sodelujočega agenta. Shema konfiguracije je prikazana na sliki 7.

6Tudi nadzorovano učenje je lahko porazdeljeno, vendar je konfiguracija razmeroma preprosta.

Primer je vključen v spremno implementacijo.

Nadzorni

proces modela idr.^Parametri

Prediktorji Optimizatorji

Igralci

Vrste epizod Vrste

opazovanj

Simulacije Opazovanja

Dejanja

Epizode Parametri Parametri

a)

b) c)

Slika 7: Shema platforme OpenAI Rapid, kot je bila uporabljena za OpenAI Five. a) Centraliziran nadzorni proces usklajuje sodelujoče komponente. b) Opazovanja več igralskih procesov se pošiljajo v vrste prediktorjev, ki jih obdelajo in nazaj pošljejo dejanja, da se uveljavijo v okolju. c) Epizodne izkušnje igralcev se periodično posre- duje v vrste optimizatorjev. Optimizatorji proizvedejo gradiente za vsak svoj paket vzorcev, sinhrono povprečijo gradiente med seboj [70] in vsak zase posodobijo pa- rametre – tako so parametri po vsakem koraku med njimi domnevno sinhronizirani, nakar morajo biti posredovani prediktorjem.

Konfiguracija ustreza splošnim razpoložljivim komponentam, a so določene na- prave načeloma bolj primerne za določene naloge. Npr. za simulacije igre lahko zadoščajo CPU-ji, prediktorji in optimizatorji pa navadno rabijo vsaj GPU-je.

Skaliranje tu deluje v več smereh. Za začetek, več kot imamo okolij in igralcev v njem, več opazovanj se bo proizvedlo. Nato se lahko te vzporedne simulacije pospeši in pridobi več podatkov v istem času. V kompromisu med paralelizacijo in pospešitvijo je prva bolj zaželena, saj so tako zmanjšane korelacije med podatki, in ker imajo prediktorji določen stalni časovni strošek. Za učinkovitost je lahko morda celo bolje, da se simulacije upočasni pod realnočasno hitrost in poveča raven paralelizacije.

Da bi obdelava lahko dohajala količino podatkov, je potrebno ustrezno povečati tudi kapacitete prediktorjev in optimizatorjev. Ko so dosežene meje skaliranja v širino, se lahko podaljša čas oz. trajanje učenja pri tej širini sodelujočih naprav.

Nazadnje, če imamo toliko podatkov, potrebujemo tudi model s kapaciteto, ki jih dejansko lahko izkoristi. Deluje tudi obratno – večji in kompleksnejši model bo potreboval več podatkov. Uravnovešenje teh razsežnosti je previdno delo, odvisno od danega problema in sploh razpoložljivih sredstev.

Zaradi ločitve komponent lahko pride do opaznih asinhronosti in posledično raz- meroma nizke izkoriščenosti naprav: veliko je prenašanja podatkov in komunikacij- skih zamud, sploh če je sodelujočih naprav veliko, kar ima lahko logistične ovire.

Komunikacija je lahko problem tudi pri sami simulaciji okolja: če gre za večagen- tno okolje, je posodabljanje okolja (poleg časa za predikcijo) pogojeno z odzivnostjo igralcev. Komunikacijske zamude lahko omili združitev določenih procesov pod isto napravo in deljenja spomina med njimi, a na račun porazdeljenosti.

Asinhronosti so lahko še bolj težavne za samo učenje. Po shemi na sliki 7 se morajo parametri prediktorjev redno posodabljati: preden dobijo novo verzijo pa- rametrov θⁿ, so lahko že nekaj časa delovali pri, recimo, m gradientnih posodobitev zaostalih parametrih θ^n−m. To ni skladno s predpostavko, da so bili vzorci proi- zvedeni s strani aktualne strategije, a so načeloma odstopanja lahko še dopustno majhna, da off-policy popravki niso potrebni: OpenAI Five je tako uporabljal on- policy PPO, a z opazko, da je že malo zaostajanje vodilo do poslabšane konvergence učenja [7].

Učinkovito skaliranje procesov je torej tehnično težavno. Da se ga sploh lahko poslužujemo, pa potrebujemo primerno simulacijsko okolje.

3 Predstavitev okolja

Predstavljeno je ustrezno izhodišče za merilo spodbujevalnega učenja in opisano nastalo simulacijsko okolje. Zaradi obsega dela poglavje ni zamišljeno kot izčrpna dokumentacija. Namesto tega se osredotoča na zunanjo podobo igre skupaj z osre- dnjimi sistemi – grafičnim in zvočnim sistemom ter omrežno arhitekturo, sicer pa na vidike, ki podpirajo posnemovalno in porazdeljeno spodbujevalno učenje.

3.1 Zgled

Z ozirom na zagotavljanje igranja pod karseda enakimi pogoji obstaja že predhodni zgled (celo s strani določenih članov AlphaStar ekipe): t. i. FTW agenti [36] (ang.for the win) v obliki prvoosebne večigralske igre “osvoji zastavo” (ang. capture the flag) namesto poenostavitev vmesnika opazujejo zaporedje slik in delujejo prevedljivo na uporabo miške in tipkovnice. Natančnost in odzivni čas agentov se je lahko relativno enostavno omejilo in ko so še vedno konsistentno premagovali človeške ekipe, je bil strateški vzrok lahko jasno utemeljen.

Primer podviga je sicer manjšega obsega, igra je preprostejša in zaradi lastne, zaprte implementacije okolja ni bilo nabora vrhunskih nasprotnikov za primerjavo, a nakazuje, da se vsaj v določenem tipu video iger lahko uporabi enakovreden vmesnik in še vedno pridobi kompleksne vzorce vedenja, kot sta predvidevanje in sodelovanje na podlagi strukturiranega zavedanja trenutnega stanja.

Tako se osredotočimo na trodimenzionalne prvoosebne igre – popularen žanr z velikim številom predstavnikov, vendar manj kandidati, ki bi za umetno inteligenco predstavljali podobno velik izziv kot omenjena RTS velikana StarCraft II in Dota 2.

Predvsem gre namreč za izpeljanke t. i. deathmatch načina, ki je bil že obravnavan v okviru različnih iger [50, 106, 79] in ki poglavitno izpostavlja zaznavno-motorično sposobnost merjenja in odzivnega časa.

Primer obstoječe igre, ki je prvoosebna, taktična in ima primerljivo bogato zgo- dovino kot profesionalni e-šport, je Counter-Strike.

3.1.1 Counter-Strike

Counter-Strike, specifično zadnja iteracija, Counter-Strike: Global Offensive, kraj.

CS ali CSGO⁷, je večigralska prvoosebna strelna igra ameriškega razvijalca Valve.

Od izida leta 2012 je CSGO gradil na slovesu predhodnikov do statusa ene izmed najpopularnejših iger po številčnosti igralcev, s povprečno pol milijona sočasnih igralcev [95] in okoli 20 milijonov igralcev mesečno [15], in gledanosti medijev [14].

Vključno od predhodne različice (1.6) so bili turnirji organizirani od leta 2000 dalje, kar igro postavlja med najstarejše uveljavljene e-športe [113].

7Iztočnice slikovnih in vsebinskih virov:

https://store.steampowered.com/app/730/CounterStrike_Global_Offensive/

https://steamcommunity.com/app/730 https://blog.counter-strike.net/

https://developer.valvesoftware.com/wiki/Counter-Strike:_Global_Offensive https://counterstrike.fandom.com/wiki/Counter-Strike_Wiki

Igra se odvija na t. i. mapi, umetnem okolju, v katerem so pazljivo razporejeni taktični gradniki, da usmerjajo in pogojujejo napredovanje po njej. Ovire so lahko premostljive, pogojno premostljive ali nepremostljive in dajejo različno mero kritja, tako pred pogledom kot streli nasprotnikov.

Slika 8: Označen tloris in delni prikaz najznamenitejše mape v CS-u: Dust2.

Osnovna nadzorna shema v CS-u je tipična med prvoosebnimi igrami: tipkovnica je uporabljena za premikanje v prostoru, miška pa za vrtenje pogleda in merjenje orožja okoli vertikalne in horizontalne osi. Poleg orožja lahko igralec nosi in upo- rablja določeno pomožno opremo in notranji denar, za katere je številski status prikazan na igralčevem zaslonu (slika 9).

Slika 9: Onesposobljanje bombe v CSGO.

Po standardnem formatu se dve ekipi po 5 igralcev asimetrično pomerjata v napadu in obrambi: cilj teroristov ⁸ je v omejenem času detonirati bombo na enem izmed v naprej označenih mest (oranžni območji na tlorisu slike 8 oz. mesti A in B), protiteroristi pa morajo to preprečiti (slika 9).

8V žargonu skupnosti se je zaradi občutljivosti tematike uveljavilo naslavljanje T-ji in CT-ji.

Igra poteka v rundah, ki v povprečju trajajo dve do tri minute: po 15 rundah ekipi zamenjata strani in igrata do 16 zmag ali neodločenega izida oz. razrešitve v podaljšku. Po vsaki rundi do menjave strani se imetje preživelih igralcev (vključno s pobranim) prenese v naslednjo z denarnimi nagradami glede na razplet runde, niz porazov in uboje nasprotnikov. Denar je lahko porabljen za nadgradnjo orožja ali nakup pomožne opreme.

Uspeh v CS-u zahteva obvladovanje veščin čez več časovnih okvirov: Igralec (dalje tudi agent) mora nadzorovati svoje gibanje in merjenje ter se odzivati na nevarnosti v okolju. Usmerjati se mora skozi predele mape in razpolagati s sredstvi, kot so življenjske točke in strelivo. Tekom rund se mora prilagajati v sodelovanju s soigralci in glede na nasprotnike, usklajevati načrte in načrtovati uporabo denarnih sredstev (ekonomijo). Splet naštetega obrodi kompleksno in dinamično vedenje, tako na ravni posameznika kot skupine.

3.1.2 Ustreznost kot merilo umetne inteligence

Poleg omenjenega ima CS določene plati, ki predstavljajo vrsto aktualnih in novih problemov, ki so zanimivi za raziskovanje umetne inteligence ter hkrati tehnični in teoretični izziv.

Komunikacija Skupinska dinamika v boju za nadzor območij je močno pogojena s pridobivanjem in deljenjem informacij. V tem je naravna priložnost, da okolje samo spodbuja oz. zahteva aktivno usklajevanje in posluževanje komunikacijskih orodij:

• Skupna ekonomija: Čeprav so denarne nagrade dodeljene igralcem posamično, si lahko v CS-u igralci delijo imetje med seboj in tako omogočijo ekipi boljše možnosti za zmago – bodisi z okrepitvijo denarno prikrajšanih bodisi s podporo sposobnejših soigralcev.

• Nedodeljenost vlog: Vsi igralci v ekipi začnejo enaki. Razlike med njimi se naknadno dosežejo preko individualnih izbir opreme, sloga igranja in razpleta posameznih rund. Tako vlog ne določa okolje samo, ampak se morajo igralci redno uskladiti med seboj.

• Medsebojna informacijska nepopolnost: Poleg nedostopnosti stanja nasprotne ekipe igralci tudi nimajo dostopa do vseh informacij svojih soigralcev (zaradi prvoosebnega pogleda). Tako je informacijska nepopolnost razširjena na lastno ekipo, zato je dosti težje sklepati o globalnem stanju okolja in so si informacije primorani izmenjati.

Uporaba zvoka Niti avtorji AlphaStar-ja niti avtorji OpenAI Five se niso odločili dovesti zvočnih informacij svojim agentom. Da je bilo zmagovanje proti ljudem brez teh informacij vseeno uspešno, priča o tem, da niso imele bistvenega pomena – vloga zvoka v danih okoljih je bila spremljevalna natančno lokaliziranim vizualnim signalom in namenjena zgolj bolj prepričljivi atmosferi, vendar ne odločilna za potek igre same.