Resumo Técnico: Bandidos Duelistas Multi-Usuário: Uma Abordagem Justa usando o Bem-Estar Social de Nash

Definição do Problema

O artigo aborda o problema do Bandido Duelista Multi-Usuário Justo, um cenário onde um agente aprende a partir de dados de preferência pareada fornecidos por $D$ usuários distintos ao longo de um horizonte de tempo $T$ com $K$ braços. Diferente dos bandidos duelistas padrão, que assumem um único modelo de preferência ou agregam preferências em uma única matriz, este trabalho considera um cenário onde cada usuário $d$ possui uma matriz de preferência potencialmente distinta $P_d$.

O desafio central é aprender uma política que equilibre os interesses desses usuários heterogêneos sem marginalizar grupos minoritários. Abordagens padrão que otimizam para o bem-estar médio (utilitário) frequentemente favorecem a maioria estatística, levando a resultados injustos para usuários com preferências divergentes. Para abordar isso, os autores definem o objetivo usando o Bem-Estar Social de Nash (NSW), que maximiza o produto das utilidades dos usuários. Este objetivo inerentemente penaliza a desigualdade, garantindo que a utilidade de nenhum usuário seja levada a zero.

Um obstáculo técnico crítico neste cenário é a ausência de recompensas absolutas; o feedback é puramente relativo (resultados binários indicando qual de dois braços é preferido). Para definir a utilidade neste cenário relativo, os autores assumem a existência de um vencedor de Condorcet para cada usuário (um braço que vence todos os outros braços com probabilidade $>0.5$). A utilidade do usuário é então definida como uma pontuação derivada da probabilidade de um braço vencer o vencedor de Condorcet específico daquele usuário.

Metodologia

Estrutura Teórica

Os autores formalizam o problema definindo uma função de pontuação $s_d(i) = 2P_{d, i, a^*_d}$, onde $a^*_d$ é o vencedor de Condorcet para o usuário $d$. A utilidade de uma política $\pi$ para o usuário $d$ é a pontuação esperada $u_d(\pi) = \mathbb{E}_{a \sim \pi}[s_d(a)]$. O objetivo global é o Bem-Estar Social de Nash:
$$f(\pi, s) = \prod_{d=1}^D u_d(\pi)$$
O objetivo é minimizar o regret esperado em relação à política ótima $\pi^*$ que maximiza este produto.

Análise de Complexidade (Hardness)

O artigo estabelece um limite inferior de regret fundamental de $\Omega(T^{2/3} \min(K, D)^{1/3})$. Este resultado demonstra que a exigência de maximizar o NSW entre usuários com vencedores de Condorcet conflitantes introduz uma dificuldade significativa em comparação aos bandidos duelistas padrão (que tipicamente alcançam regret de $O(\log T)$). A dificuldade surge porque o algoritmo deve jogar "maus" vencedores de Condorcet (ótimos para um usuário, mas que geram utilidade próxima de zero para outros) para distingui-los de vencedores "bons", criando um compromisso entre custos de exploração e regret instantâneo.

Algoritmos

Dois algoritmos são propostos para atingir este objetivo, ambos incorporando uma fase de identificação do vencedor de Condorcet:

1. Fair-Explore-Then-Commit (Fair-ETC):

   • Fase 1 (Identificação): Utiliza um algoritmo modificado de Torneio Dvoretzky-Kiefer-Wolfowitz (DKWT) para identificar o conjunto de vencedores de Condorcet $\hat{A}^*$ para todos os $D$ usuários. Esta fase aproveita interações compartilhadas para atualizar margens empíricas para todos os usuários simultaneamente.
   • Fase 2 (Exploração): Estima as pontuações de todos os braços em relação aos vencedores de Condorcet identificados.
   • Fase 3 (Comprometimento): Computa a política $\hat{\pi}$ que maximiza o NSW empírico e se compromete com ela pelo restante do horizonte.

2. Fair-$\epsilon$-Greedy:

   • Este algoritmo intercala exploração e explotação ao longo do horizonte.
   • Ele começa com a mesma fase de identificação do vencedor de Condorcet.
   • Em cada passo $t$, com probabilidade $\epsilon_t$, ele explora jogando pares envolvendo os vencedores de Condorcet estimados (usando um cronograma round-robin) para refinar as estimativas de pontuação.
   • Com probabilidade $1-\epsilon_t$, ele explota jogando a política que maximiza o NSW empírico atual.
   • A taxa de exploração $\epsilon_t$ decai ao longo do tempo para garantir a convergência.

