Optimal adversarial strategies in learning with expert advice

Anh Truong, Negar Kiyavash

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publication2013 IEEE 52nd Annual Conference on Decision and Control, CDC 2013
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Print)9781467357173
StatePublished - 2013
Externally publishedYes
Event52nd IEEE Conference on Decision and Control, CDC 2013 - Florence, Italy
Duration: Dec 10 2013Dec 13 2013

Publication series

NameProceedings of the IEEE Conference on Decision and Control
ISSN (Print)0743-1546
ISSN (Electronic)2576-2370


Other52nd IEEE Conference on Decision and Control, CDC 2013

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization


Dive into the research topics of 'Optimal adversarial strategies in learning with expert advice'. Together they form a unique fingerprint.

Cite this