Resumo Técnico: Algoritmos de Bandido Adaptativos para Mercados de Correspondência Contextual

Formulação do Problema

Este artigo investiga o problema de bandidos de múltiplos braços contextuais em mercados de correspondência de dois lados. O mercado consiste em $N$ jogadores e $K$ braços (onde $N \le K$). O desafio central reside na natureza dinâmica das preferências dos jogadores, que são modeladas por meio de uma função de utilidade contextual linear: $U_{i,j}(t) = \theta_i^\top x_j(t)$. Aqui, $\theta_i$ representa um vetor de preferências fixo e desconhecido para o jogador $i$, e $x_j(t)$ é um vetor de contexto observado para o braço $j$ no tempo $t$.

Diferentemente de configurações tradicionais com preferências estáticas, o contexto $x_j(t)$ varia ao longo do tempo, alterando potencialmente a referência de correspondência estável subjacente. O objetivo é projetar um algoritmo online que emparelhe jogadores a braços para minimizar o arrependimento estável ótimo para o jogador. Este arrependimento é definido como a diferença cumulativa entre a utilidade que um jogador recebe sob o emparelhamento do algoritmo e a utilidade que receberia sob o emparelhamento estável ótimo para o jogador (o melhor emparelhamento estável para aquele jogador) dadas as utilidades verdadeiras em cada rodada.

O artigo aborda dois cenários distintos quanto à geração de contexto:

1. Contextos Estocásticos: Os contextos são extraídos i.i.d. de uma distribuição fixa, mas desconhecida.
2. Contextos Adversariais: Os contextos podem ser arbitrários e potencialmente escolhidos por um adversário adaptativo, representando ambientes não estacionários de pior caso.

Metodologia

Os autores propõem algoritmos totalmente adaptativos que não requerem conhecimento prévio da lacuna mínima de preferência ou da estrutura de covariância dos contextos. Ambos os algoritmos empregam um esquema de transição de fase adaptativo em lotes, alternando entre exploração (refinamento de estimativas de parâmetros) e exploração (realização de emparelhamentos estáveis).

1. Cenário Estocástico: Equilíbrio de Arrependimento Adaptativo em Lotes (BARB)

Para o cenário estocástico, os autores introduzem o BARB, que opera em lotes.

• Estimação Adaptativa da Lacuna: O algoritmo mantém uma lacuna mínima de preferência candidata $\Delta_k$, inicializada com um valor de entrada e reduzida por um fator de $\sqrt{2}$ em cada lote subsequente. Isso permite que o algoritmo aproxime adaptativamente a dificuldade real do problema sem conhecer a lacuna verdadeira previamente.
• Exploração vs. Exploração:
  • Exploração: Se a norma de Mahalanobis de um vetor de contexto $\|x_j(t)\|_{V_i(t)^{-1}}$ exceder um limiar $\xi_k$, o algoritmo entra em uma fase de exploração. Ele constrói um grafo bipartido de pares de alta incerteza e realiza um Emparelhamento de Cardinalidade Máxima para coletar amostras informativas para atualizações de regressão ridge.
  • Exploração: Se a incerteza for baixa, o algoritmo utiliza o algoritmo Gale-Shapley (GS) baseado em utilidades estimadas. Ele monitora a sobreposição dos intervalos de confiança para as utilidades estimadas. Se as sobreposições forem excessivas (indicando que a estimativa de lacuna atual $\Delta_k$ é muito grande), o lote termina e o algoritmo prossegue para o próximo lote com uma estimativa de lacuna menor.
• Garantias Teóricas: Sob suposições leves, o BARB alcança um limite superior de arrependimento polilogarítmico dependente da instância de $\tilde{O}(\log^2 T / \Delta_{\min}^2)$. Além disso, sob a condição de que a matriz de covariância do contexto tenha um autovalor mínimo estritamente positivo, o limite melhora para $O(\log T / \Delta_{\min}^2)$. No regime assintótico, o artigo estabelece um limite inferior de arrependimento independente da instância e apertado de $\tilde{\Theta}(T^{2/3})$.

2. Cenário Adversarial: Oráculo Adaptativo de Explorar-Escolher (AdECO)

Para o cenário adversarial, definições padrão de arrependimento tornam-se intratáveis porque um adversário pode forçar a diferença mínima de utilidade $\delta_{\min}$ a ser arbitrariamente pequena por períodos arbitrariamente longos.

