Resumo Técnico: Aprendizado por Reforço com Observações Acionadas por Ação

1. Definição do Problema

O artigo aborda uma classe específica de Processos de Decisão de Markov Parcialmente Observáveis (POMDPs) onde a disponibilidade das observações de estado não é exógena ou fixa, mas sim acionada por ação. No RL padrão, um agente observa o novo estado após cada ação. Em muitos cenários práticos (ex: diagnósticos clínicos, negociação financeira), obter uma observação de estado é custoso, não confiável ou requer uma ação específica para ser acionado.

Os autores formalizam este cenário como Processos de Decisão de Markov com Rastreabilidade Esporádica Acionada por Ação (ATST-MDPs).

• Mecanismo: Quando um agente no estado $s$ executa a ação $a$, ele recebe uma recompensa e o ambiente transita para $s'$. Crucialmente, $s'$ nem sempre é observado. Com probabilidade $\beta(a)$, ocorre um "evento de observação" (rajada de dados), revelando $s'$ e a recompensa cumulativa desde a última rajada. Com probabilidade $1-\beta(a)$, nenhuma retroalimentação de estado é fornecida.
• Desafio: O agente deve otimizar simultaneamente a política de controle e decidir quando acionar observações (escolhendo ações com $\beta(a)$ mais alto) para reduzir a incerteza, equilibrando o custo da aquisição de informação contra o desempenho do controle.
• Distinção: Diferente dos POMDPs padrão, onde as observações são ruidosas mas frequentes, ou do RL com atrasos exógenos onde a retroalimentação é apenas tardia, os ATST-MDPs apresentam atrasos endógenos, onde as escolhas de ação do agente determinam diretamente a frequência da revelação do estado.

2. Metodologia

2.1 Espaço de Estado Aumentado e Equações de Bellman

Para lidar com a observabilidade parcial, os autores definem um espaço de estado aumentado $\mathcal{X} = \mathcal{S} \times \mathcal{A}^{<\infty}$. Um estado aumentado $x = (s_1, a_1, \dots, a_n)$ consiste no último estado observado $s_1$ e na sequência de ações tomadas desde essa observação.

• Suficiência: O estado aumentado serve como um estatístico suficiente para o histórico, permitindo que o problema seja tratado como um MDP totalmente observado em $\mathcal{X}$.
• Dinâmica: A transição em $\mathcal{X}$ é uma mistura: com probabilidade $\beta(a)$, o estado reseta para o novo estado observado $s'$; com probabilidade $1-\beta(a)$, a sequência de ações é anexada ($x \leftarrow x \cdot a$).
• Equações de Bellman: Os autores derivam equações de optimalidade de Bellman para funções de valor $V^\pi$ e $Q^\pi$ neste espaço aumentado, provando a existência de uma política aumentada ótima $\pi^*$.

2.2 Reformulação de Sequência de Ações

Reconhecendo que o espaço de estado aumentado ramifica-se infinitamente, os autores propõem uma reformulação baseada na estrutura de renovação das rajadas de dados. Em vez de decidir ação por ação, o agente se compromete com uma sequência de ações $a \in \mathcal{A}^\mathbb{N}$ em cada rajada de dados, executando-a até que a próxima observação ocorra.

• Isso transforma o problema em um processo de decisão sobre $(\mathcal{S}, \mathcal{A}^\mathbb{N})$.
• A função de valor $K^\pi(s, a)$ representa a recompensa descontada esperada acumulada a partir do estado $s$ ao executar a sequência $a$ até a próxima rajada de dados, mais o valor de continuação do estado revelado.

2.3 Representação Linear sob a Suposição de MDP Linear

Para tornar tratável o espaço de sequência de ações de dimensão infinita, o artigo assume uma estrutura de MDP Linear (Suposição 4.1), onde os núcleos de transição e recompensas são lineares em um mapa de características $\phi(s, a)$.

• Insight Chave: Sob esta suposição, a função de valor da sequência de ações $K^\pi$ admite uma representação linear em um mapa de características de dimensão finita $\psi: \mathcal{S} \times \mathcal{A}^\mathbb{N} \to \mathbb{R}^{2d}$.
• Construção: O mapa de características $\psi$ é construído usando matrizes de ação $M_a$ (derivadas da dinâmica de transição) e probabilidades de observação $\beta_a$. Especificamente, $\psi$ codifica a evolução das características ao longo da sequência de ações e a probabilidade de ocorrência de rajadas de dados em cada etapa.
• Resultado: $K^\pi(s, a) = \langle \psi(s, a), v^\pi_{1,2} \rangle$, onde $v^\pi_{1,2}$ é um vetor dependente da política. Isso permite o uso de métodos padrão baseados em regressão, apesar do espaço de ações infinito.

