Smoothed analysis of policy iteration and value iteration for deterministic discounted and mean-payoff games played on any graph

1.1. Discounted and mean-payoff games.

• A deterministic turn-based game has two players choosing successive edges in a weighted directed graph, with one maximizing and the other minimizing the limiting payoff.Discounted and mean-payoff variants define that limit differently.Source: §1.1 · p. 3

1.2. Two algorithmic paradigms: value and policy iteration.

• Solving turn-based stochastic games remains open in the sense that no polynomial-time algorithm is known, despite practical performance and exponential-time hard instances for known algorithms.The problem is in NP ∩ coNP.Source: §1.2 · p. 3
• Value iteration repeatedly applies an operator to value estimates; the discounted Shapley operator is a contraction, while Zwick–Paterson uses iterates of the mean-payoff operator to recover exact values.For integer weights, sufficiently many iterates yield an approximation from which the exact game value can be deduced.Source: §1.2 · p. 4
• Krasnoselskii–Mann and Halpern iteration have been used for related mean-payoff settings, and this paper applies them to deterministic mean-payoff games with smoothed-polynomial-time guarantees.The authors describe this application to deterministic games as previously unobserved.Source: §1.2 · p. 4
• Policy iteration repeatedly updates both players’ policies until its improving measure certifies optimal strategies.For mean-payoff games and discount factors exponentially close to 1, known iteration bounds can remain exponential in the number of states.Source: §1.2 · pp. 4–5

1.3. Smoothed analysis and the previous result for ergodic graphs.

• Perturbing linear-program inputs with Gaussian noise yields a polynomial-time smoothed bound for the simplex method, motivating smoothed analysis as an account of practical efficiency.The result bounds time by a polynomial in the dimensions and inverse noise scale.Source: §1.3 · p. 5
• Loff and Skomra proved that a policy-iteration algorithm solves deterministic discounted or mean-payoff games on ergodic graphs in smoothed polynomial time.The guarantee holds with high probability after independently Gaussian-perturbing normalized payoffs in [−1, 1].Source: §1.3 · p. 5
• An ergodic graph has no pair of disjoint traps, one for each player.A trap is a strict subset of vertices in which one player can keep the other confined, regardless of the other player’s choices.Source: §1.3 · p. 5

1.4. Our main two results.

• The Loff–Skomra policy-iteration algorithm runs in smoothed polynomial time with high probability on any graph for deterministic discounted or mean-payoff games.The guarantee is for normalized payoffs in [−1, 1] independently perturbed by Gaussian noise with standard deviation ρ.Source: §1.4 · p. 5
• A value-iteration algorithm also runs in smoothed polynomial time with high probability for deterministic discounted or mean-payoff games on any graph.The stated perturbation is independent Gaussian noise of standard deviation ρ applied to normalized payoffs in [−1, 1].Source: §1.4 · pp. 5–6
• The paper’s value-iteration analysis uses Krasnoselskii–Mann and Halpern iterations rather than the Zwick–Paterson aggregation approach, whose probabilistic applicability was unclear to the authors.The paper also describes a condition number usable for both ergodic and non-ergodic deterministic games.Source: §1.4 · p. 6

Contribution 1

• The paper generalizes Loff and Skomra’s condition number from ergodic games to general graphs, basing it on the GKK equations.The new measure is intended for games that need not be ergodic.Source: §1.5 · p. 6

Contribution 2

• Perturbed inputs are well-conditioned with high probability; the non-ergodic analysis uses log-Lipschitz distributions because the previous analysis fails at a crucial juncture.The proof draws inspiration from recent smoothed analysis of the simplex method.Source: §1.5 · p. 6

Contribution 3

• Policy iteration is efficient on well-conditioned games under the new condition number, using a discounted-to-mean-payoff transfer that requires γ exponentially close to 1 for general games.Known discounted-game policy iteration algorithms run in time polynomial in n and 1/(1−γ).Source: §1.5 · pp. 6–7

Contribution 4

