A two-player zero-sum repeated game between a learner and nature whose value identity generates Bayesian updating and an exact accounting of exponential-weights regret at once is given, and supplies the comparator-class variational form that a wide class of concentration phenomena share.
Abstract
We give a two-player zero-sum repeated game between a learner and nature whose value identity generates Bayesian updating and an exact accounting of exponential-weights regret at once, and supplies the comparator-class variational form that a wide class of concentration phenomena share. The terminal payoff is the most a comparator can gain at fixed relative entropy from the prior, and the one-step constraint is an information budget on nature's move under the learner's mixed action. With the learner's move otherwise unrestricted, Gibbs/Bayes weights emerge as its unique Bellman equalizer -- the mixed action that makes the per-round loss independent of which direction nature moves -- with log-partition functions playing the role of value functions. The regret decomposes exactly into three parts: a per-round information loss reflecting the variation in observed outcomes, an additive retempering drift that accounts exactly for any change of measurement scale between rounds, and the information the comparator carries relative to the prior. The variance and bounded-range proxies that drive standard regret bounds are looser relaxations of this decomposition, which holds generally and governs them all. Both players'strategies are read off from the decomposition term by term, and repeated play yields an information-theoretic ledger of self-play in place of the usual quadratic-variation surrogate. The same comparator-class geometry accounts for the classical large-deviation bounds, and methods across bandits, posterior sampling, aggregation, and boosting are specializations of the one regret decomposition.
We study information design when a designer with commitment shapes the information of strategically interacting, far-sighted agents whose actions drive a persistent, controlled Markov state. We introduce the Markov Bayes correlated equilibrium (Markov BCE), the controlled-Markov generalisation of the BCE of Bergemann and Morris (2016), characterised by a dynamic obedience condition that adds a continuation-value term to the static one and reduces to it when actions cannot move the state. Recommending actions is without loss; the designer's problem is recursive in the agents'promised continuation utilities and is solved by a set-valued backward-induction algorithm whose optimum exists and lies between the no-disclosure and first-best values. For linear-quadratic-Gaussian payoffs the obedience condition becomes a covariance condition with a modified interaction matrix, and the stationary case reduces to an algebraic Riccati equation. When agents instead learn the transition, we identify the rent an agent earns from a model of the dynamics sharper than the designer anticipates: it is non-negative, zero at the known-dynamics benchmark, and deterred only by building slack into obedience. Under persistent excitation the cumulative rent grows logarithmically as heterogeneous agents'estimates converge. Two worked examples, in congestion and resource coordination, together with a numerical study illustrate the theory.
Finite-player nonzero-sum optimal stopping games typically lead to coupled equilibrium systems whose complexity grows rapidly with the number of players. We introduce an independently randomized formulation in which each stopping rule is represented by an adapted, nondecreasing cumulative stopping process. The canonical embedding preserves pure-profile payoffs, and a pure profile is a Nash equilibrium of the original game if and only if its embedding is a Nash equilibrium of the randomized game. We adopt the $\alpha$-potential approach to construct an $\alpha_N$-potential function, with the error $\alpha_N=O(N^{-1})$ under weak-interaction. We also identify an exact-potential subclass with a closed-form threshold equilibrium. For local stopped-status interactions, randomized payoffs admit a local stopped-mass representation, and potential maximization can be formulated as a multidimensional singular-control problem with local gradient constraints and a nonlocal condition for finite jumps. Under suitable regularity assumptions, we study the associated Hamilton-Jacobi-Bellman quasi-variational inequality and its regularity properties. For unknown model coefficients, we propose a bounded-intensity Potential-CT-DDPG learning algorithm. Numerical experiments closely match the analytical benchmark and yield estimated best-response improvements consistent with $N^{-1}$ scaling.
We study an agent who tracks several independent, unobserved, slowly drifting states and is paid by how well a chosen action matches each state but who can process only a bounded amount of information per period. The payoff environment is deliberately symmetric—quadratic matching losses, Gaussian drift, Gaussian observation noise—and the agent’s objective contains no asymmetry: we treat both the risk-neutral (linear) objective and the long-run log-growth (Kelly) objective. Within this symmetric environment, we show that the value of attentionis sharply asymmetric in the sign of the agent’s surprise. Because the matching payoff is maximized when action equals state, a surprisingly low payoff is strong evidence of a state mismatch that is worth correcting, whereas a surprisingly high payoff is evidence either of noise or of a match already achieved—in both cases carrying little decision-relevant information. We prove (Theorem 1) that the posterior expected mismatch, and hence the value of information, is strictly decreasing in the realized payoff, negligible for good surprises and rising steeply for bad ones, with a correspondingly asymmetric slope. We then show that an information-constrained agent optimally adopts a threshold attention policy (Theorem 2), which, under one explicit and standard bridge—that valuation inherits attention weight, as in salience and rational-inattention theories of choice—projects onto a reference-dependent value function with a kink at the expected payoff and a loss-side slope strictly steeper than its gain-side slope (Corollary 1): precisely the signature of loss aversion. The mechanism supplies the structure of loss aversion—its sign, its reference point, and how it varies with the environment—while its magnitude is one calibrated parameter that places the implied coefficient in the empirical range. Risk aversion follows as a corollary (Theorem 3): the kink induces first-order risk aversion over small symmetric gambles, inverting the usual hierarchy in which (second-order) risk aversion is primitive, and loss aversion is an add-on. The mechanism is immune to the Rabin calibration critique. Simulations benchmark the myopic policy against the computed optimum, map the mechanism’s robustness across noise tails, and locate the implied coefficient; we close with extensions to endogenous gain-seeking in convex (“gold-rush”) environments, population heterogeneity through learned priors, and a reading of hedonic affect as the Lagrange multiplier that prices a scarce attentional resource.
Held-out log-likelihood is the standard currency for comparing statistical models of neural spike trains, and is often reported as bits per spike relative to a homogeneous Poisson baseline. The units of this metric are difficult to reason about: it is rarely obvious whether an improvement of, say, 0.34 bits per spike is a large effect or a negligible one. This note develops an interpretation of held-out log-likelihood borrowed from game-theoretic statistics. A fitted model Q is treated as a player who bets on each upcoming observation at prices set by a baseline model B. Under the optimal (Kelly) betting strategy the player’s contract function is exactly the likelihood ratio q/b, and the expected log-likelihood ratio 𝓛 is the exponential growth rate of the player’s wealth. Because the wealth process is a nonnegative martingale under the null hypothesis that B generated the data, Ville’s inequality turns it into an anytime-valid test: the baseline may be rejected at level α as soon as wealth exceeds 1/α. This yields a simple summary statistic, the time to significance τΔ=-Δlog(α)/𝓛, which is the amount of held-out recording needed on average to reject the baseline at level α. Since τ is a strictly decreasing function of 𝓛, it ranks models identically to bits per spike; it is not a new statistic but a more interpretable unit for an existing one, expressed in seconds of recording rather than in bits. We illustrate the construction on head-direction cells recorded in mouse anterior thalamus, where a generalized linear model reaches significance against a homogeneous Poisson baseline in roughly 120 ms of held-out data for a strongly tuned cell and roughly 11 s for a moderately tuned cell.
Learning dynamics in zero-sum games are typically analyzed under algorithmic symmetry: both agents use the same update rule, or methods from a common algorithmic family. This is at odds with the nature of zero-sum games; competing agents need not coordinate on algorithm selection. This paper studies algorithmic asymmetry in learning dynamics in zero-sum games. In particular, we ask whether fast convergence can be recovered when one agent is fixed to vanilla gradient descent, whose standard regret-based analysis certifies, at best, $O(1/\sqrt{T})$ ergodic convergence. We show that the slow rate is not intrinsic. When one agent uses gradient descent, the opposing agent can use a modified optimistic update, which we call Alternating Optimistic Gradient Descent (AOGD), to make the joint dynamics simulate Alternating Gradient Descent on the even iterates. As a result, the time-average of the asymmetric GD vs.\ AOGD dynamics converges to Nash equilibria at rate $O(1/T)$. Our results show that fast convergence need not require coordinated algorithm selection: one agent can compensate for a slower opponent. More broadly, the paper highlights algorithmic asymmetry as a useful lens for understanding cross-class interactions in multiagent optimization.
We examine the interplay between ordinal, preference-based solution concepts in games and the long-run behavior of game dynamics, asking in particular to what extent the combinatorial data of a game -- its preference graph -- determine the outcomes of no-regret learning dynamics -- such as follow-the-regularized-leader (FTRL). In one direction, we show that the skeleton of every dynamically stable set (i.e. the set of pure profiles it contains) must also be preferentially stable, that is, it must be closed under profitable deviations. We then ask the converse question: when do preferences determine the long-run behavior of the players'learning dynamics? We begin by showing that preferences characterize asymptotic stability in the case of subgames -- i.e. subsets of pure profiles obtained by restricting players'action sets. Beyond this case however, the equivalence between dynamic and preferential stability collapses: concretely, we construct a three-player game with a preferentially stable set whose span is dynamically unstable, showing in this way that preferences do not suffice as a criterion of dynamic stability. We then bridge this gap via the notion of resilience under aggregate deviations, an easy-to-check payoff-based condition that guarantees asymptotic stability of arbitrary spans of pure strategies.
Omar Abbadi, R. Laraki, P. Mertikopoulos· 0 citations
A new machine-learning framework aims to improve the success rate of computational protein design while moving away from results that reproduce sequences found in nature.
MIT News · Artificial Intelligence· news.mit.eduAug 24, 2026
