Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Aprenda Controle Monte Carlo Off-Policy | Métodos de Monte Carlo
Introdução ao Aprendizado por Reforço

bookControle Monte Carlo Off-Policy

Enquanto os métodos on-policy aprendem seguindo e aprimorando a mesma política, os métodos off-policy introduzem uma diferença: eles aprendem sobre uma política (a política alvo) enquanto seguem outra (a política de comportamento). Essa separação é poderosa — permite avaliar ou melhorar uma política alvo sem a necessidade de realmente segui-la durante a coleta de dados.

Analogia

Vamos voltar à sorveteria do capítulo anterior. Você e seu amigo entram, e novamente, os três sabores familiares estão disponíveis: chocolate, baunilha e morango. Chocolate é o seu favorito, e sua primeira reação é pedi-lo. Mas essa loja é nova para você, e não tem certeza se escolher chocolate é a melhor opção. Felizmente, seu amigo é um grande apreciador de sorvetes e já visitou quase todas as lojas da cidade. Você pede a opinião dele. "O chocolate aqui é razoável," ele diz, "mas confie em mim — o morango é excepcional." Então, com base na experiência dele, você decide deixar sua escolha habitual de lado e optar pelo morango.

Essa decisão — confiar na experiência de outra pessoa para orientar sua própria escolha — é a essência dos métodos off-policy. Você está tentando aprimorar sua tomada de decisão utilizando dados coletados sob o comportamento de outra pessoa. Ainda é exploração — mas guiada por experiência externa em vez da sua própria.

Amostragem de Importância

Como o agente segue a política de comportamento durante a geração dos episódios, é necessário considerar a diferença entre o que a política de comportamento gera e o que a política alvo geraria. É aqui que entra a amostragem de importância.

A amostragem por importância fornece um método para ajustar os retornos observados sob a política de comportamento, tornando-os estimativas válidas para a política alvo.

Vamos analisar uma trajetória que começa em um determinado estado StS_t e segue uma política π\pi até o episódio terminar em um tempo TT. Especificamente, observamos:

At,St+1,At+1,...,STA_t, S_{t+1}, A_{t+1}, ..., S_{T}

Agora, qual é a probabilidade dessa trajetória ocorrer sob uma política π\pi? Ela depende tanto das probabilidades de ação da política quanto da dinâmica de transição do ambiente:

p(trajectoryπ)=k=tT1π(AkSk)p(Sk+1Sk,Ak)p(trajectory | \pi) = \prod_{k=t}^{T-1} \pi(A_k | S_k)p(S_{k+1} | S_k, A_k)

Agora, suponha que a trajetória tenha sido realmente gerada por uma política diferente — a política de comportamento bb. Para utilizar corretamente essa trajetória para estimar expectativas sob a política alvo π\pi, é necessário considerar o quanto essa sequência de ações seria mais ou menos provável sob π\pi em comparação com bb.

É aqui que entra a razão de amostragem por importância. Ela é definida como a probabilidade relativa da trajetória sob as duas políticas:

ρ=p(trajectoryπ)p(trajectoryb)=k=tT1π(AkSk)p(Sk+1Sk,Ak)b(AkSk)p(Sk+1Sk,Ak)=k=tT1π(AkSk)b(AkSk)\rho = \frac{p(trajectory | \pi)}{p(trajectory | b)} = \prod_{k=t}^{T-1} \frac{\pi(A_k | S_k)p(S_{k+1} | S_k, A_k)}{b(A_k | S_k)p(S_{k+1} | S_k, A_k)} = \prod_{k=t}^{T-1} \frac{\pi(A_k | S_k)}{b(A_k | S_k)}

No final, as probabilidades de transição se cancelam, já que ambas as políticas operam no mesmo ambiente, e o valor de ρ\rho depende apenas das políticas, não do ambiente.

Por que isso é importante

A razão ρ\rho indica como reponderar o retorno GtG_t observado sob a política de comportamento para que ele se torne uma estimativa não tendenciosa do que o retorno teria sido sob a política alvo:

