Learning in Matching Games with Bandit Feedback

Resumo Técnico: Aprendizado em Jogos de Emparelhamento com Feedback de Bandidos

Formulação do Problema
Este artigo introduz um novo problema de aprendizado situado na interseção entre mercados de emparelhamento de dois lados e teoria dos jogos. O cenário envolve um mercado generalizado com dois conjuntos distintos de agentes, $P$ e $A$, que são emparelhados por uma plataforma central ao longo de um horizonte de tempo $T$. Diferente dos problemas de emparelhamento tradicionais, onde os agentes possuem preferências estáticas e conhecidas, ou dos configurações padrão de Multi-Armed Bandit (MAB), onde os agentes recebem pagamentos estocásticos diretos, este framework postula que, uma vez emparelhados, os agentes participam de um jogo de soma zero de dois jogadores (ZSG) com uma matriz de pagamentos inicialmente desconhecida.

Neste cenário, os agentes devem aprender simultaneamente a dinâmica subjacente do jogo e derivar suas preferências a partir dos resultados dessas interações. Em cada passo de tempo $t$:

1. Uma plataforma central gera um emparelhamento $m_t$ baseado nas preferências estimadas dos agentes.
2. Os agentes emparelhados selecionam estratégias (ações mistas) e amostram ações específicas.
3. Os agentes recebem feedback estocástico de bandidos (recompensas) e observam as ações de seu parceiro emparelhado.
4. Os agentes atualizam suas estimativas das matrizes de pagamentos e de suas preferências para a rodada seguinte.

O desafio central é aprender um Equilíbrio de Emparelhamento, um conceito de solução definido por [10], onde o emparelhamento é estável (sem pares de bloqueio) e os agentes jogam um Equilíbrio de Nash (NE) com seus parceiros atribuídos. A dificuldade surge porque os agentes não conhecem as matrizes de jogo a priori e devem explorar para formar preferências, enquanto o mecanismo de emparelhamento (tipicamente Gale-Shapley) depende dessas preferências para garantir a estabilidade.

Metodologia e Algoritmo
Para abordar isso, os autores propõem o UCB-MG, um algoritmo baseado no princípio do "otimismo diante da incerteza". A metodologia opera da seguinte forma:

• Estimativas Otimistas: Os agentes mantêm limites superiores de confiança (UCB) para as matrizes de pagamento de potenciais emparelhamentos. Especificamente, para um par $(p, a)$, a matriz de pagamento estimada $\bar{A}_{p,a}$ é construída adicionando um bônus de confiança à média empírica das recompensas observadas.
• Formação de Preferências: Com base nessas matrizes de pagamento otimistas, os agentes computam o valor otimista do jogo ($\bar{V}^*$) assumindo o jogo ideal (estratégias minimax) contra cada potencial parceiro. Os agentes então classificam suas preferências de acordo com esses valores de jogo otimistas.
• Emparelhamento: A plataforma central coleta essas preferências relatadas e executa o algoritmo Gale-Shapley (GS) para gerar um emparelhamento estável para a rodada atual.
• Execução de Estratégia: Uma vez emparelhados, os agentes selecionam ações baseadas nas estratégias minimax derivadas de suas matrizes de pagamento otimistas, amostram ações e recebem feedback para atualizar suas estimativas.

Formulação de Regret: Instabilidade de Emparelhamento
Uma contribuição crítica do artigo é a definição de uma métrica de regret apropriada, denominada Instabilidade de Emparelhamento (MI). Definições de regret padrão de MAB ou teoria dos jogos são insuficientes porque o objetivo é convergir para um equilíbrio conjunto de emparelhamento e estratégia.

Os autores definem MI como a solução de um programa linear que minimiza subsídios $s_a$ sujeito a:

1. Ausência de Pares de Bloqueio: Garantir que nenhum par $(p, a)$ possa melhorar sua utilidade ao desviar-se, dado o perfil de estratégia atual.
2. Racionalidade Individual: Garantir que os agentes prefiram seu emparelhamento em vez de ficarem sem par.
3. Garantia de Valor: Garantir que os agentes recebam uma utilidade pelo menos igual ao valor minimax de seu jogo (uma relaxação da condição estrita de Nash para facilitar uma análise tratável).

O regret cumulativo $R_T$ é definido como a soma da Instabilidade de Emparelhamento ao longo do horizonte $T$.

Principais Contribuições

1. Definição do Problema de Aprendizado: O artigo formaliza o primeiro cenário de aprendizado onde agentes em um mercado de dois lados devem aprender jogos desconhecidos para formar preferências para emparelhamento.
2. Métrica de Regret: Introduz a Instabilidade de Emparelhamento, estendendo o conceito de Instabilidade de Subconjunto [8, 17] para cenários onde agentes emparelhados jogam jogos. Esta métrica quantifica a distância de um Equilíbrio de Emparelhamento.
3. Design de Algoritmo: Os autores propõem um algoritmo baseado em UCB (UCB-MG) que integra a estimativa otimista de valor de jogo com o mecanismo Gale-Shapley.
4. Garantias Teóricas: O artigo prova que o algoritmo proposto alcança um limite de regret sublinear e independente da instância de $\tilde{O}(\sqrt{Tmkpa})$, onde $T$ é o horizonte, $m$ e $k$ são o número de ações por agente, e $p$ e $a$ são o número de agentes em cada lado.
5. Generalização: O limite teórico unifica resultados existentes. Quando $m=k=1$, recupera o limite para o emparelhamento clássico de dois lados ($\tilde{O}(\sqrt{Tpa})$). Quando $p=a=1$, recupera o limite para o auto-jogo (self-play) em jogos de soma zero ($\tilde{O}(\sqrt{Tmk})$).

Resultos e Evidência Empírica
Os autores fornecem validação empírica usando instâncias sintéticas onde as matrizes de pagamento são amostradas de uma distribuição normal. Eles comparam três cenários:

• Self-Play: Ambos os lados seguem o algoritmo UCB-MG.
• Nash-Response: Um lado conhece as matrizes de jogo reais e joga a estratégia de Equilíbrio de Nash, enquanto o outro aprende.
• Best-Response: Um lado conhece as matrizes reais e as estratégias do oponente, jogando a melhor resposta.

Os resultados indicam que o sistema aprende um resultado estável em todos os cenários, exibindo crescimento de regret sublinear. Como esperado, o cenário Nash-Response produz o menor regret. Curiosamente, embora o cenário Best-Response supere inicialmente o Self-Play, seu desempenho degrada conforme o tamanho do mercado (número de agentes e ações) aumenta, provavelmente devido à complexidade introduzida pelo fato de um lado explorar o outro.

Significância e Direções Futuras
O artigo reivindica significância como um passo inicial para entender o aprendizado em ambientes onde os agentes recebem pagamentos apenas após interagirem através de ações em um jogo, em vez de receberem sinais de preferência diretos. Demonstra que resultados estáveis podem ser aprendidos eficientemente em tais configurações complexas e acopladas.

Os autores enquadram modestamente este trabalho como uma fundação para pesquisas futuras. Eles identificam várias direções abertas:

• Estender o modelo de jogos de soma zero para jogos de soma geral.
• Integrar algoritmos de aprendizado sem-regret (como Exp3) na estrutura de emparelhamento para lidar com dinâmicas de soma não zero.
• Relaxar a suposição de que os agentes observam as ações de seus parceiros.
• Explorar modelos de jogo alternativos (jogos de Markov, jogos de Stackelberg) e estruturas de emparelhamento (mercados de muitos-para-um).
• Investigar configurações descentralizadas onde os agentes selecionam tanto os emparelhamentos quanto as estratégias sem um coordenador central.