Aprendizagem por reforço
Jacques Robin
CIn-UFPE
O que é aprendizagem por reforço?
 Uma classe de problemas de aprendizagem (pela qual
existe uma grande diversidade de técnicas)
 Aprendizagem:
por um agente com objetivo(s) situado em um ambiente
da utilidade dos estados do ambiente com respeito a esse(s)
objetivo(s)
ou de uma política de ação maximizando o grau de satisfação
desse(s) objetivo(s)
indiretamente via recepção de reforço (ou dica) positivo ou
negativo
quando se encontra em alguns estados
ou como resultado da execução de uma ação ou uma serie de ações
Exemplo de tarefa
de aprendizagem por reforço
 Agente explorador da caverna do wumpus
 Explora N instâncias aleatoriamente geradas da caverna
 Recebe reforços:
+1 quando sai vivo da caverna sem o ouro
+5 quando sai vivo da caverna com o ouro
-5 quando morre caindo em um buraco ou devorado pelo wumpus
 Aprende:
função f: Percepções  Ações, para um agente puramente reativo
ou, função g: EstadosDaCaverna  Utilidades, para um agente
reativo com estado interno, modelo perceptivo e modelo efetivo do
ambiente
Aprendizagem por reforço x
Aprendizagem supervisionada
Aprendizagem por reforço
Aprendizagem supervisionada
 retorno na forma de dica, as vezes
para um conjunto de escolhas
 retorno na forma da escolha correta,
separadamente por cada escolha: ex,
na situação 26, ação 67 era a melhor
ex, na situação 26, a ação 27
é nota 0.8
 requer treinamento antes da
ex, a partir da situação 26, a serie
utilização
de ação 27, 3, 12, 79, e 99 é nota 0.3
 aprende mapeamentos componentes:
 permite treinamento
classificação
tanto prévio a utilização
quanto durante a utilização
 aprende mapeamento global
percepção(t)  ação(t)
 para satisfazer simultaneamente
vários objetivos
(percepção(t),modelo(t-1))
 modelo(t)
previsão
(modelo(t),ação(t))
 modelo(t+1))
otimização
(modelo(t+1),objetivo(t))
 max(utilidade(t+1))
 para satisfazer um único objetivo
Conceitos chaves da
aprendizagem por reforço
 Política de ação
 Função de reforço
 Função de valor
(ou utilidade)
 Modelo do ambiente
Policy
Reward
Value
Model of
environment
Política de ação
 Mapeia estado percebido do ambiente pelo agente para a
ação a executar nesse estado que maximiza satisfação
dos seus objetivos
 : percepção(estado(ambiente))
 ação(estado(ambiente))
 estado percebido pode ser última percepção recebida ou
modelo construído a partir das percepções anteriores
  pode ser determinista ou estocástica
Função de reforço
 Mapeia estados do ambiente ou transição do ambiente de
um estado para um outro para um número indicando a
satisfação imediata dos objetivos do agente nesse estado
ou no estado resultando da transição
 r: estado(ambiente)  real, ou
 r: (estado1(ambiente), estado2(ambiente))  real
 r codifica os objetivos do agente de maneira imediata
local
 r pode ser determinista ou estocástica
Função de valor
 Mapeia estado do ambiente para um número indicando o a
satisfação futura atingível dos objetivos do agente a
partir desse estado
 v: estado(ambiente)  real
 v codifica os objetivos do agente de maneira global e a
prazo
 v(e) definida como função aditiva dos reforços nos
