1비트 통신 제약 하의 배치 확률적 선형 밴딧
Batched Stochastic Linear Bandits with 1-Bit Communication Constraints
한국어 초록
본 논문은 배치와 통신 제약이 자연스럽게 결합된 확률적 선형 밴딧을 연구한다. 시간 지평은 크기가 $B$로 동일한 배치들로 나뉘며, 각 배치 동안 학습자는 요청한 $B$개의 팔 선택을 에이전트에게 보내고, 에이전트는 해당하는 $B$개의 보상을 관측한 뒤 학습자에게 단 1비트의 피드백으로 응답한다. 각 배치마다 학습자는 에이전트가 사용할 1비트 양자화 규칙을 지정하며, 이 규칙은 이전에 받은 모든 비트에는 의존할 수 있으나 과거의 보상에 직접 의존할 수는 없다. 이 설정은 라운드별 양자화만 있거나 총 비트 예산만 있는 기존 모델들 사이의, 중요하지만 탐구되지 않았던 ``중간 지대''를 다룬다. 노이즈가 없는 경우에도 1비트 통신 병목 때문에 $\Omega(B\min\{d,\log\lvert \mathcal{A} \rvert\})$의 후회가 불가피함을 보이는 미니맥스 하한을 증명한다. 표준적인 통계적 한계와 결합하면 $\widetilde{\Omega}(B\min\{d,\log\lvert \mathcal{A} \rvert\} + \sqrt{dT \min\{d,\log\lvert \mathcal{A} \rvert\}})$의 일반적인 하한이 도출된다. $G$-최적 설계와 1비트 평균 추정에 기반한 두 가지 단계적 제거 알고리즘을 개발한다. 첫 번째는 $\widetilde{O}(dB + d\sqrt{T})$의 후회를 달성하며 $\lvert \mathcal{A} \rvert = \exp(\Omega(d))$일 때 로그 인자를 제외하고 하한과 일치한다. 두 번째는 안전한 팔 식별과 웜스타트 절차를 도입하여 $\widetilde{O}(B\log\lvert \mathcal{A} \rvert + d^{3/2}\sqrt{B} + \sqrt{dT\log\lvert \mathcal{A} \rvert})$의 후회를 얻으며, 이는 $(\lvert \mathcal{A} \rvert, B, d, T)$의 폭넓은 스케일링 영역에서 거의 최적이다. 종합하면, 본 결과는 배치 크기가 $\Theta(\sqrt{T})$만큼 큰 경우에도, 배치당 단 1비트의 피드백만으로 폭넓은 스케일링 영역에서 제약 없는 선형 밴딧의 미니맥스 후회에 거의 근접할 수 있음을 보여준다.
원문 초록
We study stochastic linear bandits under a natural combination of batching and communication constraints: the time horizon is partitioned into batches of equal size $B$, and during each batch the learner sends $B$ requested arm pulls to an agent, who then observes the corresponding $B$ rewards and responds with a single bit of feedback to the learner. For each batch, the learner specifies the 1-bit quantization rule the agent uses, which may depend on all previously received bits but not on any past rewards directly. This setting addresses a significant yet unexplored ``middle ground'' between previous models having per-round quantization only or total bit budgets only. We establish a minimax lower bound showing that $\Omega(B\min\{d,\log\lvert \mathcal{A} \rvert\})$ regret is unavoidable due to the 1-bit communication bottleneck, even in the absence of noise. Combined with standard statistical limits, this yields a general lower bound of $\widetilde{\Omega}(B\min\{d,\log\lvert \mathcal{A} \rvert\} + \sqrt{dT \min\{d,\log\lvert \mathcal{A} \rvert\}})$. We develop two phased-elimination algorithms based on $G$-optimal designs and 1-bit mean estimation. The first achieves $\widetilde{O}(dB + d\sqrt{T})$ regret, matching the lower bound up to logarithmic factors when $\lvert \mathcal{A} \rvert = \exp(\Omega(d))$, and the second incorporates a safe-arm identification and warm-start procedure to obtain $\widetilde{O}(B\log\lvert \mathcal{A} \rvert + d^{3/2}\sqrt{B} + \sqrt{dT\log\lvert \mathcal{A} \rvert})$ regret, which is near-optimal in broad scaling regimes of $(\lvert \mathcal{A} \rvert, B, d, T)$. Together, our results demonstrate that a single bit of feedback per batch suffices to nearly match the minimax regret of unconstrained linear bandits in broad scaling regimes, even for batch sizes as large as $\Theta(\sqrt{T})$.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2605.30976v2제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.