A maior rede de estudos do Brasil

Grátis
32 pág.
RL-Introducao_2aula_parteb

Pré-visualização | Página 1 de 2

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 selecionado

Crie agora seu perfil grátis para visualizar sem restrições.