Conditional universal consistency

Players choose an action before learning an outcome chosen according to an unknown and history-dependent stochastic rule. Procedures that categorize o utcomes, and use a randomized variation on fictitious play within each cate gory are studied. These procedures are "conditionally consistent:" they yie ld almost as high a time-average payoff as if the player knew the condition al distributions of actions given categories. Moreover, given any alternati ve procedure, there is a conditionally consistent procedure whose performan ce is no more than epsilon worse regardless of the discount factor. We also discuss cycles, and argue that the time-average of play should resemble a correlated equilibrium. Journal of Economic Literature Classification Numbe rs: C72, C73, C63, D83. (C) 1999 Academic Press.