Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicality

Resumo Técnico: Follow-the-Perturbed-Leader para Bandits Decoplados

Configuração do Problema
Este artigo aborda o problema de bandits multi-arma decoplados (MAB), um cenário onde o aprendiz seleciona duas armas distintas em cada rodada $t$: uma arma $i_t$ para exploração (incorrendo na perda $\ell_{t, i_t}$ sem observá-la) e uma arma $j_t$ para exploração (observando a perda $\ell_{t, j_t}$ sem incorrer nela). Este quadro modela cenários como sistemas de comunicação ultra-wideband (sensando um canal diferente do canal de transmissão) e transferência sim-to-real em robótica. O objetivo é minimizar o pseudo-arrependimento, definido como a diferença entre a perda cumulativa incorrida pelas escolhas de exploração do aprendiz e a perda cumulativa da melhor arma fixa a posteriori.

O artigo visa garantias Melhor-de-Ambos-os-Mundos (BOBW), buscando alcançar:

1. Arrependimento ótimo de $O(\sqrt{KT})$ no regime adversarial (onde as perdas são determinadas por um adversário adaptativo).
2. Arrependimento quase ótimo e independente do tempo de $O(K/\Delta_{\min})$ no regime adversarial estocasticamente constrito (SCA) (que inclui o cenário estocástico padrão), onde $\Delta_{\min}$ é o menor intervalo de subotimalidade.

Metodologia
Os autores propõem uma nova política baseada no quadro Follow-the-Perturbed-Leader (FTPL), especificamente projetada para superar os gargalos computacionais das políticas BOBW existentes em configurações decopladas.

• Estratégia de Exploração: O aprendiz seleciona a arma de exploração $i_t$ minimizando uma estimativa de perda cumulativa perturbada:
  $$i_t = \arg\min_{i \in [K]} \left\{ \hat{L}_{t,i} - \frac{r_{t,i}}{\eta_t} \right\}$$
  onde $\hat{L}_{t,i}$ é a estimativa de perda cumulativa, $\eta_t$ é a taxa de aprendizado e $r_{t,i}$ são perturbações aleatórias i.i.d. amostradas de uma distribuição Pareto $P_\alpha$ com parâmetro de forma $\alpha > 1$. Este tipo de perturbação corresponde à política $\beta$-Tsallis-INF (com $\alpha = 1/(1-\beta)$), conhecida por alcançar garantias BOBW.

• Estratégia de Exploração (Inovação Chave): Em algoritmos de bandit FTPL padrão, a construção de um estimador de perda ponderado por importância (IW) não viesado tipicamente requer conhecer a probabilidade exata $w_{t,i}$ de selecionar a arma $i$. Em bandits decoplados, a probabilidade de exploração $p_{t,i}$ deve ser definida com base em $w_{t,i}$. No entanto, o FTPL não fornece uma expressão de forma fechada para $w_{t,i}$ (diferentemente do FTRL), e estimar o vetor completo via reamostragem geométrica é computacionalmente caro ($O(K^2)$ ou superior).
  Para resolver isso, os autores introduzem uma probabilidade substituta $q_{t,i}$ que pode ser computada diretamente a partir das estimativas de perda atuais, sem reamostragem ou otimização convexa:
  $$q_{t,i} = \left( \frac{1}{1 + \eta_t \hat{L}_{t,i}} \wedge \frac{1}{\sigma_{t,i}^{1/\alpha}} \right)^{\frac{\alpha+1}{2}}$$
  onde $\sigma_{t,i}$ é a classificação de $\hat{L}_{t,i}$ entre todas as armas. A arma de exploração $j_t$ é então selecionada de acordo com a distribuição normalizada $p_{t,i} = q_{t,i} / \sum_j q_{t,j}$. Esta abordagem evita a necessidade de valores explícitos de $w_{t,i}$, mantendo as propriedades teóricas necessárias para garantias BOBW.

Contribuições Principais

1. Primeira Política Baseada em FTPL para Bandits Decoplados com BOBW: O artigo apresenta a primeira política que alcança garantias BOBW em bandits decoplados sem resolver problemas de otimização convexa (exigidos por abordagens baseadas em FTRL como Decoupled-Tsallis-INF) ou empregar procedimentos de reamostragem (tipicamente exigidos para estimativa de probabilidade FTPL).
2. Eficiência Computacional: Ao substituir o cálculo do vetor completo de probabilidades pela substituta $q_{t,i}$ computável eficientemente, a política proposta reduz a complexidade computacional por etapa. Embora a ordenação das estimativas de perda leve $O(K \log K)$, os autores observam que uma implementação otimizada pode alcançar atualizações de $O(K)$ rastreando mudanças de classificação incrementalmente. Isso contrasta com políticas FTRL que requerem otimização convexa iterativa (por exemplo, método de Newton) a cada etapa.
3. Garantias Teóricas:
   • Regime Adversarial: A política alcança um limite de arrependimento de $O(\sqrt{KT})$, igualando o limite inferior conhecido para bandits decoplados.
   • Regime Estocástico/SCA: A política alcança um limite de arrependimento de $O(K/\Delta_{\min})$ (especificamente $O(\sqrt{K/\Delta_{\min}} \sum_{i \neq i^*} 1/\Delta_i + K/\Delta_{\min})$ para $\alpha=3$), que é quase ótimo e melhora os limites dependentes do tempo de bandits estocásticos padrão.

Resultados

• Teóricos: O artigo fornece provas rigorosas (via decomposição de arrependimento em termos de estabilidade e penalidade) mostrando que a probabilidade substituta $q_{t,i}$ está suficientemente próxima da verdadeira probabilidade de exploração para manter os limites de arrependimento necessários.
• Empíricos: Experimentos em dados sintéticos (ambos os regimes adversarial e estocástico) e uma simulação do mundo real usando o conjunto de dados MovieLens 100K demonstram que a política FTPL proposta:
  • Alcança menor arrependimento cumulativo comparado a políticas BOBW existentes (Decoupled-Tsallis-INF/FTRL e EXP3).
  • Demonstra eficiência computacional superior. No regime adversarial, a política proposta roda significativamente mais rápido que as linhas de base baseadas em FTRL. Para $K=64$, a razão de tempo de execução de FTRL para FTPL foi observada ser aproximadamente 1363 vezes mais lenta.
  • Escala efetivamente com o número de armas $K$, mantendo robustez através de tamanhos de intervalo $\Delta$ variados.

Significado e Alegações
O artigo alega que sua contribuição principal é preencher a lacuna entre a optimalidade teórica de políticas BOBW baseadas em FTRL e a eficiência computacional do FTPL no contexto de bandits decoplados. Ao eliminar a necessidade de otimização convexa e reamostragem, o método proposto permite que o FTPL realize plenamente suas vantagens de eficiência sem sacrificar o desempenho de arrependimento. Os autores sugerem que a técnica de usar probabilidades substitutas computáveis eficientemente no lugar de vetores de probabilidade exatos pode ser aplicável a outros quadros algorítmicos (como a família Prod) além do FTPL, potencialmente permitindo eficiência computacional aprimorada em configurações de bandit mais amplas. O trabalho é motivado por aplicações práticas em sistemas de comunicação e robótica onde a latência computacional por etapa é crítica.