1

Aprendizado por ReforçoAprendizado por Reforço

Carlos H. C. RibeiroProfessor Adjunto

Divisão de Ciência da ComputaçãoInstituto Tecnológico de Aeronáutica

CTC15

CTC15 2

Como programar um “jogador automático” para enfrentar um

adversário que às vezes é imperfeito?

2

CTC15 3

Opção 1: MINIMAX (Teoria dos Jogos)

• Idéia: escrever um programa que maximize a expectativa de vitória do jogador, considerando que o adversário jogará de modo a minimizar esta expectativa (expansão da árvore de estados).

• Mas o nosso adversário não joga sempre de modo a minimizar a expectativa... MINIMAX não se aplica.

CTC15 4

Opção 2: Usar um modelo probabilístico do adversário

• Idéia: escrever um programa que maximize uma expectativa de vitória do jogador, considerando que o adversário jogará de acordo com um modelo.

• Muito bom. Mas primeiro preciso gerar o modelo do nosso adversário...

3

CTC15 5

Opção 3: Usar Aprendizado por Reforço

• Primeiro defino uma tabela de números, endereçada pelos possíveis estados do problema.

• Cada número da tabela é uma medida da probabilidade de se vencer o jogo, a partir do estado correspondente. Chamemos esta medida de valor do estado. Inicialmente, carrego a tabela com valores aleatórios, porque a princípio não sei quão bom ou quão ruim um estado é (não desenvolvi nenhum modelo).

CTC15 6

Opção 3: Usar Aprendizado por Reforço

• Jogo várias vezes contra o adversário. Propago o resultado final de cada jogo aos estados que levaram a isto, modificando seus respectivos valores.

• O resultado final é propagado porque sei o valor esperado associado aos estados finais. Por exemplo, qualquer estado com três X alinhados tem valor 1, e qualquer estado com três Oalinhados tem valor 0.

4

CTC15 7

Algumas Idéias FundamentaisAlgumas Idéias Fundamentais

• Aprendizado por experimentação• “O mundo é o melhor modelo de si mesmo”• AR é caracterizado por problemas que envolvem

o conceito de Autonomia• AR liga conceitos de IA e Controle Ótimo• AR é aplicável a problemas reais

CTC15 8

Bibliografia Básica: livrosBibliografia Básica: livros

• Reinforcement Learning: An IntroductionA. Barto / R. Sutton, MIT Press, 1998☺ Didático, princípios bem explicados, bons exercícios

Discussão insuficiente de alguns tópicos importantes

• Neurodynamic ProgrammingD. Bertsekas / J. Tsitsiklis, Athena, 1996☺ Razoavelmente completo e bem formalizado

Um pouco confuso e pesado para uma primeira leitura

5

CTC15 9

TDGammon (Tesauro, 1992)TDGammon (Tesauro, 1992)

• Jogo estocástico• Árvore de estados

de alta ramificação: da ordem de 1020

estados !!!

CTC15 10

TD-Gammon (Tesauro, 1992)TD-Gammon (Tesauro, 1992)

• Aprendizado por Reforço baseado em múltiplos jogos consigo mesmo (self-play)

• Tão bom quanto melhores jogadores humanos !!!

Isto é um pouco mais impressionante do que um jogador automático pro Jogo da Velha...

Naturalmente, TD-Gammon chamou muito a atenção para o uso de técnicas de AR em

problemas realistas...

6

CTC15 11

1. Caracterizando o problema1. Caracterizando o problema

• Autonomia: o que é, para que serve• O modelo básico

CTC15 12

2. Uma metodologia para se estudar AR

• Processos Decisórios de Markov• Programação Dinâmica• Força Bruta: O Método Monte Carlo• O Método das Diferenças Temporais

– O conceito de bootstrapping– Formulação não-causal– Formulação causal

7

CTC15 13

3. AR = Controle Ótimo + Autonomia

• Predição ok... E o Controle?• Controle Autônomo: Q-learning

CTC15 14

1. Caracterizando o problema

8

CTC15 15

Autonomia (Russel & Norvig, 1997)

Agente = “Algo” que observa e atua em um ambienteAutonomia = Capacidade de um agente escolher ações com

base na própria experiênciaExperiência = Interação com o ambiente

Um animal é autônomo (mas nenhum agente é tabula rasa...)Uma R.N.A. treinada com supervisão não é autônomaUm programa de inferência típico não é autônomo

CTC15 16

