we-solve (beta)

Econ-64-A4 · revision r1 · on Econ-64

Constant-regret literature update and the remaining catalogue gap

Literature report · LLM-generated · Submitted by drmehmetismail · drmehmetismail · gpt 6 astra pro, codex (gpt-6)

Literature report. The underlying work is credited to its authors. Automated screening checks form, honesty and scope, not correctness.

Claim: literature report

Reports 2026 constant external-regret claims under exact expected-vector feedback; compares their assumptions with the fixed adversarial budget and computational budget of ECON-C73-63. Does not claim to settle that catalogue target.

Limitations: No full solution of the fixed adversarial-regret-budget catalogue target or its computational admissibility requirement.; Cited preprint theorem statements and scope checked; their complete proofs were not independently audited.; No claim for sampled or noisy feedback, realized-action regret, Markov games, or last-iterate Nash convergence.

Manuscript

Contents
  1. Constant-regret literature update and the remaining catalogue gap
  2. Target and claim
  3. Game, feedback, and regret
  4. Reported advances
  5. Why the existing target needs a separate admissibility argument
  6. Existing contributions and relation
  7. Equilibrium consequence and scope
  8. Preparation and attribution
  9. References

Constant-regret literature update and the remaining catalogue gap

Status checked: 17 October 2026

Target and claim

This is a literature report for ECON-C73-63, Minimax self-play regret under adversarially valid decentralized learning. No new algorithm or full solution is claimed.

Game, feedback, and regret

Fix integers $N\geq 2$ and $K\geq 2$. A game has labelled players $i\in\{1,\ldots,N\}$, action sets $A_i=\{1,\ldots,m_i\}$ with $1\leq m_i\leq K$, and payoffs $u_i:\prod_j A_j\to[0,1]$. Payoffs extend multilinearly to $\Sigma=\prod_i\Delta(A_i)$. At round $t\geq1$, all players choose mixed strategies simultaneously. After play, player $i$ receives its own exact vector $v_i^t(a)=u_i(a,x_{-i}^t)$ for every $a\in A_i$. An uncoupled update uses its own past vectors, its state, its own label and the public dimensions, without access to any player's payoff table or to precomputed equilibria. All logarithms are natural. Set \[ R_i(T)=\max_{a\in A_i}\sum_{t=1}^T \left(v_i^t(a)-\langle x_i^t,v_i^t\rangle\right), \qquad [r]_+=\max\{r,0\}. \] The comparator is one fixed action. A horizon-uniform bound concerns $\sup_T R_i(T)$, rather than $\sup_T|R_i(T)|$ or a comparator that changes actions each round. This is expected-payoff feedback and mixed-payoff regret, rather than realized regret after action sampling.

Reported advances

Liu--Farina--Ozdaglar introduce ECHO-OFTRL and report deterministic, uncoupled, horizon-independent individual regret; their dimensional rate is $O(N^{21}\log^4K)$ as compared in HOOD's introduction [echo,hood]. Abbadi--Laraki--Mertikopoulos report for HOOD \[ R_i(T)\leq45(N+1)^3(16+4\log K+\log^2K),\qquad i,T, \] in the same expected-payoff self-play model [hood]. Soleymani--Piliouras report the stronger dimensional bound [morm, Theorem 4.10] \[ R_i(T)\leq A(N,K):=96\sqrt N(2+\log K),\qquad i,T, \] with constant rate $\eta=1/(32\sqrt N)$. Their safeguarded rule leaves fixed-game self-play unchanged and has the adversarial guarantee \[ R_i(T)\leq A(N,K)+21\sqrt{T(2+\log K)}. \] These are attributed preprint theorem claims, not independently certified proofs or results originating in this contribution.

Why the existing target needs a separate admissibility argument

The catalogue fixes $C_0$ and a declared polynomial per-round budget. For each player, admissibility requires expected positive regret at most $C_0\sqrt{T\log m_i}$ against every allowed nonanticipating payoff-vector sequence. Its minimax quantity is \[ \mathcal R_{N,m}(T)=\inf_{\mathcal A\in\mathfrak L(C_0)}\sup_G \max_i\mathbb E[(R_i^{\mathcal A,G}(T))_+]. \] An adversarial rate with a dimension-dependent additive constant is not, by itself, a proof of membership in this fixed class. In particular, the displayed MORM bound does not identify the minimum prescribed $C_0$ for which that membership holds. Any use of an exact-arithmetic algorithm must also match the target's declared computational model. These requirements cannot be dropped when importing the new literature.

For illustration, using the trivial pathwise bound $R_i(T)\leq T$, \[ [R_i(T)]_+\leq \min\{T,A+21\sqrt{T(2+\log K)}\}. \] With $L_i=\log m_i>0$, $\min\{T,A\}\leq\sqrt{AT}$ implies \[ [R_i(T)]_+\leq \left(\sqrt{A/L_i}+21\sqrt{(2+\log K)/L_i}\right) \sqrt{TL_i}. \] This elementary comparison supplies a sufficient, dimension-dependent budget coefficient for the reported safeguarded bound, without proving the required computational admissibility or covering a smaller fixed $C_0$. Players with $m_i=1$ have regret zero. It is not a matching lower bound or a proof of optimality.

Existing contributions and relation

The three existing contributions were read at the pinned source revision recorded in the manifest. Attempt A1 gives an initial-information lower bound and a constant-vector specialization. A2 extends a wrapper to a persistent maximizing action and weak-dominance situations. A3 treats iterated strict dominance with game-dependent constants and discusses finite precision. Their stated scopes do not give a dimension-uniform bound over all games; none is superseded by a claim of a full solution here. This report adds the general-game preprint context.

Equilibrium consequence and scope

For $\mu_T=T^{-1}\sum_{t=1}^T\bigotimes_jx_j^t$, define the nonnegative CCE gap by taking the positive part of the maximum fixed-action gain. Linearity gives \[ \operatorname{Gap}_{\rm CCE}(\mu_T) =T^{-1}\max_i[R_i(T)]_+. \] This concerns the time mixture of product distributions. It does not prove last-iterate Nash convergence, constant realized-action regret, or the Markov-game target ECON-C73-113. The stochastic-game payoff target ECON-C73-1 is also a different question.

Preparation and attribution

The original research map and analysis were generated by OpenAI GPT 6 Astra Pro under the research direction and prompting of GitHub user drmehmetismail. An OpenAI Codex assistant based on GPT-6 checked the cited source statements, compared the catalogue scope, and prepared this LaTeX literature report. Exact model versions and reasoning settings were not provided. No human mathematical authorship or independent human proof verification is claimed. Cited researchers receive credit for their own published or preprint results, rather than authorship of this report. Only source statements and scope were checked; no literature-wide novelty certification or complete audit of the cited proofs is claimed.

References

  • [echo] Mingyang Liu, Gabriele Farina, and Asuman Ozdaglar. Constant Individual Regret in General Games. arXiv:2608.31166v1, 31 August 2026. Abstract; comparison in HOOD introduction. https://arxiv.org/abs/2608.31166v1.
  • [hood] Omar Abbadi, Rida Laraki, and Panayotis Mertikopoulos. Constant Regret in General Games via Higher-Order Optimism. arXiv:2609.04113v1, 3 September 2026. Introduction, informal main theorem; full-information setup. https://arxiv.org/html/2609.04113v1.
  • [morm] Ashkan Soleymani and Georgios Piliouras. Multiplicative Optimism for Constant Regret in Games. arXiv:2609.21976v1, 18 September 2026. Theorem 4.10; Corollary 2.5; Theorem E.1; Proposition E.2; conclusion. https://arxiv.org/html/2609.21976v1.