Resumo Técnico: Identificação de Conjunto de Pareto Bayesiano para Bandidos Multi-Objetivo Multi-Braços de Tempo Contínuo (Anytime)

Definição do Problema

O artigo aborda o problema do Bandido Multi-Objetivo Multi-Braços (MOMAB), focando especificamente na Identificação de Conjunto de Pareto (PSI). Diferente dos problemas de bandido de objetivo único padrão, que visam maximizar a recompensa cumulativa (minimização de regret) ou identificar um único melhor braço, o MOMAB envolve a otimização de múltiplos objetivos, potencialmente conflitantes, simultaneamente. Neste cenário, não existe um único braço que seja ótimo em todos os critérios; em vez disso, existe um conjunto de braços Pareto-ótimos ($P^\star$) que representam os melhores compromissos (trade-offs).

O desafio específico tratado é a formulação de PSI de Tempo Contínuo (Anytime). Enquanto a literatura existente cobriu extensivamente configurações de orçamento fixo (minimização de erro após um número definido de amostras) e confiança fixa (minimização de amostras para atingir uma precisão alvo), há uma lacuna em algoritmos que possam fornecer uma estimativa válida e continuamente atualizada do conjunto de Pareto após cada observação, sem uma regra de parada predefinida. Isso é crítico para aplicações do mundo real onde os tomadores de decisão precisam monitorar o progresso e, potencialmente, encerrar experimentos dinamicamente com base em níveis de confiança, em vez de restrições rígidas de recursos.

Metodologia: Top-Two Pareto Front Thompson Sampling (TTPFTS)

Os autores introduzem o Top-Two Pareto Front Thompson Sampling (TTPFTS), o primeiro algoritmo Bayesiano de tempo contínuo (anytime) projetado para o problema de MOMAB PSI. O algoritmo estende os princípios do Top-Two Thompson Sampling (TTTS) do problema de identificação do melhor braço de objetivo único para o domínio multi-objetivo.

Mecanismo Central

Em vez de escalar os objetivos com um vetor de preferência (o que reduziria o problema a um único objetivo), o TTPFTS opera diretamente nos fronts de Pareto. Em cada passo de tempo $t$:

1. Amostragem da Posterior: O algoritmo amostra vetores de recompensa média $\tilde{\theta}^{(t)}_a$ para todos os $K$ braços a partir de suas respectivas distribuições posteriores condicionadas ao histórico $H(t-1)$.
2. Identificação do Front: Com base nessas amostras, ele identifica o Primeiro Front de Pareto ($F^\star_1$), consistindo nos braços que não são dominados por nenhum outro braço amostrado.
3. Seleção Estocástica: Um teste de Bernoulli com probabilidade $\rho$ determina qual front será explorado:
   • Com probabilidade $\rho$: Um braço é selecionado uniformemente ao acaso do Primeiro Front ($F^\star_1$). Isso foca em verificar braços atualmente considerados ótimos.
   • Com probabilidade $1-\rho$: O algoritmo remove o $F^\star_1$ e identifica o Segundo Front de Pareto ($F^\star_2$) a partir dos braços restantes. Um braço é então selecionado uniformemente ao acaso do $F^\star_2$. Isso promove a exploração dos braços subótimos mais promissores (desafiantes) para testar se eles foram subestimados ou para solidificar seu status de subotimalidade.
4. Atualização: O braço selecionado é acionado, a recompensa é observada e o histórico é atualado. O algoritmo mantém um conjunto de recomendação $\hat{P}^\star_t$ (o conjunto de Pareto das médias da posterior) em todos os momentos.

Garantias Teóricas

O artigo fornece uma prova de corretude assintótica (Teorema 1). Sob suposições padrão (braços finitos, posteriors consistentes, lacunas de Pareto estritas e exploração suficiente), a estimativa do algoritmo $\hat{P}^\star_t$ converge para o verdadeiro conjunto de Pareto $P^\star$ com probabilidade 1 conforme $t \to \infty$. A prova baseia-se no Lema 1, que estabelece que o TTPFTS garante a exploração infinita de todos os braços quase certamente, impedindo que qualquer braço seja permanentemente "congelado" do processo de amostragem.

Principais Contribuições

