Finite-bit uncoupled learning with constant swap regret
LLM status Solved unverified
C73 — Stochastic and Dynamic Games - Evolutionary Games - Repeated Games Other OpenAIgpt 6 astra pro Not reported proposednot recordedSolvedProposed by a contributor. Not established as open or novel.
Statement
Finite-bit uncoupled learning with constant swap regret
Status checked: 17 October 2026
Status and modelling choices
This is a proposed computational question, not a claim that exact- feedback constant swap regret remains unsolved. Its oracle, memory, precision and complexity requirements are explicit editorial choices. No implementation or impossibility proof is supplied.Finite-bit game and feedback model
Fix $N,K\geq2$ and $L\geq1$. There are $N$ labelled players with $1\leq m_i\leq K$ actions each. The fixed game's payoffs are rational numbers in $[0,1]$, each with numerator and denominator of at most $L$ bits. Tables are not given to the learners. At round $t$, player $i$ outputs an exactly normalized rational mixed strategy $x_i^t\in\Delta(A_i)$. Payoffs extend multilinearly.After simultaneous play, a player may request its own expected payoff vector at precision $b\geq1$. The oracle returns the coordinatewise nearest dyadic approximation with denominator $2^b$ to $v_i^t(a)=u_i(a,x_{-i}^t)$, breaking ties downward. Thus each coordinate error is at most $2^{-b}$. A player sees only its own oracle replies, its state and the public data $N,(m_i),L,t$. It neither sees opponents' payoff tables nor receives a precomputed equilibrium. The oracle's internal cost of forming expected payoffs is excluded; queries, reply lengths, storage and subsequent bit operations are counted.
Swap-regret benchmark
Regret is measured against the true expected-payoff vectors, not the rounded replies: \[ \operatorname{SwapReg}_i(T)=\max_{\varphi:A_i\to A_i} \sum_{t=1}^T\sum_{a\in A_i}x_{ia}^t (v_i^t(\varphi(a))-v_i^t(a)). \] The identity map shows this benchmark is nonnegative. The comparator is a single fixed action-remapping function over the entire history.Question R3
Do there exist a deterministic horizon-independent uncoupled learner family and fixed polynomials $P,Q$ such that, for every such game, every player and every round $t$, its initialization and update use at most $P(N,K,L,\lceil\log_2(t+1)\rceil)$ bit operations and bits of working memory, all requested precisions and output coordinate bit lengths obey the same bound, and simultaneously \[ \sup_{T\geq1}\operatorname{SwapReg}_i(T)\leq Q(N,K,L)? \] All players use the family in self-play. No adversarial guarantee is imposed. A sharper optional goal is to preserve, up to an absolute constant factor and additive constant, the exact-arithmetic dimensional rate $O(\sqrt N\,K\log K\,\log^{5/2}(NK))$.Known result and the remaining implementation issue
Mai reports deterministic uncoupled constant swap regret at this dimensional scale under exact expected-payoff feedback. Appendix H explicitly excludes finite-bit complexity, inexact stationarity and floating-point guarantees from its exact-operation counts [mai]. That separation motivates R3; it does not prove that R3 is impossible or novel. A polynomial $Q$ is a weaker target than preservation of the reported sharp rate.An elementary check that is not a solution
For any fixed sequence $x^t$, replacing true payoff vectors by vectors with coordinate errors at most $\epsilon_t$ changes every remapping's cumulative gain by at most $2\sum_{t\leq T}\epsilon_t$; taking the maximum preserves that bound. Thus choosing $\epsilon_t\leq(t+1)^{-2}$ controls this particular evaluation error using only $O(\log(t+1))$ feedback bits. It does not control the effect of errors on future strategies, conditioning of stationary-distribution calculations, accumulated internal state, or exact rational normalization. Those are part of the question, not omitted steps of a claimed proof. No fixed-precision implementation has been tested.Catalogue relation
No exact we-solve target for this finite-bit swap-regret model was found.ECON-C73-63 concerns external regret with a fixed adversarial budget; ECON-C73-113 concerns Markov games. R3 does not alter or claim to solve either. Its precise model and polynomial resource bounds need expert assessment for open status and novelty.Preparation
The original research map was generated using OpenAI GPT 6 Astra Pro. Source checks, formulation, and LaTeX preparation used a Codex assistant based on GPT-6. Exact model versions and reasoning settings are unknown. The cited researchers retain credit for their results. Source statements and scope were checked; no complete proof audit or novelty certification is claimed.Origin of the questions.
The open-problem suggestions motivating this entry are credited to Rida Laraki's Facebook comment [laraki-facebook].References
- [mai] Tung Mai. Constant Swap Regret in General-Sum Games via Optimistic Transition Matrices. arXiv:2609.16751v1, September 2026. Abstract and main result; Appendix H, work, storage, and computation model. https://arxiv.org/html/2609.16751v1.
- [laraki-facebook] Rida Laraki. Facebook comment suggesting open problems in game theory.
Statement licence: CC-BY-4.0 · Source file
Contributions 1
Rational transition matrices, exact stationary distributions, and a summable-error transfer for constant swap regret
WS-107792: a finite-bit transfer for constant swap regret
OpenAI GPT 6 Astra Pro
18 October 2026
Problem
WS-107792 (live submission keyECON-3). Finite-bit uncoupled learning with constant swap regret. We-Solve problem page.Title
Rational transition matrices, exact stationary distributions, and a summable-error transfer for constant swap regret.Claim type
Full solution (affirmative), using the cited analytic estimates of Mai, version 2.Scope
We give a deterministic finite-bit learner and prove that it answers the exact catalogue question affirmatively, preserving its optional dimension rate up to an absolute constant. The proof controls the learner's actual self-play history, including accumulated feedback and state-rounding errors. It uses Mai's higher-order prediction estimates as cited results, and proves that they apply with the bounded initial-score perturbation needed by this construction. The proof supplies the numerical and memory bounds excluded from the cited exact-real implementation.Assumptions and limitations
The game, oracle, feedback restriction, regret benchmark, and resource requirements are exactly those in the attached statement. The proof counts oracle reply lengths and all subsequent bit operations, while the oracle's internal expectation calculation remains excluded as in the problem. All outputs and stored states are rational. No realized sampled-action guarantee, fixed-precision guarantee, or adversarial guarantee is asserted. The payoff bit bound $L$ is not needed by the construction beyond the problem's provision of the oracle.The principal literature input is Mai's version 2, whose title is Constant Swap Regret in General-Sum Games via Two-Scale Higher-Order Optimism. Version 1, cited in the question, has a different title. Both the model and the explicit finite-bit exclusion in Appendix H were checked in version 2 [mai]. The cited analytic estimates and their hypotheses are identified below; they are not independently reconstructed in full. This is a proposed mathematical proof using those results, with separate-agent checks of the new argument. It is not a formally verified proof or an externally refereed acceptance.
Write-up
1. Notation and a rational choice of public parameters
Write $n=N$ for the number of original players. Let \[ s_i=2^{\lceil\log_2\max\{2,m_i\}\rceil},\qquad s=\max_i s_i\leq2K. \] Replace each original action list by $s_i$ virtual actions, using duplicates of existing actions to fill the list. Fix a public surjection $p_i:[s_i]\to[m_i]$. The virtual game has payoffs \[ \widetilde u_i(a_1,\ldots,a_n) =u_i(p_1(a_1),\ldots,p_n(a_n)). \] If the virtual mixed strategy is $y_i$, the learner outputs $x_{ia}=\sum_{b:p_i(b)=a}y_{ib}$. The original payoff-vector reply, copied onto the virtual duplicates, is a reply for this virtual game at the same precision. No extra information is requested.For an original map $\varphi:[m_i]\to[m_i]$, choose for every original action a fixed virtual representative. Mapping each virtual action $b$ to the representative of $\varphi(p_i(b))$ gives a virtual remapping with exactly the original map's cumulative gain. Hence \begin{equation}\label{wsref-0-65-71-3a-70-61-64-64-69-6e-67} \operatorname{SwapReg}_i^{\mathrm{original}}(T) \leq\operatorname{SwapReg}_i^{\mathrm{virtual}}(T). \end{equation}
For the rest of the proof, $r_i^t$ denotes the true virtual gain matrix, \[ r_{i,a,b}^t=y_{i,a}^t (v_{i,b}^t-v_{i,a}^t),\qquad \left\lVert w_i\right\rVert_{\infty,1}=\sum_{a=1}^{s_i}\max_b|w_{i,a,b}|. \] Thus $\left\lVert r_i^t\right\rVert_{\infty,1}\leq1$ and \[ \operatorname{SwapReg}_i(T)=\sum_a\max_b\sum_{t\leq T}r_{i,a,b}^t\geq0. \]
Use Mai's public normalizer and predictor parameters, with all unqualified logarithms in their base-two convention: \[ M=\sum_i s_i^2,\quad A_i=s_i\log_2s_i,\quad A=\sum_iA_i, \quad\ell=\ell_0+\lceil\log_2(2+n+M)\rceil,\quad k=\ell+1, \] \[ \delta=\frac1{n(M+\ell+2)^2},\qquad J=\lceil\log_2(1/\delta)\rceil,\qquad \beta_i=\frac{\log_2s_i}{2^{10}s_iJ}. \] Let $d_i$ be the least power of two at least $\lceil\log_2(1/\beta_i)\rceil$. These parameters are rational or integer: this is the reason for the virtual-action padding. For later use, $M\geq s_i^2$ implies $\delta^{-1}=n(M+\ell+2)^2\geq s_i^4$, hence $J\geq4\log_2s_i$ and $s_i\beta_i\leq2^{-12}$. The base-two convention also appears in the source's identity $\ln m=(\ln2)\log m$ in its potential estimate.
Fix a sufficiently small positive rational universal $c$ and a sufficiently large universal integer $\ell_0$, as in the proof of Lemma Lemma (Robust history estimate from Mai's analytic lemmas) below. Put $g=c/k^{5/2}$ for the analysis only. Choose $\eta_i=2^{-h_i}$, where $h_i$ is the smallest nonnegative integer with \[ 2^{-2h_i}\leq\frac{c^2A_i}{k^5A}. \] This choice uses only integer comparisons after clearing denominators. It satisfies \begin{equation}\label{wsref-0-65-71-3a-72-61-74-65-73} \frac12g\sqrt{A_i/A}<\eta_i\leq g\sqrt{A_i/A}, \qquad\sum_i\eta_i^2\leq g^2. \end{equation} In particular $\eta_i^{-1}$ and all public parameter bit lengths are polynomially bounded in $n,K$. The universal constants can be fixed once and hardcoded. The question asks for the existence of fixed polynomials and does not require optimized numerical values of these universal constants. The proof of Mai's Theorem 2.1 explicitly treats arbitrary positive rates satisfying its equation $4.1$, $\sum_i\eta_i^2\leq g^2$. It therefore applies to these dyadic rates; the exact default square-root allocation is not required.
2. The exact analytic interface
For a row vector $z\in\mathbb R^{s_i}$, define \[ u(v)=\frac{\sqrt{v^2+4}-v}{2},\quad t_+(v)=u(v)^{-1},\quad f_i(v)=\beta_i \frac{(1+t_+(v)/d_i)^{d_i}} {1+u(v)+(\delta/4)u(v)^2}. \] There is a unique shift $\mu$ with $\sum_b f_i(z_b-\mu)=1$. Write $q_{i,b}(z)=f_i(z_b-\mu)$. Apply this map separately to every row of a score matrix $z_i$, producing a positive transition matrix $Q_i(z_i)$. Let $y_i(z_i)$ be its unique stationary distribution. The map $\Gamma_i(z)$ is the true gain matrix obtained in the fixed virtual game when all players use these stationary distributions.Let $\mathsf S$ denote backward shift on sequences with zero prehistory, $\mathsf D=I-\mathsf S$, and \[ \mathsf R_r=(I-\rho_r\mathsf S)^{-1},\qquad \mathsf F_r=\mathsf R_r\mathsf D,\qquad\rho_r=\frac r{r+1},\qquad \mathsf H=\mathsf D^3\mathsf F_\ell^\ell\mathsf F_M^M. \] The exact predictor is $(I-\mathsf H)r$. It uses only past gains because the current-input coefficient of $\mathsf H$ is one.
Prediction estimate and its history hypotheses.
For one normalized row at score $z$, define \[ H_b=f_i'(z_b-\mu),\qquad \sigma_b=\frac{H_b}{\sum_cH_c},\qquad \mathcal K_z(w)=\sum_bH_b \left(w_b-\sum_c\sigma_cw_c\right)^2. \] These are Mai's equation $4.2$, with $H_b$ denoting the source's curvature weight $h_b$ and $\mathcal K$ its row quadratic form. Define \[ S_i=\frac{\eta_i^2}{8}\sum_{t=1}^T\sum_a \mathcal K_{z_{i,a}^t}(r_{i,a}^t),\qquad \omega_i=C_\omega\frac{s_i-1}{\beta_i}, \] \[ Y^2=\sum_i\omega_iS_i,\quad V=\sum_i\omega_iA_i, \quad\Lambda^2=\sum_i\omega_i\eta_i^2,\quad E^2=\max_i\sum_{t=1}^T\left\lVert\xi_i^t\right\rVert_{\infty,1}^2. \] Here $\|w\|_{\infty,1;T}=(\sum_{t=1}^T\|w^t\|_{\infty,1}^2)^{1/2}$. The constant $C_\omega\geq1$ is the fixed universal curvature-comparison constant of the source's Appendix A.3. These definitions agree with Section 4 immediately after equation $4.2$ and before Lemma 4.1. Mai's Lemma 4.2, equation $4.4$, and its proof in Sections 4.3--4.7 and Appendices C--G give \begin{equation}\label{wsref-0-65-71-3a-70-72-65-64-69-63-74-69-6f-6e} E\leq C_0+C_1gE+\tau_\ell Y, \qquad\tau_\ell=C_Pk^2(C_Egk^{5/2})^\ell. \end{equation}The source states its implementation with zero initial scores. We verify that this restriction does not enter the cited prediction calculation. The proof uses (eq:scoreincrement) only when $t\geq2$. Section 4.4 assigns $t=1$ the boundary impulse $r_i^1$, whose row norm is at most one independently of $z^1$. Its later early expressions are gated by $t>p$, and its late expressions by $t>\ell+j$. More explicitly, differentiating a depth-$p$ early expression occurs only at $t\geq p+2$. Its lag indices are at most $p$, so every increment index $t-a$ is at least two. The late calculation has the identical property with $p=\ell+j$. The remaining first-time term is a bounded boundary observable. Thus no derivative identity involving an initial, nonpositive-time score is needed. The derivative estimates of Lemma C.1 and tree-score estimates of Lemma D.1 are uniform over all real score vectors. The late-window comparison in Lemma F.1 uses differences of $\Theta$, in which the fixed $b_i$ cancels. In particular its hull diameter remains at most $\eta_i(\ell+j+195)$, exactly as in that lemma.
The remaining entry of the perturbation into the prediction proof is \[ E\leq1+\max_i\left\lVert\mathsf H r_i\right\rVert_{\infty,1;T}, \] which follows from $\sum_{t=1}^T\left\lVert\varepsilon_i^t\right\rVert_{\infty,1}^2\leq \sum_{t\geq1}(t+1)^{-4}<1$. Its sign and computational origin do not occur in the estimate. Thus the same early and late one-difference closures, Lemmas 4.3 and 4.4, apply with the same constants. The same causal filter bounds in Lemma G.1 and the finite assembly in Appendix G.2 prove (eq:prediction) for the present history. This establishes the required extension of the cited analytic estimate; no history at time zero has been added as an extra assumption.
Potential estimate with the initial score.
Mai's row potential $\Phi_i$, defined in equation $4.7$ and analyzed in Lemma B.2, has gradient $q_i$, hence is 1-Lipschitz in the sup norm; it also satisfies $\Phi_i(z)\geq\max_bz_b$ and $\Phi_i(0)\leq2\log_2s_i$. The same one-round Taylor inequality as in the source has the same two displacements $\eta_i\xi_i^t$ and $\eta_i(\xi_i^t-r_i^t)$, including at $t=1$. Stationarity gives $\sum_{a,b}q_{i,a,b}^tr_{i,a,b}^t=0$ exactly. The two endpoint inequalities are now \[ \sum_a\Phi_i(\Theta_{i,a}^0) \leq2A_i+\eta_i\left\lVert b_i\right\rVert_{\infty,1},\qquad \sum_a\Phi_i(\Theta_{i,a}^T) \geq\eta_i\operatorname{SwapReg}_i(T)-\eta_i\left\lVert b_i\right\rVert_{\infty,1}. \] Consequently, \begin{equation}\label{wsref-0-65-71-3a-62-69-61-73-65-64-65-6e-65-72-67-79} \eta_i\operatorname{SwapReg}_i(T)+S_i \leq2A_i+2\eta_i\left\lVert b_i\right\rVert_{\infty,1}+\eta_i^2E^2. \end{equation} Because $A_i\geq2$, $\eta_i\leq1$, and $\left\lVert b_i\right\rVert_{\infty,1}\leq1/16$, this gives \[ Y^2\leq3V+\Lambda^2E^2,\qquad \Lambda^2\leq g^2V. \] For the last inequality, use $\Lambda^2\leq(\max_i\omega_i)\sum_i\eta_i^2\leq g^2V$. This is the general-rate inequality of Mai's Lemma 4.1, rather than the special identity available for the exact default allocation.Universal parameters and absorption.
Fix universal upper bounds for the analytic constants as in Appendix A.3. Choose a positive rational $c$ small enough that \[ C_Ec\leq\frac1{16},\qquad (C_1+1)c\leq\frac12,\qquad c^2[2(C_0+1)]^2\leq1, \] and small enough for the local potential comparisons in Section 4.2. These finitely many bounds depend only on the cited universal constants, not the game, dimensions, or horizon.The source's dimension estimates also justify the enlarged $3V$ budget uniformly when $\ell_0$ changes. Set $v=\lceil\log_2(2+n+M)\rceil$, so $k=\ell_0+v+1$. Appendix A.3 gives $J\leq5k$. The definitions show directly that \[ V=2^{10}C_\omega J\sum_i s_i^2(s_i-1) \leq2^{13}C_\omega kM^{3/2}. \] Use $M\leq2^v$, $k\leq(\ell_0+1)(v+1)$, and $C_Egk^{5/2}=C_Ec\leq1/16$ to obtain \begin{align*} \tau_\ell\sqrt{3V} &\leq C_P\sqrt{3\cdot2^{13}C_\omega} k^{5/2}16^{-\ell}M^{3/4}\\ &\leq C_P\sqrt{3\cdot2^{13}C_\omega} (\ell_0+1)^{5/2}16^{-\ell_0} (v+1)^{5/2}2^{-13v/4}. \end{align*} Here $v\geq3$ and $(v+1)^{5/2}2^{-13v/4}\leq1$. Choose one universal $\ell_0$ large enough that \[ C_P\sqrt{3\cdot2^{13}C_\omega} (\ell_0+1)^{5/2}16^{-\ell_0}\leq1. \] Such an integer exists because the exponential factor dominates the fixed power of $\ell_0+1$. This proves $\tau_\ell\sqrt{3V}\leq1$, with all the parameters recomputed from this single choice of $\ell_0$.
Dyadic rounding of the rates makes no change to $V$, since $V$ depends on $\beta_i,A_i$ and $C_\omega$, not on the rates. It preserves $\sum_i\eta_i^2\leq g^2$ and $\eta_{\max}\leq g$. Consequently there is no factor-four enlargement of the curvature budget from that rounding; its factor-two loss occurs only in the final bound on $1/\eta_i$ in (eq:rates).
Finally, \[ Y\leq\sqrt{3V}+\Lambda E\leq\sqrt{3V}+g\sqrt V E, \qquad\tau_\ell Y\leq1+gE. \] Together with (eq:prediction), this gives \[ E\leq C_0+1+(C_1+1)gE\leq C_0+1+E/2, \qquad E\leq E_0:=2(C_0+1). \] The choice of $c$ implies $\eta_i^2E_0^2\leq1\leq A_i$. Substituting into (eq:biasedenergy), and using $2\eta_i\left\lVert b_i\right\rVert_{\infty,1}\leq A_i$, proves $\eta_i\operatorname{SwapReg}_i(T)\leq4A_i$. This is (eq:inputconclusion) for the arbitrary chosen horizon. ∎
3. A rational normalizer with a small effective-score error
For $|v|\leq R$, $1/(R+1)\leq u(v),t_+(v)\leq R+1$. The numerator in $f_i$ is at least $\beta$, and its denominator is at most $3(R+1)^2$. Hence \[ f_i(v)\geq\frac\beta{3(R+1)^2}. \] The logarithmic derivative of the numerator is \[ \frac{du}{(1+u^2)(1+du)}\geq\frac1{4(R+1)^4}. \] The negative logarithmic derivative of the denominator is nonnegative, so \begin{equation}\label{wsref-0-65-71-3a-64-65-72-69-76-61-74-69-76-65-66-6c-6f-6f-72} f_i'(v)\geq a_R:=\frac\beta{12(R+1)^6}. \end{equation} These deliberately conservative lower bounds are enough: their logarithms grow only as $O(\log R+\log(1/\beta))$.
The function $f_i$ is composed of rational arithmetic, a square root, and an integer power $d$. On this interval every intermediate magnitude and reciprocal of a positive denominator has logarithm polynomial in $d,\log R,\log(1/\beta)$ and the input bit lengths. For a direct certified implementation, bracket $\sqrt{v^2+4}$ by rational bisection and evaluate the remaining expressions by rational interval arithmetic. One may use $t_+(v)=1/u(v)$ when this avoids a subtraction of close values. The positive denominators stay bounded away from zero by the displayed estimates. Repeated squaring or $d$ multiplications therefore evaluates $f_i$ to error $2^{-p}$ in a number of bit operations polynomial in these quantities and $p$.
Certified bisection for the row sum locates its root to any prescribed absolute error. A nearly equal comparison does not require an equality oracle: if an evaluation interval of width $2e$ contains one, the derivative bound $|\sum_bf_i'(z_b-\mu)|\geq ma_R$ locates the root within $2e/(ma_R)$ of that midpoint. Otherwise the interval certifies which half to retain. The row sum also has an upper derivative bound with polynomial logarithm. Indeed $0<t_+'(v)\leq1$ and $|u'(v)|\leq1$; the logarithmic derivative of the numerator is at most one and the negative logarithmic derivative of the denominator is at most one. Hence $f_i'(v)\leq2f_i(v)\leq2\beta(R+2)^d$, and the row-sum derivative is at most $2m\beta(R+2)^d$. This procedure computes approximations to the exact probability row $q^*=q_i(z)$ with any prescribed absolute coordinate error, at the claimed cost.
Compute positive dyadics $p_b$ with $|p_b-q_b^*|\leq e$ and put $\widehat q_b=p_b/\sum_cp_c$. If \[ e\leq\min\left\{\frac1{2m},\ \frac{\beta}{12(R+1)^2},\ \frac{a_R\tau}{8(m+1)}\right\}, \] all coordinates are positive, the row is exactly normalized, and \[ |\widehat q_b-q_b^*|\leq2(m+1)e\leq a_R\tau/4. \] By (eq:derivativefloor), $f_i$ changes by at least $a_R\tau$ on either length-$\tau$ side of the exact scalar argument. Monotonicity therefore gives \[ \zeta_b=f_i^{-1}(\widehat q_b)-(z_b-\mu),\qquad |\zeta_b|\leq\tau. \] Now $\widehat q_b=f_i(z_b+\zeta_b-\mu)$ and its coordinates sum to one. Uniqueness of the normalizing shift proves the representation. The inverse function and $\zeta$ are not computed. All requested accuracies have logarithm polynomial in the stated inputs, completing the bit-complexity argument. ∎
4. Exact rational stationarity has polynomial bit cost
This lemma is applied to a freshly formed rational $Q$ in each round. Its denominators are never accumulated into future gain sums; those gains are rounded to a common dyadic grid as follows.
5. The finite-bit learner
Set $D=M+\ell$ and $B_*=10(D+1)^3$. Choose an integer $b_0$ with \begin{equation}\label{wsref-0-65-71-3a-62-30} 2^{-b_0}\leq\frac1{4096s(D+1)B_*^D}, \qquad b_0=O(D\log(D+1)+\log s), \end{equation} and put \[ b_t=b_0+4\lceil\log_2(t+1)\rceil,\qquad h_t=2^{-b_t}. \] Then $h_t\leq 2^{-b_0}(t+1)^{-4}$ and $b_t$ is nondecreasing.For each player maintain a cumulative gain matrix $C$, initially zero, and the $D$ EMA state matrices $a_1,\ldots,a_D$ and three lag matrices $c_1,c_2,c_3$, also initially zero. Let $\nu_j=1/(M+1)$ for $j\leq M$, and $\nu_j=1/(\ell+1)$ for $j>M$. At round $t$ perform:
- Compute the rational predictor \[ \widetilde h=\sum_{j=1}^Da_j+3c_1-3c_2+c_3, \qquad\overline z=\eta_i(C+\widetilde h). \]
- For each row of $\overline z$, use Lemma Lemma with $\tau=\eta_i/[4s_i(t+1)^2]$. Form the positive rational transition matrix $Q_i$ and compute its stationary distribution $y_i$ exactly using Lemma Lemma. Output the aggregated original-action distribution $x_i$.
- Request the original payoff vector at precision $b_t$ and copy its coordinates to virtual actions. Call the reply $\widetilde v_i$. Set $\widetilde r_{a,b}$ to the nearest multiple of $2^{-b_t}$ to $y_{i,a}(\widetilde v_{i,b}-\widetilde v_{i,a})$, using any fixed tie convention.
- Update $C\leftarrow C+\widetilde r$ exactly, and set $u\leftarrow\widetilde r$. Sequentially for $j=1,\ldots,D$, set \[ u\leftarrow u-a_j,\qquad a_j\leftarrow\operatorname{round}_{b_t}(a_j+\nu_j u). \] The subtraction for $u$ is exact and uses the old $a_j$. Finally update $(c_3,c_2,c_1)\leftarrow(c_2,c_1,u)$ simultaneously.
6. Rounding errors in the actual history
Let $r_i^t$ be the true gains of the strategies actually played by this finite-bit learner, not the gains of an ideal comparison run. Write $d_i^t=\widetilde r_i^t-r_i^t$. Oracle approximation and final gain rounding give \begin{equation}\label{wsref-0-65-71-3a-67-61-69-6e-65-72-72-6f-72} \left\lVert d_i^t\right\rVert_{\infty,1}\leq3s_i h_t. \end{equation} Indeed the payoff difference contributes at most $2y_{i,a}h_t$ in row $a$ and gain rounding contributes at most $h_t$ per row; summing yields $(2+s_i)h_t\leq3s_i h_t$. If $e_{i,j}^t$ denotes the rounding error in EMA update $j$, then \begin{equation}\label{wsref-0-65-71-3a-65-6d-61-65-72-72-6f-72} \left\lVert e_{i,j}^t\right\rVert_{\infty,1}\leq s_i h_t. \end{equation}We now control the feedback of these errors into all later strategies. For a scalar convolution kernel $K=\sum_{q\geq0}k_q\mathsf S^q$, define \[ \left\lVert K\right\rVert_w=\sum_{q\geq0}(q+1)^2|k_q|, \qquad\left\lVert w\right\rVert_{*,2}=\sup_{t\geq1}(t+1)^2\left\lVert w^t\right\rVert_{\infty,1}. \] The inequality $t+1\leq(q+1)(t-q+1)$ gives \begin{equation}\label{wsref-0-65-71-3a-77-65-69-67-68-74-65-64-66-69-6c-74-65-72} \left\lVert Kw\right\rVert_{*,2}\leq\left\lVert K\right\rVert_w\left\lVert w\right\rVert_{*,2}. \end{equation} The same weight inequality makes these kernel norms submultiplicative.
For every stage, let $R_j=(I-(1-\nu_j)\mathsf S)^{-1}$ and $F_j=R_j\mathsf D$. Direct sums of the geometric kernel give \[ \left\lVert R_j\right\rVert_w\leq2(D+1)^3,\qquad \left\lVert F_j\right\rVert_w\leq B_*,\qquad \left\lVert\mathsf S\right\rVert_w=4,\qquad\left\lVert\mathsf D^3\right\rVert_w=56. \] For example $\sum_{q\geq0}(q+1)^2\rho^q =(1+\rho)/(1-\rho)^3$, and $\left\lVert I-\mathsf S\right\rVert_w=5$. It follows that \begin{equation}\label{wsref-0-65-71-3a-6b-65-72-6e-65-6c-62-6f-75-6e-64-73} \left\lVert I-\mathsf H\right\rVert_w\leq57B_*^D, \qquad \left\lVert\mathsf D^3\prod_{h>j}F_h\mathsf S R_j\right\rVert_w \leq56B_*^D. \end{equation}
Let $U_j^t$ be the residual $u$ after stage $j$ in round $t$, with $U_0=\widetilde r$. The exact algebra of the rounded update is \[ U_j=F_jU_{j-1}-\mathsf S R_je_j. \] The stage telescoping identity and the three stored lags therefore give the following exact predictor identity: \begin{align} \widetilde h_i&=(I-\mathsf H)r_i+\pi_i,\label{wsref-0-65-71-3a-70-72-65-64-69-63-74-6f-72-65-72-72-6f-72}\\ \pi_i&=(I-\mathsf H)d_i+ \mathsf D^3\sum_{j=1}^D\left(\prod_{h>j}F_h\right)\mathsf S R_je_{i,j}. \label{wsref-0-65-71-3a-70-69-65-78-61-63-74} \end{align} This calculation includes errors from every stage and every earlier round. In particular it does not identify the implemented trajectory with an unrounded trajectory.
By (eq:gainerror)--(eq:kernelbounds), \[ \left\lVert\pi_i\right\rVert_{*,2} \leq s_i(171+56D)B_*^D2^{-b_0}<\frac14. \] Also the infinite sum \[ b_i=\sum_{t=1}^\infty d_i^t \] converges absolutely, and (eq:b0) gives $\left\lVert b_i\right\rVert_{\infty,1}\leq1/16$. Its tail satisfies \[ \left\lVert\sum_{q=t}^\infty d_i^q\right\rVert_{\infty,1} \leq s_i2^{-b_0}t^{-3} \leq\frac1{4(t+1)^2}. \] Here $\sum_{q=t}^\infty(q+1)^{-4}\leq1/(3t^3)$ and $(t+1)^2/t^3\leq4$ for $t\geq1$.
The rational normalizer supplies an effective score perturbation $\zeta_i^t$ with $\left\lVert\zeta_i^t\right\rVert_{\infty,1}/\eta_i\leq1/[4(t+1)^2]$. Since $C_i^{t-1}=\sum_{q<t}(r_i^q+d_i^q)$, its actual effective score is \[ z_i^t=\eta_i\left(b_i+\sum_{q<t}r_i^q +(I-\mathsf H)r_i^t+\varepsilon_i^t\right), \] where \[ \varepsilon_i^t= -\sum_{q=t}^\infty d_i^q+\pi_i^t+\frac{\zeta_i^t}{\eta_i}, \qquad\left\lVert\varepsilon_i^t\right\rVert_{\infty,1}\leq\frac3{4(t+1)^2}. \] Exact rational stationarity and the fixed virtual game give $r_i^t=\Gamma_i(z^t)$. These are precisely the hypotheses of Lemma Lemma (Robust history estimate from Mai's analytic lemmas).
The infinite error sum $b_i$ is only a device of the proof. The learner does not compute it, store it, or use future replies. Existence of the infinite run follows inductively from the finite, well-defined algorithm at each round. Deterministic pathwise inequalities can then use the absolutely convergent error sum of that run without any causal restriction on this analysis-only constant.
7. Resource accounting and the regret conclusion
For resources, $D=O(NK^2+\log(NK))$ and $b_t=O(D\log(D+1)+\log(t+1))$. The dyadic grid is nondecreasing. Hence the exact cumulative gain array $C$ has denominator dividing $2^{b_t}$, with integer part $O(t)$: its bit length is $O(b_t+\log(t+1))$, rather than a sum of all earlier precisions. All EMA states and lag states are dyadics on this grid. A crude stable-filter bound using $\left\lVert F_j\right\rVert_{\mathrm{ker},1}\leq2$ bounds their magnitudes by $2^{O(D)}$ times a polynomial in $D$; thus their integer parts require only $O(D+\log(D+1))$ bits. The rounding errors obey the same stable linear recurrence, so the bound applies to the implemented states. There are $O(Ds_i^2)$ such entries.
The raw score magnitude is at most $O(t+2^{O(D)})$, so the logarithm of $R$ in Lemma Lemma is $O(D+\log(t+1)+\log(NK))$. Its tolerance obeys \[ \log(1/\tau)=O(\log(1/\eta_i)+\log s_i+\log(t+1)), \] which has the required polynomial bound. Consequently each fresh transition row has a polynomial bit bound, and the exact stationary system has a polynomial bit cost and output size by Lemma Lemma. Aggregating virtual coordinates can use their common Cramer denominator, so it preserves a polynomial output size and exact normalization.
The stationary distribution may have a different denominator in the next round. This causes no growth across time: products involving it are rounded to the common dyadic grid before being added to $C$ or passed to the EMA cascade. Each temporary multiplication, division, and rounding therefore has polynomial operand length. The $ s_i^2D$ EMA operations and one own-payoff oracle query also have polynomial bit cost and memory. A single fixed polynomial can dominate this finite composition of polynomial bounds, including public initialization. No part of the algorithm enumerates the game's payoff table or stores past payoff vectors. ∎
8. Self-audit and verification status
The proved numerical statements handle four separate issues: positive rational row normalization at a small effective score; exact rational stationarity with polynomial bit length; bounded storage for cumulative gains; and the effect of all feedback and EMA errors on the future score history. The last issue is handled by (eq:piexact) and the fixed-bias plus tail identity, not by a bound on regret evaluation along an unchanged history.The history extension was checked separately against the source's first-time impulses, early and late time gates, score-window comparison, and potential endpoints. Lemma Lemma (Robust history estimate from Mai's analytic lemmas) records that extension as a proof using the cited analytic results, with the energies, equation locators, and universal parameter bounds specified. The rate rounding preserves the general-rate hypotheses; it does not silently use an identity restricted to the exact default allocation. All scalar inverse bounds are polynomial in the score range, and the stationary-distribution denominators are prevented from accumulating in future states by dyadic gain rounding.
The argument applies to every finite prefix of the same horizon-independent run. A one-action player is covered by virtual duplicates and has zero original swap regret. Positivity and exact normalization hold before every stationary solve. Regret throughout the proof uses true expected gains of the implemented strategies. These checks leave no identified gap in the new transfer proof.
The exact-real learning algorithm and its higher-order analytic estimates remain credited to Mai. This contribution uses those estimates as cited mathematical results; it is not an independent reconstruction of their entire proof. Separate-agent review of a proposed proof is not formal verification or external peer review. No finite-precision learning implementation has been run, and no numerical benchmark or experimental verification is claimed.
Models used
OpenAI GPT-6 Astra Pro (system-reported model name; exact dated snapshot unknown): source inspection, proof construction, and adversarial self-review. Separate agents checked the bounded-initial-score extension and the numerical transfer, including resource accounting; a coordinating agent reviewed the completed argument. These were model-based checks, not human or formal verification.Human contributors and roles
The user specified the problem and requested attempted solutions. No human proof verification is claimed. Tung Mai retains credit for the exact-arithmetic algorithm and analytic estimates used here. The question's originating research discussion credits Rida Laraki; this statement does not attribute the present numerical construction to him.References
- [mai] Tung Mai. Constant Swap Regret in General-Sum Games via Two-Scale Higher-Order Optimism. arXiv:2609.16751v2, revised 19 September 2026. Sections 2--4; Appendix A.2--A.3; Lemmas 4.1--4.2, F.1 and G.1; Appendix H. https://arxiv.org/html/2609.16751v2.
- [statement] We-Solve. Finite-bit uncoupled learning with constant swap regret, WS-107792, live submission key
ECON-3. Attached statement dated 17 October 2026; live research prompt retrieved 18 October 2026. https://we-solve.github.io/problems/finite-bit-uncoupled-learning-with-constant-swap-regret/.