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

arXiv: https://arxiv.org/abs/2501.01849 · HTML: https://mlsanity.com/paper/2501.01849/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 13 of its 45 references that are in the map.
- First posted on arXiv 3 Jan 2025.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)
- LLM alignment / RLHF / preference optimisation / [LLM preference optimization methods](https://mlsanity.com/alignment/llm-preference-optimization-methods/)

## Builds on (most cited first, 13 of 13)

- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance](https://mlsanity.com/paper/2305.05176/) (2023)
- [OpenAssistant Conversations -- Democratizing Large Language Model Alignment](https://mlsanity.com/paper/2304.07327/) (2023)
- [Federated Linear Contextual Bandits](https://mlsanity.com/paper/2110.14177/) (2021)
- [Which LLM to Play? Convergence-Aware Online Model Selection with Time-Increasing Bandits](https://mlsanity.com/paper/2403.07213/) (2024)
- [Auto-Instruct: Automatic Instruction Generation and Ranking for Black-Box Language Models](https://mlsanity.com/paper/2310.13127/) (2023)
- [On Speeding Up Language Model Evaluation](https://mlsanity.com/paper/2407.06172/) (2024)
- [Comparison-based Conversational Recommender System with Relative Bandit Feedback](https://mlsanity.com/paper/2208.09837/) (2022)
- [Efficient Explorative Key-term Selection Strategies for Conversational Contextual Bandits](https://mlsanity.com/paper/2303.00315/) (2023)
- [FedConPE: Efficient Federated Conversational Bandits with Heterogeneous Clients](https://mlsanity.com/paper/2405.02881/) (2024)
- [StyleChat: Learning Recitation-Augmented Memory in LLMs for Stylized Dialogue Generation](https://mlsanity.com/paper/2403.11439/) (2024)

## Built on by (most cited first, 8 of 8)

- [Online Multi-LLM Selection via Contextual Bandits under Unstructured Context Evolution](https://mlsanity.com/paper/2506.17670/) (2025)
- [Maestro: Learning to Collaborate via Conditional Listwise Policy Optimization for Multi-Agent LLMs](https://mlsanity.com/paper/2511.06134/) (2025)
- [Survey: Multi-Armed Bandits Meet Large Language Models](https://mlsanity.com/paper/2505.13355/) (2025)
- [Offline Learning for Combinatorial Multi-armed Bandits](https://mlsanity.com/paper/2501.19300/) (2025)
- [Neuroplasticity in Artificial Intelligence -- An Overview and Inspirations on Drop In & Out Learning](https://mlsanity.com/paper/2503.21419/) (2025)
- [Leveraging the Power of Conversations: Optimal Key Term Selection in Conversational Contextual Bandits](https://mlsanity.com/paper/2505.21393/) (2025)
- [Agent-Based Simulations of Online Political Discussions: A Case Study on Elections in Germany](https://mlsanity.com/paper/2503.24199/) (2025)
- [Faster, Smaller, and Smarter: Task-Aware Expert Merging for Online MoE Inference](https://mlsanity.com/paper/2509.19781/) (2025)

## Abstract (arXiv)

Prompt-based offline methods are commonly used to optimize large language model (LLM) responses, but evaluating these responses is computationally intensive and often fails to accommodate diverse response styles. This study introduces a novel online evaluation framework that employs a multi-agent conversational bandit model to select optimal responses while aligning with user preferences dynamically. To tackle challenges such as high-dimensional features, large response sets, adaptive conversational needs, and multi-device access, we propose MACO, Multi-Agent Conversational Online Learning, which comprises two key components: (1) textttMACO-A: Executed by local agents, it employs an online elimination mechanism to filter out low-quality responses. (2) textttMACO-S: Executed by the cloud server, it adaptively adjusts selection strategies based on aggregated preference data. An adaptive preference mechanism triggers asynchronous conversations to enhance alignment efficiency. Theoretical analysis demonstrates that MACO achieves near-optimal regret bounds, matching state-of-the-art performance in various degenerate cases. Extensive experiments utilizing Google and OpenAI text embedding models on the real-world datasets with different response styles, combined with Llama and GPT-4o, show that MACO consistently outperforms baseline methods by at least 8.29% across varying response set sizes and numbers of agents.