Structured Stochastic Linear Bandits
Structured Stochastic Linear Bandits
复制标题
结构化随机线性老虎机
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
A. Banerjee
中科院分区：
文献类型：
--
作者：
Nicholas Johnson;V. Sivakumar;A. Banerjee
随机线性匪徒问题是在每轮算法中从决策集中选择向量的综合症，然后它接收到未知向量的嘈杂的线性损失参数。这样一个问题的目标是最大程度地减少（伪）的遗憾，这是算法的总预期损失与事后最佳固定向量的总预期损失之间的差异。在本文中，我们考虑未知参数具有结构的设置，例如，稀疏，稀疏，低秩，可以通过标准捕获，例如$ l_1 $，$ l _ {（1,2）} $，核准则。我们专注于构建具有高概率的所有回合中包含未知参数的置信椭圆形。我们显示了此类椭圆形的半径取决于与捕获结构相关的集合的高斯宽度。这种表征会导致较紧密的信心椭圆形，因此，与基于环境维度的现有文献相比，与现有文献中的界限相比，后悔的界限更加明显。
The stochastic linear bandit problem proceeds in rounds where at each round the algorithm selects a vector from a decision set after which it receives a noisy linear loss parameterized by an unknown vector. The goal in such a problem is to minimize the (pseudo) regret which is the difference between the total expected loss of the algorithm and the total expected loss of the best fixed vector in hindsight. In this paper, we consider settings where the unknown parameter has structure, e.g., sparse, group sparse, low-rank, which can be captured by a norm, e.g., $L_1$, $L_{(1,2)}$, nuclear norm. We focus on constructing confidence ellipsoids which contain the unknown parameter across all rounds with high-probability. We show the radius of such ellipsoids depend on the Gaussian width of sets associated with the norm capturing the structure. Such characterization leads to tighter confidence ellipsoids and, therefore, sharper regret bounds compared to bounds in the existing literature which are based on the ambient dimensionality.