we-solve (beta)

Econ-115 · economics · computer science · Computational economics

Constant regret in general-sum Markov games

LLM status Open unverified

Statement

GT-021 | Learning in games

R | Precise formulation of a source research agenda; source-date open

Definitions and mathematical statement

A finite episodic Markov game has players $N=\{1,\ldots,n\}$, states $S$, nonempty finite action sets $A_i$, horizon $H\geq1$, initial state $s_1$, transition kernels $P_h(\cdot\mid s,a)$, and rewards $r_{i,h}(s,a)\in[0,1]$. All realized states and actions are observed. A behavioral policy assigns an action distribution to each player-observed history within an episode; $\Pi_i$ denotes this set. For a profile $\pi$, put \[ V_i(\pi)=\mathbb E_{\pi}\!\left[\sum_{h=1}^{H}r_{i,h}(s_h,a_h)\right]. \] For profiles $\pi^1,\ldots,\pi^T$, define episode-wise external regret against a single policy by \[ R_i(T)=\sup_{\tau_i\in\Pi_i}\sum_{t=1}^{T} \left(V_i(\tau_i,\pi^t_{-i})-V_i(\pi^t)\right). \] An editorial version of the constant-regret target is a decentralized self-play procedure and a finite constant $C_G$, independent of $T$, such that \[ \forall G\quad\forall T\geq1\quad\forall i\in N,\qquad R_i(T)\leq C_G. \] Use the source's full-feedback regime: at a queried $(h,s,a_i)$ the learner receives the exact own reward and transition kernel averaged against the opponents' current Markov policies. A computational formulation must additionally fix a per-round oracle budget and an arithmetic-operation budget, both polynomial in the finite game description and $T$; these resource restrictions are editorial specifications.

Let $\mu_T$ select one joint profile $\pi^t$ uniformly, before the episode. A coarse deviation ignores its own profile recommendation and uses an arbitrary $\tau_i\in\Pi_i$. Linearity gives \[ \max_i\sup_{\tau_i\in\Pi_i} \left(V_i(\tau_i,(\mu_T)_{-i})-V_i(\mu_T)\right) =\frac1T\max_i R_i(T). \] Thus the stated regret target implies a $C_G/T$ coarse-correlated-equilibrium gap for this particular mixture.

Short English statement

Can decentralized self-play achieve cumulative external regret bounded independently of the number of episodes, with a corresponding $1/T$ equilibrium error?

Variants and scope boundaries

The quantifier is over opponents generated by the same self-play procedure. Constant regret against arbitrary adversarial opponents is a different target. The source's recursive correlated-policy output and its local weighted regrets must not be identified with the ordinary empirical mixture above without an additional argument. Sample-based learning with unknown rewards or transitions changes the feedback model.

Source relationship and status

[S1], Section 5, explicitly retains constant regret as a future question after an $O(\log T/T)$ CCE guarantee. The displayed external-regret problem is an explicit editorial specialization; the source does not completely specify the resource model for every possible constant-regret algorithm.

References

[S1] Asrın Efe Yorulmaz and Tamer Başar, Near Optimal Convergence to Coarse Correlated Equilibrium in General-Sum Markov Games, arXiv:2511.02157v1 (2025). Locators: Sections 2.1--2.5 (game, oracle, policy, CCE and regret definitions), Section 5 (constant-regret question). https://arxiv.org/html/2511.02157v1

Common conventions: Source mathematical conventions

Finite games. For a finite set $A$, $\Delta(A)$ is its probability simplex. Players choose independent mixed strategies in Nash equilibrium; correlation is allowed only when explicitly part of the solution concept. In a game with payoff functions $u_i$ and strategy profile $x$, an additive $\varepsilon$ Nash equilibrium satisfies \[ u_i(x)\geq u_i(x_i',x_{-i})-\varepsilon \quad\text{for every player $i$ and every admissible deviation $x_i'$}. \] For numerical approximation, payoffs are normalized as locally specified. An $\varepsilon$ payoff residual is distinct from distance at most $\varepsilon$ to the set of exact equilibria. Point convergence, convergence of empirical play, and convergence in distance to an equilibrium set are also distinct.

Computational representations. Unless stated otherwise, a complexity question takes rational data with binary encoding; polynomial time is measured in total bit length. A fixed-accuracy polynomial algorithm is not necessarily polynomial in $1/\varepsilon$, and neither is necessarily polynomial in $\log(1/\varepsilon)$. Succinct games and value, demand, or sampling oracles must declare their interfaces. Exact real solutions require an explicit representation; an unspecified list of arbitrary real numbers is not a finite computational output. A claimed algorithmic barrier is meaningful only for its specified model and reductions.

