Turn-Based Stochastic Mean-Payoff Games in Deterministic Quasipolynomial Time

Introduction

Mean-payoff games ask how two players can control the long-run average reward of an infinite play. In the stochastic version, some transitions are chosen by chance. This combines strategic choice with the possibility of moving between regions having different long-run rewards. The input may describe very small transition probabilities and very large rewards with only a few binary digits, so an algorithm whose cost depends on their magnitudes need not be efficient in the input length.

The problem and the result

An instance consists of a finite directed multigraph $G = (V, E)$ with $V = \{1, \ldots, n\}$, $n \ge1$, and at least one outgoing edge at every vertex. The vertex set is partitioned as

Each edge $e$ has an integer reward $w(e)$. At a vertex of $V_{\max}$, Max chooses the next edge; at a vertex of $V_{\min}$, Min chooses it; at a vertex $i \in V_{\mathrm{ch}}$, the next edge is drawn from a prescribed rational probability distribution $p_i$ on the outgoing edges. Rewards and the numerators and positive denominators of the probabilities are encoded in binary. The graph and all edge data are listed explicitly. Loops, parallel edges, zero probabilities, and unreduced fractions are permitted.

Both players observe the complete finite history, including traversed edges, and may use arbitrary behavioral strategies with private randomness. Chance draws have the prescribed conditional law at the current vertex. A pure positional strategy chooses one outgoing edge at each vertex of its player, independently of the preceding history. For a play $\pi= (X_0, e_0, X_1, e_1, \ldots)$ define

Here $\sigma$ and $\tau$ range over Max’s and Min’s behavioral strategies, respectively. The expectation is taken after the pathwise lower limit. If $L$ is the complete binary input length, the decision problem is to output the set

Theorem 1.1. There are a uniform deterministic Turing machine and an absolute constant $C$ such that, on every valid input described above, the machine outputs exactly $U$ in at most

bit operations. The bound includes input reading, exact rational arithmetic, and output. Vertices of value zero are included.

Historical context

Shapley introduced stochastic games with positive stopping probabilities and characterized their values by a contraction operator [14]. Gillette considered the undiscounted, long-run average objective [8]; Liggett and Lippman supplied the classical stationary-strategy theorem for perfect-information time-average games [11]. The relation between discounting and long-run optimization is also classical. Blackwell showed in finite dynamic programming that one stationary policy is optimal for every discount factor sufficiently close to one [3]. Rational discounted values provide the corresponding stabilization mechanism for perfect-information stochastic games; see, for example, Gimbert and Zielonka [9], Theorem 3.

The computational problem connects several familiar classes of games. A simple stochastic game is a finite turn-based reachability game in which chance chooses fairly between two successors. Condon placed its threshold problem in NP $\cap$ coNP [6], and Ludwig gave a randomized subexponential algorithm [12]. Zwick and Paterson developed pseudopolynomial algorithms for deterministic mean-payoff games and a reduction to simple stochastic games [16]. Andersson and Miltersen later proved polynomial-time Turing equivalences among computing values and optimal strategies in simple stochastic, stochastic mean-payoff, and stochastic discounted-payoff games, with numerical parameters—including the discount factor—given in binary [2], Theorem 1. Randomized strategy-improvement algorithms have subexponential expected bounds [15]. A different line obtains pseudopolynomial bounds when the number of random positions is fixed [1, 4]. Numerical reward and denominator parameters in such bounds distinguish them from a bound in the complete binary input length. Deterministic quasipolynomial algorithms have also been obtained for simple stochastic games of bounded treewidth [5].

Theorem 1.1 also gives a deterministic quasipolynomial algorithm for deciding whether the reachability value of a simple stochastic game is at least $1/2$. Make the target absorbing, with reward $+1$ on its self-loop, and give every other edge reward $-1$; any other terminal vertex receives a self-loop of reward $-1$. For every strategy pair the pathwise mean payoff is $2\mathbf{1}_{\{\text{target is reached}\}}-1$. Its expectation is twice the reachability probability minus one, so taking the strategy extrema proves the reduction. The transformation increases the input length by at most a constant factor.

An explicit small discount is only one part of the present algorithm. Andersson and Miltersen already bounded a sufficient discount using determinant coefficients and polynomial sign stabilization [2 Lemma 1], Lemma 1; Gaubert, Grand-Clément, and Katz give sharper bounds on Blackwell optimality thresholds [7]. Hansen, Miltersen, and Zwick proved that strategy iteration is strongly polynomial when the discount factor is fixed [10]. The dependence of their bound on the inverse distance of that factor from one does not yield a polynomial bound in its binary encoding. Here the discount has polynomial bit length, and a recursive comparison algorithm controls the cost of locating its fixed point.

For games without chance vertices, a deterministic quasipolynomial algorithm in the complete binary input length is given in OpenAI [13], Theorem 1.1. Its simultaneous labeling construction is the direct predecessor of the method used here. We extend that construction to discounted operators, so that chance transitions enter through the same order and translation properties as player choices.

The proof and its main ideas

The first part of the proof replaces the mean-payoff problem by one discounted fixed point. For $0 < u < 1$, the discounted map takes the maximum, minimum, or chance average of $uw(e) + (1-u)t_j$ over edges $e : i \to j$. It is a contraction and has a unique fixed point $v(u)$. An explicit integer $H$, of polynomial binary length, gives a nonzero-value gap of at least $1/H$ and a discount $\lambda$ for which $\lVert v(\lambda) - \operatorname{val} \rVert_\infty\le1/(16H)$. Section 2 proves these estimates by elementary bounds on the rational functions of a fixed positional pair. Its gain and bias then give pathwise guarantees against every behavioral opponent. This establishes the payoff convention used here directly.

