🤖 machine learning

Regret, equilibrium, and learning in games: A guided tour

Este artigo fornece uma visão unificada de políticas de aprendizado regularizadas em jogos, analisando seus limites de arrependimento em configurações adversariais de agente único e sua convergência ao equilíbrio em interações multiagentes, ao mesmo tempo em que estabelece uma ponte entre processos de aprendizado dinâmicos e conceitos de racionalidade estática em ambos os modelos de informação de oráculo e de bandit.

Autores originais: Panayotis Mertikopoulos

Publicado 2026-08-11

📖 8 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Panayotis Mertikopoulos

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine um mundo onde todos estão constantemente tentando fazer a melhor escolha, mas ninguém tem um livro de regras, ninguém sabe o que os outros estão pensando e as regras do jogo podem mudar a cada segundo. Este é o parquinho caótico da teoria dos jogos, um ramo da ciência que estuda como as pessoas (ou computadores, ou animais) tomam decisões quando o seu sucesso depende do que todos os outros fazem. Durante décadas, os cientistas assumiram que, se todos fossem perfeitamente racionais, acabariam por descobrir o equilíbrio perfeito chamado equilíbrio de Nash, onde ninguém tem razão para mudar a sua estratégia. Mas, no mundo real, as pessoas não são calculadoras perfeitas; são desordenadas, reativas e, muitas vezes, estão apenas tentando sobreviver. Assim, surgiu uma grande questão: se deixarmos esses agentes imperfeitos aprenderem por tentativa e erro, eles acabarão por tropeçar acidentalmente nesse equilíbrio perfeito ou ficarão apenas girando em círculos?

Este artigo, escrito por Panayiotis Mertikopoulos, leva-nos numa visita guiada através desta realidade desordenada. Explora o aprendizado em jogos, um campo que se situa na intersecção entre a economia, a ciência da computação e a inteligência artificial. O autor apresenta uma família de estratégias inteligentes chamadas aprendizado regularizado. Pense nestas estratégias como uma forma de um jogador olhar para os seus erros e recompensas passados, mas com um "empurrão gentil" para evitar que ele fique obcecado por um movimento específico. É como um estudante estudando para uma prova: ele revisa seus exames antigos (o passado), mas também se força a tentar algumas novas questões de prática (exploração) para não ficar preso na resposta errada. O artigo pergunta: se todos usarem estas regras de aprendizado inteligentes e ligeiramente cautelosas, encontrarão eventualmente uma paz estável (um equilíbrio de Nash) ou ficarão presos num ciclo de caos?

A História do Aprendiz Inteligente

Para entender a jornada do artigo, primeiro temos que conhecer o nosso protagonista: O Aprendiz. Imagine que você está jogando um videogame contra um oponente misterioso que você não consegue ver. Você não conhece as regras do jogo e não sabe se o seu oponente está tentando vencer você ou apenas brincando. A cada turno, você escolhe um movimento, recebe uma pontuação e então tem que decidir o que fazer a seguir.

Nos velhos tempos, os cientistas pensavam que a melhor maneira de jogar era o Jogo Fictício (Fictitious Play). Isso é como um estudante que olha para cada prova que já fez e diz: "Ok, eu tirei um A nas terças-feiras, então farei exatamente o que fiz nas terças-feiras para sempre". O artigo mostra que isso é um pouco rígido demais. Se o jogo mudar mesmo que um pouco, essa estratégia de "imitador" pode ficar presa em um loop, oscilando entre duas escolhas ruins para sempre, sem perceber que existe uma opção melhor. É como um cachorro perseguindo a própria cauda; ele está se movendo, mas não está chegando a lugar nenhum.

O artigo propõe uma maneira melhor: Seguir o Líder Regularizado (Follow-the-Regularized-Leader - FTRL). Em vez de apenas copiar cegamente o passado, este método adiciona um "regularizador". Pense nisso como um colchão de segurança ou um filtro de curiosidade. Ele diz: "Ei, aquele movimento que você fez da última vez foi bom, mas talvez não aposte sua vida inteira nele. Vamos manter um pouco de suas opções abertas, só por precaução". Isso evita que o aprendiz ganhe confiança rápido demais e fique preso em um loop suboptimal.

Os Dois Mundos do Aprendizado

O artigo divide a história em dois mundos diferentes para ver como este novo método funciona.

