다중 최적 암을 갖는 밴딧: 미니맥스 리그릿과 비적응성
Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity
한국어 초록
많은 실제 의사결정 문제가 여러 정답을 가질 수 있다는 점에서 착안하여, 본 논문에서는 다수의 최적 암(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 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.