Resumo Técnico: Auto-exploração para Aprendizado por Reforço Online

Definição do Problema

O artigo aborda o dilema fundamental entre exploração e explotação no Aprendizado por Reforço (RL) on-policy para Processos de Decisão de Markov (MDPs) de horizonte infinito e desconto, com espaços de estados e ações finitos. Especificamente, ele foca no cenário on-policy, onde os dados são gerados por uma única trajetória de uma cadeia de Markov, em vez de um modelo generativo ou lote offline.

Os algoritmos de estado da arte atuais frequentemente dependem de duas suposições problemáticas para garantir a convergência:

1. Exploração Suficiente: Eles assumem que cada ação pode ser selecionada com uma probabilidade maior que zero para qualquer estado (frequentemente imposta via exploração $\epsilon$-greedy explícita). No entanto, em configurações on-policy não regularizadas, políticas ótimas podem ser determinísticas, fazendo com que essa suposição falhe.
2. Parâmetros Dependentes do Algoritmo: Os limites de complexidade de amostra existentes frequentemente dependem de parâmetros como o tempo de mistura (mixing time) e a distribuição estacionária das cadeias de Markov induzidas pelas políticas intermediárias. Esses parâmetros são desconhecidos na prática e podem ser arbitrariamente grandes, levando a algoritmos subótimos ou não implementáveis.

O artigo busca desenvolver métodos livres de parâmetros que alcancem uma complexidade de amostra $O(\epsilon^{-2})$ independente do algoritmo, sem exigir conhecimento prévio de taxas de mistura ou distribuições estacionárias, evitando também a subotimalidade de cronogramas de exploração explícitos.

Metodologia

Os autores introduzem uma nova classe de métodos chamada Auto-exploração (Auto-exploration), integrada ao Stochastic Policy Mirror Descent (SPMD). A ideia central é explorar automaticamente tanto o espaço de estados quanto o de ações através de mecanismos baseados em dados, em vez de hiperparâmetros fixos.

1. Fundamentação Teórica: Novos Garantias de Convergência

Os autores estabelecem, primeiramente, novas garantias de convergência de última iteração (last-iterate) de alta probabilidade para o SPMD. Diferente de trabalhos anteriores que focam na convergência de média de iterações ou da melhor iteração, esta análise garante que a política final esteja próxima da ótima.

• Suposições: A análise exige apenas que a função Q seja limitada e que o estimador estocástico possua um pequeno viés ponderado e momentos de segunda ordem limitados.
• Técnica: A prova utiliza um novo agrupamento de iterações e uma nova análise da divergência de Bregman adaptada ao fator de desconto $\gamma$, melhorando os limites anteriores por um fator de $O((1-\gamma)^{-2})$.

2. Cenário Tabular: Tempo de Exploração Dinâmico

Para o caso tabular, os autores propõem um tempo de exploração dinâmico para substituir o tempo de mistura desconhecido.

• Truncated On-Policy Monte Carlo (TOMC): Eles utilizam um estimador truncado para a função Q. Se um par estado-ação não for visitado dentro de um determinado tempo, ele recebe um valor alto para desencorajar sua seleção.
• Parada Dinâmica: Em vez de um horizonte de exploração fixo, o algoritmo executa por uma duração determinada pelo primeiro tempo de atingimento (first hitting time) de pares estado-ação. Este tempo é aleatório e baseado em dados.
• Exploração Implícita: O método baseia-se na existência de uma política determinística ótima que induz uma cadeia de Markov irredutível. Sob essa suposição, os autores provam que a política explora naturalmente estados "difíceis de alcançar" (exploração de estado implícita) sem a necessidade de randomização explícita.

3. Aproximação de Função Linear: Nova Distribuição de Amostragem

Para o cenário de aproximação de função linear, os autores abordam a dificuldade de amostrar a partir da distribuição estacionária desconhecida.

