We study the linear contextual bandit problem with finite action sets. When
the problem dimension is $d$, the time horizon is $T$, and there are $n \leq
2^{d/2}$ candidate actions per time period, we (1) show that the minimax
expected regret is $\Omega(\sqrt{dT (\log T) (\log n)})$ for
研究此论文中的上下文臂带，其中上下文是独立且恒定分布的 d 维随机向量，期望回报在臂参数和上下文中都是线性的；提出了一种截断版的 LinUCB 算法，称为 Tr-LinUCB，其在截断时间 S 之前遵循 LinUCB，在之后进行纯粹的开发，S=Cd log（T）时达到 O（d log（T））的遗憾，如果 S = d log（T）的某个升幂，则相对于最优解的损失是费用为 loglog（T）的乘法，这种对超调敏感的 Tr-LinUCB 算法的实用重要性。