Metody sztucznej inteligencji
Uczenie (się) ze wzmocnieniem
Politechnika Śląska
Katedra Podstaw Konstrukcji Maszyn
(RL=Reinforcement learning)
Rok akademicki 2003/2004
Wykład 6
Materiały dydaktyczne (na prawach rękopisu)
dla studentów Wydziału Mechanicznego Technologicznego
Wszystkie ilustracje pochodzą z S. Russel, P. Norvig, Artificial
Intelligence - A modern approach, Prentice Hall, 1995
MSI-w5/1 MSI-w5/2
Uczenie indukcyjne
Przykład: gra w szachy (1)
(na przykładach)
" Uczenie indukcyjne jest niekorzystne:
" Uczenie indukcyjne:
 Przykłady dostarczane przez nauczyciela:
 Środowisko dostarcza przykładów - pary (sytuacja na szachownicy; najlepszy ruch dla tej sytuacji)
(wejście-wyjście)
 Ile może być takich przykładów?
 Zadanie polega na nauczeniu się funkcji, która
" Gdy brak nauczyciela, agent może losowo wybierać
mogłaby być uogólnieniem tych przykładów
posunięcia i budować model predykcyjny: jak
" Można uczyć się na przykładach, gdy:
będzie wyglądać szachownica po wykonaniu jego
 Nauczyciel dostarcza poprawnych wartości ruchu i w jaki sposób partner prawdopodobnie
odpowie na ten ruch
 Lub predykcje uzyskiwane poprzez
zastosowanie funkcji mogą być zweryfikowane
Gdy agent nie wie, który ruch jest dobry, a który zły,
w następnym kroku działania agenta
MSI-w5/3 MSI-w5/4
trudno mu zdecydować, który ruch wybrać
Przykład: gra w szachy (2) Uczenie ze wzmocnieniem (RL)
" Istota:
" W grze w szachy istnieje sprzężenie
wykorzystanie nagród w celu wyuczenia przez
zwrotne:
agenta skutecznego działania
 Gdy jest nauczyciel, może ocenić ruch
" Trudność: agent nie wie:
 Gdy go nie ma, na końcu partii wiadomo, czy
 jaka akcja jest właściwa
agent wygrał, czy nie
 jaka nagroda jest przypisana do której akcji
" Takie sprzężenie nazywa się nagrodą lub
" Nagroda jest specjalnym rodzajem percepcji
wzmocnieniem
" W wielu złożonych dziedzinach jest jedynym
" W szachach nazywane jest stanem
wykonalnym sposobem wyuczenia agenta działań
terminalnym w sekwencji historii stanów o wysokim poziomie
MSI-w5/5 MSI-w5/6
Podstawy RL: jak mogą zmieniać
RL: Sformułowanie problemu
się zadania uczenia (1)
" Środowisko:
" Agent działający w swoim środowisku
 dostępne - agent identyfikuje stany poprzez
odbiera percepcje (wrażenia)
percepcje
" Niektóre percepcje są odwzorowywane na
 niedostępne - agent utrzymuje pewien stan
ujemne lub dodatnie użyteczności
wewnętrzny próbując monitorować środowisko
" Następnie agent decyduje, które działanie
" Agent posiada wiedzę o środowisku
podjąć i wynikach jego działań
LUB
agent musi wyuczyć się tego modelu wraz
z informacją o użyteczności
MSI-w5/7 MSI-w5/8
Podstawy RL: jak mogą zmieniać Podstawy RL: jak mogą zmieniać
się zadania uczenia (2) się zadania uczenia (3)
" Nagrody mogą być otrzymywane: " Agent może działać jako uczeń :
 tylko w stanie terminalnym (końcowym)  Pasywny, biernie obserwujący świat  dziejący
się obok i próbujący nauczyć się użyteczności
 w każdym stanie
 bycia w różnych stanach
" Nagrody mogą być
 Aktywny, który musi ponadto działać stosując
 składnikami bieżącej wartości użyteczności,
wyuczoną informację, oraz może stosować
którą agent stara się maksymalizować
swój własny generator problemów który
 wskazówkami co do bieżącej użyteczności