Ambos os algoritmos são provados para alcançar um limite superior de regret de $\tilde{O}(T^{2/3})$, correspondendo à dependência do limite inferior em relação ao horizonte de tempo $T$ até fatores logarítmicos.

Principais Contribuições

1. Formulação do Problema: A primeira formalização do problema do Bandido Duelista Multi-Usuário Justo, modelando utilidades de usuários distintas baseadas em seus vencedores de Condorcet individuais e adotando o NSW como o objetivo de justiça.
2. Limite Inferior de Regret: A derivação de um limite inferior de regret de $\Omega(T^{2/3} \min(K, D)^{1/3})$, que os autores afirmam ser o primeiro resultado quantificando o custo da justiça em bandidos duelistas com preferências heterogêneas.
3. Soluções Algorítmicas: A proposta dos algoritmos Fair-ETC e Fair-$\epsilon$-Greedy, acompanhados de limites superiores de regret teóricos que correspondem à dependência do limite inferior em relação a $T$.
4. Validação Empírica: Simulações extensas demonstrando que os algoritmos propostos superam as bases utilitárias em métricas de justiça (coeficiente de Gini, bem-estar mínimo do usuário) enquanto mantêm um regret cumulativo competitivo.

Resultados Experimentais

Os autores avaliaram seus algoritmos tanto em preferências geradas aleatoriamente quanto em dados do mundo real (o conjunto de dados Sushi, agrupado em usuários macroscópicos).

• Preferências Aleatórias: Em várias configurações de usuários ($D$) e braços ($K$), tanto o Fair-ETC quanto o Fair-$\epsilon$-Greedy demonstraram regret sublinear, superando consistentemente as bases utilitárias e uma base uniforme sobre usuários.
• Métricas de Justiça: Os algoritmos propostos alcançaram o maior Bem-Estar Social de Nash e coeficientes de Gini significativamente menores em comparação com as abordagens utilitárias. Eles também mantiveram um bem-estar mínimo de usuário mais alto, indicando melhor proteção para as preferências das minorias.
• Preferências Agrupadas: Em cenários com clusters distintos de maioria e minoria (simulando preferências polarizadas), os algoritmos utilitários favoreceram a maioria, levando a alta desigualdade. Os algoritmos justos propostos equilibraram com sucesso os interesses, mantendo baixos coeficientes de Gini e alto bem-estar mínimo.
• Conjunto de Dados Sushi: Nos dados do mundo real, os métodos propostos alcançaram o menor regret cumulativo nas configurações de cluster $D=5$ e $D=10$. Embora uma base uniforme tenha mostrado uma justiça ligeiramente melhor no caso fragmentado de $D=10$, ela sofreu com um regret vastamente inferior.

Significância e Alegações

O artigo afirma ser o primeiro trabalho a quantificar o custo da justiça em bandidos duelistas com preferências heterogêneas, estabelecendo um limite inferior de regret fundamental de $\Omega(T^{2/3})$. Os autores posicionam seu trabalho como um passo necessário em direção ao aprendizado de máquina centrado no ser humano, onde otimizar para a preferência média é insuficiente e potencialmente prejudicial aos grupos minoritários.

Ao integrar o objetivo de Bem-Estar Social de Nash na estrutura de bandidos duelistas, o trabalho fornece uma base teórica e algorítmica para aprender políticas que equilibram eficiência com justiça. Os autores observam que sua abordagem é distinta de trabalhos anteriores de multi-agentes bandit (ex: Hossain et al., 2021; Jones et al., 2023) porque opera em um cenário de preferência relativa em vez de um com recompensas absolutas, exigindo técnicas de estimativa de utilidade fundamentalmente diferentes.

O artigo conclui modestamente, reconhecendo que trabalhos futuros podem estender este framework para bandidos duelistas contextuais, espaços de ação contínuos e cenários onde a suposição do vencedor de Condorcet não se sustenta (possivelmente usando pontuações de Copeland ou Borda).