Finding the discounted fixed point by ordinary contraction iteration would take a number of steps depending on $1/\lambda$, which can be exponential in the input length. The second part of the proof treats any monotone map $F : \mathbb{R}^n \to\mathbb{R}^n$ satisfying

In an integer box, a subsolution is an integer vector $y$ satisfying $F_i(y) \ge y_i$ at coordinates above the lower face; a supersolution satisfies the reverse inequality at coordinates below the upper face. A subsolution close to an upper face requires a plus label there, while a supersolution close to a lower face requires a minus label. The procedure assigns each coordinate a positive mass for each sign. Its guarantee holds simultaneously for all comparison vectors whose coordinates away from the opposite face have total mass at most one.

Section 3 adapts the two-pass pivot and mass-reweighting method of OpenAI [13] (Sections 4–5). The crucial translations have a fixed sign: subsolutions move downward and supersolutions upward. The discounted translation identity preserves their required inequalities, allowing comparison vectors in a large box to be used in smaller recursive boxes. Two pivot passes then arrange a redistribution of the masses that keeps the required comparisons valid. At each recursive call, at most one child leaves both mass vectors unchanged. Every other child increases each product of a coordinate’s two masses by a fixed factor. Starting from uniform masses, only $O(\log(n + 1))$ such choices are possible along a path, even when the coordinate range is exponentially large.

The final part explains why these boundary labels suffice to find the fixed point. After scaling, we place an integer subsolution $Y$ and an integer supersolution $Z$ on opposite sides of it, with $Z - Y$ uniformly small. Neither vector is computed. A label excluding one comparison vector from a boundary strip permits that boundary to move inward while retaining both. Section 4 shrinks the enclosing box in this way, and the value gap converts the final approximation into the exact nonnegative-value set.

The reusable part of the argument is the labeling procedure: its correctness uses monotonicity and the scalar translation identity, and does not inspect the graph or the transition probabilities. The two-sided integer comparison vectors provide the link from that procedure to a discounted game. Quantitative discounting supplies the required accuracy, while the recursion determines the deterministic quasipolynomial running time.

Throughout, vector inequalities, extrema, and integer rounding are coordinatewise, and $\mathbf{1}$ denotes the all-ones vector. The proof uses only exact arithmetic.

A quantitative discount reduction

We first reduce the sign of each mean-payoff value to an approximation of one discounted fixed point. The reduction needs two quantitative facts: nonzero values are separated from zero, and a discount of polynomial bit length approximates every value more accurately than this separation. We prove both facts directly, including the identification of the limiting discounted value with the expected pathwise lower average.

The discounted fixed-point method originates in Shapley’s work [14]. Our argument for a single positional pair at all small discounts is a quantitative version of the eventual-optimality principle introduced by Blackwell for finite Markov decision processes [3]; stationary optimality for perfect-information stochastic games with limiting-average payoffs was established by Liggett and Lippman [11]. Quantitative thresholds for small-discount optimality are studied further in [7]. The estimates and the payoff convention needed here are proved below.

Let $n = |V|$, and define

Here $W,Q,A_0,H$ are positive integers. The denominator in the product defining $Q$ is the positive denominator supplied in the input; the fractions need not be reduced. An empty product is one. The explicit input gives $n=O(L)$ and $\log Q,\log W=O(L)$, because the denominator and reward bits are included in $L$. Therefore

so $\lambda_0$ has polynomial bit length.

For $0<u<1$, define $f_u:\mathbb{R}^V\to\mathbb{R}^V$ by taking at vertex $i$ the maximum, minimum, or prescribed chance average of

according as $i$ belongs to Max, Min, or Chance. This map is monotone and is a contraction in the maximum norm, with constant $1-u$. Indeed, each expression in (2.2) changes by at most $(1-u)\lVert t-t'\rVert_\infty$, and taking an extremum or an average preserves that bound. Its iterates from zero converge, because the successive differences decrease geometrically. Their limit is the unique fixed point, denoted $v(u)$. Since $f_u$ preserves $[-W,W]^V$,

Theorem 2.1 (Quantitative discount reduction). For every game in the input class, there are vectors $G,\psi\in\mathbb{R}^V$ and a pure positional strategy pair $(\sigma^*,\tau^*)$ whose selected edges attain the extrema defining $f_u(v(u))$ for every $0<u\le1/(2H)$. Moreover,

For every start vertex $i$ and every behavioral opposing strategy,

Consequently $G_i = \operatorname{val}(i)$. Each $G_i$ is rational with a representation whose denominator has absolute value at most $A_0$, and

The proof has an algebraic part and a probabilistic part. Rational functions first give a pair that works for every sufficiently small discount, together with its limiting gain $G$ and first-order term $\psi$. We then use these two vectors to control individual plays against arbitrary behavioral opponents.

A positional pair valid for all small discounts

Temporarily fix a pure positional pair: one outgoing edge at each Max and Min vertex. Let $P$ be its row-stochastic transition matrix and let $r_i$ be its expected one-step reward at $i$. At a chance vertex the transition probabilities of parallel edges are added in $P$, whereas their possibly different rewards are averaged in $r$. The pair’s discounted equations are

The matrix $I-(1-u)P$ is invertible for $0<u<1$: a vector in its kernel would satisfy $\lVert x\rVert_\infty\le(1-u)\lVert x\rVert_\infty$. The corresponding affine contraction preserves $[-W,W]^V$, so its solution satisfies $\lVert x(u)\rVert_\infty\le W$.

The determinant argument follows the rational-function sign method of Andersson and Miltersen [2]; we derive all coefficient bounds in the input parameters above. For a polynomial $a$, write $\lVert a\rVert_{\operatorname{coef}}$ for the sum of the absolute values of its coefficients. This norm is subadditive and submultiplicative. Every entry of $QP$ and $Qr$ is an integer. Cramer’s rule therefore gives integer polynomials $N_i,D$ with