1. Primeiro Algoritmo Bayesiano de Tempo Contínuo para MOMAB PSI: O TTPFTS preenche a lacuna na literatura em relação a algoritmos de tempo contínuo para identificação de conjunto de Pareto, oferecendo uma alternativa flexível às abordagens de orçamento fixo e confiança fixa.
2. Nova Métrica de Quantificação de Incerteza (UQ): Os autores introduzem uma métrica independente da verdade fundamental (ground-truth) para estimar a confiança do algoritmo em sua previsão atual de Pareto. Esta métrica calcula a sobreposição de Bhattacharyya entre as densidades da posterior dos braços no primeiro front estimado ($\hat{P}^\star_1$) e no segundo front ($\hat{P}^\star_2$).
   • Alta sobreposição indica alta incerteza (dificuldade em distinguir braços ótimos de subótimos).
   • Baixa sobreposição indica alta confiança (separação clara entre os fronts).
   • Esta métrica serve como um proxy em tempo real para o desempenho da identificação, permitindo critérios de parada dinâmicos.
3. Aplicação Real em Descoberta Molecular: O algoritmo é validado em um cenário desafiador de biblioteca de síntese sob demanda ultra-grande (94 milhões de candidatos), demonstrando sua utilidade na identificação de moléculas que otimizam propriedades conflitantes (Similaridade Estrutural e LogP).

Resultados Empíricos

Benchmarks Sintéticos

O TTPFTS foi avaliado contra algoritmos de orçamento fixo de última geração (variantes de Successive Rejects e Successive Halving do Empirical Gap Elimination, EGE) em oito ambientes sintéticos com variadas geometrias de front de Pareto e dimensões.

• Desempenho: O TTPFTS superou consistentemente o Uniform Sampling e o algoritmo EGE-SH. Ele alcançou paridade de desempenho com o EGE-SR (a base de orçamento fixo mais forte) em todos os ambientes, apesar da restrição mais rigorosa de tempo contínuo.
• Escalabilidade: Em ambientes com grandes espaços de ação (ex: $K=200$), o TTPFTS superou significativamente as variantes de EGE, sugerindo que sua alocação impulsionada pela posterior é mais eficaz do que a eliminação rígida baseada em lacunas em problemas de larga escala.
• Robustez: O algoritmo apresentou bom desempenho mesmo com suposições de prior fracas (distribuições uniformes).

Estudo de Caso de Descoberta Molecular

Na exploração de uma biblioteca de 94 milhões de compostos:

• Eficiência: O TTPFTS identificou moléculas que coincidem perfeitamente com o front de Pareto da verdade fundamental (52 moléculas) enquanto avaliava apenas 0,05% do banco de dados.
• Comparação: Superou significativamente tanto a Busca Aleatória (Random Search), que encontrou zero moléculas ótimas, quanto o método de aprendizado ativo de última geração, MolPAL.
• Correlação de Incerteza: A métrica de UQ proposta mostrou uma forte correlação negativa com a métrica de Jaccard (precisão). À medida que o algoritmo melhorava sua estimativa do conjunto de Pareto, a métrica de incerteza diminuía, validando seu uso como um indicador confiável de convergência, independente da verdade fundamental.

Significância e Alegações

O artigo afirma que o TTPFTS fornece uma metodologia robusta para monitorar o progresso do aprendizado em cenários complexos de múltiplos objetivos sem a necessidade de conhecimento do verdadeiro front de Pareto. Ao combinar uma estratégia de exploração de tempo contínuo com uma nova métrica de quantificação de incerteza, este trabalho transforma o problema de identificação de conjunto de Pareto de uma tarefa de amostragem estática em um sistema de suporte à decisão dinâmico.

Os autores enfatizam que esta abordagem permite aos tomadores de decisão:

• Determinar dinamicamente quando o front de Pareto está suficientemente resolvido para encerrar um experimento.
• Otimizar o equilíbrio entre recursos computacionais e confiança na descoberta.
• Aplicar esses benefícios em cenários do mundo real, como a descoberta de fármacos, onde a triagem exaustiva é inviável e as preferências podem não ser conhecidas a priori.

O artigo permanece modesto quanto aos limites de erro de tempo finito, reconhecendo que, embora a corretude assintótica seja provada, derivar taxas explícitas de tempo finito continua sendo um desafio semelhante ao enfrentado pelo Thompson Sampling padrão no passado. No entanto, os autores argumentam que a combinação de solidez assintótica, forte desempenho empírico e a utilidade prática da métrica de incerteza estabelece o TTPFTS como um avanço significativo na tomada de decisão multi-objetivo.