Q-learning é um algoritmo de aprendizado por reforço livre de modelo que treina um agente para atribuir valores às suas ações possíveis com base em seu estado atual, sem exigir um modelo do ambiente. Ele pode lidar com problemas com transições estocásticas e recompensas sem exigir adaptações. Para qualquer processo de decisão de Markov finito, o Q-learning encontra uma política ótima no sentido de maximizar o valor esperado da recompensa total ao longo de qualquer e todos os passos sucessivos, a partir do estado atual, dado tempo de exploração infinito e uma política parcialmente aleatória. O "Q" refere-se à função que o algoritmo calcula: a recompensa esperada - ou seja, a qualidade - de uma ação tomada em um determinado estado.
Em um exemplo simples, um agente em um labirinto de grade aprende a alcançar uma saída que vale 10 pontos. Em uma bifurcação, o Q-learning pode atribuir um valor maior a mover-se para a direita do que para a esquerda se a direita chega à saída mais rápido, melhorando essa escolha ao tentar ambas as direções ao longo do tempo. Isso ilustra como o algoritmo equilibra recompensa imediata contra resultados de longo prazo por meio de atualizações iterativas.
Contexto de Aprendizado por Reforço
O aprendizado por reforço envolve um agente, um conjunto de estados \(\mathcal{S}\), e um conjunto \(\mathcal{A}\) de ações por estado. Ao executar uma ação \(a \in \mathcal{A}\), o agente transita de estado para estado. Executar uma ação em um estado específico fornece ao agente uma recompensa, uma pontuação numérica. O objetivo do agente é maximizar sua recompensa total adicionando a recompensa máxima alcançável de estados futuros à recompensa por alcançar seu estado atual, influenciando efetivamente a ação atual pelo potencial de recompensa futura. Essa recompensa potencial é uma soma ponderada dos valores esperados das recompensas de todos os passos futuros a partir do estado atual.
Como exemplo, considere embarcar em um trem, onde a recompensa é medida pelo negativo do tempo total de embarque. Uma estratégia é entrar pela porta do trem assim que ela abre, minimizando o tempo inicial de espera. Se o trem está lotado, no entanto, a entrada é lenta, pois passageiros que saem lutam para partir. O tempo total de embarque é então 0 segundos de espera mais 15 segundos de luta. No dia seguinte, por acaso aleatório (exploração), o agente espera e deixa os outros partirem primeiro, resultando em uma espera mais longa, mas menos tempo de luta. No geral, esse caminho tem uma recompensa maior, pois o tempo total de embarque é 5 segundos de espera mais 0 segundos de luta. Através da exploração, apesar da ação inicial paciente resultar em um custo maior do que a estratégia forçada, o custo geral é menor, revelando uma estratégia mais recompensadora.
Mecânica do Algoritmo
Após \(\Delta t\) passos no futuro, o agente decidirá algum próximo passo. O peso para este passo é calculado como \(\gamma^{\Delta t}\), onde \(\gamma\) (o fator de desconto) é um número entre 0 e 1. Assumindo \(\gamma < 1\), ele valoriza recompensas recebidas mais cedo do que aquelas recebidas mais tarde, refletindo o valor de um bom começo. \(\gamma\) também pode ser interpretado como a probabilidade de sucesso ou sobrevivência a cada passo \(\Delta t\).
O algoritmo tem uma função que calcula a qualidade de uma combinação estado-ação: \(Q: \mathcal{S} \times \mathcal{A} \to \mathbb{R}\). Antes que o aprendizado comece, \(Q\) é inicializado com um valor fixo possivelmente arbitrário escolhido pelo programador. Em cada tempo \(t\), o agente seleciona uma ação \(A_t\), observa uma recompensa \(R_{t+1}\), entra em um novo estado \(S_{t+1}\) (que pode depender tanto do estado anterior \(S_t\) quanto da ação selecionada), e \(Q\) é atualizado. A atualização central é uma equação de Bellman como uma simples atualização de iteração de valor, usando a média ponderada do valor atual e a nova informação:
\(Q_{new}(S_t, A_t) \leftarrow (1 - \alpha) \cdot Q(S_t, A_t) + \alpha \cdot [R_{t+1} + \gamma \max_a Q(S_{t+1}, a)]\)
onde \(\alpha\) é a taxa de aprendizado, controlando quanto a nova informação sobrepõe a informação antiga.
Exploração e Explotação
O algoritmo depende de um equilíbrio entre exploração (tentar novas ações para descobrir suas recompensas) e explotação (escolher ações conhecidas por produzir altas recompensas). Uma política parcialmente aleatória, como epsilon-greedy, seleciona a ação mais conhecida na maioria das vezes, mas ocasionalmente escolhe uma ação aleatória para explorar. Isso garante que o agente possa melhorar suas estimativas ao longo do tempo, como visto no exemplo do embarque no trem, onde a exploração aleatória revelou uma estratégia melhor.
Convergência e Otimalidade
Para qualquer processo de decisão de Markov finito, o Q-learning converge para uma política ótima que maximiza a recompensa total esperada a partir de qualquer estado inicial, desde que haja tempo de exploração infinito e um cronograma adequado de taxa de aprendizado. O algoritmo não exige um modelo das dinâmicas de transição do ambiente, tornando-o aplicável a problemas onde tal modelo é desconhecido ou complexo. Essa propriedade livre de modelo o distingue de métodos baseados em modelo que exigem probabilidades de transição explícitas.
Aplicações e Extensões
O Q-learning tem sido aplicado em robótica, jogos e sistemas autônomos. Sua forma tabular funciona para espaços de estados pequenos, mas para espaços grandes ou contínuos, extensões como deep Q-networks combinam Q-learning com aprendizado profundo e redes neurais como aproximadores de função. Esses avanços permitiram sucessos em domínios como agentes de jogos de inteligência artificial e tarefas de controle de aprendizado de máquina. Os princípios do algoritmo também sustentam a pesquisa moderna em aprendizado por reforço em instituições como BAIR (Berkeley AI Research) e MIT CSAIL.