Eπ[Gt]=Eb[ρGt]\def\E{\operatorname{\mathbb{E}}} \E_\pi[G_t] = \E_b[\rho \cdot G_t]

Em outras palavras, mesmo que os dados tenham sido coletados usando bb, ainda é possível estimar os retornos esperados sob π\pi — desde que bb atribua probabilidade diferente de zero para toda ação que π\pi possa tomar (suposição de cobertura).

Considerações Práticas

Variância do Amostragem por Importância

A incorporação da amostragem por importância é conceitualmente simples. Ajusta-se a função valor de ação estimada q(s,a)q(s, a) ponderando cada retorno observado com a respectiva razão de amostragem por importância. A formulação mais simples é a seguinte:

q(s,a)=i=0N(s,a)ρi(s,a)Returnsi(s,a)N(s,a)q(s, a) = \frac{\sum_{i=0}^{N(s, a)} \rho_i(s, a) \cdot Returns_i(s, a)}{N(s, a)}

onde:

  • ρi(s,a)\rho_i(s, a) é a razão de amostragem por importância para a ii-ésima trajetória iniciada em (s,a)(s, a);
  • Returnsi(s,a)Returns_i(s, a) é o retorno dessa trajetória;
  • N(s,a)N(s, a) é o número de vezes que (s,a)(s, a) foi visitado.

Isto é conhecido como amostragem por importância ordinária. Fornece uma estimativa não tendenciosa de q(s,a)q(s, a), mas pode apresentar variância muito alta, especialmente quando as políticas de comportamento e alvo diferem significativamente.

Para mitigar o problema da variância, pode-se utilizar uma alternativa mais estável: amostragem por importância ponderada. Este método normaliza os pesos de importância, reduzindo o impacto de razões elevadas e proporcionando um aprendizado mais estável:

q(s,a)=i=0N(s,a)ρi(s,a)Returnsi(s,a)i=0N(s,a)ρi(s,a)q(s, a) = \frac{\sum_{i=0}^{N(s, a)} \rho_i(s, a) \cdot Returns_i(s, a)}{\sum_{i=0}^{N(s, a)} \rho_i(s, a)}

Nesta versão, o numerador é a mesma soma ponderada dos retornos, mas o denominador agora é a soma dos pesos de importância, em vez de uma simples contagem.

Isso torna a estimativa tendenciosa, mas o viés diminui à medida que mais amostras são coletadas. Na prática, a amostragem por importância ponderada é preferida devido à sua variância significativamente menor e maior estabilidade numérica.

Políticas

Assim como no caso on-policy, utilizam-se políticas ε\varepsilon-gananciosas tanto para a política alvo π(as)\pi(a | s) quanto para a política de comportamento b(as)b(a | s).

À primeira vista, parece natural tornar a política alvo totalmente gananciosa — afinal, o objetivo final é uma política gananciosa. Na prática, entretanto, isso causa um grande problema: se em algum passo π(as)=0\pi(a | s) = 0 para a ação realmente tomada pela política de comportamento, a razão de amostragem por importância ρ\rho se torna zero e o restante do episódio é efetivamente descartado.

Ao utilizar um pequeno ε\varepsilon (por exemplo, ε=0.01\varepsilon = 0.01) na política alvo, garante-se que π(as)>0\pi(a | s) > 0 para toda ação, de modo que ρ\rho nunca colapse para zero no meio do episódio. Após o treinamento, é trivial converter a política ε\varepsilon‑gananciosa aprendida em uma política estritamente gananciosa. Assim como no aprendizado on-policy, deve-se utilizar decaimento de ε\varepsilon na política de comportamento, mas desta vez principalmente por estabilidade numérica, já que ρ\rho ainda pode cair para zero durante o episódio, devido à forma como os números são representados em computadores.

Pseudocódigo

question mark

Qual é o objetivo da amostragem por importância?

Select the correct answer

Tudo estava claro?

Como podemos melhorá-lo?

Obrigado pelo seu feedback!

Seção 4. Capítulo 6

Pergunte à IA

expand

Pergunte à IA

ChatGPT

Pergunte o que quiser ou experimente uma das perguntas sugeridas para iniciar nosso bate-papo

