Convergence and Stability of Coupled Belief–Strategy Learning Dynamics in Continuous Games

Strategic agents often need to engage in repeated interactions with each other while learning an unknown environment that impacts their payoffs. Such a situation arises in online market platforms, where buyers and sellers repeatedly make their transaction decisions while learning the latent market condition that governs the price distribution. The price distribution is updated based on the previous transactions and buyer reviews on platforms such as Amazon, eBay, and Airbnb (Moe and Fader (2004); Acemoglu et al. (2017)). Another situation concerns with transportation networks, where travelers make route choice decisions on a day-to-day basis while also learning the underlying state of network that affects the travel time distribution. This travel time distribution is repeatedly updated based on the delay and flow information provided by navigation apps such as Google Maps or Apple Maps (Zhu et al. (2010); Wu et al. (2021); Meigs et al. (2017)). In both situations, players’ strategic decisions (purchases and sales on online platforms or route choices in transportation networks) influence the learning of the unknown environment (latent market condition or network state), which then impact the players’ future decisions. Thus, the long-run outcome of strategic interactions among players is governed by the joint evolution of stage-wise decisions made by the players and learning of the unknown environment.

In this article, we introduce and study a learning model to describe this joint evolution in a game-theoretic setting. In our model, a finite number of strategic agents (players) repeatedly play a game with continuous strategy sets. The payoff of each player in the game is a function of the strategy profile with an unknown parameter (or parameter vector). A public information platform (e.g. a market platform or navigation app) serves as an information aggregator that intermittently updates and broadcasts a Bayesian belief estimate of the payoff parameter based on stage-wise game outcomes (i.e. strategies and randomly realized payoffs) to all players. Players then account for the most current belief when updating their strategies.

The players’ strategy update in our learning dynamics is generic so that it can be used to model a broad class of strategy learning rule that players decide to choose based on the updated belief and the strategy played in the previous stage. In particular, the strategy update can incorporate two classes of learning rules that naturally arise from utility-maximizing players. One is the belief-based best response dynamics, where, in each stage, players update their strategies using the best response that maximizes their expected utility given the updated belief and their opponents’ strategies. Another class is the belief-based no-regret learning dynamics, where each player updates their strategy using an online mirror ascent algorithm that maximizes the expected utility, and the gradient used in the algorithm is estimated using the updated belief. When the true parameter is known to players, our learning dynamics reduces to the classical strategy learning in games with complete information. For this special case, the belief-based best response dynamics reduces to the best response dynamics with complete information of utility functions, and the belief-based no-regret learning reduces to the no-regret learning dynamics with complete information of the gradient of utility functions.

Past literature has extensively studied various strategy learning rules in games. Learning rules based on best response strategies have been studied in both games with finite strategy set and continuous strategy sets when players have complete information of their utility functions. This includes simultaneous and sequential best response dynamics (Milgrom and Roberts (1990); Monderer and Shapley (1996b); Hofbauer and Sorin (2006)), fictitious play (Fudenberg and Kreps (1993); Monderer and Shapley (1996a)), and stochastic fictitious play (Benaim and Hirsch (1999); Hofbauer and Sandholm (2002)). For games with finite strategy sets, various learning rules have been proposed to model how players, who do not have complete information of the payoff matrices, learn an equilibrium based on the realized payoffs in every stage. Examples include log-linear learning (Blume et al. (1993), Marden and Shamma (2012), Alós-Ferrer and Netzer (2010)), regret-based learning (Hart and Mas-Colell (2003), Foster and Young (2006), Marden et al. (2007), Daskalakis et al. (2011); Syrgkanis et al. (2015)), payoff-based learning (Cominetti et al. (2010), Marden et al. (2009)), and replicator dynamics (Sandholm (2010b), Beggs (2005), Hopkins (2002)). On the other hand, in games with continuous strategy sets, learning dynamics typically assume the knowledge of players’ utility functions (e.g. the dynamics based on best responses), or consider that a stochastic estimate of the gradient of utility functions is available (e.g. no-regret learning and gradient-based learning in continuous games Rosen (1965); Mertikopoulos and Zhou (2019); Bravo et al. (2018)).

We extend the past literature by focusing on coupled belief-strategy dynamics, which naturally describes the learning behavior of players who adjust their strategies while relying on an information platform to learn the unknown utility functions that are parametrized. The setting of parametrized utility functions is especially relevant to continuous games since players need to learn their utility function on a continuous strategy set. To the best of our knowledge, past literature has not analyzed the long-run outcomes of coupled belief-strategy updates in continuous games. Our focus is to develop an approach to analyze the convergence and stability (both local and global) properties of this learning dynamics, and derive conditions under which a complete information Nash equilibrium naturally arises from the learning dynamics. Our conditions for learning complete information equilibrium can also be used for studying equilibrium computation algorithms in continuous games, however, such algorithmic aspects of equilibrium computation are outside the scope of our work.

