Approximating the Termination Value of One-Counter MDPs and Stochastic Games

Computer Science – Computer Science and Game Theory

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

35 pages, 1 figure, full version of a paper presented at ICALP 2011, invited for submission to Information and Computation

Scientific paper

One-counter MDPs (OC-MDPs) and one-counter simple stochastic games (OC-SSGs) are 1-player, and 2-player turn-based zero-sum, stochastic games played on the transition graph of classic one-counter automata (equivalently, pushdown automata with a 1-letter stack alphabet). A key objective for the analysis and verification of these games is the termination objective, where the players aim to maximize (minimize, respectively) the probability of hitting counter value 0, starting at a given control state and given counter value. Recently, we studied qualitative decision problems ("is the optimal termination value = 1?") for OC-MDPs (and OC-SSGs) and showed them to be decidable in P-time (in NP and coNP, respectively). However, quantitative decision and approximation problems ("is the optimal termination value ? p", or "approximate the termination value within epsilon") are far more challenging. This is so in part because optimal strategies may not exist, and because even when they do exist they can have a highly non-trivial structure. It thus remained open even whether any of these quantitative termination problems are computable. In this paper we show that all quantitative approximation problems for the termination value for OC-MDPs and OC-SSGs are computable. Specifically, given a OC-SSG, and given epsilon > 0, we can compute a value v that approximates the value of the OC-SSG termination game within additive error epsilon, and furthermore we can compute epsilon-optimal strategies for both players in the game. A key ingredient in our proofs is a subtle martingale, derived from solving certain LPs that we can associate with a maximizing OC-MDP. An application of Azuma's inequality on these martingales yields a computable bound for the "wealth" at which a "rich person's strategy" becomes epsilon-optimal for OC-MDPs.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Approximating the Termination Value of One-Counter MDPs and Stochastic Games 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 Approximating the Termination Value of One-Counter MDPs and Stochastic Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximating the Termination Value of One-Counter MDPs and Stochastic Games will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-296924

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.