🤖 AI

Functional multi-armed bandit and the best function identification problems

This paper introduces the functional multi-armed bandit and best function identification problem classes to address real-world scenarios like competitive LLM training, proposing a novel F-LCB reduction scheme that constructs UCB-type algorithms with provable regret bounds based on nonlinear optimization convergence rates.

Original authors: Yuriy Dorn, Aleksandr Katrutsa, Ilgam Latypov, Anastasiia Soboleva

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yuriy Dorn, Aleksandr Katrutsa, Ilgam Latypov, Anastasiia Soboleva

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a chef trying to find the single best recipe out of a hundred candidates to serve at a grand banquet. You have a limited amount of time and ingredients (a "budget").

In the old way of doing things (traditional methods), you might try to bake a little bit of every cake, taste them, and then decide. Or, you might bake one cake all the way to the end, then the next, then the next. Both of these approaches are slow and wasteful. If you have 100 cakes, you might run out of time before you even finish the first few.

This paper introduces a smarter way to solve this problem, which the authors call the Functional Multi-Armed Bandit (FMAB) and the Best Function Identification (BFI) problem.

Here is the breakdown of their idea using simple analogies:

1. The Problem: The "Black Box" Cake Contest

Usually, when computers try to pick the best model (like a neural network for AI), they treat each model as a "black box." They don't know how the cake rises or how the ingredients mix; they just taste the result.

The Challenge: Training modern AI models is like baking a massive, complex cake. It takes days and costs a fortune in electricity. You can't afford to bake every single candidate recipe to the very end to see which one is best.
The Goal: You need to find the recipe with the lowest error (the tastiest cake) and stop wasting time on the bad ones as quickly as possible.

2. The New Idea: "Smart Tasting" (F-LCB)

The authors propose a new algorithm called F-LCB. Think of this as a very smart sous-chef who doesn't just taste the cake; they understand the physics of baking.

Instead of treating each recipe as a mystery box, F-LCB treats each recipe as a process with a known speed limit.

The Analogy: Imagine you know that "Recipe A" (a simple sponge cake) usually doubles in size every minute. "Recipe B" (a dense fruitcake) only grows 1% every minute.
How F-LCB works:
1. It starts baking all recipes a tiny bit.
2. It looks at the "Lower Confidence Bound" (LCB). This is a fancy way of saying: "Based on how fast this cake should be rising, what is the worst-case scenario for its final taste?"
3. If a cake is rising too slowly compared to its potential, the algorithm says, "This one is likely a loser," and stops baking it.
4. It pours all its remaining time and ingredients into the recipes that are showing the most promise.

3. Why is this better than the old ways?

The paper compares their method to two famous competitors: Successive Halving and Hyperband.

