Magnifying Lens Abstraction for Stochastic Games with Discounted and Long-run Average Objectives

Details Magnifying Lens Abstraction for Stochastic Games with Discounted and Long-run Average Objectives Magnifying Lens Abstraction for Stochastic Games with Discounted and Long-run Average Objectives

2011-07-11

arxiv.org/abs/1107.2132v1

Computer Science

Computer Science and Game Theory

Scientific paper

Turn-based stochastic games and its important subclass Markov decision processes (MDPs) provide models for systems with both probabilistic and nondeterministic behaviors. We consider turn-based stochastic games with two classical quantitative objectives: discounted-sum and long-run average objectives. The game models and the quantitative objectives are widely used in probabilistic verification, planning, optimal inventory control, network protocol and performance analysis. Games and MDPs that model realistic systems often have very large state spaces, and probabilistic abstraction techniques are necessary to handle the state-space explosion. The commonly used full-abstraction techniques do not yield space-savings for systems that have many states with similar value, but does not necessarily have similar transition structure. A semi-abstraction technique, namely Magnifying-lens abstractions (MLA), that clusters states based on value only, disregarding differences in their transition relation was proposed for qualitative objectives (reachability and safety objectives). In this paper we extend the MLA technique to solve stochastic games with discounted-sum and long-run average objectives. We present the MLA technique based abstraction-refinement algorithm for stochastic games and MDPs with discounted-sum objectives. For long-run average objectives, our solution works for all MDPs and a sub-class of stochastic games where every state has the same value.

Affiliated with

Also associated with

No associations

Rating

Magnifying Lens Abstraction for Stochastic Games with Discounted and Long-run Average Objectives 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 Magnifying Lens Abstraction for Stochastic Games with Discounted and Long-run Average Objectives, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Magnifying Lens Abstraction for Stochastic Games with Discounted and Long-run Average Objectives will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-564323