O que exatamente é o bootstrapping no aprendizado por reforço?

23

Aparentemente, no aprendizado por reforço, o método da diferença temporal (TD) é um método de inicialização. Por outro lado, os métodos de Monte Carlo não são métodos de inicialização.

O que exatamente é o bootstrapping no RL? O que é um método de inicialização no RL?

nbro
fonte

Respostas:

22

O bootstrapping no RL pode ser lido como "usando um ou mais valores estimados na etapa de atualização para o mesmo tipo de valor estimado".

Na maioria das regras de atualização de TD, você verá algo parecido com esta atualização SARSA (0):

Q(s,a)Q(s,a)+α(Rt+1+γQ(s,a)Q(s,a))

O valor é uma estimativa para o valor verdadeiro de e também chamado de destino TD. É um método de autoinicialização porque, em parte, estamos usando um valor Q para atualizar outro valor Q. Há uma pequena quantidade de dados reais observados na forma de , a recompensa imediata para a etapa e também na transição de estado .Rt+1+γQ(s,uma)Q(s,uma)Rt+1ss

Contraste com Monte Carlo, onde a regra de atualização equivalente pode ser:

Q(s,a)Q(s,a)+α(GtQ(s,a))

Onde foi a recompensa total com desconto no momento , assumindo nesta atualização, que ele começou nos estados , tomando a ação , e seguiu a política atual até o final do episódio. Tecnicamente, que é o intervalo de tempo para a recompensa e o estado do terminal. Notavelmente, esse valor-alvo não usa nenhuma estimativa existente (de outros valores Q), apenas usa um conjunto de observações (ou seja, recompensas) do ambiente. Como tal, é garantido que seja uma estimativa imparcial do valor real de , pois é tecnicamente uma amostra deGttsaGt=k=0Tt1γkRt+k+1TQ ( s , a ) Q ( s , a )Q(s,a)Q(s,a).

A principal desvantagem do bootstrap é que ele é direcionado para quaisquer valores iniciais de (ou ). Provavelmente, estas estão erradas, e o sistema de atualização pode ser instável como um todo por causa de muita auto-referência e dados reais insuficientes - esse é um problema com o aprendizado fora da política (por exemplo, Q-learning) usando redes neurais.Q(s,a)V(s)

Sem o bootstrapping, usando trajetórias mais longas, geralmente há uma alta variação , o que, na prática, significa que você precisa de mais amostras antes da convergência das estimativas. Portanto, apesar dos problemas com o bootstrap, se puder ser feito para funcionar, ele pode aprender significativamente mais rápido e é geralmente preferido em relação às abordagens de Monte Carlo.

Você pode comprometer os métodos baseados em amostras de Monte Carlo e os métodos de TD de uma única etapa que iniciam usando uma mistura de resultados de diferentes trajetórias de comprimento. Isso se chama aprendizado de TD ( )λ λ λ e há uma variedade de métodos específicos, como SARSA ( ) ou Q ( ).λλ

Neil Slater
fonte
1
Provavelmente isso deveria ser outra pergunta. No entanto, se você deseja responder, por que exatamente e uma estimativa para ? Q ( s , a )Rt+1+γQ(s,a)Q(s,a)
Nbro 23/01
1
@ nbro: porque na convergência, (essas equações e a maior parte da RL são determinadas pelas equações de Bellman para os MDPs). Observando um evento real que ocorreu iniciando com o estado se ação , você está essencialmente amostrando essa expectativa. O problema é que o valor que você tem para provavelmente ainda não convergiu, portanto a amostra é tendenciosa. s a Q ( S t + 1 , A t + 1 )Q(s,a)=E[Rt+1+γQ(St+1,At+1)|St=s,At=a]saQ(St+1,At+1)
Neil Slater
1
O que impede alguém de usar métodos de MC como uma queima na fase, antes de mudar para o bootstrap? Ou isso pode ser considerado um sub-caso de ? λTD
N1k31t4 15/06
1
@ n1k31t4: Nada impede isso, e deve ser uma abordagem de RL válida. Seria diferente de TD ( ), mas motivado pela mesma idéia de tentar obter bons recursos dos dois algoritmos. Você precisaria experimentá-lo e comparar a eficiência de aprendizado com TD ( ) - você ainda tem um hiper parâmetro para ajustar, que é o número de episódios para executar o MC. Uma versão mais geral seria permitir que mude - comece com e decaia-o para, por exemplo, ou qualquer valor que parecer mais ideal. No entanto, que tem 2 parâmetros hyper, taxa de decaimento e alvo paraλ λ λ = 1 0,4 λλλλλ=10.4λ
Neil Slater
@NeilSlater, ao usar o bootstrap, ele pode convergir? Não consigo entender por que deveria, já que Q (s ', a') é apenas um palpite arbitrário que distorce a estimativa de Q (s, a). Além disso, por que o MC tem uma alta variação em comparação ao TD?
d56 15/06
4

Em geral, a inicialização no RL significa que você atualiza um valor com base em algumas estimativas e não em alguns valores exatos . Por exemplo

Atualizações incrementais da avaliação de políticas de Monte Carlo:

V(St)=V(St)+α(GtV(St))

TD (0) Atualizações de avaliação de políticas:

V(St)=V(St)+α(Rt+1+γV(St+1)V(St))

Em TD (0), o retorno a partir do estado é estimado (inicializado) por enquanto em MC usamos o retorno exato .sRt+1+γV(St+1) Gt

plopd
fonte