Zagadnienia

15.1 Uwagi wstępne
15.2 Uczenie się przez wzmacnianie
- 15.2.1 Model Rotha i Ereva
- 15.2.2 Model Busha-Mostellera
15.3 Inne typy uczenia

15. Elementy teorii uczenia się w grach

15.1. Uwagi wstępne

Sformułowanie ”uczenie się”, lub ”uczenie” (będziemy oba te terminu używać wymiennie) w modelach teoriogrowych ma szeroki sens. W ogólności oznacza zmianę, dopasowywanie strategii przez graczy. Celem tych zmian jest optymalizacja użyteczności granych strategii, przy uwzględnieniu reakcji przeciwników, i ewentualne osiągnięcie równowagi. Jest wiele sposobów definiowania, opisu, za pomocą teoriogrowych modeli formalnych, procesu uczenia się. W szczególności rozważa się zarówno modele w których uczenie się jest wynikiem powtarzalnych interakcji między skończoną grupa graczy (np. między dwoma graczami), jak i uczenie w populacjach z continuum graczy. Rozważa się zarówno interakcje opisywane przez gry ekstensywne, jak i powtarzalne gry strategiczne.

W [5], str. 3 autorzy określają w nastepujący sposob model uczenia:

A ”learning model” is any model that specifies the learning rules used by individual players and examines their interaction when the game (or games) is played repeatedly.

”Strategicznym” celem różnych modeli uczenia się jest modelowanie rzeczywistych procesów ekonomicznych i społecznych. Teoria gier odgrywa tu ważną rolę jako środek opisu interakcji między podmiotami. Z formalnego punktu widzenia efekt uczenia sie to pewien stan, na ogół stacjonarny, o własnościach stabilności, który jest osiągany w wyniku procesu uczenia. Na ogół chce się by formalnym wynikiem procesu uczenia się byłoosiagnięcie pewnego stanu równowagi, typu równowagi Nasha, opisywanego przez atraktor odpowiedniego układu dynamicznego.

Istnieje wiele bardzo różnych modeli formalnych uczenia. Różnorodność modeli uczenia się odzwierciedla różnorodność możliwych założeń dotyczących graczy, stopnia złożoności ich zdolności analizowania sytuacji i możliwych reakcji, zakresu i złożoności uzyskiwanych informacji o grze, o przebiegu gry itp. Poszczególne modele uczenia się zależą w szczególności od

1. funkcji użyteczności (wypłat) graczy

2. informacji posiadanej przez graczy

3. Pamięci (o poprzednich rundach) posiadanej przez graczy i od ich zdolności obliczeniowych (np. można założyć zdolność wykonywania operacji arytmetycznych).

4. Typu zbioru graczy: może to być np. zbiór dwóch graczy, skończony zbiór graczy grających w gry dwu- lub wieloosobowe, zbiór continuum graczy–mamy wtedy do czynienia z grami populacyjnymi.

Najprostsze modele sa opisywane angielskim terminem reinforced learning, króry będziemy tłumaczyć jako uczenie się przez wzmacnianie, i opisują graczy reagujących na bodźce które podwyższają lub obniżają prawdopodobieństwo grania danymi strategiami. Przykładowe modele omówimy w następnym podrozdziale. Prostota tych modeli jest pozorna, odpowiednie modele formalne, opisywane za pomocą procesów Markowa, są na ogół skomplikowane (w szczególności gdy nie są to łańcuchy Markowa) i trudne do ścisłej analizy matematycznej. Jest też szeroka gama bardziej wyrafinowanych formalnie modeli, w których gracze mają określoną wiedzę o przeciwnikach, o używanych przez nich strategiach i otrzymywanych przez nich wypłatach, i którzy mają możliwości prognostyczne przewidywania kolejnych etapów gry. Gracze mają pewne przewidywania, przekonania (predictions, beliefs) dotyczące wyboru akcji przez przeciwników w przyszłej rundzie (ogólniej—-w przyszłych rundach) i grają ”optymalne” akcje. Do takich modeli należą modele imitacji, modele lepszych i najlepszych odpowiedzi (myopic better or myopic best response) oraz modele gry fikcyjnej (fictitious play) i gry fikcyjnej z szumem (smooth fictitious play).

Uwaga 15.1

Historycznie Cournot i Bertrand stworzyli pierwsze modele formalne oparte o uczenie się graczy. Co więcej, wynikiem odpowiednich algorytmów uczenia się była równowaga Nasha.

15.2. Uczenie się przez wzmacnianie