Each entry of the matrix defining $D$ has coefficient norm at most $3Q$. The replacing column defining $N_i$ is $Qur$, whose entries have coefficient norm at most $QW$. Expanding each determinant over its $n!$ permutations gives

Whether this pair’s chosen edge is optimal at a player vertex $i$ is determined by comparisons with every outgoing edge $e:i\to j$. Each comparison is the sign of

The numerator has coefficient norm at most $(3+W)A_0\le H$.

To control these signs, let $a$ be any nonzero integer polynomial with $\lVert a\rVert_{\operatorname{coef}}\le H$. Factoring its lowest power of $u$ gives $a(u)=u^k(c+uq(u))$, where $c$ is a nonzero integer. For $0<u\le1/(2H)$,

Thus the sign of $a(u)$ throughout this interval is the sign of its lowest nonzero coefficient. This observation applies to both the numerator and denominator in (2.10); the denominator is nonzero there by invertibility. Every edge comparison therefore has a constant sign or vanishes identically on the interval.

Now choose attaining edges in the maximum and minimum defining $f_{\lambda_0}(v(\lambda_0))$. They give a pure positional pair $(\sigma^*,\tau^*)$, and its linear solution at $\lambda_0$ equals $v(\lambda_0)$. Since $\lambda_0 \le1/(2H)$, all edge inequalities that hold at $\lambda_0$ continue to hold for every $0 < u \le1/(2H)$. For each such $u$, the pair’s linear solution is consequently a fixed point of $f_u$, hence equals $v(u)$. The pair is needed for the proof; the algorithm need not compute it.

The rational gain and its approximation error

Use the polynomials of the pair just selected. Let $\ell$ be the lowest nonzero degree of $D$. Boundedness of $N_i(u)/D(u)$ as $u \downarrow0$ implies that $u^\ell$ also divides each $N_i$. Define $\widehat{D}=D/u^\ell$ and $\widehat{N}_i=N_i/u^\ell$. Their coefficient norms satisfy (5), and $\widehat{D}(0)$ is a nonzero integer. The quotient is analytic at zero, so it has the expansion (2.4), with

The bound (2) gives $|G_i| \le W$. The displayed denominator has magnitude at most $A_0$, and its numerator is an integer. Thus $G_i \ne0$ implies $|G_i| \ge1/A_0 \ge1/H$.

The same coefficient bounds also control the approximation error. The polynomial $\widehat{N}_i-G_i\widehat{D}$ has constant coefficient zero and coefficient norm at most $(1+W)A_0$. For $0 < u \le1/(2H)$, the tail of $\widehat{D}$ has magnitude at most $A_0u \le1/2$, so $|\widehat{D}(u)| \ge1/2$. It follows that

At $u=\lambda_0$, this is the error claimed in (4).

It remains to identify $G_i$ with the mean-payoff value. The gain controls which transitions can persist, and the coefficient $\psi$ then controls the rewards on those transitions. For a selected player edge $e:i\to j$, substitution of (2.4) into the discounted equation gives

At a chance vertex, the corresponding identities are

At a Min vertex, the inequality $v_i(u)\le uw(e)+(1-u)v_j(u)$ for an arbitrary outgoing edge first gives $G_i\le G_j$. If $G_i=G_j$, subtracting this common constant, dividing by $u$, and letting $u\downarrow0$ gives

At a Max vertex, the gain inequality and, when the gains agree, the bias inequality both reverse.

From one-step inequalities to pathwise payoffs

We use two elementary facts about adapted processes. Fixing a selected strategy will give the gain along a play one-sided conditional drift. The first lemma shows that the gain then becomes constant, so only gain-preserving player moves can persist and the bias inequalities apply. The second lemma shows that the centered contributions at chance vertices have vanishing averages.

Lemma 2.2 (Finite-valued submartingales). Let $(Z_t)_{t\geq0}$ be adapted to a filtration $(\mathcal{F}_t)_{t\geq0}$ and take values in a fixed finite subset of $\mathbb{R}$. If $\mathbb{E}[Z_{t+1}\mid\mathcal{F}_t]\geq Z_t$ for every $t$, then $Z_t$ is eventually constant almost surely. Its eventual value $Z_\infty$ satisfies $\mathbb{E}Z_\infty\geq\mathbb{E}Z_0$.

Proof. Add a constant to make $Y_t=Z_t+c$ nonnegative. Conditional expectation and the assumed drift give

Summing and using boundedness shows that $\mathbb{E}\sum_{t\geq0}(Y_{t+1}-Y_t)^2<\infty$. The sum is therefore finite almost surely. If there is more than one possible value, let $\Delta>0$ be the minimum distance between distinct values. Every change contributes at least $\Delta^2$ to the sum, so only finitely many changes occur. The singleton case is immediate. Finally, $\mathbb{E}Z_t\geq\mathbb{E}Z_0$ for all $t$, and bounded convergence gives the claimed expectation inequality.

Lemma 2.3 (Averages of bounded martingale differences). Let $(\mathcal{F}_t)_{t\geq0}$ be a filtration. Suppose $D_t$ is $\mathcal{F}_{t+1}$-measurable, $\mathbb{E}[D_t\mid\mathcal{F}_t]=0$, and $\lvert D_t\rvert\leq c$ for a fixed finite constant $c$. Then $T^{-1}\sum_{t<T}D_t\to0$ almost surely.

Proof. For $s<t$, conditioning on $\mathcal{F}_t$ gives $\mathbb{E}[D_sD_t]=0$. Hence $\mathbb{E}[(\sum_{t<T}D_t)^2]\leq Tc^2$. Chebyshev’s inequality at $T=j^2$ gives, for every $\varepsilon>0$,