Mundo 1: O Jogador Solo (O Bandido)
Primeiro, o autor observa um único jogador enfrentando um ambiente imprevisível (como uma máquina caça-níqueis que muda suas regras de pagamento aleatoriamente). Aqui, o objetivo é minimizar o Arrependimento (Regret). O arrependimento é a diferença entre a pontuação que você obteve e a pontuação que você poderia ter obtido se tivesse conhecido o futuro e escolhido o movimento perfeito durante todo o tempo.
O artigo prova que, com este método de "colchão de segurança", o arrependimento do jogador cresce muito lentamente. Não é zero, mas é tão pequeno em relação ao tempo total de jogo que, a longo prazo, o jogador está fazendo quase tão bem quanto o gênio perfeito que sabia tudo desde o início. É como dizer: "Embora eu não soubesse o futuro, minha estratégia inteligente e cautelosa me impediu de cometer erros enormes".

Mundo 2: O Jogo em Grupo (O Caos)
Depois, o artigo joga todos em uma sala juntos. Agora, o ambiente não é aleatório; ele é moldado pelos outros jogadores, que também estão tentando aprender e melhorar. Este é o ambiente multiagente.
Aqui, o artigo faz a grande pergunta: se todos estiverem usando estas regras de aprendizado inteligentes e cautelosas, eles eventualmente se acalmarão e alcançarão um Equilíbrio de Nash? Um Equilíbrio de Nash é um estado onde todos estão felizes com sua escolha e ninguém quer mudar porque isso apenas os tornaria piores.

A resposta é uma mistura fascinante de "Sim, mas..." e "Depende".

A Boa Notícia: Em jogos onde os jogadores competem diretamente (como um jogo de soma zero, onde um ganha e o outro perde), o artigo mostra que, se você tirar a média de seus movimentos ao longo do tempo, eles de fato convergem para um equilíbrio de Nash. É como uma dança caótica que, quando você a desacelera e observa os passos médios, revela um ritmo perfeito.
A Conexão com o "Teorema do Folclore" (Folk Theorem): O artigo conecta este processo de aprendizado a uma ideia famosa da biologia evolutiva chamada "teorema do folclore". Na natureza, se uma espécie encontra uma maneira estável de sobreviver, ela permanece nela. O artigo mostra que, nesses jogos, se o processo de aprendizado dos jogadores se estabilizar em um ponto específico, esse ponto deve ser um equilíbrio de Nash. Além disso, se um ponto for um equilíbrio "estrito" (significando que é a única melhor escolha), os jogadores estão quase garantidos a encontrá-lo e permanecer nele, como uma bola rolando para o fundo de uma tigela profunda.
A Ressalva: O artigo também avisa que isso não acontece em todos os jogos. Em alguns cenários complexos, os jogadores podem nunca se estabilizar ou podem se estabelecer em um equilíbrio "ruim", onde todos estão presos em um loop suboptimal. O artigo descarta explicitamente a ideia de que o aprendizado sempre leva ao resultado perfeito em todas as possibilidades.

A Magia das "Caixas Pretas"

Uma das partes mais legais do artigo é como ele lida com a informação. No mundo real, você raramente sabe tudo. Você pode saber apenas a sua própria pontuação, não o que seu oponente fez ou quais eram as outras opções.
O artigo usa um truque inteligente chamado Modelo de Caixa Preta (Black-Box Model). Imagine que você é um detetive tentando adivinhar o clima. Você não tem um satélite; você tem apenas um termômetro. Você tem que construir um modelo de "caixa preta" para adivinhar o quadro completo do clima baseado apenas nesse número.
O artigo mostra que, mesmo com essa informação limitada (chamada de feedback de bandido/bandit feedback), o método de aprendizado regularizado ainda funciona. É como o detetive usando suas pistas limitadas para eventualmente descobrir que a tempestade está chegando, mesmo sem um satélite. O artigo prova que, mesmo quando os jogadores veem apenas suas próprias recompensas e têm que adivinhar o resto, a estratégia do "colche de segurança" ainda os ajuda a evitar o desastre e a se mover em direção à estabilidade.

O Veredito

Então, qual é a conclusão final? O artigo não afirma ter resolvido todos os jogos do universo. Não diz que algoritmos de aprendizado tornarão o mundo uma utopia. Em vez disso, fornece um mapa unificado para entender como o aprendizado funciona.

Ele nos diz que:

O Arrependimento é uma boa bússola: Se você conseguir aprender a minimizar o arrependimento (evitando grandes erros), estará no caminho certo.
A Cautela é fundamental: Adicionar um pouco de "regularização" (manter as opções abertas) evita que o sistema fique preso em loops.
A Estabilidade é possível: Em muitos tipos importantes de jogos, se todos usarem estas regras de aprendizado inteligentes, eles eventualmente encontrarão um equilíbrio estável onde ninguém quer mudar.

