Improved subexponential analysis of the Random-Action-Removal algorithm for 2-player turn-based games and non-binary AUSOs

Jul 16, 2026

Concise description and improved analysis of the Random-Action-Removal algorithm for solving 2-player, 0-sum, turn-based stochastic and non-stochastic games on graphs or finite state sets. The method also finds the sink of an Acyclic Unique Sink Orientation (AUSO) of a non-binary hypercube. It yields the fastest known randomized performance for discounted/non-discounted stochastic games and mean payoff games, slightly improving prior work while keeping the algorithm unchanged.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages32

Reading Time1 h 21 min

Abstract

Introduction

arXiv :2607 .06334v 1 [ cs .DS] 7 Jul 2026 Improved subexponential analysis of the Random-Action-Removal algorithm for 2-player turn-based games and non-binary AUSOs Uri Zwick∗ Abstract We give a concise description and an improved analysis of the Random-Action-Removal algorithm for solving 2-player, 0-sum, turn-based, possibly infinite duration, stochastic or non-stochastic games played on graphs, or on finite sets of states. More generally, the algorithm can be used to find the sink of an Acyclic Unique Sink Orientation (AUSO) of a non-binary hypercube. The families of games that can be solved by the algorithm include discounted and non-discounted stochastic games (SGs) and Mean Payoff Games (MPGs) . The obtained algorithm is the fastest known randomized algorithm for solving such games, slightly improving on a much more complicated algorithm of Hansen and Zwick (STOC 2015) . The Random-Action-Removal algorithm is an adaptation of the Random-Facet algorithm used to solve linear programming (LP) problems, or, more generally, LP-type problems. Two dual variants of the Random-Facet algorithm were developed independently by Kalai (STOC 1992) and by Matoušek, Sharir and Welzl (SoCG 1992) . For LP problems, the algorithm of Kalai is a primal simplex algorithm, while the algorithm of Matoušek, Sharir and Welzl is a dual simplex algorithm. The Random-Action-Removal algorithm for games or AUSOs is an adaptation of the dual algorithm of Matoušek, Sharir and Welzl, and is a randomized strategy iteration algorithm. We present an improved analysis of the Random-Action-Removal algorithm that shows that it solves games with n states and m ≥ 2n actions, belonging to one of the players, in eO ( √n ln(m/n)) time. This improves on a previous eO ( √n ln(m/ √ n)) bound that follows from the analysis of Matoušek, Sharir and Welzl (SoCG 1992) . Our improved analysis relies of the hypercube structure of games and AUSOs. It does not improve on the bound of Matoušek, Sharir and Welzl for general LP-type problems that may lack such structure. The improved bound is obtained by deriving a tighter recurrence relation implied by the hypercube structure, and by using interesting mathematical techniques, such as the discrete WKB method, for solving the resulting non-standard recurrence relation. An eO ( √n ln(m/n)) bound for games and AUSOs also follows from an improved algorithm for solving LP and LP-type problems of Hansen and Zwick (STOC 2015) . However, this bound is obtained using a much more complicated algorithm, and has worst constant factors in the exponent. The main point of this paper is that the eO ( √n ln(m/n)) bound holds for the simple and natural Random-Action-Removal algorithm without any modification. The improvement from eO ( √n ln(m/ √n) ) to eO ( √n ln(m/n) ) is especially significant when m = O (n), which is a very natural setting, as then the bound on the running time of the algorithm drops from eO ( √nlnn) to eO ( √n) . 1 Introduction The simplex algorithm is one of the most important algorithms used to solve linear programming (LP) problems, both in theory and in practice. However, no variant of the simplex algorithm is known to run in polynomial time in the worst case. Furthermore, most natural variants of the simplex algorithm are known to require exponential time on some carefully designed instances. ∗ Blavatnik School of Computer Science, Tel Aviv University, Israel. E-mail: [zwick@tau.ac.il](zwick@tau.ac.il. Work)[. Work](zwick@tau.ac.il. Work) supported by ISF grant no. 2854/20 . Kalai [Kal92a; Kal92b] and Matoušek, Sharir and Welzl [MSW96], in breakthrough results, obtained randomized variants of the simplex algorithm with subexponential running times. Their algorithms are actually duals of each other. The algorithm of Kalai [Kal92a; Kal92b], usually called the RandomFacet algorithm, is a primal simplex algorithm, while the algorithm of Matoušek, Sharir and Welzl [MSW96] is a dual simplex algorithm.

FAQs

What problem does the Random-Action-Removal algorithm solve in this paper?

It solves 2-player, 0-sum, turn-based stochastic or non-stochastic games, potentially with infinite duration, modeled on graphs or finite state sets. It also computes the sink of a non-binary AUSO of a hypercube.

What improved running-time bound is proved for the algorithm?

For games with n states and m ≥ 2n actions (belonging to one player), the paper shows an eO(√n ln(m/n)) time bound. This improves a previous eO(√n ln(m/√n)) bound obtained from earlier analysis.

Why does the paper obtain a tighter bound than earlier work?

The improvement relies on exploiting the hypercube structure specific to games and AUSOs to derive a tighter recurrence relation. It also uses specialized techniques, including the discrete WKB method, to handle the resulting non-standard recurrence.

Jul 16, 2026

Upload by River Wang