Adaptive Prior Selection in Gaussian Process Bandits with Thompson Sampling

Este trabalho propõe dois algoritmos, PE-GP-TS e HP-GP-TS, baseados em amostragem de Thompson para Gaussian Processes, que realizam a seleção conjunta de priores e a minimização de arrependimento em problemas de otimização de caixa preta, oferecendo garantias teóricas e validação experimental superior em comparação com métodos existentes.

O essencial

Imagine que você é um explorador em um território desconhecido, tentando encontrar o ponto mais alto de uma montanha (o "melhor resultado") sem ter um mapa. Você só pode subir um pouco, olhar ao redor e ver a altura, mas não sabe como a montanha inteira é.

No mundo da inteligência artificial, isso se chama Otimização de Funções. O problema é que, para navegar nesse território, o explorador precisa de um "mapa mental" (chamado de Priori ou Prior) para fazer previsões sobre o que está além do que ele já viu.

Aqui está o grande dilema: Qual mapa mental usar?

• Devo assumir que a montanha é suave e arredondada?
• Ou que ela é cheia de picos agudos e vales profundos?
• Ou que ela tem um padrão repetitivo?

Na maioria dos trabalhos anteriores, os cientistas assumiam que já sabiam qual era o mapa correto. Mas, na vida real, isso quase nunca acontece. Se você escolher o mapa errado, você pode ficar preso em um vale ou gastar tempo subindo em lugares inúteis.

Os autores deste paper (Jack Sandberg e Morteza Haghir Chehreghani) propõem uma solução inteligente: Não adivinhe o mapa. Descubra-o enquanto você caminha.

Eles criaram dois novos métodos para ajudar o explorador a escolher o melhor "mapa mental" (prior) e a encontrar o topo da montanha ao mesmo tempo, usando uma técnica chamada Thompson Sampling (que é como jogar dados ponderados para decidir onde ir).

Vamos conhecer os dois heróis da história:

1. O Detetive Cético (PE-GP-TS)

Imagine que você tem uma caixa com 10 mapas diferentes. O Detetive Cético começa usando todos eles.

• Como funciona: A cada passo, ele escolhe um mapa e um local para explorar. Se o mapa diz "lá tem um pico alto" e você chega lá e só encontra uma pedra, o Detetive fica bravo.
• A Regra: Se um mapa fizer previsões erradas muitas vezes, ele é eliminados da caixa. É como se o Detetive dissesse: "Esse mapa é inútil, jogue fora!".
• O Resultado: Com o tempo, a caixa fica cheia apenas dos mapas que funcionam bem. Ele é eficiente porque descarta o que não serve, mas às vezes pode ser um pouco lento para eliminar os mapas ruins se eles forem "sortudos" no início.

2. O Mestre da Probabilidade (HP-GP-TS)

Este é o método mais sofisticado. Em vez de apenas jogar mapas fora, o Mestre da Probabilidade mantém todos os mapas, mas ajusta a "confiança" que ele tem em cada um.

• Como funciona: Imagine que cada mapa tem uma ficha de apostas. Se um mapa acerta uma previsão, sua ficha ganha valor. Se erra, perde valor.
• A Estratégia: O Mestre não joga fora os mapas ruins imediatamente. Ele apenas diminui a chance de usar aquele mapa. Ele faz uma "aposta dupla": aposta em qual mapa está certo E em qual local explorar.
• O Resultado: É como se ele tivesse um radar que, com o tempo, aponta quase exclusivamente para o mapa correto, sem precisar descartar os outros bruscamente. Isso é muito eficiente e evita que ele explore lugares ruins por "otimismo exagerado".

Por que isso é importante?

Antes desse trabalho, os algoritmos eram como turistas que insistem em usar um mapa de 1950 em uma cidade que mudou completamente. Eles gastavam muito tempo explorando lugares errados (chamado de "arrependimento" ou regret na teoria).

Os novos métodos dos autores são como turistas que:

1. Aprendem rápido: Percebem rapidamente qual mapa faz sentido.
2. Não desperdiçam energia: Param de seguir mapas ruins assim que percebem que estão errados.
3. Funcionam na prática: Eles testaram isso com dados reais (como temperatura em laboratórios da Intel, tráfego em rodovias da Califórnia e chuva no Noroeste do Pacífico) e com dados simulados.

O Veredito:
Os novos métodos (especialmente o Mestre da Probabilidade, HP-GP-TS) encontraram os melhores resultados mais rápido e cometeram menos erros do que os métodos antigos. Eles provaram que, em vez de tentar adivinhar a resposta perfeita no início, é melhor ter um sistema que aprende e se adapta enquanto você trabalha.

Em resumo: É como ter um GPS que não apenas te diz para onde ir, mas também aprende qual é o melhor tipo de mapa para a sua viagem específica, descartando as versões erradas e ajustando as corretas em tempo real.

Resumo técnico

1. Problema e Contexto

O trabalho aborda o problema de otimização de funções de caixa-preta (blackbox) utilizando Bandits de Processo Gaussiano (GP Bandits). Neste cenário, um agente seleciona sequencialmente "braços" (pontos de entrada) para maximizar a recompensa cumulativa, onde a função de recompensa esperada é modelada como uma amostra de um Processo Gaussiano (GP).

O Desafio Central:
A maioria das abordagens teóricas assume que o prior do GP (definido pela função de média e, crucialmente, pela função de kernel) é conhecido. Na prática, isso raramente é verdade. Os praticantes geralmente usam Estimativa de Máxima Verossimilhança (MLE) para selecionar hiperparâmetros, mas isso carece de garantias teóricas em problemas de decisão sequencial e pode levar a uma exploração ineficiente.

O objetivo deste trabalho é desenvolver algoritmos que realizem seleção adaptativa de priori e minimização de arrependimento (regret) simultaneamente, sem assumir que a priori correta é conhecida a priori. O agente deve distinguir entre um conjunto finito de priores candidatos para explorar eficientemente o espaço de busca.

2. Metodologia

Os autores propõem dois novos algoritmos baseados em Amostragem de Thompson (Thompson Sampling - TS), que substituem métodos baseados em Limites Superiores de Confiança (UCB) conhecidos por serem excessivamente otimistas.

A. PE-GP-TS (Prior-Elimination GP-TS)

Este algoritmo é uma extensão do PE-GP-UCB (anterior), mas adaptado para Thompson Sampling.

• Mecanismo: Mantém um conjunto de priores ativos. Em cada passo, amostra uma função de cada prior ativo e seleciona o braço que maximiza essa função amostrada.
• Eliminação: Monitora o erro de previsão acumulado do prior selecionado. Se a soma dos erros de previsão exceder um limiar estatístico (baseado em desigualdades de concentração), o prior é eliminado do conjunto ativo.
• Vantagem: Diferente do PE-GP-UCB, que possui "duas camadas de otimismo" (seleção de prior + seleção de braço via UCB), o PE-GP-TS possui apenas uma camada (amostragem posterior), reduzindo a exploração excessiva.

B. HP-GP-TS (HyperPrior GP-TS)

Este algoritmo adota uma abordagem totalmente bayesiana utilizando amostragem de hiper-posterior.

• Mecanismo: Em vez de eliminar priores, o algoritmo mantém uma distribuição de probabilidade sobre o conjunto de priores (hiper-posterior).
• Processo:
  1. Amostra um prior $p_t$ da distribuição atual do hiper-posterior.
  2. Amostra uma função $f_t$ do GP condicionado a esse prior.
  3. Seleciona o braço $x_t$ que maximiza $f_t$.
  4. Observa a recompensa e atualiza o hiper-posterior calculando a verossimilhança da observação sob cada prior candidato.
• Diferencial: Ao contrário de métodos que integram sobre o hiper-posterior (como Expected Improvement), o HP-GP-TS amostra apenas uma instância, reduzindo significativamente o custo computacional.

3. Contribuições Principais

