Resumo Técnico: Classificação e Seleção com Múltiplas Respostas Corretas e Estimativas Não Respondíveis

Formulação do Problema

Este artigo aborda problemas de classificação e seleção (R&S) de precisão fixa em configurações estruturadas caracterizadas por dois desafios específicos que complicam os modelos tradicionais de "identificação do melhor braço":

1. Múltiplas Respostas Corretas: O conjunto de respostas corretas, $A^\star(\theta)$, pode conter mais de um elemento (ex: selecionar qualquer alternativa "boa" dentro de uma tolerância $\epsilon$).
2. Estimativas Não Respondíveis: Devido a observações ruidosas, as estimativas empíricas podem cair temporariamente fora do "conjunto respondível" $\Theta^\star$, onde não existe uma resposta válida. Isso ocorre em cenários como R&S de múltiplas fidelidades (onde as médias empíricas violam restrições de viés) ou bandits duelistas (onde preferências estimadas induzem ciclos, impedindo um vencedor de Condorcet).

O objetivo é projetar uma regra de parada $\tau_\delta$ e uma regra de decisão $\hat{a}_{\tau_\delta}$ de modo que a probabilidade de selecionar uma resposta correta seja de pelo menos $1-\delta$ para todo $\theta \in \Theta^\star$, enquanto minimiza o custo total de amostragem esperado $E_\theta[B_{\tau_\delta}]$. O framework permite tipos de medição heterogêneos com custos variados.

Metodologia: O Framework Unificado

Os autores propõem um framework unificado que generaliza a perspectiva de "nomeação adaptada a armadilhas" (Qin e You, 2026) para lidar com respostas de valores de conjunto e não-respondibilidade transitória. Os componentes principais são:

1. Conjuntos de Aceitação por Resposta e Armadilhas (Pitfalls)

Em vez de focar em uma única resposta verdadeira, o framework decompõe o problema por respostas candidatas $a \in A$.

• Conjuntos de Aceitação ($\Theta^\star_a$): O conjunto de parâmetros onde a resposta $a$ é correta.
• Regiões de Rejeição ($Alt_a$): O conjunto de instâncias respondíveis onde $a$ é incorreta.
• Armadilhas ($X_a$): A região de rejeição $Alt_a$ é decomposta em uma união finita de conjuntos convexos mais simples $Alt_{a,x}$, indexados por "armadilhas" $x$. Uma armadilha representa uma forma específica de uma resposta falhar (ex: um desafiante específico superando o atual nomeado).

2. Razão de Verossimilhança Generalizada (GLR) Restrita de Parada

Para lidar com estimativas não respondíveis, os autores definem uma estatística GLR restrita $Z_n(a)$ para cada candidato $a$:
$$Z_n(a) = \inf_{\vartheta \in Alt_a} \Gamma(N_n; \hat{\theta}_n, \vartheta) - \inf_{\vartheta \in \Theta^\star_a} \Gamma(N_n; \hat{\theta}_n, \vartheta)$$
onde $\Gamma$ é a soma das divergências de Kullback–Leibler (KL) por coordenada e $\hat{\theta}_n$ é o MLE não restrito.

• Se a estimativa for não respondível, a estatística permanece bem definida ao comparar o melhor ajuste na região de rejeição contra o melhor ajuste na região de aceitação.
• A regra de parada $\tau_\delta$ é acionada quando $\max_{a \in A} Z_n(a) \geq \beta_{n,\delta}$.
• A regra de decisão seleciona a resposta que maximiza esta estatística, proporcionando robustez contra vencediros empíricos indefinidos.

3. O Valor Característico Max-Max-Min

O artigo deriva um limite inferior para o custo esperado, motivado por um valor característico $\Gamma^\star(\theta)$:
$$\Gamma^\star(\theta) \triangleq \max_{p \in \Delta_U} \max_{a \in A} \min_{x \in X_a} D_{a,x}(p; \theta)$$
onde $D_{a,x}$ é a taxa de informação normalizada pelo custo para descartar a armadilha $x$ para a resposta $a$.