The sum over $j$ is finite. The probability that one of these events occurs after index $m$ is at most the tail of this sum, which tends to zero. Applying this argument to $\varepsilon=1,1/2,1/3,\ldots$ proves convergence along squares on a single event of probability one. For $j^2\leq T<(j+1)^2$, the additional partial sum has magnitude at most $c(2j+1)$. Dividing by $T\geq j^2$ extends convergence to every $T$.

Completion of the proof of Theorem 2.1. Fix a start vertex $i$, fix Max to $\sigma^*$, and let Min use an arbitrary behavioral strategy. Write $X_t$ for the vertex before the edge $e_t$ is traversed, and let $\mathcal{F}_t$ be the sigma-field generated by the complete observed history through $X_t$. At a chance vertex the conditional law of $e_t$ is the prescribed distribution. At a player vertex it is the distribution induced by that player’s strategy, including any private randomness.

The process $G_{X_t}$ has nonnegative conditional drift. A selected Max edge preserves $G$ by (2.13); every Min edge weakly increases $G$; and the first identity in (2.14) gives zero drift at a chance vertex. Lemma 2.2 gives an eventual value $G_\infty$ with

Define the one-step residual and its chance part by

These random variables are uniformly bounded because the arena is finite. At a chance vertex, the two identities in (2.14) imply

Outside chance vertices $D_t = 0$. Thus $\mathbb{E}[D_t \mid\mathcal{F}_t] = 0$, and Lemma 2.3 gives $T^{-1}\sum_{t<T} D_t \to0$ almost surely.

After $G_{X_t}$ has become constant, every traversed nonchance edge preserves $G$. Its residual is zero at Max vertices by (2.13), and nonnegative at Min vertices by (2.15). The nonchance residuals are therefore nonnegative except for a finite initial segment. Consequently

Telescoping the bias terms gives

The first average tends to $G_\infty$, and the last term tends to zero. Hence $\operatorname{MP}_w \ge G_\infty$ almost surely. Taking expectations and using (2.16) proves the first inequality in (2.5).

For the second inequality, fix Min to $\tau^*$ and let Max be arbitrary. Now $-G_{X_t}$ has nonnegative conditional drift. The same finite-valued lemma yields an eventual gain $G_\infty$ with $\mathbb{E}G_\infty\le G_i$. The chance residuals still have average zero. At Min vertices the selected edges have residual zero; at Max vertices an edge preserving $G$ has nonpositive residual by the reversed version of (2.15). Thus the nonchance residuals are eventually nonpositive, and (2.17) gives

This also bounds the pathwise lower average. Taking expectations proves the second inequality in (2.5).

Max can therefore guarantee $G_i$, and Min can guarantee that the payoff is at most $G_i$, so $\operatorname{val}(i) = G_i$. The payoffs and gain limits in these expectation comparisons are bounded. The argument permits each opposing history-dependent distribution and establishes the expected-liminf convention directly.

Simultaneous labeling for discounted monotone maps

We now construct the labels that will permit a box to shrink while retaining the integer comparison vectors around the discounted fixed point. The construction depends only on order and on the response to a common translation. We therefore work in the following abstract setting: $n \ge1$ and $F : \mathbb{R}^n \to\mathbb{R}^n$ satisfy

All vector inequalities, minima, maxima, and floors in this section are coordinatewise. The algorithm uses $F$ only by evaluating $\lfloor F(t)\rfloor$ at integer vectors $t$.

The two pivot passes and subsequent mass change adapt the simultaneous labeling construction of [13], Sections 4–5. Here the operator has the discounted translation rule in (9). The proof below establishes the required labeling theorem directly; the signs of the witness translations are what make that adaptation possible.

Witnesses and the labeling guarantee

An input consists of $A \in\mathbb{Z}^n$, a width

and positive rational mass vectors $a,b \in\mathbb{Q}_{>0}^n$. Write $u=A+D\mathbf{1}$, $P=D/32$, and $a(S)=\sum_{i\in S}a_i$, $b(S)=\sum_{i\in S}b_i$ for $S\subseteq\{1,\ldots,n\}$. The representation in Equation (10) is unique. Its short range of mantissas will later allow small relative decreases in the width.

Definition 3.1 (Witnesses and claims). An integer vector $y\in[A,u]$ is a subsolution in the box if

It is a plus witness if also $a(S_y)\le1$; its claims are the indices $i$ for which $y_i\ge u_i-P$.

An integer vector $z\in[A,u]$ is a supersolution in the box if

It is a minus witness if also $b(S_z)\le1$; its claims are the indices $i$ for which $z_i\le A_i+P$. The sets $S_y,S_z$ are the respective supports. A witness is relevant if it has at least one claim.

Every claim belongs to its witness’s support, since $0<P<D$. The output must respect all these claims simultaneously, although the algorithm is not given any witness and does not search for one.

Theorem 3.2 (Recursive simultaneous labeling). Let $F:\mathbb{R}^n\to\mathbb{R}^n$ satisfy Equation (9). There is a terminating deterministic procedure $\mathcal{L}(A,D,a,b)$, using exact evaluations of $\lfloor F(t)\rfloor$ for $t\in\mathbb{Z}^n$ and integer and rational arithmetic, with the following guarantee. For every input as in Equation (10) and Definition 3.1, its output $\ell\in\{+,-\}^n$ satisfies

The existence of a labeling will already follow from the finite box iteration below. The purpose of the recursive construction is to obtain such labels with the controlled branching and decreasing rank of Lemma 3.5, replacing dependence on the numerical width by dependence on its exponent.

Lemma 3.3 (Comparison and a finite box iteration). Every subsolution $y$ and supersolution $z$ in the same box satisfy $y\le z$. Starting at $t^0=u$, the iteration

