Sammanfattning Två standardalgoritmer för att ungefär lösa två-spelare nollsummor samtidig räckvidd spel är värde iteration och strategi iteration. Vi bevisar övre och nedre gränserna på 2 m (N) på det värsta fall antalet iterationer som behövs av båda dessa algoritmer för att ge icke-triviala approximationer till värdet av ett spel med N icke-terminal positioner och m åtgärder för varje spelare i varje position. I synnerhet har båda algoritmerna dubbelexponentiell komplexitet. Även när spelet ges som ingång har bara en icke-terminal position, visar vi en exponentiell lägre gräns på det värsta fall antalet iterationer som behövs för att ge icke-triviala approximationer.
Det visades i REF att standardalgoritmer för (ungefär) lösa dessa spel, värde iteration och policy iteration, kan vara extremt långsam i värsta fall: de kan ta ett dubbelt exponentiellt antal iterationer för att få någon icke-trivial approximation, även när värdet v * är 1.
The Complexity of Solving Reachability Games Using Value and Strategy Iteration
{'venue': 'Theory of Computing Systems', 'journal': 'Theory of Computing Systems', 'mag_field_of_study': ['Computer Science', 'Mathematics']}