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.
2
-
$\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$– Soumya BasuJul 3, 2020 at 6:11
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
You may find this video useful:
https://www.youtube.com/watch?v=0vrqCDcxbxs&t=22s
Also, this video here (time 00:43) states some books that can help:
