  Recommendation systems are a key modern application of machine learning, but
they have the downside that they often draw upon sensitive user information in
making their predictions. We show how to address this deficiency by basing a
service's recommendation engine upon recommendations from other existing
services, which contain no sensitive information by nature. Specifically, we
introduce a contextual multi-armed bandit recommendation framework where the
agent has access to recommendations for other services. In our setting, the
user's (potentially sensitive) information belongs to a high-dimensional latent
space, and the ideal recommendations for the source and target tasks (which are
non-sensitive) are given by unknown linear transformations of the user
information. So long as the tasks rely on similar segments of the user
information, we can decompose the target recommendation problem into systematic
components that can be derived from the source recommendations, and
idiosyncratic components that are user-specific and cannot be derived from the
source, but have significantly lower dimensionality. We propose an
explore-then-refine approach to learning and utilizing this decomposition; then
using ideas from perturbation theory and statistical concentration of measure,
we prove our algorithm achieves regret comparable to a strong skyline that has
full knowledge of the source and target transformations. We also consider a
generalization of our algorithm to a model with many simultaneous targets and
no source. Our methods obtain superior empirical results on synthetic
benchmarks.