1. Novos Algoritmos: Proposição de PE-GP-TS e HP-GP-TS para seleção adaptativa de priori em GP Bandits.
2. Análise Teórica de Regret:
   • Estabelecimento de limites superiores de regret para ambos os algoritmos.
   • Para PE-GP-TS, o regret é da ordem $O(\sqrt{T \log T |P| \hat{\gamma}_T})$, onde $|P|$ é o número de priores e $\hat{\gamma}_T$ é o ganho de informação máximo no pior caso.
   • Para HP-GP-TS, o regret é da ordem $O(\sqrt{T \log T \bar{\gamma}_T})$, onde $\bar{\gamma}_T$ é o ganho de informação médio (sobre a distribuição do hiper-prior). Isso é teoricamente superior quando os priores têm complexidades diferentes e o prior correto é mais simples.
3. Crítica Técnica: Os autores identificam e detalham falhas técnicas na prova do limite de regret do algoritmo MixTS (Hong et al., 2022b) no cenário linear, questionando a validade de certas condicionais usadas na prova original.
4. Validação Experimental: Avaliação extensiva em dados sintéticos e do mundo real, demonstrando superioridade sobre métodos baseados em UCB e outras abordagens bayesianas.

4. Resultados Experimentais

Os algoritmos foram testados em três configurações sintéticas (diferentes kernels, diferentes escalas de comprimento e subespaços) e três conjuntos de dados reais (temperatura Intel, tráfego PeMS e precipitação PNW).

• Desempenho de Regret:
  • O HP-GP-TS e o EEI (Expected Improvement totalmente bayesiano) apresentaram consistentemente o menor regret, aproximando-se do desempenho de um "oráculo" que conhece a priori correta.
  • O PE-GP-TS superou o PE-GP-UCB em todos os cenários, confirmando que a redução da "otimização excessiva" (over-exploration) melhora o desempenho.
  • O SCoreBO (Self-Correcting Bayesian Optimization) apresentou regret significativamente mais alto, apesar de tentar identificar o prior.
• Seleção de Priori:
  • O HP-GP-TS identificou o prior correto com muito mais frequência (acurácia de 63% em experimentos de kernel) em comparação aos métodos de eliminação (17%).
  • Os métodos de eliminação (PE) tendem a eliminar poucos priores ou falhar em distinguir kernels complexos (como RBF vs. Matérn), enquanto o HP-GP-TS concentra a massa de probabilidade no prior correto rapidamente.
• Escalabilidade:
  • O regret do HP-GP-TS não aumentou com o número de priores $|P|$ nos experimentos de subespaço, mantendo-se próximo ao do oráculo.
  • Em contraste, os métodos de eliminação (PE) mostraram um aumento no regret proporcional a $\sqrt{|P|}$.
• Dados Reais: Em todos os conjuntos de dados reais, o HP-GP-TS obteve o menor regret ou esteve dentro de um erro padrão do melhor algoritmo, superando consistentemente o SCoreBO e o PE-GP-UCB.

5. Significado e Conclusão

Este trabalho é significativo por fornecer uma solução prática e teoricamente fundamentada para o problema de incerteza de hiperparâmetros em otimização bayesiana.

• Redução de Otimismo: Ao substituir a seleção baseada em UCB (que é intrinsecamente otimista) pela Amostragem de Thompson, os autores conseguiram mitigar a exploração desnecessária de priores incorretos, o que é crucial quando o espaço de priores é grande.
• Eficiência Computacional vs. Teórica: O HP-GP-TS oferece um equilíbrio notável: é computacionalmente mais eficiente que métodos de integração total (como EEI) e teoricamente mais robusto que métodos de eliminação simples, especialmente em cenários onde a complexidade dos priores varia.
• Impacto Prático: A capacidade de aprender a priori correta "on-the-fly" sem sacrificar o desempenho de otimização torna esses algoritmos altamente aplicáveis em cenários do mundo real, como ajuste de hiperparâmetros de ML, descoberta de fármacos e otimização de redes, onde o modelo correto da função subjacente é desconhecido.

Em resumo, o artigo demonstra que a combinação de Amostragem de Thompson com mecanismos de seleção de priori adaptativa (seja por eliminação ou atualização de hiper-posterior) supera os métodos tradicionais baseados em UCB, oferecendo melhores garantias de regret e maior eficiência na identificação do modelo correto.