💬 NLP

Online Learning and Equilibrium Computation with Ranking Feedback

Este artigo investiga o aprendizado online com feedback baseado em rankings em vez de utilidades numéricas, demonstrando que a sublinearidade do arrependimento é geralmente impossível sem suposições adicionais, mas propondo novos algoritmos que alcançam esse objetivo sob condições específicas de variação de utilidade ou feedback de tempo médio, permitindo o cálculo de equilíbrios em jogos e validando sua eficácia em tarefas de roteamento de modelos de linguagem.

Autores originais: Mingyang Liu, Yongshan Chen, Zhiyuan Fan, Gabriele Farina, Asuman Ozdaglar, Kaiqing Zhang

Publicado 2026-03-20

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Mingyang Liu, Yongshan Chen, Zhiyuan Fan, Gabriele Farina, Asuman Ozdaglar, Kaiqing Zhang

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 que você é um chef de cozinha tentando descobrir qual é o prato favorito dos seus clientes. No mundo ideal da inteligência artificial, os clientes diriam exatamente: "Este prato vale 9,5 pontos, aquele vale 3". Mas, na vida real, as pessoas são mais relutantes em dar notas exatas. Elas preferem dizer: "Eu prefiro o prato A ao B, e o B ao C".

Este artigo, escrito por pesquisadores do MIT e outras universidades, trata exatamente desse desafio: como aprender e tomar decisões inteligentes quando só recebemos "rankings" (ordens de preferência) e não notas numéricas.

Aqui está a explicação simplificada, usando analogias do dia a dia:

1. O Problema: O Chef Cego

Na maioria dos sistemas de aprendizado de máquina, o computador recebe um "número" de volta (como uma nota de 1 a 10) para saber se fez algo bom ou ruim. Isso é fácil para o algoritmo.

Mas em muitas situações reais (como recomendações de filmes, casamentos em apps de namoro ou roteamento de modelos de linguagem), as pessoas só dão comparações.

Exemplo: Um app de namoro mostra 3 candidatos. O usuário diz: "Gosto mais do João do que do Pedro, e do Pedro mais do que do Carlos". O app não sabe quanto o usuário gostou, apenas a ordem.

O artigo pergunta: É possível aprender a fazer as melhores escolhas apenas com essa lista de preferências?

2. A Descoberta Surpreendente: Nem Sempre é Fácil

Os autores descobriram que, em alguns cenários, a resposta é um sonoro "Não".

A Analogia do "Gosto Instantâneo": Imagine que o cliente muda de opinião a cada segundo de forma caótica. Se você só recebe a ordem de preferência daquele momento exato, o sistema fica cego. É como tentar adivinhar o clima olhando apenas para uma nuvem que passa rápido demais; o sistema não consegue distinguir se a nuvem é de chuva ou de sol porque a informação é muito ruidosa.
O Perigo da "Certidão Absoluta": Se o sistema de ranking for muito preciso (sempre escolhe o melhor sem erro), o algoritmo também falha. É como um professor que só diz "Certo" ou "Errado" sem dar dicas. Se você errar, não sabe quão errado foi, então não consegue aprender a corrigir o caminho. O artigo prova matematicamente que, nessas condições extremas, o aprendizado é impossível.

3. A Solução: O Algoritmo "Detetive"

Mas não se desespere! Os autores criaram novos algoritmos que funcionam, desde que assumamos que o mundo não muda de forma totalmente caótica.

A Analogia do "Gosto que Muda Devagar": Eles assumem que as preferências dos clientes mudam de forma suave. Se hoje o cliente gosta de pizza, amanhã ele ainda gosta de pizza, talvez com um leve ajuste.
O Truque do "Sliding Window" (Janela Deslizante): O algoritmo age como um detetive que não olha apenas para o último caso, mas analisa os últimos 100 rankings. Ele usa estatística para "adivinhar" os números que estão escondidos atrás das preferências.
- Se o cliente diz "A > B > C", o algoritmo calcula: "Ok, A deve ter uma pontuação alta, B média e C baixa".
- Ele faz isso repetidamente, ajustando suas estimativas como quem afina um rádio até encontrar a estação clara.

4. O Cenário de Jogos: Encontrando o Equilíbrio

O artigo também olha para situações onde várias pessoas jogam juntas (como um jogo de xadrez ou um mercado de ações).

