Optimal adversarial strategies in learning with expert advice
Optimal adversarial strategies in learning with expert advice
复制标题
在专家建议下学习的最佳对抗策略
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
N. Kiyavash
中科院分区：
文献类型：
--
作者：
A. Truong;N. Kiyavash
我们为专家建议学习框架提出了一种对抗性设置，其中一位专家意图通过提供错误的建议来损害推荐系统。该问题被表述为马尔可夫决策过程（MDP）并通过动态规划来解决。有点令人惊讶的是，我们证明，在对数损失的情况下，恶意专家的最佳策略是每一步都撒谎的贪婪策略。此外，提供了损失函数的充分条件来保证贪婪策略的最优性。然而，我们的实验结果表明，该条件不是必需的，因为即使平方损失不满足条件，当使用平方损失时，贪婪策略也是最优的。此外，实验结果表明，对于绝对损失，最优策略是阈值策略。
We propose an adversarial setting for the framework of learning with expert advice in which one of the experts has the intention to compromise the recommendation system by providing wrong recommendations. The problem is formulated as a Markov Decision Process (MDP) and solved by dynamic programming. Somewhat surprisingly, we prove that, in the case of logarithmic loss, the optimal strategy for the malicious expert is the greedy policy of lying at every step. Furthermore, a sufficient condition on the loss function is provided that guarantees the optimality of the greedy policy. Our experimental results, however, show that the condition is not necessary since the greedy policy is also optimal when the square loss is used, even though the square loss does not satisfy the condition. Moreover, the experimental results suggest that, for absolute loss, the optimal policy is a threshold one.