Accession Number:

ADA458138

Title:

Trading Memory for Randomness

Descriptive Note:

Corporate Author:

CALIFORNIA UNIV BERKELEY DEPT OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCE

Report Date:

2004-01-01

Pagination or Media Count:

13.0

Abstract:

Strategies in repeated games can be classified as to whether or not they use memory andor randomization. We consider Markov decision processes and 2-player graph games, both of the deterministic and probabilistic varieties. We characterize when memory andor randomization are required for winning with respect to various classes of - regular objectives, noting particularly when the use of memory can be traded for the use of randomization. In particular, we show that Markov decision processes allow randomized memoryless optimal strategies for all Mueller objectives. Furthermore, we show that 2-player probabilistic graph games allow randomized memoryless strategies for winning with probability 1 those Mueller objectives which are upward-closed. Upward-closure means that if a set of infinitely repeating vertices is winning, then all supersets of alpha are also winning.

Subject Categories:

  • Statistics and Probability
  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE