Strongly Polynomial Time Complexity of Policy Iteration for $L_\infty$ Robust MDPs

Ali Asadi; Alipasha Montaseri; Carlo Pagano; Ehsan Goharshady; Krishnendu Chatterjee; Mehrdad Karrabi

REVIEW 2 major objections 4 minor 1 cited by

This paper proves that policy iteration for L∞ robust MDPs runs in strongly polynomial time when the discount factor is fixed, resolving a long-standing open algorithmic question.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-03 06:09 UTC pith:LCMZXK7I

load-bearing objection Resolves a real open problem with a plausible proof, but the written finiteness step has a genuine gap—repairable by invoking their own Theorem 21 where Lemma 8 is used. the 2 major comments →

arxiv 2601.23229 v2 pith:LCMZXK7I submitted 2026-01-30 cs.AI cs.CC

Strongly Polynomial Time Complexity of Policy Iteration for L_infty Robust MDPs

Ali Asadi , Krishnendu Chatterjee , Ehsan Goharshady , Mehrdad Karrabi , Alipasha Montaseri , Carlo Pagano This is my paper

classification cs.AI cs.CC MSC 90C4068Q25

keywords robust Markov decision processesL-infinity uncertainty setspolicy iterationstrongly polynomial algorithmdiscounted-sum payoffpotential functionhomotopy algorithmsigned subset sums

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Markov decision processes model sequential decisions under uncertainty; robust MDPs harden the model by letting transition probabilities be chosen adversarially from known uncertainty sets. This paper proves that for (s,a)-rectangular robust MDPs whose uncertainty sets are L∞ balls — a model that subsumes ordinary MDPs and turn-based stochastic games — policy iteration with a fixed discount factor runs in strongly polynomial time: the number of arithmetic steps is polynomially bounded in the number of states and actions, independent of the numerical values of costs, nominal probabilities, and uncertainty radii. Concretely, the robust-chain variant terminates in O(n⁴ log n · log((1−γ)/n²)/log γ) improvement steps, and the full agent–environment variant in O(n·m·log(1−γ)/log γ). This resolves an open question that had resisted proof since strongly polynomial algorithms were found for the non-robust case, and the obstacle was substantial: a naive reduction to stochastic games explodes because L∞ balls have exponentially many corners. The result shows that, once the discount factor is held constant, worst-case uncertainty in transition probabilities costs policy iteration no extra iterations.

Core claim

For an L∞ robust Markov chain with n states, RMC-PI terminates in O(n⁴ log n · log((1−γ)/n²)/log γ) iterations; for an (s,a)-rectangular L∞ RMDP, RMDP-PI terminates in O(n·m·log(1−γ)/log γ) iterations. Both counts are independent of costs, probabilities, and radii, so for fixed γ the algorithms are strongly polynomial. The engine: a potential function f_ρ measuring the largest remaining mass transfer toward a high-value successor; a halving lemma forcing that discrepancy to halve every L = log_γ((1−γ)/2n²) steps; and a combinatorial lemma: unitary signed subset sums of n+2 reals have only O(n log n) most-significant bits. Improvement uses a homotopy two-pointer algorithm, not corner enumerat

What carries the argument

Three pieces carry the argument. (1) A potential function f_ρ(s,s′,s″) = min(P*_{s,s′} − P^ρ_{s,s′}, P^ρ_{s,s″} − P*_{s,s″})·(v*_{s′} − v*_{s″}): the largest remaining mass transfer available to improve ρ, bounding the gap from both sides. (2) A halving lemma: every L = log_γ((1−γ)/2n²) iterations the critical discrepancy halves, since the value error contracts exponentially from above but cannot fall faster than (1−γ)/(2n²) per unit potential. (3) A combinatorial lemma: unitary signed subset sums of n+2 reals have O(n log n) distinct most-significant bits, so a leading digit changes only polynomially often. Policy improvement uses a homotopy two-pointer mass transfer, not corner enumeration

Load-bearing premise

The load-bearing premise (Appendix H, Step 1) is that every transition vector the homotopy step can output is a signed subset sum (coefficients −1, 0, or 1) of the nominal probabilities, the radius, and 1 — even though the one partially adjusted entry of such a vector can carry the radius with a coefficient as large as the number of states, which the counting lemma as used in the main proof does not cover.

What would settle it

Run the homotopy improvement on a small L∞ ball and enumerate every transition vector it can output: if any output has an interior entry of the form 1 − Σ_{j≠i} P̂_{s,j} + k·δ(s) with |k| ≥ 2 — a probability not expressible as a unitary signed subset sum of the nominal vector, the radius, and 1 — then the finiteness step of the proof fails for that entry and the O(n log n) scale bound cannot apply. A random search over 3–4 state chains would surface such a vector if one exists.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

For any fixed discount factor γ < 1, robust policy iteration becomes the first proven strongly polynomial algorithm for (s,a)-rectangular L∞ RMDPs; LP-based and value-iteration approaches depend on bit precision or converge only geometrically.
Because L∞ RMDPs subsume classical MDPs and turn-based stochastic games, the result reproduces and generalizes the strongly-polynomial regime previously known for those two models.
The iteration bounds are completely independent of the numerical values of costs, nominal probabilities, and uncertainty radii — only the number of states, the number of actions, and γ enter the count.
The stated formulas also show how the bound degrades as γ approaches 1 through the factor log(1−γ)/log γ, which grows without bound — a direct consequence of the theorems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The dyadic-scale counting lemma is the load-bearing number theory: extending strongly polynomial policy iteration to other uncertainty geometries (L₁ balls, general polytopes) would require an analogous finiteness statement, and for general polytopes corner counts explode — so the L∞ geometry may sit near the tractability boundary.
The bounds imply an on-the-fly stopping test for implementations: track the largest potential triple, and once its discrepancy has exhausted its O(n log n) leading bits, the current policy is provably optimal — a certificate sharper than value-gap thresholds.
The conceptual template — exponential contraction from above plus a potential-based lower bound forcing periodic halving of a discrete quantity — is generic and may transfer to other policy-improvement dynamics, including the open strongly-polynomial question for plain MDP policy iteration.
The s-rectangular (shared-uncertainty) L∞ model is not covered: coupling of the environment's choices across actions changes the potential landscape, so the argument does not obviously port, and the paper leaves that case open.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

Resolves a real open problem with a plausible proof, but the written finiteness step has a genuine gap—repairable by invoking their own Theorem 21 where Lemma 8 is used.

read the letter

Worth reading closely. The paper gives the first strongly-polynomial bound for robust policy iteration on (s,a)-rectangular L∞ RMDPs with fixed discount factor, extending Ye and Hansen et al. to a robust model that subsumes MDPs and turn-based stochastic games. The main engine is a potential function over probability mass transfers inside the L∞ balls plus a combinatorial lemma bounding the number of dyadic scales hit by signed subset sums. That lemma, and the dyadic-interval counting argument, is new and interesting. The paper is also honest about provenance: Theorem 21, the strengthened bound, is credited to an AI agent and to Sardari's improvement, and it is not used where the main proof needs it.

The reader's conditional verdict is about right. Appendix H Step 1 is the load-bearing spot: it defines X_s as the nominal probabilities plus {δ(s),1} and then applies Lemma 8, whose coefficients are restricted to {-1,0,1}. But the homotopy algorithm can produce an interior entry 1 − Σ_{j≠i} P̂_{s,j} + (|D|−|R|)δ(s), so the coefficient of δ(s) can be Ω(n), not unitary. The stress-test note is correct as written. The gap is repairable: Theorem 21 gives exactly the needed bound with C=O(n), and the authors even state it, but they don't cite it in the proof of Theorem 9. A serious referee should ask them to wire that in. Without it, the finiteness step doesn't go through as written.

Two smaller issues. The potential function is defined with a min of two one-sided discrepancies, which can be negative for an arbitrary triple; the proof never explicitly says the maximizing triple has the orientation that makes it positive (deficit at a high-value state, excess at a low-value state). This is likely a one-paragraph fix, but it needs to be there. And the bit-size condition for strong polynomiality is waved at rather than proved; for a fixed constant γ the story is fine, but it should be stated cleanly.

No circularity; the citation pattern looks fair. This deserves peer review. I'd send it out, with instructions to check Appendix H carefully.

Referee Report

2 major / 4 minor

Summary. The manuscript studies discounted (s,a)-rectangular robust MDPs with L-infinity uncertainty sets and claims that a robust policy iteration algorithm (RMDP-PI) terminates in strongly polynomial time for constant discount factor. The analysis first treats robust Markov chains: it defines a potential function over triples of states, proves contraction and mass-transfer bounds (Lemmas 4-7), and combines them with a combinatorial result on the number of dyadic intervals hit by bounded signed subset sums (Lemma 8; Theorems 20 and 21) to obtain an O(n^4 log n * log((1-gamma)/n^2)/log gamma) iteration bound for RMC-PI (Theorem 9). It then extends the approach to RMDPs, obtaining O(n m log(1-gamma)/log gamma) iterations (Theorem 17). The main text gives proof sketches; full proofs are in the appendices.

Significance. If the proof can be completed, this is a substantial contribution: it would resolve a recognized open problem on strongly polynomial algorithms for robust MDPs with L-infinity uncertainty and fixed discount, generalizing results of Ye and of Hansen et al. to the robust setting. The potential-function/mass-transfer framework and the explicit dyadic-interval bounds are interesting ingredients in their own right, and the paper is careful to distinguish its own Theorem 20 from the independently obtained strengthening Theorem 21. It also correctly identifies why a previous claimed reduction to stochastic games does not yield a polynomial algorithm. However, the written proof contains gaps that must be repaired before the claims are established.

major comments (2)

[Appendix H (proof of Theorem 9), Step 1] Step 1 asserts that for X_s = {P-hat_{s,s'}} union {delta(s), 1}, every homotopic transition probability P^rho_{s,s'} belongs to A(X_s) as defined in Lemma 8, i.e. with coefficients in {-1,0,1}. This is not correct. As described in the properties of homotopic policies in Section 3, an interior entry can be p_i = 1 - sum_{j != i} P-hat_{s,j} + (|D_s| - |R_s|) delta(s), where R_s and D_s can both be large. The coefficient of delta(s) is therefore generally not in {-1,0,1} and can be Omega(n). Consequently Lemma 8, whose unitary signed subset sums only cover coefficients in {-1,0,1}, does not bound the number of most significant bits of P*_{s,s'} - P^rho_{s,s'}. The paper itself states Theorem 21, which gives a bound for a general coefficient bound C, but Theorem 21 is not cited or used in Appendix H. The finiteness step becomes valid if Theorem 21 (or a version of Lemma 8 with C = O(n)) is
[Lemma 5 / Appendix E] In the mass-transfer proof of Lemma 5, each elementary transfer from state k to state j is bounded by f^rho(i,j,k). But f^rho(s,s',s'') = min(...) * (v*_{s'} - v*_{s''}) is nonpositive whenever v*_{s'} < v*_{s''}; in that case it cannot upper-bound the absolute contribution m|v*_j - v*_k|. The proof implicitly assumes all transfers go from lower-value to higher-value states. While this monotonicity does hold for the optimal L-infinity-constrained maximizing distribution and can be proved by a rearrangement/Monge argument, it is not stated or established in the manuscript. Without it, Lemma 5, and hence Lemma 7 and the iteration bound, are not fully supported. Please add an explicit justification, or adjust the potential/definition so that sign issues are handled.

minor comments (4)

[Appendix H, Step 1] The sentence 'it can be verified that rho_s in X_s' should presumably read 'P^rho_s in A(X_s)' or 'P^rho_{s,s'} in A(X_s)'; as written it conflates a probability vector with a scalar set.
[Appendix G / Section 1] The inclusion of the Aletheia-generated Theorem 21 and the reproduced prompt/output is unusual. Even if the mathematics is correct, the provenance of the theorem and the direct quotation from an AI agent should be handled according to the journal's policies on AI contributions, and the relationship of Theorem 21 to the main proof should be clarified (it is stated but not used).
[Section 5] The sentence 'We first recall the Bellman operator and its properties (Lemma 11), which imply the exponential convergence rate of RMDP-PI (Lemma 11)' cites Lemma 11 twice; the second reference should be Lemma 12.
[General] There are several typographical and grammatical issues (e.g., 'undefined' in places, 'uncertaninty' in Section 5, inconsistent capitalization). A careful proofreading pass is recommended.

