On Regret Bounds of Thompson Sampling for Bayesian Optimization

Este artigo preenche lacunas na análise do Thompson Sampling com Processos Gaussianos (GP-TS) ao estabelecer limites de arrependimento inferiores e superiores, incluindo limites de segundo momento, arrependimento "leniente" esperado e uma melhoria no limite cumulativo em relação ao horizonte temporal $T$, superando as limitações anteriores que se restringiam principalmente a limites de arrependimento esperados.

O essencial

Imagine que você é um explorador em uma ilha misteriosa e precisa encontrar o ponto mais alto (o pico da montanha) para plantar uma bandeira. O problema é que a ilha é enorme, você não tem um mapa, e cada vez que você sobe em um lugar para ver a altura, você gasta muito tempo e energia (custo alto). Além disso, o terreno é "ruidoso": às vezes, a neblina ou o vento fazem você achar que está mais alto do que realmente está.

Esse é o problema da Otimização Bayesiana. Você quer encontrar o melhor lugar com o menor número de tentativas possível.

Para isso, os cientistas usam dois "bússolas" principais (algoritmos) para decidir onde ir a seguir:

1. GP-UCB: Uma bússola que é muito conservadora e segura. Ela sempre assume o "pior caso possível" dentro de uma margem de erro e vai para onde a margem de erro é maior. É como andar com um guarda-chuva enorme: você se protege muito bem, mas pode andar devagar.
2. GP-TS (Thompson Sampling): Uma bússola mais aventureira. Ela cria um "mapa imaginário" do terreno, sorteia um desses mapas aleatoriamente e vai para o ponto mais alto desse mapa específico. É como se você fechasse os olhos, imaginasse um terreno possível e fosse para lá. É mais rápido e intuitivo, mas às vezes pode se perder.

O que os autores descobriram?

Os autores deste artigo (Shion Takeno e Shogo Iwazaki) decidiram investigar a bússola aventureira (GP-TS) para ver se ela é realmente tão boa quanto a conservadora (GP-UCB) em termos de matemática e segurança. Eles encontraram quatro coisas importantes:

1. A Bússola Aventureira às vezes "Fica Presa" (Limite Inferior)

Eles provaram que, em situações muito específicas e ruins, a bússola aventureira (GP-TS) pode ficar confusa e escolher o caminho errado muitas vezes seguidas.

• A Analogia: Imagine que você está em um labirinto. A bússola conservadora (UCB) sempre verifica todas as portas antes de entrar. A aventureira (TS) escolhe uma porta baseada em um palpite. O artigo mostra que, se o labirinto for desenhado de um jeito muito malvado, a aventureira pode ficar girando em círculos por muito tempo.
• O Resultado: Eles mostraram que a chance de a bússola aventureira falhar e gastar muito tempo (regret) não cai tão rápido quanto a gente gostaria. Se você quer ter 99% de certeza de que não vai falhar, a bússola conservadora é mais eficiente. A aventureira precisa de um esforço extra (polinomial) para garantir a mesma segurança.

2. Ajustando a "Fórmula da Sorte" (Melhorando o Limite Superior)

Antes, os matemáticos diziam: "Se a bússola aventureira falhar, ela pode falhar muito, e a chance disso acontecer é proporcional a 1/δ". Isso é um número grande se δ for pequeno.

• A Analogia: Pense em um seguro de vida. O seguro antigo dizia: "Se você tiver um acidente, pagaremos R$ 1 milhão, mas a chance de pagar é 1 em 100". O novo estudo mostrou que, na verdade, a chance de pagar é 1 em 10.
• O Resultado: Eles criaram uma nova fórmula matemática (usando o "segundo momento" da variância) que mostra que a bússola aventureira é mais estável do que pensávamos. A chance de ela dar um "branco" gigante é menor do que se imaginava. Isso torna a bússola mais confiável.

3. A "Regra da Tolerância" (Regret Leniente)

Às vezes, não precisamos do pico exato da montanha. Se estamos a 1 metro do topo, já estamos satisfeitos. Isso é chamado de "regret leniente".

• A Analogia: Se você quer encontrar o melhor restaurante da cidade, não precisa ser o absolutamente melhor (o número 1). Se for um dos 10 melhores, já é ótimo.
• O Resultado: Eles provaram que a bússola aventureira é excelente nisso. Ela encontra um lugar "bom o suficiente" muito rápido. É como se ela fosse muito eficiente em encontrar "bons restaurantes" sem precisar gastar tempo procurando o "melhor restaurante do mundo".

