Search papers, labs, and topics across Lattice.
This paper explores learning in games through the lens of both single-agent and multi-agent scenarios, focusing on how agents adapt their strategies in non-stationary and adversarial environments. It introduces regularized learning policies that balance best responses with exploration to mitigate the risk of suboptimal choices, providing regret bounds for adversarial multi-armed bandits and establishing convergence results for zero-sum games. The findings highlight the interplay between individual learning and collective dynamics, offering insights into the stability of Nash equilibria and the implications for rational decision-making in strategic settings.
Regularized learning policies can significantly enhance decision-making in adversarial environments by balancing exploration and exploitation, leading to improved convergence in multi-agent scenarios.
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.
