Resumo Técnico: Bootstrap Baseado em Modelo de Cadeias de Markov Controladas

Formulação do Problema

O artigo aborda o desafio da inferência estatística para Cadeias de Markov Controladas (CMCs) finitas em cenários onde a política de comportamento que gera os dados pode ser não estacionária ou dependente do histórico. Este cenário é prevalente no aprendizado por reforço (RL) offline, onde os dados são coletados por uma política desconhecida $\pi_b$ que não necessariamente satisfaz as suposições de estacionariedade ou markovianidade.

Os métodos de bootstrap existentes para cadeias de Markov frequentemente dependem de estacionariedade ou condições específicas de mistura que não se aplicam a CMCs gerais com controles dependentes do histórico. Além disso, intervalos de confiança (ICs) padrão de plug-in baseados em Teoremas do Limite Central (TLCs) exigem estimação de covariância, o que pode degradar o desempenho em amostras finitas. Os autores identificam dois problemas em aberto:

1. É possível desenvolver um bootstrap baseado em modelo para CMCs finitas sem exigir estacionariedade ou markovianidade da política de controle?
2. É possível estabelecer a consistência distribucional de tal estimador de bootstrap e estendê-lo a tarefas de RL subsequentes, como Avaliação Fora de Política (OPE) e Recuperação de Política Ótima (OPR)?

Metodologia

Configuração do Modelo e dos Dados

Os autores consideram uma CMC finita $\{(X_i, A_i)\}_{i \ge 0}$ com espaço de estados $\mathcal{S}$ e espaço de ações $\mathcal{A}$. O núcleo de transição é $M(a)_{s,t} = P(X_{i+1}=t | X_i=s, A_i=a)$. O conjunto de dados offline observado $\mathcal{D}_n$ consiste em $K$ episódios de comprimento fixo $T$ (onde $n=KT$), gerados por uma política de comportamento desconhecida $\pi_b$. A política $\pi_b$ é permitida ser não estacionária e dependente do histórico.

A partir de $\mathcal{D}_n$, os autores calculam:

• Estimador empírico de transição baseado em contagem: $\hat{M}(a)_{s,t} = N(a)_{s,t} / N(a)_s$.
• Política de comportamento empírica: $\hat{\pi}_b(a|s) = N(a)_s / N_s$.

Procedimento de Bootstrap Baseado em Modelo

O método proposto constrói uma CMC de bootstrap $\{(X^*_i, A^*_i)\}_{i \ge 0}$ usando o núcleo de transição empírico $\hat{M}$ e a política de comportamento empírica $\hat{\pi}_b$.

1. Inicialização: Para cada réplica de bootstrap $j$, o processo inicia no estado inicial observado do episódio original, $X^{*(k,j)}_0 = X^{(k)}_0$.
2. Simulação: As transições são geradas sequencialmente amostrando ações $A^{*(k,j)}_i \sim \hat{\pi}_b(\cdot | X^{*(k,j)}_i)$ e próximos estados $X^{*(k,j)}_{i+1} \sim \hat{M}(A^{*(k,j)}_i)_{X^{*(k,j)}_i, \cdot}$.
3. Estimação: A partir do conjunto de dados simulado $\mathcal{D}^*_n$, um estimador de transição de bootstrap $\hat{M}^*$ é computado.
4. Replicação: Este processo é repetido $B$ vezes para obter réplicas de bootstrap $\hat{M}^{*(1)}, \dots, \hat{M}^{*(B)}$.

Aplicações Subsequentes

O bootstrap é aplicado a dois alvos subsequentes:

• Avaliação Fora de Política (OPE): Estimação de funções valor $V_\pi$ e funções Q $Q_\pi$ para uma política alvo fixa $\pi$ resolvendo equações de Bellman com $\hat{M}$ e $\hat{M}^*$.
• Recuperação de Política Ótima (OPR): Estimação de funções valor ótimas $V_\star$ e $Q_\star$ resolvendo equações de Bellman ótimas com $\hat{M}$ e $\hat{M}^*$.

Intervalos de confiança são construídos usando os quantis empíricos das réplicas de bootstrap (IC percentil) ou via métodos de pivô.

Principais Contribuições Teóricas

1. Consistência Distribucional do Bootstrap

O artigo estabelece os primeiros resultados de consistência distribucional para bootstraps baseados em modelo em CMCs finitas com políticas potencialmente não estacionárias ou dependentes do histórico.