Uczenie się przez wzmacnianie (reinforcement learning) jest jednym z najprostszych modeli uczenia. Można go rozpatrywać zarówno dla gier rozgrywanych wielokrotnie między dwoma graczami, jak i dla gier populacyjnych. W literaturze stosowana jest też nazwa stimulus–response models, używana np. w modelu Busha–Mostellara zaproponowanym w latach 50ych XX wieku.

Podstawową cechą takich modeli jest fakt że strategie które daja ”satysfakcjonujący” wynik (np. nie gorszy od oczekiwań, aspiracji) będa w przyszłej rundzie grane z większym prawdopodobieństwem. W modelu tym jedyną informacją jaka posiada gracz jest jego wypłata w danej rundzie. Opiszemy modele w którym stopień wzmocnienia tendencji (prawdopodobieństwa) grania daną strategią w nastepnej rundzie zależy od różnicy między wypłatą uzyskiwaną z tej strategii, a pewnym poziomem aspiracji. W ogolności poziom aspiracji może być endogeniczny, ulegający zmianie w trakcie kolejnych rund. W opisywanym modelu poziom aspiracji będzie stały, egzogeniczny.

Model jest w pewnym sensie ”prymitywny”–gracze nie znają strategicznej postaci gry, a jedynie otrzymywaną wypłatę. Gracze nie potrzebuja znać wypłat z poszczególnych strategii, a nawet nie muszą wiedzieć że biorą udział w grze.

Uwaga 15.2

Uczenie się przez wzmacnianie nazywa się też uczeniem adaptacyjnym (learning through adaptation). Inne przedstawione niżej typy uczenia się będziemy nazywać uczeniem wyrafinowanym (sophisticated learning) (inne tłumaczenia tego zwrotu: ”wymyślne”, czy też ”finezyjne” uczenie się, wydają się jeszcze gorsze).

15.2.1. Model Rotha i Ereva

Omówimy model zaproponowany przez Rotha i Ereva [28]. Rozważamy dwuosobową GS z dodatnimi wypłatami. Gracz $i$ ma $r_{i},i=1,2$ strategii. Każdej z nich jest przypisana zależna od czasu nieujemna liczba, która nazwiemy inklinacją (propensity) $\theta _{{ij}}(t),\ i=1,2,\ k=1,...r_{i}.$ Jest to ”tendencja, skłonność” gracza $i$ do grania strategią $k$ . Każdemu graczowi jest w ten sposób przypisany wektor wag

$\sigma _{i}(t)=(\sigma _{{i1}}(t),...\sigma _{{ir_{i}}}(t)):\ \ \sigma _{{ik}}=\frac{\theta _{{ik}}}{\sum _{{l=1}}^{{r_{i}}}\theta _{{il}}}\ \ i=1,2.$

(15.1)

Mając dany wektor wag $\sigma _{i}(t)$ będziemy mówili że gracz $i$ stosuje (gra) w chwili $t$ strategię mieszaną $\sigma _{i}(t)$ . Znajdziemy równanie ewolucji $\sigma _{i}(t)$ .

Niech $s_{i}=s_{i}(t),\ i=1,2$ oznacza strategię czystą graną przez $i$ w $t$ , a (z pewną nieścisłością oznaczeń) $\pi _{i}\equiv\pi _{i}(t)$ wypłatę $i$ gdy gracze grają tymi strategiami. Wprowadzimy też dla każdej strategii czystej $s_{{ik}}\in A_{i},i=1,2,\ k=1,...r_{i}$ jej funkcję indykatorową, pomnożoną przez wartość wypłaty (”skalowaną przez wypłatę”):

$\psi _{{ik}}=\pi _{i}$ gdy $s_{i}=s_{{ik}}$ , czyli gdy w chwili t jest grana strategia $s_{{ik}},\ \ i=1,2,$

$\psi _{{ik}}=0$ wpp.

Definiujemy dynamikę zmian inklinacji graczy:

$\theta _{{ik}}(t+1)=\theta _{{ik}}(t)+\psi _{{ik}}(t),\ \ i=1,2,\ \ k=1,...r_{i}.$

(15.2)

Każda grana strategia otrzymuje wzmocnienie w wysokości uzyskanej z niej wypłaty. Jeżeli założymy że kazdy gracz ma staly poziom aspiracji równy zero, to równoważnie możemy powiedziec że wzmocnienie jest równe różnicy pomiędzy wypłata a poziomem aspiracji. W tym sensie model ten zakłada dodatnie wzmocnienie (positive stimulus). Istnieje cała gama modeli w których wzmocnienie może być ujemne oraz w których poziom aspiracji jest zmienną endogeniczną i może być inny dla każdego gracza, patrz np. [38, 23, 22].

