The impact of uncertainty on regularized learning in games

• URL: http://arxiv.org/abs/2506.13286v1
• Date: Mon, 16 Jun 2025 09:28:22 GMT
• Title: The impact of uncertainty on regularized learning in games
• Authors: Pierre-Louis Cauvin, Davide Legacci, Panayotis Mertikopoulos,
• Abstract summary: We investigate how randomness and uncertainty influence learning in games.<n>In particular, we look at the dynamics of "follow-the-regularized-leader"<n>We show that, in any game, regardless of the noise level, "uncertainty favors extremes"
• Score: 24.800126996235512
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we investigate how randomness and uncertainty influence learning in games. Specifically, we examine a perturbed variant of the dynamics of "follow-the-regularized-leader" (FTRL), where the players' payoff observations and strategy updates are continually impacted by random shocks. Our findings reveal that, in a fairly precise sense, "uncertainty favors extremes": in any game, regardless of the noise level, every player's trajectory of play reaches an arbitrarily small neighborhood of a pure strategy in finite time (which we estimate). Moreover, even if the player does not ultimately settle at this strategy, they return arbitrarily close to some (possibly different) pure strategy infinitely often. This prompts the question of which sets of pure strategies emerge as robust predictions of learning under uncertainty. We show that (a) the only possible limits of the FTRL dynamics under uncertainty are pure Nash equilibria; and (b) a span of pure strategies is stable and attracting if and only if it is closed under better replies. Finally, we turn to games where the deterministic dynamics are recurrent - such as zero-sum games with interior equilibria - and we show that randomness disrupts this behavior, causing the stochastic dynamics to drift toward the boundary on average.

Related papers

• Do LLMs Know When to Flip a Coin? Strategic Randomization through Reasoning and Experience [1.7223564681760168]
  Strategic randomization is a key principle in game theory, yet it remains underexplored in large language models (LLMs)<n>We propose a novel zero-sum game inspired by the Tian Ji Horse Race, where the Nash equilibrium corresponds to a maximal entropy strategy.<n>We show that weaker models remain deterministic regardless of prompts, while stronger models exhibit increased randomization under explicit hints.
  arXiv  Detail & Related papers  (2025-06-21T05:26:33Z)
• Paths to Equilibrium in Games [6.812247730094933]
  We study sequences of strategies satisfying a pairwise constraint inspired by policy updating in reinforcement learning. Our analysis reveals a counterintuitive insight that reward deteriorating strategic updates are key to driving play to equilibrium along a satisficing path.
  arXiv  Detail & Related papers  (2024-03-26T19:58:39Z)
• The equivalence of dynamic and strategic stability under regularized learning in games [33.74394172275373]
  We examine the long-run behavior of regularized, no-regret learning in finite games. We obtain an equivalence between strategic and dynamic stability. We show that methods based on entropic regularization converge at a geometric rate.
  arXiv  Detail & Related papers  (2023-11-04T14:07:33Z)
• Game-Theoretic Robust Reinforcement Learning Handles Temporally-Coupled Perturbations [98.5802673062712]
  We introduce temporally-coupled perturbations, presenting a novel challenge for existing robust reinforcement learning methods. We propose GRAD, a novel game-theoretic approach that treats the temporally-coupled robust RL problem as a partially observable two-player zero-sum game.
  arXiv  Detail & Related papers  (2023-07-22T12:10:04Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  We study the problem of computing an approximate Nash equilibrium of continuous-action game without access to gradients. We model players' strategies using artificial neural networks. This paper is the first to solve general continuous-action games with unrestricted mixed strategies and without any gradient information.
  arXiv  Detail & Related papers  (2022-11-29T05:16:41Z)
• Who Leads and Who Follows in Strategic Classification? [82.44386576129295]
  We argue that the order of play in strategic classification is fundamentally determined by the relative frequencies at which the decision-maker and the agents adapt to each other's actions. We show that a decision-maker with the freedom to choose their update frequency can induce learning dynamics that converge to Stackelberg equilibria with either order of play.
  arXiv  Detail & Related papers  (2021-06-23T16:48:46Z)
• Disturbing Reinforcement Learning Agents with Corrupted Rewards [62.997667081978825]
  We analyze the effects of different attack strategies based on reward perturbations on reinforcement learning algorithms. We show that smoothly crafting adversarial rewards are able to mislead the learner, and that using low exploration probability values, the policy learned is more robust to corrupt rewards.
  arXiv  Detail & Related papers  (2021-02-12T15:53:48Z)
• On the Impossibility of Convergence of Mixed Strategies with No Regret Learning [10.515544361834241]
  We study convergence properties of the mixed strategies that result from a general class of optimal no regret learning strategies. We consider the class of strategies whose information set at each step is the empirical average of the opponent's realized play.
  arXiv  Detail & Related papers  (2020-12-03T18:02:40Z)
• No-regret learning and mixed Nash equilibria: They do not mix [64.37511607254115]
  We study the dynamics of "follow-the-regularized-leader" (FTRL) We show that any Nash equilibrium which is not strict cannot be stable and attracting under FTRL. This result has significant implications for predicting the outcome of a learning process.
  arXiv  Detail & Related papers  (2020-10-19T13:49:06Z)
• Chaos, Extremism and Optimism: Volume Analysis of Learning in Games [55.24050445142637]
  We present volume analyses of Multiplicative Weights Updates (MWU) and Optimistic Multiplicative Weights Updates (OMWU) in zero-sum as well as coordination games. We show that OMWU contracts volume, providing an alternative understanding for its known convergent behavior. We also prove a no-free-lunch type of theorem, in the sense that when examining coordination games the roles are reversed: OMWU expands volume exponentially fast, whereas MWU contracts.
  arXiv  Detail & Related papers  (2020-05-28T13:47:09Z)
• Efficient exploration of zero-sum stochastic games [83.28949556413717]
  We investigate the increasingly important and common game-solving setting where we do not have an explicit description of the game but only oracle access to it through gameplay. During a limited-duration learning phase, the algorithm can control the actions of both players in order to try to learn the game and how to play it well. Our motivation is to quickly learn strategies that have low exploitability in situations where evaluating the payoffs of a queried strategy profile is costly.
  arXiv  Detail & Related papers  (2020-02-24T20:30:38Z)
• Optimal strategies in the Fighting Fantasy gaming system: influencing stochastic dynamics by gambling with limited resource [0.0]
  Fighting Fantasy is a popular recreational fantasy gaming system worldwide. Each round, a limited resource (luck') may be spent on a gamble to amplify the benefit from a win or mitigate the deficit from a loss. We use a backward induction approach to solve the Bellman equation for the system and identify the optimal strategy for any given state during the game.
  arXiv  Detail & Related papers  (2020-02-24T11:31:25Z)

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.