we-solve (beta)

Econ-148 · economics · computer science · Computational economics

Learning with persistent states

LLM status Open unverified

Statement

Original subject group: Game theory and strategic interaction

Audit classification: Published research agenda. Tardos’s 2026 ICM lecture explicitly identifies carry-over learning as a research area. The uniform welfare inequality is editorial and is false for arbitrary learners.

Definitions and precise research target

Model and research target. Consider a finite-state resource-allocation game with state space $S$, finite action sets $A_i$, reward $r_i(s,a)\in[0,1]$, and transition kernel $P(s'\mid s,a)$. States record budgets or other resources carried between periods. Fix initial law $\nu$, a class $\mathcal C$ of admissible kernels and reward systems, and a class $\mathcal L$ of decentralized learning rules using explicitly specified feedback. Let $W_T(L)=E_{\nu,L}[\sum_{t=1}^T\sum_i r_i(s_t,a_t)]$. Let $W_T^*$ be the maximal expected welfare of a centralized controller with the same initial law, transitions, and resource constraints. Determine assumptions and behavioral performance criteria under which \[ W_T(L)\geq c\,W_T^*-o(T) \quad\text{for every game in }\mathcal C\text{ and every }L\in\mathcal L, \] with a nonzero constant $c$ independent of the horizon. Define the little-order remainder uniformly over the stated class. Any regret comparator must simulate the state trajectory induced by an alternative policy; holding observed states fixed is generally inadequate when actions alter tomorrow's resources. Characterize which mixing, smoothness, information, or budget assumptions are necessary, and give tight failures outside the guarantee.

Definitions and maintained assumptions (editorial unless a source definition is named). A policy or learner is a stochastic map from its available history to an action distribution; declare whether it observes state, own reward, opponent actions and transition outcomes. The centralized benchmark optimizes a joint policy using the same physical state dynamics and an explicitly stated information advantage. A class $\mathcal L$ cannot include arbitrary always-wasteful rules if positive welfare guarantees are sought. Specify a behavioral requirement, for example policy regret against an admissible stationary policy class, with each comparator’s entire state trajectory simulated under that policy. Define a uniform remainder $g(T)\ge0$ by $g(T)/T\to0$, independent of the game and learner, and require $W_T(L)\ge cW_T^*-g(T)$. To make this meaningful, state uniform bounds on state and action counts, rewards, mixing times and the policy-regret bound; unrestricted state-class variation can destroy uniformity. Finite-state existence or finite-horizon dynamic programming for one known instance is a baseline, not the claimed frontier.

Variants and assumption changes

  1. Uniform mixing (editorial). Require every stationary joint policy to induce an irreducible chain with a common mixing-time bound. Seek welfare guarantees under a specifically defined policy-regret condition and known reward smoothness.
  2. Resource traps (editorial). Permit an absorbing depleted-resource state. Construct tight examples showing whether exploration or irreversible budget use prevents positive uniform guarantees, then test restoration by replenishment or reset assumptions.

References and source audit

  1. Learning outcomes in dynamic games; repeated auctions with budgets. Supports the stated research area; exact displayed specification is editorial. https://epubs.siam.org/doi/full/10.1137/25M1808064
  1. Éva Tardos. 2026. Learning and the Price of Anarchy in Games. Learning outcomes in dynamic games; Packet routing as a dynamic game; Theorem8. https://epubs.siam.org/doi/full/10.1137/25M1808064. DOI: https://doi.org/10.1137/25M1808064.

Common conventions: Source mathematical conventions

These conventions apply to each entry unless explicitly replaced.

Models and identification. A primitive model $m$ specifies all probability laws, feasible choices, information, equilibrium and measurement rules used by its target. The admissible class $\mathcal M$ is fixed independently of outcomes. If $P_O(m)$ is its observable probability law and $\tau(m)$ the target, its identified set at observable law $P$ is \[ \mathcal I_\tau(P)=\{\tau(m):m\in\mathcal M,\ P_O(m)=P\}. \] Point identification means that this set is a singleton. An empty set signals incompatibility of data and assumptions. Coordinate bounds need not describe the joint set. Bounds are sharp only if every retained target is attainable or arbitrarily approachable by compatible models. Finite bounds require explicit restrictions on unobserved quantities; unrestricted confounding, hidden wealth, extrapolation or arbitrary equilibrium selection can yield uninformative sets.

Causal interventions. A potential outcome $Y_i(p)$ is the outcome under a complete policy regime $p$, including timing, financing, information and market spillovers. The target population and units are fixed before treatment. With interference, use the complete assignment vector or a justified exposure mapping; individual no-interference notation alone cannot identify an economy-wide intervention. A difference of mean potential outcomes does not require the cross-world joint distribution. Conditioning on post-treatment migration, survival, enrollment or employment changes the estimand and needs separate justification.

Statistical statements. An estimator, confidence set, forecast or test specifies a sampling law, model class and loss/coverage criterion. Uniform $(1-\alpha)$-coverage means $\inf_{m\in\mathcal M}\Pr_m\{\tau(m)\in C_n\}\geq1-\alpha$, or an explicitly asymptotic version. The whole parameter space trivially has coverage, so informativeness requires a stated width, risk or power objective. A forecasting improvement is relative to a named benchmark, information set and evaluation population.

Equilibrium and optimization. An equilibrium comprises feasible plans, optimality, beliefs where needed, budget constraints and all market/resource clearing. The primitives or a stated benchmark define each correspondence $\mathcal E(p;m)$. Nonemptiness is assumed or proved, never inferred just from compact policy sets. A selected-equilibrium target uses a declared selection rule; a robust target quantifies over all permitted equilibria. Use suprema or infima unless attainment is established. An $\varepsilon$-optimal policy is feasible and within $\varepsilon$ of the finite optimum value. Report an empty feasible set separately.

Welfare and accounting. Normative utility, interpersonal normalization, social weights, numeraire, discounting and the use of public receipts are primitives. Behavioral utility need not coincide with the welfare criterion. Household welfare includes ownership income and rents once; adding profits again to compensating variation generally double-counts them. A monetary equivalent is defined by an explicit transfer and price convention, with monotonicity and range conditions. Average effects, mechanism contributions, transfers and welfare losses are different targets. Infinite sums require convergence and dynamic feasible plans require terminal or no-Ponzi conditions.

Source versions. A working-paper date, revision date and journal publication year are distinguished. A DOI for a journal version is not automatically the DOI of an earlier manuscript. Locators refer to the stated version and printed pages where specified. A metadata-only check does not verify a claim about a full-text conclusion. Every entry's source subsection narrows the provenance claim accordingly.

Statement licence: CC-BY-4.0 · Source file

Contributions 1

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

GPT 6 Astra Ultra attempt on Econ-148

Persistent states: a welfare guarantee and two failures of observed-state regret

Status: Unresolved. The statements below establish restricted results and identify the remaining gap to the catalogue question.

Abstract

When states evolve independently of actions, a statewise smoothness inequality and regret against stationary deviations imply a finite-horizon welfare bound against a central controller. When actions change transitions, zero regret measured on the observed state trajectory can coexist with arbitrarily poor welfare, even under a common Doeblin reset. The constructions pinpoint why counterfactual state trajectories matter.

Short target and behavioral requirement

The catalogue asks for welfare guarantees for learning in finite games with persistent, action-dependent states. Fix finite states $S$, finite action sets $A_i$, rewards $u_i(s,a)\in[0,1]$, and social welfare $w(s,a)=\sum_i u_i(s,a)$. A central controller has the same physical transition law and sees the current state. It may choose the whole action vector. Its optimal expected horizon-$T$ welfare is $W_T^*$.

For the positive theorem assume the transition kernel $P(s'\mid s)$ is independent of all actions. The learners see the state. Let $\pi^*(s)$ maximize $w(s,a)$ for each state, with a fixed tie rule. Assume their realized play satisfies, in expectation, \[ {\mathbb{E}}\sum_{t=1}^T u_i(S_t,A_t) \ge{\mathbb{E}}\sum_{t=1}^T u_i(S_t,\pi_i^*(S_t),A_{-i,t})-R_i(T). \] This is a regret requirement against a state-dependent stationary deviation, stronger than regret only against one constant action. It can be imposed against all stationary maps; only this particular comparator is needed in the theorem. No assertion is made that arbitrary learners satisfy it.

A statewise guarantee when transitions are exogenous

Suppose constants $\lambda>0$, $\mu\ge0$ obey, for every state $s$ and action profile $a$, \[ \sum_i u_i(s,\pi_i^*(s),a_{-i}) \ge\lambda w(s,\pi^*(s))-\mu w(s,a). \]
Theorem (Finite-horizon welfare bound): Under these assumptions the learners' expected welfare $W_T$ satisfies \[ W_T\ge {\lambda\over1+\mu}W_T^* -{\sum_iR_i(T)\over1+\mu}. \] If the number of players is uniformly bounded and the regret bounds are uniformly sublinear over a declared model class, this supplies a uniform sublinear remainder for that class. No mixing assumption is needed in this exogenous-state case.
Proof: Because actions do not affect states, every policy of the central controller induces the same state law. Maximizing current welfare at every state cannot reduce any future payoff, so $W_T^*={\mathbb{E}}\sum_t w(S_t,\pi^*(S_t))$. Sum the regret inequalities over players and apply the smoothness inequality at each observed $(S_t,A_t)$. This gives $W_T\ge\lambda W_T^*-\mu W_T-\sum_iR_i(T)$. Rearrangement proves the bound. The uniform assertion follows directly from the stated uniform bounds. The argument makes no comparison between different state trajectories because those trajectories have identical laws under all actions. ∎
This is a conditional theorem: it supplies no new learning algorithm or computational regret rate. It also does not permit regret comparators to hold opponents' reactions fixed in one place and re-equilibrate them in another.

An irreversible trap

Proposition (Zero observed-state regret, linear policy regret): There is a one-player two-state, two-action model and a deterministic learner with zero external regret on its observed states for every horizon, but welfare 1 against central optimum $T$ for every $T\ge1$.
Proof: States are $s,d$, initially $s$, and actions are safe and bad. Both actions earn reward 1 in $s$ and 0 in $d$. From $s$, safe stays in $s$ and bad enters $d$; $d$ is absorbing under either action. Choose bad initially. Its total reward is 1. Every fixed action or stationary state-dependent action earns exactly the same reward when evaluated on the learner's observed states, since current reward does not depend on action. That external regret is zero. The policy always choosing safe, with its own induced trajectory, remains in $s$ and earns $T$. Thus regret against counterfactual policies is $T-1$. ∎
A stage payoff comparison has ignored the opportunity cost of consuming the favorable state. The example does not contradict guarantees that assume sublinear policy regret: this learner fails that assumption.

Uniform mixing does not repair the wrong comparator

For a reset probability $\eta\in(0,1]$, keep the same reward function but change transitions. From either state, safe has base next state $s$ and bad has base next state $d$. With probability $\eta$ replace the base next state by a fresh fair draw from $\{s,d\}$, independently over time.
Theorem (An ergodic failure with explicit ratio): Every stationary randomized policy induces an irreducible, aperiodic chain with one-step total-variation contraction factor at most $1-\eta$. Nevertheless the always-bad learner has zero observed-state regret against every stationary deviation. Starting at $s$, its welfare and the central optimum are \[ W_T=1+(T-1)\eta/2,\qquad W_T^*=1+(T-1)(1-\eta/2). \] Their limiting ratio is $\eta/(2-\eta)$. Consequently no strictly positive asymptotic welfare fraction uniform over all $\eta>0$ follows from observed-state regret and mere ergodicity.
Proof: Every transition row assigns at least $\eta/2$ to each state, proving irreducibility and aperiodicity. Each row is a mixture of mass $\eta$ on the same fair-reset law and mass $1-\eta$ on another law. Coupling the common reset proves the contraction bound, also for mixtures of actions at a state.

Current rewards remain action-independent, so all deviations evaluated on observed states earn the learner's reward exactly. Under always bad, every next state is $s$ with probability $\eta/2$, independent of the previous state. Under always safe it is $s$ with probability $1-\eta/2$. The central controller cannot obtain a larger next-period probability of $s$ under any action mixture, and its current reward is already fixed by the state. Backward induction therefore makes always safe optimal. Summing the initial reward and subsequent expected rewards gives the formulas. Dividing and taking $T\to\infty$ gives the ratio, which tends to zero as $\eta\downarrow0$. ∎

At a fixed positive lower bound on $\eta$, the last argument does not rule out constants depending on that bound. Nor does it disprove a positive theorem with a proper policy-regret condition in an action-dependent smooth game. It shows that replacing that condition by observed-state regret is invalid even in a very small, rapidly describable Markov model.

Remaining target and reference

The next needed result must compare each deviation on its induced state law, control opponents' adaptations, and keep mixing and regret constants uniform over the stated class. The positive theorem covers only action-independent transitions; the negative examples diagnose an inadequate hypothesis. They do not settle the catalogue's general persistent-state learning frontier.

References

  • [Tardos] É. Tardos (2026), Learning and the price of anarchy in games, Proceedings of the International Congress of Mathematicians 2026, vol. 2, 302--312. https://doi.org/10.1137/25M1808064. Background on welfare from learning and dynamic-game challenges. The restricted theorem and counterexamples here are proved explicitly and do not assert a general learning result for the dynamic models discussed in that article.

Completion Estimate

30%

Go to contribution →