REVIEW 2 major objections 3 minor 4 references
Value-Set Iteration: Computing Optimal Correlated Equilibria in Infinite-Horizon Multi-Player Stochastic Games
T0 review · 2 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read In infinite-horizon stochastic games, an $(\epsilon,\delta)$-optimal correlated equilibrium can be computed in time polynomial in the game size and in $(1/(\epsilon\delta(1-\gamma)))^{n+1}$, and for $c$-turn-based games, in time…
desk verdict Solid general algorithm with a real gap in the c-turn-based speedup; worth reviewing and fixing. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the inducible value set $V^\star(s)$, the set of all payoff vectors a correlated equilibrium can induce from state $s$, together with the update map $\Phi$ that expands a candidate value-set function by forcing a Bellman-like decomposition, an incentive-compatibility constraint, and the requirement that all continuation values lie inside the candidate sets. $\Phi$ is monotone, so Tarski's fixed-point theorem yields a greatest fixed point, which is shown to be $V^\star$. The algorithmic version replaces $\Phi$ with a grid approximation $\hat{\Phi}$ whose values are convex hulls of grid points near $\Phi$, and reduces membership checks to a linear program obtained by substituting $z(a,b,s') = \bar{\pi}(a) \cdot y(a,b,s')$ for the product of a first-step action distribution and a convex-combination weight on a polytope vertex.
What would settle it
Take the two-agent game from Theorem 1, whose only high-value correlated equilibrium uses an irrational probability, feed it to value-set iteration with a fine rational grid, and explicitly simulate all one-step deviations of the returned policy: if the policy violates a deviation constraint by more than $\delta$ or its principal value is more than $\epsilon$ below the optimal exact CE value, the approximation theorem is false.
Extended reading notes
Core claim
The central discovery is that the set of all values inducible at a state by a correlated equilibrium — the inducible value set — is exactly the greatest fixed point of a monotone operator $\Phi$ acting on value-set functions. Value-set iteration, starting from the hypercube of all possible values, converges to this greatest fixed point, and a grid-discretized version reaches an approximate fixed point in finitely many iterations. Every point in that approximate fixed point is shown to be $(\epsilon,\delta)$-inducible, so picking the point with the best principal value yields an $(\epsilon,\delta)$-optimal correlated equilibrium whose policy can be queried on demand for any history in polynomial time. For $c$-turn-based games, a $\lambda$-memory meta-game construction keeps the relevant value sets low-dimensional, giving polynomial dependence on the number of players.
Load-bearing premise
The whole fixed-point and complexity analysis rests on the linear program that tests membership in the $\xi$-neighborhood of $\Phi(V)(s)$ being exact even when the recommended action has probability zero, and on the number of vertices of each value set staying within the grid-derived bound; if either fails, the computed policy may not be a $\delta$-CE and the stated running time would not follow.
Editorial extensions
If this is right
- For any fixed number of agents, an $(\epsilon,\delta)$-optimal correlated equilibrium can be computed in polynomial time, and the resulting policy can be executed by generating its action distribution on the fly for any queried history.
- For $c$-turn-based games, the running time is polynomial in the number of agents, since the $\lambda$-memory meta-game keeps the effective value-space dimension constant.
- The $\delta$ allowance in the incentive constraints is not merely a convenience: the paper proves that without such resource augmentation, even a constant-factor approximation of the optimal stationary correlated equilibrium is NP-hard, and that rational-probability policies can lose arbitrarily relative to irrational ones.
- The same algorithm readily computes a correlated equilibrium (not necessarily optimal) in time exponential in the number of agents, and the paper leaves open whether that dependence can be removed for succinctly represented games.
- The bi-criterion formulation lets the algorithm compare against the best exact correlated equilibrium while only ever needing to produce a $\delta$-CE, matching the inapproximability results that rule out stronger guarantees.
Reading between the lines
- The greatest-fixed-point view of inducible value sets likely transfers to other history-dependent solution concepts, such as extensive-form communication equilibria, where compact value-based representations could bypass explicit history enumeration in the same way.
- The paper's on-the-fly policy generation suggests a natural online implementation: rather than materializing a strategy, an agent could run the LP-based query procedure at each time step, which may be especially useful when the game is learned rather than fully specified in advance.
- The parameter $\lambda = \log(\xi/4)/\log\gamma$ reveals a concrete trade-off: as the discount factor approaches 1, the memory depth needed for the turn-based speedup grows, so the polynomial-in-$n$ guarantee degrades as $\gamma \to 1$; a direct test would be to measure the running time on the same $c$-turn-based instance under increasing $\gamma$.
- The LP substitution $z = \bar{\pi} \cdot y$ suggests that similar linearization may handle other bilinear incentive constraints that arise when a coordinator and agents interact over time, providing a template beyond correlated equilibria.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies computation of optimal extensive-form correlated equilibria in infinite-horizon discounted multi-player stochastic games. It introduces value-set iteration, a fixed-point algorithm based on inducible value sets, and proves that with a bi-criterion approximation—value within epsilon and incentive violation at most delta—an (epsilon, delta)-optimal CE can be computed in time polynomial in the game size and (1/(epsilon*delta*(1-gamma)))^(n+1) (Theorem 15), and in time polynomial in the number of players for c-turn-based games (Theorem 18). It also presents two inapproximability results: restricting policies to rational probabilities can arbitrarily degrade the value (Theorem 1), and computing an (epsilon, delta)-optimal stationary CE is NP-hard under the resource-augmentation benchmark (Theorem 2). The central fixed-point characterization, the convergence analysis, and the LP membership test are laid out in detail; the main weakness I identify concerns the c-turn-based extension, where the proof of Lemma 17 does not control the incentive error for inactive agents and the complexity argument does not account for the full-dimensional vertex representation of the cylinder-shaped value sets.
Significance. If correct, the results are significant: they give the first general algorithmic treatment of optimal history-dependent CEs in infinite-horizon stochastic games, with a clean fixed-point characterization and matching hardness results that justify the bi-criterion relaxation. The general constant-n algorithm appears sound: the value-set iteration converges by monotonicity to the greatest fixed point, the finite-grid approximation is parameter-free after choosing xi, and Lemma 14's LP substitution is valid, including the case where pi-bar(a) = 0. The advertised c-turn-based polynomial-in-n result is, however, not established by the current proofs; fixing Lemma 17 and the vertex-representation issue are necessary before the main claim can be accepted.
major comments (2)
- [Section 5.2, Lemma 17 (Appendix A.3)] The proof of Lemma 17 does not establish the delta-CE property for agents that are not in the acting set of the current meta-state. In the displayed comparison of Q^{pi,rho} and Q^{pi,rho,tilde r}, the first sum Sum_{ell=t+1}^{t+lambda} gamma^{ell-t} xi' is justified only for agents i in I_{x_t^0}; for any j not in I_{x_t^0}, the neighborhood neigh^{I_x}_{xi'} relaxes coordinate j to the whole box, so the subsidy error at ell=t+1 can already be 1+xi, not xi'. Since Definition 1 requires the incentive constraint at every history (sigma; s, a), including histories where j does not act, and a deviation by j changes the recorded action and hence the future correlation signals, the conclusion that pi is a delta-CE is not supported by the written argument. This gap is load-bearing for Theorem 18's polynomial-in-n claim.
- [Section 5.2, Lemma 16 and Theorem 18] The complexity bound for c-turn-based games does not follow from the representation used in the manuscript. Lemma 16 counts only the grid points in the active dimensions I_x and concludes that the number of grid points per meta-state is (2/xi+2)^{(lambda+1)c}; however, the value set V(x) is a cylinder over the inactive coordinates, so its vertex representation as a polytope in R^{n+1} has 2^{n+1-|I_x|} vertices multiplied by the active vertices. Lemma 14, which Theorem 18 invokes, explicitly assumes a vertex representation and its LP has one variable per vertex, so a direct application has cost exponential in n. The paper does not provide the alternative polynomial-size H-representation or separation-oracle version of Lemma 14 needed to make the polynomial-in-n claim follow.
minor comments (3)
- [Appendix A.1, proof of Theorem 2] The principal's reward at each x_i is r_max, so the discounted value in the yes case is gamma^2 * r_max (not gamma^2), and the threshold in the no case and the constant epsilon should be scaled by r_max. The reduction is unaffected because r_max is a constant for fixed gamma, but the displayed numbers should be corrected.
- [Appendix A.3, proof of Lemma 16] The sentence 'The fact that V = bPhi_TB(V) and V subset of V* follows the same argument there' reverses the inclusion asserted by the lemma; it should be V supset of V*.
- [Section 5.1] The statement 'Since lambda is a constant' is not accurate when gamma and xi are part of the input, because lambda = log(xi/4)/log gamma depends on the accuracy and discount parameters. Theorem 18 should state explicitly that the bound is polynomial in the listed arguments with lambda fixed, or the dependence on 1/xi and 1/(1-gamma) should be tracked.
Circularity Check
No significant circularity: the fixed-point characterization and LP-based construction are self-contained; the one appeal to prior work is not load-bearing.
full rationale
The paper's central derivation is self-contained. V*(s) is defined as the set of inducible values, and Proposition 3 expands any value in V*(s) into a one-step Bellman expansion together with the IC and onward-value constraints; the same constraints define Phi, so the fixed-point equation is not assumed but proved from the definitions. Lemmas 4 and 11 (the inducibility of fixed points) are proved constructively: Algorithm 2 expands the target value through the fixed point and the proof of Lemma 12 compares the original, subsidized, and truncated games to show that the resulting policy is a delta-CE inducing a value within epsilon. Lemma 14 is an LP feasibility test; the quadratic-to-linear substitution z(a,b,s') = pi-bar(a)*y(a,b,s') is explicitly verified in both directions, including the pi-bar(a)=0 case, so it is a mathematical equivalence rather than a smuggled assumption. No fitted parameter is later called a prediction, and the inapproximability results (Theorems 1 and 2) are reductions from irrational-value constructions and GAP 3-SAT/PCP, independent of the algorithmic claim. The only appeal to previous work is the pointer to Murray and Gordon (2007) in the proof of Lemma 4, but the paper supplies a more general self-contained proof (Lemmas 11-12), so that citation is not load-bearing. The reviewer-identified weakness in Lemma 17--that the lambda-step error bound may not cover agents inactive at the current meta-state--is a potential correctness gap in the c-turn-based construction, not a circularity; it concerns whether a stated bound holds, not whether an input is being recycled as an output. Therefore no circular step can be exhibited, and the circularity score is 0.
Assumptions & free parameters
free parameters (2)
- discretization step xi =
xi = (1-gamma) * min{epsilon, delta/2}
- memory window lambda =
lambda = log(xi/4) / log gamma
assumptions (6)
- standard math Tarski fixed point theorem: every monotone map on a complete lattice has a greatest fixed point.
- domain assumption The game has finite state and action spaces, perfect recall, and the interaction history becomes common knowledge at the end of each time step.
- domain assumption Rewards are normalized to [-(1-gamma)/2,(1-gamma)/2].
- domain assumption Immediate deviation checking (Eq. (5)) is sufficient for global incentive compatibility because the policy is IC in every subgame.
- standard math A correlated equilibrium exists in every one-shot game.
- domain assumption The choice lambda = log(xi/4)/log gamma ensures (1+xi)*gamma^lambda < xi/2, requiring gamma < 1.
Cite this review
Pith. "Pith review of Value-Set Iteration: Computing Optimal Correlated Equilibria in Infinite-Horizon Multi-Player Stochastic Games." pith.science (2026). https://pith.science/paper/5MRG7SOD
@misc{pith2026250607186,
author = {Pith},
title = {Pith review of: Value-Set Iteration: Computing Optimal Correlated Equilibria in Infinite-Horizon Multi-Player Stochastic Games},
year = {2026},
howpublished = {\url{https://pith.science/paper/5MRG7SOD}},
note = {Machine review of arXiv:2506.07186}
}
abstract
We study the problem of computing optimal correlated equilibria (CEs) in infinite-horizon multi-player stochastic games, where correlation signals are provided over time. In this setting, optimal CEs require history-dependent policies; this poses new representational and algorithmic challenges as the number of possible histories grows exponentially with the number of time steps. We focus on computing $(\epsilon, \delta)$-optimal CEs -- solutions that achieve a value within $\epsilon$ of an optimal CE, while allowing the agents' incentive constraints to be violated by at most $\delta$. Our main result is an algorithm that computes an $(\epsilon,\delta)$-optimal CE in time polynomial in $1/(\epsilon\delta(1 - \gamma))^{n+1}$, where $\gamma$ is the discount factor, and $n$ is the number of agents. For (a slightly more general variant of) turn-based games, we further reduce the complexity to a polynomial in $n$. We also establish that the bi-criterion approximation is necessary by proving matching inapproximability bounds. Our technical core is a novel approach based on inducible value sets, which leverages a compact representation of history-dependent CEs through the values they induce to overcome the representational challenge. We develop the value-set iteration algorithm -- which operates by iteratively updating estimates of inducible value sets -- and characterize CEs as the greatest fixed point of the update map. Our algorithm provides a groundwork for computing optimal CEs in general multi-player stochastic settings.
Figures
Figures from the paper (1 more)
Reference graph
Works this paper leans on
-
[1]
∈ ∆({a, b}). Let x = π(a | s′ i) and suppose that the agent responds by playing actiona with probability y. In this case, the agent’s value is v(x, y) = xy · (1 + γ · v(x, y)) + x(1 − y) · (0 + γ · 0) + (1 − x)y · (0 + γ · 0) + (1 − x)(1 − y) · (2 + γ · v(x, y)), where we used the fact that the value at states′′ 1 is 0. When γ = 1/2, This gives v(x, y) = ...
work page 2007
-
[2]
Subsidized gameGsubs: During the execution ofπ, each player is subsidized by˜r according to the interaction history. Every time a new states is generated following historyσ, every player i receives a reward˜ri(σ; s), in addition to their original rewards given byr
-
[3]
Additionally, we terminate it at time stept + 1
Truncated game Gtrun: The game is subsidized as above. Additionally, we terminate it at time stept + 1. In this final time step, regardless of the joint action performed, every player i receives only a rewardui(σ; st+1) based on the history(σ; st+1)
-
[4]
The Original gameG (where neither ˜r nor u is applied). Subsidized vs. Truncated We first compareGsubs and Gtrun and show thatπ forms a CE in both games and inducesv. In what follows, we denote byV π,˜r and V π,˜r the V-values induced by π in Gsubs and Gtrun, respectively. The same notation applies to the Q-values. For Gtrun, this can be verified by induc...
work page 2011
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.