• The paper introduces three mean-payoff value-iteration algorithms: Krasnoselskii–Mann and Halpern iterations partition the graph into constant-value subgames, while a combined method uses Zwick–Paterson and Halpern iterations.The combined method uses Zwick–Paterson iteration to partition the graph while Halpern iteration solves each subgame.Source: §1.5 · p. 7

Contribution 5

• All three value-iteration algorithms run in smoothed polynomial time, with bounds obtained by first analyzing well-conditioned constant-value games and then reducing general games to such subgames.The combined Zwick–Paterson/Halpern method receives a better bound than plain Krasnoselskii–Mann and Halpern iteration.Source: §1.5 · p. 7

1.7. Contribution 1. A condition number for non-ergodic graphs.

• The GKK equations group vertices into clusters with equal value, while allowing different clusters to have different values.The remaining equations select the best bias-adjusted payoff within each cluster and constrain edges between different-value clusters.Source: §1.7 · p. 8
• Choosing the argmax or argmin edge at each vertex from a solution yields optimal, bias-induced policies.Source: §1.7 · p. 8
• Expressing bias-induced policies through linear constraints partitions edge-weight space into polyhedral cones, whose boundaries define the condition number.The condition number measures inverse distance to the boundary, adapting the Loff–Skomra approach to the GKK equations.Source: §1.7 · p. 8

1.8. Contribution 2. Showing that perturbed inputs are well-conditioned.

• The earlier Loff–Skomra argument fixes other edge weights and bounds one edge away from a single cutoff, but the coupled inequalities obstruct that approach here.It uses a union bound over edges after establishing that each edge is unlikely to lie near its cutoff.Source: §1.8 · p. 9
• In non-ergodic games, cluster-value inequalities can place the same edge weight between multiple cutoffs, whose dependencies are difficult to untangle.The bounds themselves may depend on payoffs that occur in other such inequalities.Source: §1.8 · p. 9
• Log-Lipschitz distributions relate the probability of an event to that of its translation, enabling a new approach to the conditioning analysis.The paper takes inspiration from simplex-method analyses that first establish results for log-Lipschitz noise and then relate Gaussian noise to it.Source: §1.8 · pp. 9–10
• A small shift into each policy-pair cone leaves most of its probability mass in a region deep within that cone.The condition number is inverse distance to the boundary; the argument applies across the cones in the partition.Source: §1.8 · p. 10

1.9. Contribution 3.

• When γ > 1 − 1/poly(n,∆), the mean-payoff optimal strategies are also optimal for the discounted game, allowing known discounted-game policy iteration to run in poly(n, ∆) time.The paper reproves Loff and Skomra’s Theorem 6.1 for its new condition number.Source: §1.9 · p. 10
• Against either fixed mean-payoff optimal policy, the opponent’s unique discounted best response remains its mean-payoff optimal policy.The argument for the opposing player is symmetric.Source: §1.9 · p. 10
• A deviation that leaves the current component is excluded because its mean-payoff separation exceeds the possible discount-to-mean value difference.The separation is at least ∥r∥/∆(r), while the difference is at most O(n(1 − γ)∥r∥).Source: §1.9 · p. 10
• Within a component, a deviation that creates a new cycle or changes a path leading to it is likewise ruled out by the bias inequalities and the discount-to-mean estimate.The new cycle’s mean weight is separated from the original mean-payoff value.Source: §1.9 · p. 10

1.10. Contribution 4. Three value-iteration algorithms.

• The first two algorithms apply Halpern and Krasnoselskii–Mann iteration to the Shapley operator, using its non-expansiveness and additive homogeneity.For constant-value games, the ergodic equation becomes a fixed-point equation in the quotient space R^n/R^1.Source: §1.10 · p. 11
• An approximate bias need only approximately satisfy the ergodic equation; it need not be close to an actual bias vector.Once sufficiently accurate, this approximate solution is sufficient for recovering optimal policies.Source: §1.10 · p. 11
• Plain Krasnoselskii–Mann and Halpern iterations extend to arbitrary games by approximating values, ignoring cross-value edges, and applying the approximate-bias method within constant-value components.After cross-value edges are ignored, the game decomposes into constant-value subgames.Source: §1.10 · p. 11
• The third algorithm combines Zwick–Paterson edge detection with restarted Halpern iteration on detected clusters, improving dependence on the condition number.After all cross-value edges are found, Halpern iteration runs directly on constant-value components.Source: §1.10 · p. 11

