Optimal Attack Strategies Against Predictors - Learning from Expert Advice

Motivated by many real-world examples, such as recommendation systems or sensor fusion, and aiming to capture the influence of malicious experts who intentionally degrade the performance of learning systems, we analyze optimal adversarial strategies against the weighted average prediction algorithm in the learning with expert advice framework. All but one expert is honest and the malicious expert's goal is to sabotage the performance of the algorithm by strategically providing dishonest recommendations. We formulate the problem as a Markov decision process and analyze it under various settings. For the logarithmic loss, somewhat surprisingly, we prove that the optimal strategy for the adversary is the greedy policy, i.e., lying at every step. For the absolute loss, in the 2-experts, discounted cost setting, we prove that the optimal strategy is a threshold policy, where the malicious expert tells the truth until he earns enough weight and then lies afterwards. We extend the results to the infinite horizon problem and find the exact thresholds for the stationary optimal policy. Finally, we use a mean field approach in the N-experts setting to find the optimal strategy when the predictions of the honest experts are independent and identically distributed. We justify our results using simulations throughout this paper.