Multiagentní zpětnovazební učení

Cílem zpětnovazebního učení je naučit se chování v prostředí. Máme agenta v prostředí, kde může provádět řadu akcí. Každá akce nějak prostředí změní (transformuje ho do nového stavu) a po provedení akce může agent dostat odměnu. Cílem agenta je maximalizovat tuto odměnu. Při multiagentním zpětnovazebním učené je v prostředí více agentů současně. Tito agenti mohou buď spolupracovat (např. při společném řešení problému), nebo soutěžit (např. když se učí hrát fotbal).

Prostředí můžeme formálně popsat jako markovský rozhodovací proces (MDP), který je zadaný čtveřicí $(S, A, P, R)$, kde $S$ je konečná množina stavů prostředí, $A$ je (konečná) množina akcí (případně může být nahrazena množinami $A_s$ akcí aplikovatelných ve stavu $s$), $P_a(s, s’)$ je přechodová funkce, která udává pravděpodobnost, že aplikací akce $a$ ve stavu $s$ přejde prostředí do stavu $s’$ a $R_a(s, s’)$ je funkce odměn, která udává okamžitou odměnu, kterou agent dostane od prostředí, pokud ve stavu $s$ provede akci $a$ a převede tím prostředí do stavu $s’$. U přechodové funkce je důležité, že splňuje tzv. markovskou podmínku, tj. že závisí pouze na aktuálním stavu $s$ a akci $a$ a nikoliv na akcích a stavech předcházejících.

Chování agenta potom můžeme popsat pomocí strategie (policy) $\pi: S \times A \to [0,1]$, kde $\pi(s,a)$ udává pravděpodobnost provedení akce $a$ ve stavu $s$. Cílem zpětnovazebního učení je potom najít strategii $\pi$ takovou, že maximalizuje celkovou odměnu, kterou agent získá $\sum_{t=0}^\infty \gamma^tR_{a_t}(s_t, s_{t+1})$, kde $a_t = \pi(s_t)$ je akce provedená agentem v kroku $t$ a $\gamma < 1$ je diskontní faktor, který zajišťuje, že suma je konečná.

Hodnota stavu a hodnota akce

Hodnota stavu $s$ při použití strategie $\pi$ je definována jako $V^\pi(s) = \mathrm{E}[R] = \mathrm{E}[\sum_{t=0}^\infty \gamma^t r_t|s_0 = s]$, kde $R$ je celková diskontovaná odměna a $r_t$ odměna získaná v kroku $t$. Kromě hodnoty stavu uvažujeme také hodnotu akce $a$ ve stavu $s$, pokud se dále pokračuje podle strategie $\pi$. Ta se značí jako $Q^\pi(s, a)$. Výhodou tohoto přístupu je, že nepotřebujeme model prostředí, který popisuje, jak akce prostředí ovlivňují. Agent se může naučit tento model během toho, co se učí chování.

Cílem agenta je tedy nalezení strategie $\pi^\star$, takové, že $V^{\pi^\star}(s) = \max_\pi V^\pi(s)$.

Q-učení

$Q$-učení je klasický algoritmus pro zpětnovazební učení. Tento algoritmus se snaží naučit výše definovanou funkci $Q$ a reprezentuje ji jako matici s řádky pro každý stav a sloupci pro každou akci. Tato matice je aktualizována pokaždé, když agent provede akci v prostředí a získá odměnu. Aktualizace je založena na tzv. Bellmanových rovnicích \(Q^{\pi}(s,a) = \sum_{s'} \mathcal{P}_{s s'}^{a} \Big[ \mathcal{R}_{s s'}^{a} + \gamma \sum_{a'} \pi (s', a') Q^{\pi}(s', a') \Big].\) Konkrétně, kdykoli agent provede akci $a_t$ ve stavu $s$ a obdrží odměnu $r$, je matice $Q$ aktualizována následujícím způsobem: \(Q^{new}(s_{t},a_{t}) \leftarrow (1-\alpha) \cdot Q(s_{t},a_{t}) + \alpha \cdot \bigg( r_{t} + \gamma\cdot \max_{a}Q(s_{t+1}, a) \bigg),\)

