Introduction
In the Multi-Armed Bandit (MAB) framework, a learner seeks to identify the best arm from a set by sampling and observing noisy rewards. Linear Multi-Armed Bandits (LMAB) extend this by representing arms as vectors, where rewards are linear functions of these features. The goal of Best Arm Identification (BAI) is to find the optimal arm with a fixed confidence level using the minimum number of samples.
While theoretical lower bounds for sample complexity are well-established, existing algorithms that approach these bounds face significant practical hurdles. As shown in the comparison below, many state-of-the-art methods require computationally intractable "minimax oracles" or demand prior knowledge of the hidden reward vector's norm—information rarely available in real-world scenarios.
The PELEG Algorithm
The authors introduce PELEG (Phased Elimination Linear Exploration Game), a novel algorithm that bridges the gap between theoretical optimality and practical implementation. PELEG operates through a series of phases, maintaining a confidence ellipsoid to prune suboptimal arms.
The defining feature of PELEG is its use of a two-player zero-sum game to determine sampling distributions:
- The MAX Player: Employs a no-regret learning algorithm (such as Hedge) to propose a sampling distribution over the active arms.
- The MIN Player: Acts as an adversary, identifying reward models that are difficult to distinguish from the current best estimate.
Through iterative interaction, these players converge toward an optimal sampling strategy. This game-theoretic approach replaces the need for complex optimization oracles with standard convex programming subroutines, making the algorithm explicitly implementable.
Empirical Performance
PELEG was evaluated against state-of-the-art methods across several synthetic benchmarks, including standard basis vectors, unit spheres, and "confounding arm" scenarios designed to test algorithm robustness.
Key findings from the experiments include:
- Instance-Optimality: PELEG's sample complexity matches the theoretical lower bound up to logarithmic factors.
- Efficiency in Large Arm Sets: In high-dimensional settings with many arms (e.g., $K=700$), PELEG significantly outperformed competitors by avoiding "forced exploration" in uninformative directions. For instance, in complex settings, PELEG used roughly 75% fewer samples than some rival algorithms.
- Robustness: Unlike previous instance-optimal methods, PELEG does not require an upper bound on the parameter norm ($\|\theta^*\|_2$), making it more suitable for black-box optimization tasks.
Conclusion and Future Work
PELEG represents a significant advancement in linear bandit research by providing the first instance-optimal algorithm that is both explicitly implementable and free from restrictive prior knowledge requirements. While some logarithmic factors in the complexity bounds remain to be tightened and the computational overhead of the internal game can be high in extreme dimensions, the framework offers a powerful new tool for efficient exploration in high-dimensional feature spaces.
Summary updated