sugeruje specjalne działania poznawcze
(eksploracja nieznanych części otoczenia)
MSI-w5/9 MSI-w5/10
Uczenie pasywne w znanym
Podstawowe warianty RL-agenta
środowisku
" Pasywny RL-agent w znanym, dostępnym
" Agent uczy się funkcji użyteczności na
środowisku (reprezentacja za pomocą
podstawie stanów (lub historii stanów), a
stanów)
następnie używa jej do wyboru akcji które
" Środowisko generuje przejścia stanów,
maksymalizują oczekiwaną użyteczność ich
a agent stara się nauczyć użyteczności tych
wyników
stanów
" Agent uczy się funkcji akcja-wartość, która
" Założenie: agentowi dostarczono model Mi,j
daje oczekiwaną użyteczność podjęcia
podający prawdopodobieństwo przejścia ze
danej akcji w danym stanie (Q-learning)
stanu i do stanu j
MSI-w5/11 MSI-w5/12
Proste środowisko stochastyczne
Przykład sekwencji trenujących
W każdym ciągu trenującym agent zaczyna w stanie (1,1)
i odbiera sekwencję przejść stanów dopóki nie osiągnie
jednego ze stanów terminalnych (4,2) lub (4,3), w
których otrzymuje nagrodę
(1,1)(1,2)(1,3)(1,2)(1,3)(1,2)(1,1)(2,1)(3,1)(4,1)(4,2) -1
(1,1)(1,2)(1,3)(2,3)(3,3)(4,3) +1
(1,1)(1,2)(1,1)(1,2)(1,1)(2,1)(3,1)(3,2)(4,2) -1
(1,1)(1,2)(1,1)(1,2)(1,3)(2,3)(1,3)(2,3)(3,3)(4,3) +1
(1,1)(2,1)(3,1)(2,1)(1,1)(1,2)(1,3)(2,3)(3,3)(4,3) +1
Założenie upraszczające: użyteczność sekwencji jest sumą nagród
(1,1)(2,1)(1,1)(1,2)(1,3)(2,3)(3,3)(3,2)(4,2) -1
zgromadzonych dla wszystkich stanów tej sekwencji (tj. funkcja
Celem jest wykorzystanie informacji o nagrodach do
użyteczności jest addytywna).
nagroda do otrzymania = suma nagród do otrzymania począwszy nauczenia się oczekiwanej użyteczności U(i) stanu
MSI-w5/13 MSI-w5/14
od danego stanu a skończywszy na stanie terminalnym
nieterminalnego i
Aktualizacja tabeli wartości
Program pasywnego RL-agenta
funkcji użyteczności
function PASSIVE-RL-AGENT(e) returns działanie
static: U, tablica estymat funkcji użyteczności
" Agent aktualizuje bieżące wartości funkcji
N, tablica częstości dla stanów
użyteczności po każdym przejściu stanów
M, tablica prawdopodobieństw przejścia ze stanu do stanu
percepts, sekwencja (początkowo pusta) " Stosowane algorytmy UPDATE:
 Naiwna aktualizacja (NU)
Dodaj e do percepts
 Adaptacyjne programowanie dynamiczne (ADP)
Zwiększ N[STAN[e]]
 Uczenie na podstawie chwilowych różnic (TD)