Po przekształceniach algebraicznych otrzymujemy, zakładając jednostajną ograniczoność $\psi _{{ij}},\pi _{i}$

$\sigma _{{ik}}(t+1)=\sigma _{{ik}}(t)+\frac{1}{\Theta(t)}[\psi _{{ik}}(t)-\pi _{i}(t)\sigma _{{ik}}(t)]+0(\frac{1}{[\Theta _{i}]^{2}}),\ \ i=1,2,\ \ k=1,...r_{i},$

(15.3)

gdzie $\Theta _{i}(t)=\sum _{{k=1}}^{{r_{i}}}\theta _{{ik}}(t),\ 0(a)$ oznacza skladnik rzędu $a$ . Ponieważ $\psi _{{ij}},\pi _{i}$ są zmiennymi losowymi (ich realizacje zależą od wybory strategii czystych przez graczy), więc mamy w ten sposób określony proces stochastyczny. Okazuje się że równanie na wartości oczekiwane przyrostów wag $\sigma _{{ik}}(t+1)-\sigma _{{ik}}(t)$ są analogiczne do równań replikatorowych dla dwóch populacji. Dla gier $2\times 2$ zostały udowodnione odpowiednie twierdzenia aproksymacyjne, patrz np. [21].

Formalna prostota modelu jest wynikiem minimalnych założeń o wiedzy i ”kognitywnych” umiejętnościach graczy–znają oni jedynie swoje wypłaty (np. z poprzedniej rundy) i na podstawie tej wiedzy podejmują decyzję o wyborze przyszłej akcji.

15.2.2. Model Busha-Mostellera

Jest to drugi podstawowy model uczenia przez wzmacnianie. Jest 2 graczy, każdy ma do wyboru dwie (takie same) akcje, każda z nich wybiera z pewnym prawdopodobieństwem. Po wyborze akcji i otrzymaniu wypłat każdy z graczy uaktualnia prawdopodobieństwa. Jeżeli wypłata jest wyższa od pewnego poziomu aspiracji to prawdopodobieństwo użycia w następnym kroku akcji zagranej poprzednio rośnie, wpp. maleje.

Niech $y=(y_{1},y_{2}),\ y_{i}\in A_{i},\ i=1,2$ –profil strategii czystych graczy, $u_{i}(y_{1},y_{2})$ –wypłata gracza $i$ z takiego profilu. Niech $p=(p_{1},p_{2})$ –profil strategii mieszanych graczy: $p_{i}$ oznacza prawdopodobieństwo grania pierwszej strategii przez gracza $i$ .

Niech $y^{n}=(y_{1}^{n},y_{2}^{n})$ –profil strategii czystych zagrany w $n$ –tym kroku. Definiujemy stymulus (stimulus) gracza $i$ :

$s_{i}(y^{n})=\frac{u_{i}(y^{n})-As_{i}}{sup_{{a\in A_{1}\times A_{2}}}|u_{i}(a)-As_{i}|},$

(15.4)

gdzie $As_{i}$ oznacza ustalony poziom aspiracji gracza $i,i=1,2$ .

Zauważmy że $s_{i}\in[-1,1]$ –stymulus może być dodatni lub ujemny. Widać że do obliczenia stymulusa gracza potrzebna jest jego wypłata, poziom aspiracji oraz znajomość wypłat z wszystkich profili czystych, natomiast gracze nie znają wypłat i wyboru akcji przeciwników.

Stymulus posłuży nam do zdefiniowania (dyskretnej) dynamiki układu, czyli u nas do uaktualniania prawdopodobieństwa grania np. pierwszej strategii przez obu graczy.

Niech $p_{{i,y_{i}}}^{{n+1}}$ oznacza prawdopodobieństwo że gracz $i$ w $n+1$ rundzie zagra $y_{i}$ . Dynamika ma postać:

$p_{{i,y_{i}}}^{{n+1}}=p_{{i,y_{i}}}^{{n}}+l_{i}s_{i}(y^{n})(1-p_{{i,y_{i}}}^{{n}})$

(15.5)

jezeli $s_{i}(y^{n})\ge 0$ , oraz

$p_{{i,y_{i}}}^{{n}}+l_{i}s_{i}(y^{n})p_{{i,y_{i}}}^{{n}}$

(15.6)

jeżeli $s_{i}(y^{n})<0.$ Parametr $l_{i}\in[0,1]$ nazywamy tempem uczenia się (learning rate).

Prawdopodobieństwo akcji nie zagranej jest uaktualniane tak by w sumie z prawdopodobieństwem akcji zagranej dawały 1. Im większy iloczyn $l_{i}s_{i}(y^{n})$ tym większa zmiana prawdopodobieństwa.