stops at a vector $t^*$ after at most $nD+1$ evaluations of $T$. For every such pair $y,z$ one has $y\le t^*\le z$.

Proof. If $m=\max_j(y_j-z_j)>0$, choose $i$ with $y_i-z_i=m$. Since $y_i>z_i\ge A_i$ and $z_i<y_i\le u_i$, both defining inequalities apply at $i$. Monotonicity and the common translation rule give

a contradiction.

The map $T$ preserves the finite integer box and is monotone. Moreover $T(u) \le u$, so induction gives $t^{m+1} \le t^m$. Each changing step decreases the nonnegative integer $\sum_i(t_i^m-A_i)$ by at least one. Its initial value is $nD$, which proves the termination bound, including the final unchanged step.

For an integer $y \in[A,u]$, the subsolution condition is equivalent to $y \le T(y)$. Indeed, when $y_i > A_i$, the latter inequality is equivalent to $y_i \le\lfloor F_i(y)\rfloor$, and at the other coordinates it is automatic. If $y$ is a subsolution, induction gives $y \le t^m$: from $y \le t^m$ one obtains $y \le T(y) \le T(t^m) = t^{m+1}$. Thus $y \le t^*$. The fixed point $t^* = T(t^*)$ is itself a subsolution, and the comparison principle gives $t^* \le z$ for every supersolution $z$.

The recursive procedure

A centered call of even width $r$ at an integer pivot $k$ means the call $\mathcal{L}(k-(r/2)\mathbf{1},r,a',b')$ with the indicated masses. All calls use the same map $F$. In a nonbase call set

The pivot will stay between $c-M\mathbf{1}$ and $c+M\mathbf{1}$. The two passes use narrow centered boxes to identify some labels directly and arrange the remaining witnesses so that the later mass change preserves their admissibility. The downward pass preserves the plus masses, and the upward pass preserves the minus masses. A final wider centered call supplies the signs used to change both mass vectors.

Procedure $\mathcal{L}(A,D,a,b)$. Execute the first applicable base case. If neither applies, execute Steps 3–6 in order.

1. Mass base case. If $a_i b_i>1$ for every $i$, return $+$ at $i$ when $b_i>1$, and return $-$ otherwise.

2. Width base case. If $d<12$, compute $t^*$ by (3.3). Return $+$ at $i$ when $t_i^*>A_i+D/2$, and return $-$ otherwise.

3. Downward pass. Initialize $k=c$. Make a centered width-$q$ call at $k$ with masses $(a,\frac{4}{3}b)$, and use its labels to update all coordinates simultaneously by

Replace $k$ by $k^{\mathrm{new}}$ and repeat until an update leaves the pivot unchanged. Denote this last pivot by $k^\downarrow$ and set

4. Upward pass. Start at $k=k^\downarrow$. Make a centered width-$q$ call at $k$ with masses $(\frac{4}{3}a,b)$, and update simultaneously by

Replace $k$ by $k^{\mathrm{new}}$ and repeat until an unchanged update. Denote the last pivot by $k^f$ and set

5. Provisional labels and new masses. Make a centered width-$D/2$ call at $k^f$ with masses $(a,b)$. For its output $\ell^0$, define

6. Continuation and overrides. Call $\mathcal{L}(A,D,\bar{a},\bar{b})$. In its output replace the signs on $I_-$ by $-$ and those on $I_+\setminus I_-$ by $+$. Return this label vector.

Each pass includes the final child call whose update changes nothing. That call will certify a mass inequality at the stopped pivot. All coordinates in one update use the same old pivot and the same child output; there is no order-dependent coordinate update.

The purpose of the passes is the following mass property. For every witness with a claim outside its own override set—$I_+$ for a plus witness and $I_-$ for a minus witness—the coordinates in its support whose provisional labels match its sign will have total mass greater than $3/4$. Here mass means $a$-mass for a plus witness and $b$-mass for a minus witness. Its original total mass is at most one, so Step 5 will leave its new total mass below

It will therefore remain a witness for the continuation in the unchanged box. At the same time, every product $a_i b_i$ is multiplied by $32/25$. We first use this product growth to prove termination; the subsequent witness analysis proves the stated mass property and hence correctness.

Lemma 3.4 (Valid boxes and bounded passes). Every child input is valid and its box lies inside its parent’s box. If the child calls terminate, each pivot pass makes at most $1024n+1$ calls. The width base case makes at most $522240n+1$ evaluations of $\lfloor F\rfloor$.

Proof. In a nonbase call $d\ge12$, so $c,M,q,p$ and the half-widths $q/2,D/4$ are integral. The centered widths have the allowed representations $q=h2^{d-7}$ and $D/2=h2^{d-1}$. The pivot caps keep $c-M\mathbf{1}\le k\le c+M\mathbf{1}$, and a centered box has width $r\le D/2$. Its boundaries satisfy

The continuation uses the same box. All masses remain positive rationals.

Every pivot coordinate lies on the grid of spacing $p$ through $c_i$, because $M/p=512$ is integral. In a changing update some coordinate moves by $p$; each coordinate is monotone during a pass and travels at most $2M$, hence moves at most $1024$ times. There are at most $1024n$ changing updates, followed by one unchanged update. Finally, $d<12$ implies $D\le255\cdot2^{11}=522240$, so the width bound follows from Lemma 3.3. □

The continuation preserves the width, so width reduction alone does not prove termination. The mass products provide the missing measure. Define

This integer is used only in the proof, not computed by the procedure.