Por que estudar agentes autônomos?• Em Engenharia: modelos mais simples e precisos -

agente desenvolve modelo necessário e suficiente para a tarefa em questão.

• Em IA: enfoque alternativo com ênfase na atividade situada do agente como fator de aprendizado (IA nouvelle - Brooks, Maes, Mataric, etc..).

• Em ciência cognitiva: formalização de conceitos behavioristas

9

CTC15 17

2. Uma metodologia para se

estudar AR

CTC15 18

Agente ⇔ Processo Dinâmico

Processo Dinâmico

Agente

10

CTC15 19

A teoria: processos de decisão de Markov (MDP’s)• Estados s• Ações a• Reforços r(s,a)• Transições entre estados• Condição de Markov: Estado atual depende apenas de

últimos estado e ação ( e possivelmente de algum parâmetro aleatório independente)

Como estudar agentes autônomos?

O critério: uma função de valor (ou custo) VO objetivo: encontrar política de ações que maximize (minimize) o valor esperado do valor (custo)

CTC15 20t t+1

st-1

a t+1

a t-1a t-2

r(s t-1, a t-1) r(s t, a t) r(s t+1, a t+1)

st

st+1

a t

t-1

11

CTC15 21

Exemplo 1: Controle de Inventário

• Problema: comprar uma quantidade de um certo produto a intervalos regulares (em um total de N intervalos) de modo a satisfazer uma certa demanda

• Estado: sk = estoque no começo do período k• Ação: ak = compra feita no começo do período k• Uma perturbação aleatória wk = demanda no período k,

respeitando uma certa distribuição de probabilidade• Reforço rk = r(sk) + cak, onde r(sk) é o custo de estocar sk

unidades do produto no período k e c é o custo unitário do produto comprado.

CTC15 22

Exemplo 1: Controle de Inventário

• Evolução do estado: sk+1 = sk + ak - wk

• Função de custo a ser minimizada:

( ) ( ) ( )( )⎭⎬⎫

⎩⎨⎧

++= ∑−

=

1

0E

N

kkkNo casrsrsV

12

CTC15 23

Exemplo 2: Pêndulo Invertido

• Problema: controlar um pêndulo invertido exercendo forças +F ou -F sobre a base do carrinho (controle bang-bang). “Controlar” significa não permitir que a barra caia ou que o carrinho choque-se com as paredes.

+F -F

CTC15 24

Exemplo 2: Pêndulo Invertido• Estado: quádrupla• Ação: +F ou -F• Reforço: -1 em caso de falha, senão 0.• Evolução do estado: sk+1 = f(sk , ak) (?)• Possível função de custo a ser minimizada:

( )tttt xx θθ && ,,,

( )⎭⎬⎫

⎩⎨⎧

= ∑∞

=0E

tt

ko rsV γ

desconto temporal γ < 1: POR QUÊ?

13

CTC15 25

Modelo Básico Agente ⇔ Processo

Seletor de ações

processo

agente

reforço

ação

“estado”

CTC15 26

SE EU TENHO AS PROBABILIDADES DE TRANSIÇÃO (ou seja, um modelo do processo)

PROBLEMA CLÁSSICO DE CONTROLE ÓTIMO(solução baseada em programação dinâmica)

14

CTC15 27

Controle ÓtimoControle Ótimo

( ) ( ) ( ) ( ) ( ){ } ações de ótima política :,,

0,|Pmax

0,|PV

*1

*0

*

*1

*1

*

Laak ksrkass

k ksrkasss kkkakkko

=

⎥⎥⎦

⎤

⎢⎢⎣

⎡∑∞

==∑

∞

== −−

μ

γγ

Idéia fundamental:

– Defino a função de valor ( ) ( ) ( )∑∞

== −

0,|PV 1

k ksrkasss kkko γ

desconto temporal γ < 1: necessário paraproblemas sem terminação garantida ...

– Obtenho uma política de ações que maximize a função de valor

CTC15 28

Controle Ótimo: Operadores FundamentaisControle Ótimo: Operadores Fundamentais

• Operador de Aproximações Sucessivas

• Operador de Iteração de Valores

( )( ) ( )( ) ( )( ) ( )sVsssssrsVSs

′′+= ∑∈′

μγμμ ,|P,T

( )( ) ( ) ( ) ( )⎥⎦

⎤⎢⎣

⎡ ′′+= ∑∈′ Ssa