• Regime de Cadeia Única ($K=1, T \to \infty$): O Teorema 1 prova que, condicionado aos dados $\mathcal{D}_n$, $\sqrt{n} \text{vec}(\hat{M}^* - \hat{M})$ converge em distribuição para um limite Gaussiano $N(0, \bar{\Lambda})$, correspondendo à distribuição assintótica do estimador original $\sqrt{n} \text{vec}(\hat{M} - M)$.
• Regime Episódico ($T$ fixo, $K \to \infty$): A Proposição 1 estende este resultado ao cenário episódico incorporando os episódios em uma única cadeia via pseudo-transições. Confirma-se que o bootstrap permanece consistente mesmo quando os episódios são separados por reinicializações.

Ferramentas Técnicas:

• Uma nova Lei dos Grandes Números (LGN) de Bootstrap para contagens de visitação ($N^*_s/n \to p_s$ q.c.).
• Uma nova aplicação do Teorema do Limite Central (TLC) de Martingala para incrementos de transição de bootstrap, utilizando condições de mistura fraca (Suposições 1–3) para lidar com a estrutura de dependência.

2. Validade para OPE e OPR

A Proposição 2 estende a consistência distribucional para os estimadores de função valor e função Q usando o Método Delta.

• Os autores verificam a diferenciabilidade de Hadamard dos operadores de Bellman em relação à matriz de blocos de transição.
• Para OPE, as réplicas de bootstrap de $V_\pi$ e $Q_\pi$ convergem para os mesmos limites Gaussianos que os estimadores originais.
• Para OPR, sob uma condição de não degeneração (lacuna estritamente positiva entre ações ótimas e subótimas), as réplicas de bootstrap de $V_\star$ e $Q_\star$ também alcançam consistência distribucional.

Resultados Experimentais

Os autores avaliam o desempenho em amostras finitas no problema RiverSwim ($S=6, A=2$), um benchmark conhecido por exploração difícil devido a frequências de visitação desbalanceadas e políticas ótimas quase degeneradas.

• Configuração: Comparações foram feitas contra o bootstrap episódico (Hao et al., 2021) e ICs de plug-in baseados em TLC (Zhu et al., 2024; Su et al., 2026) em vários tamanhos de amostra ($n$) e comprimentos de episódio ($T$).
• Descobertas:
  • Os ICs percentil de bootstrap baseados em modelo propostos superam substancialmente as linhas de base, alcançando cobertura próxima à nominal (por exemplo, 0,48–0,54 para 50%, 0,87–0,94 para 90%, 0,92–0,97 para 95%) em regimes bem amostrados ($n \ge 500$).
  • As linhas de base (bootstrap episódico e TLC de plug-in) exibem subcobertura sistemática, particularmente em tamanhos de amostra pequenos e comprimentos de episódio curtos.
  • O bootstrap episódico falha completamente em $n=50$ quando $T \ge 50$ (colapsando para cobertura zero) porque um único episódio elimina a variação de bootstrap.
  • O desempenho é mais fraco para pares estado-ação raramente visitados (perto do estado 6) e horizontes curtos ($T=10$), consistente com as restrições teóricas de normalidade assintótica e não degeneração.

Significado e Limitações

Significado:
O artigo fornece uma base teórica rigorosa para o uso de bootstraps baseados em modelo em RL offline, abordando especificamente a lacuna onde as políticas de comportamento são não estacionárias ou dependentes do histórico. Demonstra que tais bootstraps produzem intervalos de confiança assintoticamente válidos tanto para núcleos de transição quanto para alvos de RL subsequentes, sem exigir estimação explícita de covariância.

Limitações e Direções Futuras (conforme declarado pelos autores):

• Função de Recompensa: A análise assume uma função de recompensa conhecida. Embora os autores notem que a validade provavelmente se mantiver se a estimativa de recompensa convergir, os efeitos em amostras finitas do erro de estimação de recompensa não são analisados.
• Espaço Estado-Ação: Os resultados atuais são limitados a espaços estado-ação finitos. A extensão para aproximação de função ou espaços contínuos é deixada para trabalhos futuros.
• Regimes Assintóticos: A análise episódica assume que $T$ é fixo e $K \to \infty$. A consistência do bootstrap no regime onde $K$ é fixo ($K>1$) e $T \to \infty$ permanece uma questão em aberto.
• Políticas Não Estacionárias: Embora a teoria acomode políticas não estacionárias, os experimentos numéricos utilizaram principalmente políticas de comportamento estacionárias; experimentos adicionais com políticas não estacionárias são sugeridos.