Resumo Técnico: Tree-Guided Identify-Then-Exploit (TG-ITE)

Formulação do Problema

O artigo aborda o problema de bandidos duelistas estocásticos de $N$-braços sob a suposição do vencedor de Condorcet. Neste cenário, um aprendiz seleciona pares de braços $(i, j)$ e observa um resultado binário indicando qual braço venceu, regido por uma matriz de preferência desconhecida $P$. A suposição central é a existência de um vencedor de Condorcet único $a^\star$ tal que $P(a^\star, j) > 1/2$ para todo $j \neq a^\star$, enquanto as preferências entre os braços não vencedores podem ser cíclicas.

O estudo foca em unificar três objetivos distintos dentro deste mesmo framework:

1. Identificação do Melhor Braço (BAI - Best Arm Identification): Retornar $a^\star$ com alta confiança ($1-\delta$) em um tempo de parada dependente dos dados.
2. Minimização de Regret Fraco (Weak Regret Minimization): Minimizar o regret cumulativo onde uma rodada incorre em zero regret se pelo menos um dos dois braços escolhidos for $a^\star$.
3. Minimização de Regret Forte (Strong Regot Minimization): Minimizar o regret onde uma rodada incorre em zero regret apenas se ambos os braços escolhidos forem $a^\star$ (auto-jogo ou self-play).

A questão central de pesquisa é se um framework algorítmico unificado pode alcançar o desempenho ideal para todos os três objetivos simultaneamente, superando o tradicional compromisso (trade-off) entre exploração (necessária para BAI) e explotação (necessária para minimização de regret).

Metodologia: Tree-Guided Identify-Then-Exploit (TG-ITE)

A solução proposta, TG-ITE, adota um paradigma de Identificar-Então-Explotar (Identify-Then-Exploit). Ela desacopla o problema em uma fase de identificação compartilhada seguida por estratégias de explotação específicas para cada objetivo.

1. Primitiva de Identificação Compartilhada: TREEASCENT

A inovação central é um algoritmo de Identificação Guiada por Árvore chamado TREEASCENT. Diferente das estratégias padrão de "Explorar-Então-Comprometer" (ETC - Explore-Then-Commit), que são frequentemente subótimas em regret cumulativo, o TREEASCENT utiliza uma estrutura de árvore binária balanceada e determinística para guiar a busca pelo vencedor de Condorcet.

• Mecanismo: Partindo de um braço arbitrário $b$, o algoritmo sobe pelo caminho do ancestral de uma árvore binária fixa. Em cada nível $h$, ele realiza um torneio de eliminação direta (knockout tournament) em um "bloco de irmãos" de braços (braços recém-anexados naquele nível) para encontrar um representante.
• Fusão (Merging): O representante do bloco de irmãos é então comparado contra o "campeão" atual (o vencedor do nível anterior) usando um teste pairwise sequencial (DUELTEST).
• Eficiência: Ao alocar orçamentos de confiança proporcionais ao tamanho dos blocos de irmãos (tamanhos que crescem geometricamente), o algoritmo identifica um incumbente de alta confiança com complexidade de amostra de $O(N)$. Isso é alcançado sem exigir suposições mais fortes como transitividade estocástica forte ou desigualdade do triângulo estocástico, baseando-se apenas na existência do vencedor de Condorcet e em um gap global $\Delta$.

2. Estratégias de Explotação Específicas por Objetivo

Uma vez que um incumbente de alta confiança é identificado via TREEASCENT, o framework muda para políticas de explotação específicas:

• Para BAI (TG-ITE-BAI): O algoritmo simplesmente executa o TREEASCENT e para ao retornar o braço identificado. Isso alcança complexidade de amostra de $O(N)$, correspondendo ao limite inferior teórico para BAI.
• Para Regret Fraco (TG-ITE-WEAK): O algoritmo usa o TREEASCENT como um "aquecimento" (warm start) de confiança constante para encontrar um vencedor inicial. Ele então emprega uma estratégia do tipo Vencedor-Permanece (WS - Winner-Stays) chamada SCREENANDREPLACE. Em cada época, o incumbente atual é testado contra todos os desafiantes. Se um desafiante parecer vencer o incumbente, um torneio de substituição é realizado. Esta abordagem alcança $O(N)$ de regret fraco, melhorando os resultados anteriores de $O(N \log N)$.
• Para Regret Forte (TG-ITE-STRONG): O algoritmo identifica um incumbente confiável via TREEASCENT e então inicia o auto-jogo (self-play, comparando o incumbente contra si mesmo).
  • Horizonte Conhecido: Executa o TREEASCENT com confiança $1/(H+1)$, então auto-jogo.
  • Horizonte Qualquer Momento (Anytime): Intercala passagens de identificação cada vez mais confiáveis com blocos de auto-jogo cada vez mais longos.
  • Isso alcança $O(N \log T)$ de regret forte, igualando algoritmos especializados de regret forte.