sVassasrsV ,|P,maxT γ

15

CTC15 29

Operadores Fundamentais: ExemploOperadores Fundamentais: ExemploEstados s1, s2 , desconto γ = 1 Ações a1, a2

Reforços r(s1, a1) = 2, r(s1, a2) = 1 Valores V (s2) = 1, V (s3) = 2

políticas μ1={μ1(s1)=a1 , μ1(s2)=...}e μ2={μ2(s1)=a2 , μ2(s2)=...}

s2s1

s3

0.6

0.4

a1: a2

: s2s1

s3

0.5

0.5

( )( ) ( )( ) ( )( ) ( )

( ) 4.324.016.012

,|P,T 1111111

=×+××+=

=′′+= ∑∈′

sVsssssrsVSs

μγμμ

CTC15 30

( )( ) ( )( ) ( )( ) ( )

( ) 5.225.015.011

,|P,T 1212112

=×+××+=

=′′+= ∑∈′

sVsssssrsVSs

μγμμ

( )( ) 4.3T 1 =sV

16

CTC15 31

Controle Ótimo: Propriedades dos OperadoresControle Ótimo: Propriedades dos Operadores

• Teorema 1

• Corolário 1

• Teorema 2 (Equação de Bellman)ou seja, é o (único) ponto fixo do operador

• Corolário 2ou seja, é o (único) ponto fixo do operador

• Teorema 3 Uma política μ é ótima se e somente se

( ) ( )( )sVsV N

NTlim*

∞→=

( ) ( )( )sVsV N

N ππ Tlim∞→

=** TVV =

*V*V T

πππ VV T=πV πT

** TT VV =π

CTC15 32

Controle Ótimo: Algoritmos de Programação DinâmicaControle Ótimo: Algoritmos de Programação Dinâmica

• Iteração de Valores

• Iteração da Política• passo 1: avaliar a política atual

• passo 2: obter uma política melhorada

( ) ( )( )[ ]sVs N

NTlimarg*

∞→=μ

kμ

1+kμ

kkkkkkVVVV M

μμμμμμ Tou T ≈=

( ) ( )( )[ ] Targ1 sVskk μμ =+

17

CTC15 33

Autonomia

Modelo do processo não disponível

Probs. de transição desconhecidas

CTC15 34

Aprendizado por Reforço = Controle Ótimo + Autonomia?

18

CTC15 35

Como aprender autonomamente?Como aprender autonomamente?

ciclo:• observo novo estado • defino experiência• atualizo estimação de custos (ou espero um pouco...)• escolho ação em função das novas estimativas

tttt rsas ,,, 1+

ts

Por enquanto, vamos nos concentrar na estimação do custo Vpara uma política fixa de ações (esqueça o controle) ...

Solução: tentar minimizar iterativamente (Robbins-Monro) uma estimativa da função de custo

CTC15 36

Algoritmo Robbins-MonroAlgoritmo Robbins-Monro

( )( )tttttt rvrgrr −+=+~,1 α

( )[ ]

∞<∞= ∑∑∞

=

∞

= 0t

2t

0tt e