Circularity Check

0 steps flagged

No material circularity: the polynomial iteration bound is proved from independent combinatorial and geometric lemmas; the main weakness is a proof gap, not circularity.

full rationale

The paper's central bound does not assume its conclusion. The potential function f^ρ is defined using P* and v*, but the lower/upper bounds relating ∥v*−v^ρ∥ to f^ρ are proved from the Bellman equations in Appendices D–F and do not presuppose the polynomial iteration bound. Lemma 8 is proved independently in Appendix G via a dyadic-interval/Siegel-lemma argument (Theorem 20), and Theorem 9 follows by chaining Lemma 2 (exponential contraction), Lemma 7 (halving of discrepancies) and Lemma 8 (polynomially many MSBs) without reusing the theorem being proved. The one self-citation (Chatterjee et al. 2024) is used in the introduction to explain why a previously claimed reduction from RMDPs to turn-based stochastic games is not polynomial-size; this is motivational context and is not load-bearing for the new proof. The citation of Feng et al. 2026 / Aletheia (Theorem 21) is expressly auxiliary: the paper states 'our own Theorem 20 is sufficient for Lemma 8' and merely reports the stronger version, so it is not part of the derivation chain. The substantive weakness flagged by the skeptic is a correctness gap, not circularity: Appendix H Step 1 asserts that homotopic policies produced by Algorithm 2 lie in A(X_s) with coefficients in {−1,0,1}, but Algorithm 2's 'interior' entry can have the form 1 − Σ_{j≠i} P̂_{s,j} + (|D|−|R|)δ(s), so the coefficient of δ(s) need not belong to {−1,0,1} and Lemma 8 as stated may not bound the discrepancy. This gap means the finiteness step is unsupported as written, but it does not reduce the conclusion to an input or a self-citation; it is a repairable mathematical gap rather than circular reasoning.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

The proof relies on standard tools (Siegel's lemma, Banach fixed point), the rectangular L-infinity modeling assumption, and the external homotopy algorithm. No fitted parameters or invented physical entities appear. The main internal theorem (dyadic-interval bound) is proved rather than assumed.

axioms (5)

standard math Siegel's lemma
Used in Appendix G (Proposition 25 and Lemma 27) to prove the dyadic-interval bound Theorems 20/21; quoted from Diophantine Geometry.
standard math Banach fixed-point theorem
Used in Lemmas 1 and 11 to establish contraction and unique fixed point of the robust Bellman operator.
domain assumption (s,a)-rectangular L-infinity uncertainty sets
Assumptions 1 and 2 define the model; the entire result is scoped to this uncertainty class.
domain assumption Positional deterministic optimal policies exist
Invoked in Section 2 (Policy Types), citing Iyengar (2005) and Nilim & El Ghaoui (2005).
domain assumption Homotopy algorithm of Behzadian et al. (2021) is correct and runs in O(n log n)
Algorithm 2 is taken from prior work; correctness is cited, not reproved in this paper.

pith-pipeline@v1.3.0-alltime-deepseek · 23819 in / 19666 out tokens · 215868 ms · 2026-08-03T06:09:37.568887+00:00 · methodology

0 comments

Cite this review

Pith. "Pith review of Strongly Polynomial Time Complexity of Policy Iteration for $L_\infty$ Robust MDPs." pith.science (2026). https://pith.science/paper/LCMZXK7I

@misc{pith2026260123229,
  author       = {Pith},
  title        = {Pith review of: Strongly Polynomial Time Complexity of Policy Iteration for $L_\infty$ Robust MDPs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LCMZXK7I}},
  note         = {Machine review of arXiv:2601.23229}
}

Share X Bluesky LinkedIn Reddit HN

read the original abstract

