RL-Introducao_2aula_parteb

Prévia do material em texto

Plano de Aulas: 
 Reinforcement Learning 
– Conceitos básicos 
– Elementos de um sistema RL/Características 
 Fundamentos Teóricos 
– Processos de Decisão de Markov 
– Propriedade de Markov 
– Funções de Valor 
– Aprendizado RL 
 Métodos básicos para a solução do problema de RL 
– Programação Dinâmica 
– Monte Carlo 
– Diferenças Temporais 
 TD 
 Aprendizado on-policy e off-policy 
 Q-Learning 
 SARSA 
 AHC 
– Eligibility Traces 
 Estudo de Casos 
Método de Monte Carlo 
 Não não necessitam de informação completa do 
ambiente 
 Aprendizado a partir da experiência: seqüências de 
estados e ações e retornos obtidos pela interação 
agente-ambiente: 
− Aprendizagem a partir de experiência on-line é interessante 
pois não requer conhecimento a priori da dinâmica do 
ambiente, mesmo assim consegue encontrar uma política ótima 
 Aprendizagem a partir de experiência simulada também é 
eficiente 
• Embora um modelo seja necessário, este necessita gerar 
apenas exemplos de transições, não sendo necessário 
distribuições de probabilidades: 
 
− Em várias situações é fácil gerar experiência de acordo com a 
distribuição desejada, mas muito difícil de se obter a distribuição 
Método de Monte Carlo 
• Métodos MC são meios de se resolver problemas de 
aprendizagem por reforço, tomando como base médias 
dos retornos obtidos em seqüência 
 No sentido de se garantir que os retornos sejam bem 
definidos, define-se métodos MC apenas para tarefas 
episódicas: 
Método de Monte Carlo 
– Assume-se que a experiência é dividida em episódios, que 
todos os episódios terminam, qualquer que seja a seqüência de 
ações; 
– Apenas ao final do episódio, as estimativas dos valores e as 
 políticas são modificadas; 
– MC é incremental em episódios, não em passos; 
Avaliação de Política Monte Carlo 
 Dado , deseja-se obter um método de 
aprendizagem para estimar V 
– Lembrando que o valor de um estado é o retorno 
esperado—ganhos futuros, esperados, e cumulativos a 
partir do estado 
– Um forma óbvia de estimarmos o valor de um estado, 
então, é simplesmente calcular a média dos retornos 
observados após visitarmos aquele estado 
Avaliação de Política Monte Carlo 
 À medida que trajetórias são produzidas, e ganhos 
são observados, a média deve convergir para o 
valor esperado. 
 – Esta é a idéia básica de métodos MC 
Avaliação de Política Monte Carlo 
 Suponha que deseja-se estimar V π(s) (o valor de 
um estado s sob a política π), dado um conjunto de 
episódios obtidos a partir de π e passando por s 
 – Cada ocorrência de s em um episódio é chamada de visita a s 
Every-visit MC Method: 
– Estima V (s) como a média dos retornos que seguem 
cada visita a s em um episódio 
Avaliação de Política Monte Carlo 
First-visit MC Method: 
– Estima V (s) como a média dos retornos que seguem 
a primeira visita a s em um conjunto de episódios 
 Os métodos MC FV-EV convergem para o valor 
esperado 
– Neste caso, cada retorno é uma amostra independente 
e identicamente distribuída (i.i.d) de V (s) 
– A partir da lei dos grandes números, a seqüência de 
médias converge para o valor esperado de V(s) 
Avaliação de Política Monte Carlo 
 Inicialização 
–  ← política a ser avaliada 
– V ← função valor-estado arbitrária 
– Return(s) ← lista vazia, para todo s  S 
Avaliação de Política Monte Carlo- 
Algoritmo FV 
 Repita indefinidamente 
– Gere um episódio usando  
– Para cada estado s que aparece no episódio 
 R ← retorno seguindo a primeira ocorrência de s 
 Adicione R à lista Return(s) 
 V(s) ← Average(Return(s)) 