• Distribuição de Visitação Descontada: Eles propõem uma nova distribuição de amostragem baseada na distribção de visitação de estados descontada ($\kappa^\pi_{s_{or}}$) partindo de um estado de origem arbitrário, em vez da distribuição estacionária. Esta distribuição é sempre bem definida e não requer a estimativa de tempos de mistura.
• Diferenciação Temporal Condicional (CTD): O algoritmo constrói um operador estocástico usando uma estratégia de amostragem de duas fases:
  1. Exploração de Estado: Utiliza uma política perturbada $\tilde{\pi}^{(S)}$ para alcançar um estado de origem fixo $s_{or}$.
  2. Exploração de Ação: Uma vez em $s_{or}$, alterna para a política atual $\pi$ (com exploração de ação opcional $\tilde{\pi}^{(A)}$) por um número de passos geometricamente distribuído.
• Tratamento de Viés: O método distingue entre casos onde o erro de aproximação de função é conhecido (exploração implícita suficiente) versus desconhecido (exigindo exploração explícita para mitigar o viés).

Principais Contribuições

1. Complexidade de Amostra $O(\epsilon^{-2})$ Independente do Algoritmo: O artigo apresenta o primeiro algoritmo baseado em SPMD para RL on-policy online que alcança complexidade de amostra $O(\epsilon^{-2})$ tanto em cenários tabulares quanto de aproximação de função linear. Crucialmente, o limite de complexidade depende de constantes específicas do problema (como a taxa de mistura da política ótima), mas é independente de parâmetros dependentes do algoritmo (como as taxas de mistura de políticas intermediárias).
2. Implementação Livre de Parâmetros: Os métodos propostos não exigem conhecimento prévio de tempos de mistura, distribuições estacionárias ou outras constantes dependentes do problema. Eles utilizam tempos de exploração dinâmica derivados de observações em tempo real (tempos de atingimento).
3. Convergência de Última Iteração de Alta Probabilidade: Os autores fornecem garantias rigorosas de convergência de alta probabilidade para a última iteração do SPMD, uma garantia mais forte do que os limites de média de iterações ou de regret comuns na literatura anterior.
4. Nova Distribuição de Amostragem: Na configuração de aproximação de função, a introdução de uma distribuição de amostragem baseada na distribuição de visitação descontada cobre uma classe mais geral de cadeias de Markov do que aquelas que dependem de distribuições estacionárias.

Resultados

• Cenário Tabular: O algoritmo alcança precisão $\epsilon$ com probabilidade $1-\delta$ usando no máximo $\tilde{O}(D_{expl}(\delta) \cdot |A|^{2-\frac{1}{2}+\log_2(1/[1-\gamma])} (1-\gamma)^{-5} \epsilon^{-2})$ amostras. Aqui, $D_{expl}(\delta)$ é uma constante independente do algoritmo relacionada às propriedades de mistura da política ótima.
• Aproximação de Função: Um limite de complexidade de amostra semelhante é estabelecido para o cenário linear. A análise revela um compromisso (trade-off): se o erro de aproximação de função for desconhecido, a exploração explícita é necessária para garantir a convergência; se conhecido, a exploração implícita é suficiente.
• Melhoria sobre o Estado da Arte: A complexidade de amostra melhora os limites de exploração implícita anteriores (ex: [37]) por um fator de $O(|A|^{1/2}/(1-\gamma))$ e remove a dependência de taxas de mistura específicas do algoritmo.

Significância e Alegações

O artigo afirma resolver um problema de longa data: alcançar complexidade de amostra $O(\epsilon^{-2})$ on-policy e independente do algoritmo para RL descontado com estados e ações finitos sem cronogramas de exploração explícitos.

• Praticidade: Ao eliminar a necessidade de ajustar hiperparâmetros baseados em taxas de mistura ou distribuições estacionárias desconhecidas, os métodos são "simples de implementar" e robustos.
• Rigor Teórico: O trabalho une as garantias teóricas à implementação prática ao fornecer limites não assintóticos que se aplicam à última iteração, que é o resultado real do algoritmo.
• Novidade: O conceito de "auto-exploração" via tempos de parada dinâmica e o uso de distribuições de visitação descontadas para amostragem são apresentados como contribuições inovadoras que avançam a compreensão da exploração em RL on-policy.

Os autores posicionam este trabalho como um passo para tornar algoritmos de RL eficientes implementáveis em cenários do mundo real, onde a dinâmica do ambiente (e, portanto, as propriedades de mistura) é desconhecida.