kde $\alpha$ je rychlost učení a akci $a_t$ lze vybrat několika metodami. Nejběžnější z nich je tzv. $\epsilon$-greedy strategie, která vybere nejlepší akci (podle $Q$) s pravděpodobností $\epsilon$ a vybere náhodnou akci s pravděpodobností $1-\epsilon$. Náhodnost zlepšuje exploraci (zkoušení nových akcí) při $Q$-učení.

Deep Q-Learning

Moderní implementace $Q$-učení je založena na hlubokých neuronových sítích. V hlubokém $Q$-učení je trénována neuronová síť tak, aby aproximovala matici $Q$. Dostává na vstupu stavy a vrací hodnoty všech akcí v daném stavu. Během tréninku agent provádí akce v prostředí a pamatuje si stavy, akce a získané odměny. Na jejich základě je sestavena trénovací množina a síť je trénována tak, aby minimalizovala rozdíl mezi $Q(s, a)$ a $R_a(s, s’) + \gamma max_{a’}Q_k(s’, a’)$. Ztrátová funkce pro toto trénování je tedy

\[\mathbb E_{s' \sim P_a(s, s')}\big[ (R_a(s, s') + \gamma \max_{a'}Q_\theta(s', a') - Q_\theta(s, a))^2 \big]\\|{\theta = \theta_k}.\]

Při trénování pomáhají uložené trojice stavu, akce a získané odměny, protože síť může informace použít vícekrát. Tato uložená zkušenost (tzv. experience buffer) také pomáhá snížit korelaci vstupů sítě, což zlepšuje trénink. Často se používá i další trik - může být problém v tom, že stejná síť je trénována a zároveň používána pro výběr akce. Proto se někdy používají dvě sítě, jedna je pevná a používá se pro výběr akce, zatímco druhá je trénovaná. Po určitém počtu epoch je pevná síť nahrazena trénovanou a trénování pokračuje.

Evoluční algoritmy

Kromě použití hlubokého $Q$-learningu je také možné trénovat neuronovou síť pomocí evolučních algoritmů. V tomto případě zakódujeme všechny váhy v neuronové síti jako jedince evolučního algoritmu a použijeme evoluční algoritmus pro spojitou optimalizaci (např. evoluční strategii nebo diferenciální evoluci). Celková odměna, kterou agent získá, se použije jako fitness funkce a maximalizuje se. Hlavní výhodou tohoto přístupu je, že je snazší učení paralelizovat (v RL může být vyhodnocení prostředí nejpomalejším krokem) a evoluční algoritmus dobře funguje i v případech s řídkými odměnami (tj. prostředí dává odměnu pouze v některých krocích, v extrémním případě pouze v posledním).

Multi-agentní zpětnovazební učení

Algoritmy pro multi-agentní zpětnovazební učení jsou často založeny na algoritmech pro jednotlivé agenty popsaných výše. Nejjednodušší modifikací (použitelnou zejména v kooperativních případech) je tzv. joint-action learning (JAL). V JAL jsou všichni agenti modelováni jako jeden agent s $n$-ticemi akcí - jednou pro každého agenta. To znamená, že algoritmus Q-učení lze použít téměř přímo, nicméně hlavní nevýhodou je, že počet akcí exponenciálně roste s počtem agentů.

Další oblíbenou technikou je self-play, při self-play simulujeme řadu agentů, každý z nich se rozhoduje nezávisle, nicméně všichni mají stejný rozhodovací postup (např. neuronovou síť) pro výběr akce. V takovém případě máme vlastně sadu identických agentů. I když to omezuje expresivitu možných strategií (všichni agenti se chovají stejně), značně to snižuje složitost problému. Self-play se často používá v kompetitivním případě. Například pokud chceme trénovat agenty na fotbal, můžeme jednomu týmu dát strategii (např. náhodně inicializovanou neuronovou síť) a druhý tým se proti ní učí hrát. Po nějakém čase, když je druhý tým schopný porazit ten první, nastavíme strategii prvního týmu na tu, co se naučil druhý tým, a pokračujeme v tréninku proti této vylepšené strategii. To také znamená, že nemusíme mít strategii, proti které bychom trénovali, tuto strategii vytváříme (a vylepšujeme) během tréninku výsledné strategie.