4. O Caminho Mais Curto (Melhorando o Tempo Total)

Finalmente, eles olharam para o tempo total da viagem (T).

• A Analogia: Imagine que você tem 100 dias para explorar a ilha. A bússola conservadora diz: "Vou chegar perto do topo em 100 dias". A bússola aventureira, com as novas regras matemáticas que eles criaram, também consegue chegar perto do topo em 100 dias, mas com menos restrições sobre o tipo de terreno (kernels Matérn).
• O Resultado: Eles conseguiram provar que a bússola aventureira é tão eficiente quanto a conservadora em encontrar o topo, mesmo em terrenos muito complexos e rugosos, desde que o terreno não seja "muito áspero" (uma condição matemática chamada $\nu > 2$).

Resumo para Levar para Casa

Este artigo é como um manual de instruções atualizado para a bússola aventureira (GP-TS).

• O Problema: Ninguém sabia se ela era tão segura quanto a bússola conservadora (GP-UCB).
• A Descoberta: Eles mostraram que ela tem um "ponto fraco" em situações extremas (pode ficar confusa), mas que, no dia a dia, ela é muito mais eficiente e rápida do que se pensava.
• A Solução: Eles criaram novas regras matemáticas que tornam a bússola aventureira mais confiável e provaram que ela é perfeita para encontrar "soluções boas o suficiente" rapidamente.

Em suma, se você precisa de segurança absoluta e tem tempo, use a bússola conservadora. Mas se você quer ser ágil, eficiente e encontrar soluções ótimas (ou muito próximas do ótimo) em menos tempo, a bússola aventureira (GP-TS) é uma escolha excelente, e agora temos a matemática para provar isso!

Resumo técnico

Resumo Técnico: Limites de Arrependimento do Thompson Sampling para Otimização Bayesiana

Autores: Shion Takeno (Universidade de Nagoya) e Shogo Iwazaki (MI-6 Ltd.)
Contexto: Otimização Bayesiana (BO) com Processos Gaussianos (GP).

1. Problema e Motivação

A Otimização Bayesiana (BO) é um framework poderoso para otimizar funções "caixa-preta" caras, utilizando modelos probabilísticos, tipicamente Processos Gaussianos (GP). Dois algoritmos dominantes na literatura são o GP-UCB (Upper Confidence Bound) e o GP-TS (Thompson Sampling).

• O Estado da Arte: O GP-UCB possui limites de arrependimento (regret) bem estabelecidos, incluindo limites de alta probabilidade e esperados. Recentemente, foram obtidos limites mais apertados para o GP-UCB, incluindo limites de "arrependimento leniente" (lenient regret) e limites de alta probabilidade que dependem logaritmicamente do parâmetro de confiança $\delta$.
• A Lacuna: As análises do GP-TS foram historicamente limitadas a limites de arrependimento esperado. Embora o GP-TS tenha desempenho empírico robusto, seus limites de alta probabilidade eram fracos (dependência polinomial em $1/\delta$) e não havia limites estabelecidos para arrependimento leniente ou limites de alta probabilidade otimizados para o horizonte de tempo$T$.
• Objetivo: Este artigo visa preencher essas lacunas, fornecendo uma análise de arrependimento refinada para o GP-TS, comparável à do GP-UCB, e investigando a dependência em $\delta$ e $T$.

2. Metodologia e Premissas

O estudo opera no cenário Bayesiano, onde a função objetivo $f$ é assumida como uma trajetória amostral de um Processo Gaussiano com média zero e uma função de covariância (kernel) $k$.

• Configuração: Otimização sequencial com ruído de observação ($y_t = f(x_t) + \epsilon_t$).
• Kernels Analisados: Linear, Quadrático Exponencial (SE) e Matérn (com parâmetro de suavidade $\nu$).
• Métricas de Desempenho:
  1. Arrependimento Cumulativo ($R_T$): Soma das diferenças entre o ótimo global e as escolhas feitas.
  2. Arrependimento Leniente ($LR_T$): Soma das diferenças apenas quando o erro excede uma tolerância $\Delta$ (foca em identificar ações "boas o suficiente").
  3. Dependência em Probabilidade ($\delta$): Analisa como o limite de arrependimento escala com a confiança $1-\delta$.

3. Principais Contribuições e Resultados

Os autores apresentam quatro contribuições teóricas principais:

A. Limite Inferior de Arrependimento para GP-TS (Teorema 3.1)