estados alcançáveis a partir de e:
v(ek) = i[k,+[ pi.r(ei)
v(ek) = i[k,j] r(ei)
v(ek) = limji[k,j] r(ei)
Modelo do ambiente
 Modelo perceptivo, mapeia percepções para representação interna
do estado do ambiente
mp: (percepção(t), modelo(estado(ambiente(t-1))))
 modelo(estado(ambiente(t)))
 Modelo efetivo, mapeia ação a efetuar para representação interna
do estado do ambiente resultando dessa ação
me: (ação(t), modelo(estado(ambiente(t))))
 modelo(estado(ambiente(t+1)))
 Cada um desses modelos pode ser:
 representado em extensão por uma tabela, ou
 representado em intenção por algum formalismo de representação do
conhecimento como operadores de próximo estado, regras, lógica,
operadores de planejamento
 manualmente codificado, ou
 aprendido com aprendizagem supervisionado
Exemplo introdutório: jogo da velha
X
X
O X
O X
X
X
O X
O
O X
O
x
X O X
X O X
O X
O
O X
X
O
...
x
...
...
x o
X
} x joga
x
...
o
o x
x
} o joga
x
...
...
...
...
...
} x joga
} o joga
x o
x
x o
} x joga
Exemplo introdutório: jogo da velha
1. Inicializar tabela de valores com tabela de reforços
Estado
x
V(s) – Probabilidade estimada de ganhar
.5
?
.5
?
x x x
o
o
1
vitória
x o
o
o
0
derrota
o x o
o x x
x o o
0
empate
x
2. Fazer agente jogar muitos jogos contra adversário imperfeito
 Escolhendo:
 a grande maioria das vezes ação que leva a estado de maior valor
 as vezes aleatoriamente ação que leva a estado com valor menor
 Atualiza tabela depois de cada ação
 levando do estado s para o estado s´
 com a formula: V(s) := V(s) + p(V(s´) – V(s))
 na qual p é o tamanho de passo de aprendizagem
Exemplo introdutório: jogo da velha
 Exemplo de técnica de aprendizagem por reforço dita de
diferencia temporal
 Se p decresce a cada iteração, convergência para a
tabela de valor representando política de ação ótima
contra um adversário usando uma política de ação fixa
 Se p não decresce até 0, bom desempenho mesmo contra
adversário que muda lentamente sua política de ação
 Ilustra como aprendizagem por reforço permite um
agente:
tomar em conta conseqüências de longo prazo da suas ações sem
busca explícita no espaço dos estados ou das seqüências de ações
adaptar-se a um adversário ou a um ambiente dinâmico sem um
modelo explícito do mesmo
Exemplos de aplicações práticas
da aprendizagem por reforço
 Jogos com agente treinado jogando contra ele mesmo, ou
várias encarnações ligeiramente diferentes dele
 Navegação e manipulação robótica
 Filtragem de e-mail sem aquisição manual nem de regras
de filtragem, nem de corpus de exemplos positivos e
negativos
Tipologia dos problemas
de aprendizagem por reforço







Passivo
Reforço em qualquer estado
Com modelo prévio do ambiente
Aprendizagem da função valor
Ambiente accessível
Ambiente determinista
Ambiente episódico
Ativo
Reforço em poucos estados
Sem modelo prévio do ambiente
Aprendizagem da função
ação-valor
 Ambiente inacessível
 Ambiente não determinista
 Ambiente não episódico




 No caso mais complexo,
a aprendizagem por reforço é
praticamente equivalente a IA
como um todo
Aprendizagem por reforço passivo x ativo
Passivo
Ativo
 Ambiente passa de um estado para
o outro sem intervenção do agente
 A cada transição, agente apenas:
 Agente tenta descobrir uma boa
política de ação
 A cada transição, agente:
percebe o estado e recebe reforço
atualiza sua representação do valor
desse estado
 Equivalente a situação na qual:
Agente faz mudar o ambiente pela
execução de uma política de ação
predefinida
Agente não tenta descobrir uma boa
política de ação
mas apenas avaliar política
predefinida
percebe o estado e recebe reforço
atualiza sua representação do valor
desse estado
escolhe uma ação a executar que
muda o estado do ambiente
Dilema aproveitamento-exploração
 Na aprendizagem por reforço ativa o agente enfrenta dilema
aproveitamento-exploração:
Quando gulosamente aproveitar da estimação atual da função valor e
escolher ação que a maximiza?
Quando curiosamente explorar outra ação que pode levar a melhorar
estimação atual da função valor?
Particularmente relevante quando aprendizagem ocorre durante
utilização, sem fase de treinamento prévio
Taxa de exploração = proporção de escolhas curiosas
Geralmente se começa com uma taxa de exploração alta que vai
decrescendo com tempo
Mesmo princípio do que o simulated annealing
Aprendizagem por reforço com reforço
em todos x em poucos estados
Reforço em todos os estados
Reforço em poucos estados
 Agente recebe reforço em todos
os estados
 Pode facilmente atribuir esse
reforço esse estado o a última
ação que executou
 Simplifica a atualização da
estimativa do valor desse estado
ou ação
 Agente recebe reforço apenas em
poucos estados
 Enfrenta o problema da
distribuição desse reforço entre
as várias ações que executou
desde o último reforço
 Dificulta atualização da estimativa
