A Finite-Iteration Theory for Asynchronous Categorical Distributional Temporal-Difference Learning

Resumo Técnico: Uma Teoria de Iteração Finita para Aprendizado Temporal-Diferencial Distribucional Categórico Assíncrono

Declaração do Problema
Avanços recentes no aprendizado por reforço (RL) distribucional estabeleceram garantias assintóticas robustas para métodos de avaliação de políticas categóricas, especificamente o aprendizado temporal-diferencial categórico escalar (CTD) na métrica de Cramér e o aprendizado temporal-diferencial categórico sinalizado multivariado (MTD) na métrica de discrepância máxima de média (MMD). No entanto, análises não assintóticas (de iteração finita) existentes focam majoritariamente em atualizações de estado completo síncronas, modelos generativos ou substitutos idealizados. Em configurações práticas de RL online, o aprendizado TD categórico padrão opera de forma assíncrona: realiza atualizações de estado único em cada iteração impulsionadas por uma trajetória markoviana. Isso cria uma lacuna teórica entre a teoria assintótica estabelecida e o comportamento de iteração finita das recursões exatas utilizadas na prática. Este artigo aborda essa lacuna fornecendo garantias de iteração finita para CTD e MTD assíncronos sob regimes de horizonte fixo com e sem desconto.

Metodologia
Os autores fecham a lacuna entre atualizações assíncronas práticas e a teoria de aproximação estocástica (SA) de iteração finita através de um quadro unificado baseado em embeddings isométricos estado a estado e geometria de supremo de bloco.

1. Embeddings Isométricos e Contração:

   • Para CTD, os autores utilizam a métrica de Cramér e um embedding isométrico de massa cumulativa ($I_C$). Isso transforma o operador de Bellman projetado em uma contração em uma norma de supremo de bloco ($\|\cdot\|_{2,\infty}$) com módulo $\sqrt{\gamma}$ (com desconto) ou uma contração ponderada (horizonte fixo).
   • Para MTD, eles empregam a métrica MMD com um kernel característico e um embedding de matriz de Gram ($I_M$). Isso converte similarmente o mapa de Bellman projetado em uma contração na geometria MMD de supremo de bloco, com módulo $\gamma^{c/2}$ (com desconto) ou uma contração ponderada (horizonte fixo).

2. Formulação de Aproximação Estocástica (SA) Assíncrona:

   • A regra padrão de atualização de estado único é reescrita como uma recursão de SA assíncrona: $U_{k+1} = U_k + \alpha_k P_{S_k}(\hat{T}(U_k; S_k, \xi_k) - U_k(S_k))$.
   • A análise baseia-se em quadros abstratos de iteração finita para recursões contrativas sob amostragem i.i.d. e markoviana (construindo sobre Chen et al., Robbins-Monro e Borkar).
   • Geometria de Perturbação: Uma distinção crítica é feita entre as estruturas de ruído dos dois métodos. O CTD opera em um regime de ruído limitado devido ao suporte limitado das distribuições categóricas e à geometria de Cramér. Em contraste, o MTD opera em um regime de perturbação afim porque a projeção categórica sinalizada é afim e não uniformemente limitada, levando a limites de perturbação que escalonam com a norma da iteração atual.

3. Regimes Analisados:

   • Avaliação de Política com Desconto: Analisada sob amostragem i.i.d. (replay/modelo generativo) e amostragem de trajetória markoviana (RL online padrão). O caso markoviano incorpora limites de tempo de mistura geométrica.
   • Avaliação de Horizonte Fixo sem Desconto: Analisada para tarefas episódicas com um horizonte fixo $H$. Como não há fator de desconto $\gamma < 1$ para impulsionar a contração, os autores introduzem uma métrica de bloco ponderada ($\lambda^h$) através da pilha do horizonte. Isso recupera uma propriedade de contração onde o horizonte $h$ faz bootstrap a partir de $h-1$. A análise é realizada nas fronteiras dos episódios para lidar com a deriva dependente da fase dentro de um episódio.