Ex: Robô Reciclador 
 Aplicando o método MC FV à avaliação da 
política equiprovável, obtem-se , após uma 
seqüência de 1000 episódios, cada um 
consistindo de 200 passos: 
– V (l) = 41,11 e V (h) = 47,84 
PD: V (l) = 41, 20 e V (h) = 48, 46. 
– os quais são bem próximos aos obtidos através da 
programação dinâmica. 
Robô Reciclador: O comportamento do 
algoritmo MC primeira-visita 
Exemplo: Blackjack 
 O objetivo do jogo é obter cartas cuja soma de seus 
números é o mais próximo de 21, mas sem exceder 
este valor. 
 Todas as cartas com figuras contam como 10 e o Ás 
pode contar como 1 ou 11 
 O jogo começa com duas cartas para o jogador e 
duas para o distribuidor 
– Uma das cartas do distribuidor pode ser vista 
 Se o jogador tem 21, então ele ganha o jogo a 
menos que o distribuidor também tenha 21, 
definindo um empate 
 O jogador pode pedir uma nova carta (“hit”) até que 
ele pare (“stick”) ou ultrapasse o valor de 21 
(“goes bust”), neste último caso ele perde o jogo 
 O distribuidor segue uma estratégia fixa, sem 
margem para escolha: 
– Ele pára se a soma for igual ou superior a 17, 
caso contrário ele pede carta. 
Exemplo: Blackjack 
Blackjack: Formulação 
 Blackjack é naturalmente formulado 
como um MDP episódico e finito 
– Cada jogo de blackjack é um episódio 
– Os retornos são –1, +1 e 0 (derrota, vitória e 
empate) 
– Todos os ganhos intermediários do jogo são 
nulos 
 As ações dos jogadores são “hit” e “stick” 
 Assume-se que o estado é dado pela soma dos 
valores das cartas dos dois jogadores 
 Assume-se que as cartas são retiradas de um 
baralho de tamanho infinito, portanto não há 
vantagem em recordarmos quais cartas foram 
retiradas do baralho 
Blackjack: Formulação 
 Observações: 
– Note que o mesmo estado nunca re-ocorre em 
um episódio, portanto não há diferença entre os 
métodos MC first-visit e every-visit 
– Embora tenha-se conhecimento completo do 
ambiente, seria muito difícil aplicar métodos DP 
para calcular a função valor 
 DP requer a distribuição para todas as possíveis 
transições de estados 
 Precisa-se de: P 
a
s,s’ e R
a
s,s’ 
Blackjack: Formulação 
Blackjack: Resultados 
http://lcn.epfl.ch/tutorial/english/reinf-bj/html/index.html 
Estimação MC do Valor das Ações 
 Se um modelo não está disponível (MDP), então 
é útil estimar o valor das ações, Q*(s,a), em vez 
do valor dos estados, V*(s) 
– Quando o modelo é conhecido, os valores dos 
estados são suficientes: simplesmente “olhamos” 
um passo a frente e escolhemos a ação que nos 
leva à melhor combinação de retorno e ao 
próximo estado. 
 Sem um modelo o valor do estado sozinho não 
é suficiente: tem-se que explicitamente estimar 
o valor de cada ação, o que nos permitirá 
sugerir uma política de controle. 
Estimação MC do Valor das Ações 
 Um dos objetivos principais dos métodos MC é 
estimar Q*, considerando o problema de avaliar 
uma política. 
– O problema de estimar Q(s, a), o retorno 
esperado quando iniciamos no estado s, 
tomamos a ação a, e seguimos a política  
 Os métodos MC são essencialmente os 
mesmos vistos para estimar o valor dos 
estados 
– O único problema é que muitos pares estado-
ação podem não ser visitados 
– Se  é uma política determinística, então para 
seguir  observa-se retornos apenas de uma 
ação para cada estado 
Estimação MC do Valor das Ações 
 Para que os métodos MC funcionem, 
