양자 다중 팔 밴딧 및 선형 밴딧: 하한과 알고리즘
Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms
한국어 초록
본 논문에서는 학습자가 양자 보상(reward) 오라클 또는 그 역원을 통해 각 팔(arm)이나 행동을 질의하는 양자 다중 팔 밴딧(QMAB) 및 양자 선형 밴딧(QLB)을 연구합니다. 이전 연구에서는 $K$개의 팔을 가진 QMAB에 대해 $O(K\log T)$, $d$차원 QLB에 대해 $O(d^2\operatorname{polylog} T)$의 후회(regret)를 달성하는 시간 범위 $T$에 대한 알고리즘을 제시했습니다. 그러나 이는 $K$와 $T$에 대한 최적의 의존성과 $d$에 대한 의존성을 추가로 개선할 수 있는지 여부를 미해결 상태로 남겨두었습니다. 본 연구에서는 QMAB에 대해 $\Theta(K\log(1+T/K))$라는 최초의 엄밀한 미니맥스(minimax) 후회 경계를 증명하고, 유한 행동 QLB에 대해 $T$와 무관한 후회를 배제하는 최초의 하한인 $\Omega(d\log(1+T/d))$를 증명합니다. 본 연구의 하한은 고정된 보상 평균을 대안 구간과 구별하기 위한 고신뢰도 단일 팔 양자 테스팅 하한에 기반합니다. 이후 밴딧-테스팅 축소(reduction)를 통해 이를 QMAB 하한으로 확장하며, 선형 임베딩(embedding)을 통해 유한 행동 QLB 하한을 도출합니다. 이에 대응하는 QMAB 상한은 양자 몬테카를로(QMC) 추정량의 꼬리 경계(tail bound)를 사용하여 도출됩니다. 유한 행동 QLB의 경우, 설계 가중치에 맞춘 질의 할당을 통해 낮은 바이어스(bias) 및 낮은 분산을 갖는 양자 평균 추정량과 작은 지지 집합(small-support)을 갖는 $G$-최적 설계를 결합한 단계별 제거(phased elimination) 알고리즘을 제안합니다. 행동 집합의 크기가 $\operatorname{poly}(d)$일 때, 이 알고리즘의 후회는 $d$에 대해 거의 선형적이며 다항 로그 인자(polylogarithmic factor) 범위 내에서 본 연구의 하한과 일치합니다.
원문 초록
We study quantum multi-armed bandits (QMAB) and quantum linear bandits (QLB), where the learner queries each arm or action through a quantum reward oracle or its inverse. Prior work gives algorithms over horizon $T$ with regret $O(K\log T)$ for QMAB with $K$ arms and $O(d^2\operatorname{polylog} T)$ for $d$-dimensional QLB. This leaves open the optimal dependence on $K$ and $T$ and whether the dependence on $d$ can be further improved. In this work, we prove the first tight minimax regret bound of $Θ(K\log(1+T/K))$ for QMAB and the first lower bound of $Ω(d\log(1+T/d))$ for finite-action QLB, ruling out regret independent of $T$. Our lower bounds rely on a high-confidence single-arm quantum testing lower bound for distinguishing a fixed reward mean from an interval of alternatives. A bandit-to-testing reduction then lifts it to the QMAB lower bound, while a linear embedding gives the finite-action QLB lower bound. The matching QMAB upper bound is obtained using a tail bound for the Quantum Monte Carlo (QMC) estimator. For finite-action QLB, we propose a phased elimination algorithm that combines a low-bias low-variance quantum mean estimator with a small-support $G$-optimal design through a query allocation matched to the design weights. When the action set has size $\operatorname{poly}(d)$, its regret is nearly linear in $d$ and matches our lower bound up to polylogarithmic factors.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
지속적 후보 집합을 활용한 선형 밴딧 가속화
Accelerating Linear Bandits with Persistent Candidate Sets
행동의 수가 $K$개로 매우 큰 고정된 집합을 갖는 선형 밴딧(linear bandit)에서는 완전 낙관적 점수 산출(exhaustive optimistic scoring)로 인해 라운드당 $\mathcal{O}(K)$회의 점수 평가가 필요하여 행동 선택 비용이 커질 수 있습니다. 본 논문에서는 $k$개의 활성 행동을 유지하고 매 라운드마다 나머지 $K-k$개 행동 중에서 $q$개의 도전자(challenger)를 균등하게 표본추출하는 Persistent Candidate LinUCB(\textsc{PC-LinUCB})를 제안합니다. 이 $k+q$개의 후보에 대해서만 점수를 평가함으로써, \textsc{PC-LinUCB}는 라운드당 점수 평가 횟수를 $\mathcal{O}(k+q)$로 줄입니다. 고정된 신뢰 수준에서 표준 선형 밴딧 학습 항과 $\mathcal{O}\left((K-k)\log(K-k)/q\right)$ 차수의 추가적 탐색 비용(discovery cost)으로 구성된 문제 독립적(problem-independent) 및 문제 의존적(problem-dependent) 고확률 후회 경계(regret bound)를 증명합니다. 특히, 이 추가 비용은 시간 지평(horizon)에 따라 증가하지 않습니다. 고정된 간격(gap)과 충분히 긴 시간 지평에 대해 균등 도전자 표본추출 조건 하에서 $\Omega\left((K-k)/q\right)$ 후회 하한을 도출하여, 부분 후보 접근 자체가 불가피한 후회 비용을 수반함을 보여줍니다. 실험 결과, \textsc{PC-LinUCB}는 유사한 수준의 후회를 유지하면서 LinUCB의 속도를 대폭 가속하며, 지속적 후보 메커니즘이 LinUCB를 넘어 다른 알고리즘으로도 확장될 수 있음을 보입니다.
오분류 리덕션을 통한 비정상 선형 밴딧의 동적 후회
Dynamic Regret for Non-Stationary Linear Bandits via Misspecification Reductions
용량 제약이 있는 지연 피드백 온라인 볼록 최적화
Capacity-Constrained Online Convex Optimization with Delayed Feedback
커널 밴딧(Kernel Bandits)에 대한 일반적인 $\widetildeΩ(\sqrt{Tγ_T})$ 하한
A General $\widetildeΩ(\sqrt{T γ_T})$ Lower Bound for Kernel Bandits
커널 밴딧(kernel bandit) 문제는 주어진 재생 커널 힐베르트 공간(Reproducing Kernel Hilbert Space, RKHS)에서 유계 노름(bounded norm)을 갖는 미지의 함수를 잡음이 있는 피드백(noisy feedback)을 통해 순차적으로 최적화하는 문제이다. 커널 밴딧의 후회(regret) 분석에서 중심이 되는 양은 최대 정보 획득량(maximum information gain) $γ_T$이다. 특히, 기존에 알려진 가장 좋은 상한(upper bound)은 로그 항(log factor)을 제외하면 $\sqrt{Tγ_T}$로 스케일링되며, 제곱 지수(squared exponential) 커널과 마테른(Matérn) 커널과 같은 특정 커널에 대해서는 이와 거의 일치하는 하한(lower bound)이 도출되어 왔다. 그러나 일반적인 커널에 대한 하한은 부족하여, 어느 정도의 일반성에서 상한이 근사 최적(near-optimal)인지가 불분명하다. 본 논문에서는 콤팩트 정의역(compact domain) 상의 비상수 연속 커널(non-constant continuous kernel)에 대해 일반적인 $Ω(\sqrt{Tγ_T/\log T})$ 미니맥스 후회 하한을 수립하여, 매우 일반적인 의미에서 (로그 항 범위 내에서의) 근사 최적성을 입증한다. 우리는 이 하한에 나타나는 로그 항이 일반적으로는 피할 수 없음을 보이지만, 특정 조건 하에서는 이를 제거할 수 있음을 보인다. 특히 우리의 결과는 $ν\in (0,2)$인 마테른-$ν$(Matérn-$ν$) 커널, $γ\in (0,2)$인 $γ$-지수(γ-exponential) 커널, 그리고 특정 조각별 다항식(piecewise-polynomial) 커널에 대해 미니맥스 최적 스케일링이 (상수 인자 범위 내에서) 정확히 $Θ(\sqrt{Tγ_T})$임을 함의한다.
클러스터 인식 스케칭을 통한 효율적인 선형 밴딧
Efficient Linear Bandits via Cluster-Aware Sketching
본 논문에서는 유한한 아암 집합(finite arm set)을 갖는 고차원 환경에서 선형 밴딧(linear bandit)의 계산 효율성 문제를 연구합니다. 선형 밴딧에서는 특징(feature) 벡터의 차원 $d$가 증가함에 따라 매 업데이트 라운드마다 $O(d^2)$의 계산 비용이 증가하게 됩니다. SOFUL과 같은 전통적인 스케칭(sketching) 기반 방법들은 고정된 크기의 행렬 스케칭을 통해 계산량을 줄이지만, 데이터의 스펙트럼 꼬리(spectral tail)가 두껍고 스케치 크기가 적절히 선택되지 않을 때 무의미한 선형 후회(linear regret)를 초래할 위험이 있습니다. 후회 수렴(convergence)을 보장하고 계산 비용을 효과적으로 줄이기 위해, 우리는 클러스터링 메커니즘을 도입하고 클러스터 스케치 선형 밴딧(CS-LB) 알고리즘을 제안합니다. 제안하는 방법은 스펙트럼 꼬리 취약점 없이 강건한 서브리니어 후회(sublinear regret)를 보장하도록 각 클러스터 내에서 전체 공분산 정보를 보존하고, 각 클러스터에 센티널(sentinel)을 할당하여 클러스터 전환을 수행하며, 조정 가능한 스케치 크기 $l<d$를 통해 라운드당 업데이트 계산량을 $O(l^2d)$로 줄입니다. 합성 데이터셋에 대한 실험은 제안된 방법이 효율성과 후회 간의 유리한 절충(trade-off)을 일관되게 유지함을 보여줍니다.
단일 인덱스 밴딧의 최적 후회
Optimal Regret for Single Index Bandits
우리는 보상이 알 수 없는 보상 함수를 통해 고차원 컨텍스트의 알 수 없는 1차원 투영(projection)에 의존하는 $\textit{단일 인덱스 밴딧}$(single-index bandit) 문제를 연구한다. 이 모델은 선형 및 일반화 선형 밴딧을 비모수적(nonparametric) 설정으로 확장하며, 보상 함수가 사전에 알려지지 않은 경우에 특히 적합하다. 단조(monotone) 보상 함수에 대한 최적 후회(regret) 보장은 알려져 있으나, 일반적인 비단조(non-monotone) 경우는 여전히 잘 이해되지 않으며, 현재까지 알려진 최선의 상한은 $\tilde{\mathcal{O}}(T^{3/4})$이다(보상 함수에 대한 표준 유계성 및 립시츠(Lipschitz) 가정 하에서 [Kang et al., 2025]). 우리는 일반 단일 인덱스 밴딧의 최적 후회를 확립함으로써 이 격차를 해소한다. 우리는 Zoomed Single Index Bandit with Upper Confidence Bound($\texttt{ZoomSIB-UCB}$)라는 간단한 2단계 알고리즘을 제안한다. 이 알고리즘은 먼저 정규화된 스타인(Stein) 추정량을 통해 투영 방향을 추정하고, 이산화(discretization)를 통해 문제를 1차원 밴딧으로 축소한 후 UCB를 적용한다. 이 접근법은 $\tilde{\mathcal{O}}(T^{2/3})$의 후회를 달성하며, 추가적인 가정 없이 기존 연구를 크게 개선한다. 우리는 또한 $\tilde{\Omega}(T^{2/3})$의 일치하는 미니맥스 하한을 증명하여 상한이 본질적으로 타이트함을 보인다. 상한과 하한을 종합하면 단일 인덱스 밴딧에서 후회에 대한 정밀한 특성화를 제공한다. 더불어, 실험 결과는 우리 접근법의 효과성과 강인성을 추가로 입증한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.
저자 비고
arXiv Comments
35 pages; to appear in SODA 2027