Principais Contribuições

1. Garantias de Iteração Finita para CTD e MTD Assíncronos: O artigo estabelece taxas de convergência não assintóticas explícitas para as recursões assíncronas padrão de ambos CTD e MTD. Esta é a primeira teoria desse tipo para esses métodos específicos sob atualizações de estado único impulsionadas por trajetória.
2. Quadro Unificado para Cenários com Desconto e Horizonte Fixo: Os autores fornecem um tratamento teórico coerente que cobre tanto problemas com desconto (com amostragem i.i.d. e markoviana) quanto problemas de horizonte fixo sem desconto (sob amostragem episódica i.i.d.).
3. Decomposição Determinística do Erro de Representação: O artigo registra uma decomposição que separa o erro total em um termo algorítmico (controlado pelos limites de iteração finita) e um termo de viés de projeção determinístico (dependente da família de suporte categórico). Isso permite que a análise de SA e o viés de discretização sejam analisados independentemente.
4. Constantes Explícitas e Regimes de Tamanho de Passo: A análise fornece constantes explícitas para três regimes de tamanho de passo:
   • Tamanho de passo constante: Convergência geométrica para uma vizinhança $O(\alpha)$.
   • Tamanho de passo diminuído linearmente: Decaimento residual de $O(1/k)$ (erro quadrático), implicando complexidade de amostra de $O(\epsilon^{-2})$ para erro médio $\epsilon$.
   • Tamanho de passo diminuído polinomialmente: Decaimento de $O(1/k^z)$, trocando a taxa de convergência por condições de admissibilidade mais brandas.

Resultados

• Regime com Desconto: Para ambos CTD e MTD, sob amostragem i.i.d., o erro quadrático converge a uma taxa de $O(1/k)$ com tamanhos de passo diminuídos linearmente. Sob amostragem markoviana, a taxa é $\tilde{O}(1/k)$, incorrendo em um sobrecusto logarítmico devido ao tempo de mistura da cadeia de Markov subjacente.
• Regime de Horizonte Fixo: Para tarefas episódicas sem desconto, o erro nas fronteiras dos episódios converge a taxas análogas ao caso com desconto. Especificamente, convergência de $O(1/m)$ para erro quadrático após $m$ episódios (equivalente a $O(\epsilon^{-2})$ transições).
• Regimes de Ruído: Os resultados confirmam que o CTD beneficia-se de ruído uniformemente limitado, enquanto o MTD requer o tratamento de limites de ruído afins, o que introduz constantes adicionais relacionadas à norma da iteração nas garantias de convergência.

Significado e Alegações
O artigo alega fechar uma lacuna teórica significativa entre a compreensão assintótica do RL distribucional e as atualizações práticas, assíncronas e de estado único usadas em implementações. Ao demonstrar que as recursões categóricas padrão constituem esquemas de SA assíncronos com estruturas contrativas em embeddings adequados, os autores permitem um controle rigoroso de iteração finita.

Os autores observam modestamente o escopo de seu trabalho:

• A teoria é limitada a avaliação de políticas tabulares e de estado finito e não aborda controle ou melhoria de política.
• As garantias são limites de expectativa e não limites de alta probabilidade.
• Os resultados aplicam-se às recursões assíncronas exatas usadas na prática, distinguindo-as de trabalhos anteriores que analisaram substitutos síncronos ou baseados em modelo.

O trabalho estabelece que, uma vez que CTD e MTD são formulados com os embeddings estado a estado apropriados, suas regras de atualização possuem as propriedades estruturais necessárias (contração, continuidade de Lipschitz e perturbação controlada) para serem analisadas usando ferramentas modernas de SA não assintótica, fornecendo a primeira teoria de iteração finita para esses métodos distribucionais amplamente utilizados em configurações online realistas.