• Descoberta: Os autores construíram um caso de problema de dois braços onde o GP-TS sofre um arrependimento de ordem $\Omega(1/\delta^c)$ com probabilidade $\delta$.
• Implicação: Isso prova que, em geral, o GP-TS não pode atingir limites de arrependimento de alta probabilidade com dependência logarítmica em $1/\delta$(ou seja,$O(\log(1/\delta))$), ao contrário do GP-UCB. A dependência polinomial é inerente ao método em certos cenários.

B. Limite Superior de Alta Probabilidade Aprimorado (Teorema 3.2)

• Método: Derivaram um limite superior para o segundo momento do arrependimento cumulativo ($E[R_T^2]$).
• Resultado: Ao aplicar a desigualdade de Markov no segundo momento, obtiveram um limite de alta probabilidade que melhora a dependência em $\delta$ de $O(1/\delta)$ para $O(1/\sqrt{\delta})$.
• Significado: Embora ainda não seja logarítmico, é uma melhoria significativa sobre os resultados anteriores que dependiam diretamente do limite esperado.

C. Limites de Arrependimento Leniente Esperado (Teorema 3.3)

• Inovação: Estabelecem o primeiro limite de arrependimento leniente esperado para o GP-TS.
• Resultado: O limite é polilogarítmico no horizonte de tempo $T$ (ex: $O(\text{polylog}(T))$), alinhando-se com os melhores limites de alta probabilidade conhecidos para o GP-UCB.
• Técnica: Utilizaram uma prova diferente da literatura existente (Cai et al., Iwazaki), baseada em contagem de potencial elíptico, que pode ser estendida para o GP-UCB.

D. Limite de Arrependimento Cumulativo Otimizado em $T$ (Teorema 3.5 e Lemma 3.4)

• Refinamento: Adaptaram a análise recente do GP-UCB (Iwazaki, 2025b) para o GP-TS.
• Resultado: Derivaram um limite de alta probabilidade de $\tilde{O}(\sqrt{T})$ para kernels SE e Matérn.
• Condição Relaxada: Uma contribuição crucial é o relaxamento da condição de suavidade para kernels Matérn. Trabalhos anteriores exigiam $2\nu + d \leq \nu^2$. Este trabalho mostra que a condição **$\nu > 2$** é suficiente, o que é mais geral e alinha-se com as premissas necessárias para a existência de maximizadores únicos (Lemma 2.4).

4. Discussão Técnica e Limitações

• Comparação com Bayrooti et al. (2025): O artigo discute que resultados recentes que sugerem limites $O(\sqrt{T\gamma_T \log(T/\delta)})$ para GP-TS podem conter falhas na transferência de técnicas do cenário frequentista para o Bayesiano, devido à aleatoriedade da função $f$. O Teorema 3.1 serve como um contra-argumento teórico à possibilidade de limites logarítmicos em $\delta$ sem modificações no algoritmo.
• Inflação de Variância: Os autores conjecturam que o uso de "variance inflation" (inflação de variância), comum em cenários frequentistas, poderia permitir limites melhores em $\delta$ para o GP-TS, mas a extensão das provas para o cenário Bayesiano com arrependimento leniente permanece um desafio devido ao uso de desigualdades como Azuma-Hoeffding.
• Condição $\nu > 2$: Embora o relaxamento para $\nu > 2$ seja uma melhoria, ele ainda exclui kernels Matérn amplamente utilizados com $\nu = 1/2$ ou $3/2$. Determinar se essa condição é fundamental ou se pode ser relaxada ainda é uma questão em aberto.

5. Significado e Impacto

Este trabalho é fundamental para a teoria da Otimização Bayesiana porque:

1. Estabelece Limites Fundamentais: Demonstra que o GP-TS tem limitações teóricas intrínsecas na dependência de $\delta$ que o diferenciam do GP-UCB, orientando a escolha do algoritmo baseada em requisitos de garantia probabilística.
2. Unificação de Análise: Fornece ferramentas analíticas (como o Lemma 3.4) que podem ser aplicadas tanto ao GP-TS quanto ao GP-UCB, simplificando a análise de algoritmos de amostragem posterior.
3. Avanço em Arrependimento Leniente: Abre novas direções para a análise de algoritmos estocásticos focando em identificar ações "boas o suficiente" em vez de apenas o ótimo global, uma métrica mais prática para muitas aplicações industriais.

Em suma, o paper oferece a análise de arrependimento mais completa e rigorosa até o momento para o Thompson Sampling em Otimização Bayesiana, equilibrando a compreensão de suas limitações com a demonstração de seu potencial através de limites refinados.