Discounting and averaging in games across time scales (Q2909220)

Two-level discounted and mean-payoff games played by two players on a perfect-information stochastic game graph are studied. The upper level game is a discounted or mean-payoff game and the lower level game is a (undiscounted) reachability game. Two-level games model hierarchical and sequential decision making under uncertainty across different time scales. For both discounted and mean-payoff two-level games, it is shown that there exist pure memoryless optimal strategies for both players and an ordered field property. It is shown that if there is only one player (Markov decision processes), then the values can be computed in polynomial time. It follows that whether the value of a player is equal to a given rational constant in two-level discounted or mean-payoff games can be decided in NP \(\cap \) coNP.