Computer Science – Computer Science and Game Theory
Scientific paper
2011-08-18
Computer Science
Computer Science and Game Theory
Submitted to SODA 2012 (Symposium On Discrete Algorithms, Kyoto)
Scientific paper
The question of knowing whether the policy Iteration algorithm (PI) for solving Markov Decision Processes (MDPs) has exponential or (strongly) polynomial complexity has attracted much attention in the last 50 years. Recently, Fearnley proposed an example on which PI needs an exponential number of iterations to converge. Though, it has been observed that Fearnley's example leaves open the possibility that PI behaves well in many particular cases, such as in problems that involve a fixed discount factor, or that are restricted to deterministic actions. In this paper, we analyze a large class of MDPs and we argue that PI is efficient in that case. The problems in this class are obtained when optimizing the PageRank of a particular node in the Markov chain. They are motivated by several practical applications. We show that adding natural constraints to this PageRank Optimization problem (PRO) makes it equivalent to the problem of optimizing the length of a stochastic path, which is a widely studied family of MDPs. Finally, we conjecture that PI runs in a polynomial number of iterations when applied to PRO. We give numerical arguments as well as the proof of our conjecture in a number of particular cases of practical importance.
Delvenne Jean-Charles
Hollanders Romain
Jungers Raphaël
No associations
LandOfFree
Policy Iteration is well suited to optimize PageRank 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 Policy Iteration is well suited to optimize PageRank, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Policy Iteration is well suited to optimize PageRank will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-181476