  In this paper, we investigate a novel problem of building contextual bandits
in the vertical federated setting, i.e., contextual information is vertically
distributed over different departments. This problem remains largely unexplored
in the research community. To this end, we carefully design a customized
encryption scheme named orthogonal matrix-based mask mechanism(O3M) for
encrypting local contextual information while avoiding expensive conventional
cryptographic techniques. We further apply the mechanism to two commonly-used
bandit algorithms, LinUCB and LinTS, and instantiate two practical protocols
for online recommendation under the vertical federated setting. The proposed
protocols can perfectly recover the service quality of centralized bandit
algorithms while achieving a satisfactory runtime efficiency, which is
theoretically proved and analyzed in this paper. By conducting extensive
experiments on both synthetic and real-world datasets, we show the superiority
of the proposed method in terms of privacy protection and recommendation
performance.