U�!UPDATE(U, e, percepts, M, N)
if TERMINALNY?[e] then percepts �! pusta sekwencja
" Od wyboru algorytmu aktualizacji funkcji
return działanie Obserwuj
użyteczności zależą właściwości agenta RL
Różne wersje algorytmu
zależą od funkcji UPDATE
MSI-w5/15 MSI-w5/16
Naiwna aktualizacja (1) Naiwna aktualizacja (2)
" Pochodzi z adaptacyjnej teorii sterowania
" Estymaty użyteczności uzyskane z
(Widrow & Hoff, 1960), zwane LMS=least mean
zastosowaniem algorytmu LMS
squares
minimalizują błąd średniokwadratowy ze
" Założenie: dla każdego stanu w sekwencji
względu na zaobserwowane dane
trenującej zaobserwowane dla tej sekwencji
reward-to-go dostarcza bezpośredniej informacji o
" Dla funkcji użyteczności reprezentowanej
oczekiwanym reward-to-go
za pomocą tablicy aktualizacja tej tablicy
" Na końcu każdej sekwencji algorytm oblicza
dokonywana jest za pomocą obliczania
zaobserwowane reward-to-go dla każdego stanu i
wartości średniej bieżącej (ruchomej)
aktualizuje wartość estymowaną dla tego stanu
MSI-w5/17 MSI-w5/18
Naiwna aktualizacja (3) Naiwna aktualizacja (4)
function LMS-UPDATE(U, e, percepts, M, N) returns aktualne U
" Zastosowanie algorytmu LMS jest równoważne
nauczeniu się funkcji użyteczności bezpośrednio
if TERMINALNY?[e] then
reward-to-go �! 0 z przykładów:
for each ei in percepts (zaczynając od końca) do
(stan; nagroda do odebrania)
reward-to-go �! reward-to-go + REWARD[ei]
" Takie podejście sprowadza RL do
U[STATE[ei]] �! RUNNING-AVERAGE(
standardowego problemu uczenia indukcyjnego
U[STAN[ei]] , reward-to-go, N[STAN[ei]] )
end
" Funkcja użyteczności może być także
--------------------------------------------------------
reprezentowana np. przez sztuczną sieć
reward-to-go = nagrody do zebrania
neuronową
RUNNING-AVERAGE = średnia bieżąca
MSI-w5/19 MSI-w5/20
Naiwna aktualizacja (5) Naiwna aktualizacja (6)
" Wada: LMS nie wykorzystuje informacji zawartej w
tym, że użyteczności stanów są od siebie zależne!
" Struktura przejść pomiędzy stanami narzuca bardzo
silne dodatkowe więzy:
Użyteczność danego stanu jest średnią ważoną
(wagi=prawdopodobieństwa) użyteczności
następników tego stanu plus nagrody przypisanej do
tego stanu
" Zignorowanie tej informacji powoduje bardzo wolną
zbieżność użyteczności do ich wartości dokładnych
Ponad 1000 sekwencji potrzeba, by agent uzyskał
MSI-w5/21 MSI-w5/22
użyteczności bliskie wartościom poprawnym!!
Adaptacyjne programowanie Adaptacyjne programowanie
dynamiczne (1) dynamiczne (2)
" Użyteczności U(i) oblicza się rozwiązując układ " Ponieważ agent jest pasywny, nie dokonuje
równań: żadnej maksymalizacji wartości ze względu
na akcje
U(i)= R(i)+ U( j)
"Mij
" ADP dobrze wykorzystuje doświadczenie
j
gdzie:
" ADP stanowi odniesienie dla innych
R(i)- nagroda przypisana do stanu i
algorytmów RL
Mij - prawdopodobieństwo wystąpienia
" Dla dużych przestrzeni stanów ADP jest
przejscia ze stanu i do stanu j
trudny do rozwiązania
" Wartości dokładne użyteczności zawiera Rys. 20.1(c)
MSI-w5/23 MSI-w5/24
Uczenie na podstawie Uczenie na podstawie
chwilowych różnic (1) chwilowych różnic (2)
" Istota: wykorzystać zaobserwowane przejścia
function TD-UPDATE(U, e, percepts, M, N) returns tablica U
pomiędzy stanami, aby poprawić wartości
if TERMINALNY?[e] then
użyteczności dla zaobserwowanych stanów by
U[STAN[e]]�!RUNNING-AVERAGE(U[STAN[e],
były one zgodne z równaniami więzów:
NAGRODA[e], N[STAN[e]])
else if percepts zawiera więcej niż jeden element then
U(i)�! U(i)+ą(R(i)+U( j)-U(i))
e �! przedostatni element ciągu percepts
gdzie ą - parametr prędkości uczenia i, j �! STAN[e ], STAN[e]
U[i] �! U[i] + ą(N[i])(NAGRODA[e ] + U[j] - U[i])
" Częstość aktualizacji zależy od
prawdopodobieństwa przejścia pomiędzy
stanami
MSI-w5/25 MSI-w5/26
Uczenie na podstawie Pasywne uczenie w nieznanym
chwilowych różnic (3) otoczeniu (1)
" ADP można skutecznie stosować także w
tym przypadku (otoczenie wolno ewoluuje)
" Agent uczy się modelu środowiska poprzez
bezpośrednie obserwacje przejść stanów
reprezentowanych przez tablicę M
" Wartości tablicy M buduje się na podstawie
znajomości liczby przejść danego stanu w
Choć TD generuje bardziej zaszumione wartości użyteczności, stany sąsiadujące z tym stanem
błąd średniokw. jest istotnie mniejszy niż dla LMS
MSI-w5/27 MSI-w5/28
Pasywne uczenie w nieznanym Aktywne uczenie się
otoczeniu (2) w nieznanym otoczeniu (1)
" Pasywny RL-agent ma ustaloną strategię
działania i nie musi troszczyć się o to, jaką
akcję wybrać
" Aktywny RL-agent musi rozważać:
 Jaką akcję wybrać
 Jakie mogą być wyniki tej akcji
 Jak wyniki tej akcji mogą wpłynąć na
otrzymane nagrody
ADP jest zbieżne dużo szybciej niż LMS i TD MSI-w5/29 MSI-w5/30
Aktywne uczenie się
Eksploracja (1)
w nieznanym otoczeniu (2)
" Model środowiska musi uwzględniać " Problem - jaką akcję powinien w danej
prawdopodobieństwa Mija przejścia ze stanu i sytuacji podjąć agent (wynik działania
do innego stanu j, gdy jest dana akcja a PERFORMANCE-ELEMENT)
" Racjonalny RL-agent maksymalizuje swoją " Akcja ma dwa rodzaje skutków:
użyteczność:
 Zwiększa nagrody dla bieżącej sekwencji stanów
a  Ma wpływ na odebrane percepcje, a przez to na
U(i)= R(i)+ max U( j)
"Mij
zdolność agenta do uczenia się i otrzymywania
a
nagród dla przyszłych sekwencji
" Agent musi wybierać akcję w każdym kroku,
MSI-w5/31 MSI-w5/32
do czego potrzebuje miary osiągów
Eksploracja (2) Eksploracja (2)
" Losowy wybór
" Dwa skrajne podejścia do zadania wyboru
 umożliwia nauczenie dobrych estymat użyteczności dla
kolejnej akcji:
wszystkich stanów
 Losowy wybór z nadzieją, że agent w końcu
 nigdy nie poprawia osiągów w zakresie dodatnich nagród
zbada całe środowisko (wacky=stuknięty)
" Zachłanne podejście
 Zwykle znajduje ścieżkę do nagrody +1
 Zachłanne (greedy) podejście maksymalizujące
 Ale potem trzyma się tej ścieżki i nigdy nie nauczy się
użyteczność z wykorzystaniem bieżących estymat
użyteczności dla innych stanów (nie osiągnie perfekcji,
ponieważ nie znajdzie lepszej ścieżki - zadowala się
znalezioną ścieżką, która daje jakieś gwarantowane
nagrody)
MSI-w5/33 MSI-w5/34
Eksploracja (3)
Eksploracja (4)
" Optymistyczna estymata użyteczności U+
(nagród do zebrania):
�ł
+ a +
�ł �ł
U (i)�! R(i)+ max f U ( j), N(a,i)�ł
"Mij
�ł �ł
a
j
�ł łł
N(a, i) - ile razy próbowano akcję a w stanie i
Optymistyczna ocena
najwyższej możliwej nagrody
" Przykładowa funkcja f(u, n):
w jakimkolwiek stanie
ńł
R+ gdy n < Ne
f (u, n)=
�ł Minimalna liczba prób
dla pary (akcja, stan)
ółu w przeciwnym razie MSI-w5/36
MSI-w5/35
Eksploracja (5) Uczenie funkcji akcja-wartość (1)
" Istotne znaczenie w RL:
 Wystarczają do podejmowania decyzji bez
wykorzystania modelu
 Mogą być wyuczone bezpośrednio poprzez
sprzężenie zwrotne z nagrodą
" Gdy Q(a,i)=wartość wykonania akcji a w
stanie i :
U(i)= max Q(a,i)
a
MSI-w5/37 MSI-w5/38
Uczenie funkcji akcja-wartość (2) Uczenie funkcji akcja-wartość (3)
" Podejście bez modelu umożliwia TD:
�ł
2
Q(a,i)�! Q(a,i)+ą�ł R(i)+ max Q(a , j)- Q(a,i)�ł
�ł
2
a
�ł łł
obliczane po każdym przejściu ze stanu i do j
" Podejście bez wykorzystania modelu, bardzo
skuteczne
MSI-w5/39 MSI-w5/40
Uczenie funkcji akcja-wartość (4) Uogólnienia w RL (1)
" WAŻNE PYTANIE - czy i kiedy warto " Dotychczas wszystkie rozpatrywane funkcje
budować model? (U, M, R, Q) reprezentowano tabelarycznie
" Odpowiedz
intuicyjna: gdy środowisko " Co zrobić, gdy liczba stanów jest ogromna
staje się coraz bardziej skomplikowane, np. (szachy - 1050)?!!
 szachy
" Funkcyjna reprezentacja użyteczności, np.
 warcaby
U(i)= w1 f1(i)+ w2 f2(i)+K+ wn fn(i)
warto budować model tego środowiska
Zamiast 1050 wartości trzeba określić n wag
MSI-w5/41 MSI-w5/42
Uogólnienia w RL (2) Uogólnienia w RL (3)
" Zalety: " Zastosowania do gier:
 niesłychana kompresja wiedzy o problemie  Program grający w szachy (Samuel, 1959)
" liniowa funkcja użyteczności
 Możliwość uogólniania: na podstawie
" 16 wag (!!!)
stanów, które agent zbadał, wnioskuje o
" program gra jak dobry szachista
stanach, których nie zbadał
 Sieć neuronowa do gry w trik-traka
" Modele można zbudować jako:
(backgammon - 10120 stanów ) (1992)
 Drzewa decyzyjne
" 40 węzłów w warstwie ukrytej
 Sieci neuronowe
" po 200 000 gier (2 tygodnie trenowania) program
 ... osiągnął poziom standardowego gracza
MSI-w5/43 MSI-w5/44
Ewolucja w świecie organizmów
żywych
" Doprowadza do wykształtowania się udanych
Algorytmy genetyczne organizmów, bo:
 Organizmy niedopasowane do otoczenia wymierają
i programowanie ewolucyjne
 Organizmy dopasowane mogą się reprodukować
" Potomstwo jest podobne do rodziców
" Gdy środowisko powoli ewoluuje, organizmy
dopasowują się do zmian, także ewoluując
" Czasem występują losowe mutacje:
 W większości przypadków mutanty szybko wymierają
 Niektóre mutacje prowadzą do nowych udanych gatunków
MSI-w5/45 MSI-w5/46
Algorytm genetyczny Algorytm genetyczny (GA) w AI
function GENETIC-ALGORITHM(populacja, FITNESS-FN)
returns osobnik " Działa dobrze w sztucznych systemach
inputs:populacja, zbiór osobników
" Osobnikiem może być:
FITNESS-FN, funkcja określająca dopasowanie osobnika
 Kompletna funkcja realizowana przez agenta,
repeat
wtedy FITNESS-FN jest miarą osiągów agenta lub
rodzice �! SELECTION(populacja, FITNESS-FN)
funkcją nagrody
populacja �! REPRODUCTION(rodzice)
 Funkcja składowa agenta, wtedy FITNESS-FN jest
until jakiś osobnik nie jest wystarczająco dopasowany
return najlepszy osobnik w populacja, ze względu na FITNESS-FN składową krytyki
 . . .
MSI-w5/47 MSI-w5/48
GA jako RL Przeszukiwanie w GA
" Ponieważ proces ewolucyjny uczy funkcji agenta " Jest równoległe (każdy osobnik jest
bazując na sporadycznych nagrodach niezależny)
(potomstwo!!) udzielonych przez funkcję selekcji,
" Ma charakter hill-climbing (robi się małe
ma on cechy RL
zmiany genetyczne w osobnikach i używa
" GA nie wykorzystuje relacji występujących pomiędzy
najlepszych potomków)
nagrodami i akcjami podejmowanymi przez agenta
" Problem:
lub stanami środowiska
 Czy zajmować się głównie najlepszymi, ignorując
