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.

本文针对预算多臂赌博机问题，提出了改进的汤普森采样方法以解决资源预算限制带来的选择不足。通过采用信息松弛采样框架，该研究提出了一系列随机算法，更加优化了决策过程，对比传统基准也得到了显著的改进。理论分析和模拟结果表明，所提算法在多个场景中均优于预算汤普森采样，展现了良好的应用前景。

通过信息松弛改进预算多臂赌博机中的汤普森采样