# FedPOB: Sample-Efficient Federated Prompt Optimization via Bandits

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 43 of its 57 references that are in the map.
- First posted on arXiv 29 Sep 2025.

## Builds on (most cited first, 30 of 43)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Prefix-Tuning: Optimizing Continuous Prompts for Generation](https://mlsanity.com/paper/2101.00190/) (2021)
- [The Power of Scale for Parameter-Efficient Prompt Tuning](https://mlsanity.com/paper/2104.08691/) (2021)
- [Qwen Technical Report](https://mlsanity.com/paper/2309.16609/) (2023)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Them](https://mlsanity.com/paper/2210.09261/) (2022)
- [Large Language Models Are Human-Level Prompt Engineers](https://mlsanity.com/paper/2211.01910/) (2022)
- [MPNet: Masked and Permuted Pre-training for Language Understanding](https://mlsanity.com/paper/2004.09297/) (2020)
- [Large Language Models as Optimizers](https://mlsanity.com/paper/2309.03409/) (2023)
- [GPT Understands, Too](https://mlsanity.com/paper/2103.10385/) (2021)
- [Automatic Prompt Optimization with "Gradient Descent" and Beam Search](https://mlsanity.com/paper/2305.03495/) (2023)
- [Federated Learning Based on Dynamic Regularization](https://mlsanity.com/paper/2111.04263/) (2021)
- [Promptbreeder: Self-Referential Self-Improvement Via Prompt Evolution](https://mlsanity.com/paper/2309.16797/) (2023)
- [RLPrompt: Optimizing Discrete Text Prompts with Reinforcement Learning](https://mlsanity.com/paper/2205.12548/) (2022)
- [PromptAgent: Strategic Planning with Language Models Enables Expert-level Prompt Optimization](https://mlsanity.com/paper/2310.16427/) (2023)
- [GrIPS: Gradient-free, Edit-based Instruction Search for Prompting Large Language Models](https://mlsanity.com/paper/2203.07281/) (2022)
- [Black-Box Prompt Optimization: Aligning Large Language Models without Model Training](https://mlsanity.com/paper/2311.04155/) (2023)
- [FedPrompt: Communication-Efficient and Privacy Preserving Prompt Tuning in Federated Learning](https://mlsanity.com/paper/2208.12268/) (2022)
- [Improving Text-to-Image Consistency via Automatic Prompt Optimization](https://mlsanity.com/paper/2403.17804/) (2024)
- [Differentially-Private Federated Linear Bandits](https://mlsanity.com/paper/2010.11425/) (2020)
- [Black-box Prompt Learning for Pre-trained Language Models](https://mlsanity.com/paper/2201.08531/) (2022)
- [Federated Learning of Large Language Models with Parameter-Efficient Prompt Tuning and Adaptive Optimization](https://mlsanity.com/paper/2310.15080/) (2023)
- [Federated Multi-Armed Bandits](https://mlsanity.com/paper/2101.12204/) (2021)
- [PRewrite: Prompt Rewriting with Reinforcement Learning](https://mlsanity.com/paper/2401.08189/) (2024)
- [Efficient Exploration for LLMs](https://mlsanity.com/paper/2402.00396/) (2024)
- [Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Models](https://mlsanity.com/paper/2202.04593/) (2022)

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

- [A Component-Based Survey of Interactions between Large Language Models and Multi-Armed Bandits](https://mlsanity.com/paper/2601.12945/) (2026)
- [COBRA-Skills: Contextual Bandit-Guided Evolution for Agent Skill Optimization](https://mlsanity.com/paper/2609.11682/) (2026)
- [Federated Prompt Learning: A Unified Framework, Empirical Analysis, and Future Directions](https://mlsanity.com/paper/2608.13844/) (2026)

## Abstract (arXiv)

The performance of large language models (LLMs) is highly sensitive to the input prompt, making prompt optimization a critical task. However, real-world application is hindered by three major challenges: (1) the black-box nature of powerful proprietary LLMs, (2) the need for high sample efficiency due to query costs, and (3) the desire for privacy-preserving collaboration among multiple users. To address these challenges simultaneously, we introduce a novel framework for sample-efficient federated prompt optimization based on multi-armed bandits (MABs). The MAB framework is uniquely suited for this problem as it is (1) inherently a black-box optimization method, (2) practically sample-efficient, and (3) enables collaborative learning with theoretically guaranteed benefit from more participating agents. We first propose the Federated Prompt Optimization via Bandits (FedPOB) algorithm, a federated variant of the Linear UCB algorithm, where agents collaborate by sharing model parameters instead of raw data. We then extend our approach to the practical setting of comparative user feedback by introducing FedPOB with Preference Feedback (FedPOB-Pref), an efficient algorithm based on federated dueling bandits. Extensive experiments demonstrate that both FedPOB and FedPOB-Pref significantly outperform existing baselines and that their performance consistently improves as more agents participate in the collaboration, validating the effectiveness of our federated approach.