Contextual bandit with linear reward functions is among one of the most
extensively studied models in bandit and online learning research. Recently,
there has been increasing interest in designing \emph{locally private} linear
contextual bandit algorithms, where sensitive information contained in contexts
and rewards is protected against leakage to the general public. While the
classical linear contextual bandit algorithm admits cumulative regret upper
bounds of $\tilde O(\sqrt{T})$ via multiple alternative methods, it has
remained open whether such regret bounds are attainable in the presence of
local privacy constraints, with the state-of-the-art result being $\tilde
O(T^{3/4})$. In this paper, we show that it is indeed possible to achieve an
$\tilde O(\sqrt{T})$ regret upper bound for locally private linear contextual
bandit. Our solution relies on several new algorithmic and analytical ideas,
such as the analysis of mean absolute deviation errors and layered principal
component regression in order to achieve small mean absolute deviation errors.

通过分析均值绝对偏差误差和分层主成分回归，我们展示了一种能够在局部隐私线性情境播放机中实现 O (√T) 累积遗憾上界的解决方案。