Principais Contribuições e Resultados

1. Framework Unificado

O TG-ITE é o primeiro framework a unificar BAI, regret fraco e regret forte em bandidos duelistas usando uma primitiva de identificação compartilhada. Ele demonstra que o compromisso entre identificação e minimização de regret é "benigno" no cenário de bandidos duelistas devido à capacidade de usar um braço para exploração e outro para explotação.

2. Melhoria na Complexidade de Amostra e Limites de Regret

• BAI: Alcança complexidade de amostra de $O(N)$ sem exigir transitividade estocástica forte ou suposições de ordem total, igualando os melhores resultados conhecidos para BAI.
• Regret Fraco: Alcança $O(N)$ de regret fraco, fechando a lacuna de $O(\log N)$ encontrada em abordagens de otimização conjunta anteriores (ex: Ma et al., 2025) e igualando os melhores limites independentes de instância.
• Regret Forte: Alcança $O(N \log T)$ de regret, igualando as garantias de algoritmos especializados como WS-S e RUCB.
• Otimização Conjunta: O framework permite a otimização simultânea de BAI e regret fraco, alcançando garantias de $O(N)$ para ambos, eliminando os fatores subótimos de $O(\log N)$ presentes em trabalhos anteriores.

3. Garantias Teóricas

O artigo fornece provas rigorosas da correção e do custo do TREEASCENT e das subsequentes fases de explotação.

• Teorema 1: O TREEASCENT identifica o vencedor de Condorcet com probabilidade $1-\epsilon$ usando $O(N)$ comparações.
• Teorema 2: O regret fraco do TG-ITE-WEAK é limitado por $O(N/\Delta^2)$, sendo linear em $N$ e independente do horizonte de tempo $T$.
• Teoremas 3 & 4: Os limites de regret forte são $O(N \log T)$ tanto para horizontes conhecidos quanto desconhecidos.

4. Extensões

O artigo também apresenta uma Extensão Orçada de Gap Conhecido (Seção 5). Se um limite inferior $g$ sobre o gap de Condorcet for conhecido, o algoritmo pode substituir o DUELTEST de tempo qualquer por um teste de orçamento fixo. Isso remove o fator $\log(1/\Delta)$ dos limites, fornecendo orçamentos de comparação determinísticos e garantias mais estreitas, embora ao custo de exigir conhecimento prévio do gap.

Validação Experimental

Os autores avaliam o TG-ITE contra baselines representativos (incluindo WS-W, WS-S, RUCB, WR-TINF e WSW-PE) em instâncias sintéticas projetadas para testar a não-transitividade e gaps assimétricos.

• Escalabilidade de BAI: O TG-ITE-BAI escala quase linearmente com $N$, superando métodos de eliminação pairwise adaptativos em instâncias cíclicas.
• Regret Fraco: O TG-ITE-WEAK alcança o menor regret cumulativo e estabiliza rapidamente, demonstrando a eficácia da estratégia de warm-start.
• Regret Forte: O TG-ITE-STRONG supera significativamente os baselines, com a curva achatando assim que o auto-jogo começa, confirmando o comportamento teórico de $O(N \log T)$.

Significância e Alegações

O artigo afirma que o TG-ITE fornece evidência teórica de que o compromisso entre Identificação do Melhor Braço e Minimização de Regret é relativamente benigno em bandidos duelistas. Ao alavancar a estrutura única de bandidos duelistas (selecionar dois braços), o framework consegue desacoplar com sucesso as fases de exploração e explotação sem a subotimalidade tipicamente vista em bandidos multi-braços padrão.

Os autores enfatizam que sua abordagem:

1. Unifica três objetivos distintos sob uma única primitiva de identificação reutilizável (TREEASCENT).
2. Melhora o estado da arte para regret fraco ao remover o fator $O(\log N)$ e relaxar a suposição de ordem total.
3. Iguala as taxas ótimas para BAI e regret forte sem exigir suposições estruturais mais fortes (como transitividade estocástica forte) das quais algoritmos ótimos anteriores dependiam.

O trabalho sugere que o modelo "Identificar-Então-Explotar", quando guiado por uma decomposição de torneio baseada em árvore, é uma estratégia poderosa e generalizável para o aprendizado baseado em preferências.