arXiv:2408.15535

Improving Thompson Sampling via Information Relaxation for Budgeted Multi-armed Bandits

Woojin Jeong, Seungki Min

제출 2024-08-28

원문 초록

We consider a Bayesian budgeted multi-armed bandit problem, in which each arm consumes a different amount of resources when selected and there is a budget constraint on the total amount of resources that can be used. Budgeted Thompson Sampling (BTS) offers a very effective heuristic to this problem, but its arm-selection rule does not take into account the remaining budget information. We adopt \textit{Information Relaxation Sampling} framework that generalizes Thompson Sampling for classical $K$-armed bandit problems, and propose a series of algorithms that are randomized like BTS but more carefully optimize their decisions with respect to the budget constraint. In a one-to-one correspondence with these algorithms, a series of performance benchmarks that improve the conventional benchmark are also suggested. Our theoretical analysis and simulation results show that our algorithms (and our benchmarks) make incremental improvements over BTS (respectively, the conventional benchmark) across various settings including a real-world example.

함께 살펴볼 논문

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

arXiv:2607.09688v1cs.LG공통 태그 Thompson Sampling, Multi-Armed Bandits

Prioritizing Search Space Regions in the Low Autocorrelation Binary Sequences Problem

낮은 자기상관 이진 수열 문제(LABS)는 통신, 신호 처리, 위성 항법 분야에서 중요한 응용을 갖는 어려운 조합 최적화 과제이다. 본 논문은 LABS 탐색 공간의 제한 클래스에 걸쳐 계산 노력을 적응적으로 배분하기 위해 Thompson 샘플링과 병렬 자기회피 보행(self-avoiding walk)을 결합한 하이브리드 탐색 프레임워크를 제안한다. 파티션을 다중 팔 밴딧(multi-armed bandit) 설정의 팔(arm)로 모델링함으로써, 제안된 방법은 덜 샘플링된 영역의 탐험(exploration)을 유지하면서도 경험적으로 더 높은 성능 지수(merit factor)를 산출하는 파티션 쪽으로 탐색 자원을 동적으로 전환한다. 이 접근법은 GPU 병렬 실행, 공유 사후 업데이트, 효율적인 이웃 평가, 그리고 사이클 방지를 위한 블룸 필터(Bloom filter)를 통해 추가로 가속된다. 또한 제약된 분할 비대칭 공간(partitioned skew-symmetric space)을 먼저 탐색한 후 비제약 공간에서 최적 후보를 정제하는 2단계 최적화 전략을 사용한다. 긴 이진 수열에 대한 실험 결과, 제안된 방법은 $450 \le L \le 527$ 범위의 35개 수열 길이와 $L=573$에 대해 이전에 알려진 최선의 결과를 개선하였다. 특히 $L=451$에서 성능 지수 8.0을 초과하는 새로운 최장 수열을 보고한다. 결과는 또한 Thompson 샘플링이 더 나은 관측 성능을 보이는 파티션을 효과적으로 우선시함을 보여주며, LABS 최적화에서 온라인 데이터 기반 자원 배분의 가치를 확인한다. 전반적으로 제안된 프레임워크는 고성능 성능 지수 최대화를 위한 확장 가능하고 효과적인 전략을 제공한다.

arXiv:2606.28616v1cs.LG공통 태그 Thompson Sampling, Multi-Armed Bandits

절댓값 섭동을 통한 선형 밴딧의 무작위 탐험

Randomized Exploration for Linear Bandits via Absolute Perturbations

확률적 선형 밴딧(stochastic linear bandits)에서 표준적인 상한 신뢰 구간(UCB) 알고리즘은 간단한 빈도주의 후회(regret) 분석을 허용하지만 계산 비용이 클 수 있는 반면, 톰슨 샘플링(Thompson Sampling, TS)은 계산 효율이 높지만 낙관적이지 않은 특성으로 인해 분석이 일반적으로 더 어렵다. 본 논문에서는 부호 있는 탐험(exploration) 노이즈를 절댓값으로 대체함으로써 기댓값 측면에서 낙관성을 보장하는 TS의 간단한 변형인 절댓값 톰슨 샘플링(Absolute Thompson Sampling, ATS)을 제안한다. 이는 TS의 계산 효율성을 유지하면서 TS 분석에서 흔히 요구되는 기술적으로 복잡한 반집중(anti-concentration) 논증을 피할 수 있어, UCB 방식의 단순한 후회 분석이 가능하다. ATS가 $\tilde{O}(d^{3/2}\sqrt{K})$의 후회를 달성함을 보이며, 이는 선형 밴딧에서 TS에 대한 기존 경계와 일치한다. 나아가 앙상블(ensemble) 크기로 정규화(normalization)하여 여러 절댓값 섭동에 대한 최댓값을 취하는 앙상블 절댓값 톰슨 샘플링(Ensemble Absolute Thompson Sampling, EATS)을 도입한다. 앙상블 크기가 커질수록 EATS는 UCB 목적함수로 수렴하여 극한에서 UCB 동작을 회복한다. 실험 결과, 중간 크기의 앙상블만으로도 이미 강력한 성능을 발휘함을 보인다. 본 결과는 이론과 실제 모두에서 무작위 탐험과 결정론적 낙관주의 사이의 가교를 제시한다.