The Competitors: These are like a chef who cuts the budget in half every round. They bake everyone a little, kill the bottom 50%, bake the rest a little more, kill the bottom 50% again. It's efficient, but it's a bit rigid. It doesn't care how the cake is rising, just the current taste.
F-LCB (The Authors' Method): This chef looks at the trajectory. If a cake is rising fast, F-LCB knows it will be great soon and focuses on it. If a cake is rising slowly, it knows it will never catch up.
The Result: In their experiments (baking digital cakes on a computer), F-LCB found the best model faster and with less computing power than the competitors, especially when the budget was tight.

4. What did they prove?

The authors didn't just guess this would work; they did the math to prove it.

The Lower Bound: They proved that no matter how clever you are, there is a minimum amount of time you must spend to find the best cake.
The Upper Bound: They proved that their F-LCB algorithm gets very close to that minimum time limit. It's as efficient as mathematically possible (within a small margin of error).

5. Real-World Tests

They tested this in three scenarios:

Smooth Cakes: Standard, well-behaved mathematical functions. F-LCB found the best one quickly.
Rough Cakes: Functions that are jagged and hard to optimize. F-LCB still worked well.
Neural Networks: They used it to pick the best AI architecture for an image classification task (identifying objects in pictures). F-LCB identified the best model using fewer training steps than the other methods.

Summary

The paper says: "Stop guessing blindly. Use the known speed of your optimization process to predict which models will win, and stop wasting money on the ones that are already losing."

They created a tool (F-LCB) that acts like a smart manager, constantly checking the progress of every candidate, cutting off the slow ones early, and pouring all resources into the winner, saving massive amounts of time and money in the process.

Technical Summary: Functional Multi-Armed Bandit and Best Function Identification

1. Problem Statement

The paper addresses the model selection problem in scenarios with limited computational budgets, such as competitive neural network training. The core challenge is identifying the optimal function (e.g., the best neural network architecture or hyperparameter setting) from a set of $K$ candidate parametric functions $\{f_1, \dots, f_K\}$ , where each function $f_i$ is defined over a convex decision set $X_i$ .

The authors formalize two new problem setups that generalize classical Multi-Armed Bandit (MAB) and Best Arm Identification (BAI):

Functional Multi-Armed Bandit (FMAB): The agent selects an index $i_t$ and a decision vector $x_{t, i_t} \in X_{i_t}$ at each time step $t$ . The goal is to minimize the cumulative regret $R_O(T) = \sum_{t=1}^T [f_{i_t}(x_{t, i_t}) - f^*]$ , where $f^* = \min_{i} \min_{x \in X_i} f_i(x)$ . Unlike standard MAB where arms are random variables, here each arm is an unknown function optimized via a black-box oracle (e.g., gradients).
Best Function Identification (BFI): The agent aims to identify the single best function $J_T$ after $T$ rounds such that the final regret $R_B(T) = \min_{x \in X_{J_T}} f_{J_T}(x) - f^*$ is minimized.

The paper argues that reducing these problems to standard MAB (by treating every point $x$ as an arm) leads to infeasible computational costs due to the continuous nature of the decision spaces. Instead, the proposed framework leverages the internal dynamics of optimization algorithms.

2. Methodology: The F-LCB Algorithm

To solve FMAB and BFI, the authors propose the F-LCB (Functional Lower Confidence Bound) algorithm. This is a UCB-type algorithm that constructs confidence intervals based on the convergence rates of underlying base optimization algorithms rather than statistical concentration of random variables.

Core Mechanism

Base Optimizers: Each candidate function $f_i$ is associated with a base optimization algorithm $A_i$ (e.g., Projected Gradient Descent, Accelerated Gradient Descent) known to have a specific convergence rate $g_i(k, \delta)$ .
Lower Confidence Bound (LCB): At each step, the algorithm maintains an LCB for each function $i$ :
$LCB_i(k_i, \delta) = f_i(x_{i, k_i}) - g_i(k_i, \delta)$
Here, $k_i$ is the number of iterations allocated to function $i$ , and $g_i(k_i, \delta)$ represents the theoretical upper bound on the sub-optimality gap after $k_i$ steps.
Selection Rule: The algorithm selects the arm $i_t$ with the minimum LCB value.
Update: It performs one iteration of the base optimizer $A_{i_t}$ , updates the function value, and recalculates the LCB.
Stopping Criterion (for BFI): The process stops when the gap between the current best estimate and the LCB falls below a threshold $\epsilon$ , ensuring the identified function is within $\epsilon$ of the global optimum.

The algorithm effectively balances exploration (allocating budget to functions with high uncertainty or promising potential) and exploitation (refining the best candidate) by reacting immediately when an arm's LCB becomes suboptimal.

3. Key Contributions

Theoretical Contributions

Problem Formulation: The paper introduces the FMAB and BFI frameworks, formally distinguishing them from classical MAB by modeling arms as optimization tasks with known convergence properties.
Lower Bounds: The authors establish minimax lower bounds for both FMAB and BFI in deterministic settings. These bounds depend on the complexity of the function classes (e.g., convex $M$ $M$ -Lipschitz, $L$ $L$ -smooth, $\mu$ $μ$ -strongly convex).
- For example, for convex $M$ -Lipschitz functions, the lower bound is $\Omega(MR\sqrt{T})$ .
- For $\mu$ -strongly convex and $L$ -smooth functions, the bound is $\Omega(R^2)$ .
Regret Upper Bounds: The paper proves that the F-LCB algorithm achieves regret upper bounds that match the derived lower bounds up to logarithmic factors.
- In the deterministic case, the regret depends on the convergence rate $r$ of the base optimizer (e.g., $O(\sqrt{T})$ for $r=1/2$ ).
- In the stochastic case (inexact oracles), the bounds incorporate noise parameters and hold with high probability.

Algorithmic Contributions

F-LCB Algorithm: A novel reduction scheme that integrates optimization convergence rates into the bandit selection process. It unifies the arm selection step with the update of the current optimum approximation.
Flexibility: The framework allows for different base optimizers for different arms, provided their convergence rates are known.

4. Experimental Results

The authors validate F-LCB through numerical experiments on synthetic and real-world datasets:

Synthetic Convex Functions:
- Smooth Convex: F-LCB successfully identified the function with the global minimum among three candidates, ceasing updates to suboptimal functions once identified.
- Non-Smooth Convex: Using piece-wise linear functions and a subgradient method, F-LCB demonstrated convergence to the optimal function with cumulative regret consistent with theoretical bounds.
- Inexact Oracles: In the presence of gradient noise, F-LCB still identified the best function, though convergence curves were less distinct than in the deterministic case.
Neural Network Selection (BFI):
- Setup: The algorithm was applied to the CIFAR-100 image classification task, selecting the best architecture from a set of 10 models (including MobileNet, ShuffleNet, and ResNet variants) with fewer than 5M parameters.
- Comparison: F-LCB was compared against SuccessiveHalving (SH) and Hyperband.
- Outcome: F-LCB outperformed both baselines in low-budget scenarios (e.g., $T=50, 100$ ), achieving a lower mean rank for the selected model. Unlike Hyperband, which splits budgets across multiple SH runs, F-LCB does not permanently discard models but dynamically allocates resources. In larger budgets ( $T \ge 350$ ), F-LCB performed comparably to SH, consistently identifying the best model.

5. Significance and Claims

The paper claims that F-LCB provides a theoretically grounded alternative to heuristic AutoML methods (like SuccessiveHalving and Hyperband) and purely black-box approaches (like Bayesian Optimization).

Theoretical Guarantees: Unlike heuristic methods, F-LCB leverages the known convergence rates of optimization routines to derive formal regret guarantees and identification bounds.
Efficiency: The approach is particularly effective when computational budgets are tight, as it avoids the sub-exponential costs associated with treating optimization problems as standard MABs with infinite arms.
Applicability: The framework is applicable to any scenario where candidate models are solved via iterative optimization with known convergence properties (e.g., convex relaxations, specific optimization method selection).

Limitations Acknowledged by the Authors

The paper explicitly notes that the approach requires prior knowledge of the objective's functional class and the convergence rate $g(k, \delta)$ of the base algorithm. This is a significant constraint for deep learning, where convergence rates for non-convex neural network training are not well-defined in the strict sense required by the algorithm's definition. Consequently, while the method works for convex problems and specific optimization tasks, its application to general neural network training relies on heuristic approximations of $g(k)$ .