Dissertação

A convergent variant of Q-learning with linear function approximation EVALUATED

O problema da divergência em aprendizagem usando diferenças temporais e aproximação funcional está fortemente presente na literatura. Dois dos mais famosos algoritmos em aprendizagem por reforço, TD(\lambda) e Q-learning, não têm garantia de convergência com aproximações funcionais não-lineares. O Q-learning pode até divergir em problemas simples com arquiteturas lineares. O presente estudo procura contribuir para o estado de arte com (i) um melhor entendimento da divergência do TD(0) com arquiteturas não-lineares e (ii) um método convergente, alternativo ao Q-learning, para arquiteturas lineares. Relativamente à primeira contribuição, estudamos um contra-exemplo conhecido e propomos uma alternativa mais simples (dimensionalmente). No exemplo proposto, o TD(0) com uma aproximação não-linear converge para uma de várias possíveis soluções dependendo do valor inicial. Relativamente à segunda contribuição, identificamos um novo conjunto de condições que garantem convergência com probabilidade 1 do Q-learning com aproximação linear, propondo uma variação do algoritmo a duas escalas de tempo. As condições introduzidas são parcialmente inspiradas no DQN, um método proposto recentemente com grande sucesso empírico. Na escala de tempo rápida, o algoritmo que propomos executa uma iteração onde o impacto do bootstrapping é atenuado. Na escala de tempo lenta, a iteração é uma transformação da rede objetivo. Estabelecemos a convergência do algoritmo, apresentamos um limite ao erro obtido e discutimos os nossos resultados à luz de resultados existentes de convergência em aprendizagem por reforço com aproximação funcional. Por fim, ilustramos o comportamento convergente do nosso método em domínios onde o Q-learning fora mostrado divergente.
Aprendizagem por reforço, aprendizagem por diferenças temporais, controlo off-policy, Q-learning, aprendizagem automática, aproximação estocástica.

Novembro 13, 2019, 13:0

Publicação

Obra sujeita a Direitos de Autor

Orientação

ORIENTADOR

Francisco António Chaves Saraiva de Melo

Departamento de Engenharia Informática (DEI)

Professor Associado

ORIENTADOR

Pedro Alexandre Simões dos Santos

Departamento de Matemática (DM)

Professor Auxiliar