1

MSI-w5/1

Metody sztucznej inteligencji

Politechnika Śląska

Katedra Podstaw Konstrukcji Maszyn

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/2

Uczenie (się) ze wzmocnieniem

(RL=Reinforcement learning)

MSI-w5/3

Uczenie indukcyjne 

(na przykładach)

• Uczenie indukcyjne:

– Środowisko dostarcza przykładów - pary 

(wejście-wyjście)

– Zadanie polega na nauczeniu się funkcji, która 

mogłaby być uogólnieniem tych przykładów

• Można uczyć się na przykładach, gdy:

– Nauczyciel dostarcza poprawnych wartości
– Lub predykcje uzyskiwane poprzez 

zastosowanie funkcji mogą być zweryfikowane 

w następnym kroku działania agenta

MSI-w5/4

Przykład: gra w szachy (1)

• Uczenie indukcyjne jest niekorzystne:

– Przykłady dostarczane przez nauczyciela:

(sytuacja na szachownicy; najlepszy ruch dla tej sytuacji)

– Ile  może być takich przykładów?

• Gdy brak nauczyciela, agent może 

losowo 

wybierać 

posunięcia i budować model predykcyjny: jak 
będzie wyglądać szachownica po wykonaniu jego 
ruchu i w jaki sposób partner 

prawdopodobnie

odpowie na ten ruch

Gdy agent nie wie, który ruch jest dobry, a który zły, 
trudno mu zdecydować, który ruch wybrać

MSI-w5/5

Przykład: gra w szachy (2)

• W grze w szachy istnieje sprzężenie 

zwrotne:

– Gdy jest nauczyciel, może ocenić ruch
– Gdy go nie ma, na końcu partii wiadomo, czy 

agent wygrał, czy nie

• Takie  sprzężenie nazywa się 

nagrodą

lub 

wzmocnieniem

• W szachach nazywane jest 

stanem 

terminalnym

w sekwencji historii stanów

MSI-w5/6

Uczenie ze wzmocnieniem (RL)

• Istota: 

wykorzystanie nagród w celu wyuczenia przez 

agenta skutecznego działania

• Trudność: 

agent nie wie

:

– jaka akcja jest właściwa
– jaka nagroda jest przypisana do której akcji

• Nagroda  jest 

specjalnym rodzajem percepcji

• W  wielu  złożonych dziedzinach jest jedynym 

wykonalnym sposobem wyuczenia agenta działań 

o wysokim poziomie

2

MSI-w5/7

RL: Sformułowanie problemu

• Agent działający w swoim środowisku 

odbiera percepcje

(wrażenia)

• Niektóre percepcje

są odwzorowywane na 

ujemne

lub 

dodatnie użyteczności

• Następnie agent 

decyduje

, 

które działanie 

podjąć

MSI-w5/8

Podstawy RL: jak mogą zmieniać 

się zadania uczenia (1)

• Środowisko:

– dostępne

- agent identyfikuje stany poprzez 

percepcje

– niedostępne

- agent utrzymuje pewien stan 

wewnętrzny próbując monitorować środowisko

• Agent 

posiada wiedzę o środowisku 

i wynikach jego działań

LUB 

agent 

musi wyuczyć się tego modelu wraz 

z informacją o użyteczności

MSI-w5/9

Podstawy RL: jak mogą zmieniać 

się zadania uczenia (2)

• Nagrody  mogą być otrzymywane:

– tylko w stanie terminalnym

(końcowym)

– w  każdym stanie

• Nagrody  mogą być

– składnikami bieżącej wartości użyteczności

, 

którą agent stara się maksymalizować

– wskazówkami co do bieżącej użyteczności

MSI-w5/10

Podstawy RL: jak mogą zmieniać 

się zadania uczenia (3)

• Agent może działać jako uczeń :

– Pasywny

, biernie obserwujący świat „dziejący 

się obok” i próbujący nauczyć się użyteczności 
„bycia w różnych stanach”

– Aktywny

, który musi ponadto działać stosując 

wyuczoną informację, oraz może stosować 
swój własny generator problemów który  
sugeruje specjalne działania poznawcze 
(eksploracja nieznanych części otoczenia)

MSI-w5/11

Podstawowe warianty RL-agenta

• Agent uczy się funkcji użyteczności na 

