Aprendizagem por Reforço: Uma Primeira
Introdução
Parte III
CIPEEL, 2006
Prof. Eduardo Camponogara
Departamento de Automação e Sistemas
Universidade Federal de Santa Catarina
Julho, 2006
Sumário
Interface Agente-Ambiente
O Problema de Aprendizagem por Reforço
Fundamentos Matemáticos
Exemplo: Robô Reciclador
Interface Agente-Ambiente
Sumário
Interface Agente-Ambiente
O Problema de Aprendizagem por Reforço
Fundamentos Matemáticos
Exemplo: Robô Reciclador
Interface Agente-Ambiente
Interface Agente-Ambiente
Sistema tı́pico
◮
Um sistema tı́pico de Aprendizagem por Reforço constitui-se
basicamente de um agente interagindo em um ambiente via
percepção e ação.
◮
A ação tomada muda de alguma forma o ambiente, afetando
o estado na tentativa de alcançar o seu objetivo, e as
mudanças são comunicadas ao agente através de um sinal de
reforço e o próximo estado.
Interface Agente-Ambiente
Interface Agente-Ambiente
Sistema tı́pico
Agente
Estado
st
Reforço (Ganho)
rt
rt+1
Ambiente
st+1
Ação
at
Interface Agente-Ambiente
Interface Agente-Ambiente
Modelos
◮
Os efeitos das ações não podem ser perfeitamente
antecipados.
◮
O agente deve monitorar o ambiente e reagir.
O estado do ambiente é representado por:
◮
1. um conjunto de variáveis de estado, S;
2. um conjunto de ações discretas, A(s), habilitadas a cada
estado s ∈ S; e
3. valor das transições de estados, um sinal de reforço
denominado ganho.
O Problema de Aprendizagem por Reforço
Sumário
Interface Agente-Ambiente
O Problema de Aprendizagem por Reforço
Fundamentos Matemáticos
Exemplo: Robô Reciclador
O Problema de Aprendizagem por Reforço
O Problema de Aprendizagem por Reforço
Objetivo
◮
Levar o agente a escolher as ações que tendem a aumentar a
soma de valores de reforço.
◮
Ou seja, encontrar uma polı́tica ótima, π ∗ , um mapeamento
de estados em ações que maximize os sinais de reforço
acumulados no tempo.
O Problema de Aprendizagem por Reforço
O Problema de Aprendizagem por Reforço
O Problema de Aprendizagem por Reforço apresenta cinco partes
fundamentais.
(I) Ambiente
◮
O ambiente deve ser pelo menos parcialmente observável
através de sensores ou descrições simbólicas.
◮
Também é possı́vel, entretanto, que toda a informação
relevante do ambiente esteja perfeitamente disponı́vel.
◮
Modelos para o ambiente (antecipação/predição de
conseqüências de ações).
O Problema de Aprendizagem por Reforço
O Problema de Aprendizagem por Reforço
(II) Polı́tica de Controle/Decisão
◮
Uma polı́tica expressa pela função π, representa o
comportamento que o agente segue para alcançar o objetivo.
◮
Em outras palavras, uma polı́tica π é um mapeamento de
estados s e ações a em um valor π(s, a).
◮
π(s, a) é a probabilidade do agente tomar a ação a ∈ A(s)
quando este se encontrar no estado s ∈ S.
O Problema de Aprendizagem por Reforço
O Problema de Aprendizagem por Reforço
(II) Polı́tica de Controle/Decisão
◮
O comportamento do agente apresenta variações à medida
que ele vai acumulando experiência a partir das interações
com o ambiente.
◮
O aprendizado pode ser expresso em termos da convergência
até uma polı́tica ótima, π ∗ , que conduza à solução do
problema de forma ótima.
O Problema de Aprendizagem por Reforço
O Problema de Aprendizagem por Reforço
(III) Reforço e Retorno
◮
O reforço é um sinal do tipo escalar, rt+1 , devolvido pelo
ambiente ao agente.
◮
O reforço é emitido assim que uma ação tenha sido efetuada e
uma transição de estado, st → st+1 , tenha ocorrido.
◮
As funções de reforço expressam o objetivo que o agente deve
alcançar.
◮
O agente deve maximizar a quantidade total de reforços
recebidos chamado de retorno acumulado.
O Problema de Aprendizagem por Reforço
O Problema de Aprendizagem por Reforço
(III) Reforço e Retorno
◮
No caso mais simples o retorno é um somatório:
RT = rt+1 + rt+2 + rt+3 + . . . + rT
◮
Em outros casos a interação entre agente e ambiente não
termina naturalmente em um episódio, mas continua sem
limite.
◮
Para essas tarefas a formulação do retorno é um problema,
pois T = ∞ e o retorno que se deseja também tenderá ao
infinito (RT = ∞).
O Problema de Aprendizagem por Reforço
O Problema de Aprendizagem por Reforço
(III) Reforço e Retorno
◮
A taxa de amortização, γ, determina o grau de influência que
têm os valores futuros sobre o reforço total.
◮
A expressão do retorno aplicando taxa de amortização é
expressa por:
Rt = rt+1 + γrt+2 + γ 2 rt+3 + . . . =
∞
X
k=0
onde 0 ≤ γ ≤ 1.
γ k rt+k+1
O Problema de Aprendizagem por Reforço
O Problema de Aprendizagem por Reforço
Sobre a taxa de amortização
◮
Se γ = 0, o agente tem uma visão mı́ope dos reforços,
maximizando apenas os reforços imediatos.
◮
Se γ = 1, a visão do reforço abrange todos os estados futuros
dando a mesma importância para ganhos neste momento e
qualquer ganho futuro.
O Problema de Aprendizagem por Reforço
O Problema de Aprendizagem por Reforço
(IV) Função de Reforço
A função de reforço define quais são os bons e maus eventos para
os agentes.
Três classes básicas de função de retorno são:
1. Reforço só no estado final: as recompensas são todas zero,
exceto no estado final, em que o agente recebe uma
recompensa real (e.g., +1) ou uma penalidade (e.g., −1).
2. Tempo mı́nimo ao objetivo: alcançar o estado final.
3. Minimizar reforços
O Problema de Aprendizagem por Reforço
O Problema de Aprendizagem por Reforço
(V) Função Valor
◮
Função valor como o mapeamento do estado, ou par
estado-ação, em um valor que é obtido a partir do reforço
atual e dos reforços futuros.
◮
A função valor que considera só o estado s é denotada por
V (s) e denominada função valor-estado.
◮
A função valor que considera o par estado-ação (s, a) é
denotada por Q(s, a) e denominada função valor-ação.
O Problema de Aprendizagem por Reforço
O Problema de Aprendizagem por Reforço
(V) Função Valor-Estado
◮
A função valor depende também da polı́tica π que o agente
adota.
◮
Em um Processo de Decisão Markoviano, se define função
valor-estado V π (s), dependente da polı́tica π, conforme a
equação:
∞
X
γ k rt+k+1 | st = s}
V (s) = Eπ {Rt | st = s} = Eπ {
π
k=0
onde a função V π (s) é o valor esperado do retorno a partir do
estado st = s, no instante t, quando o agente se comporta
conforme a polı́tica π.
O Problema de Aprendizagem por Reforço
O Problema de Aprendizagem por Reforço
(V) Função Valor-Ação
◮
Considerando o par estado-ação, a equação para a função
valor-ação Q π (s, a) é:
Q π (s, a) = Eπ {Rt | st = s, at = a}
∞
X
γ k rt+k+1 | st = s, at = a}
= Eπ {
k=0
◮
Q π (s, a) é o reforço esperado para um estado st = s e uma
ação at = a no instante t, e assumindo que o comportamento
do agente deste momento em diante é caracterizado pela
polı́tica π.
Fundamentos Matemáticos
Sumário
Interface Agente-Ambiente
O Problema de Aprendizagem por Reforço
Fundamentos Matemáticos
Exemplo: Robô Reciclador
Fundamentos Matemáticos
Fundamentos Matemáticos
Dois conceitos fundamentais:
◮
Propriedade Markov
◮
Processo de Decisão Markoviano (PDM)
Fundamentos Matemáticos
Propriedade de Markov
Propriedade de Markov
◮
Se a resposta em t + 1 para uma ação efetuada em t depende
de todo o histórico de ações até o momento atual,
◮
então a dinâmica do ambiente é definida pela especificação
completa da distribuição de probabilidades:
Pr {st+1 = s ′ , rt+1 = r | st , at , rt , st−1 , at−1 , . . . , r1 , s0 , a0 }
◮
Onde Pr é a probabilidade do estado st+1 ser o estado s ′ ,
sendo esta uma função que depende de todos os estados,
ações e reforços passados.
Fundamentos Matemáticos
Propriedade de Markov
Propriedade de Markov
◮
Se a resposta do ambiente em t + 1 depende apenas do
estado e ação tomada em t,
◮
Então, a probabilidade da transição para o estado s ′ é dada
por:
′
a
Ps,s
′ = Pr {st+1 = s | st = s, at = a}
◮
No caso acima, a dinâmica do ambiente satisfaz a Propriedade
de Markov.
Fundamentos Matemáticos
Propriedade de Markov
Processo de Decisão Markoviano (PDM)
Definição
Uum Processo de Decisão Markoviano é definido como:
◮
Um conjunto de estados S
◮
Um conjunto de ações A(s) habilitadas em cada estado s ∈ S
◮
Um conjunto de transições entre estados associadas às ações
◮
E um conjunto de probabilidades P sobre o conjunto S que
representa uma modelagem das transições entre os estados.
Fundamentos Matemáticos
Propriedade de Markov
Processo de Decisão Markoviano (PDM)
Processo de Decisão Markoviano
Dado um par estado-ação (s, a), a probabilidade do estado s passar
a um estado s ′ quando a ação a for tomada é dada por:
′
a
Ps,s
′ = Pr {st+1 = s | st = s, at = a}
onde Pr é o operador de probabilidade.
Fundamentos Matemáticos
Propriedade de Markov
Processo de Decisão Markoviano (PDM)
Processo de Decisão Markoviano
Dados um estado e ação atuais e um estado seguinte s ′ , o valor
esperado do retorno é:
a
′
Rs,s
′ = E {rt+1 | st = s, at = a, st+1 = s }
Fundamentos Matemáticos
Propriedade de Markov
Processo de Decisão Markoviano (PDM)
Processo de Decisão Markoviano
a e retorno esperado R a
Os valores de probabilidade Ps,s
′
s,s ′
determinam os aspectos mais importantes da dinâmica de um
PDM finito.
Fundamentos Matemáticos
Propriedade de Markov
Processo de Decisão Markoviano (PDM)
Processo de Decisão Markoviano
Podemos caracterizar o PDM como:
1. um ambiente que evolui probabilisticamente de acordo com
um conjunto finito e discreto de estados;
2. para cada estado do ambiente, existe um conjunto finito de
ações possı́veis;
3. a cada transição o agente recebe um retorno positivo ou
negativo do ambiente em relação à ação tomada; e
4. estados são observados, ações são executadas e reforços são
relacionados.
Exemplo: Robô Reciclador
Sumário
Interface Agente-Ambiente
O Problema de Aprendizagem por Reforço
Fundamentos Matemáticos
Exemplo: Robô Reciclador
Exemplo: Robô Reciclador
Robô Reciclador
Robô reciclador
O robô funciona a bateria e tem como objetivo coletar o maior
número de latas possı́vel, gastando o mı́nimo de energia.
As ações são controladas por um agente que deve:
◮
procurar ativamente por latas por um determinado perı́odo de
tempo;
◮
permanecer parado a espera que alguém lhe traga as latas; ou
◮
voltar à base para recarregar as baterias.
Exemplo: Robô Reciclador
Robô Reciclador
Interface Agente-Ambiente
Ambiente
Ganho
Estado
Ação
Exemplo: Robô Reciclador
Robô Reciclador
Modelo
◮
As decisões são tomadas com base no nı́vel de energia da
bateria: alto ou baixo. Logo:
S = {alto, baixo}
◮
As ações possı́veis são:
A = {vasculhar , aguardar , recarregar }
◮
Ações habilitadas a cada estado:
◮
◮
A(alto) = {vasculhar , aguardar }
A(baixo) = {vasculhar , aguardar , recarregar }.
Exemplo: Robô Reciclador
Robô Reciclador
Modelo
◮
Para cada lata coletada, o agente recebe uma recompensa de
+1.
◮
Caso ele fique sem carga o mesmo leva uma punição no valor
de −3.
◮
Queremos que o robô colete o maior número possı́vel de latas,
assim adotou-se um retorno R vasculhar ≥ R aguardar .
Exemplo: Robô Reciclador
Robô Reciclador
Dinâmica do ambiente
s = st
alto
alto
baixo
baixo
alto
alto
baixo
baixo
baixo
baixo
s ′ = st+1
alto
baixo
alto
baixo
alto
baixo
alto
baixo
alto
baixo
a = at
vasculhar
vasculhar
vasculhar
vasculhar
aguardar
aguardar
aguardar
aguardar
recarregar
recarregar
a
Ps,s
′
α
1−α
1−β
β
1
0
0
1
1
0
a
Rs,s
′
vasculhar
R
R vasculhar
−3
R vasculhar
R aguardar
R aguardar
R aguardar
R aguardar
0
0
Exemplo: Robô Reciclador
Robô Reciclador
Dinâmica do ambiente
1, R aguardar
1 − β, −3
aguardar
vasculhar
β, R vascu
1, 0
alto
recarregar
baixo
α, R vasculhar
vasculhar
aguardar
1 − α, R vasculhar
1, R aguarda
Exemplo: Robô Reciclador
Parte III: Fim
◮
Obrigado pela presença