1.11. Contribution 5. Value iteration in smoothed polynomial time.

• All three value-iteration algorithms run in polynomial time on well-conditioned inputs, using a proof distinct from the discounted-game argument for policy iteration.Approximate solutions of the ergodic equation are interpreted as exact solutions for nearby games.Source: §1.11 · p. 11
• In constant-value games, an approximate bias is an exact bias for a nearby game whose weights differ by at most ε, while preserving the induced policies.The perturbation shifts all outgoing edges of each vertex by the same amount.Source: §1.11 · p. 12
• Well-conditioning keeps the weight vector away from the boundary of its bias-induced policy region, so a sufficiently accurate approximate bias reveals the original game’s optimal policies.Convergence estimates then give polynomial iteration bounds in the condition number.Source: §1.11 · p. 12
• For general games, value iteration separates cross-value edges before applying the constant-value approximate-bias analysis independently within each component.Any of the three studied procedures can perform the value-separation phase.Source: §1.11 · p. 12
• Plain Krasnoselskii–Mann and Halpern iterations have quadratic dependence on ∆(r), while the combined Zwick–Paterson/Halpern algorithm avoids that loss and achieves a better condition-number dependence.The combined method restarts Halpern iteration when it detects a new cross-value edge.Source: §1.11 · p. 12

• Section 2 collects background on mean-payoff games, the Shapley operator, the Hilbert seminorm, optimality equations, bias-induced policies, and constant-value components.Source: §1.12 · pp. 12–13
• Sections 3–4 analyze constant-value games and single-optimal-cycle cone decompositions, linking condition numbers to the steps needed for value iteration to recover optimal policies.Section 3 introduces approximate biases and studies Krasnoselskii–Mann and Halpern iteration.Source: §1.12 · p. 13
• Section 5 extends the cone decomposition and Loff–Skomra condition-number framework to arbitrary, not necessarily ergodic, game graphs.Source: §1.12 · p. 13
• Section 6 defines a value condition number for gaps between distinct state values and shows three value-iteration methods detect or ignore cross-value edges in time polynomial in the inverse smallest gap.This reduces general games to the constant-value analysis.Source: §1.12 · p. 13
• Section 7 bounds value- and policy-iteration complexity by the new condition number, while Section 8 proves sufficiently perturbed inputs are well-conditioned with high probability, yielding smoothed polynomial-time guarantees.The Section 8 proof treats log-Lipschitz perturbations and transfers the estimate to Gaussian perturbations.Source: §1.12 · p. 13

2.1. Definition of mean-payoff games.

• In a mean-payoff game, players choose moves on a weighted graph to maximize or minimize the long-run average reward; optimal policies guarantee the state-value vector, and fixed policies lead to a cycle.A policy optimal for one player guarantees that player’s bound against any opponent strategy.Source: §2.1 · pp. 14–15
• The game’s value vector changes by at most ||r − r̃||∞ when edge weights change, and an optimal policy remains 2||r − r̃||∞-optimal under the new weights.These bounds apply to a fixed game graph.Source: §2.1 · p. 15

2.2. Preliminaries on Shapley operator and Hilbert seminorm.

• The Shapley operator is monotone and additively homogeneous, and is therefore non-expansive in the Hilbert seminorm.The Hilbert seminorm is zero exactly on constant vectors.Source: §2.2 · p. 16

2.3. Preliminaries on the GKK theorem and bias induced policies.

