No-regret Dynamics and Fictitious Play

Abstract

Potential based no-regret dynamics are shown to be related to fictitious play. Roughly, these are epsilon-best reply dynamics where epsilon is the maximal regret, which vanishes with time. This allows for alternative and sometimes much shorter proofs of known results on convergence of no-regret dynamics to the set of Nash equilibria.

References in corpus (2)

• Stochastic approximations of set-valued dynamical systems: Convergence with positive probability to an attractor
• Consistency of vanishing smooth fictitious play

Cited by in corpus (11)

• Game-Theoretic Multiagent Reinforcement Learning
• Distributed stochastic optimization via matrix exponential learning
• No-regret learning and mixed Nash equilibria: They do not mix
• Computational Performance of Deep Reinforcement Learning to find Nash Equilibria
• Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium
• Tight last-iterate convergence rates for no-regret learning in multi-player games
• Gradient-free Online Learning in Games with Delayed Rewards
• Learning in Quantum Common-Interest Games and the Separability Problem
• Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information
• Uncoupled Bandit Learning towards Rationalizability: Benchmarks, Barriers, and Algorithms
• Distributed No-Regret Learning in Multi-Agent Systems