Como posso modelar um problema como um MDP se o agente não segue a ordem sucessiva de estados?

Dec 31 2020

No meu problema, o agente não segue a ordem sucessiva de estados, mas seleciona com $\epsilon$- obter o melhor par (estado, ação) de uma fila de prioridade. Mais especificamente, quando meu agente vai para um estado$s$ e abre suas ações disponíveis $\{ a_i \}$, então estima cada $(s,a)$emparelhar (regressão com DQN) e armazená-lo na fila. Para que meu agente mude para o estado$s'$, ele escolhe o melhor par da fila em vez de seguir uma das ações disponíveis $\{ a_i \}$ de $s$. Observo que um estado tem um conjunto de ações parcialmente diferente dos outros.

Porém, dessa forma, como posso modelar meu MDP se meu agente não segue a ordem sucessiva de estados?

Mais especificamente, tenho um rastreador focado que tem uma entrada de alguns URLs de sementes. Quero produzir o máximo possível de URLs relevantes com as sementes. Eu modelo a estrutura RL da seguinte maneira.

  • Estado: a página da web,
  • Ações: os URLs externos da página da web do estado,
  • Recompensa: de fonte externa sei se o conteúdo da página da web é relevante.

O problema é que, durante o rastreamento, se o agente continuar avançando seguindo a transição de estado sucessiva, ele pode cair em armadilhas de rastreamento ou ótimos locais. Essa é a razão pela qual uma fila de prioridade é usada de maneira importante no rastreamento. O agente de rastreamento não segue mais a ordem sucessiva de transições de estado. Cada par de estado-ação é adicionado à fila de prioridade com seu valor de ação estimado. Para cada vez, ele seleciona o par estado-ação mais promissor entre todos os pares na fila. Observo que cada ação de URL pode ser estimada levando em consideração o estado da página da Web onde foi extraída.

Respostas

1 FedericoMalerba Jan 03 2021 at 15:38

Seu problema fundamental é que você está confundindo o estado e as ações neste cenário. As páginas da web não são seus estados; seu estado é toda a fila prioritária de (website-outlink)pares + os (new_website-outlink)pares. Sua ação é qual par você seleciona.

Agora, esta é uma configuração de problema de espaço de estado de tamanho variável e espaço de ação de tamanho variável ao mesmo tempo. Para lidar com isso, vamos começar observando que nãostate==observation precisa ser (em geral). Então, qual é a sua observação? Sua observação é um lote de tamanho variável de:

  1. (website-outlink)pares ou
  2. next_website(onde cada um next_websiteé determinado por seu par correspondente)

Ambas as observações podem funcionar bem, escolher entre uma ou outra é apenas uma questão de se você deseja que seu agente aprenda "quais links abrir antes de abri-los" ou "quais links são significativos (depois de abri-los)".

O que sua fila prioritária está essencialmente fazendo é apenas adicionar um truque interessante que:

  • Salva a complexidade computacional de manter o estado ordenado (lembre-se de que seu estado não é um website, mas a lista / lote de website-outlink)
  • Evita recalcular desnecessariamente os valores Q para cada uma de suas ações (lembre-se de que uma ação não é selecionar um link de saída new_website, mas selecionar um link de saída de todas as opções disponíveis na fila)

Observe, entretanto, que para realmente ter o segundo salvamento, é crucial armazenar os valores Q para cada par !!!

A última coisa importante a notar é que em um cenário onde você usa um Replay Buffer (o que eu acho provável, visto que você escolheu um DQN), você não pode usar a fila de prioridade enquanto aprende com a RB. Para ver por que (e para ver em detalhes como seu processo de aprendizagem realmente se parece), comece lembrando que suas atualizações de valor Q são dadas pela fórmula aqui ; seu estado s_té um lote (quase ordenado 1 ) de pares. Q(s_t, a_t)é apenas o resultado da execução de sua regressão DQN apenas no melhor site / par neste lote (você temadicionar um índice para denotar a melhor escolha ao adicionar transições à RB, a fim de ser consistente sobre qual ação foi executada a partir deste estado). Para calcular a estimativa do valor futuro ideal, no entanto, você terá que recalcular o valor Q de cada site / par no próximo estado. NÃO PODE usar a fila de prioridade ao treinar na RB.

1 Você ordenou a fila de prioridade para todos os sites que continha enquanto procurava o último site, mas todos os new_website-outlinkpares que você está adicionando ainda não foram ordenados. Você ainda tem que executar o agente neles e então pode ordená-los com o resto da fila de prioridade para gerar o próximo estado (que ainda não será ordenado porque você terá new_new_website-outinkpares).