Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes

Details Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes

2011-04-18

arxiv.org/abs/1104.3489v1

Computer Science

Computer Science and Game Theory

15 pages, 3 figures, a full version of a paper accepted to LICS 2011

Scientific paper

We study Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) functions. We consider two different objectives, namely, expectation and satisfaction objectives. Given an MDP with k reward functions, in the expectation objective the goal is to maximize the expected value, and in the satisfaction objective the goal is to maximize the probability of runs such that the limit-average value stays above a given vector. We show that under the expectation objective, in contrast to the single-objective case, both randomization and memory are necessary for strategies, and we show that finite-memory randomized strategies are sufficient. We show that under the satisfaction objective, in contrast to the single-objective case, randomization is necessary for strategies, and we show that randomized memoryless strategies are sufficient for epsilon-approximation, for all epsilon>0. We show that the decision problems for both expectation and satisfaction objectives can be solved in polynomial time and the trade-off curve (Pareto curve) can be epsilon-approximated in time polynomial in the size of the MDP and 1/epsilon, and exponential in the number of reward functions, for all epsilon>0. Our results also reveal flaws in an earlier paper ("Markov Decision Processes with multiple Long-Run Average Objectives", FSTTCS 2007) for MDPs with multiple mean-payoff functions under the expectation objective, correct the flaws and obtain improved results.

Affiliated with

Also associated with

No associations

Rating

Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes 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 Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-72206