A Analogia do "Jogo de Tabuleiro": Se todos os jogadores usarem esse novo algoritmo, eles acabam aprendendo a jogar de forma que ninguém queira mudar de estratégia sozinho. Isso é chamado de Equilíbrio.
Imagine um restaurante onde todos os clientes aprendem a pedir o prato que mais agrada ao grupo, sem precisar de um gerente mandando. O sistema encontra um ponto de harmonia natural.

5. O Teste Prático: O Roteador de Inteligência Artificial

Para provar que isso funciona, eles testaram em um cenário real: Roteamento de Modelos de Linguagem (LLMs).

O Cenário: Imagine que você tem vários robôs (GPT-4, Llama, etc.) e um usuário faz uma pergunta. O sistema precisa decidir qual robô responder.
O Desafio: O usuário não dá uma nota. Ele apenas diz: "A resposta do Robô A foi melhor que a do Robô B".
O Resultado: O algoritmo aprendeu rapidamente a enviar as perguntas para o robô certo, minimizando erros e agradando o usuário, mesmo sem nunca ter visto uma nota numérica.

Resumo em uma Frase

Este papel nos ensina que, mesmo sem números exatos, podemos ensinar máquinas a tomar decisões ótimas, desde que usemos estatística inteligente para transformar "gosto mais de A que de B" em conhecimento útil, e que isso funciona maravilhosamente bem em jogos e recomendações do mundo real.

É como ensinar um cachorro a fazer truques não dizendo "faça 5 sentar", mas apenas dizendo "isso foi melhor do que aquilo", e o cachorro, com o tempo, aprende a fazer o truque perfeito.

Resumo Técnico: Aprendizado Online e Computação de Equilíbrio com Feedback de Classificação

1. Problema e Motivação

O artigo aborda o problema de aprendizado online em ambientes não estocásticos e potencialmente adversários, onde o agente (aprendiz) não recebe feedback numérico direto (vetores de utilidade), mas sim feedback de classificação (ranking) sobre um conjunto de ações propostas.

Contexto: Em muitas aplicações do mundo real, como sistemas de recomendação com humanos no loop (RLHF) ou plataformas de encontros, é mais fácil para os usuários classificar opções do que atribuir pontuações numéricas precisas. Além disso, restrições de privacidade podem impedir o acesso a utilidades numéricas.
Desafio: A maioria dos algoritmos clássicos de aprendizado online (como aqueles que garantem "no-regret") depende de feedback numérico. O uso de apenas rankings introduz incerteza e perda de informação, tornando a minimização de arrependimento (regret) desafiadora.
Objetivo: Determinar quando é possível minimizar o arrependimento externo (external regret) com feedback de classificação e desenvolver algoritmos que, ao serem usados por múltiplos jogadores em um jogo, converjam para um Equilíbrio Correlacionado Aproximado (CCE).

2. Modelos de Feedback e Configurações

Os autores definem dois tipos principais de mecanismos de ranking baseados no modelo Plackett-Luce (PL), que utiliza um parâmetro de temperatura $\tau$ para modelar a incerteza:

InstUtil Rank (Utilidade Instantânea): O ranking é gerado com base na utilidade instantânea $u(t)$ no tempo $t$ . É relevante para cenários onde o feedback é "one-shot" (ex: um cliente que chega, classifica e sai).
AvgUtil Rank (Utilidade Média no Tempo): O ranking é gerado com base na utilidade média acumulada até o tempo $t$ ( $u_{avg}(t) = \frac{1}{t}\sum_{s=1}^t u(s)$ ). É relevante para agentes com memória ou usuários de longo prazo.

Além disso, consideram dois cenários de feedback:

Full-Information: O agente propõe todas as ações possíveis.
Bandit: O agente propõe apenas um subconjunto $K$ de ações.

3. Resultados de Impossibilidade (Lower Bounds)

Uma parte crucial do trabalho é estabelecer limites inferiores rigorosos, mostrando que o aprendizado eficiente é impossível em certas configurações sem suposições adicionais:

InstUtil Rank: Para qualquer temperatura $\tau$ suficientemente pequena (determinística), é impossível alcançar arrependimento sublinear (o arrependimento cresce linearmente com o tempo $T$ ). Isso ocorre porque o feedback não revela informações suficientes sobre as diferenças de utilidade entre ações quando o sistema é muito determinístico.
AvgUtil Rank:
- No cenário de Full-Information, se $\tau \le O(\frac{1}{T \log T})$ , o arrependimento mínimo é linear.
- No cenário de Bandit, se $\tau \le O(\frac{1}{\log T})$ , o arrependimento mínimo é linear.
Conclusão: Em ambientes adversários gerais, o feedback de ranking puro (especialmente com modelos determinísticos) não é suficiente para garantir aprendizado eficiente.

