标题： 范数无关的线性Bandits 显示英文标题

标题： Norm-Agnostic Linear Bandits

摘要： 线性上下文-bandit 模型有着广泛的应用，包括推荐系统等，但它有一个很强的假设：算法必须知道未知参数 $\theta^*$ 的范数上界 $S$，而该参数决定了奖励生成。这一假设迫使实践者猜测与置信边界相关的值 $S$，除了希望 $\|\theta^*\|\le S$ 成立以保证后悔值较低外别无选择。本文首次提出不需要这种知识的新算法。具体来说，我们提出了两种算法，并分析了它们的后悔上界：一种适用于动态臂集合设置，另一种适用于固定臂集合设置。对于前者，我们的后悔上界表明，不知道 $S$ 并不会影响后悔上界的主项，只会增加低阶项。对于后者，我们现在不知道 $S$ 并不会在后悔上界中付出代价。 我们的数值实验表明，假设知道$S$的标准算法在$\|\theta^*\|\le S$不成立时可能会 catastrophic 失败，而我们的算法则能保持较低的遗憾。 显示英文摘要

摘要： Linear bandits have a wide variety of applications including recommendation systems yet they make one strong assumption: the algorithms must know an upper bound $S$ on the norm of the unknown parameter $\theta^*$ that governs the reward generation. Such an assumption forces the practitioner to guess $S$ involved in the confidence bound, leaving no choice but to wish that $\|\theta^*\|\le S$ is true to guarantee that the regret will be low. In this paper, we propose novel algorithms that do not require such knowledge for the first time. Specifically, we propose two algorithms and analyze their regret bounds: one for the changing arm set setting and the other for the fixed arm set setting. Our regret bound for the former shows that the price of not knowing $S$ does not affect the leading term in the regret bound and inflates only the lower order term. For the latter, we do not pay any price in the regret for now knowing $S$. Our numerical experiments show standard algorithms assuming knowledge of $S$ can fail catastrophically when $\|\theta^*\|\le S$ is not true whereas our algorithms enjoy low regret.