arXiv:2606.21757v1cs.LG공통 태그 Thompson Sampling, Multi-Armed Bandits

AdaPrivate-TS: Private Thompson Sampling for Contextual Bandits with Privacy Amplification

우리는 Thompson Sampling과 배치 zCDP 합성을 결합한 차등 프라이버시(differentially private) 문맥적 밴딧 알고리즘인 AdaPrivate-TS를 제안한다. 핵심 통찰은 차등 프라이버시 노이즈가 사후 공분산을 구조적인 방식으로 팽창시킨다는 점이다. 즉, $b$에 가우시안 노이즈 $N(0,σ^2 I)$를 추가하면 샘플링 공분산이 $v^2 A^{-1} + σ^2 A^{-2}$가 되며, Thompson Sampling은 이를 순수한 손상이 아닌 불확실성 증가로 해석한다. 확률적 문맥 하에서의 이벤트 수준 프라이버시(개별 상호작용 보호)의 경우, 병렬 합성이 배치 전반에 걸쳐 노이즈를 분산시키기 때문에 프라이버시 비용이 $T$에 대해 로그 스케일인 $O(\sqrt{d}\,\log T/\sqrt{ρ})$에 불과함을 증명한다. 또한, 엄격한 프라이버시 예산에서 유효 노이즈를 줄일 수 있는 푸아송 서브샘플링을 통한 프라이버시 증폭을 탐구한다. 합성 및 실세계 데이터셋에 대한 실험 결과는 다음을 보여준다. (1) AdaPrivate-TS는 $\varepsilon \in [0.5, 5]$에서 비공개 성능의 93-99%를 달성하며, UCB 대비 0.5-3.7%, 극단적인 $\varepsilon$에서 적응형 탐험 튜닝 시 최대 18%까지 성능을 능가한다. (2) 프라이버시 증폭은 낮은 $\varepsilon$에서 추가적으로 2-5%의 성능 향상을 제공한다. (3) MovieLens 및 Jester에서 AdaPrivate-TS는 이벤트 수준 기준 모델 중 전반적으로 최고 성능을 달성하며 $\varepsilon \geq 2$에서 지배적이다. (4) DP-SVD 비공개 특징 하에서 UCB 대비 Thompson Sampling의 우위가 +11%까지 증가하며, 이는 노이즈-불확실성 해석이 보상 프라이버시에만 국한되지 않음을 확인한다. 우리는 인터랙티브 zCDP 합성 하에서의 프라이버시 보장에 대한 엄밀한 증명과 수렴 곡선, 12-시드 신뢰구간, DP-SVD 특징 절제 실험을 포함한 포괄적인 평가를 제공한다.

arXiv:2602.06014v2cs.LG공통 태그 Thompson Sampling, Multi-Armed Bandits

Optimism Stabilizes Thompson Sampling for Adaptive Inference

톰슨 샘플링(TS)은 확률적 다중 슬롯머신(multi-armed bandit) 문제에 널리 활용되지만, 적응적 데이터 수집 환경에서의 추론 특성은 미묘하다. 표본 평균에 대한 고전적 점근 이론은 각 팔(arm)별 표본 크기가 확률적이며 행동 선택 규칙을 통해 보상과 결합되어 있기 때문에 실패할 수 있다. 본 연구에서는 독립적인 준가우시안(sub-Gaussian) 보상 잡음을 갖는 $K$-팔 확률적 다중 슬롯머신에서 가우시안 무작위 인덱스를 사용하는 톰슨 샘플링의 적응적 추론을 연구하고, 각 팔의 선택 횟수가 결정론적 척도 주변에 집중되는 \emph{안정성}을 회복하는 핵심 메커니즘으로 \emph{낙관주의(optimism)}를 규명한다. 이 안정성은 적응적 샘플링에도 불구하고 점근적으로 유효한 왈드(Wald) 추론을 가능하게 한다. 첫째, 여러 팔이 최적인 도전적인 체제를 포함하여 임의의 $K \ge 2$에 대해 분산 팽창 TS가 안정적임을 증명하며, 최적 팔들에 대한 점근적으로 균일한 할당과 준최적 팔들에 대한 날카로운 로그 선택 횟수 점근론을 도출한다. 이는 새로운 승자 맵(winner-map) 및 리아푸노프 드리프트(Lyapunov-drift) 기법을 활용하여 여러 최적 팔 간의 할당을 제어함으로써 \citet{halder2025stable}이 제기한 $K$-팔 확장 문제를 해결한다. 둘째, 가우시안 인덱스 분산은 유지하되 인덱스 중심에 명시적인 평균 보너스를 추가하는 대안적인 낙관적 수정을 분석하고, 유사한 안정성 결론을 도출한다. 요약하면, 적절하게 구현된 낙관주의는 톰슨 샘플링을 안정화하고 다중 슬롯머신 문제에서 점근적으로 유효한 왈드 추론을 가능하게 하며, 단지 완만한 추가적인 후회(regret) 비용만을 수반한다.

토론

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