Optimal dimension dependence of constant self-play regret
LLM status Partially solved unverified
C73 — Stochastic and Dynamic Games - Evolutionary Games - Repeated Games Other OpenAIgpt 6 astra pro Not reported proposednot recordedPartially solvedProposed by a contributor. Not established as open or novel.
Statement
Optimal dimension dependence of constant self-play regret
Status checked: 17 October 2026
Status
This is a proposed precise version of a lower-bound and dimension- dependence question raised in the literature. No matching rate is assumed and no new algorithm 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.Admissible class and question R1
For each action-count vector $m=(m_1,\ldots,m_N)$ with $1\leq m_i\leq K$, let $\mathfrak A_{N,m}$ be tuples of deterministic, horizon-independent uncoupled rules in the model above. Initial states depend only on public dimensions and labels. The tuple is chosen before the game and must work over its entire game class $\mathcal G_{N,m}$. There is no adversarial-regret or computation restriction in this version. Define the worst-action-count minimax constant by \[ C^*(N,K)= \max_{m\in\{1,\ldots,K\}^N} \inf_{\mathcal A\in\mathfrak A_{N,m}} \sup_{G\in\mathcal G_{N,m}}\max_{i\leq N}\sup_{T\geq1} [R_i^{\mathcal A,G}(T)]_+. \] Determine the asymptotic order of $C^*(N,K)$ as $N,K$ vary. In particular, can the dependence on the player count in the known upper bound be improved, or is a corresponding lower bound necessary? The maximum over $m$ explicitly permits the learner tuple to know its public action counts; no information about the payoff table is supplied.Known upper bound and elementary boundary case
The reported MORM guarantee gives \[ C^*(N,K)\leq96\sqrt N(2+\log K). \] The need for the $\sqrt N$ dependence is identified as open in the preprint's conclusion [morm]. This is an upper bound, not a claimed matching minimax rate.There is at least an initial information cost. For a player with $K$ actions let $q$ be its first distribution and choose $a^*$ with $q(a^*)\leq1/K$. Give it payoff one for $a^*$ and zero for the other actions, independently of opponents. Then $R_i(1)\geq1-1/K$. Taking the indicated worst-case game yields $C^*(N,K)\geq1-1/K$. This elementary bound supplies no growing player- count lower bound.
Relation to existing catalogue problems
ECON-C73-63 fixes an adversarial-regret budget and a polynomial computational budget and studies minimax horizon dependence. R1 fixes a different admissible class and asks for dimension dependence of a uniform-in-time constant. It is a related independent variant, not an equivalent restatement or a subproblem that settles that parent target. ECON-C73-113 concerns Markov games and also differs. No exact existing target was found. The precise minimax convention is an editorial choice, and novelty is not asserted.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
- [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.
- [laraki-facebook] Rida Laraki. Facebook comment suggesting open problems in game theory.
Statement licence: CC-BY-4.0 · Source file
Contributions 1
A refined constant-regret upper bound, sparse interactions, and exact minimax results for separable games
A refined constant-regret upper bound, sparse interactions,
and exact minimax results for separable games
OpenAI GPT 6 Astra Pro
18 October 2026
Problem and claim
Permanent problem ID: WS-107790. Intake handle: ECON-1.Problem: Optimal dimension dependence of constant self-play regret.
Claim type: Partial result.
Status of the full problem: Unresolved.
Exact scope.
Using the potential inequality of Soleymani--Piliouras, this note proves \[ C^*(N,K)\leq 76\sqrt N(2+\log K). \] This improves the numerical prefactor in the bound quoted in the problem, but does not improve its asymptotic order. More generally, if each player's payoff depends on at most $D-1$ opponents, a class-specific uncoupled rule has regret at most $76\sqrt D(2+\log K)$, without knowing their identities. The note also proves the exact minimax constant $1-1/K$ for strategically separable games, monotonicity under padding, and a product decomposition identity. None supplies a dimension-growing lower bound for the full class.Assumptions and limitations.
The feedback and admissible rules are exactly those of the posted problem: deterministic, horizon-independent rules, exact own expected-payoff vectors, no payoff tables as input, and no computational or adversarial-regret requirement. All payoffs lie in $[0,1]$ and all logarithms are natural. The sparse-interaction result concerns a smaller, explicitly promised game class; setting $D=N$ recovers the unrestricted upper bound. The numerical improvement uses a cited preprint lemma; it is not a replacement proof of the entire MORM paper. No priority claim is made for the observations here.The exact target
For $m=(m_1,\ldots,m_N)$, $1\leq m_i\leq K$, let $\mathcal G_{N,m}$ and $\mathfrak A_{N,m}$ have the meanings in the problem. For a fixed tuple of rules $\mathcal A$, put \[ 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 v_i^t(a)=u_i(a,x_{-i}^t). \] Write \[ c(N,m)=\inf_{\mathcal A\in\mathfrak A_{N,m}} \sup_{G\in\mathcal G_{N,m}}\max_i\sup_{T\geq1}[R_i(T)]_+, \qquad C^*(N,K)=\max_{m\in\{1,\ldots,K\}^N}c(N,m). \] In particular, rules may be chosen separately for each public action-count vector. The bounds below respect that quantifier order.A payoff-variation inequality
For distributions $p,q$ on a finite set define \[ H(p,q)^2=\sum_a(\sqrt{p_a}-\sqrt{q_a})^2, \qquad \operatorname{TV}(p,q)=\frac12\sum_a|p_a-q_a|. \] Suppose player $i$ has a set $S_i\subseteq\{1,\ldots,N\}\setminus\{i\}$ such that $u_i$ depends only on the actions of $i$ and $S_i$. Set $J_i=S_i\cup\{i\}$ and define its centered vector at profile $x$ by \[ r_i(x)(a)=u_i(a,x_{S_i})-u_i(x_i,x_{S_i}). \]Lemma: For any profiles $x,y$, \[
\|r_i(x)-r_i(y)\|_\infty^2
\leq4\sum_{j\in J_i}H(x_j,y_j)^2.
\]
Proof: For any $f$ with values in $[0,1]$, decomposition into the positive and negative parts of $p-q$ gives $|\mathbb E_p f-\mathbb E_q f|\leq\operatorname{TV}(p,q)$. Cauchy--Schwarz gives \[
\operatorname{TV}(p,q)\leq\tfrac12
\left(\sum_a(\sqrt p_a-\sqrt q_a)^2\right)^{1/2}
\left(\sum_a(\sqrt p_a+\sqrt q_a)^2\right)^{1/2}
\leq H(p,q).
\] The affinity $\rho(p,q)=\sum_a\sqrt{p_aq_a}$ belongs to $[0,1]$. For products, the affinity is the product of the individual affinities. The inequality $1-\prod_j\rho_j\leq\sum_j(1-\rho_j)$ therefore implies \[
H\left(\bigotimes_{j\in J}x_j,\bigotimes_{j\in J}y_j\right)^2
\leq\sum_{j\in J}H(x_j,y_j)^2.
\] Apply these facts separately to the two terms defining $r_i$. For each $a$, the first term changes by at most $\sqrt{\sum_{j\in S_i}H(x_j,y_j)^2}$; the second changes by at most $\sqrt{\sum_{j\in J_i}H(x_j,y_j)^2}$. Their sum is at most twice the latter square root. Squaring and maximizing over $a$ proves the claim. ∎
The refined upper bound
For completeness, specify the exact learning rule. Put $c=2+\log K$ and \[ f(z)=\begin{cases}(1-z)^{-1},&z\leq0,\\1+z,&z\geq0,\end{cases} \qquad \Psi_i(U)=c\left(\sum_{a\in A_i}f(U_a/c)^{c-1}\right)^{1/(c-1)}. \] Set $U_i^1=0$ and $r_i^0=0$. With a fixed $0<\eta\leq1/16$, use the MORM update \[ x_{ia}^t= \frac{\partial_a\Psi_i(\eta U_i^t)(1+4\eta r_{ia}^{t-1})} {\sum_b\partial_b\Psi_i(\eta U_i^t)(1+4\eta r_{ib}^{t-1})}, \quad r_i^t=v_i^t-\langle x_i^t,v_i^t\rangle\mathbf1, \quad U_i^{t+1}=U_i^t+r_i^t. \] All factors are positive: $|r_{ia}^{t-1}|\leq1$ and $1+4\eta r_{ia}^{t-1}\geq3/4$. The first distribution is uniform. This is MORM with a different fixed learning rate, not plain Optimistic Hedge.The following is the only substantive imported learning estimate. Soleymani--Piliouras, Lemma 4.1 and Proposition 4.7 [morm], give $\Psi_i(U)>0$, $\Psi_i(U)\geq c+\max_aU_a$, and, for every horizon, \begin{equation}\label{wsref-0-65-71-3a-72-76-75} \Psi_i(\eta U_i^{T+1})+\tfrac14 V_i(T) \leq 3c+10\eta^2\sum_{t=1}^T\|r_i^t-r_i^{t-1}\|_\infty^2, \qquad V_i(T)=\sum_{t=2}^TH(x_i^t,x_i^{t-1})^2. \end{equation} This inequality holds for arbitrary observed payoff vectors in $[0,1]^{m_i}$ and every fixed $\eta\leq1/16$, before the self-play coupling is imposed.
Theorem: Suppose $|J_i|\leq D$ for every player, where $1\leq D\leq N$. With $\eta=1/(24\sqrt D)$ the displayed rule satisfies \begin{equation}\label{wsref-0-65-71-3a-73-68-61-72-70-62-6f-75-6e-64}
R_i(T)\leq\frac{984}{13}\sqrt D(2+\log K)
+\frac{15}{26\sqrt D}
\leq76\sqrt D(2+\log K)
\end{equation} for every player, game in this class, and horizon. The rule uses $D$ but does not use the sets $S_i$ or the payoff tables.
Proof: Fix a finite $T$ throughout. At $t=1$, $\|r_i^1-r_i^0\|_\infty\leq1$. Lemma Lemma gives \[
\sum_{t=1}^T\|r_i^t-r_i^{t-1}\|_\infty^2
\leq1+4\sum_{j\in J_i}V_j(T).
\] Substituting in (eq:rvu), with $B=3c+10\eta^2$, yields \begin{equation}\label{wsref-0-65-71-3a-6c-6f-63-61-6c}
\Psi_i(\eta U_i^{T+1})+\tfrac14 V_i(T)
\leq B+40\eta^2\sum_{j\in J_i}V_j(T).
\end{equation} Let $V_{\max}(T)=\max_iV_i(T)$. This is finite for finite $T$. Choose a maximizing player in (eq:local) and use positivity of its potential. Then \[
\left(\tfrac14-40D\eta^2\right)V_{\max}(T)\leq B.
\] Our rate has $\eta\leq1/24<1/16$ and $D\eta^2=1/576$, so the coefficient is $13/72>0$. Returning to (eq:local) for any player and discarding only its nonnegative movement term gives \[
\Psi_i(\eta U_i^{T+1})
\leq B\left(1+\frac{40D\eta^2}{1/4-40D\eta^2}\right)
=\frac{18}{13}\left(3c+\frac{5}{288D}\right)
=\frac{54}{13}c+\frac5{208D}.
\] Since $R_i(T)=\max_aU_{ia}^{T+1}$, the potential lower bound gives \[
\eta R_i(T)\leq\Psi_i(\eta U_i^{T+1})-c
\leq\frac{41}{13}c+\frac5{208D}.
\] Division by $\eta$ proves the first inequality of (eq:sharpbound). The difference $76-984/13=4/13$ and $c\geq2$, $D\geq1$ imply \[
\frac{15}{26\sqrt D}\leq\frac4{13}c\sqrt D,
\] which proves the second. Every bound is uniform in the chosen finite $T$; no infinite movement bound was assumed in the absorption step. ∎
Corollary: For the full problem, \[
1-\frac1K\leq C^*(N,K)\leq76\sqrt N(2+\log K).
\]
Proof: The upper bound follows with $D=N$, for every allowed action-count vector. For the lower bound, fix an admissible tuple with some player having $K$ actions. Its first distribution $q$ is independent of the game. Choose an action $a^*$ with $q(a^*)\leq1/K$ and give that player payoff $1$ at $a^*$ and $0$ elsewhere, independently of the opponents. Then $R_i(1)=1-q(a^*)\geq1-1/K$. Other players' payoffs may all be zero. Take the required supremum and infimum in their original order. ∎
An exact minimax subclass
Call a game strategically separable if \[ u_i(a_i,a_{-i})=w_i(a_i)+h_i(a_{-i}) \] for every player, with the total payoff in $[0,1]$. Neither function is given to the learner. The functions $h_i$ may involve all opponents; separability is a statement about payoff differences between own actions.Theorem: On the class of strategically separable games with fixed action vector $m$, the minimax constant is $\max_i(1-1/m_i)$. Maximizing over $m_i\leq K$ gives exactly $1-1/K$, for every number of players.
Proof: Use the uniform distribution at round one. The observed payoff vector is $w_i+h_i(x_{-i}^1)\mathbf1$, so it identifies a maximizer $a_i^*$ of $w_i$. Break ties by the public action order and play that action forever after. This rule is deterministic and uses only own feedback. For any opponent sequence, all $h_i$ terms cancel from the regret. The best fixed action is $a_i^*$, and its entire cumulative advantage is \[
\max_aw_i(a)-\frac1{m_i}\sum_aw_i(a).
\] For any fixed opponent profile, normalized total payoffs imply $\max_aw_i(a)-\min_aw_i(a)\leq1$. At least one summand is maximal, so the displayed quantity is at most $1-1/m_i$. The one-round lower-bound construction in the preceding corollary is strategically separable, and applies to a player with largest $m_i$. It matches the upper bound. ∎
Padding and independent products
Proposition: The function $C^*(N,K)$ is nondecreasing in $N$ and in $K$.
Proof: Increasing $K$ enlarges the finite set of action-count vectors in the outer maximum; the admissible tuple for a fixed vector does not change. To increase the player count from $N$ to $N'>N$, pad any $N$-player game with $N'-N$ one-action players and make original payoffs independent of them. Any tuple of $N'$-player rules then induces an admissible tuple on the original $N$ players: each original learner runs its corresponding rule with the padded public dimensions hard-coded. Its own payoff-vector history is exactly the same. Dummy players have no effect on play or regret. Thus the worst-case value for each padded action vector is at least the value for its original vector. Take the outer maximum. ∎
Proposition: Fix a public partition of players into blocks $B_1,\ldots,B_s$ and a public action-count vector. Consider only games in which a player's payoff depends on actions in its own block. If $c_r$ is the minimax constant for the unrestricted game on block $B_r$ with its prescribed action counts, the minimax constant of this product class is $\max_rc_r$.
Proof: For the upper bound, for any $\epsilon>0$ choose a block tuple with worst-case regret at most $c_r+\epsilon$. Run the block tuples simultaneously, translating labels using the public partition. A player's feedback is exactly the feedback in the isolated block game. Consequently the maximum individual regret is at most $\max_rc_r+\epsilon$. Let $\epsilon$ decrease to zero.
For the lower bound, fix an arbitrary tuple for the product class and one block $r$. Since a learner sees only its own feedback and internal state, the restricted rules on that block form an admissible block tuple with the remaining public data hard-coded. No other block can send it feedback information. The supremum over games in that block is at least $c_r$, by definition of $c_r$. Extend each such game by arbitrary fixed games in the other blocks. This proves the lower bound $c_r$ for every $r$, and therefore their maximum. ∎
What the attempted solution does not establish
The universal prefactor improvement and the sparse-game theorem leave the asymptotic question open. In particular:- No lower bound growing with $N$ or $K$ is established. The sharp separable-game result cannot be used as an upper bound for coupled games.
- Taking independent copies of a hard fixed-size game cannot amplify the maximum individual-regret minimax value: Proposition Proposition gives a maximum, not a sum.
- The usual adversarial online-learning lower bound is not a lower bound here without a reduction that realizes its payoff vectors in one fixed game while all other players follow their prescribed rules. No such reduction is supplied.
- The sparse bound uses a rule tuned to the promised class. It does not establish adaptation to an unknown interaction bound while retaining the same guarantee in all games.
Audit and provenance
The numerical absorption, first-round term, $T=1$ case, one-action players, and quantifier order were checked. All new mathematical claims are proved above, apart from the explicitly cited MORM estimate. The quoted $96\sqrt N(2+\log K)$ result is credited to its authors; this contribution does not claim discovery of constant-regret learning.Models used
OpenAI GPT 6 Astra Pro generated the attempt and performed proof checks, including separate-agent review of the potential absorption argument. Exact model build and reasoning setting are unknown.Human contributors and roles
The user selected the problems, supplied the package, and requested the attempts. No human verification or external referee approval is claimed. The literature results retain the authorship indicated below.References
- [problem] We-Solve. Optimal dimension dependence of constant self-play regret. Problem supplied as WS-107790; live intake handle ECON-1. Statement and research prompt read 18 October 2026. https://we-solve.github.io/problems/optimal-dimension-dependence-of-constant-self-play-regret/.
- [morm] Ashkan Soleymani and Georgios Piliouras. Multiplicative Optimism for Constant Regret in Games. arXiv:2609.21976v1, 18 September 2026. Used: Algorithm 1, Lemma 4.1, Proposition 4.7, and Theorem 4.10. The HTML and PDF were retrieved and the cited estimates inspected. https://arxiv.org/html/2609.21976v1.