Can I read Polyhedral Value Iteration for Discounted Games and Energy Games on EtoBox?

Polyhedral Value Iteration for Discounted Games and Energy Games by Alexander Kozachinskiy is a book available to read on EtoBox.

What is Polyhedral Value Iteration for Discounted Games and Energy Games about?

We present a deterministic algorithm, solving discounted games with n nodes in n O(1) • (2 + √ 2) n -time. For bipartite discounted games our algorithm runs in n O(1) •2 n -time. Prior to our work no deterministic algorithm running in time 2 o(n log n) regardless of the discount factor was known. We call our approach polyhedral value iteration. We rely on a well-known fact that the values of a discounted game can be found from the so-called optimality equations. In the algorithm we consider a polyhedron obtained by relaxing optimality equations. We iterate points on the border of this polyhedron by moving each time along a carefully chosen shift as far as possible. This continues until the current point satisfies optimality equations. Our approach is heavily inspired by a recent algorithm of Dorfman et al. (ICALP 2019) for energy games. For completeness, we present their algorithm in terms of polyhedral value iteration. Our exposition, unlike the original algorithm, does not require edge weights to be integers and works for arbitrary real weights..

Author

Alexander Kozachinskiy

Publisher

Society for Industrial and Applied Mathematics

Published

2021

Language

EN