Regret vs. Bandwidth Trade-off for Recommendation Systems

Linqi Song, Christina Fragouli, Devavrat Shah

Published 2018-10-15Version 1

We consider recommendation systems that need to operate under wireless bandwidth constraints, measured as number of broadcast transmissions, and demonstrate a (tight for some instances) tradeoff between regret and bandwidth for two scenarios: the case of multi-armed bandit with context, and the case where there is a latent structure in the message space that we can exploit to reduce the learning phase.