Solving simple stochastic games with few coin toss positions

Details Solving simple stochastic games with few coin toss positions Solving simple stochastic games with few coin toss positions

2011-12-22

arxiv.org/abs/1112.5255v3

Computer Science

Computer Science and Game Theory

Scientific paper

Gimbert and Horn gave an algorithm for solving simple stochastic games with running time O(r! n) where n is the number of positions of the simple stochastic game and r is the number of its coin toss positions. Chatterjee et al. pointed out that a variant of strategy iteration can be implemented to solve this problem in time 4^r r^{O(1)} n^{O(1)}. In this paper, we show that an algorithm combining value iteration with retrograde analysis achieves a time bound of O(r 2^r (r log r + n)), thus improving both time bounds. While the algorithm is simple, the analysis leading to this time bound is involved, using techniques of extremal combinatorics to identify worst case instances for the algorithm.

Affiliated with

Also associated with

No associations

Rating

Solving simple stochastic games with few coin toss positions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Solving simple stochastic games with few coin toss positions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Solving simple stochastic games with few coin toss positions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-306034