Algorithms for Linear Equations with Min and Max Operators Under (Absolutely) Halting Condition

We consider linear equations with min and max operators (LEMMs) that contain many subproblems ranging from optimization, learning, to games. Recently, Chatterjee et al. [2025] gave a systematic study of the complexity of different subclasses. Three key subclasses–(I) halting branching process, (II) absolutely halting LEMMs, and (III) halting LEMMs–are proved to be in UP $\cap$ coUP while generalizing stochastic games (SSGs). In this work, we study the classic algorithms of Policy Iteration (PI) and Value Iteration (VI) for these general subclasses. First, we simplify the problem hierarchy by showing the equivalence between halting branching process and SSGs. Then, we show that while PI diverges for absolutely halting LEMMs due to the loss of monotonicity, VI remains convergent, a result we establish via diagonal rescaling. Finally, we show that neither PI nor VI converges for general halting LEMMs and, to this end, propose variants of simple policy iteration that ensure convergence across all subclasses.