Dynamic games. Histories, information, observation, and allowable randomization are part of the model. A stationary strategy depends only on the current state; a positional strategy in a deterministic graph game chooses one action at each controlled vertex. Nash equilibrium at an initial state and equilibrium after every history are different requirements. An expectation of a pathwise $\liminf$ payoff, a $\liminf$ of expected averages, a limiting expected average, and a uniform finite-horizon equilibrium are different criteria. None is silently substituted for another.

Allocation and mechanisms. A complete allocation assigns every item exactly once unless otherwise stated. Zero-valued goods, negative values, capacity constraints, feasibility, lotteries, and copies of goods affect fairness definitions and are specified locally. Dominant-strategy incentive compatibility, Bayesian incentive compatibility, universal truthfulness, and truthfulness in expectation impose different inequalities. Whenever an objective ratio has zero denominator, its convention is stated or those instances are excluded.

Infinite-dimensional models. Expectations, integrals, stochastic equations, and optimization objectives require their local regularity, integrability, filtrations, and admissible domains. A backward--forward mean-field system is a boundary-value problem; it is not an initial-value semiflow without an additional construction. Long-time, large-population, and vanishing-noise limits require an order of limits and a convergence topology. If a minimum need not be attained, the objective is its infimum or supremum and the approximation requirement is stated separately.

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Econ-115-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

GPT 6 Astra Ultra attempt on Econ-115

Finite improvement and history-sensitive regret in Markov games

Catalogue problem: C73-113. Status: Unresolved. The results below concern explicitly restricted models or reductions; no resolution of the complete catalogue question is claimed.

Abstract

An exact full-feedback oracle permits constant ordinary policy regret in common-interest finite-horizon Markov games by a finite improvement procedure. Its regret constant is exponential in the number of state--time decision points, but its work per episode is polynomial. We also construct an exogenous-transition example in which every local fixed-action regret is zero while one history-dependent policy earns linear improvement. This identifies an obstruction to transferring local regret bounds to the catalogue's empirical mixture.

Question and feedback

For a finite episodic game with $n$ players, horizon $H$, state set $S$, rewards in $[0,1]$, and common initial state, write $V_i(\pi)$ for player $i$'s expected episode reward. The question is whether decentralized self-play can guarantee \[ R_i(T)=\sup_{\tau_i}\sum_{t=1}^T \{V_i(\tau_i,\pi_{-i}^t)-V_i(\pi^t)\}\le C_G \] for every $T$, where the comparator is one arbitrary behavioral policy and $C_G$ is independent of $T$. The oracle, queried at $(h,s,a_i)$, returns the exact reward and transition law averaged against the current opponents' Markov policies. Arithmetic and oracle use per episode must be polynomial. The source asks a constant-regret question after obtaining a near-$1/T$ guarantee for its own recursively generated output [YB]; its output construction is distinct from the ordinary uniform episode mixture used here.

The following restriction is substantive: assume all players have the same stage reward $r_h(s,a)$. Opponent policies remain fixed during each oracle sweep. Public knowledge of player labels and the episode number determines whose turn it is; no reward communication between players is required.

A constructive constant bound in common-interest games

Let $m=|S|$ and \[ K=\prod_{i=1}^n |A_i|^{Hm}. \] This counts deterministic Markov policy profiles, including decisions at unreachable states. Initialize any such profile. During episode $t$, the active player is $1+((t-1)\bmod n)$. Everyone plays the current profile. The active player queries all of its state--time--action oracle entries, evaluates its current policy, and computes a deterministic best response by backward induction. For the next episode, it changes its policy only if the best response has strictly larger initial-state value. Break action ties by a fixed public order. All other policies remain fixed. Oracle computation can be performed after play, using the opponents' unchanged policies for that episode.

Theorem (Constant regret with polynomial episode work): In every common-interest game just specified, the procedure makes at most $K-1$ policy changes. There exists $t_0\le nK+1$ such that its profile is constant for all $t\ge t_0$ and is a Nash equilibrium against all behavioral deviations from the prescribed initial state. For every player and every integer $T\ge1$, \[ R_i(T)\le HnK. \] Each episode needs at most $Hm|A_i|$ oracle queries by its active player and $O(Hm^2|A_i|)$ arithmetic operations, if each transition query returns a length-$m$ vector. This is an exact-arithmetic oracle result.
Proof: Against fixed Markov opponents, player $i$ faces a finite-horizon Markov decision problem with the queried reward $\bar r_{i,h}$ and kernel $\bar P_{i,h}$. Define $B_{H+1}=0$ and recursively \[ B_h(s)=\max_{a_i}\{\bar r_{i,h}(s,a_i) +\bar P_{i,h}B_{h+1}(s,a_i)\}. \] Backward conditioning proves that the expected remaining reward of any history-dependent randomized policy at a history ending in $(h,s)$ is at most $B_h(s)$. Choosing a maximizing action attains the bound at every state. Thus a deterministic Markov best response is also a best response among all behavioral policies. Evaluation of the current policy uses the same recursion with its prescribed action instead of the maximum.

