Researchers from MIT have introduced a novel approach to a long-standing challenge in online learning: making optimal decisions when faced with an overwhelming, potentially infinite, number of "experts" in an unpredictable, nonstochastic environment. Their proposed meta-algorithm, BEES (Best Expert Search), provides a robust framework for navigating these complex decision spaces.
The Challenge of Infinite Experts
In the traditional multi-armed bandit problem, a learner chooses actions to maximize rewards. The "expert advice" variant adds a layer where the learner receives suggestions from various experts before acting. While standard algorithms like Exp4 perform well with a small, fixed number of experts, they struggle in two critical scenarios:
- Infinite Expert Sets: In applications like hyperparameter tuning or feature selection, the number of possible configurations (experts) can be infinite, making it computationally impossible to query all of them at every step.
- Adversarial Environments: Most existing research on infinite-armed bandits assumes rewards follow a predictable statistical distribution (stochastic). This paper addresses the nonstochastic setting, where rewards may be assigned by an "oblivious adversary" attempting to minimize the learner's gains.
The BEES Framework
The authors propose a two-layered solution consisting of a ranking-capable subroutine and a meta-algorithm that manages expert subsets over time.
Exp4.R: Ranking as a Pruning Tool
At the core of the system is Exp4.R, a variant of the classic Exp4.P algorithm. The "R" stands for Ranking. Unlike its predecessor, Exp4.R calculates a specific threshold vector that allows the learner to infer the correct ranking of experts with high probability. By identifying which experts are definitively underperforming, the learner can prune the search space and focus resources on the most promising candidates.
BEES Meta-Algorithm
BEES manages the infinite set of experts by dividing the learning process into epochs. In each epoch, it runs Exp4.R on a finite subset of experts. As time progresses, both the number of experts queried and the length of the epochs grow exponentially.
A specialized version, BEES.LB, is designed for "structured experts" where performance follows a specific pattern, such as model complexity. This version utilizes the ranking property of Exp4.R to "zoom in" on the optimal expert index more efficiently.
Key Insights and Results
The most significant theoretical contribution is the high-probability regret bound of $\tilde{O}((i^*)^{1/\alpha}K + \sqrt{\alpha KT})$, where $i^*$ represents the index of the best expert. This result demonstrates that the "penalty" for having infinite experts depends primarily on the location of the best expert in the initial ordering, rather than the total size of the set.
When the best expert's index is relatively small, the algorithm achieves regret comparable to settings where the number of experts is finite and known. The parameter $\alpha$ allows users to tune the exploration-exploitation trade-off, balancing the search for new "hidden gem" experts against the exploitation of known top performers.
Empirical Performance
In synthetic simulations involving 10 actions and nonstochastic rewards, the researchers validated their theoretical findings. The experts were arranged in a "weakly unimodal" structure (as seen in Figure 1) corrupted by Gaussian noise.
As shown in Figure 2, BEES.LB significantly outperformed both the standard BEES and a truncated version of Exp4.P. By exploiting the unimodal structure of the expert space, BEES.LB was able to find the performance "sweet spot" much faster, resulting in lower cumulative regret over the time horizon.
Conclusion and Future Directions
BEES provides a powerful new tool for online learning in adversarial, high-dimensional spaces. While the algorithm's efficiency is currently tied to the initial ordering of experts, it represents a major step forward in handling infinite expert sets without making strong stochastic assumptions. Future work may focus on developing "instance-dependent" bounds and further optimizing the algorithm for massive-scale computational systems.
Summary updated