necessita-se estimar o valor de todas as 
ações a partir de cada estado, não apenas 
aquelas ações favorecidas pela política 
– Este é o problema geral de manter a propriedade 
de exploração 
Estimação MC do Valor das Ações 
 Duas maneiras de garantir a propriedade de 
exploração 
– Um forma de garantir a exploração continuada é 
iniciar cada episódio em uma par estado-ação, 
sendo que cada par tem probabilidade não nula 
de ser selecionadocomo inicial 
– Outra forma é considerar apenas políticas 
estocásticas que associam probabilidade não 
nula a todas as ações 
Estimação MC do Valor das Ações 
Controle Monte Carlo 
 As duas formas acima de modificação (avaliação & 
melhoria) trabalham de certa forma uma contra a 
outra, cada uma criando uma meta para outra, mas 
juntamente eles fazem com que a política e a função 
valor-ação se aproximam das ótimas. 
 Para MC, avaliação de política é feita exatamente 
como anteriormente. Assume-se que: 
Controle Monte Carlo 
 a) Observa-se um número infinito de episódios 
 b) Os episódios são gerados de acordo com a 
propriedade de exploração de pares estado-ação 
– Para melhoria de política, faz-se a política gulosa 
com respeito aos valores correntes da função valor 
O procedimento iterativo de: 
• tomar uma política, 
• avaliá-la, 
• obter política gulosa com base na função valor-ação 
e assim sucessivamente, é conhecido como iteração 
de política generalizada: 
Controle Monte Carlo 
Onde: A indica avaliação de política e 
 M indica processo guloso de melhora de política . 
Se o número de episódios for suficientemente grande, 
a função valor convergirá para a função valor-ação 
ótima Q
∗
. 
Controle MC ES (“Exploring Starts”) 
 Condições não realísticas 
– Episódios satisfazem a condição de exploração 
inicial 
– Avaliação de política pode ser realizada com um 
número infinito de episódios 
Controle Monte Carlo 
 Algoritmo prático 
– Para obter-se um algoritmo prático, tem-se que 
remover ambos os obstáculos acima 
Controle MC: Superando Obstáculos 
 Para métodos MC é natural alternar entre 
avaliação de política e melhoria de política de 
episódio em episódio 
 Duas maneiras de contornar a condição de 
número infinito de episódios: 
– Aproximar Q  em vez computá-la precisamente 
– Interromper o processo de avaliação, antes de se 
obter convergência, executando melhoria de 
política 
Método de Monte Carlo 
 Converge quando o número de visitas de s é infinito; 
 
 As estimativas de cada estado são independentes (não faz 
bootstrap); 
 
 Para comparar alternativas seria necessário explorar todas as 
ações de cada estado; 
 
 Solução: explorar a cada início de episódio um novo estado. 
 
Os métodos de Monte Carlo (Rubinstein, 1981) não precisam 
da modelagem do ambiente e se apresentam de forma 
simples em termos conceituais. 
 
Não são viáveis quando a solução do problema é possível 
apenas de forma incremental (utilizando somente o estado 
atual e os estados imediatos), pois para se atualizar a função 
de valor os métodos de Monte Carlo exigem que o estado final 
seja alcançado no processo. 
Reinforcement Learning: 
Vantagens e Desvantagens dos Métodos 
 
Plano de Aulas: 
 Reinforcement Learning 
– Conceitos básicos 
– Elementos de um sistema RL/Características 
 Fundamentos Teóricos 
– Processos de Decisão de Markov 
– Propriedade de Markov 
– Funções de Valor 
– Aprendizado RL 
 Métodos básicos para a solução do problema de RL 
– Programação Dinâmica 
– Monte Carlo 
– Diferenças Temporais 
 TD 
 Aprendizado on-policy e off-policy 
 Q-Learning 
 SARSA 
 AHC 
– Eligibility Traces 
 Estudo de Casos