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.

本文介绍了一种新的推荐系统模型，其面临探索 - 开发折衷，并可以被建模为多臂老虎机设置，由于用户具有自利性质，因此不能被强制性遵循推荐，作者提出了一种算法以探索为基础，同时考虑到代理人的利益，是一个渐进最优、刺激兼容、先验个体理性的推荐算法。

受托机构强盗

Fiduciary Bandits

Multi-armed bandit problems are the predominant theoretical model of
exploration-exploitation tradeoffs in learning, and they have countless
applications ranging from medical trials, to communication networks, to Web
search and advertising. In many of these application domains the learner may be
constrained by one or more supply (or budget) limits, in addition to the
customary limitation on the time horizon. The literature lacks a general model
encompassing these sorts of problems. We introduce such a model, called
"bandits with knapsacks", that combines aspects of stochastic integer
programming with online learning. A distinctive feature of our problem, in
comparison to the existing regret-minimization literature, is that the optimal
policy for a given latent distribution may significantly outperform the policy
that plays the optimal fixed arm. Consequently, achieving sublinear regret in
the bandits-with-knapsacks problem is significantly more challenging than in
conventional bandit problems.
We present two algorithms whose reward is close to the information-theoretic
optimum: one is based on a novel "balanced exploration" paradigm, while the
other is a primal-dual algorithm that uses multiplicative updates. Further, we
prove that the regret achieved by both algorithms is optimal up to
polylogarithmic factors. We illustrate the generality of the problem by
presenting applications in a number of different domains including electronic
commerce, routing, and scheduling. As one example of a concrete application, we
consider the problem of dynamic posted pricing with limited supply and obtain
the first algorithm whose regret, with respect to the optimal dynamic policy,
is sublinear in the supply.

介绍了一种称为带背包的赌徒问题的通用模型，结合了随机整数规划和在线学习的方面。该论文提出了两种算法来解决这个问题，它们的报酬接近于信息论上的最优解，但同时带背包的赌徒问题相比传统的赌徒问题更具挑战性。