Lemma 3.5 (Rank and branching). The procedure terminates. At a nonbase call every child has smaller rank $d+B(\mu(a,b))$. There is exactly one child preserving $B$, the provisional call, and it decreases $d$ by one. There are at most $2048n+3$ other children; each decreases $B$ by at least one and does not increase $d$. Proof. At a nonbase call $B(\mu)>0$, since otherwise the mass base case would apply. Whenever $\mu' \ge\rho\mu$, the definition gives $B(\mu') \le B(\mu)-1$. Both pivot passes multiply every mass product by $4/3 \ge\rho$. The continuation multiplies every mass product by $(4/5)(8/5)=\rho$, independently of the provisional label. These children reduce $B$ and preserve or reduce $d$. Only the provisional call keeps the masses; it halves the width and reduces $d$ by one. This proves the rank assertion.

Induction on the nonnegative rank proves termination. The base cases are finite by their definitions and Lemma 3.4. At a nonbase call every child terminates by induction, and the bound on each pivot pass then applies. The number of children decreasing $B$ is at most $2(1024n+1)+1=2048n+3$.

Translating a witness into a centered box

To analyze the labels, we follow an arbitrary parent witness through the centered calls. Translation places its largest deviation from the pivot at one boundary of the child box; clipping removes coordinates far below that largest deviation. The surviving support will identify the mass forced near the largest deviation when a pivot pass stops.

Fix a nonbase input and a pivot $k \in[c-M\mathbf{1},c+M\mathbf{1}]$. For a relevant plus witness $y$, define its peak and gaps by

For a relevant minus witness $z$, put

The gaps are nonnegative integers and at least one gap is zero. The following lemma handles both signs, including the inequalities introduced by the discount factor.

Lemma 3.6 (Translation and clipping). Let $r \in\{q,D/2\}$ and let $y$ or $z$ be a relevant witness of the parent box. Define, according to its sign,

The resulting vector is an integer subsolution or supersolution, respectively, in the centered width-$r$ box. Its support is exactly $\{i:g_i(k)<r\}$, which is contained in the parent’s support. It claims every index with $g_i(k)\le r/32$. It is a witness for that child whenever its support has mass at most one for the child’s mass vector of the corresponding sign.

Proof. A parent claim gives, in either case,

Outside the parent support one has $y_i=A_i$ or $z_i=u_i$. The corresponding deviation is at most $-D/2+M=-3D/8$, so its gap is at least $23D/32>D/2$. Such an index cannot belong to $\{i:g_i(k)<r\}$.

Before clipping, the two expressions on the right of (15) are

respectively. They lie on the correct side of the far boundary; clipping at the other boundary puts the vector in the child box. These expressions also show directly that the support is exactly the set of gaps strictly below $r$, and that every gap at most $r/32$ gives a claim. For the plus case let $t=-s_y(k)+r/2<0$, where the strict sign follows from (3.14) and $r/2\le D/4$. One has $y'\ge y+t\mathbf{1}$. At an index in the child support, equality holds in that coordinate, and the parent subsolution inequality applies. Therefore

using $\gamma t\ge t$. For the minus case let $t=s_z(k)-r/2>0$. Now $z'\le z+t\mathbf{1}$, with coordinatewise equality on the child support, and

using $\gamma t\le t$. Thus the required inequalities survive both translation and clipping. The stated mass condition is exactly the remaining condition for being a child witness.

What the two pivot passes enforce

We prove correctness by induction on the rank from Lemma 3.5. For the remainder of this subsection, fix a nonbase call and assume that all its children satisfy Theorem 3.2. Witnesses, supports, and claims refer to the parent input unless stated otherwise.

In each pass, the sign whose masses are unchanged protects its own peak: coordinates close enough to that peak must receive its sign and remain stationary. The opposite sign has its masses multiplied by $4/3$. At the final unchanged update, any witness of that sign with a claim outside its override set must consequently have mass greater than $3/4$ near its peak. The next two lemmas make these statements precise.

Lemma 3.7 (The downward pass). For every relevant plus witness $y$, the peak $s_y(k)$ is constant throughout the downward pass and at most $D/2$. No plus witness claims an index in $I_-$. Every minus witness $z$ with a claim outside $I_-$ satisfies

Proof. Fix a relevant plus witness $y$ and consider an update from $k$. The width-$q$ translation in Lemma 3.6 is a plus witness for the child, since the plus masses are unchanged and its support is contained in $S_y$. Its claims include all indices with $g_i^y(k)\le q/32=p$. The child labels all of them by $+$, so they do not move. In particular, every peak achiever continues to attain the old peak.

At any other coordinate let $\delta_i=k_i-k_i^{\mathrm{new}}$. Then $0\le\delta_i\le p$ and

Thus no moving coordinate reaches the old peak, even when several coordinates move simultaneously. The peak is unchanged. At the initial pivot $c$, $y\le u$ gives $s_y(c)\le D/2$. If $y$ claims $i$, it follows that

so $i\notin I_-$.

For the mass assertion, let $z$ claim $j\notin I_-$. Then $k_j^\downarrow\ge c_j-P$ and $z_j\le A_j+P$, whence

At a lower-capped coordinate $k_i^\downarrow=c_i-M$ one instead has $k_i^\downarrow-z_i\le D/2-M$, since $z_i\ge A_i$. Every peak achiever is therefore strictly above the lower cap. If the mass in Equation (16) were at most $3/4$, the width-$q$ translation of $z$ would have support mass at most one under the final child’s minus masses $\frac{4}{3}b$. It would be a minus witness and would claim every peak achiever. The child would label such a coordinate by $-$, forcing it to move down because it is above the lower cap. This contradicts the unchanged update. The mass is therefore strictly greater than $3/4$.

Lemma 3.8 (The upward pass). For every relevant minus witness $z$, the peak $s_z(k)$ is constant throughout the upward pass and at most $D/2$. No minus witness claims an index in $I_+$. At the final pivot the following mass inequalities hold:

if $z$ has a claim outside $I_-$,

if $y$ has a claim outside $I_+$.

