A Linear Matching Bandit Approach to Online Multi-Human Multi-Robot Teaming

Formulação do Problema
O artigo aborda o desafio do agrupamento (teaming) online de múltiplos humanos e múltiplos robôs, um cenário onde um aprendiz deve atribuir um conjunto fixo de $K$ robôs com capacidades desconhecidas a conjuntos variáveis de $M$ agentes humanos ao longo de $T$ rodadas. O objetivo é maximizar a recompensa cumulativa gerada por essas equipes de humanos e robôs. O problema é estruturado dentro de um framework de bandit de correspondência linear (linear matching bandit). A dificuldade central reside em dois aspectos: o "espaço de braços intratável", onde tratar cada correspondência única como um braço de bandit distinto leva a um crescimento exponencial, e a "complexidade combinatória", onde as restrições de correspondência interconectam as recompensas e complicam a otimização.

Os autores assumem uma estrutura de recompensa linear onde a recompensa esperada de uma equipe formada por um agente humano $m$ (com vetor de características conhecido $X_{m,t} \in \mathbb{R}^d$) e um robô $k$ (com vetor de características desconhecido $\theta_k \in \mathbb{R}^d$) é dada pelo produto interno $X_{m,t}^\top \theta_k$. Embora as características humanas sejam observáveis (derivadas de perfis ou contexto da tarefa), as características dos robôs são desconhecidas devido à complexidade e falta de transparência em sistemas de IA avançados. O aprendiz observa as características dos humanos que chegam, seleciona uma correspondência (uma função de injeção de humanos para robôs) e recebe recompensas ruidosas.

Metodologia: Algoritmo LinMatch
Para resolver isso, os autores propõem o LinMatch, um algoritmo de aprendizado online baseado no princípio do "Otimismo na Presença de Incerteza" (Optimism in the Face of Uncertainty - OFU). O algoritmo opera em rodadas e consiste nas seguintes etapas:

1. Construção do Intervalo de Confiança: Usando regressão ridge, o LinMatch estima os vetores de características desconhecidos $\theta_k$ para cada robô. Ele mantém uma matriz de covariância $V_{k,t}$ e uma soma ponderada de recompensas $H_{k,t}$ para cada robô baseada em atribuições históricas. Isso permite a construção de um intervalo de confiança elipsoidal $\hat{\Theta}_{k,t}$ para cada $\theta_k$, garantindo que o parâmetro real esteja dentro do intervalo com alta probabilidade.
2. Correspondência Otimista: Em cada rodada, o algoritmo computa uma correspondência "otimista". Em vez de usar as estimativas pontuais de $\theta_k$, ele seleciona os vetores de parâmetros dentro dos intervalos de confiança que maximizam a recompensa total esperada.
3. Resolução Eficiente via Programação Linear: Uma contribuição técnica fundamental é a reformulação do problema de correspondência otimista. Os autores demonstram que o programa de números inteiros mistos necessário para encontrar a correspondência que maximiza a soma dos produtos internos sobre os conjuntos de confiança pode ser desacoplado. Ao definir estimativas de recompensa otimistas $\tilde{y}_{mk,t}$ para cada par humano-robô, o problema reduz-se a um problema padrão de correspondência de peso máximo em um grafo bipartido. Isso pode ser resolvido eficientemente em tempo $O(K^3)$ usando o algoritmo Húngaro.

Principais Contribuições e Resultados Teóricos
O artigo apresenta duas contribuições primárias:

1. Reformulação Algorítmica: Ele recastea o problema de correspondência otimista em cada rodada como um programa linear de correspondência de peso máximo, tornando-o computacionalmente tratável via algoritmo Húngaro.
2. Limites de Regret Estritos (Tight Regret Bounds): Os autores estabelecem garantias teóricas rigorosas para o LinMatch.
   • Limite Superior: Eles estabelecem um limite superior independente da instância do regret cumulativo de $\tilde{O}(d\sqrt{MKT})$, onde $d$ é a dimensão das características, $M$ é o número de humanos, $K$ é o número de robôs e $T$ é o horizonte de tempo.
   • Limite Inferior: Eles provam um limite inferior minimax de $\Omega(d\sqrt{MKT})$ para qualquer política de correspondência neste cenário.
   • Otimalidade: O ajuste entre os limites superior e inferior estabelece uma taxa de regret ótima e estrita de $\tilde{\Theta}(d\sqrt{MKT})$. Isso demonstra que o LinMatch alcança o regret perfeitamente ótimo alcançável em relação a todos os parâmetros do problema ($T, d, M, K$).

Resultados Experimentais
Os autores validam o LinMatch através de simulações numéricas com $K=20$ robôs e $M=10$ humanos.

• Comparação com ETC: O LinMatch é comparado com um algoritmo Explore-Then-Commit (ETC). Embora o ETC possa alcançar um regret sublinear com uma fase de exploração de comprimento ótimo, ele sofre de regret linear se a exploração for insuficiente. O LinMatch demonstra um desempenho mais consistente com um intervalo de confiança mais estreito em comparação ao ETC.
• Sensibilidade à Regularização: Experimentos variando o parâmetro de regularização $\lambda$ mostram que, embora o limite superior teórico exija $\lambda \ge L^2$, na prática, valores menores (por exemplo, $\lambda=1$) frequentemente produzem um regret menor, sugerindo que a condição teórica é conservadora.

Significância e Escopo
O artigo afirma que o LinMatch é o primeiro trabalho a mostrar que a taxa de regret ótima alcançável e independente da instância para problemas de correspondência com uma estrutura de bandit linear é precisamente $\tilde{\Theta}(d\sqrt{MKT})$. A abordagem proposta foi desenhada para ser aplicável além do agrupamento humano-robô para qualquer problema de correspondência centralizada com características lineares, como alocação de habitação e sistemas de recomendação. O trabalho destaca que, ao aproveitar a estrutura linear e a otimização combinatória eficiente, é possível superar a complexidade exponencial tipicamente associada ao agrupamento de múltiplos agentes em configurações de aprendizado online.