arXiv:2309.06349v2 stat.ML

분수 사후분포를 이용한 Thompson Sampling의 일반화 후회 분석

Generalized Regret Analysis of Thompson Sampling using Fractional Posteriors

Prateek Jaiswal, Debdeep Pati, Anirban Bhattacharya, Bani K. Mallick

제출 2023-09-12

한국어 초록

Thompson sampling(TS)은 확률적 다중 팔 밴딧(multi-armed bandit) 문제를 푸는 데 가장 널리 쓰이고 초기부터 알려진 알고리즘 중 하나이다. 표준 사후분포 대신 분수 또는 $α$-사후분포($α\in(0,1)$)를 사용하는 TS 변형인 $α$-TS를 고려한다. $α$-사후분포를 계산할 때, 표준 사후분포 정의에 들어 있는 가능도는 인자 $α$로 tempering된다. $α$-TS에 대해 사전과 보상 분포에 매우 완만한 조건 하에서 instance-dependent $\mathcal{O}\left(\sum_{k \neq i^*} Δ_k\left(\frac{\log(T)}{C(α)Δ_k^2} + \frac{1}{2} \right)\right)$ 및 instance-independent $\mathcal{O}(\sqrt{KT\log K})$ 빈도주의 후회 상한을 모두 얻는다. 여기서 $Δ_k$는 $k$번째 팔과 최적 팔의 참 보상 평균 간 gap이고, $C(α)$는 알려진 상수이다. 서브가우시안(sub-Gaussian) 및 지수족(exponential family) 모델 모두 보상 분포에 대한 우리의 일반 조건을 만족한다. 사전 분포에 대한 조건은 양수이고 연속적이며 유계인 밀도로 쉽게 만족시킬 수 있다. 또한 상수까지 improved UCB [Auer and Ortner, 2010]와 (상수 차이 내에서) 일치하는 또 다른 instance-dependent 후회 상한을 제시한다. 후회 분석은 $α$-사후분포에 대한 비점근 집중 분석과 Bernstein–von Mises 유형 결과의 최근 이론적 발전을 신중하게 적응·결합한다. 더 나아가, 분석은 폐형 사후분포나 켤레 사전(conjugate prior) 같은 추가 구조적 성질을 요구하지 않는다.

원문 초록

Thompson sampling (TS) is one of the most popular and earliest algorithms to solve stochastic multi-armed bandit problems. We consider a variant of TS, named $α$-TS, where we use a fractional or $α$-posterior ($α\in(0,1)$) instead of the standard posterior distribution. To compute an $α$-posterior, the likelihood in the definition of the standard posterior is tempered with a factor $α$. For $α$-TS we obtain both instance-dependent $\mathcal{O}\left(\sum_{k \neq i^*} Δ_k\left(\frac{\log(T)}{C(α)Δ_k^2} + \frac{1}{2} \right)\right)$ and instance-independent $\mathcal{O}(\sqrt{KT\log K})$ frequentist regret bounds under very mild conditions on the prior and reward distributions, where $Δ_k$ is the gap between the true mean rewards of the $k^{th}$ and the best arms, and $C(α)$ is a known constant. Both the sub-Gaussian and exponential family models satisfy our general conditions on the reward distribution. Our conditions on the prior distribution can be easily satisfied by a density that is positive, continuous, and bounded. We also establish another instance-dependent regret upper bound that matches (up to constants) to that of improved UCB [Auer and Ortner, 2010]. Our regret analysis carefully adapts and combines recent theoretical developments in the non-asymptotic concentration analysis and Bernstein-von Mises type results for the $α$-posterior distribution. Moreover, our analysis does not require additional structural properties such as closed-form posteriors or conjugate priors.

제출 이력

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

  1. arXiv:2309.06349v2제출 시각 미확인

함께 살펴볼 논문

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

토론

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