2.4 Estimativa e Algoritmo de Aprendizado

O artigo propõe o ATST-LSVI-UCB (Iteração de Valor de Mínimos Quadrados com Limites Superiores de Confiança para Estados de Rastreabilidade Esporádica Acionada por Ação).

• Estimativa de Características: Como o verdadeiro mapa de características $\psi$ é desconhecido, o algoritmo estima as matrizes de ação subjacentes $M_a$ e as probabilidades de observação $\beta_a$ a partir de dados exploratórios usando regressão de ridge e médias empíricas. O Teorema 4.6 e o Corolário 4.9 fornecem limites de complexidade de amostra não assintóticos para construir uma aproximação $\epsilon$-admissível de $\psi$.
• Algoritmo: O algoritmo opera em episódios com horizontes geométricos. Ele realiza iteração de valor para trás (backward value iteration) no mapa de características estimado para calcular estimativas de valor otimistas (usando bônus UCB) e executa sequências de ações gananciosas.
• Otimização: Embora o espaço de ações seja infinito, a otimização $\max_a K(s, a)$ é realizada sobre a imagem compacta do mapa de características. Na prática, isso pode ser aproximado restringindo-se a sequências de profundidade finita ou eventualmente periódicas.

3. Principais Contribuições

1. Formalização de ATST-MDPs: Um novo framework para RL onde a disponibilidade de observação é uma função da ação escolhida, unindo o gap entre POMDPs padrão e gerais.
2. Fundamentos Teóricos: Derivação de equações de Bellman no espaço de estado aumentado e prova da existência de política ótima.
3. Representação Linear: Demonstração de que, sob a suposição de MDP linear, a função de valor sobre sequências de ações é linear em um mapa de características de dimensão finita, permitindo aprendizado eficiente.
4. Algoritmo e Limites de Regret: Proposta do ATST-LSVI-UCB, um algoritmo de iteração de valor otimista. Os autores provam um limite de regret de $\tilde{O}(\sqrt{d^3 K (1-\gamma)^{-3}})$ para aprendizado episódico, correspondendo à taxa ótima conhecida para MDPs lineares totalmente observáveis.
5. Complexidade de Amostra: Estabelecimento de garantias de complexidade de amostra para estimar o mapa de características da sequência de ações a partir de dados, mostrando que é polinomial na dimensão $d$ e independente do tamanho do espaço de estados $|\mathcal{S}|$.

4. Resultados

• Teóricos: O limite de regret corresponde ao estado da arte para MDPs lineares com observabilidade total, apesar da complexidade adicional de observabilidade parcial e atrasos acionados por ação. O limite escala com a dimensão de característica $d$, número de episódios $K$ e o inverso do fator de desconto $(1-\gamma)$.
• Empíricos: Experimentos em dois ambientes tabulares, RiverSwim (focado em exploração) e RiverBalance (focado em estabilização), demonstram a viabilidade do algoritmo.
  • Em RiverSwim, observações esparsas (baixo $\beta$) surpreendentemente aceleraram a convergência ao incentivar compromissos de malha aberta mais longos (exploração).
  • Em RiverBalance, observações frequentes (alto $\beta$) renderam maiores recompensas, pois a tarefa exigia correções dependentes do estado para manter a estabilidade.
  • Os resultados destacam que a frequência ideal de observação é dependente da tarefa.

5. Significância e Alegações

O artigo afirma fornecer uma fundação teórica para aprendizado por reforço em ambientes com observações de estado acionadas por ação. Sua significância reside em:

• Preenchimento de Lacunas: Aborda uma classe de POMDPs especificamente relevante na prática (percepção ativa, sensores de alto custo) que métodos gerais de POMDP têm dificuldade em lidar devido à intratabilidade computacional.
• Tratabilidade: Ao aproveitar a estrutura de renovação induzida pelas rajadas de dados e a suposição de MDP linear, transforma um problema de observabilidade parcial intratável em um problema de regressão linear tratável.
• Otimalidade: Alcança taxas de regret comparáveis a configurações totalmente observáveis, sugerindo que o "custo" da observabilidade esporádica pode ser mitigado se o mecanismo de observação for compreendido e aproveitado.
• Estimativa Livre de Recompensa: A estimativa do mapa de características é livre de recompensa, o que significa que o aprendizado estrutural do ambiente (dinâmicas e probabilidades de observação) pode ser desacoplado da função de recompensa específica, permitindo uma adaptação de política flexível.

Os autores observam que trabalhos futuros devem focar no design de esquemas de aproximação eficientes para a otimização de sequências de ações infinitas e no desenvolvimento de algoritmos totalmente online que refinem adaptativamente as estimativas de características sem dados exploratórios pré-coletados.