When Exploration Comes for Free with Mixture-Greedy: Do we need UCB in Diversity-Aware Multi-Armed Bandits?
Bahar Dibaei Nia, Farzan Farnia · 2026
Read When Exploration Comes for Free with Mixture-Greedy: Do we need UCB in Diversity-Aware Multi-Armed Bandits? by Bahar Dibaei Nia, Farzan Farnia (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-21716.txt.
Introduction
Dibaei Nia and Farnia ask whether greedy choice is enough when picking among generative models. With diversity-aware scores, a mix of models can beat any single one, which changes the bandit problem. Prior methods add an Upper Confidence Bound bonus to push exploration. Across datasets and metrics, that bonus slowed learning and hurt sample efficiency, they find. A plain mixture-greedy rule converged faster and scored better. Their theory explains why: diversity goals favor interior mixes, so exploration comes free from the shape of the objective itself.
Catalog record
| CREATOR | Bahar Dibaei Nia, Farzan Farnia |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 92733 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.21716
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
When Exploration Comes for Free with Mixture-Greedy: Do we need UCB in Diversity-Aware Multi-Armed Bandits? Bahar Dibaei Nia, Farzan Farnia Abstract Efficient selection among multiple generative models is increasingly important in modern generative AI, where sampling from suboptimal models is costly. This problem can be formulated as a multi-armed bandit task. Under diversity-aware evaluation metrics, a non-degenerate mixture of generators can outperform any individual model, distinguishing this setting from classical best-arm identification. Prior approaches therefore incorporate an Upper Confidence Bound (UCB) exploration bonus into the mixture objective. However, across multiple datasets and evaluation metrics, we observe that the UCB term consistently slows convergence and often reduces sample efficiency. In contrast, a simple Mixture-Greedy strategy without explicit UCB-type optimism converges faster and achieves even better performance, particularly for widely used metrics such as FID and Vendi where tight confidence bounds are difficult to construct. We provide theoretical insight explaining this behavior: under transparent structural conditions, diversity-aware objectives induce implicit exploration by favoring interior mixtures, leading to linear sampling of all arms and sublinear regret guarantees for entropy-based, kernel-based, and FID-type objectives. These results suggest that in diversity-aware multi-armed bandits for generative model selection, exploration can arise intrinsically from the objective geometry, questioning the necessity of explicit confidence bonuses. 1 Introduction Figure 1 : Comparison of mixture selection strategies over five ImageNet pretrained generative models from 54 ’s repository in terms of RKE \uparrow (left) and KID \downarrow (right) of generated samples from step 1 to t (plots’ x-axis). Mixture-Greedy performed better than Mixture-UCB ( 45 ) (with the UCB exploration term) in both the experiments with RKE and KID objectives. Mixture-Oracle always generates samples from the population-optimal mixture of models. The past decade has witnessed remarkable advances in generative modeling, leading to a wide availability of high-quality pretrained generators across diverse architectures and training paradigms. Early approaches such as variational autoencoders (VAEs) ( 25 ) and generative adversarial networks (GANs) ( 14 ) established scalable frameworks for learning complex data distributions. Subsequent architectural and training advances ( 24 ; 9 ; 57 ) , together with the emergence of diffusion-based generative models ( 19 ; 53 ; 46 ) , have substantially improved both sample fidelity and diversity. As a result, practitioners often have access to multiple well-trained generative models that differ in architecture, training data, and inference cost. In such settings, a fundamental practical question arises: how can one select or combine these generators in a sample-efficient manner? Generating samples from suboptimal models can be computationally expensive, and evaluation budgets are typically limited. Suppose we are given m candidate generators, where the i th generator \mathcal{G}_{i} induces a distribution P_{\mathcal{G}_{i}} . At each round t=1,2,\dots,T , we select a generator index I_{t}\in[m] , observe a sample X_{t}\sim P_{\mathcal{G}_{I_{t}}} , and update an estimate of a target evaluation score. The objective is to allocate samples so as to approach the best achievable evaluation performance while minimizing the number of samples drawn from suboptimal generators. A natural formalization of this task is as a stochastic multi-armed bandit problem ( 47 ; 52 ; 28 ) . Standard bandit algorithms aim to balance exploration and exploitation in the online selection process. To do this, a well-established approach is the Upper Confidence Bound (UCB) principle ( 4 ) , which augments empirical estimates with optimism bonuses to encourage exploration of uncertain arms. In the context of generative model selection, however, the evaluation criteria are typically non-linear functionals of the underlying distribution rather than simple expected rewards. For example, the Fréchet Inception Distance (FID) ( 18 ) compares mean and covariance statistics of two distributions, and other widely used metrics such as Kernel Inception Distance (KID) ( 7 ) and precision-recall based measures ( 48 ; 27 ) also depend on higher-order distributional properties. To address this, 20 proposed a bandit framework tailored to generative model evaluation and derived UCB-type confidence bounds for the FID metric, enabling online best-arm identification despite the non-linearity of the objective. A notable finding in generative model selection is the recognition that the optimal solution need not be a single generator, i.e., the best individual arm in the bandit formulation considered by 20 . Rather, as shown by 45 , under several diversity-aware evaluation metrics, a non-degenerate mixture of generators can strictly outperform every individual model. Let \alpha\in\Delta_{m}:=\{\alpha\in\mathbb{R}^{m}:\alpha\succeq 0,\ \mathbf{1}^{\top}\alpha=1\} denote mixture weights and define the mixture distribution P_{\alpha}=\sum_{i=1}^{m}\alpha_{i}P_{\mathcal{G}_{i}} . The mixture-model selection problem can then be formulated as \displaystyle\alpha^{\star}\;\in\;\underset{\alpha\in\Delta_{m}}{\arg\!\max}\;\;\mathrm{Score}\bigl(P_{\alpha}\bigr) (1) Unlike classical best-arm identification, the optimizer of equation 1 may lie in the interior of the simplex, implying that combining generators can strictly improve performance. To address this, 45 proposed Mixture-UCB algorithms that operate over the simplex and incorporate Upper Confidence Bound (UCB) bonuses. For quadratic kernel-based objectives such as KID ( 7 ) and RKE ( 21 ) , they showed that uniform high-probability guarantees can be obtained by estimating a finite number of pairwise expectations, making UCB-style exploration analytically tractable in that regime. Extending such guarantees to non-quadratic metrics, including FID and entropy-based diversity scores such as the Vendi score ( 12 ) , remains significantly more challenging, as the resulting UCB bound would be loose due to the non-quadratic structure, leading to over-exploration and substantially slow convergence to the optimal solution. In this work, we revisit a foundational design choice in bandit-based generative model selection: Is an explicit UCB exploration bonus actually necessary? In classical best-arm bandits with linear rewards, purely greedy strategies are known to be brittle: early estimation noise can cause the algorithm to over-commit to an apparently good arm, stop collecting data from others, and never recover. UCB-style optimism was introduced precisely to prevent this collapse by forcing continued exploration ( 4 ) . Surprisingly, we empirically find that this classical intuition does not necessarily carry over to diversity-aware mixture selection. Across extensive experiments on multiple datasets and evaluation metrics, adding the UCB bonus consistently slows convergence and often reduces sample efficiency. In contrast, a simple Mixture-Greedy strategy that repeatedly optimizes the empirical objective over the simplex \Delta_{m} (without any explicit exploration bonus) converges faster and achieves comparable or superior performance, especially for widely used non-quadratic metrics such as FID and Vendi, where constructing UCB bounds is challenging. Our explanation is that diversity-aware mixture objectives can induce implicit exploration . The main distinction from best-arm identification is that the decision space here is not the discrete set of arms but the continuous simplex of mixtures. For many diversity-aware metrics, the optimum is attained by a non-degenerate mixture, and the objective itself tends to disfavor degenerate solutions that place nearly all mass on a single generator. As a result, optimizing the empirical objective can naturally produce interior mixture weights, which in turn ensures that every generator continues to receive samples. In other words, the mixture geometry plus the diversity-aware objective can create an exploration effect that is internal to the optimization problem, rather than an external confidence bonus appended to it. We formalize this phenomenon by providing theoretical results showing that, under explicit structural conditions, Mixture-Greedy stays uniformly away from the boundary of \Delta_{m} , which yields linear sampling of all arms and sublinear regret without UCB. Our analyses cover representative families of objectives