arXiv:2609.38659v2 stat.ML

다중 최적 암을 갖는 밴딧: 미니맥스 리그릿과 비적응성

Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity

Kaixuan Ji, Qiwei Di, Qingyue Zhao, Heyang Zhao, Quanquan Gu

제출 2026-09-29

한국어 초록

많은 실제 의사결정 문제가 여러 정답을 가질 수 있다는 점에서 착안하여, 본 논문에서는 다수의 최적 암(optimal arm)을 갖는 다중 암 밴딧(multi-armed bandit, MAB)을 연구한다. $A$개의 최적 암을 갖는 $K$-암 밴딧에 대해, 먼저 기존 서브샘플링 알고리즘(De Heide et al., 2021; Zhu and Nowak, 2020)에 대한 더욱 정밀한 분석을 제공하여 $\tilde{O}\Big(\frac{K-A}{\sqrt{KA}}\sqrt{T} \Big)$의 미니맥스 리그릿(minimax regret)을 확립함으로써 기존의 $\tilde{O}(\sqrt{KT/A})$ 리그릿을 개선한다. 여기서 $T$는 총 상호작용 횟수이며 $\tilde O(\cdot)$는 모든 상수 및 로그 인수를 생략한 표기이다. 이어 로그 인수 범위 내에서 일치하는 하한(lower bound)을 제시하여, 본 연구에서 도출한 속도가 미니맥스 최적에 거의 부합함을 보인다. 나아가 특정 최적 암 개수에 대해 준최적(near-optimal)인 알고리즘은 더 적은 수의 최적 암에 대한 최적 리그릿보다 실질적으로 훨씬 더 큰 리그릿을 발생시키므로, 준최적 리그릿을 달성하기 위해서는 $\tilde{O}(1)$ 인수 내에서 $A$에 대한 사전 지식이 필수적임을 보인다. 종합적으로, 본 연구 결과는 $1 \leq A \leq K-1$ 전체 범위에 걸쳐 $A$를 갖는 $K$-암 밴딧에 대한 포괄적인 미니맥스 특성 규명을 제공한다.

원문 초록

We study multi-armed bandits (MAB) with multiple optimal arms, motivated by the fact that many practical decision making problems admit multiple correct answers. For $K$-armed bandits with $A$ optimal arms, we first provide a sharper analysis of previous sub-sampling algorithms (De Heide et al., 2021; Zhu and Nowak, 2020), establishing a $\tilde{O}\Big(\frac{K-A}{\sqrt{KA}}\sqrt{T} \Big)$ minimax regret, where $T$ is the total number of interactions and $\tilde O(\cdot)$ drops all constant and logarithmic factors, improving the previous $\tilde{O}(\sqrt{KT/A})$ regret. We then provide a matching lower bound up to logarithmic factors, indicating that our established rate is nearly minimax-optimal. We further show that the knowledge of $A$ up to $\tilde{O}(1)$ factors is necessary to achieve near-optimal regret, as near-optimal algorithms for one number of optimal arms must incur substantially larger regret than optimal regret for a smaller number. Overall, our results provide a comprehensive minimax characterization of $K$-armed bandits with $A$ over the entire range of $1 \leq A \leq K-1$.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2609.38659v2

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.