Asymptotically efficient adaptive strategies in repeated games. 1. Certainty equivalence strategies

This paper addresses the problem of dynamic decision making in an uncertain and competitive environment. A decision maker (player 1) faces a system about which he has some (parametric) uncertainty, and which is affected also by the actions of other agents. We focus on a worst-case analysis from the viewpoint of player 1, using the simplified model of a repeated matrix game with lack of information on one side, where single-stage rewards are random but announced, and perfect observations are assumed. Certain ideas from the field of stochastic adaptive control are used to formulate performance criteria in a non-Bayesian setting, and to devise appropriate control strategies. The basic performance measure is the total reward accumulated by player 1 over all stages played; the purpose of player 1 is to guarantee that his expected total reward will be “close” to what he could guarantee under complete information. The present paper considers adaptive decision strategies of the Certainty Equivalence type, based on (modified) Maximum Likelihood estimator, and studies their asymptotic (long-term) performance. A sequel paper will be devoted to “asymptotically optimal” strategies.