Quando os métodos de Monte Carlo são preferidos aos de diferença temporal?

12

Ultimamente tenho pesquisado muito sobre o aprendizado por reforço. Eu segui o aprendizado de reforço de Sutton & Barto : uma introdução para a maior parte disso.

Sei o que são os Processos de Decisão de Markov e como o aprendizado de Programação Dinâmica (DP), Monte Carlo e Diferença Temporal (DP) pode ser usado para resolvê-los. O problema que tenho é que não vejo quando Monte Carlo seria a melhor opção em relação ao aprendizado de TD.

A principal diferença entre eles é que o aprendizado de TD usa bootstrapping para aproximar a função de valor de ação e Monte Carlo usa uma média para fazer isso. Eu realmente não consigo pensar em um cenário em que este seja o melhor caminho a percorrer.

Meu palpite é que pode ter algo a ver com desempenho, mas não consigo encontrar nenhuma fonte que possa provar isso.

Estou faltando alguma coisa ou o TD-learning geralmente é a melhor opção?

Anne-dirk
fonte

Respostas:

8

O principal problema com o aprendizado de TD e DP é que suas atualizações de etapas são tendenciosas nas condições iniciais dos parâmetros de aprendizado. O processo de inicialização normalmente atualiza uma função ou consulta Q (s, a) em um valor sucessor Q (s ', a'), usando as estimativas atuais. Claramente, no início do aprendizado, essas estimativas não contêm informações de recompensas reais ou transições de estado.

Se o aprendizado funcionar como pretendido, o viés será reduzido assintoticamente em várias iterações. No entanto, o viés pode causar problemas significativos, especialmente para métodos fora da política (por exemplo, Q Learning) e ao usar aproximadores de função. É provável que essa combinação falhe em convergir que é chamada de tríade mortal em Sutton & Bart.

Os métodos de controle de Monte Carlo não sofrem esse viés, pois cada atualização é feita usando uma amostra real do que Q (s, a) deve ser. No entanto, os métodos de Monte Carlo podem sofrer alta variação, o que significa que mais amostras são necessárias para alcançar o mesmo grau de aprendizado em comparação com o TD.

Na prática, o aprendizado de TD parece aprender com mais eficiência se os problemas com a tríade mortal puderem ser superados. Resultados recentes usando a repetição da experiência e cópias encadeadas de estimadores fornecem soluções alternativas que abordam problemas - por exemplo, foi assim que o aluno DQN para jogos da Atari foi construído.

Há também um meio termo entre TD e Monte Carlo. É possível construir um método generalizado que combine trajetórias de diferentes comprimentos - do TD de uma etapa até a execução completa de episódios em Monte Carlo - e combiná-las. A variante mais comum disso é o aprendizado de TD ( ), em que é um parâmetro de (aprendizado de TD efetivamente em uma etapa) a (aprendizado de Monte Carlo efetivamente), mas com um bom recurso que pode ser usado em contínuo problemas). Normalmente, um valor entre e torna o agente de aprendizado mais eficiente - embora, como muitos hiperparâmetros, o melhor valor para usar dependa do problema.X 0 1 0 1λλ0 01 10 01 1

Se você estiver usando um método baseado em valor (em oposição a um método baseado em políticas), o aprendizado de TD geralmente é mais utilizado na prática, ou um método de combinação de TD / MC como TD (λ) pode ser ainda melhor.

Em termos de "vantagem prática" para MC? O aprendizado de Monte Carlo é conceitualmente simples, robusto e fácil de implementar, embora muitas vezes mais lento que o TD. Geralmente, eu não o usava para um mecanismo de controlador de aprendizado (a menos que com pressa de implementar algo para um ambiente simples), mas consideraria seriamente para avaliação de políticas, a fim de comparar vários agentes, por exemplo - isso se deve a medida imparcial, o que é importante para o teste.

Neil Slater
fonte
Primeiro, obrigado pela resposta. Vejo como, em tese, um algoritmo imparcial pode ser preferido sobre um tendencioso. Mas, considerando a alta variação que Monte Carlo pode dar no início do treinamento, não vejo como isso realmente importa. Tanto o Monte Carlo quanto o TD começarão com aproximações imprecisas e, pelo que eu li, o TD convergirá muito mais rapidamente. Eu simplesmente não consigo realmente ter uma vantagem prática de usar Monte Carlo. (Divertindo a tríade mortal pode ser evitado)
Anne-Dirk
11
@ Anne-dirk Se você estiver usando um método baseado em valor (em oposição a um método baseado em políticas), o aprendizado de TD é geralmente usado mais na prática, ou um método de combinação TD / MC como TD (λ) pode ser Melhor. Não sei ao certo o que você quer dizer com "vantagem prática"? O aprendizado de Monte Carlo é conceitualmente simples, robusto e fácil de implementar. Geralmente, eu não o usava para um mecanismo de controlador de aprendizado (a menos que tenha pressa de implementar algo para um ambiente simples), mas consideraria seriamente para avaliação de políticas, a fim de comparar vários agentes, por exemplo.
Neil Slater
@ Neul Slater Aaaah Entendo ... Esse é o tipo de resposta que eu estava procurando :) Obrigado pela ajuda!
Anne-Dirk
-1

Essencialmente, isso depende do seu ambiente.

O TD explora a propriedade Markov, ou seja, os estados futuros de um processo dependem apenas do estado atual e, portanto, geralmente é mais eficiente usar o TD em ambientes Markov.

O MC não explora a propriedade Markov, pois baseia as recompensas em todo o processo de aprendizado, que se presta a ambientes não-Markov.

BigBadMe
fonte
Não acho que isso esteja correto ou, pelo menos, óbvio. A propriedade Markov, no contexto de RL, está associada aos estados. Você pode esclarecer por que os algoritmos MC funcionariam melhor quando a propriedade Markov não seria satisfeita?
nbro 22/02/19
Para ser claro, eu estava me referindo à eficiência. Se você pode explorar a propriedade Markov, o TD é vantajoso, porque você pode iniciar em qualquer estado, ação e ação e o resultado será sempre o mesmo, para que você possa calcular o erro do TD com altos níveis de certeza. Com o não-MDP, se você obtiver um estado parcialmente observado, o TD pode não ser muito eficiente. Isso não quer dizer que você não pode usar TD em não-MDPs, mas pode ser ineficiente e obter melhor sucesso com TD lambda do que com TD (1).
BigBadMe 23/02/19
"Se você pode explorar a propriedade Markov, o TD é vantajoso, porque você pode iniciar em qualquer estado, ação e ação e o resultado sempre será o mesmo", será o mesmo se o ambiente for determinístico. O que isso tem a ver com a propriedade Markov? Eu não recebo suas reivindicações. Onde você leu que o TD será mais ineficiente que o MC, por exemplo, POMDPs?
Nbro 23/02/19
Literalmente, tem tudo a ver com ser Markov; se você estiver em um ambiente Markov, depois de estabelecer a ação a no estado a, ele levará a 'com recompensa x - sempre será o caso em um ambiente markov, para que você não precise avaliá-lo e mais - você pode tomar medidas maiores e o TD permite explorar isso. Mas não será o caso em um POMDP, porque você pode ter exatamente o mesmo estado, executar a mesma ação, mas acabar em estados e recompensas completamente diferentes.
BigBadMe 23/02/19
"se você estiver em um ambiente de Markov, depois que você estabelecer a ação a no estado a, ele liderará o estado 'com recompensa x". Não . Isso só é verdade se o ambiente for determinístico . O ambiente também pode ser estocástico . "esse sempre será o caso em um ambiente markov". Não , esse é um problema ortogonal à propriedade Markov.
nbro 23/02/19