Jak určit, zda je naše strategie (pro celý systém) optimální? Co to vůbec znamená, aby strategie byla optimální? Existuje několik běžných kritérií, která můžeme použít. Jedním z nich je, že soubor strategií pro agenty by měl být Nashovým ekvilibriem (tj. žádný agent nemůže zlepšit svůj užitek jednostrannou změnou strategie), dalším kritériem by mohla být Pareto optimálnost (tj. neexistuje žádná jiná množina strategií, která by dával větší užitek všem agentům současně). Dalším běžnou mírou kvality strategií je sociální blahobyt (social welfare) a sociální spravedlnost (social fairness). Sociální blahobyt je součtem celkových užitků strategií, zatímco sociální spravedlnost je součinem těchto užitků. Proto je sociální spravedlnost maximalizována, pokud mají všichni agenti stejné (nebo podobné) užitky.

Úkol

Vaším posledním úkolem je implementovat jeden z algoritmů pro zpětnovazební učení v multi-agentních systémech pro zjednodušenou verzi problému level-based foraging. V tomto problému agenti mají za úkol sbírat objekty z prostředí. Agenti i objekty však mají úrovně a agenti mohou objekt sebrat objekt pouze tehdy, je-li součet úrovní všech agentů sousedících s objektem vyšší než úroveň objektu. V našem zjednodušení mají všichni agenti úroveň 1 a všechny objekty mají celočíselnou úroveň mezi 1 a počtem agentů v systému. Nebudeme také kontrolovat sousední pozice, ale pouze počet agentů na stejné pozici jako objekt. Objekty jsou automaticky sebrány vždy, když je počet agentů v místě objektu stejný nebo vyšší než úroveň objektu.

Prostředím tohoto problému je čtvercová mřížka a objekty a agenti jsou na začátku na náhodných místech. Agenti dostanou odměnu rovnající se úrovni objektu za libovolný sebraný objekt a také -0,1 za každé krok v simulaci. Hodnotí se tedy jak sebrání objektů, tak doba, kterou to zabere.

Implementace tohoto prostředí a jednoduchého příkladu agenta (se joint akcemi) je v přiložených zdrojových kódech. Je tam také opravdu jednoduchá vizualizace, kde agenti jsou oranžovo-červené čtverce (tmavší barvy pro více agentů na stejném místě) a objekty jsou modré čtverce (tmavší barvy pro objekty s vyšší úrovní).

V podstatě musíte implementovat dvě metody agenta - action a reward. Metoda action získá stav jako dvojici mapy světa a poloh agentů (ve mapě představují záporná čísla agenty - $-i$ znamená, že na daném místě je $i$ agentů - a kladná čísla jsou objekty a jejich úrovně). Polohy agentů jsou ve stejném pořadí, ve kterém byste měli vrátit seznam akcí pro agenty (tj. $i$-tá akce bude použita pro agenta na $i$-té pozici v seznamu poloh). Jsou pouze čtyři možné akce - NORTH, SOUTH, WEST a EAST - reprezentované čísly 0-3. Funkce reward je volána po každém kroku, aby informovala agenty o odměně, kterou získali v předchozím kroku.

Na úkolu můžete pracovat v týmech do 4 studentů. Nicméně nejjednodušší řešení (manuální implementace strategie za 5 bodů) a implementace frameworku v jiném jazyce jsou dostupné pouze pro jednotlivce (ty jsou opravdu jednoduché). Řešení za 8 bodů by mělo být proveditelné pomocí Q-learningu, nicméně může být zapotřebí určité chytré reprezentace stavu (která sníží počet stavů) a také využití chytřejších akcí (jako je přesun nejbližších agentů směrem k danému místu).

Termín pro odevzdání je stanoven daleko v budoucnosti, takže máte dostatek času na něm pracovat. To neznamená, že by zadání mělo být tak těžké - jen vám to dává příležitost získat nějaké body později, pokud je budete potřebovat.

Termín: 15. září 2024
Body:

Pro nalezení strategie založené na RL můžete pracovat v týmech do 4 studentů. Jednoduché, skriptované strategie (za 5 bodů) budou přijímány pouze od jednotlivců (nikoli týmů).

Mgr. Martin Pilát, Ph.D.
Malostranské náměstí 25
118 00 Praha
Martin.Pilat@mff.cuni.cz