• The GKK optimality equations admit a bias whose induced policies are optimal; for any ε > 0, a bias exists with ||u*||∞ ≤ (1 + ε)n||r||H and ||u*||H ≤ (2 + ε)n||r||H.For constant-value games, these bounds hold with ε = 0.Source: §2.3 · pp. 17–18
• Removing edges between vertices with different values preserves the game’s value and yields connected components that each have constant value; policies optimal on every component are optimal in the original game.The reduced graph’s value vector is the original value vector.Source: §2.3 · p. 19
• A policy optimal on the reduced graph guarantees at least each starting vertex’s value in the full game, with analogous reasoning for Min.Under the paired policies, traversed edges preserve or increase value, and cycles remain within a component.Source: §2.3 · p. 19
• The proposed two-stage algorithm identifies edges joining vertices of different values, removes them, then solves constant-value games on reduced components.For randomly perturbed games, value iteration algorithms are intended to solve both stages efficiently.Source: §2.3 · pp. 19–20

• An ε-approximate bias has Shapley residual at most ε in the Hilbert seminorm, a weaker requirement than being close to an actual bias.The paper notes that efficient algorithms do not find approximations in the stronger closeness sense.Source: §3 · p. 20
• An ε-approximate bias is a bias for a nearby constant-value game with weights within ε, and it induces the same policies in both games.The original game’s value vector has Hilbert seminorm at most 2ε, and those policies are (2ε)-optimal there.Source: §3 · p. 20
• Krasnoselskii–Mann and Halpern iteration are applied to the Shapley operator to find approximate biases in constant-value games.Source: §3 · pp. 20–21
• Additive homogeneity lets the ergodic equation be viewed as a fixed-point equation in an additively projective space, so the iterations need not know the game value.The related interpretation appears in.Source: §3 · p. 21
• For sufficiently large k, every policy induced by either iteration is optimal.Source: §3 · p. 22
• In the example, Zwick–Paterson iterates converge to the value vector but fail to induce the optimal policy at even k, while Krasnoselskii–Mann iteration induces it for every k ≥ 1.The Zwick–Paterson residual does not converge.Source: §3 · p. 23
• In the W-parameter example, the Krasnoselskii–Mann residual stays at 1 for 2W iterations and the Halpern residual for 3W iterations before decreasing.These delays are consistent with the respective bounds in Theorem 3.4.Source: §3 · p. 24

4. Condition number for games with a single equilibrium cycle

• The condition number ∆(r) governs the convergence of both iterations to optimal policies on well-conditioned constant-value games.This is the same condition number that governs the algorithm from [LS24].Source: §4 · pp. 24, 26
• For r in Pσ,τ, the game has constant value λσ,τ(r), a unique bias up to an additive constant, and only the policy pair (σ, τ) is bias-induced.The bias is uσ,τ(r).Source: §4 · p. 25
• The condition number used by and this section’s definition differ by at most a factor of 2, so either can study conditioning of randomized games.The section notes that studied its condition number for ergodic graphs, while the cited analysis applies to any mean-payoff game with one equilibrium cycle.Source: §4 · pp. 24, 26
• A weight vector in Pσ,τ remains in that cone after perturbations of size at most sl(r)/(4n + 3) in the infinity norm.The section also states that an ε-approximate bias, for ε = sl(r)/(4n + 3), induces the same policy pair (σ, τ).Source: §4 · p. 26
• Krasnoselskii–Mann yields an optimal induced policy for k ≥ 36n^2(4n + 3)^2∆(r)^2, while Halpern does so for k ≥ 16n(4n + 3)∆(r)^−1.Both bounds apply when r belongs to Pσ,τ for a pair in Ξ.Source: §4 · p. 26

5. Condition number for general games

