{"ID":6023606,"CreatedAt":"2026-07-08T01:00:23.257252134Z","UpdatedAt":"2026-07-10T14:27:52.484755835Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.06334","arxiv_id":"2607.06334","title":"Improved subexponential analysis of the Random-Action-Removal algorithm for 2-player turn-based games and non-binary AUSOs","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 \\emph{simplex} algorithm, while the algorithm of Matou{š}ek, Sharir and Welzl is a dual \\emph{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 \\emph{strategy iteration} algorithm. Our improved analysis shows that the Random-Action-Removal algorithm solves games with~$n$ states and $m\\ge 2n$ actions in $e^{O(\\sqrt{n\\ln(m/n)})}$ time. This improves on a previous $e^{O(\\sqrt{n\\ln(m/\\sqrt n)})}$ bound for the algorithm that follows from the analysis of Matou{š}ek, Sharir and Welzl (SoCG 1992). An $e^{O(\\sqrt{n\\ln(m/n)})}$ bound, with worse constant factors, was previously obtained using a much more complicated algorithm for solving LP and LP-type problems of Hansen and Zwick (STOC 2015).","short_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 Un...","url_abs":"https://arxiv.org/abs/2607.06334","url_pdf":"https://arxiv.org/pdf/2607.06334v1","authors":"[\"Uri Zwick\"]","published":"2026-07-07T14:29:47Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}