Q-learning

Visão geral

aprendizado Q (Q-learning) é um algoritmo fundamental em Aprendizado por Reforço para aprender como um agente deve agir em um ambiente para maximizar a recompensa de longo prazo. Ele é:

Sem modelo (model-free): não requer conhecer a dinâmica de transição do ambiente.
Diferença temporal (temporal-difference, TD): aprende a partir de alvos por bootstrapping (bootstrapped) que combinam recompensas imediatas com estimativas de valor futuro.
Fora da política (off-policy): pode aprender o valor de uma política ótima (gulosa (greedy)) enquanto segue uma política de comportamento (behavior policy) exploratória diferente.

O aprendizado Q aprende uma função valor-ação (action-value function) (também chamada de função Q (Q-function)), denotada (Q(s,a)), que estima o retorno esperado descontado ao executar a ação (a) no estado (s) e então se comportar de forma ótima a partir daí. Uma vez que (Q) é aprendida, a política (policy) é tipicamente a política gulosa: [ \pi(s) = \arg\max_a Q(s,a). ]

O aprendizado Q é especialmente influente porque se estende naturalmente de configurações tabulares (tabular) (pequenos espaços discretos de estados/ações) para abordagens modernas de aproximação de função (function approximation) como Redes Q Profundas (Deep Q-Networks, DQN), que conseguem lidar com entradas de alta dimensionalidade, como imagens.

Contexto: Processos de Decisão de Markov e Funções de Valor

O aprendizado Q geralmente é definido para um Processo de Decisão de Markov (Markov Decision Process, MDP) (ver Processos de Decisão de Markov), caracterizado por:

Estados (s \in \mathcal{S})
Ações (a \in \mathcal{A})
Dinâmica de transição (P(s' \mid s,a))
Função de recompensa (R(s,a,s')) (frequentemente escrita como (r))
Fator de desconto (discount factor) (\gamma \in [0,1))

O objetivo é maximizar o retorno esperado descontado: [ G_t = \sum_{k=0}^{\infty} \gamma^k r_{t+k+1}. ]

Funções valor-ação

A função valor-ação ótima (optimal action-value function) (Q^*(s,a)) é o máximo retorno esperado alcançável a partir de ((s,a)): [ Q^*(s,a) = \max_\pi \mathbb{E}_\pi \left[ G_t \mid s_t=s, a_t=a \right]. ]

Se você conhece (Q^*), agir de forma ótima é simples: escolher a ação com o maior valor em cada estado.

Equação de Otimalidade de Bellman

A ideia teórica central por trás do aprendizado Q é a equação de otimalidade de Bellman (Bellman optimality equation) para (Q^*): [ Q^*(s,a) = \mathbb{E}\left[r + \gamma \max_{a'} Q^*(s',a') \mid s,a\right]. ]

Ela diz: o valor ótimo de ((s,a)) é igual à recompensa imediata esperada mais o valor ótimo descontado do próximo estado (medido pela melhor próxima ação).

O aprendizado Q usa essa equação como um alvo de aprendizado mesmo quando o agente não conhece as probabilidades de transição.

A Atualização do Aprendizado Q (Controle TD)

Quando o agente vivencia uma transição ((s,a,r,s')), o aprendizado Q realiza a atualização:

[ Q(s,a) \leftarrow Q(s,a) + \alpha \left( r + \gamma \max_{a'} Q(s',a') - Q(s,a) \right), ]

onde:

(\alpha \in (0,1]) é a taxa de aprendizado (learning rate)
o termo entre parênteses é o erro de TD (TD error): [ \delta = r + \gamma \max_{a'} Q(s',a') - Q(s,a). ]

Por que o aprendizado Q é fora da política

Observe que a atualização usa (\max_{a'} Q(s',a')), que corresponde a agir de forma gulosa no próximo estado — mesmo que o agente tenha, na prática, escolhido ações exploratórias. Isso é a marca registrada do aprendizado fora da política: você pode se comportar de acordo com uma política de comportamento (para explorar) enquanto aprende sobre a política gulosa/ótima.

Em contraste, o algoritmo de controle TD na política (on-policy) SARSA usa o valor da próxima ação real (a') executada, em vez do máximo. Essa diferença importa para segurança e comportamento de exploração em alguns ambientes (por exemplo, “caminhada no penhasco (cliff walking)”).

Esboço do Algoritmo (Aprendizado Q Tabular)

Um loop típico de aprendizado Q tabular é:

Initialize Q(s,a) arbitrarily (often zeros)

For each episode:
  Initialize state s
  Repeat until terminal:
    Choose action a using an exploration policy derived from Q (e.g., ε-greedy)
    Take action a, observe reward r and next state s'
    Q(s,a) ← Q(s,a) + α [ r + γ max_a' Q(s',a') − Q(s,a) ]
    s ← s'

Embora a atualização seja simples, o desempenho depende fortemente de como você explora e de como define as taxas de aprendizado.

Estratégias de Exploração

Como o aprendizado Q é fora da política, você pode aprender valores gulosos enquanto se comporta de modo exploratório. A abordagem mais simples e mais comum é a exploração (\varepsilon)-gulosa ((\varepsilon)-greedy).

\(\varepsilon\)-gulosa

Com probabilidade (1-\varepsilon), escolha a ação gulosa; com probabilidade (\varepsilon), escolha uma ação aleatória:

[ a = \begin{cases} \arg\max_{a} Q(s,a) & \text{com prob. } 1-\varepsilon \ \text{ação aleatória} & \text{com prob. } \varepsilon \end{cases} ]

Práticas comuns:

Começar com (\varepsilon) mais alto (por exemplo, 1.0) e reduzir gradualmente (anneal) até um valor pequeno (por exemplo, 0.01–0.1).
Usar cronogramas dependentes do estado (state-dependent) ou dependentes do tempo (time-dependent) para incentivar uma exploração ampla no início.

Outras ideias de exploração (alto nível)

Exploração softmax/Boltzmann (Softmax/Boltzmann exploration): amostrar ações proporcionalmente a (\exp(Q(s,a)/\tau)), onde (\tau) é uma temperatura.
Otimismo diante da incerteza (optimism in the face of uncertainty): inicializar (Q) de forma otimista para incentivar o teste de ações.
Exploração no estilo Limite Superior de Confiança (Upper Confidence Bound, UCB): mais comum em bandits, mas conceitualmente relevante quando você consegue estimar incerteza.
Métodos regularizados por entropia (entropy-regularized methods): mais comuns em famílias baseadas em política como Gradientes de Política, mas representam uma filosofia diferente de exploração.

Convergência e Suposições (Caso Tabular)

No cenário tabular ((\mathcal{S}), (\mathcal{A}) finitos), o aprendizado Q tem garantias clássicas de convergência sob suposições que asseguram exploração suficiente e uma aproximação estocástica (stochastic approximation) estável.

Uma formulação comum é: o aprendizado Q converge para (Q^*) com probabilidade 1 se:

Todos os pares estado–ação são visitados infinitas vezes, normalmente garantido por uma estratégia de exploração que nunca para completamente de explorar (ou segue um cronograma GLIE — ver abaixo).
As taxas de aprendizado satisfazem as condições de Robbins–Monro (Robbins–Monro conditions) para cada ((s,a)): [ \sum_t \alpha_t(s,a) = \infty,\quad \sum_t \alpha_t^2(s,a) < \infty. ] (Intuição: os passos devem ser grandes o suficiente para continuar aprendendo, mas não tão grandes a ponto de o ruído impedir a convergência.)
As recompensas são limitadas e o MDP é estacionário.

GLIE (Ganancioso no Limite com Exploração Infinita)

Uma condição suficiente padrão frequentemente discutida é GLIE (Greedy in the Limit with Infinite Exploration): o comportamento se torna guloso no limite, mas cada ((s,a)) continua sendo explorado infinitas vezes. Uma forma é uma política (\varepsilon_t)-gulosa em que (\varepsilon_t \to 0) lentamente, combinada com taxas de aprendizado adequadas.

Nota prática

Essas garantias valem para aprendizado tabular. Com aproximação de função — especialmente redes neurais — a convergência não é, em geral, garantida, e técnicas de estabilização se tornam cruciais (ver DQN abaixo).

Exemplo Prático: Intuição de Mundo em Grade ou Caminhada no Penhasco

Considere um pequeno mundo em grade (gridworld) em que:

Estados são células da grade.
Ações são cima/baixo/esquerda/direita.
A recompensa é (-1) por passo e (0) no objetivo.

O aprendizado Q inicialmente vagará aleatoriamente ((\varepsilon) alto), coletando recompensas negativas. Ao longo do tempo:

Ele aprende quais ações reduzem o número esperado de passos até o objetivo.
O termo (\max_{a'} Q(s',a')) propaga “boas notícias” para trás: uma vez que o objetivo é encontrado, estados próximos aprendem que uma ação leva mais perto do objetivo; então estados mais distantes aprendem, etc.

Na “caminhada no penhasco” (um exemplo clássico), a natureza fora da política do aprendizado Q tende a aprender o caminho mais curto e arriscado perto do penhasco (porque ele aprende o caminho ótimo guloso), mesmo que o comportamento exploratório às vezes caia do penhasco. O SARSA, por ser na política, pode aprender uma rota mais segura sob exploração persistente.

Tabular vs Aproximação de Função

Aprendizado Q tabular

Use aprendizado Q tabular quando:

O espaço de estados é pequeno e discreto (ou pode ser discretizado de forma razoável).
Você consegue armazenar (Q(s,a)) explicitamente (por exemplo, como uma tabela 2D).

Prós:

Simples, estável sob suposições clássicas
Fácil de depurar e interpretar

Contras:

Não escala para espaços de estados grandes ou contínuos

Aproximação de função

Quando (|\mathcal{S}|) é enorme (ou contínuo), armazene (Q(s,a)) como uma função parametrizada (Q_\theta(s,a)), por exemplo:

Modelos lineares: (Q_\theta(s,a) = \phi(s,a)^\top \theta)
Redes neurais: (Q_\theta(s,a)) produzida por uma rede profunda

O objetivo de aprendizado frequentemente é formulado como minimizar um erro de TD quadrático sobre amostras: [ \min_\theta ; \mathbb{E}\left[\left(r + \gamma \max_{a'} Q_\theta(s',a') - Q_\theta(s,a)\right)^2\right]. ]

A “tríade mortal”

Com aproximação de função, aprendizado fora da política e bootstrapping juntos, podem ocorrer instabilidade e divergência (frequentemente chamado de “tríade mortal (deadly triad)”). Esse é um dos principais motivos pelos quais o aprendizado Q profundo prático usa truques de estabilização.

Redes Q Profundas (DQN) (Alto Nível)

DQN é a extensão de aprendizado profundo do aprendizado Q que tornou viável aprender a partir de observações de alta dimensionalidade, como pixels de jogos Atari. Ela usa uma rede neural para aproximar (Q(s,a)).

As principais ideias de estabilização do DQN:

Repetição de experiência

Em vez de aprender apenas com a transição mais recente, armazene transições em um buffer de repetição (replay buffer) e amostre mini-batches uniformemente (ou com priorização em variantes). Benefícios:

Quebra correlações temporais fortes em dados sequenciais
Melhora a eficiência amostral (sample efficiency) ao reutilizar experiências passadas
Faz o treinamento se parecer mais com aprendizado supervisionado (supervised learning) em batches i.i.d.

Rede-alvo

Usar a mesma rede para computar tanto (Q(s,a)) quanto o alvo (r + \gamma \max_{a'} Q(s',a')) pode criar ciclos de realimentação prejudiciais. O DQN mantém:

Rede online (Q_\theta) (treinada a cada passo)
Rede-alvo (Q_{\theta^-}) (atualizada lentamente/periodicamente)

Alvo: [ y = r + \gamma \max_{a'} Q_{\theta^-}(s',a'). ]

Perda: [ L(\theta) = \mathbb{E}\left[(y - Q_\theta(s,a))^2\right]. ]

Loop de treinamento em alto nível (pseudocódigo ilustrativo)

Initialize replay buffer D
Initialize online network Qθ and target network Qθ- = Qθ

For each step:
  Select action using ε-greedy from Qθ
  Execute action, observe (s, a, r, s')
  Store transition in D
  Sample minibatch from D
  Compute targets using Qθ-
  Gradient step on (target - Qθ(s,a))^2
  Periodically update Qθ- ← Qθ

Variantes comuns de DQN (alto nível)

Muitas melhorias são amplamente usadas na prática:

DQN Duplo (Double DQN): reduz o viés de superestimação (overestimation bias) do operador max ao desacoplar seleção e avaliação de ações.
Redes de duelo (dueling networks): decompõem (Q(s,a)) em um valor de estado e uma vantagem (advantage) para aprender valores de estado de forma mais eficiente.
Repetição de experiência priorizada (prioritized experience replay): amostrar transições mais informativas com mais frequência.
Retornos de N passos (N-step returns): propagar informações de recompensa mais rapidamente do que atualizações TD de 1 passo.
Aprendizado por reforço distribucional (distributional RL): aprender uma distribuição sobre retornos, em vez de apenas a expectativa.

Aplicações Práticas

O aprendizado Q e suas variantes profundas são usados quando:

As ações são discretas (ou podem ser discretizadas)
Você quer um método baseado em valor que possa ser mais simples do que abordagens baseadas em política

Exemplos:

Jogos (por exemplo, Atari com DQN)
Robótica com conjuntos de ações discretas (por exemplo, tomada de decisão em alto nível)
Pesquisa operacional / alocação de recursos (escolhas discretas)
Sistemas de recomendação ou de lances com políticas de decisão discretas (cuidado: não estacionariedade (non-stationarity) e feedback atrasado (delayed feedback) complicam as suposições)

Para espaços de ação contínuos, o aprendizado Q puro é menos direto porque (\arg\max_a Q(s,a)) se torna um problema de otimização contínua. Esse é um dos motivos pelos quais abordagens ator-crítico (actor-critic) são populares nesse caso (ver Métodos Ator-Crítico e métodos de otimização de políticas (policy optimization methods) como Otimização Proximal de Políticas (Proximal Policy Optimization, PPO)).

Um Exemplo Mínimo de Aprendizado Q Tabular (Python)

Abaixo está um pequeno trecho ilustrativo para uma interface de ambiente discreto (semelhante a APIs no estilo Gymnasium). Ele omite muitos detalhes (tratamento de término de episódio, cronogramas de decaimento adequados, etc.), mas mostra a atualização central.

import numpy as np

n_states = 100
n_actions = 4

Q = np.zeros((n_states, n_actions))
alpha = 0.1
gamma = 0.99
epsilon = 0.1

def epsilon_greedy_action(s):
    if np.random.rand() < epsilon:
        return np.random.randint(n_actions)
    return int(np.argmax(Q[s]))

for episode in range(1000):
    s = env.reset()  # discrete state index
    done = False
    while not done:
        a = epsilon_greedy_action(s)
        s2, r, done, info = env.step(a)

        td_target = r + (0.0 if done else gamma * np.max(Q[s2]))
        td_error = td_target - Q[s, a]
        Q[s, a] += alpha * td_error

        s = s2

Detalhe-chave de implementação: quando done é true (estado terminal), normalmente não fazemos bootstrapping a partir de (Q(s',\cdot)).

Hiperparâmetros e Dicas Práticas

Parâmetros comuns e efeitos típicos:

Taxa de aprendizado (\alpha): grande demais pode desestabilizar; pequena demais desacelera o aprendizado.
Desconto (\gamma): valores mais altos enfatizam recompensa de longo prazo, mas podem aumentar a variância e tornar mais lenta a atribuição de crédito.
Exploração (\varepsilon): exploração insuficiente pode fixar um comportamento subótimo cedo.
Escalonamento/recorte de recompensas (reward scaling/clipping) (comum em DQN): pode melhorar a estabilidade, mas pode distorcer objetivos; use com critério.
Tamanho do buffer de repetição (DQN): pequeno demais reduz diversidade; grande demais pode incluir dados obsoletos em cenários não estacionários.
Período de atualização da rede-alvo (DQN): atualizações frequentes podem desestabilizar; pouco frequentes tornam o aprendizado mais lento.

Pontos Fortes e Limitações

Pontos fortes

Conceitualmente simples e amplamente aplicável em MDPs com ações discretas
Aprendizado fora da política permite reutilização de experiência (especialmente com buffers de repetição)
Forte baseline e bloco de construção para muitos sistemas de aprendizado por reforço

Limitações

A forma tabular não escala para espaços de estados grandes/contínuos
Com aproximação de função, pode ser instável sem projeto cuidadoso
O operador max pode introduzir viés de superestimação (abordado por DQN Duplo e métodos relacionados)
Menos natural para espaços de ação contínuos em comparação com métodos ator-crítico e baseados em política (ver Gradientes de Política)

Resumo

O aprendizado Q é um algoritmo clássico de controle TD sem modelo e fora da política (off-policy, model-free TD control) que aprende uma aproximação da função valor-ação ótima (Q^*) via o princípio de otimalidade de Bellman (Bellman optimality principle). Em problemas discretos pequenos, o aprendizado Q tabular pode convergir sob condições padrão de aproximação estocástica e exploração. Para problemas em grande escala, o DQN estende a ideia com redes neurais e técnicas cruciais de estabilização como repetição de experiência e redes-alvo, possibilitando aprendizado prático a partir de entradas de alta dimensionalidade.

Apesar do avanço de métodos baseados em política e ator-crítico, o aprendizado Q permanece uma parte central do ferramental de aprendizado por reforço — tanto como um algoritmo quanto como uma ideia organizadora para tomada de decisão baseada em valor.