" Działanie GA polega na prostym przeszukiwaniu
słabych? Grozi utknięcie w lokalnym maksimum!!
przestrzeni osobników w celu znalezienia osobnika
 Don t kill infeasible individuals!
maksymalizującego FITNESS-FN
MSI-w5/49 MSI-w5/50
Problemy implementacji GA Reprezentowanie osobników
" Jak określić FITNESS-FN? " Klasyczny GA:
 chromosomy zbudowane z genów
" Jak reprezentować osobniki?
 chromosom jest łańcuchem elementów
" Jak selekcjonować osobniki (do reprodukcji)?
zbudowanych ze skończonego alfabetu
" W jaki sposób osobniki reprodukują się?
 W skrajnym przypadku chromosom jest
łańcuchem bitów
" Możliwe jest stosowanie chromosomów,
których geny są liczbami rzeczywistymi
MSI-w5/51 MSI-w5/52
Strategia selekcji Reprodukcja
" Zwykle strategia losowa (ruletka) z " Losowe kojarzenie w pary
prawdopodobieństwem wylosowania
" Krzyżowanie tej pary w losowo wybranym
odpowiadającym wartości FITNESS-FN
miejscu chromosomu (2 osobniki potomne)
" Selekcja z powtórzeniami - dobry osobnik
" Mutacja dowolnego z genów (małe
ma szanse wielokrotnie być wylosowany
prawdopodobieństwo mutacji)
" Są inne strategie (rangowa, turniejowa, ...)
MSI-w5/53 MSI-w5/54
Przykład GA
Podsumowanie (1)
" Omówiono dwa podejścia
 bazujące na modelu
 bez wsparcia modelowego
" Użyteczność stanu jest oczekiwaną sumą
nagród otrzymanych od danego stanu do
końca danej sekwencji stanów
MSI-w5/55 MSI-w5/56
Podsumowanie (2) Podsumowanie (3)
" Użyteczność może być wyuczona poprzez:
" Wyuczenie funkcji akcja-wartość nie
 LMS: całkowita zaobserwowana suma nagród do
wymaga modelu ani do uczenia, ani do
otrzymania stosowana jako bezpośrednie dane dla
selekcji odpowiedniej akcji
wyuczenia tej użyteczności; model stosowany tylko do
wyboru akcji
" Gdy agent jest aktywny, musi wybierać
 ADP: iteracyjnie oblicza dokładne użyteczności
właściwe akcje, biorąc pod uwagę
stanów, gdy dany jest estymowany model; optymalnie
estymowane wartości tych akcji oraz
wykorzystuje informację o więzach
potencjalną możliwość wyuczenia nowej
 TD: aktualizuje oceny użyteczności, by pasowały do
użyteczności dla następnych stanów; model dostarcza
użytecznej wiedzy
surogatu doświadczenia
MSI-w5/57 MSI-w5/58
Podsumowanie (4)
" W  dużych przestrzeniach stanów algorytmy
RL muszą bazować na reprezentacji
funkcyjnej, co umożliwia uogólnianie wejść
ponad stanami. Algorytm TD umożliwia
bezpośrednią korektę wag
" GA ma cechy RL, gdyż używa wzmocnienia
do zwiększenia udziału udanych osobników w
populacji. GA jest zdolny do uogólniania
dzięki mutacjom i krzyżowaniu osobników
MSI-w5/59