혼합 그리디(Mixture-Greedy)를 이용한 탐색: 다양성을 고려한 다중 팔 밴딧 문제에서 UCB는 정말 필요한가?

When Exploration Comes for Free with Mixture-Greedy: Do we need UCB in Diversity-Aware Multi-Armed Bandits?

최신 생성 AI에서, 최적 이하 모델에서 샘플링하는 것은 비용이 많이 들기 때문에, 여러 생성 모델 중에서 효율적으로 선택하는 것이 점점 더 중요해지고 있습니다. 이 문제는 다중 팔 밴딧(Multi-Armed Bandit) 문제로 정의될 수 있습니다. 다양성을 고려한 평가 지표에서는, 생성 모델들의 혼합이 개별 모델보다 우수한 성능을 보이는 경우가 있으며, 이는 고전적인 최적 팔(best-arm) 식별 문제와는 다른 상황입니다. 기존 연구에서는 이러한 상황을 해결하기 위해, 혼합 목적 함수에 상위 신뢰 구간(Upper Confidence Bound, UCB) 탐색 보너스를 포함했습니다. 그러나 여러 데이터셋과 평가 지표에 대한 실험 결과, UCB 항은 일관되게 수렴 속도를 늦추고, 샘플 효율성을 저하시키는 경향을 보였습니다. 반면, 명시적인 UCB 기반 낙관주의 없이 간단한 혼합 그리디(Mixture-Greedy) 전략은 더 빠르게 수렴하고, 특히 FID 및 Vendi와 같이 엄격한 신뢰 구간을 구축하기 어려운 지표에서 더 나은 성능을 달성했습니다. 우리는 이러한 현상을 설명하는 이론적 통찰력을 제시합니다. 특정 구조적 조건 하에서, 다양성을 고려한 목적 함수는 내부 혼합을 선호함으로써 암묵적인 탐색을 유도하며, 이는 모든 팔에 대한 선형적인 샘플링과 엔트로피 기반, 커널 기반, 그리고 FID 유형의 목적 함수에 대한 하위 선형 후회 보장으로 이어집니다. 이러한 결과는 생성 모델 선택을 위한 다양성을 고려한 다중 팔 밴딧 문제에서, 탐색이 명시적인 신뢰 보너스 없이도 목적 함수의 구조로부터 자연스럽게 발생할 수 있으며, 따라서 명시적인 신뢰 보너스의 필요성에 의문을 제기한다는 것을 시사합니다.

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 \emph{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.