O artigo é uma celebração da ideia de que você não precisa ser um gênio perfeito para jogar um bom jogo. Você só precisa de uma estratégia que aprenda com o passado, permaneça curioso sobre o futuro e saiba quando ser um pouco cauteloso. Ele transforma a dança caótica da teoria dos jogos em uma história de como agentes imperfeitos podem, através do aprendizado inteligente, tropeçar em direção a um equilíbrio perfeito.

Resumo Técnico: Arrependimento, Equilíbrio e Aprendizado em Jogos: Um Guia Orientado

1. Definição do Problema e Contexto

O artigo aborda a questão fundamental da racionalidade "como se" (as-if) na teoria dos jogos não cooperativos: será que agentes egoístas e míopes, engajados em interações repetidas sem conhecimento total das regras ou da estrutura do jogo, eventualmente aprendem a agir como se fossem racionais? Especificamente, o processo de aprendizado leva a um equilíbrio de Nash (EN)?

O autor observa que os postulados de racionalidade padrão (conhecimento perfeito, capacidade de computação de equilíbrio) raramente são atendidos em aplicações modernas como aprendizado de máquina e ciência de dados. Além disso, a complexidade computacional de encontrar um EN é PPAD-completa, e Hart & Mas-Colell estabeleceram que nenhum dinamismo não acoplado converge para um EN em todos os jogos. Consequentemente, o foco muda da existência do equilíbrio para a caracterização do comportamento de longo prazo de políticas de aprendizado específicas.

O artigo distingue dois cenários:

Agente Único (Unilateral/Open-Loop): Um aprendiz enfrenta um ambiente arbitrário, não estacionário e potencialmente adversário (Bandidos Multibraços Adversários). O objetivo é minimizar o arrependimento (regret) (a diferença entre o ganho realizado e a melhor ação fixa em retrospectiva).
Multiagente (Teoria dos Jogos/Closed-Loop): Vários jogadores interagem, moldando o ambiente uns para os outros. O objetivo é determinar se a sequência de jogo induzida converge para um EN ou exibe outras propriedades de estabilidade.

2. Metodologia: Aprendizado Regularizado

O artigo propõe um framework unificado chamado Aprendizado Regularizado, que generaliza diversos algoritmos existentes (ex: Jogo Fictício, Follow-the-Leader, Pesos Exponenciais, EXP3, Tsallis-INF).

O Modelo Central

O processo de aprendizado é modelado como uma atualização de dois estágios para cada jogador $i$ no tempo $t$ :

Agregação de Pontuação: Os jogadores atualizam um vetor de pontuação agregada $y_{i,t}$ com base no feedback observado (ganhos).
$y_{i, t+1} = y_{i, t} + \gamma_t \hat{v}_{i, t}$
Aqui, $\hat{v}_{i, t}$ é um "modelo de caixa-preta" (surrogate) do vetor de ganho misto $v_i(x_t)$ , que pode incluir ruído ou viés dependendo do tipo de feedback. $\gamma_t$ é o tamanho do passo (step-size).
Seleção de Estratégia: Os jogadores mapeiam pontuações em estratégias mistas $x_{i, t}$ via um mapa de escolha regularizado $Q_i$ :
$x_{i, t+1} = Q_i(y_{i, t+1}) = \arg\max_{x \in X_i} \{ \langle y_{i, t+1}, x \rangle - h_i(x) \}$
onde $h_i$ é um regularizador estritamente convexo (ex: entropia negativa para Pesos Exponenciais, quadrática para Projeções Preguiçosas/Lazy Projections).

Modelos de Feedback

O framework acomoda várias estruturas de informação via o modelo de caixa-preta $\hat{v}_t = v(x_t) + Z_t$ , onde $Z_t$ representa o erro:

Oráculo (Informação Total): Os jogadores observam o vetor de ganho completo (ou uma estimativa não viesada).
Bandit (Baseado em Ganho): Os jogadores observam apenas o ganho realizado de sua ação escolhida. Para construir um vetor de estimativa, o artigo utiliza Estimadores de Peso de Importância (IWE), frequentemente combinados com exploração explícita (misturando a estratégia com uma distribuição uniforme) para controlar a variância.

3. Principais Contribuições e Resultados

A. Limites de Arrependimento de Agente Único

No cenário de bandido multibraços adversários, o artigo deriva limites de arrependimento para o Aprendizado Regularizado (FTRL).

