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

Formulación del Problema
El artículo aborda el desafío del equipo de múltiples humanos y múltiples robots en línea, un escenario donde un aprendiz debe asignar un conjunto fijo de $K$ robots con capacidades desconocidas a conjuntos variables de $M$ agentes humanos a lo largo de $T$ rondas. El objetivo es maximizar la recompensa acumulada generada por estos equipos de humanos y robots. El problema se enmarca dentro de un marco de bandit de emparejamiento lineal. La dificultad central reside en dos aspectos: el "espacio de brazos intratable", donde tratar cada emparejamiento único como un brazo de bandit distinto conduce a un crecimiento exponencial, y la "complejidad combinatoria", donde las restricciones de emparejamiento interconectan las recompensas y complican la optimización.

Los autores asumen una estructura de recompensa lineal donde la recompensa esperada de un equipo formado por un agente humano $m$ (con un vector de características conocido $X_{m,t} \in \mathbb{R}^d$) y un robot $k$ (con un vector de características desconocido $\theta_k \in \mathbb{R}^d$) viene dada por el producto interno $X_{m,t}^\top \theta_k$. Mientras que las características de los humanos son observables (derivadas de perfiles o contexto de la tarea), las características de los robots son desconocidas debido a la complejidad y la falta de transparencia en los sistemas de IA avanzados. El aprendiz observa las características de los humanos que llegan, selecciona un emparejamiento (una función de inyección de humanos a robots) y recibe recompensas con ruido.

Metodología: Algoritmo LinMatch
Para resolver esto, los autores proponen LinMatch, un algoritmo de aprendizaje en línea basado en el principio de "Optimismo ante la Incertidumbre" (OFU, por sus siglas en inglés). El algoritmo opera en rondas y consta de los siguientes pasos:

1. Construcción del Intervalo de Confianza: Utilizando regresión de Ridge, LinMatch estima los vectores de características desconocidos $\theta_k$ para cada robot. Mantiene una matriz de covarianza $V_{k,t}$ y una suma ponderada de recompensas $H_{k,t}$ para cada robot basada en las asignaciones históricas. Esto permite la construcción de un intervalo de confianza elipsoidal $\hat{\Theta}_{k,t}$ para cada $\theta_k$, asegurando que el parámetro real se encuentre dentro del intervalo con alta probabilidad.
2. Emparejamiento Optimista: En cada ronda, el algoritmo computa un emparejamiento "optimista". En lugar de utilizar las estimaciones puntuales de $\theta_k$, selecciona los vectores de parámetros dentro de los intervalos de confianza que maximizan la recompensa total esperada.
3. Resolución Eficiente mediante Programación Lineal: Una contribución técnica clave es la reformulación del problema de emparejamiento optimista. Los autores demuestran que el programa de enteros mixtos requerido para encontrar el emparejamiento que maximiza la suma de los productos internos sobre los conjuntos de confianza puede desacoplarse. Al definir estimaciones de recompensa optimistas $\tilde{y}_{mk,t}$ para cada par humano-robot, el problema se reduce a un problema estándar de emparejamiento de peso máximo en un grafo bipartito. Este puede resolverse eficientemente en un tiempo de $O(K^3)$ utilizando el algoritmo húngaro.

Contribuciones Clave y Resultados Teóricos
El artículo realiza dos contribuciones primarias:

1. Reformulación Algorítmica: Reformula el problema de emparejamiento optimista en cada ronda como un programa lineal de emparejamiento de peso máximo, lo que lo hace computacionalmente tratable mediante el algoritmo húngaro.
2. Límites de Regret Ajustados: Los autores proporcionan garantías teóricas rigurosas para LinMatch.
   • Límite Superior: Establecen un límite superior independiente de la instancia del regret acumulado de $\tilde{O}(d\sqrt{MKT})$, donde $d$ es la dimensión de las características, $M$ es el número de humanos, $K$ es el número de robots y $T$ es el horizonte de tiempo.
   • Límite Inferior: Prueban un límite inferior minimax de $\Omega(d\sqrt{MKT})$ para cualquier política de emparejamiento en este entorno.
   • Optimalidad: El emparejamiento de los límites superior e inferior establece una tasa de regret óptima y ajustada de $\tilde{\Theta}(d\sqrt{MKT})$. Esto demuestra que LinMatch logra el regret alcanzable estrictamente óptimo con respecto a todos los parámetros del problema ($T, d, M, K$).

Resultados Experimentales
Los autores validan LinMatch mediante simulaciones numéricas con $K=20$ robots y $M=10$ humanos.

• Comparación con ETC: LinMatch se compara con un algoritmo de Explorar-Luego-Comprometerse (ETC). Aunque ETC puede lograr un regret sublineal con una fase de exploración de longitud óptima, sufre un regret lineal si la exploración es insuficiente. LinMatch demuestra un rendimiento más consistente con un intervalo de confianza más estrecho en comparación con ETC.
• Sensibilidad de la Regularización: Los experimentos variando el parámetro de regularización $\lambda$ muestran que, si bien el límite superior teórico requiere $\lambda \ge L^2$, en la práctica, valores más pequeños (por ejemplo, $\lambda=1$) a menudo producen un menor regret, lo que sugiere que la condición teórica es conservadora.

Significancia y Alcance
El artículo afirma que LinMatch es el primer trabajo que muestra que la tasa de regret alcanzable óptima e independiente de la instancia para problemas de emparejamiento con una estructura de bandit lineal es precisamente $\tilde{\Theta}(d\sqrt{MKT})$. El enfoque propuesto está diseñado para ser aplicable más allá del equipo humano-robot a cualquier problema de emparejamiento centralizado con características lineales, como la asignación de vivienda y los sistemas de recomendación. El trabajo destaca que, al aprovechar la estructura lineal y la optimización combinatoria eficiente, se puede superar la complejidad exponencial típicamente asociada con el emparejamiento multi-agente en entornos de aprendizaje en línea.