• O mínimo interno identifica a armadilha mais difícil de descartar para uma resposta específica.
• O máximo do meio permite que o aprendiz nomeie a resposta mais "fácil" de certificar (crucial quando as estimativas são não respondíveis ou múltiplas respostas estão corretas).
• O máximo externo otimiza a alocação de amostragem $p$.
  Este valor dita a escala assintótica do orçamento de parada: $E_\theta[B_{\tau_\delta}] \gtrsim \log(1/\delta) / \Gamma^\star(\theta)$.

4. O Algoritmo ENDS

Os autores introduzem o ENDS (Estimation, Nomination, Detection, Selection - Estimativa, Nomeação, Detecção, Seleção), um procedimento geral:

1. Estimar (Estimate): Calcular um estimador $\theta_n$ (ex: amostra posterior).
2. Nomear (Nominate): Selecionar a resposta provisória $a_n$ que maximiza a estatística GLR $Z(a; p_n, \theta_n)$.
3. Detectar (Detect): Identificar a principal armadilha $x_n$ para $a_n$ (a instância alternativa mais confusa).
4. Selecionar (Select): Amostrar a próxima medição de uma distribuição de Amostragem Direcionada à Informação (IDS) sensível ao custo $H_{a_n, x_n}$, que minimiza o custo para distinguir a estimativa atual da alternativa de pior caso para a armadilha identificada.

Principais Contribuições

1. Framework Unificado: Uma receita estrutural única para R&S de precisão fixa sensível ao custo que lida simultaneamente com múltiplas respostas corretas e estimativas não respondíveis, unindo lacunas entre bandits de exploração pura e otimização de simulação.
2. Caracterização Teórica: A derivação do valor característico max-max-min, que generaliza limites inferiores existentes para cenários onde o mapa de respostas é de valores de conjunto e as estimativas podem ser temporariamente inválidas.
3. Receita Algorítmica (ENDS): Um algoritmo portátil que combina estimativa, nomeação, detecção de armadilha e IDS. O artigo fornece instanciações explícitas para:
   • Seleção de uma alternativa boa ($\epsilon$-best-arm).
   • R&S de múltiplas fidelidades.
   • Bandits duelistas com vencedores de Condorcet.
4. Fórmulas Explícitas: Derivação de expressões de forma fechada para as distribuições IDS e estatísticas GLR para as três classes de problemas representativas.

Resultados Experimentais

Experimentos numéricos extensos demonstram que o ENDS é robusto e competitivo através de problemas qualitativamente diferentes:

• Seleção de Alternativa Boa: Em configurações Gaussianas com variância desconhecida, o ENDS alcançou consistentemente o menor orçamento de parada esperado comparado com métodos de estado da arte (KN, Paulson, ZH-Proc2) e alocação uniforme, com a vantagem escalando com o número de alternativas.
• R&S de Múltiplas Fidelidades: O ENDS superou o MF-GRAD e as linhas de base de alta fidelidade apenas (TS-KKT-IDS, GRAD) na maioria das instâncias sintéticas. Notavelmente, ele lidou efetivamente com armadilhas de baixa fidelidade "enganosas", enquanto métodos que dependem apenas de alta fidelidade ou rastreamento de otimização contínua incorreram em custos mais altos.
• Bandits Duelistas: O ENDS superou significativamente as linhas de base (SAVAGE, DKWT, SEEBS) em termos de custo de parada esperado. Os autores observam que o desempenho superior deve-se em parte à regra de parada GLR desacoplada e mais forte em comparação com as regras de eliminação usadas pelas linhas de base.

Significância e Alegações

O artigo posiciona-se como uma prova de conceito de que uma linguagem algorítmica única pode ser transferida entre amplos modelos.

• Unificação: Argumenta que a presença conjunta de múltiplas respostas corretas e estimativas não respondíveis, anteriormente tratadas de maneira específica para cada problema, pode ser abordada via uma decomposição "por resposta" unificada.
• Praticidade: O "receituário unificado" proposto oferece um framework prático para problemas de exploração pura onde pontuações absolutas não estão disponíveis ou as estimativas são estruturalmente restritas.
• Modéstia: Os autores reconhecem que a calibração exata do limiar para a regra de parada permanece uma questão aberta e dependente do problema (usando uma heurística nos experimentos) e que limites superiores assintóticos rigorosos que correspondam ao valor característico são deixados para trabalhos futuros. Eles também observam que o ENDS não é atualmente projetado para problemas de larga escala devido a encargos computacionais.