Compreendendo o papel do fator de desconto na aprendizagem por reforço

43

Estou me ensinando sobre o aprendizado por reforço e tentando entender o conceito de recompensa com desconto. Portanto, a recompensa é necessária para dizer ao sistema quais pares de ação e estado são bons e quais são ruins. Mas o que não entendo é por que a recompensa com desconto é necessária. Por que deveria importar se um bom estado é alcançado em breve ou mais tarde?

Eu entendo que isso é relevante em alguns casos específicos. Por exemplo, se você estiver usando o aprendizado por reforço para negociar no mercado de ações, é mais benéfico obter lucro mais cedo ou mais tarde. Isso ocorre porque ter esse dinheiro agora permite que você faça coisas com esse dinheiro agora, o que é mais desejável do que fazer com esse dinheiro mais tarde.

Mas, na maioria dos casos, não vejo por que o desconto é útil. Por exemplo, digamos que você queira que um robô aprenda a navegar pela sala para chegar ao outro lado, onde há penalidades se colidir com um obstáculo. Se não houvesse fator de desconto, aprenderia a alcançar o outro lado perfeitamente, sem colidir com obstáculos. Pode levar muito tempo para chegar lá, mas chegará lá eventualmente.

Mas se dermos um desconto à recompensa, o robô será incentivado a alcançar o outro lado da sala rapidamente, mesmo que tenha que colidir com objetos ao longo do caminho. Claramente, este não é um resultado desejável. Claro, você quer que o robô chegue ao outro lado rapidamente, mas não se isso significa que ele precisa colidir com objetos ao longo do caminho.

Portanto, minha intuição é que qualquer forma de fator de desconto levará a uma solução abaixo do ideal. E a escolha do fator de desconto geralmente parece arbitrária - muitos métodos que eu vi simplesmente o definem em 0,9. Isso me parece muito ingênuo e parece oferecer uma troca arbitrária entre a solução ótima e a solução mais rápida, enquanto na realidade essa troca é muito importante.

Por favor, alguém pode me ajudar a entender tudo isso? Obrigado :)

Karnivaurus
fonte

Respostas:

36

TL; DR.

O fato de a taxa de desconto ser menor que 1 é um truque matemático para tornar uma soma infinita finita. Isso ajuda a provar a convergência de certos algoritmos.

Na prática, o fator de desconto pode ser usado para modelar o fato de que o tomador de decisão não tem certeza se no próximo instante de decisão o mundo (por exemplo, ambiente / jogo / processo ) vai terminar.

Por exemplo:

Se o tomador de decisão for um robô, o fator de desconto pode ser a probabilidade de o robô ser desligado no próximo instante (o mundo termina na terminologia anterior). Essa é a razão pela qual o robô é míope e não otimiza a recompensa de soma, mas a recompensa de soma com desconto .

Fator de desconto menor que 1 (em detalhes)

Para responder com mais precisão, por que a taxa de desconto deve ser menor que uma, apresentarei primeiro os Processos de Decisão de Markov (MDPs).

SA

Em sua configuração básica, o tomador de decisão toma uma ação e recebe uma recompensa do ambiente, e o ambiente muda de estado. Então, o tomador de decisão sente o estado do ambiente, toma uma ação, recebe uma recompensa e assim por diante. As transições de estado são probabilísticas e dependem apenas do estado real e das ações tomadas pelo tomador de decisão. A recompensa obtida pelo tomador de decisão depende das medidas tomadas e do estado original e do novo ambiente.

Rai(sj,sk)aisjskaiπ π():SAsjSaiAπ

π

maxπ:S(n)ailimTE{n=1TβnRxi(S(n),S(n+1))}(1),
ββ<1

Observe que o problema de otimização acima tem um horizonte de tempo infinito ( ), e o objetivo é maximizar a soma da recompensa com (a recompensa é multiplicada por ). Isso geralmente é chamado de problema do MDP com um critério de recompensa com desconto no horizonte infinito .TdiscountedRβn

O problema é chamado de desconto porque . Se não houvesse um problema com desconto a soma não convergiria. Todas as políticas que obtêm, em média, uma recompensa positiva a cada instante somam-se ao infinito. Seria um critério de recompensa de soma de horizonte infinito e não é um bom critério de otimização.β<1β=1

Aqui está um exemplo de brinquedo para mostrar o que eu quero dizer:

Suponha que haja apenas duas ações possíveis e que a função de recompensa seja igual a se e se (a recompensa não depende do estado).a=0,1R1a=10a=0

É claro que a política que recebe mais recompensa é sempre executar ação e nunca a ação . Vou chamar essa política de . Compararei com outra política que executa a ação com pequena probabilidade , e a ação caso contrário.a=1a=0πππa=1α<<1a=0

No horizonte infinito, a equação dos critérios de recompensa com desconto (1) se torna (a soma de uma série geométrica) para a política enquanto que para equação da política (1) se torna . Como , dizemos que é uma política melhor que . Na verdade, é a política ideal.11βππα1β11β>α1βπππ

