Research map / Multi-agent systems and games / LLM agents

A Multi-Agent Conversational Bandit Approach to Online Evaluation and Selection of User-Aligned LLM Responses

AAAI 2026 · Multi-agent systems and games › LLM agents · approach: Self-evolving language agent learning · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes MACO, a multi-agent conversational bandit framework (local agents MACO-A with online elimination, cloud server MACO-S with key-term conversations) for online selection of user-aligned LLM responses, with regret bounds and experiments on StyleEval and Gretel Multilingual using Google/OpenAI embeddings and Llama-3-8B-Instruct responses.

Problem

Selecting LLM responses online from a finite candidate set while adapting to diverse user style preferences across multiple devices, where offline pointwise evaluation is costly and fixed conversation schedules are inefficient.

Approach

Combines phase-elimination linear bandits with conversational key-term queries across multiple heterogeneous agents: local agents upload eigenvectors of under-explored directions, the server maps them to key terms (replacing G-optimal design) and aggregates information matrices to estimate user preference, with adaptive rather than fixed conversation frequency.

Key results

• MACO reports cumulative regret about 8.29% lower than the best baseline (ConLinUCB-MCR) in the synthetic setting with A=40 and 4 agents.
• On StyleEval, MACO reduces regret versus the best baseline ConUCB by at least 79.56% for M=4 with Google embeddings and 71.08% with OpenAI embeddings.
• MACO without G-optimal design runs in about 2.6 s versus 9.8-14.3 s with G-optimal design and 18 s for ConLinUCB-BS, at similar average reward.

Surprising findings

• The conversational, G-optimal-free variant matches the reward of the G-optimal-design variant while being several times faster.
• Baselines' regret grows linearly with the number of agents, while MACO's scales as sqrt(M) in the reported experiments.

Limitations

• Assumes a linear reward model and a sufficiently rich key-term set covering the feature space (orthonormal-basis-like condition).
• Experiments are simulated with cosine-similarity rewards rather than real user feedback.
• Assumes synchronous communication and negligible latency between agents and server.

Experimental setup

Datasets: StyleEval Gretel Multilingual

Benchmarks: StyleEval Gretel Multilingual

Metrics: cumulative regret execution time average reward

Baselines: TRIPLE-SH LinUCB Arm-Con ConUCB ConLinUCB-BS ConLinUCB-MCR ConLinUCB-UCB

Builds on: conversational linear bandits phase elimination linear bandits (PE-Lin) ConUCB ConLinUCB

Closest papers by meaning

• Chatbot Arena: An Open Platform for Evaluating LLMs by Human Preference (ICML 2024 · similarity 0.88)
• Learning to Clarify: Multi-turn Conversations with Action-Based Contrastive Self-Training (ICLR 2025 · similarity 0.88)
• Do LLM Agents Have Regret? A Case Study in Online Learning and Games (ICLR 2025 · similarity 0.87)
• Online Preference Alignment for Language Models via Count-based Exploration (ICLR 2025 · similarity 0.87)
• A Statistical Framework for Ranking LLM-based Chatbots (ICLR 2025 · similarity 0.87)
• Should we be going MAD? A Look at Multi-Agent Debate Strategies for LLMs (ICML 2024 · similarity 0.87)