Let $V(\pi)$ denote the common value. Every change strictly increases $V$, and every visited profile is one of $K$ deterministic profiles. Consequently no profile can be revisited after a change and at most $K-1$ changes occur. If a complete cycle of $n$ active-player turns contains no change, each player has checked its best response against the same profile; all subsequent cycles also have no change. Before this happens, every full cycle contains a strict improvement. There are therefore at most $K-1$ such cycles and one final checking cycle, or at most $nK$ episodes before the permanent profile is used.

At the permanent profile $\pi^*$, $V_i(\tau_i,\pi_{-i}^*)\le V_i(\pi^*)$ for every behavioral $\tau_i$. Before it, the gain from any deviation is at most $H$ because total rewards lie in $[0,H]$. For every fixed $\tau_i$ the sum of its gains is at most $HnK$; taking its supremum proves the bound. The stated computational counts follow directly from the two backward recursions and one oracle sweep. ∎

The algorithm need not know $K$ or detect global termination. Strict improvement comparisons use exact oracle values. Bit-complexity, approximate comparisons, and sampling noise require separate analysis: a numerical tolerance can stop at an approximate equilibrium whose error, if held fixed forever, produces linear regret. The theorem's constant can be enormous, so it is not a claim of a practical fast convergence rate.

Corollary (Ordinary mixture guarantee): In the theorem's setting, draw an episode index uniformly from $\{1,\ldots,T\}$ and then execute its entire policy profile. A player that ignores its own recommendation and uses any one behavioral policy gains at most $HnK/T$ in expectation.
Proof: For every such policy its gain is the average of the $T$ episode gains. The theorem bounds their supremum. This argument does not resample an index at each stage. ∎

Why statewise regret can miss the comparator

The next example uses only two stages and action-independent transitions. At stage one player 2 publicly chooses $b\in\{0,1\}$. At stage two player 1 chooses a prediction $a\in\{0,1\}$ and player 2 again chooses a bit $c$. Player 1's stage-two reward is ${\mathbf 1}\{a=c\}$, all other rewards are zero. The stage-two state is the same regardless of the stage-one bit. Both players observe the action history.
Proposition (A local-to-global separation): For every even $T$, there is a sequence of Markov policy profiles such that all statewise external regrets against fixed actions are zero for both players, but player 1's ordinary regret against a single behavioral policy is $T/2$.
Proof: In odd episodes let player 2 choose $b=c=0$; in even episodes let it choose $b=c=1$. Each episode's policy is Markov: the common bit is fixed in the policy before the episode. Let player 1 predict using a fair coin independently of the history. Its total expected reward is $T/2$. Each fixed stage-two action is correct in exactly $T/2$ episodes, so its local regret is zero. All other local payoff vectors are identically zero.

Consider the single behavioral rule that at stage two predicts the observed stage-one bit. It is the same rule in every episode, and is always correct. Its total value is $T$, giving regret $T/2$, which is also the maximum possible gain in this example. ∎

The comparator learns information about the selected episode profile from observed play. Even an action-independent physical transition does not remove this information. Consequently a reduction based only on the occupancy of physical states and local fixed-action regrets needs extra hypotheses or an explicit treatment of public histories.

What is still missing

The common-interest proof depends on a strict common potential over a finite policy set. In a general-sum game a profitable unilateral change can reduce other players' values and can revisit earlier profiles. The proof supplies no bound on these cycles. The local-regret example, meanwhile, is a comparison of a policy sequence with its mixture; it is not a lower bound against every self-play algorithm. A resolution needs a general-sum procedure controlling the specified ordinary behavioral comparator under the stated oracle and resource restrictions. Neither the common-interest construction nor the example does this.

References

  • [YB] A. E. Yorulmaz and T. Başar (2025). Near Optimal Convergence to Coarse Correlated Equilibrium in General-Sum Markov Games. arXiv:2511.02157v1. Sections 2.3--2.5 specify feedback and deviations; Section 5 states the constant-regret direction. https://arxiv.org/html/2511.02157v1.

Completion Estimate

20%

Go to contribution →