Por que o Q-learning não converge ao usar a aproximação de função?

É garantido que o algoritmo tabular de aprendizado de Q encontre a função $Q$ ideal , $Q^*$ , desde que sejam satisfeitas as seguintes condições (condições de Robbins-Monro ) em relação à taxa de aprendizado

1. $\sum_{t} \alpha_t(s, a) = \infty$
2. $\sum_{t} \alpha_t^2(s, a) < \infty$

onde $\alpha_t(s, a)$ significa que a taxa de aprendizagem utilizado quando a actualização da $Q$ valor associado com o estado $s$ e acção $a$ no momento passo de tempo $t$ , em que $0 \leq \alpha_t(s, a) < 1$ é assumida como sendo verdadeira, para todos os estados $s$ e ações $a$ .

Aparentemente, dado que $0 \leq \alpha_t(s, a) < 1$ , para que as duas condições sejam verdadeiras, todos os pares de ação de estado devem ser visitados infinitamente com frequência: isso também é afirmado no livro Aprendizado por reforço: uma introdução , além do fato de que este deve ser amplamente conhecido e é a lógica por trás do uso do $\epsilon$ política -greedy (ou políticas semelhantes) durante o treinamento.

Uma prova completa que mostra que o $Q$ learning encontra a função $Q$ ideal pode ser encontrada no artigo Convergence of Q-learning: A Simple Proof (de Francisco S. Melo). Ele usa conceitos como mapeamento de contração para definir a função $Q$ ideal (consulte também O que é o operador Bellman no aprendizado por reforço? ), Que é um ponto fixo desse operador de contração. Ele também usa um teorema (n. 2) sobre o processo aleatório que converge para $0$ , dadas algumas suposições. (A prova pode não ser fácil de seguir se você não é um cara de matemática.)

Se uma rede neural é usada para representar a função $Q$ , as garantias de convergência do $Q$ learning ainda são válidas? Por que (ou não) o Q-learning converge ao usar a aproximação de função? Existe uma prova formal de tal não convergência de $Q$ learning usando aproximação de função?

Estou procurando por diferentes tipos de respostas, daquelas que fornecem apenas a intuição por trás da não convergência do $Q$ learning ao usar a aproximação de funções àquelas que fornecem uma prova formal (ou um link para um artigo com uma prova formal).

Aqui está uma resposta intuitiva à descrição:

A aproximação de funções pode ser feita com qualquer função parametrizável. Considere o problema de um espaço $Q(s,a)$ onde $s$ são os reais positivos, $a$ é $0$ ou $1$ , e a verdadeira função $Q(s, 0) = s^2$ é Q ( s , 0 ) = s 2 e $Q(s, 1)= 2s^2$ , para todos os estados. Se o seu aproximador de função for $Q(s, a) = m*s + n*a + b$ , não existem parâmetros que possam representar com precisão a verdadeirafunção$Q$ (estamos tentando ajustar uma linha a uma função quadrática). Conseqüentemente, mesmo se você escolher uma boa taxa de aprendizado e visitar todos os estados infinitamente, sua função de aproximação nunca convergirá para a verdadeirafunção$Q$

E aqui está um pouco mais detalhadamente:

1. Redes neurais aproximam funções. Uma função pode ser aproximada em graus maiores ou menores usando polinômios mais ou menos complexos para aproximar-se dela. Se você estiver familiarizado com a aproximação da Taylor Series, essa ideia deve parecer bastante natural. Caso contrário, pense em uma função como uma onda senoidal no intervalo [0- $\pi/2$ ). Você pode aproximar (mal) com uma linha reta. Você pode aproximar melhor com uma curva quadrática. Ao aumentar o grau do polinômio que usamos para aproximar a curva, podemos obter algo que se encaixa cada vez mais na curva.

2. Redes neurais são aproximadores de funções universais . Isso significa que, se você tem uma função, também pode criar uma rede neural profunda ou larga o suficiente para aproximar a função que você criou em um grau arbitrariamente preciso. No entanto, qualquer topologia de rede específica que você escolher será incapaz de aprender todas as funções, a menos que seja infinitamente ampla ou infinitamente profunda. Isso é análogo a como, se você escolher os parâmetros corretos, uma linha pode caber em qualquer dois pontos, mas não em 3 pontos. Se você escolher uma rede com certa largura ou profundidade finita, sempre poderei construir uma função que precise de mais alguns neurônios para se ajustar adequadamente.

3. Os limites do Q-learning são válidos apenas quando a representação da função Q é exata . Para entender por que, suponha que você escolheu aproximar sua função Q com uma interpolação linear. Se a função verdadeira pode ter alguma forma, então claramente o erro em nossa interpolação pode ser ampliado sem limites simplesmente construindo uma função da função Q semelhante ao XOR, e nenhuma quantidade de tempo ou dados extras nos permitirá reduzir esse erro . Se você usar um aproximador de funções e a verdadeira função que você tentar ajustar não foralgo que a função possa aproximar arbitrariamente bem, seu modelo não convergirá adequadamente, mesmo com uma taxa de aprendizado e taxa de exploração bem escolhidas. Usando a terminologia da teoria do aprendizado computacional, podemos dizer que as provas de convergência para o Q-learning assumiram implicitamente que a verdadeira função Q é um membro do espaço de hipóteses no qual você selecionará seu modelo.

Tanto quanto sei, ainda é um problema em aberto obter uma compreensão formal muito clara de exatamente por que / quando temos falta de convergência - ou, pior, às vezes, perigo de divergência. É tipicamente atribuído à "tríade mortal" (ver 11.3 da segunda edição do livro de Sutton e Barto), a combinação de:

1. Aproximação de funções, AND
2. Bootstrapping (usando nossas próprias estimativas de valor no cálculo de nossas metas de treinamento, como realizado pelo $Q$ learning), AND
3. Treinamento fora da política (o $Q$ learning é realmente fora da política).

Isso apenas nos fornece uma descrição (possivelmente não exaustiva) dos casos em que temos falta de convergência e / ou risco de divergência, mas ainda não nos diz por que isso acontece nesses casos.

$Q^*$

Pessoalmente, acho que essa intuição ajuda a entender por que o algoritmo não pode garantir a convergência para a solução ideal, mas eu ainda esperaria intuitivamente que talvez seja capaz de "convergir" para alguma solução "estável" que seja a melhor aproximação possível as restrições inerentes à representação da função escolhida. De fato, é o que observamos na prática quando mudamos para o treinamento em políticas (por exemplo, Sarsa), pelo menos no caso de aproximadores lineares de função.

$Q(s, a)$$(s, a)$$Q$, eles geralmente são atualizados na direção "correta". Intuitivamente, isso significa que, na configuração tabular, na expectativa , iremos lentamente corrigir gradualmente quaisquer erros em quaisquer entradas isoladamente, sem prejudicar outras entradas.

$Q(s, a)$$(s, a)$$Q$

$\max$$\max$

$Q$$(s, a)$

$\max_{a'} Q(s', a')$$Q$$Q(s, a)$$\max_{a'} Q(s', a')$

Finalmente, outro artigo (ainda mais recente) que suspeito ser relevante para essa questão é o Diagnóstico de gargalos nos algoritmos de aprendizado profundo de Q , mas, infelizmente, ainda não tive tempo de lê-lo em detalhes suficientes e resumi-lo adequadamente.