Next, we summarize the main contributions of our paper.

Naturally, a complete information belief and the associated complete information equilibrium form a fixed point of our learning dynamics. However, the fixed point set may also include other fixed points that do not identify the true parameter. At these fixed points, the belief assigns a non-zero probability to other parameters besides the true parameter, which may lead to an incorrect payoff estimate for strategies that differ from the fixed point. Consequently, the associated fixed point strategy that the learning dynamics converge to may not be a complete information equilibrium.

Our proof of Theorem 1 builds on the martingale property of Bayesian beliefs as well as the properties of strategy learning in games. Firstly, we obtain the convergence of Bayesian beliefs by showing that the beliefs form a martingale. Secondly, to prove the strategy convergence, we construct a series of auxiliary strategy sequences, each of which is identical to the original sequence up to a certain stage, but differs in the “tail” subsequence – the strategies beyond that stage are updated using the fixed point belief. We show that the distance between a so-constructed auxiliary sequence and the original sequence goes to zero as the stage beyond which the two sequences differ tends to infinity. Thus, the convergence property of strategies in our coupled belief- strategy learning dynamics is derived from the convergence of the strategy updates with static belief being the fixed point belief. Finally, using the strategy convergence result, we prove that the players’ payoff distributions asymptotically approach the identical and independent distribution corresponding to the fixed point strategy. This also allows us to show that the belief concentrates exponentially fast on the subset of parameters with the property that, at fixed point, each parameter in this set induces the same payoff distribution as the true parameter.

When the sufficient and necessary condition for global stability is not satisfied, there exist one or multiple fixed points that do not have complete information of the true parameter. Then, whether learning converges to a complete information fixed point or not depends on the initial state. In this case, we study the local stability property that evaluates how robust a convergent fixed point is under local perturbations of beliefs and strategies. A fixed point is locally stable if states remain close to the fixed point with high probability when learning starts with an initial state close to that fixed point. A locally stable fixed point is robust to local perturbations, and thus is more likely to arise as the long-run outcome of the learning dynamics.

We prove that a fixed point is locally stable if it satisfies two conditions (Theorem 2): (a) The fixed point belief is locally consistent in that it consistently estimates the payoff distribution in a local neighborhood of the fixed point strategy (instead of just at the fixed point); (b) The fixed point strategy has a local neighborhood that is an invariant set for the strategy update. In proving this result, we again exploit the martingale property of beliefs and the properties of strategy updates. We use the martingale upcrossing inequality to show that under condition (a) of local consistency, we can construct a neighborhood of initial belief, which ensures that the repeatedly updated beliefs remain in a small neighborhood of the fixed point belief with high probability. Condition (b) further guarantees that strategy update is robust to local perturbations of strategies and beliefs. Importantly, we find that any complete information fixed point is locally stable, and thus is robust to local perturbations of belief and strategy (Proposition 2).

Our global and local stability analysis contributes to the study of stability of Nash equilibrium under various learning dynamics in games. In particular, previous literature has focused on the stability of evolutionary dynamics in population games (Smith and Price (1973); Taylor and Jonker (1978); Samuelson and Zhang (1992); Matsui (1992); Hofbauer and Sandholm (2009); Sandholm (2010a)), and more recently on adaptive learning dynamics in traffic routing (Dumett and Cominetti (2018)). Our results extend the equilibrium stability analysis in a complete information environment to the stability analysis on both the belief estimates and players’ strategies governed by the coupled belief-strategy dynamics.

The phenomenon that endogenous information acquisition leads to incomplete learning is central to a variety of settings that include multi-arm bandit problems (Auer et al. (2002); Cesa-Bianchi and Lugosi (2006); Lattimore and Szepesvári (2020)), endogenous social learning (Banerjee (1992); Gale and Kariv (2003); Golub and Jackson (2010); Acemoglu et al. (2014); Mossel et al. (2015)), and self-confirming equilibrium learning in extensive form games (Fudenberg and Levine (1993); Fudenberg and Kreps (1995)). In settings where the action space of each agent is finite, complete learning can be achieved when the decision maker randomly takes each action with small probability (Auer et al. (2002); Cesa-Bianchi and Lugosi (2006); Hart and Mas-Colell (2000)). In our setting, players have continuous strategy sets. Thus, it is unclear under what condition exploration is needed, and how random exploration can be used to achieve complete learning.