Proof. Fix a relevant minus witness $z$. The width-$q$ translation is a minus witness for every child in this pass because the minus masses are unchanged. All coordinates with $g_i^z(k)\le p$ must receive $-$ and stay fixed. In particular a peak achiever stays fixed. At a coordinate with $g_i^z(k)>p$, write $\delta_i=k_i^{\mathrm{new}}-k_i\in[0,p]$. Then

No coordinate overtakes the peak, so the peak is constant. At the starting pivot $k^\downarrow\le c$ and $z\ge A$, it is at most $D/2$. A minus claim at $i$ consequently implies

excluding $i$ from $I_+$. Because the peak is constant and $k$ only increases during this pass, every gap $g_i^z(k)$ is nonincreasing. Thus the set of gaps below $q$ can only grow, and Equation (16) implies Equation (3.17).

Now let a plus witness $y$ claim $j\notin I_+$. At the final pivot $k_j^f\le c_j+P$ and $y_j\ge A_j+D-P$, so

An upper-capped coordinate $k_i^f=c_i+M$ has $y_i-k_i^f\le D/2-M$, since $y_i\le u_i$. Every peak achiever is strictly below the upper cap. If the mass in Equation (3.18) were at most $3/4$, its width-$q$ translation would be a plus witness for the last child, whose plus masses are $\frac{4}{3}a$. Every peak achiever would have label $+$ and would move up, contradicting the final unchanged update. This proves the remaining inequality.

The two passes have now separated the claims into those that can safely receive an override and those whose witnesses have substantial mass near a peak at $k^f$. The wider provisional call labels all that mass with the witness’s sign. Reducing the masses of that sign then keeps each remaining witness admissible for the continuation. Figure 1 summarizes how the two passes supply the information used in this final step.

Mass reweighting and completion of the proof

Proof of Theorem 3.2. Termination follows from Lemma 3.5; we prove the labeling guarantee by induction on the same rank. In the mass base case, an index labeled $+$ has $b_i>1$, so no minus witness can contain that index in its support or claim it. At an index labeled $-$ one has $b_i\le1$ and $a_i b_i>1$, hence $a_i>1$; no plus witness can claim that index. This proves both guarantees.

In the width base case, Lemma 3.3 gives $y \le t^* \le z$ for all witnesses. A plus claim forces $t_i^* \ge u_i - P > A_i + D/2$; a minus claim forces $t_i^* \le A_i + P < A_i + D/2$. Thus the returned signs are correct.

For a nonbase call, assume correctness of all its children. Let $Q_+ = \{i : \ell_i^0 = +\}$ and $Q_- = \{i : \ell_i^0 = -\}$ be the provisional sign sets. Consider a plus witness $y$ that has a claim outside $I_+$. By (3.18), the set $G_y = \{i : g_i^y(k^f) < q\}$ has $a$-mass greater than $3/4$. It lies in $S_y$ by Lemma 3.6. Apply that lemma with width $r = D/2$ to the provisional call. Its plus masses are unchanged, so the translated vector is a plus witness. Since

every index in $G_y$ is a claim of this translated witness. All these indices belong to $Q_+$ by the child’s guarantee. Consequently

The parent vector $y$ is still a subsolution in the unchanged box, so it is a plus witness for the continuation.

For a minus witness $z$ having a claim outside $I_-$, the set $G_z = \{i : g_i^z(k^f) < q\}$ has $b$-mass greater than $3/4$ by (3.17). It lies in $S_z$. The width-$D/2$ minus translation is a witness for the provisional call because the minus masses are unchanged; every index in $G_z$ is one of its claims, and hence belongs to $Q_-$. Therefore

The same vector $z$ is a minus witness for the continuation.

It remains to check every claim after the overrides. Let $y$ claim $i$. Lemma 3.7 gives $i \notin I_{-}$. If $i \in I_{+}$, it receives the plus override. If $i \notin I_{+}$, Equation (18) applies to $y$, the continuation labels $i$ by $+$, and no override changes it. Now let $z$ claim $i$. Lemma 3.8 gives $i \notin I_{+}$. If $i \in I_{-}$, it receives the minus override. Otherwise Equation (19) applies to $z$, and the continuation’s minus label is unchanged. In particular $I_{-} \cap I_{+}$ contains no claim of either sign, so the stated priority between overrides causes no conflict. This completes the induction.

From labels to an exact decision

We now apply Theorem 3.2 to a scaled discounted map. The labels need not locate its fixed point directly. Instead, we construct two integer comparison vectors on opposite sides of that point. Their coordinatewise distance is small, so a label excluding one vector from a boundary strip also allows that boundary to move past a smaller strip without excluding either vector. Repeating this operation gives the accuracy required by Theorem 2.1.

Two nearby integer comparison vectors

Use the integers $W$, $Q$, $A_{0}$, $H$ of Section 2, and set

Let

Then $F(x) = x$, the map $F$ is monotone, and

Thus $F$ has the properties used in Section 3. Define the integer vectors

Floors and ceilings are coordinatewise; in particular, a floor of a negative number is taken toward minus infinity. These vectors are used only in the proof. The algorithm will not compute them.

Lemma 4.1. The vectors in (22) satisfy

For every coordinate $i$,

Proof. The inequalities $x - (N + 1)\mathbf{1} \le Y \le x - N\mathbf{1}$ and $x + N\mathbf{1} \le Z \le x + (N + 1)\mathbf{1}$, together with $\gamma(N + 1) = N - 1/N \le N$, give

and

Here we used monotonicity and (21). The remaining conclusions follow from these defining bounds and $\lVert x \rVert_{\infty} \le SW$.

Shrinking the box

Recall that the permitted widths are $D=h2^d$ with $128\le h\le255$ and integers $d\ge0$. Start with

