![[2503.00509] Functional multi-armed bandit and the best function identification problems](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2503.00509] Functional multi-armed bandit and the best function identification problems
Summary
This article introduces the functional multi-armed bandit (FMAB) problem and the best function identification problem, proposing a new algorithm to optimize decision-making in scenarios with limited feedback.
Why It Matters
Understanding FMAB and best function identification is crucial as they model real-world optimization problems, particularly in competitive environments like LLM training. The proposed algorithms could enhance performance in various applications, making this research relevant for advancements in machine learning and artificial intelligence.
Key Takeaways
- Introduces functional multi-armed bandit (FMAB) and best function identification problems.
- Proposes a new algorithm (F-LCB) for optimizing decision-making with limited feedback.
- Demonstrates the application of these problems in competitive LLM training.
- Provides regret upper bounds based on convergence rates of base algorithms.
- Includes numerical experiments showcasing the proposed scheme's performance.
Computer Science > Machine Learning arXiv:2503.00509 (cs) [Submitted on 1 Mar 2025 (v1), last revised 17 Feb 2026 (this version, v2)] Title:Functional multi-armed bandit and the best function identification problems Authors:Yuriy Dorn, Aleksandr Katrutsa, Ilgam Latypov, Anastasiia Soboleva View a PDF of the paper titled Functional multi-armed bandit and the best function identification problems, by Yuriy Dorn and 3 other authors View PDF HTML (experimental) Abstract:Bandit optimization usually refers to the class of online optimization problems with limited feedback, namely, a decision maker uses only the objective value at the current point to make a new decision and does not have access to the gradient of the objective function. While this name accurately captures the limitation in feedback, it is somehow misleading since it does not have any connection with the multi-armed bandits (MAB) problem class. We propose two new classes of problems: the functional multi-armed bandit problem (FMAB) and the best function identification problem. They are modifications of a multi-armed bandit problem and the best arm identification problem, respectively, where each arm represents an unknown black-box function. These problem classes are a surprisingly good fit for modeling real-world problems such as competitive LLM training. To solve the problems from these classes, we propose a new reduction scheme to construct UCB-type algorithms, namely, the F-LCB algorithm, based on algorithms f...
