Baixe o app para aproveitar ainda mais
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
Compartilhar