• For r in Pσ,τ, the policies (σ, τ) are optimal and bias-induced, and λσ,τ(r) gives the game’s value vector.The cones Pσ,τ are defined by strict inequalities for edges within equal-value components.Source: §5 · pp. 27–28
• Removing edges between vertices with different values decomposes the game into p connected components, each with a unique bias up to an additive constant and a single equilibrium cycle.The restricted policies are the corresponding restrictions of (σ, τ).Source: §5 · pp. 28–29
• The cones Pσ,τ are disjoint, and their union covers all but a measure-zero set of weights; each weight in a cone has only that pair of bias-induced policies.Some cones may be empty, and for arbitrary graphs the section does not characterize which ones are nonempty.Source: §5 · pp. 29–30
• For every r in the union of policy cones, each component’s condition number ∆ℓ(r) is at most the general game’s condition number ∆(r).This supports extending the single-cycle conditioning framework to games with multiple equilibrium cycles.Source: §5 · p. 31
• A nonempty cone Pσ,τ contains a normalized weight vector with slack at least 1, showing that these cones are wide.The section motivates this property as useful for showing that condition numbers are small under Gaussian perturbations.Source: §5 · pp. 31–32
• Even when ∆(r) is small, efficient componentwise iterations require first finding the game’s decomposition, which the next section addresses.The stated componentwise methods are Krasnoselskii–Mann and Halpern iteration.Source: §5 · p. 32

Value condition number

• The value condition number ∆val(r) is zero when no edge joins vertices of different values; otherwise it is ∥r∥H divided by the smallest value gap across such an edge.Source: §6 · p. 32

Zwick–Paterson iteration

• For Zwick–Paterson iteration, any different-value edge has endpoint iterate values separated by more than 2n∥r∥H once k ≥ 1 + 4n∆val(r).Same-value edges remain within 2n∥r∥H, but without an estimate of ∆val(r), this test does not indicate when all such edges have been found.Source: §6 · p. 33

Krasnoselskii–Mann iteration

• The normalized Krasnoselskii–Mann sequence 2u_k/k converges to the value vector λ, with a stronger convergence estimate proved for deterministic games.General results give limit existence for this iteration in stochastic mean-payoff games, while Kohlberg’s theorem identifies the limit as λ/2 for the underlying iteration operator.Source: §6 · p. 34
• After O(n∆val(r)) iterations, Krasnoselskii–Mann detects all different-value edges, ignores them, and induces the same policies as the reduced game.For k* ≥ ⌊1 + (4n + 2)∆val(r)⌋, its subsequent iterates match those on the reduced game, started from u_k*.Source: §6 · p. 35

Halpern iteration

• The normalized Halpern sequence 3u_k/k converges to the value vector λ, and its edge-detection result follows after O(n∆val(r)) iterations.The convergence-rate proof adapts reasoning for stochastic Markov Decision Processes [LR25, Theorem 9].Source: §6 · pp. 36–37
• After O(n∆val(r)) iterations, Halpern detects all different-value edges, ignores them, and induces the same policies as the reduced game.For k* ≥ ⌊1 + (12n + 3)∆val(r)⌋, subsequent iterates match those on the reduced game with shifted weights.Source: §6 · p. 37

• The displayed identity relates u_k to F and F′ and ends with a decomposition into k−k* and k*.Source: §6 · p. 38

7.1. Krasnoselskii–Mann iteration.

• Krasnoselskii–Mann iteration from zero eventually induces only optimal policies, and for r ∈ U its total complexity is O(mn + mn^2∆(r) + mn^4∆(r)^2).The analysis first removes edges between vertices of different values, then establishes optimality on each resulting constant-value component.Source: §7.1 · pp. 38–39

7.2. Halpern iteration.

• For r ∈ U, Halpern iteration finds optimal policies for all k ≥ 4 + (192n^2 + 156n + 3)∆(r) + 36n(3 + 16n + 16n^2)∆(r)^2.The proof reduces the game to connected components whose vertices have equal values, then applies shifted-weight Halpern iteration on each component.Source: §7.2 · p. 40

7.3. Combining the Zwick–Paterson iteration with the Halpern iteration.

• The Zwick–Paterson/Halpern algorithm halts and is correct on every input, and for r ∈ U runs in O(mn + mn^2∆(r)) time.It runs Zwick–Paterson to identify the reduced game while running Halpern iteration in parallel, resetting Halpern when an edge between different-value vertices is detected.Source: §7.3 · pp. 41–42

7.4. Policy iteration methods based on increasing discount factor.

