Resumo Técnico: Aprendizado em Bandidos Markovianos com Estados Não Observáveis e Épocas de Decisão Restritas

1. Definição do Problema

Este artigo aborda o problema da minimização do arrependimento (regret) em bandidos markovianos sob duas restrições específicas:

1. Estados Não Observáveis: O controlador não observa o estado interno dos braços (cadeias de Markov). O único feedback disponível é a recompensa gerada pelo braço ativado. Isso corresponde a um cenário de "feedback de bandido total" (full bandit feedback), onde o espaço de estados é oculto.
2. Épocas de Decisão Restritas: O controlador não pode alternar braços arbitrariamente a cada passo de tempo. Em vez disso, a alternância só é permitida em épocas de decisão ($\tau_i$) específicas, que são tempos de parada determinados pelo fluxo de recompensas. Especificamente, o controlador deve permanecer comprometido com um braço até que um sinal específico (por exemplo, uma recompensa não nula) seja recebido.

Os braços são modelados como Processos de Decisão de Markov (MDPs) onde a dinâmica de transição depende de o braço estar ativo ou passivo. O sistema evolui de tal forma que os braços não ativados continuam a transicionar de acordo com seus núcleos passivos ($p^0_a$), enquanto os braços ativados transicionam de acordo com os núcleos ativos ($p^1_a$).

2. Estrutura de Aprendizado e Referencial (Benchmark)

Os autores restringem sua análise a um referencial de "arrependimento puro" (pure regret).

• Políticas Puras: Uma política é definida como "pura" se ela seleciona um único braço do início ao fim do horizonte de aprendizado, sem nunca alternar.
• Definição de Arrependimento: O arrependimento é a diferença entre a recompensa cumulativa do algoritmo de aprendizado e a recompensa cumulativa da melhor política pura (o braço com o maior ganho assintótico).

Motivação para Políticas Puras:
Embora as políticas puras sejam geralmente subótimas para "bandidos inquietos" (restless bandits, onde braços inativos evoluem), os autores introduzem uma classe de bandidos chamados bandidos inquietos autodegradáveis (self-degrading restless bandits). Nestes casos, se um braço é deixado inativo, seu viés esperado (uma medida de desvio em relação à média) tende a diminuar ou manter-se constante em relação às observações do controlador. O artigo prova que, para bandidos autodegradáveis, as políticas puras são assintoticamente ótimas. Esta classe generaliza os bandidos "descansados" (rested bandits, onde braços inativos congelam) e inclui exemplos inquietos não triviais, como canais Gilbert-Elliott não preemptivos e modelos de Nerlove-Arrow.

3. Metodologia: UCB-NOM

O artigo propõe o UCB-NOM (Upper Confidence Bound for Non-Observable Markovian bandits), um algoritmo otimista inspirado no princípio UCB.

Componentes Principais do UCB-NOM:

1. Estimador de Ganho Empírico: O algoritmo estima o ganho ($g_a$) de um braço $a$ através da média das recompensas coletadas quando esse braço estava ativo.
2. Construção do Índice Otimista: Para lidar com a não observabilidade dos estados e com as restrições, o algoritmo constrói um limite superior otimista $\tilde{g}_a(t)$ para o ganho real. Este índice inclui:
   • A média de recompensa empírica.
   • Um bônus de exploração (intervalo de confiança) que considera:
     • O número de puxadas ($N_a(t)$).
     • O número de vezes que o algoritmo alternou para o braço $a$ (custo de alternância).
     • O alcance do viés (bias span - $sp(b_a)$) da cadeia de Markov do braço, que quantifica o desvio máximo da função de viés.
3. Truque do Dobramento (Doubling Trick): Para satisfazer a propriedade de "alternância rara" necessária para garantias teóricas, o algoritmo emprega um truque de dobramento. Uma vez que um braço é selecionado, ele é jogado até que o número de suas visitas dobre. Isso garante que o número de alternâncias cresça logaritmicamente com o número de puxadas.

Desafios Teóricos Abordados:

• Não-observabilidade: Diferente de trabalhos anteriores (ex: RCA por Tekin & Liu) que dependem da observação de estados para disparar ciclos de regeneração, o UCB-NOM não pode usar regeneração; em vez disso, ele limita o erro usando o alcance do viés e o número de alternâncias.
• Épocas Restritas: O algoritmo deve considerar o atraso entre as épocas de decisão. A análise assume um limite ($C_\tau$) no tempo esperado até a próxima época de decisão.