• Definição Tratável de Arrependimento: Os autores propõem uma noção refinada de arrependimento que interpola entre lacunas grandes e pequenas. Quando $\delta_{\min}(t) > \Delta$, a referência é a participação estável ótima padrão para o jogador $U^*_i(t)$. Quando $\delta_{\min}(t) \le \Delta$, a referência é uma aproximação $\alpha$ da participação estável $\epsilon$-ótima $U^\epsilon_i(t)$, utilizando um oráculo de aproximação offline.
• Projeto do Algoritmo: O AdECO segue uma estrutura adaptativa semelhante ao BARB.
  • Na fase de exploração, utiliza emparelhamento de cardinalidade máxima para reduzir a incerteza.
  • Na fase de exploração, se os intervalos de confiança estiverem bem separados, utiliza o algoritmo Gale-Shapley. Se eles se sobrepuserem (indicando lacunas pequenas), invoca um oráculo de aproximação $\alpha$ (baseado em Lin et al., 2026) para gerar um emparelhamento aleatorizado que garante uma fração da participação estável ótima.
• Garantias Teóricas: O AdECO alcança um limite de arrependimento sublinear independente da instância de $O(T^{2/3})$, definindo o parâmetro algorítmico $\Delta = O(T^{-1/3})$.

3. Extensão Descentralizada

O artigo estende brevemente a estrutura do BARB para mercados descentralizados, onde os jogadores agem independentemente sem um coordenador central. Ao introduzir uma suposição sobre identificação de ambiente (classificações top-$N$ distintas para diferentes ambientes), o algoritmo descentralizado alcança a mesma ordem de arrependimento que a versão centralizada, com um termo constante adicional dependente do número de ambientes.

Principais Contribuições

1. Métricas Novas para Dificuldade do Problema:

   • Para contextos estocásticos, o artigo introduz uma lacuna mínima de preferência ($\Delta_{\min}$), definida probabilisticamente para capturar a probabilidade de pequenas diferenças de utilidade, oferecendo uma medida mais realista do que os limites inferiores determinísticos usados em trabalhos anteriores.
   • Para contextos adversariais, define uma noção tratável de arrependimento que alterna entre referências de emparelhamento estável exatas e referências de aproximação dependendo do tamanho da lacuna, permitindo garantias significativas em cenários de pior caso.

2. Algoritmos Totalmente Adaptativos:

   • Os algoritmos propostos (BARB e AdECO) são totalmente adaptativos, não requerendo conhecimento prévio da lacuna mínima de preferência ou da estrutura de covariância da distribuição de contexto. Eles ajustam dinamicamente seus trade-offs entre exploração e exploração com base nos dados observados.

3. Limites Teóricos Apertados:

   • Estocástico: O artigo fornece limites de arrependimento polilogarítmicos dependentes da instância e, sob uma suposição leve de covariância, limites logarítmicos. Crucialmente, estabelece um limite inferior de arrependimento independente da instância e correspondente de $\Omega(T^{2/3})$, provando a apertura da taxa assintótica.
   • Adversarial: Alcança um limite de arrependimento sublinear independente da instância de $O(T^{2/3})$ para a métrica de arrependimento tratável proposta.

4. Adaptação Descentralizada: O trabalho demonstra como esses mecanismos adaptativos podem ser adaptados para configurações descentralizadas com suposições adicionais mínimas.

Resultados e Significância

O artigo afirma que sua principal significância reside em abordar a complexidade introduzida por deslocamentos contextuais em mercados de correspondência. Os autores observam que deslocamentos contextuais sutis podem alterar ligeiramente a utilidade de um jogador enquanto reconfiguram completamente a referência de emparelhamento estável subjacente, potencialmente causando grandes picos de arrependimento para outros.

• Robustez: A natureza adaptativa dos algoritmos propostos permite que lidem com estruturas de covariância de contexto arbitrárias (no caso estocástico) e sequências de contexto arbitrárias (no caso adversarial), superando bases não adaptativas como ETC (Explorar-Depois-Comprometer) em cenários onde a distribuição de contexto é mal condicionada (por exemplo, autovalores mínimos pequenos).
• Apertura Teórica: A derivação de limites superiores e inferiores correspondentes ($\tilde{\Theta}(T^{2/3})$) para o arrependimento independente da instância no cenário estocástico fornece uma compreensão fundamental da dificuldade do emparelhamento contextual com preferências desconhecidas.
• Aplicabilidade Prática: Ao remover a necessidade de conhecimento prévio da distribuição do ambiente ou de parâmetros de lacuna, os algoritmos são mais adequados para aplicações do mundo real, como mercados de trabalho online, compartilhamento de viagens e correspondência de residência médica, onde a dinâmica de preferências e as distribuições de contexto são frequentemente desconhecidas e não estacionárias.

Os autores concluem que, embora o quadro atual assuma utilidades contextuais lineares, os mecanismos adaptativos desenvolvidos oferecem uma base robusta para trabalhos futuros em estruturas de mercado mais complexas.