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. Bud- geted 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 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 conven- tional 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.
이 논문에서는 예산제약이 있는 베이지안 멀티암드벤딧 문제를 고려합니다. 각 암은 선택 시 서로 다른 양의 리소스를소비하며사용할수있는총리소스양에대한예산제약이있습니다. BTS알고리즘은이문제에 대해 매우 효과적인 휴리스틱을 제공하지만 팔 선택 규칙은 나머지 예산 정보를 고려하지 않습니다. 우리는 전통적인 멀티암드벤딧 문제에 대해 톰슨셈플링을 일반화하는 정보완화셈플링 프레임워크를 채택하고 BTS 와 같이 무작위화되지만 예산 제약과 관련하여 그들의 결정을 보다 신중하게 최적화하는 일련의 알고리즘을 제안합니다. 이러한 알고리즘과의 일대일 대응에서 기존 벤치마크를 개선하는 일련의 성능 벤치마크도 제안 됩니다. 이론적 분석 및 시뮬레이션 결과는 알고리즘(및 벤치마크)이 실제 사례를 포함한 다양한 설정에서 BTS(각각 기존 벤치마크)보다 점진적으로 개선되었음을 보여줍니다.