Otrzymaliśmy pewien model stochastyczny, ze stanem układu opisywanym przez wektor losowy $(p_{1},p_{2})$ . Realizacja zmiennej losowej $p_{i},\ i=1,2$ to prawdopodobieństwo zagrania przez gracza $i$ w kolejnym kroku pierwszej z dwóch dostepnych mu strategii. Model ten jest dyskretnym w czasie procesem Markowa z ciagłą przestrzenią stanów.

Przedstawiony model obejmuje dowolne gry 2x2, niekoniecznie symetryczne.

Używając symulacji komputerowych Flache i Macy [4] znaleźli dwa rodzaje równowag w modelu BM, które nazwali selfreinforcing equilibria oraz selfcorrecting equilibria. Te równowagi profile strategii do których dąży układ. Matematyczną formalizację tych pojęć można znaleźć w [12].

15.3. Inne typy uczenia

15.3.1. Uczenie się przez imitację

O imitacji mówimy gdy gracz w następnej rundzie rozgrywanej gry symetrycznej gra pewną strategią innego gracza (adoptuje, imituje innego gracza). Wybór strategii jest na ogół uzależniony od wypłaty uzyskiwanej przez poszczególne strategie. Możliwość imitowania zależy od modelu. Może być opisana przez pewne stałe prawdopodobieństwo, może zależeć od tego czy wypłata jest czy nie powyżej pewnego progu itd.

Po otrzymaniu możliwości imitacji gracz wybiera gracza którego strategię może imitować. Wybór gracza może być losowy, a może zależeć od wypłat uzyskiwanych przez innych graczy w poprzednich rundach. Kandydaci do ”bycia imitowanym” mogą być brani z calego zbioru graczy lub też–w przypadku gier ze strukturą przestrzenną–z odpowiednio zdefiniowanego otoczenia gracza imitującego. Można też np. wprowadzić mozliwość eksperymentowania przez dopuszczenie wyboru losowego: gracz imituje strategię przeciwnika z pewnym prawdopodobieństwem.

15.3.2. Procedury lepszej/najlepszej odpowiedzi

W modelach lepszej (better response) i najlepszej odpowiedzi (best response) zakładamy że każdy gracz zna wypłatę jaką otrzymałby z każdego możliwego wybory strategii przez wszystkich graczy oraz zna akcje wszystkich graczy w poprzedniej rundzie. Przy wyborze swojej kolejnej akcji każdy gracz zakłada że akcje przeciwników nie ulegną zmianie. Można to nazywać statycznym postrzeganiem otoczenia. Modele te opisuje się też przymiotnikiem (myopic) co odzwierciedla fakt że gracze nie biorą pod uwagę wpływu aktualnego wyboru strategii na przyszłe wybory i wypłaty uczestników gry.

W modelu lepszej odpowiedzi gracz identyfikuje wszystkie strategie które dadzą mu wyższą niż aktualna wypłate i wybiera losowo jedną z nich. W modelu najlepszej odpowiedzi gracz wybiera strategię tak aby zmaksymalizować swoja wypłatę przy oczekiwanych przez niego strategiach którymi będą grali pozostali gracze.

15.3.3. Procedura gry fikcyjnej

Jest to najstarszy i jeden z najbardziej popularnych modeli uczenia. W porównaniu z poprzednim modelem (naj)lepszych odpowiedzi mamy dalej do czynienia ze statycznym postrzeganiem otoczenia, natomiast gracze wykazują wyższy stopień ”wyrafinowania”. Po pierwsze każdy gracz zna całą dotychczasową historię gry, tzn. wszystkie akcje grane przez wszystkich graczy. Po drugie każdy gracz zakłada że każdy z pozostałych graczy będzie grał w następnej rundzie pewną strategią mieszaną, którą definiuje następujaco. Prawdopodobieństwo każdej dostepnej strategii czystej każdego z pozostałych graczy jest równe częstości dotychczasowego jej używania przez tego gracza. W kolejnej rundzie ”uczący się” gracz wybiera najlepszą odpowiedź na tak zdefiniowany profil strategii mieszanych gry.

W przypadku dwuosobowych gier strategicznych procedura gry fikcyjnej zakłada że gracz zapamiętuje wszystkie grane przez przeciwnika strategie czyste (historię gry) i na jej podstawie tworzy rozkład prawdopodobieństwa grania przez przeciwnika poszczególnych strategii czystych–strategię mieszaną–w nastepnej rundzie, w której gra najlepszą odpowiedź na tę strategię mieszaną.