Suggested prompts:

Can you explain the difference between ordinary and weighted importance sampling in more detail?

Why does using a fully greedy target policy cause problems in off-policy learning?

Can you summarize the key advantages of off-policy methods compared to on-policy methods?

Awesome!

Completion rate improved to 2.7

bookControle Monte Carlo Off-Policy

Deslize para mostrar o menu

Enquanto os métodos on-policy aprendem seguindo e aprimorando a mesma política, os métodos off-policy introduzem uma diferença: eles aprendem sobre uma política (a política alvo) enquanto seguem outra (a política de comportamento). Essa separação é poderosa — permite avaliar ou melhorar uma política alvo sem a necessidade de realmente segui-la durante a coleta de dados.

Analogia

Vamos voltar à sorveteria do capítulo anterior. Você e seu amigo entram, e novamente, os três sabores familiares estão disponíveis: chocolate, baunilha e morango. Chocolate é o seu favorito, e sua primeira reação é pedi-lo. Mas essa loja é nova para você, e não tem certeza se escolher chocolate é a melhor opção. Felizmente, seu amigo é um grande apreciador de sorvetes e já visitou quase todas as lojas da cidade. Você pede a opinião dele. "O chocolate aqui é razoável," ele diz, "mas confie em mim — o morango é excepcional." Então, com base na experiência dele, você decide deixar sua escolha habitual de lado e optar pelo morango.

Essa decisão — confiar na experiência de outra pessoa para orientar sua própria escolha — é a essência dos métodos off-policy. Você está tentando aprimorar sua tomada de decisão utilizando dados coletados sob o comportamento de outra pessoa. Ainda é exploração — mas guiada por experiência externa em vez da sua própria.

Amostragem de Importância

Como o agente segue a política de comportamento durante a geração dos episódios, é necessário considerar a diferença entre o que a política de comportamento gera e o que a política alvo geraria. É aqui que entra a amostragem de importância.

A amostragem por importância fornece um método para ajustar os retornos observados sob a política de comportamento, tornando-os estimativas válidas para a política alvo.

Vamos analisar uma trajetória que começa em um determinado estado StS_t e segue uma política π\pi até o episódio terminar em um tempo TT. Especificamente, observamos:

At,St+1,At+1,...,STA_t, S_{t+1}, A_{t+1}, ..., S_{T}

Agora, qual é a probabilidade dessa trajetória ocorrer sob uma política π\pi? Ela depende tanto das probabilidades de ação da política quanto da dinâmica de transição do ambiente:

p(trajectoryπ)=k=tT1π(AkSk)p(Sk+1Sk,Ak)p(trajectory | \pi) = \prod_{k=t}^{T-1} \pi(A_k | S_k)p(S_{k+1} | S_k, A_k)

Agora, suponha que a trajetória tenha sido realmente gerada por uma política diferente — a política de comportamento bb. Para utilizar corretamente essa trajetória para estimar expectativas sob a política alvo π\pi, é necessário considerar o quanto essa sequência de ações seria mais ou menos provável sob π\pi em comparação com bb.

É aqui que entra a razão de amostragem por importância. Ela é definida como a probabilidade relativa da trajetória sob as duas políticas:

ρ=p(trajectoryπ)p(trajectoryb)=k=tT1π(AkSk)p(Sk+1Sk,Ak)b(AkSk)p(Sk+1Sk,Ak)=k=tT1π(AkSk)b(AkSk)\rho = \frac{p(trajectory | \pi)}{p(trajectory | b)} = \prod_{k=t}^{T-1} \frac{\pi(A_k | S_k)p(S_{k+1} | S_k, A_k)}{b(A_k | S_k)p(S_{k+1} | S_k, A_k)} = \prod_{k=t}^{T-1} \frac{\pi(A_k | S_k)}{b(A_k | S_k)}

No final, as probabilidades de transição se cancelam, já que ambas as políticas operam no mesmo ambiente, e o valor de ρ\rho depende apenas das políticas, não do ambiente.

Por que isso é importante

A razão ρ\rho indica como reponderar o retorno GtG_t observado sob a política de comportamento para que ele se torne uma estimativa não tendenciosa do que o retorno teria sido sob a política alvo:

Eπ[Gt]=Eb[ρGt]\def\E{\operatorname{\mathbb{E}}} \E_\pi[G_t] = \E_b[\rho \cdot G_t]

Em outras palavras, mesmo que os dados tenham sido coletados usando bb, ainda é possível estimar os retornos esperados sob π\pi — desde que bb atribua probabilidade diferente de zero para toda ação que π\pi possa tomar (suposição de cobertura).

Considerações Práticas

Variância do Amostragem por Importância

A incorporação da amostragem por importância é conceitualmente simples. Ajusta-se a função valor de ação estimada q(s,a)q(s, a) ponderando cada retorno observado com a respectiva razão de amostragem por importância. A formulação mais simples é a seguinte:

q(s,a)=i=0N(s,a)ρi(s,a)Returnsi(s,a)N(s,a)q(s, a) = \frac{\sum_{i=0}^{N(s, a)} \rho_i(s, a) \cdot Returns_i(s, a)}{N(s, a)}

onde:

  • ρi(s,a)\rho_i(s, a) é a razão de amostragem por importância para a ii-ésima trajetória iniciada em (s,a)(s, a);
  • Returnsi(s,a)Returns_i(s, a) é o retorno dessa trajetória;
  • N(s,a)N(s, a) é o número de vezes que (s,a)(s, a) foi visitado.

Isto é conhecido como amostragem por importância ordinária. Fornece uma estimativa não tendenciosa de q(s,a)q(s, a), mas pode apresentar variância muito alta, especialmente quando as políticas de comportamento e alvo diferem significativamente.

Para mitigar o problema da variância, pode-se utilizar uma alternativa mais estável: amostragem por importância ponderada. Este método normaliza os pesos de importância, reduzindo o impacto de razões elevadas e proporcionando um aprendizado mais estável:

q(s,a)=i=0N(s,a)ρi(s,a)Returnsi(s,a)i=0N(s,a)ρi(s,a)q(s, a) = \frac{\sum_{i=0}^{N(s, a)} \rho_i(s, a) \cdot Returns_i(s, a)}{\sum_{i=0}^{N(s, a)} \rho_i(s, a)}

Nesta versão, o numerador é a mesma soma ponderada dos retornos, mas o denominador agora é a soma dos pesos de importância, em vez de uma simples contagem.

Isso torna a estimativa tendenciosa, mas o viés diminui à medida que mais amostras são coletadas. Na prática, a amostragem por importância ponderada é preferida devido à sua variância significativamente menor e maior estabilidade numérica.

Políticas

Assim como no caso on-policy, utilizam-se políticas ε\varepsilon-gananciosas tanto para a política alvo π(as)\pi(a | s) quanto para a política de comportamento b(as)b(a | s).

À primeira vista, parece natural tornar a política alvo totalmente gananciosa — afinal, o objetivo final é uma política gananciosa. Na prática, entretanto, isso causa um grande problema: se em algum passo π(as)=0\pi(a | s) = 0 para a ação realmente tomada pela política de comportamento, a razão de amostragem por importância ρ\rho se torna zero e o restante do episódio é efetivamente descartado.

Ao utilizar um pequeno ε\varepsilon (por exemplo, ε=0.01\varepsilon = 0.01) na política alvo, garante-se que π(as)>0\pi(a | s) > 0 para toda ação, de modo que ρ\rho nunca colapse para zero no meio do episódio. Após o treinamento, é trivial converter a política ε\varepsilon‑gananciosa aprendida em uma política estritamente gananciosa. Assim como no aprendizado on-policy, deve-se utilizar decaimento de ε\varepsilon na política de comportamento, mas desta vez principalmente por estabilidade numérica, já que ρ\rho ainda pode cair para zero durante o episódio, devido à forma como os números são representados em computadores.

Pseudocódigo

question mark

Qual é o objetivo da amostragem por importância?

Select the correct answer

Tudo estava claro?

Como podemos melhorá-lo?

Obrigado pelo seu feedback!

Seção 4. Capítulo 6
some-alt