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
course content

Conteúdo do Curso

Introdução ao Aprendizado por Reforço

Introdução ao Aprendizado por Reforço

1. Teoria Central de RL
2. Problema do Bandido de Múltiplos Braços
3. Programação Dinâmica
4. Métodos de Monte Carlo
5. Aprendizado por Diferença Temporal

book
Controle 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 pessoal, e seu primeiro instinto é pedi-lo. Mas esta sorveteria é nova para você, e você não tem certeza se escolher chocolate é a melhor opção. Felizmente, seu amigo é um grande apreciador de sorvetes que já visitou quase todas as sorveterias 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 de lado sua escolha habitual e optar pelo morango.

Essa decisão — confiar na experiência de outra pessoa para guiar 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 outro agente. 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 a amostragem de importância entra em cena.

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 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}

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 foi realmente gerada por uma política diferente — a política de comportamento bb. Para utilizar corretamente essa trajetória na estimativa de 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 se torne uma estimativa não viesada 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]

Ou seja, 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 razão de amostragem por importância correspondente. 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 iniciando 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.

Isso é 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 levando a 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, nosso objetivo final é uma política gananciosa. Na prática, porém, 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, garantimos 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

course content

Conteúdo do Curso

Introdução ao Aprendizado por Reforço

Introdução ao Aprendizado por Reforço

1. Teoria Central de RL
2. Problema do Bandido de Múltiplos Braços
3. Programação Dinâmica
4. Métodos de Monte Carlo
5. Aprendizado por Diferença Temporal

book
Controle 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 pessoal, e seu primeiro instinto é pedi-lo. Mas esta sorveteria é nova para você, e você não tem certeza se escolher chocolate é a melhor opção. Felizmente, seu amigo é um grande apreciador de sorvetes que já visitou quase todas as sorveterias 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 de lado sua escolha habitual e optar pelo morango.

Essa decisão — confiar na experiência de outra pessoa para guiar 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 outro agente. 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 a amostragem de importância entra em cena.

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 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}

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 foi realmente gerada por uma política diferente — a política de comportamento bb. Para utilizar corretamente essa trajetória na estimativa de 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 se torne uma estimativa não viesada 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]

Ou seja, 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 razão de amostragem por importância correspondente. 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 iniciando 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.

Isso é 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 levando a 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, nosso objetivo final é uma política gananciosa. Na prática, porém, 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, garantimos 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