do valor dos estados ou das ações
Dilema da atribuição do mérito
 Na maioria dos casos, reforço é recebido apenas em alguns estados
 Em jogos, agente pode receber reforço apenas no estado final
(ganhou? perdeu? empatou?)
 As vezes, agente executa uma política de ação ótima com apenas um
único erro grave e recebe reforço negativo
 Como identificar qual foi a ação que causou esse reforço?
 A mesma ação no mesmo estado pode ser ótima no contexto de uma
serie de ações, mas péssima no contexto de uma outra serie
 Dilema geralmente resolvido iterativamente pela execução de muitas
series de ações diferentes
Valor de uma ação em um estado estimada como média do seu valor em
todas as series tentadas
Seu valor em uma serie tentada estimada como o reforço recebido pela
serie divido pelo tamanho da serie
 Computacionalmente caro
 Ressalta necessidade de exploração
Aprendizagem por reforço
com x sem modelo prévio do ambiente
Com modelo prévio do ambiente
Sem modelo prévio do ambiente
 Agente possui modelo do ambiente
para prever transições de estado
do ambiente causada pelas suas
ações
 Em ambiente não determinista tal
modelo pode ser apenas
estocástico
 Agente ignora a priori:
tanto o valor de cada estado do
ambiente com respeito a seus
objetivos
quanto as transições de estado do
ambiente que suas ações podem
causar
 Dois tipos de técnicas:
As que permitem ao agente
aprender o valor de ação para a
realização dos seus objetivos sem
conhecer o estado do ambiente
As que permitem aprender ambas a
função valor e a função de transição
de estado
Aprendizagem por reforço de
uma função valor x de uma função ação-valor
Função valor
Função ação-valor
 associa valor diretamente a
estados dos ambiente
 valor de uma ação indiretamente
definida como valor do estado
resultado da execução da ação
 aplicável apenas para agente com
modelo efetivo do ambiente (para
prever o estado resultado da
execução de cada ação)
 associa valor diretamente a pares
(estado(ambiente),ação)
 aplicável a agente:
sem modelo efetivo do ambiente
sem nenhum modelo de um ambiente
acessível
 com modelo apenas perceptivo de
um ambiente inacessível
 chamado de Aprendizagem Q
Aprendizagem por reforço de
uma função valor x de uma função ação-valor
0
0
0
100
0
0
0
0
0
0
90
81
Função Valor
100
0
0
0
Reforços
90
100
72
81
72
0
0
0
0
Reforços
81
100
90
81
100
81
0
81
90 90
72
100
81
Função Ação-Valor
Aprendizagem por reforço em ambiente
episódico x não episódico
Ambiente episódico
 O reforço recebido pelo agente
depende apenas do estado atual do
ambiente
 O estado sucessor depende apenas
do estado atual e da ação a
executar
 Ambos são independentes dos
estados precedentes pelo qual o
ambiente passou
 Escolher uma ação em tal ambiente
chama-se de processo de decisão
de Markov
 Pode se reusar o vasto leque de
técnicas de otimização iterativas
probabilistas disponíveis para tais
processos
Ambiente não episódico
 Agentes chegando no mesmo
estados do ambiente por caminhos
diferentes podem:
receber reforços diferentes
fazer passar o ambiente para
estados diferentes executando a
mesma ação nesse mesmo estado
 Técnicas baseadas em modelos de
Markov não se aplicam
Aprendizagem por reforço em ambiente
determinista x não determinista
Ambiente determinista
Ambiente não determinista
 Agente recebe sempre mesma
percepção e mesmo reforço ao
chegar em um determinado estado
do ambiente
 Agente executando a mesma ação
no mesmo estado do ambiente
sempre leva-o no mesmo estado
sucessor
 Função valor ou ação-valor podem
ser determinista
 Agente pode receber percepções e
reforços diferentes quando chegar
várias vezes no mesmo estado do
ambiente
 Execução da mesma ação no mesmo
estado pode levar o agentes para
estados sucessores diferentes
 Sensores e atuadores ruidosos são
umas das causas de tal não
determinismo
 Função valor ou ação-valor há de
ser estocástica
Técnicas
de Aprendizagem Por Reforço (APR)
 APR passiva com modelo efetivo do ambiente:
LMS: teoria do controle adaptativo
ADP: programação dinâmica adaptativa (pesquisa operacional)
TD: diferencia temporal
 APR passiva sem modelo efetivo do ambiente:
LMS e TD
 APR ativa com modelo efetivo do ambiente:
ADP ativa e TD ativa
Modelo previamente conhecido ou iterativamente aprendido junto
a função valor
 APR ativa sem modelo efetivo do ambiente:
Aprendizagem Q
APR passiva com modelo
do ambiente não determinista
3
+1
3 -0.0380
2
-1
2 -0.1646
1 Start
1
1 -0.2911
2
3
4
1
0.0886
0.2152
+1
-0.4430
-1
-0.4177
-0.5443
-0.7722
2
3
4
 Agente guarda para cada estado:
 probabilidades de transição para os outros estados
número de vezes que foi alcançado
estimativa atual de v
 Várias técnicas em função da formula de atualização de v
Teoria do controle adaptativa
 LMS: v(sk) = ij r(sij) / n
onde sij são os estados depois de sk nos n percursos já explorados
passando por sk
reduz aprendizagem por reforço a aprendizagem supervisionada
com reforços a vir já observados sendo o retorno
valor estimado de um estado função apenas de reforços ignorando
valor estimado de outros estados
por isso converge muito lentamente
como não usa modelo do
ambiente é utilizável para
APR sem modelo
Programação dinâmica adaptativa
e diferença temporal
 ADP: v(si) = r(si) + jp(trans(si,sj)).v(sj)
onde p(trans(si,sj)) é a probabilidade do ambiente passar do
estado si para o estado sj
valor estimado de um estado função do reforço no estado, dos
valores estimados em estados vizinhos e do modelo do ambiente
por isso converge mais rapidamente que LMS
porém computacionalmente caro por tomar em consideração, para
cada percurso, todos os vizinhos de todos os estados do percurso
intratável para ambientes com muitos estados, ex, jogo do
backgammon envolveria resolver sistema de 1050 equações com
1050 variáveis
 TD: v(si,ek) = v(si,ek-1) + (r(sj) + v(sj,ek-1) - v(si,ek-1))
valor estimado do estado função do reforço no estado e do valor
estimado de apenas um vizinho, o precedente no percurso atual
 rapidez de convergência melhor que LMS mas menor que ADP
 porém mais computacionalmente escalável do que ADP
APR passiva sem modelo efetivo
do ambiente não determinista
 LMS e TD de fato não usam modelo efetivo do ambiente
e então se aplicam a esse caso sem modificação
 ADP precisa ser modificado da seguinte maneira:
modelo adquirido simultaneamente com função valor via percursos
no ambiente
cada transição observada é registrada pelo agente
esse registros são generalizados por uma técnica de
aprendizagem supervisionada incremental como:
redes neurais
redes bayesianas
programação em lógica incremental
ADP ativa
 Mudanças chaves de passivo para ativo:
Adição de política de compromisso aproveitamento-exploração
Parametrização do modelo efetivo pelas ações a executar
 Atualização: v(si) = r(sj) + maxa e(jp(trans(si,a,sj)).v(sj) , n(a,sj)),
onde
p(trans(si,a,sj)) é a probabilidade do estado sj ser o resultado da
execução da ação a no estado si
n(a,sj) é o número de vezes a ação a foi escolhida no estado sj
e(v,n) é a função de exploração
e(v,n) = r+ se n  L
e(v,n) = v se n  L
r+ é uma estimativa otimista do maior reforço disponível no ambiente
L é um limiar fixo
 Modelo p(trans(si,a,sj)) aprendido semelhantemente a p(trans(si,sj)),
exceto pelo registro da ação executada que causou a transição
observada
TD ativa
 Coeficiente  no fórmula de atualização toma em
consideração compromisso aproveitamento-exploração:
 = 1 / 1 + n(a,s)
onde n(s,a) é o número de vezes a ação a foi escolhida no estado s
 Função de exploração e acrescentada para escolher a
ação a executar
 Modelo efetivo do ambiente:
 passa a ser necessário para escolher ação a executar a cada
passo
 pode ser aprendido iterativamente usando mesmas técnicas do
que no ADP ativo
Aprendizagem Q
 Aprende valor de uma determinada ação em um determinado estado
no lugar do valor desse estado em si
 Permite dispensar modelo efetivo do ambiente inteiramente, mesmo
no caso ativo
 não precisa ser fornecido como conhecimento prévio
 nem aprendido junto a função ação-valor
 Relação entre função valor e função ação-valor:
 v(e) = maxa q(a,e)
 Fórmula de atualização:
 q(am,si,ek) = q(am,si,ek-1) +