4. Resultados Principos e Garantias Teóricas

A. Limites Inferiores (Impossibilidade de Arrependimento Logarítmico)

O artigo estabelece que, sem conhecimento prévio da estrutura do bandido, o arrependimento logarítmico ($O(\log T)$) é inalcançável para algoritmos consistentes de alternância rara.

• Teorema 4: Para qualquer algoritmo consistente e de alternância rara, o arrependimento esperado escala como $\omega(\log T)$ (super-logarítmico). Isso é provado pela construção de modelos alternativos que são indistinguíveis do modelo real apenas via recompensas, mas que possuem braços ótimos diferentes, forçando o algoritmo a puxar braços subótimos excessivamente para distingui-los.

B. Desempenho do UCB-NOM (Caso Geral)

• Teorema 6: O UCB-NOM alcança um limite de arrependimento de $O(f(T)^2 \log T)$, onde $f(T)$ é uma função de "procuração de alcance" (span proxy) que diverge para o infinito.
• Significância: Ao escolher um $f(T)$ que diverge arbitrariamente devagar, o UCB-NOM pode se aproximar arbitrariamente do regime ideal logarítmico, igualando-se efetivamente ao limite inferior super-logarítmico.

C. Desempenho com Conhecimento Prévio (Alcance do Viés Limitado)

Se o algoritmo for provido de um limite superior conhecido $D$ sobre o alcance do viés de todos os braços (e o atraso da época de decisão), o desempenho melhora significativamente.

• Teorema 8 (Dependente da Instância): Com uma procuração de alcance fixa $f \equiv D$, o UCB-NOM alcança um arrependimento dependente da instância de $O(\log T)$.
• Teorema 9 (Pior Caso): Sob a mesma suposição de alcance limitado, o algoritmo alcança um arrependimento de pior caso de $O(\sqrt{T \log T})$.

D. Ajuste e Parâmetros de Confiança

O artigo analisa a escolha do parâmetro de confiança $\delta(t)$. Sugere-se que ser "sub-otimista" (escolher um $\delta(t)$ menor para ampliar os intervalos de confiança) é preferível em ambientes markovianos comparado a bandidos estocásticos. Isso ocorre porque o ruído nos estimadores markovianos pode ser maior do que a variância da recompensa sugere devido ao alcance do viés, exigindo bônus de exploração maiores para manter a propriedade otimista.

5. Significância e Contribuições

O artigo reivindica as seguintes contribuições:

1. Formulação do Problema: Formaliza um cenário de aprendizado que combina estados não observáveis e épocas de decisão endógenas e restritas, motivado por redes de comunicação (ex: escalonamento de canais não preemptivos).
2. Bandidos Autodegradáveis: Identifica e define uma classe de bandidos inquietos onde políticas puras são ótimas, justificando o uso do arrependimento puro como referencial.
3. Limites Fundamentais: Prova que a não-observabilidade dos estados combinada com épocas de decisão restritas impede inerentemente o arrependimento logarítmico no caso geral, estabeleando um limite inferior super-logarítmico.
4. Design de Algoritmo: Introduz o UCB-NOM, um algoritmo que alcança arrependimento quase ótimo sem observação de estado. Crucialmente, os limites de arrependimento não dependem do número de estados ($|S_a|$) das cadeias de Markov subjacentes, mas sim do alcance do viés.
5. Insights Estruturais: Demonstra que, com um simples conhecimento prévio (um limite para o alcance do viés), as garantias clássicas de arrependimento logarítmico dos bandidos estocásticos podem ser recuperadas, sugerindo que a não-observabilidade de estados é um "incômodo leve" em cenários autodegradáveis, desde que os limites estruturais sejam conhecidos.

Os autores concluem que, embora o cenário seja mais complexo do que os bandidos estocásticos padrão, o framework e o algoritmo propostos fornecem garantias teóricas robustas sem exigir as técnicas complexas tipicamente associadas aos Processos de Decisão de Markov Parcialmente Observáveis (POMDPs), desde que se adira ao referencial de arrependimento puro.