Mecanismo: A regularização evita o comportamento de "ping-pong" do Follow-the-Leader (FTL) não regularizado, que sofre de arrependimento linear contra sequências adversárias.
Resultado: Para um regularizador $K$ -fortemente convexo e ganhos limitados, o arrependimento esperado é limitado por:
$E[\text{Reg}(T)] \leq \frac{H}{\eta} + \frac{\eta M^2 T}{2K}$
Otimizando a taxa de aprendizado $\eta$ resulta em um limite de arrependimento de $O(\sqrt{T})$ .
Algoritmos Específicos:
- Regularizador Quadrático: Resulta em arrependimento $O(\sqrt{AT})$ no cenário $L_\infty$ .
- Pesos Exponenciais (Regularizador de Entropia): Resulta em arrependimento $O(\sqrt{T \log A})$ , que é logarítmico no número de ações $A$ .
- Cenário Bandit (EXP3 & Tsallis-INF): Usando IWE com exploração explícita, o artigo deriva limites mostrando que o feedback de bandido incorre em uma penalidade (tipicamente $O(T^{2/3}$ com análise simples, ou $O(\sqrt{T})$ com análise mais rigorosa para Tsallis-INF) em comparação com a informação total.

B. Convergência Multiagente em Jogos Soma-Zero

Para jogos de soma zero de dois jogadores, o artigo estabelece a convergência da média ergódica do jogo para o conjunto de Equilíbrios de Nash.

Resultado: Sob esquemas apropriados de tamanho de passo e exploração, a função de gap esperado (uma medida de distância ao EN) converge para zero a uma taxa de $\tilde{O}(T^{-1/2})$ para métodos de oráculo e $\tilde{O}(T^{-1/3})$ para métodos de bandido (com potenciais melhorias para $T^{-1/2}$ via argumentos de norma local).
Significância: Isso fornece uma garantia de convergência quantitativa para o aprendizado regularizado em jogos soma-zero, preenchendo a lacuna entre os resultados clássicos de Jogo Fictício e o aprendizado online moderno.

C. O "Teorema do Folk" do Aprendizado Regularizado

O artigo deriva um conjunto de resultados de estabilidade que ligam propriedades de aprendizado dinâmico a conceitos de equilíbrio estratégico, analogamente ao teorema do folk da teoria dos jogos evolutiva (Dinâmica do Replicador).

Propriedade (P1): Se a sequência de jogo converge para um ponto $x^*$ com probabilidade positiva, então $x^*$ é um equilíbrio de Nash.
Propriedade (P2): Se um ponto $x^*$ é estocasticamente estável (permanece próximo de $x^*$ com alta probabilidade se iniciado por perto), ele é um equilíbrio de Nash.
Propriedade (P3): Equilíbrios de Nash estritos são estocasticamente assintoticamente estáveis (atraentes com alta probabilidade).
Novidade: Diferente dos resultados de aproximação estocástica padrão que muitas vezes exigem tamanhos de passo que tendem a zero, esses resultados mantêm-se mesmo com tamanhos de passo constantes para equilíbrios estritos, baseando-se no fato de que equilíbrios estritos são pontos de canto do espaço de estratégias.

4. Significância e Escopo

O artigo posiciona-se como um "guia orientado" e um ponto de entrada, em vez de um levantamento abrangente. Sua principal significância reside em:

Unificação: Fornece um framework analítico único (Aprendizado Regularizado) que engloba diversos algoritmos (Jogo Fictício, FTRL, EXP3, Tsallis-INF) e tipos de feedback (Oráculo, Bandit).
Análise de Racionalidade: Esclarece a relação entre a minimização de arrependimento e a convergência de equilíbrio, demonstrando que, embora o jogo sem arrependimento (no-regret play) não garanta o equilíbrio em todos os jogos, o aprendizado regularizado possui fortes propriedades de racionalidade (convergência para EN em jogos soma-zero, estabilidade de EN estritos).
Clareza Metodológica: Ao utilizar ferramentas de análise convexa (acoplamento de Fenchel, dualidade de convexidade forte) e aproximação estocástica, o artigo oferece uma narrativa coerente para derivar limites de arrependimento e taxas de convergência.

O autor nota explicitamente as limitações: o artigo omite a extensa literatura sobre equilíbrios correlacionados grosseiros (coarse correlated equilibria), regret-matching, calibração, aprendizado por tentativa e erro, e modelos de tempo contínuo para manter uma narrativa focada e autossuficiente. A análise é restrita a jogos finitos (embora observada sua extensão para configurações de desigualdade variacional) e não cobre em profundidade variantes baseadas em extrapolação (ex: Extra-Gradient).