Markov decision processes (MDPs) are a fundamental model in sequential decision making. Robust MDPs (RMDPs) extend this framework by allowing uncertainty in transition probabilities and optimizing against the worst-case realization of that uncertainty. In particular, $(s, a)$-rectangular RMDPs with $L_\infty$ uncertainty sets form a fundamental and expressive model: they subsume classical MDPs and turn-based stochastic games. We consider this model with discounted payoffs. The existence of polynomial and strongly-polynomial time algorithms is a fundamental problem for these optimization models. For MDPs, linear programming yields polynomial-time algorithms for any arbitrary discount factor, and the seminal work of Ye established strongly--polynomial time for a fixed discount factor. The generalization of such results to RMDPs has remained an important open problem. In this work, we show that a robust policy iteration algorithm runs in strongly-polynomial time for $(s, a)$-rectangular $L_\infty$ RMDPs with a constant (fixed) discount factor, resolving an important algorithmic question.

Figures

Figures reproduced from arXiv: 2601.23229 by Ali Asadi, Alipasha Montaseri, Carlo Pagano, Ehsan Goharshady, Krishnendu Chatterjee, Mehrdad Karrabi.

**Figure 1.** Figure 1: Visualization of the Homotopy Algorithm 2. by reaching 1 or Pˆ shi + δ(s), then hi is increased by one. Similarly, if pslo could not be decreased further, i.e. by reaching 0 or Pˆ slo − δ(s), then lo is decreased by one. See Behzadian et al. (2021) for correctness arguments. Properties of Homotopic Policies. The distribution p generated by Algorithm 2 possesses a specific structure that becomes useful lat… view at source ↗

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

On the Complexity of Discounted Robust MDPs with $L_p$ Uncertainty Sets
cs.CC 2026-05 unverdicted novelty 7.0

Policy iteration for discounted robust MDPs is strongly polynomial for L1 and L∞ uncertainty sets but hard for other Lp sets.

Reference graph

Works this paper leans on

6 extracted references · cited by 1 Pith paper

[1]

Let(σ 1, σ2)be a strategy profile inG. We construct a policy profile(σ, ρ)inRthat generates the same probability distribution over the set of infinite sequences of states inS R simply becausePr (σ1,σ2)(s)[s′] = Pr (σ,ρ)[s](s′). Specifically,σ(s) =σ 1(s)for alls∈ S 1 ∪ Sr. Note that fors∈ S 2,|A R(s)|= 1, henceσ(s)is defined in the trivial manner. Forρ, th...
[2]

C 1-linearly independent

Let(σ, ρ)be a policy profile inR. We construct(σ 1, σ2)to be a strategy profile inGwhich induces the same transition function as(σ, ρ). Given the construction ofR, it is possible to put σ1(s) =σ(s)for alls∈ S 1. Forσ 2, lets∈ S2 be arbitrary. We defineσ2(s) =ρ(s, a)for the 16 STRONGLYPOLYNOMIALTIMECOMPLEXITY OFPOLICYITERATION FORL ∞ ROBUSTMDPS unique acti...

2026
[3]

linear independence

We shall not make the analogy entirely strict by makingXto be a subset of the completion of the function field with respect to the degree valuation, as the purpose of the function field analogy is to simply illustrate the proof in an idealized setting. 22 STRONGLYPOLYNOMIALTIMECOMPLEXITY OFPOLICYITERATION FORL ∞ ROBUSTMDPS Method Sketch: Letk=|X|. We aim ...

2000
[4]

Given the properties of such policies, discussed in Section 3, we defineX s as follows so thatP ρ s,s′ ∈A(X s)for alls, s′ ∈ S: Xs ={ ˆPs,s′ |s ′ ∈ S} ∪ {δ(s),1}

Finite Discrepancy Set.For a stateswith nominal transition vector ˆPs and uncertainty radius δs, the realized transition probabilityP=P ρ s in any policyρresults from redistributing mass under theL ∞ constraint, according to Algorithm 2. Given the properties of such policies, discussed in Section 3, we defineX s as follows so thatP ρ s,s′ ∈A(X s)for alls,...
[5]

Let(s t, s′ t, s′′ t ) = argmaxs,s′,s′′ fρt(s, s′, s′′)be the maximizing triple

