  We propose to accelerate existing linear bandit algorithms to achieve
per-step time complexity sublinear in the number of arms $K$. The key to
sublinear complexity is the realization that the arm selection in many linear
bandit algorithms reduces to the maximum inner product search (MIPS) problem.
Correspondingly, we propose an algorithm that approximately solves the MIPS
problem for a sequence of adaptive queries yielding near-linear preprocessing
time complexity and sublinear query time complexity. Using the proposed MIPS
solver as a sub-routine, we present two bandit algorithms (one based on UCB,
and the other based on TS) that achieve sublinear time complexity. We
explicitly characterize the tradeoff between the per-step time complexity and
regret, and show that our proposed algorithms can achieve $O(K^{1-\alpha(T)})$
per-step complexity for some $\alpha(T) > 0$ and $\widetilde O(\sqrt{T})$
regret, where $T$ is the time horizon. Further, we present the theoretical
limit of the tradeoff, which provides a lower bound for the per-step time
complexity. We also discuss other choices of approximate MIPS algorithms and
other applications to linear bandit problems.
