Fiduciary Bandits
  Recommendation systems often face exploration-exploitation tradeoffs: the
system can only learn about the desirability of new options by recommending
them to some user. Such systems can thus be modeled as multi-armed bandit
settings; however, users are self-interested and cannot be made to follow
recommendations. We ask whether exploration can nevertheless be performed in a
way that scrupulously respects agents' interests---i.e., by a system that acts
as a fiduciary. More formally, we introduce a model in which a recommendation
system faces an exploration-exploitation tradeoff under the constraint that it
can never recommend any action that it knows yields lower reward in expectation
than an agent would achieve if it acted alone. Our main contribution is a
positive result: an asymptotically optimal, incentive compatible, and ex-ante
individually rational recommendation algorithm.
