Regret Minimization in Signal Space for Repeated Matrix Games with Partial Observations
The Bayes Envelope of a repeated matrix game traces the maximal payoo rate that a player (say P1) could secure for herself had she known in advance the empirical frequency of P2's actions. It was shown by J. Hannan (1957) that Regret Minimizing policies for P1 exist which asymptotically attain the Bayes Envelope even without such prior knowledge, but assuming a complete observation of the P2's action at each stage. Recently, these results have been extended to the case where the other player's action is not fully observed but rather some signal that is related to it. In this paper we consider a simpliied concept of the Bayesian envelope for the incomplete observation case, which is constrained to rely only on the relative frequencies of the observed signals and rewards. An important class of games for which this type of constraint seems to arise naturally is when the stage game itself involves sequential moves, so that P2's normal-form action actually corresponds to an extensive form strategy, and the unobserved part of this \action" actually corresponds to decisions that have never materialized. We ooer a solution which naturally extends the Bayes envelope concept in the reward-signals space by taking worst-case view over missing information, and show that taking the convex hull of the resulting envelope is required in order to obtain an achievable envelope. A detailed study of a speciic (Stackelberg-type) stage game in which P1 moves before P2 is used to highlight several basic properties of the proposed envelope. The analysis relies on appropriate applications of Blackwell's approachability theory.