podstawie stanów (lub historii stanów), a 
następnie używa jej do wyboru akcji które 
maksymalizują oczekiwaną użyteczność ich 
wyników

• Agent uczy się funkcji akcja-wartość, która 

daje oczekiwaną użyteczność podjęcia 
danej akcji w danym stanie (Q-learning)

MSI-w5/12

Uczenie pasywne w znanym 

środowisku

• Pasywny RL-agent w znanym, dostępnym 

środowisku (reprezentacja za pomocą 

stanów)

• Środowisko generuje przejścia stanów, 

a agent stara się nauczyć użyteczności tych 

stanów

• Założenie: agentowi dostarczono model M

i,j

podający prawdopodobieństwo przejścia ze 

stanu i do stanu j

3

MSI-w5/13

Proste środowisko stochastyczne

Założenie upraszczające:

użyteczność sekwencji jest sumą nagród 

zgromadzonych dla wszystkich stanów tej sekwencji (tj. funkcja 
użyteczności jest addytywna).

nagroda do otrzymania

= suma nagród do otrzymania począwszy

od danego stanu a skończywszy na stanie terminalnym

MSI-w5/14

Przykład sekwencji trenujących

(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

(1,1)

→(2,1)→(1,1)→(1,2)→(1,3)→(2,3)→(3,3)→(3,2)→(4,2) -1

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ę

Celem jest 

wykorzystanie informacji o nagrodach do 

nauczenia się oczekiwanej użyteczności

U(i) stanu 

nieterminalnego i

MSI-w5/15

Program pasywnego RL-agenta

function PASSIVE-RL-AGENT(e) returns działanie
static: U, tablica estymat funkcji użyteczności

N, tablica częstości dla stanów
M, tablica prawdopodobieństw przejścia ze stanu do stanu
percepts, sekwencja (początkowo pusta)

Dodaj e do percepts
Zwiększ N[STAN[e]]
U

←

UPDATE

(U, e, percepts, M, N)

if TERMINALNY?[e] then percepts

← pusta sekwencja

return działanie Obserwuj

Różne wersje algorytmu 

zależą od funkcji UPDATE

MSI-w5/16

Aktualizacja tabeli wartości 

funkcji użyteczności

• Agent aktualizuje bieżące wartości funkcji 

użyteczności po każdym przejściu stanów

• Stosowane algorytmy UPDATE:

– Naiwna aktualizacja (NU)
– Adaptacyjne programowanie dynamiczne (ADP)
– Uczenie na podstawie chwilowych różnic (TD)

• Od wyboru algorytmu aktualizacji funkcji 

użyteczności zależą właściwości agenta RL

MSI-w5/17

Naiwna aktualizacja (1)

• Pochodzi z adaptacyjnej teorii sterowania 

(Widrow & Hoff, 1960), zwane LMS=least mean

squares

• Założenie: dla każdego stanu w sekwencji 

trenującej zaobserwowane dla tej sekwencji 

reward-to-go dostarcza bezpośredniej informacji o 

oczekiwanym reward-to-go

• Na  końcu każdej sekwencji algorytm oblicza 

zaobserwowane reward-to-go dla każdego stanu i 

aktualizuje wartość estymowaną dla tego stanu

MSI-w5/18

Naiwna aktualizacja (2)

• Estymaty użyteczności uzyskane z 

zastosowaniem algorytmu LMS 
minimalizują błąd średniokwadratowy ze 
względu na zaobserwowane dane

• Dla funkcji użyteczności reprezentowanej 

za pomocą tablicy aktualizacja tej tablicy 
dokonywana jest za pomocą obliczania 
wartości średniej bieżącej (ruchomej)

4

MSI-w5/19

Naiwna aktualizacja (3)

function LMS-UPDATE(U, e, percepts, M, N) returns aktualne U

if TERMINALNY?[e] then

reward-to-go

← 0

for each e

i

in percepts (zaczynając od końca) do

reward-to-go

← reward-to-go + REWARD[e

i

]

U[STATE[e

i

]] 

← RUNNING-AVERAGE(

U[STAN[e

i

]] , reward-to-go, N[STAN[e

i

]] )

end

--------------------------------------------------------
reward-to-go = nagrody do zebrania
RUNNING-AVERAGE = średnia bieżąca

MSI-w5/20

Naiwna aktualizacja (4)

• Zastosowanie algorytmu LMS jest równoważne 

nauczeniu się funkcji użyteczności bezpośrednio 

z przykładów

:

(stan; nagroda do odebrania)

• Takie podejście sprowadza RL do 

standardowego problemu uczenia indukcyjnego

• Funkcja użyteczności może być także 

reprezentowana np. przez sztuczną sieć 

neuronową

MSI-w5/21

Naiwna aktualizacja (5)

• 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

MSI-w5/22

Naiwna aktualizacja (6)

Ponad 1000 sekwencji potrzeba, by agent uzyskał 
użyteczności bliskie wartościom poprawnym!!

MSI-w5/23

Adaptacyjne programowanie 

dynamiczne (1)

• Użyteczności U(i) oblicza się rozwiązując układ 

równań:

gdzie:
R(i)- nagroda przypisana do stanu i
M

ij

- prawdopodobieństwo wystąpienia

przejscia ze stanu i do stanu j

• Wartości dokładne użyteczności zawiera Rys. 20.1(c)

( ) ( )

( )

∑

+

=

j

ij

j

U

M

i

R

i

U

MSI-w5/24

Adaptacyjne programowanie 

dynamiczne (2)

• Ponieważ agent jest pasywny, nie dokonuje 

żadnej maksymalizacji wartości ze względu 

na akcje

• ADP dobrze wykorzystuje doświadczenie
• ADP stanowi odniesienie dla innych 

algorytmów RL

• Dla  dużych przestrzeni stanów ADP jest 

trudny do rozwiązania

5

MSI-w5/25

Uczenie na podstawie 

chwilowych różnic (1)

• Istota: 

wykorzystać zaobserwowane przejścia 

pomiędzy stanami, aby poprawić wartości 

użyteczności dla zaobserwowanych stanów by 

były one zgodne z równaniami więzów

:

gdzie α - parametr  prędkości uczenia

• Częstość aktualizacji zależy od 

prawdopodobieństwa przejścia pomiędzy 

stanami

( )

( )

( ) ( ) ( )

(

)

i

U

j

U

i

R

i

U

i

U

−

+

+

←

α

MSI-w5/26

Uczenie na podstawie 

chwilowych różnic (2)

function TD-UPDATE(U, e, percepts, M, N) returns tablica U

if TERMINALNY?[e] then

U[STAN[e]]

←RUNNING-AVERAGE(U[STAN[e],

NAGRODA[e], N[STAN[e]])

else if percepts zawiera więcej niż jeden element then

e’

← przedostatni element ciągu percepts

i, j

← STAN[e’], STAN[e]

U[i] 

← U[i] + α(N[i])(NAGRODA[e’] + U[j] - U[i])

MSI-w5/27

Uczenie na podstawie 

chwilowych różnic (3)

Choć TD generuje bardziej zaszumione wartości użyteczności,
błąd średniokw. jest istotnie mniejszy niż dla LMS

MSI-w5/28

Pasywne uczenie w nieznanym 

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 
stany sąsiadujące z tym stanem

MSI-w5/29

Pasywne uczenie w nieznanym 

otoczeniu (2)

ADP jest zbieżne dużo szybciej niż LMS i TD

MSI-w5/30

Aktywne uczenie się

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

6

MSI-w5/31

Aktywne uczenie się

w nieznanym otoczeniu (2)

• Model środowiska musi uwzględniać 

prawdopodobieństwa M

ij

a

przejścia ze stanu i

do innego stanu j, gdy jest dana akcja a

• Racjonalny RL-agent maksymalizuje swoją 

użyteczność:

• Agent musi wybierać akcję w każdym kroku, 

do czego potrzebuje miary osiągów

( ) ( )

( )

∑

+

=

j

U

M

i

R

i

U

a

ij

a

max

MSI-w5/32

Eksploracja (1)

• Problem - jaką akcję powinien w danej 

sytuacji podjąć agent (wynik działania 
PERFORMANCE-ELEMENT)

• Akcja ma dwa rodzaje skutków:

– Zwiększa nagrody dla bieżącej sekwencji stanów
– Ma  wpływ na odebrane percepcje, a przez to na 

zdolność agenta do uczenia się

i 

otrzymywania 

nagród dla przyszłych sekwencji

MSI-w5/33

Eksploracja (2)

• Dwa skrajne podejścia do zadania wyboru 

kolejnej akcji:

– Losowy wybór z nadzieją, że agent w końcu 

zbada całe środowisko (wacky=stuknięty)

– Zachłanne (greedy) podejście maksymalizujące 

użyteczność z wykorzystaniem bieżących estymat

MSI-w5/34

Eksploracja (2)

• Losowy wybór

– umożliwia nauczenie dobrych estymat użyteczności dla 

wszystkich stanów

– nigdy nie poprawia osiągów w zakresie dodatnich nagród

• Zachłanne podejście

– Zwykle znajduje ścieżkę do nagrody +1
– Ale potem trzyma się tej ścieżki i nigdy nie nauczy się 

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/35

Eksploracja (3)

MSI-w5/36

Eksploracja (4)

• Optymistyczna estymata użyteczności U

+ 

(nagród do zebrania):

N(a, i) - ile razy próbowano akcję a w stanie i

• Przykładowa funkcja f(u, n):

( )

( )

( ) ( )













+

←

∑

+

+

j

a

ij

a

i

a

N

j

U

M

f

i

R

i

U

,

,

max

( )







<

=

+

razie

 

przeciwnym

 

w

gdy

,

u

N

n

R

n

u

f

e

Optymistyczna ocena 

najwyższej możliwej nagrody 

w jakimkolwiek stanie

Minimalna liczba prób 

dla pary (akcja, stan)

7

MSI-w5/37

Eksploracja (5)

MSI-w5/38

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 :

( )

( )

i

a

Q

i

U

a

,

max

=

MSI-w5/39

Uczenie funkcji akcja-wartość (2)

• Podejście bez modelu umożliwia TD:

obliczane po każdym przejściu ze stanu i do j

• Podejście 

bez wykorzystania modelu

, bardzo 

skuteczne

( )

( )

( )

(

) ( )













−

′

+

+

←

′

i

a

Q

j

a

Q

i

R

i

a

Q

i

a

Q

a

,

,

max

,

,

α

MSI-w5/40

Uczenie funkcji akcja-wartość (3)

MSI-w5/41

Uczenie funkcji akcja-wartość (4)

• WAŻNE PYTANIE -

czy i kiedy warto 

budować model

?

• Odpowiedź intuicyjna: gdy środowisko 

staje się coraz bardziej skomplikowane, np.

– szachy
– warcaby

warto budować model tego środowiska

MSI-w5/42

Uogólnienia w RL (1)

• Dotychczas wszystkie rozpatrywane funkcje 

(U, M, R, Q) reprezentowano tabelarycznie

• Co zrobić, gdy liczba stanów jest ogromna 

(szachy - 10

50

)?!!

• Funkcyjna reprezentacja użyteczności, np.

Zamiast 10

50

wartości trzeba określić n wag

( )

( )

( )

( )

i

f

w

i

f

w

i

f

w

i

U

n

n

+

+

+

=

K

2

2

1

1

8

MSI-w5/43

Uogólnienia w RL (2)

• Zalety: 

– niesłychana kompresja wiedzy o problemie

– Możliwość uogólniania: na podstawie 

stanów, które agent zbadał, wnioskuje o 
stanach, których nie zbadał

• Modele można zbudować jako:

– Drzewa decyzyjne
– Sieci neuronowe
– ...

MSI-w5/44

Uogólnienia w RL (3)

• Zastosowania do gier:

– Program grający w szachy (Samuel, 1959)

• liniowa funkcja użyteczności
• 16 wag (!!!)
• program gra jak dobry szachista

– Sieć neuronowa do gry w trik-traka 

(backgammon - 10

120

stanów ) (1992) 

• 40 węzłów w warstwie ukrytej
• po 200 000 gier (2 tygodnie trenowania) program 

osiągnął poziom standardowego gracza

MSI-w5/45

Algorytmy genetyczne

i programowanie ewolucyjne

MSI-w5/46

Ewolucja w świecie organizmów 

żywych

• Doprowadza do wykształtowania się 

udanych 

organizmów

, bo:

– Organizmy niedopasowane do otoczenia wymierają
– 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/47

Algorytm genetyczny

function GENETIC-ALGORITHM(populacja, FITNESS-FN)

returns osobnik

inputs:populacja, zbiór osobników

FITNESS-FN, funkcja określająca dopasowanie osobnika

repeat

rodzice

← SELECTION(populacja, FITNESS-FN)

populacja

← REPRODUCTION(rodzice)

until jakiś osobnik nie jest wystarczająco dopasowany
return najlepszy osobnik w populacja, ze względu na FITNESS-FN

MSI-w5/48

Algorytm genetyczny (GA) w AI

• Działa dobrze w sztucznych systemach

• Osobnikiem może być:

– Kompletna funkcja realizowana przez agenta, 

wtedy FITNESS-FN jest miarą osiągów agenta lub 
funkcją nagrody

– Funkcja składowa agenta, wtedy FITNESS-FN jest 

składową krytyki

– . . .

9

MSI-w5/49

GA jako RL

• Ponieważ proces ewolucyjny uczy funkcji agenta 

bazując na sporadycznych nagrodach 
(potomstwo!!) udzielonych przez funkcję selekcji, 
ma on cechy RL

• GA 

nie wykorzystuje relacji

występujących pomiędzy 

nagrodami i akcjami podejmowanymi przez agenta 
lub stanami środowiska

• Działanie GA polega na 

prostym przeszukiwaniu 

przestrzeni osobników

w celu znalezienia osobnika 

maksymalizującego FITNESS-FN

MSI-w5/50

Przeszukiwanie w GA

• Jest równoległe (każdy osobnik jest 

niezależny)

• Ma charakter hill-climbing (robi się małe 

zmiany genetyczne w osobnikach i używa 

najlepszych potomków)

• Problem:

– Czy zajmować się głównie najlepszymi, ignorując 

słabych? 

Grozi utknięcie w lokalnym maksimum!!

– Don’t kill infeasible individuals!

MSI-w5/51

Problemy implementacji GA

• Jak określić FITNESS-FN?
• Jak reprezentować osobniki?
• Jak selekcjonować osobniki (do reprodukcji)?
• W jaki sposób osobniki reprodukują się?

MSI-w5/52

Reprezentowanie osobników

• Klasyczny GA:

– chromosomy zbudowane z genów
– chromosom jest łańcuchem elementów 

zbudowanych ze skończonego alfabetu

– W skrajnym przypadku chromosom jest 

łańcuchem bitów

• Możliwe jest stosowanie chromosomów, 

których geny są 

liczbami rzeczywistymi

MSI-w5/53

Strategia selekcji

• Zwykle strategia losowa (ruletka) z 

prawdopodobieństwem wylosowania 
odpowiadającym wartości FITNESS-FN

• Selekcja z powtórzeniami - dobry osobnik 

ma szanse wielokrotnie być wylosowany

• Są inne strategie (rangowa, turniejowa, ...)

MSI-w5/54

Reprodukcja

• Losowe kojarzenie w pary
• Krzyżowanie tej pary w losowo wybranym 

miejscu chromosomu (2 osobniki potomne)

• Mutacja dowolnego z genów (małe 

prawdopodobieństwo mutacji)

10

MSI-w5/55

Przykład GA

MSI-w5/56

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/57

Podsumowanie (2)

• Użyteczność może być wyuczona poprzez:

– LMS:  całkowita zaobserwowana suma nagród do 

otrzymania stosowana jako bezpośrednie dane dla 
wyuczenia tej użyteczności; model stosowany tylko do 
wyboru akcji

– ADP: iteracyjnie oblicza dokładne użyteczności 

stanów, gdy dany jest estymowany model; optymalnie 
wykorzystuje informację o więzach

– TD: aktualizuje oceny użyteczności, by pasowały do 

użyteczności dla następnych stanów; model dostarcza 
surogatu doświadczenia

MSI-w5/58

Podsumowanie (3)

• Wyuczenie funkcji akcja-wartość 

nie 

wymaga modelu ani do uczenia, ani do 
selekcji odpowiedniej akcji

• Gdy agent jest aktywny, musi wybierać 

właściwe akcje, biorąc pod uwagę 

estymowane wartości tych akcji

oraz 

potencjalną możliwość wyuczenia 

nowej 

użytecznej wiedzy

MSI-w5/59

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