4. Metodologia e Algoritmos Propostos

Para superar as limitações de impossibilidade, os autores introduzem uma suposição adicional sobre a variação sublinear dos vetores de utilidade (Assunção 5.2): a soma das variações das utilidades ao longo do tempo deve crescer mais lentamente que $T$ (i.e., $O(T^q)$ com $q < 1$ ).

Com essa suposição, eles desenvolvem novos algoritmos baseados em oráculos de aprendizado no-regret (como FTRL ou PGD) combinados com estimadores de utilidade:

Estimativa de Utilidade (Algoritmo 1):
- Decompõem o ranking de $K$ ações em comparações pares (pairwise).
- Utilizam a estrutura logística do modelo Plackett-Luce para estimar as utilidades subjacentes a partir das probabilidades de ranking observadas.
- O erro de estimativa é controlado pelo tamanho da janela de observação e pela variação das utilidades.
Algoritmo para InstUtil Rank (Algoritmo 2):
- Usa a estimativa de utilidade instantânea para alimentar um oráculo de aprendizado.
- No cenário Bandit, adiciona uma taxa de exploração uniforme ( $\gamma$ ) para garantir que todas as ações sejam observadas com probabilidade positiva.
- Garante arrependimento sublinear sob a suposição de variação sublinear.
Algoritmo para AvgUtil Rank (Algoritmo 3):
- Full-Information: Mostra que, se $\tau$ for uma constante (não tendendo a zero), a suposição de variação sublinear pode ser removida. O algoritmo é estável o suficiente para lidar com utilidades arbitrariamente variáveis.
- Bandit: Utiliza uma estratégia de "blocos" (block-based) para estimar a utilidade média, equilibrando viés e variância. Requer a suposição de variação sublinear e uma condição específica sobre a taxa de variação ( $q < 1/3$ ).

5. Computação de Equilíbrio em Jogos

O artigo conecta o aprendizado online à teoria dos jogos:

Quando todos os jogadores em um jogo de forma normal (Normal-Form Game) utilizam os algoritmos propostos, o comportamento médio no tempo converge para um Equilíbrio Correlacionado Aproximado (CCE).
O erro de aproximação ( $\epsilon$ ) depende do arrependimento individual dos jogadores.
Para garantir a convergência no cenário adversário, os algoritmos dos jogadores devem satisfazer uma condição de variação sublinear nas estratégias (Assunção 8.1), que é naturalmente satisfeita por algoritmos como FTRL com regularização forte.

6. Resultados Experimentais

Os autores validam seus métodos em duas frentes:

Jogos Gerados Aleatoriamente: Demonstram que o arrependimento e a exploração (exploitability) diminuem sublinearmente ao longo do tempo em diversos cenários de feedback (Full-Info e Bandit) e temperaturas $\tau$ .
Roteamento de Grandes Modelos de Linguagem (LLM):
- Cenário: Um servidor roteia consultas de usuários para diferentes modelos de LLM (ex: GPT-4o, Llama, Phi).
- Feedback: O usuário classifica as respostas geradas por $K$ modelos selecionados.
- Resultado: O algoritmo aprende rapidamente a rotear para o modelo que maximiza a satisfação do usuário ao longo do tempo, mesmo sem conhecer as utilidades numéricas exatas, demonstrando eficácia prática.

7. Contribuições Principais e Significância

Limites Teóricos: Estabelece limites inferiores rigorosos mostrando que o aprendizado com ranking é intrinsecamente difícil em ambientes adversários sem restrições na variação das utilidades ou com modelos muito determinísticos.
Algoritmos Robustos: Desenvolve a primeira família de algoritmos com garantias de no-regret para aprendizado online com feedback de ranking em ambientes não estocásticos.
Conexão com Equilíbrio: Demonstra que é possível computar equilíbrios de jogos (CCE) usando apenas feedback de ranking, estendendo resultados clássicos de aprendizado no-regret para cenários de preferência humana.
Aplicabilidade Prática: Oferece uma solução teórica e prática para problemas de RLHF e sistemas de recomendação onde a obtenção de scores numéricos é inviável, validado em tarefas de roteamento de LLM.

Em suma, o trabalho preenche uma lacuna fundamental entre o aprendizado online clássico (com feedback numérico) e o aprendizado baseado em preferências (ranking), fornecendo garantias teóricas e algoritmos práticos para ambientes dinâmicos e adversários.