Reference Request: I am interested in references where Yao's Minimax Principle is applied for adaptive randomized algorithms if any. More generally, I am interested in minimax lower bound results for adaptive randomized algorithms.

  • $\begingroup$ This is... very broad. Any subarea in particular? $\endgroup$
    – Clement C.
    Jul 2, 2020 at 23:10
  • $\begingroup$ I am interested in understanding repeated games where one player is adaptive and the other is oblivious. Example, adversarial bandits if you are familiar with that setup. As per my limited understanding, Yao's minimax principle works when both the players are oblivious. I don't see if any easy mapping to the setting of Yao's minimax principle is possible. $\endgroup$ Jul 3, 2020 at 6:11

1 Answer 1


You may find this video useful:


Also, this video here (time 00:43) states some books that can help:



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.