• On arbitrary graphs, the policy-iteration method from is governed by the condition number: for r ∈ Pσ,τ, (σ, τ) is uniquely optimal when 1 > γ > 1 − 1/(4n^2∆(r)).The result generalizes [LS24, Theorem 9] beyond ergodic graphs.Source: §7.3 · p. 42, §7.4 · p. 42
• The algorithms solve mean-payoff and discounted games by increasing the discount factor, and their complexity is bounded by ∆(r).DiscountedPI can use Howard’s rule or Dantzig’s rule; Dantzig’s one-player performance is polynomial independently of the discount factor, making overall complexity linear in 1/(1 − γ) rather than quadratic.Source: §7.4 · p. 44
• For r ∈ U, Theorem 7.14 proves IncreasingDiscountPI halts correctly and gives ∆+(r)-based switch bounds for Howard and Dantzig implementations, with the same estimates for IncreasingDiscountPI2.Here ∆+(r) = max{2, ∆(r)}; the supplied passages do not show the explicit switch-bound formulas.Source: §7.4 · p. 45
• IncreasingDiscountPI halts with optimal mean-payoff policies because policies optimal in discounted games become optimal in the mean-payoff game for discount factors sufficiently close to 1.The proof uses convergence of discounted values and the finiteness of the policy set, which ensures some ε-optimal policies are optimal.Source: §7.4 · p. 46
• Halving 1 − γ reaches the region 1 − γ < 1/(4n^2∆(r)), where DiscountedPI returns the optimal policies; its calls use 1 − γ ≥ 1/(8n^2∆(r)), except possibly the first.These thresholds underpin the switch-count estimates for IncreasingDiscountPI.Source: §7.4 · p. 46

Log-Lipschitz analysis

• Log-Lipschitz densities support the analysis by bounding how probabilities change under shifts; the proof partitions weights into disjoint cones and shifts within them.Each nonempty cone contains a point with slack at least 1/n, which supports the condition-number estimate.Source: §8 · p. 47

Laplace perturbations

• Independent Laplace perturbations of the game weights admit a high-probability bound on the condition number.The analysis assumes fixed weights in [-1, 1]^m and independent Laplace noise on each weight.Source: §8 · pp. 48, 52

Gaussian perturbations

• The Gaussian extension treats Gaussian density as approximately log-Lipschitz and establishes a corresponding shifted-set probability bound.That bound underlies the Gaussian analogue of the cone-partition argument.Source: §8 · pp. 48, 50
• Independent Gaussian perturbations likewise yield a high-probability condition-number bound for mean-payoff games.The Gaussian analysis adapts the Laplace argument using an estimate for shifted-set probabilities under Gaussian measure.Source: §8 · pp. 50–51

Gaussian perturbations and algorithmic complexity

• Gaussian perturbations yield smoothed-polynomial complexity guarantees for the listed policy-iteration and value-iteration algorithms on mean-payoff games.Theorem 8.13 combines the condition-number estimate with the algorithms’ complexity bounds; its policy-iteration claims also extend to discounted games.Source: §8 · p. 52

Future work

• The policy-iteration rule is nonstandard, leaving smoothed complexity of standard rules such as Howard, lexicographic, and RandomFacet open.The authors also ask whether other combinatorial algorithms have polynomial smoothed complexity.Source: §9 · p. 52
• Extending the results to stochastic games remains open; correctness of the iterative methods for arbitrary stochastic games is not established.The stated correctness analysis for Krasnoselskii–Mann and Halpern iteration uses determinism.Source: §9 · p. 52
• Whether the value-iteration rate O(1/k) is optimal for deterministic games remains unknown.The paper notes an Ω(1/k) lower bound for more general iterative methods in MDPs.Source: §9 · p. 53
• The combined Zwick–Paterson/Halpern iteration has linear dependence on 1/ρ, and achieving sublinear dependence remains an open question.The comparison in the paper is with simplex-method smoothed analysis.Source: §9 · p. 53
• The authors leave open whether other UEOPL problems, including P-Matrix Linear Complementarity, admit smoothed analysis.Source: §9 · p. 53