Satisficing in Multi-Armed Bandit Problems
Satisficing in Multi-Armed Bandit Problems
复制标题
满足多臂老虎机问题
DOI：
--
复制
发表时间：
2015
影响因子：
6.8
通讯作者：
Naomi Ehrich Leonard
中科院分区：
文献类型：
--
作者：
Paul B. Reverdy;Vaibhav Srivastava;Naomi Ehrich Leonard
满意是最大化的放松，并允许在面对不确定性时做出风险较小的决策。我们提出了两套满意的多臂强盗问题的目标，其中的目标是实现奖励为基础的决策性能高于给定的阈值。我们表明，这些新的问题是等价于各种标准的多臂强盗问题，最大化的目标，并使用等价性找到性能的界限。不同的目标可能导致不同的行为;例如，代理人在一种情况下不断探索他们的选项，而在另一种情况下只有有限的次数。对于高斯奖励的情况下，我们显示了一个额外的等价性之间的两套satisficing的目标，允许算法开发的一套适用于其他。然后，我们开发的可信上限（UCL）算法，解决问题的满意的目标，并表明这些修改后的UCL算法实现有效的满意性能的变种。
Satisficing is a relaxation of maximizing and allows for less risky decision making in the face of uncertainty. We propose two sets of satisficing objectives for the multi-armed bandit problem, where the objective is to achieve reward-based decision-making performance above a given threshold. We show that these new problems are equivalent to various standard multi-armed bandit problems with maximizing objectives and use the equivalence to find bounds on performance. The different objectives can result in qualitatively different behavior; for example, agents explore their options continually in one case and only a finite number of times in another. For the case of Gaussian rewards we show an additional equivalence between the two sets of satisficing objectives that allows algorithms developed for one set to be applied to the other. We then develop variants of the Upper Credible Limit (UCL) algorithm that solve the problems with satisficing objectives and show that these modified UCL algorithms achieve efficient satisficing performance.