Budget-Constrained Bandits over General Cost and Reward Distributions
Budget-Constrained Bandits over General Cost and Reward Distributions
复制标题
DOI：
--
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
Semih Cayci;A. Eryilmaz;R. Srikant
中科院分区：
文献类型：
--
作者：
Semih Cayci;A. Eryilmaz;R. Srikant
我们考虑一个无约束的强盗问题，其中每个手臂拉招致一个随机的成本，并产生一个随机的回报。目标是在总成本的预算约束下，最大化总期望报酬。该模型是通用的，因为它允许相关的和潜在的重尾的成本回报对，可以采取负值，如许多应用程序所要求的。我们表明，如果时刻的顺序$（2+\gamma）$的一些$\gamma > 0$存在的所有成本回报对，$O（\log B）$后悔是可实现的预算$B>0$。为了实现严格的遗憾界，我们提出了算法，利用成本和回报之间的相关性，通过提取共同的信息，通过线性最小均方误差估计的每个手臂。我们证明了这个问题的遗憾下界，并表明，所提出的算法实现紧问题相关的遗憾界，这是最佳的联合高斯成本和奖励对的情况下，一个普遍的常数因子。
We consider a budget-constrained bandit problem where each arm pull incurs a random cost, and yields a random reward in return. The objective is to maximize the total expected reward under a budget constraint on the total cost. The model is general in the sense that it allows correlated and potentially heavy-tailed cost-reward pairs that can take on negative values as required by many applications. We show that if moments of order $(2+\gamma)$ for some $\gamma > 0$ exist for all cost-reward pairs, $O(\log B)$ regret is achievable for a budget $B>0$. In order to achieve tight regret bounds, we propose algorithms that exploit the correlation between the cost and reward of each arm by extracting the common information via linear minimum mean-square error estimation. We prove a regret lower bound for this problem, and show that the proposed algorithms achieve tight problem-dependent regret bounds, which are optimal up to a universal constant factor in the case of jointly Gaussian cost and reward pairs.