Regret, equilibrium, and learning in games: A guided tour

• URL: http://arxiv.org/abs/2608.09389v1
• Date: Mon, 10 Aug 2026 10:14:50 GMT
• Title: Regret, equilibrium, and learning in games: A guided tour
• Abstract summary: This note aims to serve as an entry point to the literature on learning in games.<n>We first consider a single agent engaged in a sequential decision process in an unknown, non-stationary, and possibly adversarial environment.<n>We examine what happens when the environment is shaped by the decisions of several interacting agents.
• Score: 24.674780930891043
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This note aims to serve as an entry point to the literature on learning in games, a topic with significant theoretical appeal and a wide range of applications -- from machine learning and data science to economics and beyond. Our presentation is structured around two complementary viewpoints: We first consider a single agent -- the learner -- engaged in a sequential decision process in an unknown, non-stationary, and possibly adversarial environment. We then examine what happens when the environment is shaped by the decisions of several interacting agents, not necessarily aware of each other's actions or goals, and all seeking to improve their individual rewards. In this general context, we examine a family of regularized learning policies based on best-responding to the past history of play, up to a regularization penalty intended to encourage exploration and prevent over-commitment to suboptimal choices. In the single-agent setting, we present some basic regret bounds for regularized learning in adversarial multi-armed bandits; in the multi-agent setting, we describe an ergodic equilibrium convergence result for zero-sum games in the spirit of classical results on fictitious play, as well as a "folk theorem" linking strategic and dynamic notions of stability -- Nash equilibria and attracting points of regularized learning, respectively. We pay special attention to the information available to the players and, through a unified analysis framework, we study both oracle- and payoff-based (bandit) methods. Our goal is to provide a coherent and comprehensible -- albeit, by necessity, not comprehensive -- account of some recent ideas in the field, and to discuss their implications for the study of rationality.

Related papers

• An Introduction to Causal Reinforcement Learning [58.680653905480284]
  Causal inference and reinforcement learning operate over different aspects of the same building block, counterfactual relations.<n>We put under a unifying treatment different modes of learning, including online, off-policy, and causal calculus learning.<n>Specifically, we introduce and discuss through causal lenses generalized policy learning, where to intervene, imitation learning, and counterfactual learning.
  arXiv  Detail & Related papers  (2026-06-23T05:28:33Z)
• Actor-Dual-Critic Dynamics for Zero-sum and Identical-Interest Stochastic Games [2.992414059774663]
  We propose a novel independent and payoff-based learning framework for games that is model-free, game-agnostic, and gradient-free.<n>We establish convergence to (approximate)libria in two-agent zero-sum and multi-agent identical-interest games over an infinite horizon.<n>This provides one of the first payoff-based and fully decentralized learning algorithms with theoretical guarantees in both settings.
  arXiv  Detail & Related papers  (2026-01-31T08:48:09Z)
• Agentic Reasoning for Large Language Models [122.81018455095999]
  Reasoning is a fundamental cognitive process underlying inference, problem-solving, and decision-making.<n>Large language models (LLMs) demonstrate strong reasoning capabilities in closed-world settings, but struggle in open-ended and dynamic environments.<n>Agentic reasoning marks a paradigm shift by reframing LLMs as autonomous agents that plan, act, and learn through continual interaction.
  arXiv  Detail & Related papers  (2026-01-18T18:58:23Z)
• Performative Reinforcement Learning [8.07595093287034]
  We introduce the concept of performatively stable policy. We show that repeatedly optimizing this objective converges to a performatively stable policy.
  arXiv  Detail & Related papers  (2022-06-30T18:26:03Z)
• A unified stochastic approximation framework for learning in games [82.74514886461257]
  We develop a flexible approximation framework for analyzing the long-run behavior of learning in games (both continuous and finite) The proposed analysis template incorporates a wide array of popular learning algorithms, including gradient-based methods, exponential/multiplicative weights for learning in finite games, optimistic and bandit variants of the above, etc.
  arXiv  Detail & Related papers  (2022-06-08T14:30:38Z)
• Hindsight and Sequential Rationality of Correlated Play [18.176128899338433]
  We look at algorithms that ensure strong performance in hindsight relative to what could have been achieved with modified behavior. We develop and advocate for this hindsight framing of learning in general sequential decision-making settings. We present examples illustrating the distinct strengths and weaknesses of each type of equilibrium in the literature.
  arXiv  Detail & Related papers  (2020-12-10T18:30:21Z)
• Opponent Learning Awareness and Modelling in Multi-Objective Normal Form Games [5.0238343960165155]
  It is essential for an agent to learn about the behaviour of other agents in the system. We present the first study of the effects of such opponent modelling on multi-objective multi-agent interactions with non-linear utilities.
  arXiv  Detail & Related papers  (2020-11-14T12:35:32Z)
• End-to-End Learning and Intervention in Games [60.41921763076017]
  We provide a unified framework for learning and intervention in games. We propose two approaches, respectively based on explicit and implicit differentiation. The analytical results are validated using several real-world problems.
  arXiv  Detail & Related papers  (2020-10-26T18:39:32Z)
• On Information Asymmetry in Competitive Multi-Agent Reinforcement Learning: Convergence and Optimality [78.76529463321374]
  We study the system of interacting non-cooperative two Q-learning agents. We show that this information asymmetry can lead to a stable outcome of population learning.
  arXiv  Detail & Related papers  (2020-10-21T11:19:53Z)
• Importance Weighted Policy Learning and Adaptation [89.46467771037054]
  We study a complementary approach which is conceptually simple, general, modular and built on top of recent improvements in off-policy learning. The framework is inspired by ideas from the probabilistic inference literature and combines robust off-policy learning with a behavior prior. Our approach achieves competitive adaptation performance on hold-out tasks compared to meta reinforcement learning baselines and can scale to complex sparse-reward scenarios.
  arXiv  Detail & Related papers  (2020-09-10T14:16:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.