:se ~,Epara 1) prob. (com converge

αα

vrgr tt

( )oaprendizad de coef. :

| com acordo de amostrado :~

tαrvpvt

19

CTC15 37

3 Propostas• Monte Carlo: uso experiências completas

para estimar custos• TD (0): uso experiência imediata para

estimar custos

CTC15 38

Proposta 1: Monte CarloProposta 1: Monte CarloIdéia: força brutaForma geral da iteração:

( )tNtN

ttttNt VrrrrVV ~~~2

21 −+++++= ++++ γγγα L

Problema: atualização requer trajetória completa

Um dado estado pode aparecer mais de um vez ao longo de uma trajetória

Método “primeira visita”: só atualizo o custo para a parte da trajetória relativa à primeira visita.

Método “toda visita”: atualizo o custo para toda parte de trajetória relativa à qualquer visita.

20

CTC15 39

Proposta 2: TD(0)Proposta 2: TD(0)Idéia: Basear aprendizado em minimização do erro de

predição:

tVt instante no predição :~

( ) ( ) ( ) ( ) ( )( )ttttttttt sVsVsrsVsV ~~~~11 −++= ++ γα

Um dado estado pode aparecer mais de um vez ao longo de uma trajetóriaMétodo “primeira visita”: só atualizo o custo para a parte da trajetória

relativa à primeira visita.Método “toda visita”: atualizo o custo para toda parte de trajetória relativa

à qualquer visita.

CTC15 40

TD(0) X Monte CarloTD(0) X Monte Carlo

Random Walk :

Desconto γ = 1, P(dir)=P(esq)=0.5, α=0.8

0 0 0 0 0 1A B C D E

( ) ( ) ( ) ( ) ( )65E,

64D,

63C,

62B,

61A ===== VVVVV

21

CTC15 41

0 0 0 0 0 1A B C D E

( ) 8.)010(8.0D~ :fimED 1 =−++=⇒⇒ V

( ) 96.)8.1000(8.8.D~ :fimEDCD 1 =−++++=⇒⇒⇒⇒ V

( ) ( ) 192.96.00008.96.D~fimABCD

1 =−++++=

⇒⇒⇒⇒

V

Monte Carlo, “primeira visita”

CTC15 42

0 0 0 0 0 1A B C D E

( ) ( )

( ) ( )( ) ( )

( ) ( )( ) ( ) 0)000(8.0A~ ,0)000(8.0B~

,0)000(8.0C~ ,128.)64.00(8.64.D~:fimABCD

96.)8.01(8.8.E~ ,64.)08.0(8.0D~,0)000(8.0C~ ,0)000(8.0D~

:fimEDCD8.)001(8.0E~ ,0)000(8.0D~

:fimED

11

11

11

11

11

=−++==−++=

=−++==−++=

⇒⇒⇒⇒=−++==−++=

=−++==−++=

⇒⇒⇒⇒=−++==−++=

⇒⇒

VV

VV

VV

VV

VV

TD(0), “toda visita”

22

CTC15 43

TD(0) X Monte CarloTD(0) X Monte Carlo

CTC15 44

Variantes

• Online: atualizações feitas assim que Rt(n) é

computado.

• Offline: atualizações “guardadas” e feitas apenas ao final do episódio. Valores V não são modificados durante a execução de uma trajetória.

23

CTC15 45

Aproximando PD para ControleAproximando PD para Controle

TD(λ) + Operador de Iteração de Valores “sem modelo”

Método de Iteração de Política “Autônomo”

Tem um operador “min” atrapalhando...

Tentemos então obter diretamente o controle usando um método baseado no operador de aproximações sucessivas...

CTC15 46

Valores QValores Q( ) ( ) ( ) ( )

( ) ( ) ( )( ) ( ) ( ) ( ) ( )( )

( )( ) ( ) ( ) ( )usassasras

asasassasras

assVsV

sVassasras

us

ttttasttttttt

ttatt

ts

ttttttt

t

t

,Qmin,|P,,QT

onde

,QT,Qmax,|P,,Q

,QminT

,|P,,Q

'

Q

Q1

**

1*

1

1

1

′′+=

=+=∴

==

+=

∑

∑

∑

Δ

+

++

Δ

+

+

γ

γ

γ

24

CTC15 47

Valores QValores Q

( )( ) ( ) ( ) ( )

( )( ) ( ) ( ) ( )⎥⎦

⎤⎢⎣

⎡ ′′+=

′′+=

∑

∑

Δ

Δ

sVussusrsV

usassasras

su

us

'

'

Q

,|P,maxT

e

,Qmax,|P,,QT

γ

γ

☺ “min” agora aparece dentro do somátorio... Posso definir um algoritmo do tipo Robbins-Monropara aproximar TQ !!!

Qual é a diferença fundamental entre

CTC15 48

Q-Learning Watkins, 1989Q-Learning Watkins, 1989

• No tempo t, o agente:– observa estado st e seleciona ação at;

• No tempo t+1, o agente:– observa estado st+1 ;– atualiza o valor de ação Qt(st ,at) de acordo com

Δ Qt(st ,at)=αt [rt + γ maxa Qt (st +1 ,a) - Qt(st ,at)]☺ Aproxima o operador TQ (iterações Robbins-Monro)

☺ Convergência garantida (para representação tabular)

☺ Ações de treino podem ser escolhidas livremente

25

CTC15 49

st

st+1

a t=ak

M M

L

L

st

st+1

a1

M M

L

L st+1

ak

M M

L

L

st

st+1

aN

L Lst

( ) ( ) ( ) ( )⎟⎟⎠

⎞

⎜⎜

⎝

⎛−++= ++

kttttat

ktt

ktt asQasQrasQasQ ,,max,, 11 γα