We focus on identifying conditions under which learning is complete without the need of exploration. We show that learning is complete if (i) the convergent fixed point assigns probability 1 to a single parameter, or (ii) the convergent fixed point belief is locally consistent, and the payoff function of each player is concave in their strategy for any parameter (Proposition 3). In case (i), we know that the single parameter with probability 1 is the true parameter, and the fixed point strategy is a complete information equilibrium. In case (ii), the fixed point belief does not identify the true parameter, but the local consistency condition ensures that the belief forms consistent estimate of payoffs in a local neighborhood of the fixed point strategy. Thus, each player’s strategy is a local best response to their opponents’ strategies. Additionally, the payoff concavity condition ensures that each player’s local best response is also the true best response strategy. Therefore, in case (ii), the fixed point strategy is a complete information Nash equilibrium even though the fixed point belief does not have complete information.

If the convergent fixed point does not satisfy (i) or (ii), then learning may not be complete, and exploration of strategies other than the fixed point strategy is needed to guarantee complete learning. If payoff functions in the game are concave (which is typically assumed in most applications), then local exploration – randomly taking strategies in a local neighborhood of the fixed point – is sufficient to identify the complete information equilibrium. This is because local exploration can exclude any parameter that does not form locally consistent payoff estimate, and eventually leads to a locally consistent belief so that condition (ii) for complete learning is satisfied.

The rest of the paper is organized as follows: Section 2 describes the learning model and Section 3 details our main results – convergence and stability analysis, and conditions for complete learning. We present the proofs of our main convergence and stability theorems in Section 4. In Section 5, we discuss the extensions of our results to learning with two timescales, learning in games with finite strategies, and learning with maximum a posteriori or least square estimates. We include the proofs of propositions and technical lemmas in Appendix A.

Our learning dynamics is induced by strategic players in a finite set $I$ who repeatedly play a game $G$ for an infinite number of stages. The players’ payoffs in game $G$ depend on an unknown parameter vector $s$ belonging to a finite set $S$. Players have access to an information system (or an aggregator) that repeatedly updates and broadcasts a belief estimate $\theta=\left(\theta(s)\right)_{s\in S}\in\Delta(S)$ to all players, where $\theta(s)$ denotes the estimated probability of parameter $s$.

In game $G$, the strategy of each player $i\in I$ is a finite-dimensional vector $q_{i}$ in a convex, closed and bounded strategy set $Q_{i}$. The players’ strategy profile is denoted $q=\left(q_{i}\right)_{i\in I}\in Q\stackrel{{\scriptstyle\Delta}}{{=}}\prod_{i\in I}Q_{i}$. The payoff of each player is realized randomly according to a probability distribution. The distribution of players’ payoffs $y=\left(y_{i}\right)_{i\in I}$ for any strategy profile $q\in Q$ and any parameter $s\in S$ is denoted by the probability density function $\phi^{s}(y|q)$. We assume that $\phi^{s}(y|q)$ is continuous in $q$ for all $s\in S$. Without loss of generality, we write the player $i$’s payoff $y_{i}$ for any $s\in S$ as the sum of an average payoff function $u^{s}_{i}(q)$ that is continuous in $q$ and a zero-mean noise term $\epsilon_{i}^{s}(q)$ that can be correlated across players:

We model our learning dynamics as a discrete-time stochastic process, with state comprising of belief estimate of the unknown parameter and the players’ strategies: In each stage $k\in\mathbb{N}_{+}$, the information platform broadcasts the current belief estimate $\theta^{k}$; the players act according to a strategy profile $q^{k}=\left(q^{k}_{i}\right)_{i\in I}$; and the payoffs $y^{k}=\left(y^{k}_{i}\right)_{i\in I}$ are realized according to $\phi^{s}(y^{k}|q^{k})$ when the parameter is $s\in S$. The state of the learning dynamics in stage $k$ is $\left(\theta^{k},q^{k}\right)\in\Delta(S)\times Q$.

The unknown true parameter is $s^{*}\in S$. We suppose that the initial belief $\theta^{1}$ does not exclude any possible parameter, i.e. $\theta^{1}(s)>0$ for all $s\in S$, and the initial strategy $q^{1}\in Q$ is feasible. The evolution of states $\left(\theta^{k},q^{k}\right)_{k=1}^{\infty}$ is jointly governed by belief and strategy updates as introduced next.