Można pokazać że w przypadku gry z więcej niż jednym przeciwnikiem, przy założeniu że gracz będzie przewidywał rozkład łączny, finalnym efektem procedury jest na ogół równowaga skorelowana.

Dla wielu typów gier procedura gry fikcyjnej jest zbieżna to równowagi Nasha. Istnieją jednak proste kontrprzykłady, związane z brakiem ciągłości odwzorowania najlepszej odpowiedzi, z których pierwszy był skonstruowany w pracy [32]. Metody ”uzbieżniania” procedury polegają na wprowadzeniu różnych typów niedużych zaburzeń do gry, lub rozważanie populacji graczy zamiast jednego, patrz [25].

Równowaga Nasha została wprowadzona w 1950 r. Rok później zostały zaproponowane algorytmy znajdowania równowag Nasha. Algorytmy te zostały później zinterpretowane jako modele uczenia się w grach, w szczegolności jako procedury gry fikcyjnej patrz np. [2, 27].

15.3.4. Uczenie się przez testowanie

Gracz rozgrywa z przeciwnikiem $|S|$ gier jednokrotnych, używając kolejno wszystkich dostępnych mu strategii czystych, i używa do gry tę która mu dała największa wypłatę (w przypadku kilku takich strategii wybiera losowo jedna z nich). Ta procedura nosi nazwę procedury jednokrotnego testowania. Przy k–krotnym powtórzeniu takiego algotytmu n-krotnego otrzymujemy procedurę k–krotnego testowania, por. [17]

15.3.5. Procedury porównań

Powyższe modele uczenia się można uogólnić na jeden model który nazwiemy modelem porównywania ([26]).

Załóżmy że gracz gra pewną strategią $i$ . Dokonuje sie w pewien sposób (losowy lub nie) wyboru pewnego elementu $\omega\in\Omega$ (lub zbioru elementów) który nazwiemy próbką.

Wyjściowym formalnym obiektem modelu jest rodzina przestrzeni probabilistycznych $<\Omega,B,P>$ , gdzie zbiór próbek $\Omega$ jest metryzowalna przestrzenią topologiczną, $B$ jest $\sigma$ –algebrą zbiorów Borelowskich, a $P$ jest zbiorem wszystkich miar probabilistycznych na $B$ .

Próbka $\omega$ jest losowana zgodnie z pewnym rozkładem $\mu\in P$ . Prawdopodobieństwo zamiany strategii $i$ na $j$ jest dane wzorem

$p_{{ij}}=\int _{{\Omega}}r_{{ij}}(\omega)d\mu(\omega)$

(15.7)

gdzie $r_{{ij}}\in[0,1]$ jest tzw. funkcją reakcji, taką że wektor $(r_{{i1}}(\Omega),...,r_{{i|S|}}(\Omega))$ jest rozkładem prawdopodobieństwa na zbiorze strategii czystych $S$ dla każdej strategii $i\in S$ .

W przypadku uczenia się przez imitację przestrzeń próbek $\Omega$ jest zbiorem jednoelementowych zbiorów $\{ i\},i=1,...|S|$ . Funkcje reakcji są takie jak w poprzednim przykładzie, ograniczonym do dwóch strategii.

Dla procedury lepszej/najlepszej odpowiedzi $\Omega=S$ , tzn. przestrzeń próbek jest jednoelementowa, $\mu=1$ , a $r_{{ij}}=1/m$ jeżeli $j$ jest najlepszą odpowiedzią na $i$ , $r_{{ij}}=0$ wpp., gdzie $m$ jest liczbą najlepszych odpowiedzi.

15.3.6. Inne modele uczenia

Uczenie się racjonalne (rational learning). Jest to najbardziej ”wyrafinowany” z prezentowanych modeli. Zakładamy że gracze znają sytuację strategiczna oraz że mają subiektywny (zależny od gracza) zbiór przekonań (beliefs) o strategiach behawioralnych pozostalych graczy. Gracze reagują optymalnie na przekonania–strategie behawioralne–pozostałych graczy (w sensie najlepszej odpowiedzi: tak aby zmaksymalizować zdyskontowana sumę wszystkich swoich przyszłych wypłat).

Uczenie się behawioralne: Odpowiednie modele te są tworzone na podstawie wyników eksperymentalnych, które w szczególności pokazują że ludzie często nie zachowują sie ”racjonalnie”, powoduja się emocjami, popełniają błędy, mają ograniczony horyzont czasowy planowania strategicznego i pamięć o historii (zapominanie), ograniczoną wiarę w racjonalność, umiejętności pozostałych graczy itp.

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Wstęp do Teorii Gier