Asymptotically Efficient Adaptive Strategies in Repeated Games Part II. Asymptotic Optimality

This paper continues the analysis of a dynamic decision problem modeled as a two-person repeated game with random rewards, perfect observations, and incomplete information on one side. The emphasis is on strategies of player 1 (the uninformed player) which maximize his worst-case total reward in a strong non-Bayesian sense, namely, for all possible states of nature. An asymptotic bound on performance is first established, followed by the construction of strategies which achieve this bound. The analysis highlights the efficient acquisition of (statistical) information under conflict conditions, and especially the relations between information and payoff which are inherent in this problem.