(r(si) + maxan q(an,sj,ek-1) - q(am,si,ek-1)) / (1 + n(am,si))
onde: n(am,si) é o número de vezes a ação am foi escolhida no estado si
 adaptação ao caso de aprendizagem de uma função ação-valor da fórmula
de atualização de TD
 ADP não pode ser usado para aprender valores q pós
re-introduziria necessidade de um modelo efetivo do ambiente
 Converge menos rapidamente que ADP
Representação intencional do ambiente
 Métodos apresentados até agora não são escaláveis para
domínios com muitos estados e com muitas ações
 Solução:
mudar de uma representação em extensão dos estados do
ambiente, dos efeitos das ações e do valor dos estados ou ações
para uma representação em intenção
integrar aprendizagem por reforço com representação do
conhecimento e/ou aprendizagem supervisionado incremental
 Cada elemento de um problema de APR pode ser
abstraído por um vetor de atributos, ex,
v(ei) = w1f1(ei) + ... + wnfn(ei)
Essa soma ponderada pode ser substituída ao v(ei) nas equações
de atualização
os pesos aprendidos usando aprendizagem supervisionado
incremental
os fj(ek) aprendidos resolvendo as novas equações abstratas
Aprendizagem por reforço x
resolução de problema por meio de busca
 Métodos de busca iterativas como gradiente crescente e
simulated annealing podem ser usadas para resolver
problemas de APR
 Buscam o espaço das políticas de ação diretamente, sem
recorrer ao conceito intermediário de função valor ou
função ação-valor
 Viável apenas com ambiente muito pequenos
 Não permitem aprendizagem durante utilização, mas
apenas durante treinamento prévio
Aprendizagem por reforço x
raciocínio baseado em conhecimento
 Raciocínio baseado em conhecimento
 pode ser usado por um agente aprendendo por reforço
 junto a uma representação em intenção do problema
 para:
 interpretar percepções para identificar reforço e estado do
ambiente
 prever efeitos das ações
 calcular utilidade
Aprendizagem por reforço x planejamento
 APR pode ser combinado com planejamento hierárquico
 A decomposição de um operador O na penúltima camada
mais baixa do planejador é:
 nem enlatada
 nem construída usando planejamento
 mas construída por uma agente de APR
 Quando o agente APR:
 executa uma serie de ações
 a partir de uns dos estados satisfazendo a precondição P(O)
 se o resultado é de fazer passar o ambiente por uns dos estados
satisfazendo o efeito E(O) ele recebe um reforço +
 senão, ele recebe um reforço -
Aprendizagem por reforço x
aprendizagem conexionista e evolucionista
 Redes neurais e algoritmos genéticos podem ser usados
para resolver problemas de APR
 Aprendem políticas de ação diretamente, sem recorrer
ao conceito intermediário de função valor ou função
ação-valor
 Os pesos de uma rede neural podem ser ajustados em
função da recepção de reforços positivos ou negativos
 A função de fitness de um algoritmo genético pode ser
definida em termos dos reforços positivos ou negativos
Tópicos avançados em
aprendizagem por reforço
 Aprendizagem por reforço hierárquico:
 Idéia semelhante ao planejamento hierárquico
 Tarefa do agente decomposta em camadas
 O comportamento aprendido por reforço a uma camada mais
baixa serve para execução de ação a camada acima
 Aprendizagem por reforço relacional
 Modelo intencional do ambiente
 Baseado em programas lógicos ou árvores de decisão com
variáveis lógicas
 Fornecido como conhecimento prévio, e/ou
 aprendido junto a função valor ou ação-valor
 via programação em lógica indutiva
 Aprendizagem por reforço multi-agentes
Leituras
 Capítulo 22 do AIMA de Russell & Norvig
www.cs.berkeley.edu/~russell/aima.html
 Capítulo 13 de Machine Learning do Mitchell
www.cs.cmu.edu/~tom/mlbook.html
 Reinforcement Learning, livro de Sutton & Barbo
http://www-anw.cs.umass.edu/~rich/book/the-book.html
 Reiforcement Learning: A Survey
de Kaelbling, L.P. & Littman, M.L.
www.cs.cmu.edu/afs/cs/project/jair/pub/volume4/
kaelbling96a-html/rl-survey.html
 ifile: An Application of Machine Learning to E-Mail
Filtering, http://citeseer.nj.nec.com/11099.html