Convergence Rate.Let ft(s, s′, s′′) = min P ∗ s,s′ − Pρt s,s′,P ρt s,s′′ − P∗ s,s′′ (v∗ s′′ −v ∗ s′) be the potential value at iterationt. Let(s t, s′ t, s′′ t ) = argmaxs,s′,s′′ fρt(s, s′, s′′)be the maximizing triple. Lemma 7 states that forL= log γ 1−γ 2n2 , the mass transfer quantity associated with this triple decreases by a factor of at least 2 afte...
[6]

For any specific triple, the mass transfer value can take at mostO(nlogn)different logarithmic scales (from Step 1) before it vanishes or the triple is no longer active

Total Complexity.There are at mostn 3 distinct triples(s, s′, s′′). For any specific triple, the mass transfer value can take at mostO(nlogn)different logarithmic scales (from Step 1) before it vanishes or the triple is no longer active. Since each scale reduction requires at mostLsteps, we bound the total number of steps by: Total Iterations≤n 3 × O(nlog...

[1] [1]

Let(σ 1, σ2)be a strategy profile inG. We construct a policy profile(σ, ρ)inRthat generates the same probability distribution over the set of infinite sequences of states inS R simply becausePr (σ1,σ2)(s)[s′] = Pr (σ,ρ)[s](s′). Specifically,σ(s) =σ 1(s)for alls∈ S 1 ∪ Sr. Note that fors∈ S 2,|A R(s)|= 1, henceσ(s)is defined in the trivial manner. Forρ, th...

[2] [2]

C 1-linearly independent

Let(σ, ρ)be a policy profile inR. We construct(σ 1, σ2)to be a strategy profile inGwhich induces the same transition function as(σ, ρ). Given the construction ofR, it is possible to put σ1(s) =σ(s)for alls∈ S 1. Forσ 2, lets∈ S2 be arbitrary. We defineσ2(s) =ρ(s, a)for the 16 STRONGLYPOLYNOMIALTIMECOMPLEXITY OFPOLICYITERATION FORL ∞ ROBUSTMDPS unique acti...

2026

[3] [3]

linear independence

We shall not make the analogy entirely strict by makingXto be a subset of the completion of the function field with respect to the degree valuation, as the purpose of the function field analogy is to simply illustrate the proof in an idealized setting. 22 STRONGLYPOLYNOMIALTIMECOMPLEXITY OFPOLICYITERATION FORL ∞ ROBUSTMDPS Method Sketch: Letk=|X|. We aim ...

2000

[4] [4]

Given the properties of such policies, discussed in Section 3, we defineX s as follows so thatP ρ s,s′ ∈A(X s)for alls, s′ ∈ S: Xs ={ ˆPs,s′ |s ′ ∈ S} ∪ {δ(s),1}

Finite Discrepancy Set.For a stateswith nominal transition vector ˆPs and uncertainty radius δs, the realized transition probabilityP=P ρ s in any policyρresults from redistributing mass under theL ∞ constraint, according to Algorithm 2. Given the properties of such policies, discussed in Section 3, we defineX s as follows so thatP ρ s,s′ ∈A(X s)for alls,...

[5] [5]

Let(s t, s′ t, s′′ t ) = argmaxs,s′,s′′ fρt(s, s′, s′′)be the maximizing triple

Convergence Rate.Let ft(s, s′, s′′) = min P ∗ s,s′ − Pρt s,s′,P ρt s,s′′ − P∗ s,s′′ (v∗ s′′ −v ∗ s′) be the potential value at iterationt. Let(s t, s′ t, s′′ t ) = argmaxs,s′,s′′ fρt(s, s′, s′′)be the maximizing triple. Lemma 7 states that forL= log γ 1−γ 2n2 , the mass transfer quantity associated with this triple decreases by a factor of at least 2 afte...

[6] [6]

For any specific triple, the mass transfer value can take at mostO(nlogn)different logarithmic scales (from Step 1) before it vanishes or the triple is no longer active

Total Complexity.There are at mostn 3 distinct triples(s, s′, s′′). For any specific triple, the mass transfer value can take at mostO(nlogn)different logarithmic scales (from Step 1) before it vanishes or the triple is no longer active. Since each scale reduction requires at mostLsteps, we bound the total number of steps by: Total Iterations≤n 3 × O(nlog...