Markov Decision Processes with Multiple Long-Run Average Objectives
From MaRDI portal
Abstract: 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 limit-average functions, in the expectation objective the goal is to maximize the expected limit-average 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 case of one limit-average function, both randomization and memory are necessary for strategies even for epsilon-approximation, and that finite-memory randomized strategies are sufficient for achieving Pareto optimal values. Under the satisfaction objective, in contrast to the case of one limit-average function, infinite memory is necessary for strategies achieving a specific value (i.e. randomized finite-memory strategies are not sufficient), whereas memoryless randomized strategies are sufficient for epsilon-approximation, for all epsilon>0. We further prove 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 limit-average functions, for all epsilon>0. Our analysis also reveals flaws in previous work for MDPs with multiple mean-payoff functions under the expectation objective, corrects the flaws, and allows us to obtain improved results.
Recommendations
Cites work
- Game theory
- scientific article; zbMATH DE number 4112173 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 700091 (Why is no real title available?)
- scientific article; zbMATH DE number 1134975 (Why is no real title available?)
- Markov Decision Processes with Multiple Long-Run Average Objectives
- Markov Decision Processes with Multiple Objectives
- Multi-objective infinite-horizon discounted Markov decision processes
- Multi-objective Model Checking of Markov Decision Processes
Cited in
(22)- Multi-objective optimization of long-run average and total rewards
- Redundant data transmission in control/estimation over lossy networks
- What is decidable about partially observable Markov decision processes with \(\omega\)-regular objectives
- Quantitative multi-objective verification for probabilistic systems
- scientific article; zbMATH DE number 987932 (Why is no real title available?)
- Multi-weighted Markov decision processes with reachability objectives
- Multi-Objective Model Checking of Markov Decision Processes
- Hypervolume indicator and dominance reward based multi-objective Monte-Carlo tree search
- Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes
- Simple strategies in multi-objective MDPs
- Unifying two views on multiple mean-payoff objectives in Markov decision processes
- Hedging bets in Markov decision processes
- Markov decision processes with multiple long-run average objectives
- Markov Decision Processes with Multiple Objectives
- Markov Decision Processes with Multiple Long-Run Average Objectives
- Multi-objective Model Checking of Markov Decision Processes
- Model-Free Reinforcement Learning for Lexicographic Omega-Regular Objectives
- Stochastic games with lexicographic objectives
- Discounted-sum automata with multiple discount factors
- Discounted-sum automata with multiple discount factors
- Multi-objective -regular reinforcement learning
- Average reward reinforcement learning for omega-regular and mean-payoff objectives
This page was built for publication: Markov Decision Processes with Multiple Long-Run Average Objectives
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5458858)