where $d_0$ is the least nonnegative integer for which $D_0\ge2J$. The box $[A,A+D\mathbf{1}]$ contains $Y$ and $Z$.

While $D>K$, call $\mathcal{L}(A,D,a,b)$ with $a_i=b_i=1/n$ for all $i$. Put $u=A+D\mathbf{1}$ and $P=D/32$. Within the current box, $Y$ is a subsolution and $Z$ is a supersolution, and their support masses are at most one. Consequently, the labeling guarantee has the following contrapositive form:

For example, $Z_i\le A_i+P$ would be a minus claim and would require a minus label.

Let $D'$ be the next smaller permitted width. More explicitly,

The second case has $d\ge1$, because the loop condition implies $D>K>255$. Set $\delta=D-D'$. In the first case $\delta/D=1/h\le1/128$; in the second case this ratio is $1/256$. Thus

Define

Replace $(A,D)$ by $(A',D')$.

Lemma 4.2. Every box in this iteration contains $Y$ and $Z$. The iteration makes at most $128(d_0+1)$ calls to $\mathcal{L}$ and ends with $D\le K$.

Proof. The initial containment was established above. At a plus coordinate, (4.6) and (4.8) give

The lower endpoint can therefore increase by $\delta$; the upper endpoint remains unchanged. At a minus coordinate the same inequalities give

The upper endpoint can decrease by $\delta$; the lower endpoint remains unchanged. This proves the induction step for both comparison vectors.

There are only 128 permitted mantissas at any exponent, and the exponent never increases. The strictly decreasing sequence of widths therefore has at most $128(d_0+1)$ terms before reaching the stopping range, which contains all permitted widths at exponent zero.

At termination, $Y \le x \le Z$ and the invariant imply $A_i \le x_i \le A_i + D$. Hence

Theorem 2.1 now gives

Output exactly the indices satisfying

If $\operatorname{val}(i) = 0$, (25) puts $A_i/S$ at least $-1/(8H)$, so the index is included. If $\operatorname{val}(i) > 0$, the same conclusion holds. If $\operatorname{val}(i) < 0$, the value gap in Theorem 2.1 gives $A_i/S \le-1/H + 1/(8H) = -7/(8H)$, so the index is excluded. This proves exact correctness, including equality at zero.

Bit complexity and uniformity

It remains to show that the potentially large integer widths do not produce a large recursion tree, and that every local computation has polynomial bit cost. The first point uses the mass-product rank of Section 3; the second uses the explicit binary encoding.

Since every vertex has an outgoing edge and the input is explicit, $n$, $|E| = O(L + 1)$. The binary lengths of the probabilities and rewards give

In particular, all integers in (20) and (23) have $O((L + 2)^2)$ bits, and $d_0 = O((L + 2)^2)$. Reading the input and forming these integers by ordinary exact arithmetic take polynomial time. Every recursive box lies in its parent, and every outer box lies in the initial box. Thus all box endpoints, pivot coordinates, and integer arguments to $F$ have polynomial binary length.

For an integer vector $t$, the quantities used to evaluate $F_i(t)$ are

Max and Min take exact extrema. At a chance vertex write the encoded probability as $p(e) = c_e/d_e$ with $d_e > 0$. Its weighted sum can be formed with the common denominator $QN$ and integer numerator

Every $d_e$ divides $Q$, even when input fractions are not reduced. This formula gives polynomial bit lengths and polynomial bit cost for an evaluation and its coordinatewise floors. Zero probabilities and parallel edges require no special handling.

Consider one outer call, whose initial masses are $a_i = b_i = 1/n$. For a recursive call put

The initial value $B_0 = B(1/n^2)$ is $O(\log(n + 1))$; this includes $n = 1$, for which $B_0 = 1$. Every recursive edge decreases $d + B$. Only the provisional-label child can preserve $B$, and it decreases $d$ by one. Each other child decreases $B$ by at least one and does not increase $d$. Thus the depth is at most

and any root-to-node path contains at most $B_0$ edges decreasing $B$. At each node there is at most one $B$-preserving child and at most

other children: the two pivot passes account for the first term and the reweighted call for the final one.

A path of length $\ell$ with $j$ edges decreasing $B$ is specified by their $j$ positions and at most $s_*$ choices at each such position; the other child, if present, is unique. The total number of nodes is therefore at most

The distinction between these two kinds of children is essential: the depth may be polynomial in $L$, but branching choices occur only $O(\log(n+1))$ times on any path.

All masses can be stored as unreduced positive fractions. An edge that changes masses multiplies each by one of a fixed set of rational constants, and so increases its numerator and denominator lengths by at most a constant. The other edge leaves masses unchanged. Thus the mass lengths are polynomial (indeed $O(\log(n+1))$), and every comparison, update, and support-independent base test has polynomial bit cost. The algorithm does not compute $B$; it is used only for this analysis.

Outside its children, a nonbase call performs $O(n+1)$ pivot updates and associated vector operations, all of polynomial bit cost. In a width base case, $d<12$ gives $D \leq255 \cdot2^{11}$, an absolute constant, so the clipped-floor iteration uses at most $1+nD$ polynomial-cost evaluations. The mass base case is also polynomial. Consequently (29) bounds the bit cost of one outer call up to a polynomial factor. Lemma 4.2 bounds the number of outer calls by a polynomial as well.

Finally, all loops, tie rules, integer operations, and recursive calls are specified by finite algorithms independent of the input. A depth-first implementation stores a stack of polynomial depth whose individual records have polynomial length. Scanning such a stack or copying a record on a deterministic Turing machine costs at most a polynomial factor per local operation. The final integer tests (26) and the output take polynomial time. Absorbing these factors into (29) proves the bound $2^{C(\log_2(L+2))^2}$ for one absolute constant $C$. This completes the proof of Theorem 1.1.