No horizonte infinito, os critérios de recompensa da soma ( ) a equação (1) não convergem para nenhuma das políticas (ela soma até o infinito). Portanto, enquanto a política obtém recompensas maiores do que a ambas as políticas são iguais de acordo com esse critério. Essa é uma das razões pelas quais os critérios de recompensa da soma do horizonte infinito não são úteis.β=1ππ

Como mencionei antes, faz o truque de fazer a soma na equação (1) convergir.β<1

Outros critérios de otimização

Existem outros critérios de otimização que não impõem esse :β<1

Os critérios de horizonte finito, caso o objetivo seja maximizar a recompensa com desconto até o horizonte de tempoT

maxπ:S(n)aiE{n=1TβnRxi(S(n),S(n+1))},

para e finito.β1T

No critério de recompensa média do horizonte infinito, o objetivo é

maxπ:S(n)ailimTE{n=1T1TRxi(S(n),S(n+1))},

Nota final

Dependendo dos critérios de otimização, seria utilizado um algoritmo diferente para encontrar a política ideal. Por exemplo, as políticas ótimas dos problemas do horizonte finito dependeriam do estado e do instante de tempo real. A maioria dos algoritmos de aprendizado por reforço (como SARSA ou Q-learning) converge para a política ideal apenas para os critérios de horizonte infinito de recompensa com desconto (o mesmo acontece para os algoritmos de programação dinâmica). Para os critérios médios de recompensa, não foi demonstrado que nenhum algoritmo converja para a política ideal, no entanto, pode-se usar R-learning com bom desempenho, embora sem boa convergência teórica.

PolBM
fonte
1
Alguma idéia do que devo ler para entender todos os chineses em sua resposta?
Thibaut noah
@thibautnoah Esta é a IMHO a melhor referência Aprendizado por Reforço: Uma introdução de Sutton e Barto. [ people.inf.elte.hu/lorincz/Files/RL_2006/SuttonBook.pdf]
PolBM
graças companheiro, provavelmente vai precisar de outro livro sobre matemática, mas eu acho que é um começo;)
thibaut noah
6

Você está certo de que o fator de desconto (chamado - observe que isso é diferente de de TD- ) age como uma "urgência da vida" e, portanto, faz parte do problema - assim como ocorre em vidas humanas: algumas pessoas vivem como se vivessem para sempre; algumas pessoas vivem como se fossem morrer amanhã.γλλ

Neil G
fonte
2

TL; DR: fatores de desconto estão associados a horizontes temporais. Os horizontes de tempo mais longos têm muito mais variação , pois incluem informações mais irrelevantes, enquanto os horizontes de tempo curto são enviesados ​​em direção apenas a ganhos de curto prazo.

O fator de desconto determina essencialmente o quanto os agentes de aprendizado por reforço se preocupam com as recompensas no futuro distante em relação às do futuro imediato. Se , o agente será completamente míope e só aprenderá sobre ações que produzem uma recompensa imediata. Se , o agente avaliará cada uma de suas ações com base na soma total de todas as suas recompensas futuras.γ=0γ=1

Então, por que você não deseja sempre tornar mais alto possível? Bem, a maioria das ações não tem repercussões duradouras. Por exemplo, suponha que, no primeiro dia de cada mês, decida tratar-se de um smoothie e tenha que decidir se receberá um smoothie de mirtilo ou um smoothie de morango. Como um bom aluno de reforço, você avalia a qualidade de sua decisão pelo tamanho das suas recompensas subsequentes. Se o seu horizonte de tempo for muito curto, você só levará em consideração as recompensas imediatas, como o sabor do seu smoothie. Com um horizonte de tempo mais longo, como algumas horas, você também pode considerar coisas como se você está ou não com uma dor de estômago. Mas se o seu horizonte de tempo durar o mês inteiro, tudo o que faz você se sentir bem ou mal durante todo o mêsγlevará em consideração seu julgamento sobre se você tomou ou não a decisão correta do smoothie. Você incluirá muitas informações irrelevantes e, portanto, seu julgamento terá uma enorme variação e será difícil aprender.

Escolher um valor específico de é equivalente a escolher um horizonte de tempo. Ajuda a reescrever a recompensa com desconto um agente como onde identifico e . O valor mostra explicitamente o horizonte temporal associado a um fator de desconto; corresponde a e quaisquer recompensas muito mais queγG

Gt=Rt+γRt+1+γ2Rt+2+=k=0γkRt+k=Δt=0eΔt/τRt+Δt
γ=e1/τkΔtτγ=1τ=τas etapas de tempo no futuro são exponencialmente suprimidas. Geralmente, você deve escolher um fator de desconto para que o horizonte de tempo contenha todas as recompensas relevantes para uma ação específica, mas não mais.

clwainwright
fonte