In our model, the belief and strategy updates ($\theta$-update) – ($q$-update) capture the dynamic interplay between Bayesian parameter learning and strategy learning in games. Specifically, since the distribution of $y^{k}$ depends on the strategy profile $q^{k}$ in each stage, the sequence of payoffs $(y^{k})_{k=1}^{\infty}$ is not identically and independently distributed when the strategies $(q^{k})_{k=1}^{\infty}$ are repeatedly updated. On the other hand, the strategy updates ($q$-update) depend on the repeatedly updated beliefs $(\theta^{k})_{k=1}^{\infty}$.

We note that the belief updates can occur less frequently than the strategy updates since the subsequence of belief update stages satisfy $k_{t+1}-k_{t}\geq 1$. In Sec. 3 – 4, we present our main results by considering that $k_{t+1}-k_{t}$ is finite with probability (w.p.) 1; i.e., both belief and strategy updates follow the same timescale. In Sec. 5, we show that all results analogously hold when $\lim_{t\to\infty}k_{t+1}-k_{t}=\infty$ w.p.1; that is when the belief is updated at a slower timescale compared to the strategy updates.

For any belief $\theta$, we denote $G(\theta)$ as the game with a static information environment, where each player $i$’s utility function is the expected utility $\mathbb{E}_{\theta}\left[u_{i}^{s}(q_{i},q_{-i})\right]=\sum_{s\in S}\theta(s)u_{i}^{s}(q_{i},q_{-i})$. Note that if the belief $\theta^{k}$ were held constant as $\theta$ for all $k$, then ($q$-update) simply becomes the corresponding strategy update $q^{k+1}=F_{i}(\theta,q^{k})$ in game $G(\theta)$. Since our goal is to analyze the joint evolution of both the beliefs and the strategies (instead of the properties of a particular strategy update in static information environment), we make the following two assumptions throughout the paper:

Assumption 1 ensures that the updated strategy is upper hemicontinuous in the belief and the strategy in the previous stage. Assumption 2 guarantees the convergence of strategies induced by updates under static information environment. Without Assumption 2, strategies may not converge even in the static information environment, and consequently the joint evolution of both the beliefs and the strategies also cannot be guaranteed to converge. Assumption 3 implies that when the game has multiple equilibria, each equilibrium is isolated, and the strategy update has a unique value in the local neighborhood of each equilibrium.

Our results and analysis approach hold for all types of strategy update ($q$-update) that satisfy Assumptions 1 – 3. For the sake of concreteness, we provide two examples of $F_{i}$ that are natural extension of widely studied strategy update rules:

1. 1.

   Belief-based best response dynamics. We define the best response correspondence of each player $\mathrm{BR}_{i}(\theta^{k+1},q^{k}_{-i})\stackrel{{\scriptstyle\Delta}}{{=}}\operatorname*{arg\,max}_{q_{i}\in Q_{i}}\sum_{s\in S}\theta^{k+1}(s)u_{i}^{s}(q_{i},q^{k}_{-i})$ as the set of strategies that maximize their expected utility given the opponents’ strategies $q^{k}_{-i}$ and the updated belief $\theta^{k+1}$. The strategy is updated following any one of the following dynamics: (Simultaneous-BR) – each player chooses a best response strategy; (Sequential-BR) – players sequentially update their strategies as the best response; (Inertial-BR) – each player updates their strategy as a linear combination of their current strategy and a best response strategy.

   	$\displaystyle F_{i}(\theta^{k+1},q^{k})$	$\displaystyle=\mathrm{BR}_{i}(\theta^{k+1},q^{k}_{-i}),\quad\forall i\in I,\quad\forall k.$		(Simultaneous-BR)
   	$\displaystyle F_{i}(\theta^{k+1},q^{k})$	$\displaystyle=\left\{\begin{array}[]{ll}\mathrm{BR}_{i}(\theta^{k+1},q^{k}_{-i}),&\quad\text{if }k~{}\text{mod}~{}|I|=i,\\ q_{i}^{k},&\quad\text{otherwise}.\end{array}\right.$		(Sequential-BR)
   	$\displaystyle F_{i}(\theta^{k+1},q^{k})$	$\displaystyle=(1-\alpha^{k})q_{i}^{k}+\alpha^{k}\mathrm{BR}_{i}(\theta^{k+1},q^{k}_{-i}),\quad\forall i\in I,\quad\forall k,$		(Inertial-BR)

   where $\alpha^{k}\in[0,1]$ in (Inertial-BR) for each $k$.

2. 2.

   Belief-based no-regret learning. Given the updated belief $\theta^{k+1}$, and the current strategy profile $q^{k}$, the updated strategy $q^{k+1}$ is given by:

   $\displaystyle q_{i}^{k+1}=\operatorname*{arg\,max}_{q_{i}\in Q_{i}}\{\left(x_{i}^{k+1}\right)^{T}\cdot q_{i}-h_{i}(q_{i})\},\quad\forall i\in I,\quad\forall k,$

   (No-regret)

   where the function $h_{i}:Q_{i}\to\mathbb{R}$ is a regularizer that is continuous and strongly convex in $q_{i}$²²2The function $h$ is strongly convex if there exists $A>0$ such that $h(\lambda q+(1-\lambda)q^{\prime})\leq\lambda h(q)+(1-\lambda)h(q^{\prime})-(1/2)A\lambda(1-\lambda)\|q-q^{\prime}\|^{2}$ for all $q,q^{\prime}\in Q$ and all $\lambda\in[0,1]$, and $(x_{i}^{k})_{k=1}^{\infty}$ is a sequence of each player $i$’s scores such that $x_{i}^{1}=q_{i}^{1}$, and

   $\displaystyle x_{i}^{k+1}=x_{i}^{k}+\alpha^{k}\left(\sum_{s\in S}\theta^{k+1}(s)\frac{\partial u_{i}^{s}(q^{k})}{\partial q_{i}^{k}}\right),\quad\forall i\in I,\quad\forall k.$

   That is, the initial score of player $i$ is the same with the strategy $q^{1}_{i}$, and the score in each step is updated using gradient ascent without regard to the feasibility constraint imposed by strategy set $Q_{i}$. In particular, the gradient vector is the gradient of the expected utility function $\partial\mathbb{E}_{\theta^{k+1}}[u_{i}^{s}(q^{k})]/\partial q_{i}^{k}=\sum_{s\in S}\theta^{k+1}(s)\frac{\partial u_{i}^{s}(q^{k})}{\partial q_{i}^{k}}$ based on the updated belief $\theta^{k+1}$.³³3Our belief-based no-regret learning estimates the gradient of the expected utility function $\mathbb{E}_{\theta}[u_{i}^{s}(q)]$ based on the belief $\theta$ and the parametrized utility function $u_{i}^{s}(q)$. When the belief $\theta$ does not have complete information of the true parameter $s^{*}$, the estimated gradient is different from the gradient of the true utility function $u_{i}^{s^{*}}(q)$. As the belief converges, the estimated gradient becomes unbiased of the true gradient.

   Then, the updated strategy $q^{k+1}$ is a feasible strategy profile in $Q$ that minimizes the inner product between the strategy and the updated score vector $x^{k+1}=(x_{i}^{k+1})_{i\in I}$ plus the value of the regularizer. A common example of such regularizer is $h_{i}(q_{i})=(1/2)\|q_{i}\|^{2}$. In this case, the updated strategy is the projection of the score vector $x^{k+1}$ onto the feasible strategy set; i.e. $q_{i}^{k+1}=\operatorname*{arg\,min}_{q_{i}\in Q_{i}}\|q_{i}-x_{i}^{k+1}\|^{2}$. Thus, the strategy update follows a projected gradient ascent algorithm based on the updated belief for each player.

We note that Assumption 1 is satisfied by the belief-based best response learning and the belief-based no-regret learning when the utility function $u_{i}^{s}(q)$ is continuously differentiable with respect to $q$ for all $i\in I$ and all $s\in S$.⁴⁴4Following the Berge’s maximum theorem, for any $\theta\in\Delta(S)$, any $i\in I$ and any $q_{-i}\in Q_{-i}$, $\mathrm{BR}(\theta,q_{-i})$ is upper-hemicontinuous in $\theta$ and $q_{-i}$. Therefore, the three types of belief-based best response updates satisfy Assumption 1. Additionally, when the utility function $u_{i}^{s}(q)$ is continuously differentiable with respect to $q$ for any $s\in S$ and any $i\in I$, the updated belief given by (No-regret) is also upper-hemicontinuous in $\theta$ and $q$. From the extensive literature in learning in games (Fudenberg and Kreps (1993); Sandholm (2010b)), we know that convergence of strategy updates to equilibrium is not guaranteed in arbitrary games even under static information environment. In Table 1, we provide a list of games in which the strategy updates with the two examples of learning rules satisfy Assumption 2. Our results, as discussed next, hold for any ($q$-update) satisfying the two assumptions.

Sec. 3.1 presents the convergence of beliefs and strategies. Sec. 3.2 analyzes the local and global stability properties of fixed points. Sec. 3.3 focuses on conditions for learning to converge to equilibrium with complete information, and Sec. 3.4 illustrates our results through examples. We focus on presenting the results and explaining the intuition in this section. We defer the proofs of Theorems to Sec. 4, and the proofs of Propositions to Appendix A.