# Multi-agent Bayesian Learning with Best Response Dynamics: Convergence and
Stability††thanks: This version: August, 2021.

Manxi Wu, Saurabh Amin, and Asuman Ozdaglar M. Wu is with the Institute for
Data, Systems, and Society, S. Amin is with Laboratory for Information and
Decision Systems, A. Ozdaglar is with Department of Electrical Engineering and
Computer Science, Massachusetts Institute of Technology (MIT), Cambridge, MA,
USA, {manxiwu, amins<EMAIL_ADDRESS>
###### Abstract

We study learning dynamics induced by strategic agents who repeatedly play a
game with an unknown payoff-relevant parameter. In this dynamics, a belief
estimate of the parameter is repeatedly updated given players’ strategies and
realized payoffs using Bayes’s rule. Players adjust their strategies by
accounting for best response strategies given the belief. We show that, with
probability 1, beliefs and strategies converge to a fixed point, where the
belief consistently estimates the payoff distribution for the strategy, and
the strategy is an equilibrium corresponding to the belief. However, learning
may not always identify the unknown parameter because the belief estimate
relies on the game outcomes that are endogenously generated by players’
strategies. We obtain sufficient and necessary conditions, under which
learning leads to a globally stable fixed point that is a complete information
Nash equilibrium. We also provide sufficient conditions that guarantee local
stability of fixed point beliefs and strategies.

Keywords— Learning in games, Bayesian learning, Stochastic dynamics, Stability
analysis

##  1 Introduction

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 study learning dynamics that captures this joint evolution
in a game-theoretic setting. In our model, strategic agents (players)
repeatedly play a game with an unknown payoff-relevant parameter vector
belonging to a finite set. A public information system (e.g. a market platform
or navigation app) updates and broadcasts an estimate of the payoff parameter
based on stage-wise game outcomes (i.e. strategies and randomly realized
payoffs) to all players. The players’ strategies in the next stage are given
by a best response update rule based on the most current belief update. We
consider three types of best response updates: _Simultaneous best response_ :
each player best responds to their opponents’ current strategy; _Sequential
best response_ : players take turns to update their strategies in each stage;
and _Inertial best response_ : the updated strategy is a linear combination of
the current strategy and a best response strategy based on the updated belief.

We focus on analyzing the long-run outcomes – convergence and stability
properties (both local and global) – of the beliefs and strategies induced by
the interplay of Bayesian updates and best response dynamics. We also identify
conditions under which this learning dynamics converges to a complete
information Nash equilibrium. Moreover, our technical results are useful to
study other types of learning dynamics, such as learning under fast (resp.
slow) strategy (resp. belief) updates, and learning under non-Bayesian
estimates of the unknown parameter.

Our model of learning dynamics leads to extension of results on learning in
games with complete information to situations when long-run outcomes depend on
learning of an unknown parameter. Past literature has addressed convergence
analysis of discrete and continuous time 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)) in complete information environment. The stability properties of
learning dynamics have also been studied in games with complete information
(Samuelson and Zhang (1992); Samuelson (1994); Sandholm (2010)). The key
distinction between our learning dynamics and classical best response dynamics
is that, in our model, players are imperfectly informed about the payoff-
relevant parameter, and their strategy updates in each stage rely on the
updated Bayesian belief. Our main contribution, as summarized next, is a new
approach to study the convergence and stability properties of this learning
dynamics.

Convergence: We prove that the beliefs and strategies in our learning dynamics
converge to a fixed point with probability 1 (Theorem 1). Convergence is
guaranteed under the condition that the best response dynamics converges in
the game when the unknown parameter is constant instead of being repeatedly
updated. This condition is satisfied in a variety of games, including
potential games, zero-sum games and dominance solvable games. On the other
hand, non-convergence can be easily demonstrated in games when this condition
does not hold: if the strategies do not converge in a game with a constant
belief, then natually they also fail to converge when the beliefs are
repeatedly updated.

Furthermore, at any fixed point, the belief consistently estimates the
probability distribution of players’ payoffs given the fixed point strategy
and the fixed point strategy is an equilibrium of the game corresponding to
the belief. When the true parameter is identifiable at equilibrium (i.e. no
other parameter induces the same payoff distribution), the learning dynamics
converges to a complete information equilibrium (Proposition 1). Otherwise,
the fixed point belief may assign a non-zero probability to other parameters
that lead to an incorrect payoff estimate for strategies that differ from the
fixed point. Consequently, a fixed point strategy attained by the learning
dynamics may not be a complete information equilibrium.

The notion of fixed point in our learning dynamics is similar to the self-
confirming equilibrium introduced in Fudenberg and Levine (1993a) for
extensive-form games.111Similar concepts include conjectural equilibrium in
Hahn (1978) and subjective equilibrium in Kalai and Lehrer (1993b) and Kalai
and Lehrer (1995). At a self-confirming equilibrium, players maintain
consistent beliefs of their opponents’ strategies at information sets that are
reached, but the beliefs of strategies can be incorrect at unreached
information sets. Similarly, in our model, a fixed point can be different from
a complete information equilibrium due to the incorrect estimates on the
unobserved game outcomes formed by the beliefs (i.e., the estimated payoff
distributions of strategies that differ from the fixed point may not be
consistent). In general, these incorrect estimates may never be corrected by
the learning dynamics because information of game outcomes is endogenously
acquired based on the chosen strategies in each stage.222The phenomenon that
endogenous information acquisition leads to incomplete learning is also
central to multi-arm bandit problems Rothschild (1974); Easley and Kiefer
(1988) and endogenous social learning Duffie et al. (2009); Acemoglu et al.
(2014); Ali (2018).

Notably, multiple models have been proposed as learning foundations for self-
confirming equilibrium (Fudenberg and Kreps (1993), Fudenberg and Levine
(1993b), Kalai and Lehrer (1993a) and Kalai and Lehrer (1995)). These models
typically analyze how players maximize the present value of future payoffs in
each stage of a repeated game with a fixed discount factor while updating the
subjective beliefs of the opponents’ strategies. Our learning model focuses on
players’ best response decisions that maximize their utilities based on the
up-to-date knowledge of the payoff distribution and the opponents’ strategies.

The proof of our convergence result uses techniques from statistical learning
theory and analysis of best response dynamics in complete information games.
Firstly, we obtain the convergence of Bayesian beliefs by applying the
martingale convergence theorem. Secondly, thanks to the convergence of
beliefs, we prove that the sequence of strategies induced by the learning
dynamics with repeated belief updates converge to an auxiliary sequence of
strategies that is constructed based on the convergent fixed point belief.
Since the auxiliary strategy sequence converges to an equilibrium
corresponding to the fixed point belief, we obtain that the original strategy
sequence must also converge to the same fixed point equilibrium. Finally,
using the strategy convergence result, we prove that the players’ payoff
distributions asymptotically approaches the identical and independent
distribution generated using 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.

Our convergence result also contributes to the extensive literature on other
types of learning dynamics: 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)), payoff-based learning (Cominetti et al. (2010),
Marden et al. (2009b)), replicator dynamics (Beggs (2005), Hopkins (2002)),
and learning in large anonymous games (Kash et al. (2011); Adlakha and Johari
(2013)). These dynamics typically prescribe the manner in which the players
adjust their strategies based on the randomly realized payoffs in each stage.
On the other hand, the strategy updates in our learning dynamics capture a
rational behavioral adjustment of players in an imperfect information
environment.

Stability: We define a fixed point to be _globally stable_ if the learning
dynamics starting from any initial state converges to that fixed point with
probability 1. A fixed point is _locally stable_ if the states remain close to
the fixed point with high probability when the learning dynamics starts with
an initial state close to that fixed point. These stability notions apply to
the coupled belief-strategy dynamics in a game theoretic setting.333Frick et
al. (2020) defined a similar stability notion for Bayesian beliefs of a
utility-maximizing decision maker in a misspecified learning dynamics. In
their problem, the unknown parameters can be ordered and information is
endogenously acquired by the decision maker. We do not consider
misspecification in our learning model. Our local stability notion is defined
for the fixed point state (comprising of belief and equilibrium strategy)
under the coupled updates of Bayesian beliefs and best response strategies in
a game-theoretic setting.

We find that globally stable fixed points exist if and only if all fixed
points have complete information of the unknown parameter (Proposition 2).
This condition is equivalent to the environment in which the true parameter is
identifiable for any equilibrium strategy profile. In this case, all players
eventually learn the true parameter and choose the complete information
equilibrium.

If the condition for global stability is not satisfied, then there exist
multiple fixed points and convergent fixed point depends on the initial state.
In this case, we need to analyze the local stability property of a fixed
point, which entails studying conditions under which the states of learning
dynamics after local perturbations remains close to the fixed point with a
high probability.

In Theorem 2, we prove that a fixed point is locally stable if it satisfies
three conditions: _(a)_ Fixed point strategy is _locally upper-hemicontinuous_
in the belief; _(b)_ Fixed point has a local neighborhood that is an
_invariant set_ for the best response updates; _(c)_ 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).

Previously, local stability of Nash equilibrium has been studied in games with
complete information for both best response dynamics and evolutionary dynamics
(Smith and Price (1973); Taylor and Jonker (1978); Samuelson and Zhang (1992);
Matsui (1992); Hofbauer and Sandholm (2009); Sandholm (2010)). We provide
sufficient conditions that extend previous results to ensure stability of
fixed point under local perturbations of the coupled belief-strategy dynamics.
In particular, by using the martingale upcrossing inequality, we show that
condition _(c)_ of local consistency ensures that the repeatedly updated
beliefs remain in a small neighborhood of the fixed point belief with high
probability. Additionally, condition _(b)_ extends the local invariance
condition in complete information environment to further require that best
response dynamics does not leave a local neighborhood of the fixed point under
local perturbations of both the strategy and belief. Finally, condition _(a)_
of local upper-hemicontinuity ensures that the convergent strategy remains
close to the fixed point as long as the belief is also close to the fixed
point belief. Thus, local stability of a fixed point is guaranteed under
conditions _(a)_ – _(c)_.

Next, we present our model and results in games with continuous strategy set:
Section 2 describes the learning model and Section 3 details the convergence
and stability properties. In Section 4, we discuss the extensions of our main
results to other types of learning dynamics such as two-timescale learning,
learning in games with finite strategies, and learning with maximum a
posteriori or least square estimates.

##  2 Model of Learning Dynamics in Continuous Games

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$. The true parameter is denoted $s^{*}\in S$. Learning is
mediated by a public 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 and continuous 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.
Specifically, 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
represented 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 $u^{s}_{i}(q)$ that is a continuous function of $q$
and a noise term $\epsilon_{i}^{s}(q)$ with zero mean:

$\displaystyle y_{i}=u^{s}_{i}(q)+\epsilon_{i}^{s}(q).$ (1)

The noise terms $\left(\epsilon_{i}^{s}(q)\right)_{i\in I}$ can be correlated
across players.

In game $G$ with belief $\theta$, each player $i$’s best response
correspondence given their opponents’ strategies
$q_{-i}=\left(q^{j}\right)_{j\in I\setminus\\{i\\}}$ is the set of strategies
that maximize their expected utility, i.e. $\mathrm{BR}_{i}(\theta,q_{-i})$
$\stackrel{{\scriptstyle\Delta}}{{=}}\operatorname*{arg\,max}_{q_{i}\in
Q_{i}}\mathbb{E}_{\theta}\left[u_{i}^{s}(q_{i},q_{-i})\right]=\operatorname*{arg\,max}_{q_{i}\in
Q_{i}}\sum_{s\in S}\theta(s)u_{i}^{s}(q_{i},q_{-i})$. Additionally, the set of
equilibrium strategies for any belief $\theta$ is a non-empty set
$\mathrm{EQ}(\theta)$.

Our learning model can be specified as a discrete-time stochastic dynamics,
with state comprising of the belief estimate of unknown parameter and the
players’ strategies: In each stage $k\in\mathbb{N}_{+}$, the information
system 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 learning
dynamics in stage $k$ is $\left(\theta^{k},q^{k}\right)\in\Delta(S)\times Q$.

The initial belief $\theta^{1}$ in our learning dynamics 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, which we introduce next.

Belief update. In our model, the belief is updated intermittently and
infinitely. The stages at which the information system updates the belief can
be deterministic or random, denoted by the subsequence
$\left(k_{t}\right)_{t=1}^{\infty}$. In update stage $k_{t+1}$, the previous
belief estimate $\theta^{k_{t}}$ is updated using players’ strategy profiles
$\left(q^{k}\right)_{k=k_{t}}^{k_{t+1}-1}$ and realized payoffs
$\left(y^{k}\right)_{k=k_{t}}^{k_{t+1}-1}$ between the stages $k_{t}$ and
$k_{t+1}$ according to the Bayes’ rule:

$\displaystyle\theta^{k_{t+1}}(s)$
$\displaystyle=\frac{\theta^{k_{t}}(s)\prod_{k=k_{t}}^{k_{t+1}-1}\phi^{s}(y^{k}|q^{k})}{\sum_{s^{\prime}\in
S}\theta^{k_{t}}(s^{\prime})\prod_{k=k_{t}}^{k_{t+1}-1}\phi^{s^{\prime}}(y^{k}|q^{k})},\quad\forall
s\in S.$ ($\theta$-update)

Strategy update. Players update their strategies in each stage based on the
updated belief and the current strategies played by their opponents. Given any
$\theta^{k+1}$ and any $q^{k}_{-i}=\left(q^{k}_{j}\right)_{j\in
I\setminus\\{i\\}}$, we generically denote the strategy update for each $i\in
I$ as a set-valued function
$F_{i}\left(\theta^{k+1},q^{k}_{-i}\right):\Delta\left(S\right)\times
Q_{-i}\rightrightarrows Q_{i}$:

$\displaystyle q_{i}^{k+1}\in
F_{i}\left(\theta^{k+1},q^{k}_{-i}\right),\quad\forall i\in I.$ ($q$-update)

In particular, we consider the following three types of best response update
rules for $F_{i}$:

  1. 1.

_Simultaneous best response dynamics._ Each player chooses a strategy that is
in the best response correspondence given their opponents’ strategies and the
updated belief:

$\displaystyle
F_{i}(\theta^{k+1},q^{k}_{-i})=\mathrm{BR}_{i}(\theta^{k+1},q^{k}_{-i}),\quad\forall
i\in I.$ (Simultaneous-BR)

  2. 2.

_Sequential best response dynamics._ In each stage, exactly one player updates
their strategy as the best response strategy given the new belief. Players
sequentially updates their strategies:

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

  3. 3.

_Linear best response dynamics._ Each player updates their strategy as a
linear combination of their current strategy and a best response strategy
given the updated belief:

$\displaystyle F_{i}(\theta^{k+1},q^{k}_{-i})$
$\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,$ (Linear-BR)

where $\alpha^{k}\in[0,1]$ is the rate of strategy update in stage $k$.

Next, we present few remarks about our learning dynamics: Firstly, players are
strategic in that their strategy updates utilize a best response strategy that
maximizes their expected utilities given the latest belief estimate of the
unknown parameter and the strategies played by their opponents. If all players
know the true parameter $s^{*}$, then the three strategy updates reduce to the
classical best response dynamics in the corresponding game with complete
information.

Secondly, the three types of strategy updates differ in the timing and the
extent at which best response is incorporated in the updated strategy: All
players update their strategies in every stage in (Simultaneous-BR) and
(Linear-BR), while only one player updates strategy in (4). While players
entirely adopt the new best response strategy in updates of (Simultaneous-BR)
and (4), in (Linear-BR) each player weighs their best response strategy
according to the strategy update rate.

Thirdly, 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$. Here, we assume 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. 4, we extend our analysis to the case when belief updates
occur at a slower timescale in comparison to strategy updates, i.e.
$\lim_{t\to\infty}k_{t+1}-k_{t}=\infty$.

Fourthly, our learning dynamics considers games with continuous utility
functions and strategy sets. In Sec. 4, we show that our convergence and
stability results also apply to learning the unknown parameter in games with
finite action (pure strategy) set, where players choose mixed strategies. As a
special case, for games with finite strategies, the linear best response
dynamics (Linear-BR) with update rates $\alpha^{k}=\frac{1}{k}$ for all $k$ is
equivalent to fictitious play with repeatedly updated belief estimates.
Finally, in Sec. 4, we also argue that our results hold under other types of
parameter estimates such as the maximum a posteriori (MAP) estimate, and the
ordinary least square (OLS) estimate.

##  3 Main Results

###  3.1 Convergence

Before introducing our convergence result, we introduce two necessary
definitions.

######  Definition 1 (Kullback–Leibler (KL)-divergence).

For a strategy profile $q\in Q$, the KL divergence between the payoff
distribution with parameters $s$ and $s^{*}\in S$ is defined as:

$\displaystyle
D_{KL}\left(\phi^{s^{*}}(y|q)||\phi^{s}(y|q)\right)\stackrel{{\scriptstyle\Delta}}{{=}}\left\\{\begin{array}[]{ll}\int_{y}\phi^{s^{*}}(y|q)\log\left(\frac{\phi^{s^{*}}(y|q)}{\phi^{s}(y|q)}\right)dy,&\quad\text{if
$\phi^{s^{*}}(y|q)\ll\phi^{s}(y|q)$},\\\
\infty&\quad\text{otherwise.}\end{array}\right.$

Here $\phi^{s^{*}}(y|q)\ll\phi^{s}(y|q)$ means that the distribution
$\phi^{s^{*}}(y|q)$ is absolutely continuous with respect to $\phi^{s}(y|q)$,
i.e. $\phi^{s}(y|q)=0$ implies $\phi^{s^{*}}(y|q)=0$ w.p. 1.

######  Definition 2 (Payoff-equivalent parameters).

A parameter $s\in S$ is payoff-equivalent to the true parameter $s^{*}$ for a
strategy $q\in Q$ if $D_{KL}\left(\phi^{s^{*}}(y|q)||\phi^{s}(y|q)\right)=0$.
For a given strategy profile $q\in Q$, the set of parameters that are payoff-
equivalent to $s^{*}$ is defined as:

$\displaystyle
S^{*}(q)\stackrel{{\scriptstyle\Delta}}{{=}}\\{S|D_{KL}\left(\phi^{s^{*}}(y|q)||\phi^{s}(y|q)\right)=0\\}.$

The KL-divergence between any two distributions is non-negative, and is equal
to zero if and only if the two distributions are identical. For a given
strategy profile $q$, if a parameter $s$ is in the payoff-equivalent parameter
set $S^{*}(q)$, then the payoff distribution is identical for parameters $s$
and $s^{*}$, i.e. $\phi^{s^{*}}(y|q)=\phi^{s}(y|q)$ for all $y$. In this case,
realized payoffs cannot be used by the information system to distinguish $s$
and $s^{*}$ in the belief update ($\theta$-update) (since the belief ratio
$\frac{\theta^{k}(s)}{\theta^{k}(s^{*})}$ remains unchanged w.p. 1). Also note
that the set $S^{*}(q)$ can vary with strategy profile $q$, and hence a
payoff-equivalent parameter for a given strategy profile may not be payoff-
equivalent for another strategy profile.

We need the following assumption on the strategy updates.

######  Assumption 1.

For any initial strategy $q^{1}$, the sequence of strategies induced by
($q$-update) under any constant belief
$\theta^{k}=\theta\in\Delta\left(S\right)$ for all $k$ converges to an
equilibrium strategy profile in $\mathrm{EQ}(\theta)$.

This assumption requires that the strategy updates converge to an equilibrium
strategy when the belief is held constant (instead of being repeatedly
updated). Without this assumption, strategies may fail to converge even in
games with complete information (Shapley (1964)). Thus, Assumption 1 is a
basic requirement to guarantee the convergence of states in our learning
dynamics.

Assumption 1 is satisfied by the best response dynamics (Simultaneous-BR), (4)
and (Linear-BR) in a variety of games with complete information, including
potential games, zero sum games, and dominance solvable games (Milgrom and
Roberts (1990); Monderer and Shapley (1996b); Hofbauer and Sorin (2006),
Fudenberg and Kreps (1993); Monderer and Shapley (1996a)). Under Assumption 1,
the sequence of states (beliefs and strategies) induced by our stochastic
learning dynamics converges to a fixed point.

######  Theorem 1.

For any initial state $(\theta^{1},q^{1})\in\Delta(S)\times Q$, under
Assumption 1, the sequence of states $(\theta^{k},q^{k})_{k=1}^{\infty}$
induced by ($\theta$-update) and ($q$-update) converges to a fixed point
$(\bar{\theta},\bar{q})$ w.p. 1, and $\left(\bar{\theta},\bar{q}\right)$
satisfies:

$\displaystyle[\bar{\theta}]$ $\displaystyle\subseteq S^{*}(\bar{q}),$ (5a)
$\displaystyle\bar{q}$ $\displaystyle\in\mathrm{EQ}(\bar{\theta}),$ (5b)

where
$[\bar{\theta}]\stackrel{{\scriptstyle\Delta}}{{=}}\\{S|\bar{\theta}(s)>0\\}$,
and $\mathrm{EQ}(\bar{\theta})$ is the set of equilibrium strategies
corresponding to belief $\bar{\theta}$.

Moreover, for any $s\in S\setminus S^{*}(\bar{q})$, if
$\phi^{s^{*}}(y|\bar{q})\ll\phi^{s}(y|\bar{q})$, then $\theta^{k}(s)$
converges to 0 exponentially fast:

$\displaystyle\lim_{k\to\infty}\frac{1}{k}\log(\theta^{k}(s))=-D_{KL}(\phi^{s^{*}}(y|\bar{q})||\phi^{s}(y|\bar{q})),\quad
w.p.~{}1.$ (6)

Otherwise, there exists a positive integer $K^{*}<\infty$ such that
$\theta^{k}(s)=0$ for all $k>K^{*}$ w.p. 1.

From Theorem 1, the following properties must hold at a fixed point
$\left(\bar{\theta},\bar{q}\right)$:

  * (1)

Belief $\bar{\theta}$ identifies the true parameter $s^{*}$ in the payoff-
equivalent set $S^{*}(\bar{q})$ corresponding to fixed point strategy
$\bar{q}$. Therefore, the belief forms a consistent estimate of the payoff
distribution at the fixed point. To see this, let us denote the estimated
payoff distribution as $\mu(y|\bar{\theta},\bar{q})$. Then,

$\displaystyle\mu(y|\bar{\theta},\bar{q})\stackrel{{\scriptstyle\Delta}}{{=}}\sum_{s\in
S}\bar{\theta}(s)\phi^{s}(y|\bar{q})\stackrel{{\scriptstyle\eqref{eq:exclude_distinguished}}}{{=}}\sum_{s\in
S^{*}(\bar{q})}\bar{\theta}(s)\phi^{s}(y|\bar{q})=\sum_{s\in
S^{*}(\bar{q})}\bar{\theta}(s)\phi^{s^{*}}(y|\bar{q})=\phi^{s^{*}}(y|\bar{q}).$
(7)

  * (2)

Players have no incentive to deviate from fixed point strategy profile
$\bar{q}$ because it is an equilibrium of the game $G$ with fixed point belief
$\bar{\theta}$.

We prove Theorem 1 in three steps: Firstly, we prove that the sequence of
beliefs $\left(\theta^{k}\right)_{k=1}^{\infty}$ converges to a fixed point
belief $\bar{\theta}\in\Delta\left(S\right)$ w.p. 1 by applying the martingale
convergence theorem (Lemma 1). Secondly, we show that under Assumption 1, the
strategies $\left(q^{k}\right)_{k=1}^{\infty}$ in our learning dynamics with
belief updates also converge. This convergent strategy is an equilibrium
corresponding to the belief $\bar{\theta}$ (Lemma 2). Finally, we prove that
the belief of any $s\in S$ that is not payoff-equivalent to $s^{*}$ given
$\bar{q}$ must converge to $0$ with rate of convergence governed by (6) (Lemma
3). Hence, we can conclude that beliefs and strategies induced by the learning
dynamics converge to a fixed point $\left(\bar{\theta},\bar{q}\right)$ that
satisfies (5) w.p. 1. The formal proofs of Lemmas 1 – 3 are in Appendix A.

######  Lemma 1.

$\lim_{k\to\infty}\theta^{k}=\bar{\theta}$ w.p. 1, where
$\bar{\theta}\in\Delta(S)$.

To prove this property, we note that the subsequences of the belief ratios
$\left(\frac{\theta^{k_{t}}(s)}{\theta^{k_{t}}(s^{*})}\right)_{t=1}^{\infty}$
is a martingale for all $s\in S$, and
$\left(\theta^{k_{t}}(s^{*})\right)_{t=1}^{\infty}$ is a sub-martingale. From
the martingale convergence theorem,
$\left(\frac{\theta^{k_{t}}(s)}{\theta^{k_{t}}(s^{*})}\right)_{t=1}^{\infty}$
and $\left(\theta^{k_{t}}(s^{*})\right)_{t=1}^{\infty}$ converge w.p. 1. Thus,
the belief subsequence $\left(\theta^{k_{t}}\right)_{t=1}^{\infty}$ converges
to a fixed point belief $\bar{\theta}$ w.p. 1. Since
$\theta^{k}=\theta^{k_{t}}$ for any $k=k_{t},\dots,k_{t+1}-1$, the sequence
$\left(\theta^{k}\right)_{k=1}^{\infty}$ must also converge to $\bar{\theta}$.

######  Lemma 2.

Under Assumption 1, $\lim_{k\to\infty}q^{k}=\bar{q}$ w.p. 1, where $\bar{q}$
satisfies (5b).

In the proof of Lemma 2, for each stage $K=1,2,\dots$, we construct an
auxiliary strategy sequence $\left(\hat{q}^{k}\right)_{k=1}^{\infty}$ such
that the strategies in this sequence are identical to that in the original
sequence up to a certain stage $K$ (i.e. $\hat{q}^{k}=q^{k}$ for all
$k=1,\dots,K$), and the remaining strategies
$\left(\hat{q}^{k}\right)_{k=K+1}^{\infty}$ are induced by the best response
update with the fixed point belief $\bar{\theta}$ (instead of the repeatedly
updated belief sequence $\left(\theta^{k}\right)_{k=K+1}^{\infty}$). Under
Assumption 1, the auxiliary strategy sequence must converge to an equilibrium
$\bar{q}\in\mathrm{EQ}(\bar{\theta})$. Recall from Lemma 1, the beliefs
converge to $\bar{\theta}$. Moreover, since the expected utility function
$\mathbb{E}_{\theta}\left[u_{i}^{s}(q)\right]$ of each player $i\in I$ is
continuous in $\theta$ and $q$, we know from the Berge’s maximum theorem that
the best response correspondence $\mathrm{BR}_{i}\left(\theta,q\right)$ is
upper hemicontinuous in $\theta$ and $q$ (Lemma 7 in Appendix A). Thus, we can
prove that as $K\to\infty$, the distance between the auxiliary strategy
sequence and the original strategy sequence converges to zero, which implies
that the original strategy sequence $\left(q^{k}\right)_{k=1}^{\infty}$ also
converges to $\bar{q}\in\mathrm{EQ}(\bar{\theta})$ (i.e. $\bar{q}$ satisfies
(5b)).

######  Lemma 3.

Any fix point $\left(\bar{\theta},\bar{q}\right)$ satisfies (5a). Furthermore,
for any $s\in S\setminus S^{*}(\bar{q})$, if
$\phi^{s^{*}}(y|\bar{q})\ll\phi^{s}(y|\bar{q})$, then $\theta^{k}(s)$
satisfies (6). Otherwise, there exists a finite positive integer $K^{*}$ such
that $\theta^{k}(s)=0$ for all $k>K^{*}$ w.p. 1.

Lemma 3 is based on Lemmas 1 and 2. Although the data of the realized payoffs
$\left(y^{k}\right)_{k=1}^{\infty}$ is not independently and identically
distributed (i.i.d.) due to players’ strategy updates, we can show that since
$q^{k}$ converge to $\bar{q}$ (Lemma 2), the distribution of $y^{k}$ converges
to an i.i.d. process with $\phi^{s}(y^{k}|\bar{q})$, which is the payoff
distribution given the fixed point strategy $\bar{q}$, for each parameter $s$
as $k\to\infty$.

Finally, if the payoff distribution for the true parameter is absolutely
continuous with respect to any non-payoff-equivalent parameter $s\in
S\setminus S^{*}(\bar{q})$, then we show that the log-likelihood ratio
$\log\left(\frac{\theta^{k}(s)}{\theta^{k}(s^{*})}\right)$ converges to
$-\infty$ with an exponential rate given by the (non-zero) KL-divergence
between the distributions of realized payoff under parameters $s$ and $s^{*}$.
Thus, the belief $\theta^{k}(s)$ converges to zero exponentially fast as in
(6). On the other hand, if $\phi^{s}(y|\bar{q})$ is not absolutely continuous
with the true distribution $\phi^{s^{*}}\left(y|\bar{q}\right)$, then we can
find a small neighborhood of $\bar{q}$ such that, with positive probability,
the realized payoff $y$ satisfies $\phi^{s}(y|q)=0$ but $\phi^{s*}(y|q)>0$ for
$q$ in this neighborhood. In this case, the belief update ($\theta$-update)
will assign probability 0 to the parameter $s$. From the Borel–Cantelli lemma,
the probability that $\theta^{k}(s)$ remains positive infinitely often is
zero. Hence, there must exist a finite stage $K^{*}$, after which
$\theta^{k}(s)$ remains to be zero with probability 1.

Complete information fixed points. From (5), we define the set of fixed points
$\Omega$ as follows:

$\displaystyle\Omega\stackrel{{\scriptstyle\Delta}}{{=}}\left\\{\left(\bar{\theta},\bar{q}\right)\left|[\theta]\subseteq
S^{*}\left(\bar{q}\right),~{}\bar{q}\in\mathrm{EQ}(\bar{\theta})\right.\right\\}.$
(8)

We denote the belief vector $\theta^{*}$ with $\theta^{*}(s^{*})=1$ as the
_complete information belief_ , and any strategy
$q^{*}\in\mathrm{EQ}(\theta^{*})$ as a _complete information equilibrium_.
Since $[\theta^{*}]=\\{s^{*}\\}\subseteq S^{*}(q^{*})$, the state
$\left(\theta^{*},q^{*}\right)$ is always a fixed point (i.e.
$\left(\theta^{*},q^{*}\right)\in\Omega$), and has the property that all
players have complete information of the true parameter $s^{*}$ and choose a
complete information equilibrium. Therefore, we refer to
$\left(\theta^{*},q^{*}\right)$ as a _complete information fixed point_.

Additionally, the set $\Omega$ may contain other fixed points
$\left(\bar{\theta},\bar{q}\right)$ that are not equivalent to the complete
information environment, i.e. $\bar{\theta}\neq\theta^{*}$. Such belief
$\bar{\theta}$ must assign positive probability to at least one parameter
$s\neq s^{*}$. The property (5a) ensures that $s$ is payoff-equivalent to
$s^{*}$ given the fixed point strategy profile $\bar{q}$, and hence the
average payoff function in (1) satisfies
$u^{s}_{i}(\bar{q})=u^{s^{*}}_{i}(\bar{q})$ for all $i\in I$. However, for
other strategies $q\neq\bar{q}$, the value of $u^{s}_{i}(q)$ may be different
from $u^{s^{*}}_{i}(q)$ for one or more players $i\in I$. That is, belief
$\bar{\theta}$ consistently estimates the payoff at a fixed point strategy
$\bar{q}$ but not necessarily at all $q\in Q$. Consequently, if one or more
players had access to complete information of the true parameter $s^{*}$, they
may have an incentive to deviate from the fixed point strategy; such a fixed
point strategy profile $\bar{q}$ is not a complete information equilibrium.

We next present the sufficient and necessary condition under which all fixed
points are complete information fixed points. Besides, we derive a sufficient
condition on the set of fixed points $\Omega$ and the average payoff functions
to ensure that the strategy played in the fixed point is equivalent to a
complete information equilibrium, although the fixed point belief may not be a
complete information belief.

######  Proposition 1.

The fixed point set
$\Omega=\\{\left(\theta^{*},q^{*}\right)|q^{*}\in\mathrm{EQ}(\theta^{*})\\}$
if and only if $[\theta]\setminus S^{*}\left(q\right)$ is a non-empty set for
any $\theta\in\Delta(S)\setminus\\{\theta^{*}\\}$ and any
$q\in\mathrm{EQ}(\theta)$.

Furthermore, for a fixed point $\left(\bar{\theta},\bar{q}\right)$,
$\bar{q}=q^{*}$ if (i) There exists a positive number $\xi>0$ such that
$[\bar{\theta}]\subseteq S^{*}(q)$ for any $\|q-\bar{q}\|<\xi$; and (ii) The
payoff function $u^{s}_{i}(q_{i},q_{-i})$ is concave in $q_{i}$ for all $i\in
I$ and all $s\in[\bar{\theta}]$.

Proposition 1 is intuitive: A belief $\theta$ cannot be a fixed point belief
if a parameter in its support can be distinguished from the true parameter
$s^{*}$ with an equilibrium corresponding to $\theta$, i.e. $[\theta]\setminus
S^{*}(q)$ is non-empty for any $q\in\mathrm{EQ}(\theta)$. Hence, set $\Omega$
is comprised of only the complete information fixed points if and only if none
of the beliefs in the set $\Delta(S)\setminus\\{\theta^{*}\\}$ is a fixed
point belief.

Besides, for any fixed point $\left(\bar{\theta},\bar{q}\right)$, since
$\bar{q}_{i}$ is a best response strategy of $\bar{q}_{-i}$, $\bar{q}_{i}$ is
a local maximizer of the expected payoff function
$\mathbb{E}_{\bar{\theta}}[u_{i}^{s}(q_{i},\bar{q}_{-i})]$. Condition (i) in
Proposition 1 ensures that the value of the expected payoff function is
identical to that with the true parameter $s^{*}$ for any $q_{i}$ belonging to
a small neighborhood of $\bar{q}_{i}$. Therefore, $\bar{q}_{i}$ must be a
local maximizer of the payoff function with the true parameter
$u_{i}^{s^{*}}(q_{i},\bar{q}_{-i})$. Moreover, since condition (ii) provides
that payoffs are concave functions of $q_{i}$, $\bar{q}_{i}$ must also be a
global maximizer of $u_{i}^{s^{*}}(q_{i},\bar{q}_{-i})$. Thus, any fixed point
strategy $\bar{q}$ is an equilibrium of the game with complete information of
$s^{*}$.

Next we present three illustrative examples to further discuss the properties
of fixed points in our learning dynamics.

Example 1. (Cournot competition) A set of $I$ firms produce an identical
product and compete in a market. In each stage $k$, firm $i$’s strategy is
their production level $q_{i}^{k}\in[0,3]$. The price of the product is
$p^{k}=\alpha^{s}-\beta^{s}\left(\sum_{i\in I}q_{i}^{k}\right)+\epsilon^{s}$,
where $s=\left(\alpha^{s},\beta^{s}\right)$ is the unknown parameter vector in
the price function, and $\epsilon$ is a random variable with zero mean. The
set of parameter vectors is $S=\\{s_{1},s_{2}\\}$, where
$s_{1}=\left(2,1\right)$ and $s_{2}=\left(4,3\right)$. The true parameter is
$s^{*}=s_{1}$. The marginal cost of each firm is 0. Therefore, the payoff of
firm $i$ in stage $k$ is
$y^{k}_{i}=q_{i}^{k}\left(\alpha^{s}-\beta^{s}\left(\sum_{i\in
I}q_{i}^{k}\right)+\epsilon^{s}\right)$ for each $s\in S$. The information
system updates belief $\theta^{k}$ based on the total production $\sum_{i\in
I}q_{i}^{k}$ and the realized price $p^{k}$.

This game has a potential function, and the best response correspondence
$\mathrm{BR}(q,\theta)$ is a contraction mapping for all $q\in Q$ and all
$\theta\in\Delta(S)$. Thus, all three types of best response update rules
satisfy Assumption 1.444For any $\theta\in\Delta(S)$ and any $q\in Q$, the
best response strategy is
$\mathrm{BR}_{i}(\theta,q)=\\{\frac{\mathbb{E}_{\theta}[\alpha^{s}]}{2\mathbb{E}_{\theta}[\beta^{s}]}-\frac{1}{2}\sum_{j\neq
i}q_{j}\\}$, where $\mathbb{E}_{\theta}[\alpha^{s}]=\sum_{s\in
S}\theta(s)\alpha^{s}$ and $\mathbb{E}_{\theta}[\beta^{s}]=\sum_{s\in
S}\theta(s)\beta^{s}$. Then, for any $q,q^{\prime}\in Q$, we have
$\|\mathrm{BR}(\theta,q)-\mathrm{BR}(\theta,q^{\prime})\|<\frac{1}{4}\|q-q^{\prime}\|$,
i.e. $\mathrm{BR}(\theta,q)$ is a contraction mapping. Thus, for each of the
three best response dynamics, $F(\theta,q)$ is also a contraction mapping.
From the Banach’s fixed-point theorem, the sequence of strategies converges to
the equilibrium strategy in $\mathrm{EQ}(\theta)$ under all three best
response dynamics. From Theorem 1, the states of the learning dynamics
converge to a fixed point with probability 1 with all three types of strategy
updates. The complete information fixed point is $\theta^{*}=\left(1,0\right)$
and $q^{*}=\left(2/3,2/3\right)$. Additionally,
$\theta^{\dagger}=\left(0.5,0.5\right)$ and
$q^{\dagger}=\left(0.5,0.5\right)\in\mathrm{EQ}(\theta^{\dagger})$ is also a
fixed point since $[\theta^{\dagger}]\subseteq
S^{*}(q^{\dagger})=\\{s_{1},s_{2}\\}$. Thus,
$\left(\theta^{\dagger},q^{\dagger}\right)$ is another fixed point. Note that
at $q^{\dagger}$, the two parameters $s_{1}$ and $s_{2}$ lead to identical
price distributions, and thus cannot be distinguished.

In fact, since any $\theta\neq\theta^{*}$ must include $s_{2}$ in the support
set, one can show that $q^{\dagger}=\left(0.5,0.5\right)$ is the only strategy
profile for which $s_{1}$ and $s_{2}$ are payoff-equivalent. Thus, there does
not exist any other fixed points apart from $\left(\theta^{*},q^{*}\right)$
and $\left(\theta^{\dagger},q^{\dagger}\right)$; i.e.
$\Omega=\left\\{(\theta^{*},q^{*}),(\theta^{\dagger},q^{\dagger})\right\\}$.

Example 2.(Zero sum game) Two players $i\in\\{1,2\\}$ repeatedly play a zero-
sum game with identical convex and closed strategy sets $Q_{1}=Q_{2}=[0,6]$.
For any strategy profile $q$, the payoff of each player is
$y_{1}=-y_{2}=v^{s}(q)+\epsilon^{s}$, where

$\displaystyle
v^{s}(q)=\left(\max\left(|q^{k}_{1}-q^{k}_{2}|,s\right)-s\right)^{2}-2(q^{k}_{1})^{2},$

and $s\in S=\\{1,3,5\\}$ is the unknown parameter. The true parameter
$s^{*}=3$. Belief is updated by an information platform based on the strategy
profiles and the realized payoffs.

All three types of best response update rules satisfy Assumption 1 in this
zero sum game.555For any $\theta\in\Delta(S)$, $q_{1}=0$ maximizes the
expected utility of player 1. Thus, regardless of the sequence of player 2’s
strategies, the sequence of player 1’s strategy converges to 0 under all three
best response dynamics. Additionally, the sequence of player 2’s strategies
converges to a best response strategy in
$\mathrm{BR}_{2}(\theta,0)=\\{Q_{2}|q_{2}\leq\min\\{[\theta]\\}\\}$. Since
$\mathrm{EQ}(\theta)=\\{\left(q_{1},q_{2}\right)|q_{1}=0,q_{2}\leq\min\\{[\theta]\\}\\}$,
the sequence of strategies converges to an equilibrium strategy under all
three best response dynamics. From Theorem 1, the sequence of states converges
to a fixed point w.p. 1.

The set of complete information fixed points is
$\theta^{*}=\left(0,1,0\right)$ and
$\mathrm{EQ}(\theta^{*})=\\{\left(q^{*}_{1},q^{*}_{2}\right)|q^{*}_{1}=0,~{}q^{*}_{2}\leq
3\\}$. Apart from the complete information fixed points, any
$\theta^{\dagger}\in\Delta(S)\setminus\\{(0,0,1)\\}$ and any
$q^{\dagger}\in\\{\left(\bar{q}_{1},\bar{q}_{2}\right)|q^{\dagger}_{1}=0,~{}q^{\dagger}_{2}\leq\min\\{[\theta^{\dagger}]\\}\\}$
is also a fixed point. This is because for any belief $\theta^{\dagger}$ that
assigns positive probability on $s=1$ or $s=3$, $q^{\dagger}_{1}=0$ and
$q^{\dagger}_{2}$ such that
$|q^{\dagger}_{2}-q^{\dagger}_{2}|\leq\min\\{[\theta^{\dagger}]\\}$ is an
equilibrium, and the two parameters $s=1$ and $s=3$ are payoff equivalent at
$q^{\dagger}$.

Moreover, we can check that conditions (i) and (ii) in Proposition 1 are
satisfied by any fixed point $\left(\theta^{\dagger},q^{\dagger}\right)$.
Thus, any fixed point strategy in the set
$\\{\left(q^{\dagger}_{1},q^{\dagger}_{2}\right)|q^{\dagger}_{1}=0,~{}q^{\dagger}_{2}\leq\min\\{[\theta^{\dagger}]\\}\\}$
is a complete information equilibrium although $\theta^{\dagger}$ is not a
complete information belief.

Example 3. (Investment game) Two players repeatedly play an investment game.
In each stage $k$, the strategy $q_{i}^{k}\in[0,1]$ is the non-negative level
of investment of player $i$. Given the strategy profile
$q^{k}=\left(q^{k}_{1},q^{k}_{2}\right)$, the return of a unit investment is
randomly realized according to $r^{k}=s+q^{k}_{1}+q^{k}_{2}+\epsilon^{s}$,
where $s\in S=\\{0,1,2\\}$ is the unknown parameter that represents the
average baseline return and $\epsilon^{s}$ is the noise term. The true
parameter is $s^{*}=1$. The stage cost of investment for each player is
$3\left(q_{i}^{k}\right)^{2}$. Therefore, the payoff of each player $i\in I$
is
$y^{k}_{i}=q_{i}^{k}(s+q^{k}_{1}+q^{k}_{2}+\epsilon^{s})-3\left(q_{i}^{k}\right)^{2}=q_{i}^{k}(s-2q_{i}^{k}+q^{k}_{-i}+\epsilon^{s})$
for all $s\in S$. In each stage $k$, the information system updates belief
$\theta^{k}$ based on the total investment $q^{k}_{1}+q^{k}_{2}$ and the unit
investment return $r^{k}$.

This game is a supermodular game, and it is also dominance solvable. All three
best response dynamics satisfy Assumption 1.666For any $\theta\in\Delta(S)$
and any $q\in Q$, the best response strategy is
$\mathrm{BR}(\theta,q)=\\{\frac{\mathbb{E}_{\theta}[s]+q_{2}}{4},\frac{\mathbb{E}_{\theta}[s]+q_{1}}{4}\\}$,
where $\mathbb{E}_{\theta}[s]=\sum_{s\in S}\theta(s)s$. Same as Example 1, for
any $q,q^{\prime}\in Q$, we have
$\|\mathrm{BR}(\theta,q)-\mathrm{BR}(\theta,q^{\prime})\|=\frac{1}{4}\|q-q^{\prime}\|<\|q-q^{\prime}\|$,
i.e. $\mathrm{BR}(\theta,q)$ is a contraction mapping. Thus, under any one of
the three best response dynamics, $F(\theta,q)$ is also a contraction mapping,
and the sequence of strategies converges to an equilibrium strategy in
$\mathrm{EQ}(\theta)$. Thus, states converge to a fixed point with probability
1. In this game, since $S^{*}(q)=\\{s^{*}=1\\}$ for any $q\in Q$, the unique
fixed point is the complete information fixed point, i.e.
$\Omega=\\{\left(\theta^{*},q^{*}\right)=\left(\left(0,1,0\right),\left(1/3,1/3\right)\right)\\}$.

###  3.2 Stability

In this section, we analyze both global and local stability properties of
fixed point belief $\bar{\theta}$ and the associated equilibrium set
$\mathrm{EQ}(\bar{\theta})$.

######  Definition 3 (Global stability).

A fixed point belief $\bar{\theta}\in\Delta(S)$ and the associated equilibrium
set $\mathrm{EQ}(\bar{\theta})$ are _globally stable_ if for any initial state
$\left(\theta^{1},q^{1}\right)$, the beliefs of the learning dynamics
$\left(\theta^{k}\right)_{k=1}^{\infty}$ converge to $\bar{\theta}$ and the
strategies $\left(q^{k}\right)_{k=1}^{\infty}$ converge to
$\mathrm{EQ}(\bar{\theta})$ with probability 1.

Thus, global stability requires that that the convergent fixed point belief
and the corresponding equilibrium set do not depend on the initial state.

We next introduce the definition of local stability. For any $\epsilon>0$, we
define an $\epsilon$-neighborhood of belief $\bar{\theta}$ as
$N_{\epsilon}(\bar{\theta})\stackrel{{\scriptstyle\Delta}}{{=}}\left\\{\theta\left|\|\theta-\bar{\theta}\|<\epsilon\right.\right\\}$.
For any $\delta>0$, we define the $\delta$-neighborhood of equilibrium set as
$N_{\delta}(\mathrm{EQ}(\bar{\theta}))\stackrel{{\scriptstyle\Delta}}{{=}}\left\\{q\left|D\left(q,\mathrm{EQ}(\bar{\theta})\right)<\delta\right.\right\\}$,
where
$D\left(q,\mathrm{EQ}(\bar{\theta})\right)=\min_{q^{\prime}\in\mathrm{EQ}(\bar{\theta})}\|q-q^{\prime}\|$
is the Euclidean distance between $q$ and the set $\mathrm{EQ}(\bar{\theta})$.

######  Definition 4 (Local stability).

A fixed point belief $\bar{\theta}\in\Delta(S)$ and the associated equilibrium
set $\mathrm{EQ}(\bar{\theta})$ are _locally stable_ if for any
$\gamma\in(0,1)$ and any $\bar{\epsilon},\bar{\delta}>0$, there exist
$\epsilon^{1},\delta^{1}>0$ such that for the learning dynamics that starts
with $\theta^{1}\in N_{\epsilon^{1}}(\bar{\theta})$ and $q^{1}\in
N_{\delta^{1}}(\mathrm{EQ}(\bar{\theta}))$, the following holds:

$\displaystyle\lim_{k\to\infty}\mathrm{Pr}\left(\theta^{k}\in
N_{\bar{\epsilon}}(\bar{\theta}),~{}q^{k}\in
N_{\bar{\delta}}(\mathrm{EQ}(\bar{\theta}))\right)>\gamma.$ (9)

Thus, local stability requires that when the learning starts with an initial
state that is sufficiently close to a fixed point belief $\bar{\theta}$ and
the associated equilibrium set $\mathrm{EQ}(\bar{\theta})$, then the sequence
of beliefs (resp. sequence of strategies) is guaranteed to be arbitrarily
close to $\bar{\theta}$ (resp. $\mathrm{EQ}(\bar{\theta})$), with arbitrarily
high probability. In other words, when the belief $\bar{\theta}$ and the
equilibrium strategy set $\mathrm{EQ}(\bar{\theta})$ are locally stable, the
learning dynamics is robust to small perturbations around $\bar{\theta}$ and
$\mathrm{EQ}(\bar{\theta})$. On the other hand, if $\bar{\theta}$ and
$\mathrm{EQ}(\bar{\theta})$ are locally unstable, then there exists a non-zero
probability $\iota>0$ such that the state of learning dynamics can leave the
neighborhood of $\bar{\theta}$ and $\mathrm{EQ}(\bar{\theta})$ with
probability at least $\iota$ even when the initial belief $\theta^{1}$ (resp.
strategy $q^{1}$) is arbitrarily close to $\bar{\theta}$ (resp.
$\mathrm{EQ}(\bar{\theta})$).

Note that both global and local stability notions are not defined for a single
fixed point, but rather for the tuple
$\left(\bar{\theta},\mathrm{EQ}(\bar{\theta})\right)$, i.e. fixed points with
an identical belief $\bar{\theta}$. This is important when the game has
multiple equilibria; i.e., $\mathrm{EQ}(\theta)$ is not a singleton set for
some belief $\theta\in\Delta(S)$. That is, our stability notions do not hinge
on the convergence to a particular equilibrium in the fixed point equilibrium
set $\mathrm{EQ}(\bar{\theta})$.

We provide a necessary and sufficient condition for global stability:

######  Proposition 2.

There exists a globally stable fixed point if and only if all fixed points are
complete information fixed points, i.e.
$\Omega=\left\\{\left(\theta^{*},\mathrm{EQ}(\theta^{*})\right)\right\\}$. In
this case, $\left(\theta^{*},\mathrm{EQ}(\theta^{*})\right)$ is globally
stable.

This result is quite intuitive: If the set $\Omega$ contains another fixed
point that is not a complete information fixed point, then whether the states
of learning dynamics converge to the complete information fixed point or
another fixed point depends on the initial state; hence no fixed point in the
set can be globally stable. Also recall from Proposition 1 that all fixed
points being complete information fixed points is equivalent to the condition
that any parameter other than the true parameter $s^{*}$ can be distinguished
from $s^{*}$ at the equilibrium. From Proposition 2, we know that this
condition is also equivalent to the existence of globally stable fixed points.

To prove local stability, we assume that the following set of conditions hold:

######  Assumption 2.

For a fixed point belief $\bar{\theta}$ and the associated equilibrium set
$\mathrm{EQ}(\bar{\theta})$, $\exists\epsilon,~{}\delta>0$ such that the
neighborhoods $N_{\epsilon}\left(\bar{\theta}\right)$ and
$N_{\delta}\left(\mathrm{EQ}(\bar{\theta})\right)$ satisfy
(A2a) _Local upper hemicontinuity_ : $\mathrm{EQ}(\theta)$ is upper-
hemicontinuous in $\theta$ for any $\theta\in
N_{\epsilon}\left(\bar{\theta}\right)$.
(A2b) _Local invariance_ : Neighborhood
$N_{\delta}(\mathrm{EQ}(\bar{\theta}))$ is a locally invariant set of the best
response correspondence, i.e. $\mathrm{BR}(\theta,q)\subseteq
N_{\delta}(\mathrm{EQ}(\bar{\theta}))$ for any $q\in
N_{\delta}\left(\mathrm{EQ}(\bar{\theta})\right)$ and any $\theta\in
N_{\epsilon}\left(\bar{\theta}\right)$.
(A2c) _Local consistency_ : Fixed point belief $\bar{\theta}$ forms a
consistent payoff estimate in the local neighborhood
$N_{\delta}(EQ(\bar{\theta}))$, i.e. $[\bar{\theta}]\subseteq S^{*}(q)$ for
any $q\in N_{\delta}(EQ(\bar{\theta}))$.

######  Theorem 2.

A fixed point belief $\bar{\theta}\in\Delta(S)$ and the associated equilibrium
set $EQ(\bar{\theta})$ is locally stable under the learning dynamics
($\theta$-update) and ($q$-update) if Assumptions 1 and 2 are satisfied.

From Theorem 1, we know that Assumption 1 ensures the convergence of beliefs
and strategies under local perturbations. We now discuss the role of each of
the three conditions in Assumption 2 towards local stability. Firstly, the
local upper hemicontinuity condition _(A2a)_ guarantees that the convergent
equilibrium strategy remains close to the original fixed point equilibrium
when the belief is locally perturbed. Secondly, the local invariance condition
_(A2b)_ guarantees that the strategy sequence resulting from the strategy
updates remains within the local invariant neighborhood of the fixed point
equilibrium. We remark that for games with complete information, local
invariance reduces to the standard condition on the existence of invariant set
for best response strategy updates under no parameter uncertainty, and this
property is sufficient to ensure the local stability of complete information
equilibrium. Hence, the conditions of local upper hemicontinuity and local
invariance conditions together ensure that the strategy sequence in our
learning dynamics does not leave the local neighborhood of
$\mathrm{EQ}(\bar{\theta})$ so long as the perturbed beliefs remain close to
$\bar{\theta}$.

Finally, the local consistency condition _(A2c)_ ensures that
($\theta$-update) keeps the beliefs close to $\bar{\theta}$. Under this
condition, any parameter in the support of $\bar{\theta}$ remains to be payoff
equivalent to $s^{*}$ for any strategy in a local neighborhood of
$\mathrm{EQ}(\bar{\theta})$. That is, $\bar{\theta}$ forms a consistent
estimate of players’ payoffs not just at fixed point strategy $\bar{q}$, but
also when the strategy is locally perturbed around $\bar{q}$. Therefore, the
Bayesian belief update keeps the beliefs of all parameters in $[\bar{\theta}]$
close to their respective probabilities in $\bar{\theta}$ when the strategies
are in the local neighborhood, and eventually any parameters that are not in
$[\bar{\theta}]$ are excluded by the learning dynamics.

We now detail the proof ideas of Theorem 2 (the formal proof is given in
Appendix A). From Definition 4, to prove local stability, we need to
characterize the local neighborhoods
$N_{\epsilon^{1}}\left(\bar{\theta}\right)$ and
$N_{\delta^{1}}\left(\mathrm{EQ}(\bar{\theta})\right)$ of the initial state
$\left(\theta^{1},q^{1}\right)$ such that (9) is satisfied. In our proof, we
first show via Lemma 4 that (9) is satisfied if the sequence of states –
beliefs and strategies – remain with probability higher than $\gamma$ in the
specifically constructed neighborhoods
$N_{\hat{\epsilon}}\left(\bar{\theta}\right)$ and
$N_{\delta}\left(\mathrm{EQ}(\bar{\theta})\right)$, respectively; here,
$\hat{\epsilon}\in(0,\epsilon)$ and $\epsilon$, and $\delta$ are chosen
according to Assumption 2. Subsequently, in Lemmas 5 and 6, we precisely
characterize the neighborhoods $N_{\epsilon^{1}}\left(\bar{\theta}\right)$ and
$N_{\delta^{1}}\left(\mathrm{EQ}(\bar{\theta})\right)$ such that the sequence
of beliefs and strategies starting from initial state
$(\theta^{1},q^{1})\in(N_{\epsilon^{1}}(\bar{\theta})\times
N_{\delta^{1}}(\mathrm{EQ}(\bar{\theta}))$ remains in the respective
neighborhoods $N_{\hat{\epsilon}}(\bar{\theta})$ and
$N_{\delta}(\mathrm{EQ}(\bar{\theta}))$ that we specifically construct in
Lemma 4 with probability higher than $\gamma$.

In Lemma 4, parts _(i)_ and _(ii)_ show that under Assumption _(A2a)_ –
_(A2b)_ , the properties of local upper-hemicontinuity and local invariance
hold in the neighborhoods $N_{\hat{\epsilon}}\left(\bar{\theta}\right)$ and
$N_{\delta}\left(\mathrm{EQ}(\bar{\theta})\right)$. Additionally, part _(iii)_
shows that if the belief sequence and strategy sequence are in respective sets
$N_{\hat{\epsilon}}(\bar{\theta})$ and $N_{\delta}(EQ(\bar{\theta}))$, then
the convergent state must be in $N_{\bar{\epsilon}}(\bar{\theta})$ and
$N_{\bar{\delta}}\left(\mathrm{EQ}(\bar{\theta})\right)$.

######  Lemma 4.

Under Assumptions 1 and (A2a) – (A2b),

  1. (i)

For any $\bar{\delta}>0$, $\exists\epsilon^{\prime}\in\left(0,\epsilon\right)$
such that any $\theta\in N_{\epsilon^{\prime}}(\bar{\theta})$ satisfies
$\mathrm{EQ}(\theta)\subseteq N_{\bar{\delta}}(\mathrm{EQ}(\bar{\theta}))$.

  2. (ii)

For any $\bar{\epsilon}>0$, $\mathrm{BR}(\theta,q)\subseteq
N_{\delta}(\mathrm{EQ}(\bar{\theta}))$ for all $q\in
N_{\delta}(\mathrm{EQ}(\bar{\theta}))$ and all $\theta\in
N_{\hat{\epsilon}}\left(\mathrm{EQ}(\bar{\theta})\right)$, where
$\hat{\epsilon}=\min\\{\epsilon,\epsilon^{\prime},\bar{\epsilon}\\}$.

  3. (iii)

$\lim_{k\to\infty}\mathrm{Pr}\left(\theta^{k}\in
N_{\bar{\epsilon}}(\bar{\theta}),\right.$ $\left.q^{k}\in
N_{\bar{\delta}}(\mathrm{EQ}(\bar{\theta}))\right)\geq\mathrm{Pr}\left(\theta^{k}\in
N_{\hat{\epsilon}}(\bar{\theta}),~{}q^{k}\in
N_{\delta}(\mathrm{EQ}(\bar{\theta})),~{}\forall k\right)$.

In Lemma 4, _(i)_ follows from Assumption _(A2a)_ that $\mathrm{EQ}(\theta)$
is upper-hemicontinuous in $\theta$ in the local neighborhood
$N_{\epsilon}\left(\bar{\theta}\right)$. Then, we obtain _(ii)_ from
Assumption _(A2b)_ that $N_{\delta}\left(\mathrm{EQ}(\bar{\theta})\right)$ is
an invariant set of the best response correspondence. Furthermore, if beliefs
are in $N_{\hat{\epsilon}}(\bar{\theta})$ for all stages, then the convergent
belief must also be in $N_{\hat{\epsilon}}(\bar{\theta})\subseteq
N_{\bar{\epsilon}}(\bar{\theta})$. Based on Theorem 1, the sequence of
strategies converges. Since $N_{\hat{\epsilon}}(\bar{\theta})\subseteq
N_{\epsilon^{\prime}}(\bar{\theta})$, we know from _(i)_ in Lemma 4 that the
convergent strategy is an equilibrium in the neighborhood
$N_{\bar{\delta}}(\mathrm{EQ}(\bar{\theta}))$. Thus, _(iii)_ holds.

Thanks to Lemma 4 _(iii)_ , to prove local stability as in (9), it remains to
be established that there exist $N_{\epsilon^{1}}(\bar{\theta})$ and
$N_{\delta^{1}}\left(\mathrm{EQ}(\bar{\theta})\right)$ for the initial belief
$\theta^{1}$ and strategy $q^{1}$ such that $\mathrm{Pr}\left(\theta^{k}\in
N_{\hat{\epsilon}}(\bar{\theta}),\right.$ $\left.q^{k}\in
N_{\delta}(\mathrm{EQ}(\bar{\theta})),~{}\forall k\right)>\gamma$. In
particular, $\theta^{k}\in N_{\hat{\epsilon}}\left(\bar{\theta}\right)$ is
guaranteed if $|\theta^{k}(s)-\bar{\theta}(s)|\leq\frac{\hat{\epsilon}}{|S|}$
for all $s\in S$. We separately analyze the beliefs of all $s\in
S\setminus[\bar{\theta}]$ (i.e. the set of parameters with zero probability in
$\bar{\theta}$) in Lemma 5, and that of $s\in[\bar{\theta}]$ in Lemma 6.
Additionally, parts _(a)_ and _(b)_ in Lemma 4 are useful in Lemmas 5 and 6
for constructing $\epsilon^{1}$ and $\delta^{1}$.

Before proceeding, we need to define the following thresholds:

$\displaystyle\rho^{1}$
$\displaystyle\stackrel{{\scriptstyle\Delta}}{{=}}\min_{s\in[\bar{\theta}]}\left\\{\frac{(1-\gamma)\bar{\theta}(s)\hat{\epsilon}}{(1-\gamma+|S\setminus[\bar{\theta}]|)(|S\setminus[\bar{\theta}]|+1)|S|+(1-\gamma)\hat{\epsilon}}\right\\},$
(10a) $\displaystyle\rho^{2}$
$\displaystyle\stackrel{{\scriptstyle\Delta}}{{=}}\frac{\hat{\epsilon}}{(|S\setminus[\bar{\theta}]|+1)|S|},$
(10b) $\displaystyle\rho^{3}$
$\displaystyle\stackrel{{\scriptstyle\Delta}}{{=}}\min_{s\in[\bar{\theta}]}\left\\{\frac{\hat{\epsilon}-|S\setminus[\bar{\theta}]||S|\rho^{2}\bar{\theta}(s)}{|S|-|S\setminus[\bar{\theta}]||S|\rho^{2}},~{}\frac{\hat{\epsilon}}{|S|+|S\setminus[\bar{\theta}]|\left(\bar{\theta}(s)|S|+\hat{\epsilon}\right)},~{}\bar{\theta}(s)\right\\}.$
(10c)

Lemma 5 below shows that if the initial belief $\theta^{1}$ is in the
neighborhood $N_{\rho^{1}}(\bar{\theta})$, then $\theta^{k}(s)\leq\rho^{2}$
for all $s\in S\setminus[\bar{\theta}]$ in all stages of the learning dynamics
with probability higher than $\gamma$. Note that $\theta^{k}(s)\leq\rho^{2}$
ensures $|\theta^{k}(s)-\bar{\theta}(s)|<\frac{\hat{\epsilon}}{|S|}$ since
$\bar{\theta}(s)=0$ for all $s\in S\setminus[\bar{\theta}]$ and
$\rho^{2}<\frac{\hat{\epsilon}}{|S|}$. Additionally, the threshold $\rho^{2}$
is specifically constructed to bound the beliefs of the remaining parameters
in $[\bar{\theta}]$, which will be used later in Lemma 6.

######  Lemma 5.

For any $\gamma\in(0,1)$, if the initial belief satisfies

$\displaystyle\theta^{1}(s)<\rho^{1},\quad\forall s\in
S\setminus[\bar{\theta}],$ (11a)
$\displaystyle\bar{\theta}(s)-\rho^{1}<\theta^{1}(s)<\bar{\theta}(s)+\rho^{1},\quad\forall
s\in[\bar{\theta}],$ (11b)

then

$\displaystyle\mathrm{Pr}\left(\theta^{k}(s)\leq\rho^{2},~{}\forall s\in
S\setminus[\bar{\theta}],~{}\forall k\right)>\gamma.$ (12)

In the proof of Lemma 5, we say that the belief $\theta^{k}(s)$ completes an
upcrossing of the interval $[\rho^{1},\rho^{2}]$ if $\theta^{k}(s)$ increases
from less than $\rho^{1}$ to higher than $\rho^{2}$. Note that if the belief
of a parameter $s\in S\setminus[\bar{\theta}]$ is initially smaller than
$\rho^{1}$ but later becomes higher than $\rho^{2}$ in some stage $k$, then
the belief sequence $\left(\theta^{j}(s)\right)_{j=1}^{k}$ must have completed
at least one upcrossing of $[\rho^{1},\rho^{2}]$ before stage $k$. Therefore,
$\theta^{k}(s)\leq\rho^{2}$ for all $k$ is equivalent to that the number of
upcrossings completed by the belief is zero.

Additionally, by bounding the initial belief of parameters
$s\in[\bar{\theta}]$ as in (11b), we construct another interval
$\left[\rho^{1}/\left(\bar{\theta}(s^{*})-\rho^{1}\right),\rho^{2}\right]$
such that the number of upcrossings with respect to this interval completed by
the sequence of belief ratios
$\left(\frac{\theta^{k}(s)}{\theta^{k}(s^{*})}\right)_{k=1}^{\infty}$ is no
less than the number of upcrossings with respect to interval
$[\rho^{1},\rho^{2}]$ completed by
$\left(\theta^{k}(s)\right)_{k=1}^{\infty}$. Recall that the sequence of
belief ratios
$\left(\frac{\theta^{k}(s)}{\theta^{k}(s^{*})}\right)_{k=1}^{\infty}$ forms a
martingale process (Lemma 1). By applying Doob’s upcrossing inequality, we
obtain an upper bound on the expected number of upcrossings completed by the
belief ratio corresponding to each parameter $s\in S\setminus[\bar{\theta}]$,
which is also an upper bound on the expected number of upcrossings made by the
belief of $s$. Using Markov’s inequality and the upper bound of the expected
number of upcrossings, we show that with probability higher than $\gamma$, no
belief $\theta^{k}(s)$ of any parameter $s\in S\setminus[\bar{\theta}]$ can
ever complete a single upcrossing with respect to the interval
$[\rho^{1},\rho^{2}]$ characterized by (10a) – (10b). Hence, $\theta^{k}(s)$
remains lower than the threshold $\rho^{2}$ for all $s\in
S\setminus[\bar{\theta}]$ and all $k$ with probability higher than $\gamma$.

Furthermore, Lemma 6 utilizes another set of conditions on the initial belief
and strategy; these conditions ensure that the beliefs of the remaining
parameters $s\in[\bar{\theta}]$ satisfy
$|\theta^{k}(s)-\bar{\theta}(s)|<\frac{\hat{\epsilon}}{|S|}$, and the strategy
$q^{k}\in N_{\delta}\left(\mathrm{EQ}(\bar{\theta})\right)$ for all $k$ so
long as $\theta^{k}(s)<\rho^{2}$ for any parameter $s\in
S\setminus[\bar{\theta}]$. Recall that $\theta^{k}(s)<\rho^{2}$ for all $s\in
S\setminus[\bar{\theta}]$ is satisfied with probability higher than $\gamma$
under the conditions provided in Lemma 5.

######  Lemma 6.

Under Assumption (A2b) – (A2c), if $|\theta^{1}(s)-\bar{\theta}(s)|<\rho^{3}$
for all $s\in[\bar{\theta}]$ and $q^{1}\in
N_{\delta}\left(\mathrm{EQ}(\bar{\theta})\right)$, then

$\displaystyle\mathrm{Pr}\left(\left.\begin{array}[]{l}|\theta^{k}(s)-\bar{\theta}(s)|<\frac{\hat{\epsilon}}{|S|},~{}\forall
s\in[\bar{\theta}],~{}\forall k\\\ \text{and }q^{k}\in
N_{\delta}\left(\mathrm{EQ}(\bar{\theta})\right),~{}\forall
k\end{array}\right|\theta^{k}(s)<\rho^{2},~{}\forall s\in
S\setminus[\bar{\theta}],~{}\forall k\right)=1.$ (15)

We prove this lemma by mathematical induction. Since
$\rho^{2}<\frac{\hat{\epsilon}}{|S|}$ as in (10b), under the condition that
$\theta^{k}(s)<\rho^{2}$ for all $s\in S\setminus[\bar{\theta}]$ and all $k$,
we know that $\theta^{k}(s)<\frac{\hat{\epsilon}}{|S|}$ for all $s\in
S\setminus[\bar{\theta}]$ and all $k$. In any stage $k$, assume that
$|\theta^{k}(s)-\bar{\theta}(s)|<\frac{\hat{\epsilon}}{|S|}$ for all
$s\in[\bar{\theta}]$ and $q^{k}\in
N_{\delta}\left(\mathrm{EQ}(\bar{\theta})\right)$. Then, $\theta^{k}\in
N_{\hat{\epsilon}}\left(\bar{\theta}\right)$ in stage $k$. Additionally, under
local consistency condition in Assumption _(A2c)_ , $s\in[\bar{\theta}]$
remains to be payoff equivalent at $q^{k}$. Thus, we can show that the belief
of the next stage must satisfy
$|\theta^{k}(s)-\bar{\theta}(s)|<\frac{\hat{\epsilon}}{|S|}$ for all
$s\in[\bar{\theta}]$, which ensures that $\theta^{k+1}\in
N_{\hat{\epsilon}}\left(\bar{\theta}\right)$. Since
$\hat{\epsilon}\leq\epsilon$ as in part _(ii)_ of Lemma 4, we know that the
updated strategy $q^{k+1}$ is in
$N_{\delta}\left(\mathrm{EQ}(\bar{\theta})\right)$. Hence, we obtain (15) by
induction.

Finally, by setting $\epsilon^{1}=\min\\{\rho^{1},\rho^{3}\\}$ and
$\delta^{1}=\delta$, where $\rho^{1}$, $\rho^{3}$ are as in (10a), (10c) and
$\delta$ is given by Assumption 2, the initial state in
$N_{\epsilon^{1}}(\bar{\theta})$ and
$N_{\delta^{1}}\left(\mathrm{EQ}(\bar{\theta})\right)$ satisfies the
conditions in Lemmas 5 and 6. Then, by combining (12) and (15), we obtain that
all beliefs and strategies are in the neighborhoods
$N_{\hat{\epsilon}}\left(\bar{\theta}\right)$ and
$N_{\delta}\left(\mathrm{EQ}(\bar{\theta})\right)$ respectively with
probability higher than $\gamma$. From (c) in Lemma 4, we know that
$\lim_{k\to\infty}\mathrm{Pr}\left(\theta^{k}\in
N_{\bar{\epsilon}}(\bar{\theta}),q^{k}\in
N_{\bar{\delta}}(\mathrm{EQ}(\bar{\theta}))\right)\geq\gamma$. Thus, we have
constructed the local neighborhoods of the initial state that satisfy (9), and
we conclude Theorem 2.

We discuss the local and global stability properties of the fixed points in
Examples 1 – 3.

Example 1. (continued) Since the complete information fixed point is not the
unique fixed point, no fixed point is globally stable. We now show that the
complete information fixed point $\theta^{*}=(1,0)$,
$q^{*}=\left(2/3,2/3\right)$ is locally stable. Consider $\epsilon=1/3$ and
$\delta=1$. We can check that all three conditions in Assumption 2 are
satisfied in the neighborhoods $N_{\epsilon}\left(\theta^{*}\right)$ and
$N_{\delta}\left(q^{*}\right)$, and thus this fixed point is locally stable.
On the other hand, the other fixed point
$\theta^{\dagger}=\left(0.5,0.5\right)$ and $q^{\dagger}=\left(0.5,0.5\right)$
does not satisfy the local consistency condition since the two parameters
$s_{1}$ and $s_{2}$ can be distinguished when the strategy is perturbed in any
local neighborhood of $q^{\dagger}$.

Example 2. (continued) Since the complete information fixed point is not the
unique fixed point, no fixed point is globally stable. Moreover, by setting
$\epsilon=1/2$ and $\delta=6$, we can check that all fixed points in $\Omega$
satisfy the three conditions in Assumption 2, and thus are locally stable.

Example 3. (continued) The unique fixed point of the public good investment
game is the complete information fixed point
$\left(\theta^{*},q^{*}\right)=\left(\left(0,1,0\right),\left(1/2,1/3\right)\right)$.
From Proposition 2, the complete information fixed point is globally stable.

##  4 Extensions

In this section, we consider three types of extensions of the learning model
introduced in Sec. 2: (1) Learning with two timescales; (2) Learning in games
with finite strategy set; (3) Learning with maximum a posteriori probability
(MAP) or ordinary least squares (OLS) estimates.

(1) Learning with two timescales. Consider the case where strategy update is
at a faster timescale compared with the belief updates, i.e.
$\lim_{t\to\infty}k_{t+1}-k_{t}=\infty$ with probability 1. Under Assumption
1, as $t\rightarrow\infty$, the strategies between two belief updates $k_{t}$
and $k_{t+1}$ converge to an equilibrium strategy profile in
$\mathrm{EQ}\left(\theta^{k_{t}}\right)$ before the next belief update in
stage $k_{t+1}$. Then, the updated belief $\theta^{k_{t+1}}$ forms an accurate
payoff estimate given the equilibrium strategy. Our convergence result
(Theorem 1) holds for this two timescale dynamics. The local and global
stability results in Theorem 2 and Proposition 2 also hold in an analogous
manner.

(2) Learning in Games with Finite Strategy Set. Our results in Sec. 3 can be
extended to learning in games where strategy sets are finite and players can
choose mixed strategies. In this game, each player $i$’s action set (pure
strategies) is a finite set $A_{i}$, and the action profile (pure strategy
profile) is denoted as $a=\left(a_{i}\right)_{i\in I}\in A=\prod_{i\in
I}A_{i}$. Given any parameter $s$ and any action profile $a$, the distribution
of players’ payoff $y$ is $\phi^{s}\left(y|a\right)$.

We denote player $i$’s mixed strategy as
$q_{i}=\left(q_{i}(a_{i})\right)_{a_{i}\in A_{i}}\in
Q_{i}=\Delta\left(A_{i}\right)$, where $q_{i}(a_{i})$ is the probability of
choosing the action $a_{i}$. The strategy set $Q_{i}$ is bounded and convex.
Players’ action profile in each stage $k$, denoted as
$a^{k}=\left(a_{i}^{k}\right)_{i\in I}$, is realized from the mixed strategy
profile $q^{k}$.

Analogous to ($\theta$-update), the information system updates the belief
$\theta^{k_{t}}$ based on actions $\left(a^{k}\right)_{k=k_{t}}^{k_{t+1}-1}$
and the realized payoff vectors $\left(y^{k}\right)_{k=k_{t}}^{k_{t+1}-1}$ as
follows:

$\displaystyle\theta^{k_{t+1}}(s)$
$\displaystyle=\frac{\theta^{k_{t}}(s)\prod_{k=k_{t}}^{k_{t+1}-1}\phi^{s}(y^{k}|a^{k})}{\sum_{s^{\prime}\in
S}\theta^{k_{t}}(s^{\prime})\prod_{k=k_{t}}^{k_{t+1}-1}\phi^{s^{\prime}}(y^{k}|a^{k})},\quad\forall
s\in S.$

Similar to Sec. 2, we consider three types of best response updates:

  1. 1.

_Simultaneous best response dynamics._ All players choose an action that is
best response to the updated belief and their opponents’ action profile:

$\displaystyle a^{k+1}_{i}$
$\displaystyle\in\mathrm{BR}_{i}(\theta^{k+1},a_{-i}^{k}),\quad\forall i\in
I.$

  2. 2.

_Sequential best response dynamics._ Players change their actions to be a best
response strategy of other opponents’ actions one by one:

$\displaystyle
a_{i}^{k+1}\left\\{\begin{array}[]{ll}\in\mathrm{BR}_{i}(\theta^{k+1},a^{k}_{-i}),&\quad\text{if
}k~{}mod~{}|I|=i.\\\ =a^{k}_{i},&\quad\text{otherwise}.\end{array}\right.$

  3. 3.

_Fictitious play._ The mixed strategy $q_{i}^{k}$ represents player $i$’s
empirical frequency of actions in previous stages $1,\dots,k$. In each stage
$k$, all players best respond to their opponents’ empirical frequency
$q^{k}_{-i}$:

$\displaystyle a^{k}_{i}\in\mathrm{BR}_{i}(\theta^{k},q^{k}_{-i}),\quad
q_{i}^{k+1}=\frac{k}{k+1}q_{i}^{k}+\frac{1}{k+1}a^{k}_{i},\quad\forall i\in
I,\quad\forall k.$

We extend the definition of payoff equivalent parameters in Definition 2 as
follows: Parameter $s$ is payoff-equivalent to $s^{*}$ given $q\in Q$ if the
distribution of payoffs under $s$ is identical to that under $s^{*}$ for all
actions that are assigned with positive probability given $q$. Therefore, the
payoff-equivalent parameter set given $q$ is defined as
$S^{*}(q)\stackrel{{\scriptstyle\Delta}}{{=}}\left\\{S\left|D_{KL}\left(\phi^{s*}\left(y|a\right)||\phi^{s}\left(y|a\right)\right)=0,~{}\forall
a\in[q]\right.\right\\}$, where $[q]=\\{A|q(a)>0\\}$ is the support set of the
mixed strategy profile $q$.

The convergence result in Theorem 1 can be readily extended to games with
finite strategy sets: Under Assumption 1, the beliefs
$\left(\theta^{k}\right)_{k=1}^{\infty}$ converge to a fixed point belief
$\bar{\theta}$ that accurately estimates the payoff distribution for all
action profiles that are taken with positive probability, and the strategies
$\left(q^{k}\right)_{k=1}^{\infty}$ converge to the equilibrium set
$\mathrm{EQ}(\bar{\theta})$.

The results on global and local stability properties in Proposition 2 and
Theorem 2 also hold for games with finite strategy set. Moreover, for games
with a finite strategy set, any fixed point that satisfies the sufficient
condition of local stability must be a complete information fixed point. This
is because any local perturbation of a fixed point strategy profile can lead
to a mixed strategy with full support on all action profiles, and these mixed
strategies can distinguish any parameter $s\neq s^{*}$ from $s^{*}$. Thus,
local consistency condition in Assumption _(A2c)_ is only satisfied by the
complete information belief $\theta^{*}$.

Example 4. Atomic routing games with unknown cost parameters (Wu et al.
(2020))
A set of players $I$ repeatedly travel in a transportation network with edge
set $E$. Each player is associated with an origin-destination pair, and their
action set $A_{i}$ is the set of paths – sequences of edges – that connect
their origin to their destination. In each stage $k$, given an action profile
$a^{k}=\left(a^{k}_{i}\right)_{i\in I}$, the load on each edge $x^{k}_{e}$ is
the total number of players using that edge. The network has an uncertain
state $s\in S$ that affects the costs of edges. Given any $s$, the cost of
edge $e$ is $c_{e}^{k}=d_{e}^{s}(x_{e}^{k})+\epsilon_{e}^{s}$, where
$d_{e}^{s}(\cdot)$ is an increasing function of $x_{e}^{k}$ and
$\epsilon_{e}^{s}$ is a noise term with zero mean. The cost of each player is
$y^{k}_{i}=\sum_{e\in a^{k}_{i}}c_{e}^{k}$. The traffic information system
updates the belief of the unknown parameter vector $s$ based on the load
vector $x^{k}=\left(x_{e}^{k}\right)_{e\in E}$ of all edges, and the realized
travel time cost of all edges that are taken
$c^{k}=\left(c^{k}_{e}\right)_{e\in\\{E|x_{e}^{k}>0\\}}$.

The states in our learning dynamics converge to a fixed point under both
sequential best response dynamics and fictitious play. On the other hand, the
simultaneous best response dynamics can be cyclic.777For any
$\theta\in\Delta(S)$, the routing game has a potential function. Therefore,
the sequence of strategies under (4) and (Linear-BR) converges to an
equilibrium strategy in $\mathrm{EQ}(\theta)$ (Monderer and Shapley (1996b,
a); Marden et al. (2009a)). However, the sequence of strategies under
(Simultaneous-BR) may not converge. For example, consider a two route network
$\\{e_{1},e_{2}\\}$ with identical cost functions
$\mathbb{E}_{\theta}[d_{e}^{s}(x_{e})]=\mathbb{E}_{\theta}[s]x_{e}+1$, where
$s>0$ is the unknown parameter. There are two players. If learning that starts
with both players taking $e_{1}$, then under (Simultaneous-BR), both players
take $e_{2}$ in all even stages 2, 4, $\dots$, and take $e_{1}$ in all odd
stages 1, 2, $\dots$. Therefore, the strategy sequence does not converge under
(Simultaneous-BR), and Assumption 1 is not satisfied. At the fixed point, the
belief $\bar{\theta}$ accurately estimates the costs of all edges that are
taken by travelers in $\bar{q}$, and all players take the route that minimizes
their expected costs given $\bar{\theta}$. However, the fixed point strategy
$\bar{q}$ may not be the complete information equilibrium because
$\bar{\theta}$ can form wrong estimate on edges that are not taken in
$\bar{q}$. Finally, the complete information fixed point is locally stable.

(3) MAP and OLS estimates. Now consider a continuous and bounded parameter set
$S$, and that the initial belief $\theta^{1}(s)$ is a probability density
function of $s$ on the set $S$, and $\theta^{1}(s)>0$ for all $s\in S$. Since
the unknown parameter $s$ is continuous, Bayesian belief update in
($\theta$-update) at stage $k_{t+1}$ is as follows:

$\displaystyle\theta^{k_{t+1}}(s)$
$\displaystyle=\frac{\theta^{k_{t}}(s)\prod_{k=k_{t}}^{k_{t+1}-1}\phi^{s}(y^{k}|q^{k})}{\int_{s\in
S}\theta^{k_{t}}(s)\prod_{k=k_{t}}^{k_{t+1}-1}\phi^{s}(y^{k}|q^{k})ds},\quad\forall
s\in S.$

Instead of computing the full posterior belief in each stage (which entails
computing the continuous integration in the denominator of the Bayesian
update), we consider learning with maximum a posteriori (MAP) estimator that
maximizes the posterior belief of the unknown parameter:

$\displaystyle\theta^{k_{t+1}}_{M}(s)$
$\displaystyle=\operatorname*{arg\,max}_{s\in
S}\theta^{k_{t+1}}(s)=\operatorname*{arg\,max}_{s\in
S}\theta^{k_{t}}(s)\prod_{k=k_{t}}^{k_{t+1}-1}\phi^{s}(y^{k}|q^{k}).$
($\theta_{M}$-update)

Note that if the initial belief $\theta^{1}$ is a uniform distribution of all
parameters, then the MAP estimate is also a maximum likelihood estimate (MLE).

Our result on convergence of state (Theorem 1) can be directly extended to
this case of learning with MAP estimate. In particular, under Assumption 1,
the sequence of MAP estimates converges to a payoff equivalent parameter
$\bar{\theta}_{M}\in S^{*}(\bar{q})$ given the fixed point strategy profile,
and the strategies converge to an equilibrium strategy
$\bar{q}\in\mathrm{EQ}(\bar{\theta}_{M})$ of game $G$ with parameter
$\bar{\theta}_{M}$.

Moreover, under Assumptions 1 and 2, we can check that if the initial belief
$\theta^{1}$ is in a small local neighborhood of the belief vector that
assigns probability 1 to a fixed point MAP estimate $\bar{\theta}_{M}$ and the
strategy profile is in a small local neighborhood of the equilibrium
$\mathrm{EQ}(\bar{\theta}_{M})$, then the convergent belief remains in a small
neighborhood of the singleton belief vector so that the MAP estimate remains
to be $\bar{\theta}_{M}$ and the equilibrium set is
$\mathrm{EQ}(\bar{\theta}_{M})$. Therefore, analogous to Theorem 2, we can
conclude that $\left(\bar{\theta}_{M},\mathrm{EQ}(\bar{\theta}_{M})\right)$ is
locally stable under conditions given by Assumptions 1 and 2.

Finally, we consider a special case, where the average payoff functions are
affine in strategies:

$\displaystyle y_{i}=\left(q,1\right)\cdot s_{i}+\epsilon_{i}^{s},\quad\forall
i\in I.$ (16)

The unknown parameter vector is $s=\left(s_{i}\right)_{i\in I}$, where $s_{i}$
has $|q|+1$ dimensions. The noise term $\epsilon_{i}^{s}$ is realized from a
normal distribution with zero mean and finite variance.

From stage $1$ to $k_{t}$, player $i$’s realized payoff
$\left(y_{i}^{k}\right)_{k=1}^{k_{t}}$ can be written as a linear function of
the strategies $\left(q^{k}\right)_{k=1}^{k_{t}}$ in the following matrix
form:

$\displaystyle\underbrace{\left(\begin{array}[]{l}y_{i}^{1}\\\ y_{i}^{2}\\\
\vdots\\\
y_{i}^{k_{t}}\end{array}\right)}_{Y_{i}^{k_{t}}}=\underbrace{\left(\begin{array}[]{ll}q^{1},&1\\\
q^{2},&1\\\ \vdots&\vdots\\\
q^{k_{t}},&1\end{array}\right)}_{\widetilde{Q}^{k_{t}}}s_{i}+\left(\begin{array}[]{l}\epsilon_{i}^{1}\\\
\epsilon_{i}^{2}\\\ \vdots\\\ \epsilon_{i}^{k_{t}}\end{array}\right).$

The OLS estimate is $\hat{s}^{k_{t}}=\left(\hat{s}_{i}^{k_{t}}\right)_{i\in
I}$ where

$\displaystyle\hat{s}_{i}^{k_{t}}=\left(\left(\widetilde{Q}^{k_{t}}\right)^{\prime}\widetilde{Q}^{k_{t}}\right)^{-1}\left(\widetilde{Q}^{k_{t}}\right)^{\prime}Y_{i}^{k_{t}},\quad\forall
i\in I,\quad\forall k_{t}.$ ($\hat{s}$ \- update)

In learning dynamics with OLS estimates, the convergence of the OLS estimates
can be viewed as a special case of learning with MAP estimator because
$\hat{s}^{k_{t}}$ is identical to the MLE estimator $\theta^{k_{t}}_{M}$ when
each player’s payoff as in (16) is an affine function of the strategy profile
plus a noise term with Normal distribution. Therefore, we obtain the same
convergence result in the learning with OLS estimate as in learning with MAP
estimate. That is, the OLS estimates converge to an estimate $\bar{s}\in S$
such that $u^{\bar{s}}_{i}(\bar{q})=u^{s^{*}}_{i}(\bar{q})$ for all $i\in I$,
and strategies converge to $\bar{q}\in\mathrm{EQ}(\bar{s})$ with probability
1. Furthermore, as we have shown in Example 1, when payoff functions are
linear in players’ strategies, only the complete information fixed point
satisfies the locally consistency condition Assumption _(A2c)_. Thus, no other
fixed point satisfies the sufficient conditions for local stability.

##  5 Concluding Remarks

In this article, we studied stochastic learning dynamics induced by a set of
strategic players who repeatedly play a game with an unknown parameter. We
analyzed the convergence of beliefs and strategies induced by the stochastic
dynamics, and derived conditions for local and global stability of fixed
points. We also provided a simple condition which guarantees the convergence
of strategies to complete information equilibrium.

A future research question of interest is to analyze the learning dynamics
when players seek to efficiently learn the true parameter by choosing off-
equilibrium strategies. When there are one or more parameters that are payoff
equivalent to the true parameter at fixed point, complete learning requires
players to take strategies that may reduce their individual payoffs in some
stages. In our setup, if a player were to choose a non-equilibrium strategy,
the information resulting from that player’s realized payoff would be
incorporated into the belief update, and the new belief is known to all
players. Under what scenarios the utility-maximizing players will choose their
strategies to engage such explorative behavior is an interesting question, and
worthy of further investigation.

Another promising extension is to study multi-agent reinforcement learning
problem from a Bayesian viewpoint. In such settings, the unknown parameter
changes over time according to a Markovian transition process, and players may
have imperfect or no knowledge of the underlying transition kernel. The ideas
presented in this article are useful to analyze how players learn the belief
estimates of payoffs that depend on the latent Markov state, and adaptively
adjust their strategies that converges to an equilibrium.

## Acknowledgement

We thank Vivek Borkar, Patrick Jaillet, Jason Marden, Shankar Sastry, John
Tsitsiklis, Leeat Yariv, Muhammet Yildiz, Georges Zaccour for useful
discussions. We are grateful to speakers and participants at the 9th Workshop
on Dynamic Games in Management Science at HEC Montréal (2017); 8th IFAC
Workshop on Distributed Estimation and Control in Networked Systems (2019);
2nd Annual Conference on Learning for Dynamics and Control at Berkeley (2020).
This research was supported in part by Michael Hammer Fellowship, AFOSR
project Building Attack Resilience into Complex Networks, and NSF CAREER award
(CNS 1453126).

## References

  * Acemoglu et al. [2014] Daron Acemoglu, Kostas Bimpikis, and Asuman Ozdaglar.  Dynamics of information exchange in endogenous social networks.  _Theoretical Economics_ , 9(1):41–97, 2014.
  * Acemoglu et al. [2017] Daron Acemoglu, Ali Makhdoumi, Azarakhsh Malekian, and Asuman Ozdaglar.  Fast and slow learning from reviews.  Technical report, National Bureau of Economic Research, 2017.
  * Adlakha and Johari [2013] Sachin Adlakha and Ramesh Johari.  Mean field equilibrium in dynamic games with strategic complementarities.  _Operations Research_ , 61(4):971–989, 2013.
  * Ali [2018] S Nageeb Ali.  Herding with costly information.  _Journal of Economic Theory_ , 175:713–729, 2018.
  * Alós-Ferrer and Netzer [2010] Carlos Alós-Ferrer and Nick Netzer.  The logit-response dynamics.  _Games and Economic Behavior_ , 68(2):413–427, 2010.
  * Beggs [2005] Alan W Beggs.  On the convergence of reinforcement learning.  _Journal of Economic Theory_ , 122(1):1–36, 2005\.
  * Benaim and Hirsch [1999] Michel Benaim and Morris W Hirsch.  Mixed equilibria and dynamical systems arising from fictitious play in perturbed games.  _Games and Economic Behavior_ , 29(1-2):36–72, 1999.
  * Blume et al. [1993] Lawrence E Blume et al.  The statistical mechanics of strategic interaction.  _Games and Economic Behavior_ , 5(3):387–424, 1993.
  * Cominetti et al. [2010] Roberto Cominetti, Emerson Melo, and Sylvain Sorin.  A payoff-based learning procedure and its application to traffic games.  _Games and Economic Behavior_ , 70(1):71–83, 2010\.
  * Daskalakis et al. [2011] Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim.  Near-optimal no-regret algorithms for zero-sum games.  In _Proceedings of the Twenty-second Annual ACM-SIAM Symposium on Discrete Algorithms_ , pages 235–254. SIAM, 2011.
  * Duffie et al. [2009] Darrell Duffie, Semyon Malamud, and Gustavo Manso.  Information percolation with equilibrium search dynamics.  _Econometrica_ , 77(5):1513–1574, 2009.
  * Easley and Kiefer [1988] David Easley and Nicholas M Kiefer.  Controlling a stochastic process with unknown parameters.  _Econometrica: Journal of the Econometric Society_ , pages 1045–1064, 1988.
  * Foster and Young [2006] Dean Foster and Hobart Peyton Young.  Regret testing: Learning to play Nash equilibrium without knowing you have an opponent.  _Theoretical Economics_ , 1(3):341–367, 2006\.
  * Frick et al. [2020] Mira Frick, Ryota Iijima, and Yuhta Ishii.  Stability and robustness in misspecified learning models.  Technical report, 2020.
  * Fudenberg and Kreps [1993] Drew Fudenberg and David M Kreps.  Learning mixed equilibria.  _Games and Economic Behavior_ , 5(3):320–367, 1993.
  * Fudenberg and Levine [1993a] Drew Fudenberg and David K Levine.  Self-confirming equilibrium.  _Econometrica: Journal of the Econometric Society_ , pages 523–545, 1993a.
  * Fudenberg and Levine [1993b] Drew Fudenberg and David K Levine.  Steady state learning and Nash equilibrium.  _Econometrica: Journal of the Econometric Society_ , pages 547–573, 1993b.
  * Hahn [1978] Frank H Hahn.  Exercises in conjectural equilibria.  In _Topics in Disequilibrium Economics_ , pages 64–80. Springer, 1978\.
  * Hart and Mas-Colell [2003] Sergiu Hart and Andreu Mas-Colell.  Regret-based continuous-time dynamics.  _Games and Economic Behavior_ , 45(2):375–394, 2003.
  * Hofbauer and Sandholm [2002] Josef Hofbauer and William H Sandholm.  On the global convergence of stochastic fictitious play.  _Econometrica_ , 70(6):2265–2294, 2002.
  * Hofbauer and Sandholm [2009] Josef Hofbauer and William H Sandholm.  Stable games and their dynamics.  _Journal of Economic Theory_ , 144(4):1665–1693, 2009.
  * Hofbauer and Sorin [2006] Josef Hofbauer and Sylvain Sorin.  Best response dynamics for continuous zero-sum games.  _Discrete and Continuous Dynamical Systems Series B_ , 6(1):215, 2006.
  * Hopkins [2002] Ed Hopkins.  Two competing models of how people learn in games.  _Econometrica_ , 70(6):2141–2166, 2002.
  * Kalai and Lehrer [1993a] Ehud Kalai and Ehud Lehrer.  Rational learning leads to Nash equilibrium.  _Econometrica: Journal of the Econometric Society_ , pages 1019–1045, 1993a.
  * Kalai and Lehrer [1993b] Ehud Kalai and Ehud Lehrer.  Subjective equilibrium in repeated games.  _Econometrica: Journal of the Econometric Society_ , pages 1231–1240, 1993b.
  * Kalai and Lehrer [1995] Ehud Kalai and Ehud Lehrer.  Subjective games and equilibria.  _Games and Economic Behavior_ , 8(1):123–163, 1995.
  * Kash et al. [2011] Ian A Kash, Eric J Friedman, and Joseph Y Halpern.  Multiagent learning in large anonymous games.  _Journal of Artificial Intelligence Research_ , 40:571–598, 2011.
  * Marden and Shamma [2012] Jason R Marden and Jeff S Shamma.  Revisiting log-linear learning: Asynchrony, completeness and payoff-based implementation.  _Games and Economic Behavior_ , 75(2):788–808, 2012.
  * Marden et al. [2007] Jason R Marden, Gürdal Arslan, and Jeff S Shamma.  Regret based dynamics: convergence in weakly acyclic games.  In _Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems_ , page 42. ACM, 2007.
  * Marden et al. [2009a] Jason R Marden, Gürdal Arslan, and Jeff S Shamma.  Joint strategy fictitious play with inertia for potential games.  _IEEE Transactions on Automatic Control_ , 54(2):208–220, 2009a.
  * Marden et al. [2009b] Jason R Marden, H Peyton Young, Gürdal Arslan, and Jeff S Shamma.  Payoff-based dynamics for multiplayer weakly acyclic games.  _SIAM Journal on Control and Optimization_ , 48(1):373–396, 2009b.
  * Matsui [1992] Akihiko Matsui.  Best response dynamics and socially stable strategies.  _Journal of Economic Theory_ , 57(2):343–362, 1992.
  * Meigs et al. [2017] Emily Meigs, Francesca Parise, and Asuman Ozdaglar.  Learning dynamics in stochastic routing games.  In _2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , pages 259–266. IEEE, 2017.
  * Milgrom and Roberts [1990] Paul Milgrom and John Roberts.  Rationalizability, learning, and equilibrium in games with strategic complementarities.  _Econometrica: Journal of the Econometric Society_ , pages 1255–1277, 1990.
  * Moe and Fader [2004] Wendy W Moe and Peter S Fader.  Dynamic conversion behavior at e-commerce sites.  _Management Science_ , 50(3):326–335, 2004.
  * Monderer and Shapley [1996a] Dov Monderer and Lloyd S Shapley.  Fictitious play property for games with identical interests.  _Journal of Economic Theory_ , 68(1):258–265, 1996a.
  * Monderer and Shapley [1996b] Dov Monderer and Lloyd S Shapley.  Potential games.  _Games and Economic Behavior_ , 14(1):124–143, 1996b.
  * Rothschild [1974] Michael Rothschild.  A two-armed bandit theory of market pricing.  _Journal of Economic Theory_ , 9(2):185–202, 1974\.
  * Samuelson [1994] Larry Samuelson.  Stochastic stability in games with alternative best replies.  _Journal of economic theory_ , 64(1):35–65, 1994\.
  * Samuelson and Zhang [1992] Larry Samuelson and Jianbo Zhang.  Evolutionary stability in asymmetric games.  _Journal of Economic Theory_ , 57(2):363–391, 1992.
  * Sandholm [2010] William H Sandholm.  Local stability under evolutionary game dynamics.  _Theoretical Economics_ , 5(1):27–50, 2010.
  * Shapley [1964] Lloyd Shapley.  Some topics in two-person games.  _Advances in Game Theory_ , 52:1–29, 1964.
  * Smith and Price [1973] J Maynard Smith and George R Price.  The logic of animal conflict.  _Nature_ , 246(5427):15–18, 1973.
  * Taylor and Jonker [1978] Peter D Taylor and Leo B Jonker.  Evolutionary stable strategies and game dynamics.  _Mathematical Siosciences_ , 40(1-2):145–156, 1978.
  * Wu et al. [2020] Manxi Wu, Saurabh Amin, and Asuman Ozdaglar.  Bayesian learning with adaptive load allocation strategies.  In _Learning for Dynamics and Control_ , pages 561–570. PMLR, 2020\.
  * Wu et al. [2021] Manxi Wu, Saurabh Amin, and Asuman E Ozdaglar.  Value of information in Bayesian routing games.  _Operations Research_ , 69(1):148–163, 2021.
  * Zhu et al. [2010] Shanjiang Zhu, David Levinson, Henry X Liu, and Kathleen Harder.  The traffic and behavioral effects of the I-35W Mississippi River Bridge collapse.  _Transportation Research Part A: Policy and Practice_ , 44(10):771–784, 2010.

##  Appendix A Supplementary Proofs for Section 3

_Proof of Lemma 1._
First, we show that for any parameter $s\in S$, the sequence
$\left(\frac{\theta^{k_{t}}(s)}{\theta^{k_{t}}(s^{*})}\right)_{t=1}^{\infty}$
is a non-negative martingale, and hence converges with probability 1. Note
that for any $t=1,2,\dots$, and any parameter $s\in S\setminus\\{s^{*}\\}$, we
have the following from ($\theta$-update):

$\displaystyle\frac{\theta^{k_{t+1}}(s)}{\theta^{k_{t+1}}(s^{*})}=\frac{\theta^{k_{t}}(s)\cdot\prod_{k=k_{t}}^{k_{t+1}-1}\phi^{s}(y^{k}|q^{k})}{\theta^{k_{t}}(s^{*})\cdot\prod_{k=k_{t}}^{k_{t+1}-1}\phi^{s^{*}}(y^{k}|q^{k})}.$

Now starting from any initial belief $\theta^{1}$, consider a sequence of
strategies
$Q^{k_{t}-1}\stackrel{{\scriptstyle\Delta}}{{=}}\left(q^{j}\right)_{j=1}^{k_{t}-1}$
and a sequence of realized payoffs
$Y^{k_{t}-1}\stackrel{{\scriptstyle\Delta}}{{=}}\left(y^{j}\right)_{j=1}^{k_{t}-1}$
before stage $k_{t}$. Then, the expected value of
$\frac{\theta^{k_{t+1}}(s)}{\theta^{k_{t+1}}(s^{*})}$ conditioned on
$\theta^{1}$, $Q^{k_{t}-1}$ and $Y^{k_{t}-1}$ is as follows:

$\displaystyle\mathbb{E}\left[\left.\frac{\theta^{k_{t+1}}(s)}{\theta^{k_{t+1}}(s^{*})}\right|\theta^{1},Q^{k_{t}-1},Y^{k_{t}-1}\right]$
$\displaystyle=\frac{\theta^{k_{t}}(s)}{\theta^{k_{t}}(s^{*})}\cdot\mathbb{E}\left[\frac{\prod_{k=k_{t}}^{k_{t+1}-1}\phi^{s}(y^{k}|q^{k})}{\prod_{k=k_{t}}^{k_{t+1}-1}\phi^{s^{*}}(y^{k}|q^{k})}\right]$
(17)

where $\theta^{k_{t}}$ is the repeatedly updated belief from $\theta^{1}$
based on $Q^{k_{t}-1}$ and $Y^{k_{t}-1}$ using ($\theta$-update). Note that

$\displaystyle\mathbb{E}\left[\frac{\prod_{k=k_{t}}^{k_{t+1}-1}\phi^{s}(y^{k}|q^{k})}{\prod_{k=k_{t}}^{k_{t+1}-1}\phi^{s^{*}}(y^{k}|q^{k})}\right]=\int_{y^{k_{t}}y^{k_{t}+1}y^{k_{t+1}-1}}\left(\frac{\prod_{k=k_{t}}^{k_{t+1}-1}\phi^{s}(y^{k}|q^{k})}{\prod_{k=k_{t}}^{k_{t+1}-1}\phi^{s^{*}}(y^{k}|q^{k})}\right)\cdot\left(\prod_{k=k_{t}}^{k_{t+1}-1}\phi^{s^{*}}(y^{k}|q^{k})\right)dy^{k_{t}}y^{k_{t}+1}y^{k_{t+1}-1}$
$\displaystyle=$
$\displaystyle\int_{y^{k_{t}}y^{k_{t}+1}y^{k_{t+1}-1}}\prod_{k=k_{t}}^{k_{t+1}-1}\phi^{s}(y^{k}|q^{k})dy^{k_{t}}y^{k_{t}+1}y^{k_{t+1}-1}=1.$

Hence, for any $k=1,2,\dots$,

$\displaystyle\mathbb{E}\left[\left.\frac{\theta^{k_{t+1}}(s)}{\theta^{k_{t+1}}(s^{*})}\right|\theta^{1},Q^{k_{t}-1},Y^{k_{t}-1}\right]$
$\displaystyle=\frac{\theta^{k_{t}}(s)}{\theta^{k_{t}}(s^{*})},\quad\forall
s\in S.$

Again, from ($\theta$-update) we know that
$\frac{\theta^{k_{t}}(s)}{\theta^{k_{t}}(s^{*})}\geq 0$. Hence, the sequence
$\left(\frac{\theta^{k_{t}}(s)}{\theta^{k_{t}}(s^{*})}\right)_{t=1}^{\infty}$
is a non-negative martingale for any $s\in S$. From the martingale convergence
theorem, we conclude that $\frac{\theta^{k_{t}}(s)}{\theta^{k_{t}}(s^{*})}$
converges with probability 1.

Next we show that the sequence
$\left(\log\theta^{k_{t}}(s^{*})\right)_{t=1}^{\infty}$ is a submartingale,
and hence converges with probability 1. We define the estimated density
function of payoffs $\left(y^{k}\right)_{k=k_{t}}^{k_{t+1}-1}$ with belief
$\theta$ as
$\mu\left(\left(y^{k}\right)_{k=k_{t}}^{k_{t+1}-1}\left|\theta^{k_{t}},\left(q^{k}\right)_{k=k_{t}}^{k_{t+1}-1}\right.\right)\stackrel{{\scriptstyle\Delta}}{{=}}\sum_{s\in
S}\theta^{k_{t}}(s)\prod_{k=k_{t}}^{k_{t+1}-1}\phi^{s}(y^{k}|q^{k})$. From
($\theta$-update), we have:

$\displaystyle\mathbb{E}\left[\left.\log\theta^{k_{t+1}}(s^{*})\right|\theta^{1},Q^{k_{t}-1},Y^{k_{t}-1}\right]=\mathbb{E}\left[\left.\log\left(\frac{\theta^{k_{t}}(s^{*})\prod_{k=k_{t}}^{k_{t+1}-1}\phi^{s^{*}}(y^{k}|q^{k})}{\mu\left(\left(y^{k}\right)_{k=k_{t}}^{k_{t+1}-1}\left|\theta^{k_{t}},\left(q^{k}\right)_{k=k_{t}}^{k_{t+1}-1}\right.\right)}\right)\right|\theta^{1},Q^{k_{t}-1},Y^{k_{t}-1}\right]$
$\displaystyle=\log\theta^{k_{t}}(s^{*})+\mathbb{E}\left[\log\left(\frac{\prod_{k=k_{t}}^{k_{t+1}-1}\phi^{s^{*}}(y^{k}|q^{k})}{\mu\left(\left(y^{k}\right)_{k=k_{t}}^{k_{t+1}-1}\left|\theta^{k_{t}},\left(q^{k}\right)_{k=k_{t}}^{k_{t+1}-1}\right.\right)}\right)\right]$
$\displaystyle=\log\theta^{k_{t}}(s^{*})+\int_{y^{k_{t}}y^{k_{t}+1}y^{k_{t+1}-1}}\left(\prod_{k=k_{t}}^{k_{t+1}-1}\phi^{s^{*}}(y^{k}|q^{k})\right)\log\left(\frac{\prod_{k=k_{t}}^{k_{t+1}-1}\phi^{s^{*}}(y^{k}|q^{k})}{\mu\left(\left(y^{k}\right)_{k=k_{t}}^{k_{t+1}-1}\left|\theta^{k_{t}},\left(q^{k}\right)_{k=k_{t}}^{k_{t+1}-1}\right.\right)}\right)dy^{k_{t}}y^{k_{t}+1}y^{k_{t+1}-1}$
$\displaystyle=\log\theta^{k_{t}}(s^{*})+D_{KL}\left(\prod_{k=k_{t}}^{k_{t+1}-1}\phi^{s^{*}}(y^{k}|q^{k})\left|\left|\mu\left(\left(y^{k}\right)_{k=k_{t}}^{k_{t+1}-1}\left|\theta^{k_{t}},\left(q^{k}\right)_{k=k_{t}}^{k_{t+1}-1}\right.\right)\right.\right.\right)\geq\log\theta^{k_{t}}(s^{*}),$

where the last inequality is due to the non-negativity of KL divergence
between $\prod_{k=k_{t}}^{k_{t+1}-1}\phi^{s^{*}}(y^{k}|q^{k})$ and
$\mu\left(\left(y^{k}\right)_{k=k_{t}}^{k_{t+1}-1}\left|\theta^{k_{t}},\left(q^{k}\right)_{k=k_{t}}^{k_{t+1}-1}\right.\right)$.
Therefore, the sequence
$\left(\log\theta^{k_{t}}(s^{*})\right)_{t=1}^{\infty}$ is a submartingale.
Additionally, since $\log\theta^{k_{t}}(s^{*})$ is bounded above by zero, by
the martingale convergence theorem $\log\theta^{k_{t}}(s^{*})$ converges with
probability 1. Hence, $\theta^{k_{t}}(s^{*})$ must also converge with
probability 1.

From the convergence of $\frac{\theta^{k_{t}}(s)}{\theta^{k_{t}}(s^{*})}$ and
$\theta^{k_{t}}(s^{*})$, we conclude that $\theta^{k_{t}}(s)$ converges with
probability 1 for any $s\in S$. Since for any $k=k_{t}+1,\dots,k_{t+1}-1$,
$\theta^{k}=\theta^{k_{t}}$, we know that $\theta^{k}$ also converges. Let the
convergent vector be denoted as
$\bar{\theta}=\left(\bar{\theta}(s)\right)_{s\in S}$. We can check that for
any $k$, $\theta^{k}(s)\geq 0$ for all $s\in S$ and $\sum_{s\in
S}\theta^{k}(s)=1$. Hence, $\bar{\theta}$ must satisfy $\bar{\theta}(s)\geq 0$
for all $s\in S$ and $\sum_{s\in S}\bar{\theta}(s)=1$, i.e. $\bar{\theta}$ is
a feasible belief vector. $\square$

Before proceeding, we show that the best response correspondence is upper
hemicontinuous in the belief and the strategy profile. This result follows
directly from the Berge’s theorem of maximum and the fact that the expected
utility function $\mathbb{E}_{\theta}\left[u_{i}^{s}(q_{i},q_{-i})\right]$ is
continuous in $\theta$ and $q$.

######  Lemma 7.

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}$.

We are now ready to prove Lemma 2.

_Proof of Lemma 2._ For any stage $K\geq 1$, we construct an auxiliary
sequence of strategies $\left(\hat{q}^{k}\right)_{k=1}^{\infty}$ as follows:
First, we set $\hat{q}^{k}=q^{k}$ for all $k=1,\dots,K$. Then, for any $k>K$,
we define the following subsequences:

  * -

We define
$\tilde{q}^{k+1}\stackrel{{\scriptstyle\Delta}}{{=}}\operatorname*{arg\,min}_{\tilde{q}\in
F(\bar{\theta},q^{k})}\|\tilde{q}-q^{k+1}\|$. That is, $\tilde{q}^{k+1}$ is a
strategy updated from $q^{k}$ with the fixed point belief $\bar{\theta}$ (i.e.
$\tilde{q}^{k+1}\in F(\bar{\theta},q^{k})$). Additionally, $\tilde{q}^{k+1}$
is the closest to $q^{k+1}$ – the strategy in stage $k+1$ of the original
sequence – among all strategies in the set $F(\bar{\theta},q^{k})$.

  * -

We define the auxiliary strategy
$\hat{q}^{k+1}\stackrel{{\scriptstyle\Delta}}{{=}}\operatorname*{arg\,min}_{q\in
F(\bar{\theta},\hat{q}^{k})}\|q-\tilde{q}^{k+1}\|$. That is, $\hat{q}^{k+1}$
is a strategy updated from $\hat{q}^{k}$ with the fixed point belief
$\bar{\theta}$ (i.e. $\hat{q}^{k+1}\in F(\bar{\theta},\hat{q}^{k})$).
Additionally, $\hat{q}^{k+1}$ is the closest to $\tilde{q}^{k+1}$ among all
strategies in the set $F(\bar{\theta},\hat{q}^{k})$.

Therefore, for any $k>K$, we have:

$\displaystyle\|q^{k+1}-\tilde{q}^{k+1}\|=D\left(q^{k+1},F(\bar{\theta},q^{k})\right),~{}\|\tilde{q}^{k+1}-\hat{q}^{k+1}\|=D\left(\tilde{q}^{k+1},F(\bar{\theta},\hat{q}^{k})\right).$
(18)

We next show by mathematical induction that for any $\ell\geq 1$,
$\lim_{K\to\infty}\|q^{K+\ell}-\hat{q}^{K+\ell}\|=0$. To begin with, for
$\ell=1$, we have

$\displaystyle\|q^{K+1}-\hat{q}^{K+1}\|\leq\|q^{K+1}-\tilde{q}^{K+1}\|+\|\tilde{q}^{K+1}-\hat{q}^{K+1}\|$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:dist}}}{{=}}$ $\displaystyle
D\left(q^{K+1},F\left(\bar{\theta},q^{K}\right)\right)+D\left(\tilde{q}^{K+1},F\left(\bar{\theta},\hat{q}^{K}\right)\right).$
(19)

Since $\theta^{k}$ converges to $\bar{\theta}$ (Lemma 1), $F(\theta,q)$ is
upper hemicontinuous in $\theta$ (Lemma 7), and $q^{K+1}\in
F(\theta^{K+1},q^{K})$, we know that
$\lim_{K\to\infty}D\left(q^{K+1},F\left(\bar{\theta},q^{K}\right)\right)=0$.
Additionally, since $\hat{q}^{K}=q^{K}$ and $\tilde{q}^{K+1}\in
F(\bar{\theta},q^{K})$,
$D\left(\tilde{q}^{K+1},F\left(\bar{\theta},\hat{q}^{K}\right)\right)=0$.
Therefore, $\lim_{K\to\infty}\|q^{K+1}-\hat{q}^{K+1}\|=0$.

Now, assume that $\lim_{K\to\infty}\|q^{K+\ell}-\hat{q}^{K+\ell}\|=0$ for some
$\ell\geq 1$, we need to prove that
$\lim_{K\to\infty}\|q^{K+\ell+1}-\hat{q}^{K+\ell+1}\|=0$. Similar to (19), we
have

$\displaystyle\|q^{K+\ell+1}-\hat{q}^{K+\ell+1}\|\leq
D\left(q^{K+\ell+1},F\left(\bar{\theta},q^{K+\ell}\right)\right)+D\left(\tilde{q}^{K+\ell+1},F\left(\bar{\theta},\hat{q}^{K+\ell}\right)\right)$

Analogous to $\ell=1$, since $F(\theta,q)$ is upper hemicontinuous in
$\theta$,
$\lim_{K\to\infty}D\left(q^{K+\ell+1},F\left(\bar{\theta},q^{K+\ell}\right)\right)=0$.
Additionally, since $\lim_{K\to\infty}\|q^{K+\ell}-\hat{q}^{K+\ell}\|=0$,
$F(\theta,q)$ is upper hemicontinuous in $q$, and $\tilde{q}^{K+\ell+1}\in
F\left(\bar{\theta},q^{K+\ell}\right)$, we know that
$\lim_{K\to\infty}D\left(\tilde{q}^{K+\ell+1},F\left(\bar{\theta},\hat{q}^{K+\ell}\right)\right)=0$.
Therefore, we have $\lim_{K\to\infty}\|q^{K+\ell+1}-\hat{q}^{K+\ell+1}\|=0$.
By mathematical induction, we conclude that for any $\ell\geq 1$,
$\lim_{K\to\infty}\|q^{K+\ell}-\hat{q}^{K+\ell}\|=0$.

Finally, Assumption 1 ensures that the strategy update with constant beliefs
$\bar{\theta}$ converges to an equilibrium strategy
$\bar{q}\in\mathrm{EQ}(\bar{\theta})$. That is, for any $K\geq 1$,
$\lim_{\ell\to\infty}\|\hat{q}^{K+\ell}-\bar{q}\|=0$. Therefore,

$\displaystyle\lim_{k\to\infty}\|q^{k}-\bar{q}\|=\lim_{\ell\to\infty}\lim_{K\to\infty}\|q^{K+\ell}-\bar{q}\|\leq\lim_{\ell\to\infty}\lim_{K\to\infty}\|q^{K+\ell}-\hat{q}^{K+\ell}\|+\lim_{\ell\to\infty}\lim_{K\to\infty}\|\hat{q}^{K+\ell}-\bar{q}\|=0.$

Thus, $\lim_{k\to\infty}q^{k}=\bar{q}$. $\square$

_Proof of Lemma 3._ By iteratively applying the belief update in
($\theta$-update), we can write:

$\displaystyle\theta^{k_{t}}(s)=\frac{\theta^{1}(s)\prod_{j=1}^{k_{t}-1}\phi^{s}(y^{j}|q^{j})}{\sum_{s^{\prime}\in
S}\theta^{1}(s^{\prime})\prod_{j=1}^{k_{t}-1}\phi^{s^{\prime}}(y^{j}|q^{j})},\quad\forall
s\in S.$ (20)

We define $\Phi^{s}(Y^{k_{t}-1}|Q^{k_{t}-1})$ as the probability density
function of the history of the realized payoffs
$Y^{k_{t}-1}=\left(y^{j}\right)_{j=1}^{k_{t}-1}$ conditioned on the history of
strategies $Q^{k_{t}-1}=\left(q^{j}\right)_{j=1}^{k_{t}-1}$ prior to stage
$k_{t}$, i.e.
$\Phi^{s}(Y^{k_{t}-1}|Q^{k_{t}-1})\stackrel{{\scriptstyle\Delta}}{{=}}\prod_{j=1}^{k_{t}-1}\phi^{s}(y^{j}|q^{j})$.
We rewrite (20) as follows:

$\displaystyle\theta^{k_{t}}(s)$
$\displaystyle=\frac{\theta^{1}(s)\Phi^{s}(Y^{k_{t}-1}|Q^{k_{t}-1})}{\sum_{s^{\prime}\in
S}\theta^{1}(s^{\prime})\Phi^{s^{\prime}}(Y^{k_{t}-1}|Q^{k_{t}-1})}\leq\frac{\theta^{1}(s)\Phi^{s}(Y^{k_{t}-1}|Q^{k_{t}-1})}{\theta^{1}(s)\Phi^{s}(Y^{k_{t}-1}|Q^{k_{t}-1})+\theta^{1}(s^{*})\Phi^{s^{*}}(Y^{k_{t}-1}|Q^{k_{t}-1})}$
$\displaystyle=\frac{\theta^{1}(s)\frac{\Phi^{s}(Y^{k_{t}-1}|Q^{k_{t}-1})}{\Phi^{s^{*}}(Y^{k_{t}-1}|Q^{k_{t}-1})}}{\theta^{1}(s)\frac{\Phi^{s}(Y^{k_{t}-1}|Q^{k_{t}-1})}{\Phi^{s^{*}}(Y^{k_{t}-1}|Q^{k_{t}-1})}+\theta^{1}(s^{*})}.$
(21)

For any $s\in S\setminus S^{*}(\bar{q})$, if we can show that the ratio
$\frac{\Phi^{s}(Y^{k_{t}-1}|Q^{k_{t}-1})}{\Phi^{s^{*}}(Y^{k_{t}-1}|Q^{k_{t}-1})}$
converges to 0, then $\theta^{k_{t}}(s)$ must also converge to 0. Now, we need
to consider two cases:
_Case 1:_ $\phi^{s^{*}}(y|\bar{q})\ll\phi^{s}(y|\bar{q})$: In this case, the
log-likelihood ratio can be written as:

$\displaystyle\log\left(\frac{\Phi^{s}(Y^{k_{t}-1}|Q^{k_{t}-1})}{\Phi^{s^{*}}(Y^{k_{t}-1}|Q^{k_{t}-1})}\right)=\sum_{j=1}^{k_{t}-1}\log\left(\frac{\phi^{s}(y^{j}|q^{j})}{\phi^{s^{*}}(y^{j}|q^{j})}\right).$
(22)

For any $s\in S$, since $\phi^{s}(y^{j}|q^{j})$ is continuous in $q^{j}$, the
probability density function of
$\log\left(\frac{\phi^{s}(y^{j}|q^{j})}{\phi^{s^{*}}(y^{j}|q^{j})}\right)$ is
also continuous in $q^{j}$. In Lemma 2, we proved that
$\left(q^{k}\right)_{k=1}^{\infty}$ converges to $\bar{q}$. Then, the
distribution of
$\log\left(\frac{\phi^{s}(y^{j}|q^{j})}{\phi^{s^{*}}(y^{j}|q^{j})}\right)$
must converge to the distribution of
$\log\left(\frac{\phi^{s}(y|\bar{q})}{\phi^{s^{*}}(y|\bar{q})}\right)$. Note
that for any $s\in S\setminus S^{*}(\bar{q})$, the expectation of
$\log\left(\frac{\phi^{s}(y|\bar{q})}{\phi^{s^{*}}(y|\bar{q})}\right)$ can be
written as:

$\displaystyle\mathbb{E}\left[\log\left(\frac{\phi^{s}(y|\bar{q})}{\phi^{s^{*}}(y|\bar{q})}\right)\right]=\int_{y}\phi^{s^{*}}(y|\bar{q})\cdot\log\left(\frac{\phi^{s}(y|\bar{q})}{\phi^{s^{*}}(y|\bar{q})}\right)dy=-D_{KL}\left(\phi^{s^{*}}(y|\bar{q})||\phi^{s}(y|\bar{q})\right)<0.$

If we can show that the equation (A) below holds, then we can conclude that
the log-likelihood sequence defined by (22) converges to $-\infty$; this would
in turn imply that the sequence of likelihood ratios
$\frac{\Phi^{s}(Y^{k_{t}-1}|Q^{k_{t}-1})}{\Phi^{s^{*}}(Y^{k_{t}-1}|Q^{k_{t}-1})}$
must converge to 0. But first we need to show:

$\displaystyle\lim_{t\to\infty}\frac{1}{k_{t}-1}\log\left(\frac{\Phi^{s}(Y^{k_{t}-1}|Q^{k_{t}-1})}{\Phi^{s^{*}}(Y^{k_{t}-1}|Q^{k_{t}-1})}\right)$
$\displaystyle=\lim_{t\to\infty}\frac{1}{k_{t}-1}\sum_{j=1}^{k_{t}-1}\log\left(\frac{\phi^{s}(y^{j}|q^{j})}{\phi^{s^{*}}(y^{j}|q^{j})}\right)$
$\displaystyle=\mathbb{E}\left[\log\left(\frac{\phi^{s}(y|\bar{q})}{\phi^{s^{*}}(y|\bar{q})}\right)\right],\quad
w.p.~{}1.$ (23)

We denote the cumulative distribution function of
$\log\left(\frac{\phi^{s}(y^{j}|q^{j})}{\phi^{s^{*}}(y^{j}|q^{j})}\right)$ as
$F^{j}(z):\mathbb{R}\to[0,1]$, i.e.
$F^{j}(z)=\mathrm{Pr}\left(\log\left(\frac{\phi^{s}(y^{j}|q^{j})}{\phi^{s^{*}}(y^{j}|q^{j})}\right)\leq
z\right)$. The cumulative distribution function of
$\log\left(\frac{\phi^{s}(y|\bar{q})}{\phi^{s^{*}}(y|\bar{q})}\right)$ is
denoted $\bar{F}(z):\mathbb{R}\to[0,1]$, i.e.
$\bar{F}(z)=\mathrm{Pr}\left(\log\left(\frac{\phi^{s}(y|\bar{q})}{\phi^{s^{*}}(y|\bar{q})}\right)\leq
z\right)$. Then,

$\displaystyle\lim_{j\to\infty}F^{j}(z)=\bar{F}(z),\quad\forall
z\in\mathbb{R}.$ (24)

For any sequence of realized payoffs $(y^{j})_{j=1}^{\infty}$, we define a
sequence of random variables $\Delta=\left(\Delta^{j}\right)_{j=1}^{\infty}$,
where
$\Delta^{j}=F^{j}\left(\log\left(\frac{\phi^{s}(y^{j}|q^{j})}{\phi^{s^{*}}(y^{j}|q^{j})}\right)\right)$.
Then, we must have $\Delta^{j}\in[0,1]$, and for any $\delta\in[0,1]$,
$\mathrm{Pr}(\Delta^{j}\leq\delta)=\mathrm{Pr}\left(F^{j}\left(\log\left(\frac{\phi^{s}(y^{j}|q^{j})}{\phi^{s^{*}}(y^{j}|q^{j})}\right)\right)\leq\delta\right)=\delta$.
That is, $\Delta^{j}$ is independently and uniformly distributed on $[0,1]$.
Consider another sequence of random variables
$\left(\eta^{j}\right)_{j=1}^{\infty}$, where
$\eta^{j}\stackrel{{\scriptstyle\Delta}}{{=}}\left(\bar{F}\right)^{-1}(\Delta^{j})$.
Since $\Delta^{j}$ is i.i.d. with uniform distribution, $\eta^{j}$ is also
i.i.d. with the same distribution as
$\log\left(\frac{\phi^{s}(y|\bar{q})}{\phi^{s^{*}}(y|\bar{q})}\right)$.
Additionally, since each $\Delta^{j}$ is generated from the realized payoff
$y^{j}$, $\left(\eta^{j}\right)_{j=1}^{\infty}$ is in the same probability
space as
$\log\left(\frac{\phi^{s}(y^{j}|q^{j})}{\phi^{s^{*}}(y^{j}|q^{j})}\right)$.
From (24), we know that as $j\to\infty$, $F^{j}$ converges to $\bar{F}$.
Therefore, with probability 1,

$\displaystyle\lim_{j\to\infty}\left|\log\left(\frac{\phi^{s}(y^{j}|q^{j})}{\phi^{s^{*}}(y^{j}|q^{j})}\right)-\eta^{j}\right|=\lim_{j\to\infty}\left|\log\left(\frac{\phi^{s}(y^{j}|q^{j})}{\phi^{s^{*}}(y^{j}|q^{j})}\right)-(\bar{F})^{-1}F^{j}\left(\log\left(\frac{\phi^{s}(y^{j}|q^{j})}{\phi^{s^{*}}(y^{j}|q^{j})}\right)\right)\right|=0.$

Consequently, with probability 1,

$\displaystyle\lim_{t\to\infty}\left|\frac{1}{k_{t}-1}\sum_{j=1}^{k_{t}-1}\left(\log\left(\frac{\phi^{s}(y^{j}|q^{j})}{\phi^{s^{*}}(y^{j}|q^{j})}\right)-\eta^{j}\right)\right|\leq\lim_{t\to\infty}\frac{1}{k_{t}-1}\sum_{j=1}^{k_{t}-1}\left|\log\left(\frac{\phi^{s}(y^{j}|q^{j})}{\phi^{s^{*}}(y^{j}|q^{j})}\right)-\eta^{j}\right|=0.$
(25)

Since $\left(\eta^{j}\right)_{j=1}^{\infty}$ is independently and identically
distributed according to the distribution of
$\log\left(\frac{\phi^{s}(y|\bar{q})}{\phi^{s^{*}}(y|\bar{q})}\right)$, from
strong law of large numbers, we have:

$\displaystyle\lim_{t\to\infty}\frac{1}{k_{t}-1}\sum_{j=1}^{k_{t}-1}\eta^{j}=\mathbb{E}\left[\log\left(\frac{\phi^{s}(y|\bar{q})}{\phi^{s^{*}}(y|\bar{q})}\right)\right]=-D_{KL}\left(\phi^{s^{*}}(y|\bar{q})||\phi^{s}(y|\bar{q})\right),\quad
w.p.~{}1.$

From (25), we obtain the following:

$\displaystyle\lim_{t\to\infty}\frac{1}{k_{t}-1}\sum_{j=1}^{k_{t}-1}\log\left(\frac{\phi^{s}(y^{j}|q^{j})}{\phi^{s^{*}}(y^{j}|q^{j})}\right)=\lim_{t\to\infty}\frac{1}{k_{t}-1}\sum_{j=1}^{k_{t}-1}\eta^{j}=-D_{KL}\left(\phi^{s^{*}}(y|\bar{q})||\phi^{s}(y|\bar{q})\right),\quad
w.p.~{}1$ (26)

Hence, (A) holds. Then, for any $s\in S\setminus S^{*}(\bar{q})$,
$\lim_{t\to\infty}\frac{\Phi^{s}(Y^{k_{t}-1}|Q^{k_{t}-1})}{\Phi^{s^{*}}(Y^{k_{t}-1}|Q^{k_{t}-1})}=0$.
Thus, from (21), we know that $\lim_{t\to\infty}\theta^{k_{t}}(s)=0$ for all
$s\in S\setminus S^{*}(\bar{q})$. Since for any $k=k_{t}+1,\dots,k_{t+1}-1$,
$\theta^{k}=\theta^{k_{t}}$, we know that
$\lim_{k\to\infty}\frac{\Phi^{s}(Y^{k-1}|Q^{k-1})}{\Phi^{s^{*}}(Y^{k-1}|Q^{k-1})}=0$
and $\lim_{k\to\infty}\theta^{k}(s)=0$ for all $s\in S\setminus
S^{*}(\bar{q})$.

Finally, since $\theta^{1}(s)>0$ for all $s\in S$, the true parameter $s^{*}$
is never excluded from the belief. Therefore,
$\lim_{k\to\infty}\frac{1}{k}\log\left(\theta^{k}(s^{*})\right)=0$. For any
$s\in S\setminus S^{*}(\bar{q})$, we have the following:

$\displaystyle\lim_{k\to\infty}\frac{1}{k}\log\left(\theta^{k}(s)\right)=\lim_{k\to\infty}\frac{1}{k}\log\left(\theta^{k}(s^{*})\right)+\lim_{k\to\infty}\frac{1}{k}\log\left(\frac{\theta^{k}(s)}{\theta^{k}(s^{*})}\right)$
$\displaystyle=\lim_{k\to\infty}\frac{1}{k}\log\left(\frac{\theta^{k}(s)}{\theta^{k}(s^{*})}\right)=\lim_{k\to\infty}\frac{1}{k}\log\left(\frac{\theta^{1}(s)}{\theta^{1}(s^{*})}\right)+\lim_{k\to\infty}\frac{1}{k}\log\left(\frac{\Phi^{s}(Y^{k-1}|Q^{k-1})}{\Phi^{s^{*}}(Y^{k-1}|Q^{k-1})}\right)$
$\displaystyle=\mathbb{E}\left[\log\left(\frac{\phi^{s}(y|\bar{q})}{\phi^{s^{*}}(y|\bar{q})}\right)\right]=-D_{KL}\left(\phi^{s^{*}}(y|\bar{q})||\phi^{s}(y|\bar{q})\right),\quad
w.p.~{}1.$

_Case 2:_ $\phi^{s^{*}}(y|\bar{q})$ is not absolutely continuous in
$\phi^{s}(y|\bar{q})$.
In this case, $\phi^{s}(y|\bar{q})=0$ does not imply
$\phi^{s^{*}}(y|\bar{q})=0$ with probability 1, i.e.
$\mathrm{Pr}\left(\phi^{s}(y|\bar{q})=0\right)>0$, where
$\mathrm{Pr}\left(\cdot\right)$ is the probability of $y$ with respect to the
true distribution $\phi^{s^{*}}(y|\bar{q})$. Since the distributions
$\phi^{s}(y|q)$ and $\phi^{s^{*}}(y|q)$ are continuous in $q$, the probability
$\mathrm{Pr}\left(\phi^{s}(y|q)=0\right)$ must also be continuous in $q$.
Therefore, for any
$\epsilon\in\left(0,\mathrm{Pr}\left(\phi^{s}(y|\bar{q})=0\right)\right)$,
there exists $\delta>0$ such that
$\mathrm{Pr}\left(\phi^{s}(y|q)=0\right)>\epsilon$ for all
$q\in\\{q|\|q-\bar{q}\|<\delta\\}$.

From Lemma 2, we know that $\lim_{k\to\infty}q^{k}=\bar{q}$. Hence, we can
find a positive number $K_{1}>0$ such that for any $k>K_{1}$,
$\|q^{k}-\bar{q}\|<\delta$, and hence
$\mathrm{Pr}\left(\phi^{s}(y^{k}|q^{k})=0\right)>\epsilon$. We then have
$\sum_{k=1}^{\infty}\mathrm{Pr}\left(\phi^{s}(y^{k}|q^{k})=0\right)=\infty$.
Moreover, since the event $\phi^{s}(y^{k}|q^{k})=0$ is independent from the
event $\phi^{s}(y^{k^{\prime}}|q^{k^{\prime}})=0$ for any $k,k^{\prime}$, we
can conclude that $\mathrm{Pr}\left(\phi^{s}(y^{k}|q^{k})=0,\text{infinitely
often}\right)=1$ based on the second Borel-Cantelli lemma. Hence,
$\mathrm{Pr}\left(\phi^{s}(y^{k}|q^{k})>0,~{}\forall k\right)=0$. From the
Bayesian update ($\theta$-update), we know that if $\phi^{s}(y^{k}|q^{k})=0$
for some stage $k$, then any belief of $s$ updated after stage $k$ is 0.
Therefore, we can conclude that $\mathrm{Pr}\left(\theta^{k}(s)>0,~{}\forall
k\right)=0$ with probability 1, i.e. there exists a positive number
$K^{*}>K_{1}$ with probability 1 such that $\theta^{k}(s)=0$ for any
$k>K^{*}$. $\square$

_Proof of Proposition 1._ Firstly, if $[\theta]\setminus S^{*}(q)$ is a non-
empty set for any $\theta\in\Delta(S)\setminus\\{\theta^{*}\\}$ and any
$q\in\mathrm{EQ}(\theta)$, then no belief with imperfect information
$\theta\in\Delta(S)\setminus\\{\theta^{*}\\}$ satisfies (5a). That is, only
the complete information belief vector $\theta^{*}$ can be a fixed point
belief. Therefore, all fixed point must be complete information fixed points.

On the other hand, assume for the sake of contradiction that there exists a
belief $\theta^{\dagger}\in\Delta(S)\setminus\\{\theta^{*}\\}$ such that
$[\theta^{\dagger}]\subseteq S^{*}(q^{\dagger})$ for an equilibrium strategy
$q^{\dagger}\in\mathrm{EQ}(\theta^{\dagger})$, then
$\left(\theta^{\dagger},q^{\dagger}\right)$, which is not a complete
information fixed point, is in the set $\Omega$. Thus, we arrive at a
contradiction.

Secondly, from condition _(i)_ that $[\bar{\theta}]\subseteq S^{*}(q)$ for any
$\|q-\bar{q}\|<\xi$, we have:

$\displaystyle\mathbb{E}_{\bar{\theta}}[u_{i}^{s}(q)]=u_{i}^{s^{*}}(q),\quad\forall
i\in I.$ (27)

For any $\bar{q}\in\mathrm{EQ}(\bar{\theta})$, from condition _(ii)_ that
$\bar{q}_{i}$ is a best response to $\bar{q}_{-i}$, $\bar{q}_{i}$ must be a
local maximizer of $\mathbb{E}_{\bar{\theta}}[u_{i}^{s}(q_{i},\bar{q}_{-i})]$.
From (27), $\bar{q}_{i}$ is a local maximizer of
$u_{i}^{s^{*}}(q_{i},\bar{q}_{-i})$. Since the function
$u_{i}^{s^{*}}(q_{i},\bar{q}_{-i})$ is concave in $q_{i}$, $\bar{q}_{i}$ is
also a global maximizer of $u_{i}^{s^{*}}(q_{i},\bar{q}_{-i})$, and hence is a
best response of $\bar{q}_{-i}$ with complete information of $s^{*}$. Since
this argument holds for all $i\in I$, $\bar{q}$ is a complete information
equilibrium. $\square$

_Proof of Proposition 2._ On one hand, if
$\Omega=\\{\left(\theta^{*},\mathrm{EQ}(\theta^{*})\right)\\}$, then for any
initial state, the learning dynamics converges to a complete information fixed
point with belief $\theta^{*}$ and strategy in $\mathrm{EQ}(\theta^{*})$. That
is, $\left(\theta^{*},\mathrm{EQ}(\theta^{*})\right)$ is globally stable. On
the other hand, if there exists another fixed point
$\left(\theta^{\dagger},q^{\dagger}\right)\in\Omega\setminus\\{\left(\theta^{*},\mathrm{EQ}(\theta^{*})\right)\\}$,
then learning that starts with the initial belief
$\theta^{1}=\theta^{\dagger}$ (resp. $\theta^{1}=\theta^{*}$) and strategy
$q^{1}=q^{\dagger}$ (resp. $q^{1}=q^{*}$) remains at
$\left(\theta^{\dagger},q^{\dagger}\right)$ (resp.
$\left(\theta^{*},q^{*}\right)$) for all stages w.p. 1. Thus, in this case,
globally stable fixed points do not exist. $\square$

_Proof of Lemma 4._

  * (i)

From Assumption _(A2a)_ , we know that such $\epsilon^{\prime}$ must exist.

  * (ii)

Since $\hat{\epsilon}\leq\epsilon$, we know from Assumption _(A2b)_ that
$\mathrm{BR}(\theta,q)\subseteq
N_{\delta}\left(\mathrm{EQ}(\bar{\theta})\right)$ for any $\theta\in
N_{\hat{\epsilon}}\left(\bar{\theta}\right)$ and any $q\in
N_{\delta}\left(\mathrm{EQ}(\bar{\theta})\right)$.

  * (iii)

Under Assumption 1, we know from Theorem 1 that the sequence of the beliefs
and strategies converges to a fixed point
$\left(\theta^{\dagger},q^{\dagger}\right)$. If $\theta^{k}\in
N_{\hat{\epsilon}}(\bar{\theta})$ for all $k$, then
$\lim_{k\to\infty}\theta^{k}=\theta^{\dagger}\in
N_{\hat{\epsilon}}(\bar{\theta})\subseteq N_{\bar{\epsilon}}(\bar{\theta})$.
Additionally, from _(i)_ and the fact that
$\hat{\epsilon}\leq\epsilon^{\prime}$, we know that
$\lim_{k\to\infty}q^{k}=q^{\dagger}\in\mathrm{EQ}(\theta^{\dagger})\subseteq
N_{\bar{\delta}}\left(\mathrm{EQ}(\bar{\theta})\right)$. Therefore,

$\displaystyle\lim_{k\to\infty}\mathrm{Pr}\left(\theta^{k}\in
N_{\bar{\epsilon}}(\bar{\theta}),~{}q^{k}\in
N_{\bar{\delta}}(\mathrm{EQ}(\bar{\theta}))\right)\geq$
$\displaystyle\mathrm{Pr}\left(\theta^{k}\in
N_{\hat{\epsilon}}(\bar{\theta}),~{}\forall k\right)$ $\displaystyle\geq$
$\displaystyle\mathrm{Pr}\left(\theta^{k}\in
N_{\hat{\epsilon}}(\bar{\theta}),q^{k}\in
N_{\delta}(\mathrm{EQ}(\bar{\theta})),~{}\forall k\right).$

$\square$

In the proofs of Lemmas 5 – 6, we denote
$\left(\tilde{\theta}^{k}\right)_{k=1}^{\infty}$ as an auxiliary belief
sequence that is updated in every stage (instead of just updated at
$\left(k_{t}\right)_{k=1}^{\infty}$). That is,

$\displaystyle\tilde{\theta}^{1}=\theta^{1},\text{ and
}~{}\tilde{\theta}^{k+1}(s)=\frac{\tilde{\theta}^{k}(s)\phi^{s}(y^{k}|q^{k})}{\sum_{s^{\prime}\in
S}\tilde{\theta}^{k}(s^{\prime})\phi^{s^{\prime}}(y^{k}|q^{k})},\quad\forall
s\in S,\quad\forall k=1,2,\dots$ (28)

From ($\theta$-update), we know that

$\displaystyle\theta^{k}=\left\\{\begin{array}[]{ll}\tilde{\theta}^{k},&\quad\text{if
}k=k_{t},\quad\forall k=1,2,\dots,\\\
\theta^{k-1},&\quad\text{otherwise}.\end{array}\right.$ (31)

_Proof of Lemma 5._ First, note that
$0<\rho^{1}<\rho^{2}<\frac{\hat{\epsilon}}{|S|}$. For any $s\in
S\setminus[\bar{\theta}]$ and any $k>1$, we denote $U^{k}(s)$ the number of
upcrossings of the interval $[\rho^{1},\rho^{2}]$ that the belief
$\tilde{\theta}^{j}(s)$ completes by stage $k$. That is, $U^{k}(s)$ is the
maximum number of intervals
$\left([\underline{k}_{i},\overline{k}_{i}]\right)_{i=1}^{U^{k}(s)}$ with
$1\leq\underline{k}_{1}<\overline{k}_{1}<\underline{k}_{2}<\overline{k}_{2}<\cdots<\underline{k}_{U^{k}(s)}<\overline{k}_{U^{k}(s)}\leq
k$, such that
$\tilde{\theta}^{\underline{k}_{i}}(s)<\rho^{1}<\rho^{2}<\tilde{\theta}^{\overline{k}_{i}}(s)$
for $i=1,\dots U^{k}(s)$. Since the beliefs
$\left(\tilde{\theta}^{j}(s)\right)_{j=1}^{k}$ are updated based on randomly
realized payoffs $\left(y^{j}\right)_{j=1}^{k}$ as in (28), $U^{k}(s)$ is also
a random variable. For any $k>1$, $U^{k}(s)\geq 1$ if and only if
$\tilde{\theta}^{1}(s)<\rho^{1}$ and there exists a stage $j\leq k$ such that
$\tilde{\theta}^{j}(s)>\rho^{2}$. Equivalently, $\lim_{k\to\infty}U^{k}(s)\geq
1$ if and only if $\tilde{\theta}^{1}(s)<\rho^{1}$ and there exists a stage
$k>1$ such that $\tilde{\theta}^{k}(s)>\rho^{2}$. Therefore, if
$\tilde{\theta}^{1}(s)<\rho^{1}$ for all $s\in S\setminus[\bar{\theta}]$,
then:

$\displaystyle\mathrm{Pr}\left(\tilde{\theta}^{k}(s)\leq\rho^{2},~{}\forall
s\in S\setminus[\bar{\theta}],~{}\forall k\right)=1-\mathrm{Pr}\left(\exists
s\in S\setminus[\bar{\theta}]\text{ and
}k,~{}s.t.~{}\tilde{\theta}^{k}(s)>\rho^{2}\right)$ $\displaystyle\geq$
$\displaystyle 1-\sum_{s\in S\setminus[\bar{\theta}]}\mathrm{Pr}\left(\exists
k,~{}s.t.~{}~{}\tilde{\theta}^{k}(s)>\rho^{2}\right)=1-\sum_{s\in
S\setminus[\bar{\theta}]}\lim_{k\to\infty}\mathrm{Pr}\left(U^{k}(s)\geq
1\right).$ (32)

Next, we define
$\alpha\stackrel{{\scriptstyle\Delta}}{{=}}\bar{\theta}(s^{*})-\rho^{1}$.
Since $0<\rho^{1}<\min_{s\in[\bar{\theta}]}\\{\bar{\theta}(s)\\}$ and $s^{*}$
is in the support set, we have $\alpha\in(0,\bar{\theta}(s^{*}))$. If
$\tilde{\theta}^{1}(s)$ satisfies (11a) – (11b), then
$\frac{\tilde{\theta}^{1}(s)}{\tilde{\theta}^{1}(s^{*})}<\frac{\rho^{1}}{\alpha}$
for all $s\in S\setminus[\bar{\theta}]$. Additionally, for any stage $k$ and
any $s\in S\setminus[\bar{\theta}]$, if $\tilde{\theta}^{k}(s)>\rho^{2}$, then
$\frac{\tilde{\theta}^{k}(s)}{\tilde{\theta}^{k}(s^{*})}\geq\rho^{2}$ because
$\tilde{\theta}^{k}(s^{*})\leq 1$. Hence, whenever $\tilde{\theta}^{k}(s)$
completes an upcrossing of the interval $\left[\rho^{1},\rho^{2}\right]$,
$\frac{\tilde{\theta}^{k}(s)}{\tilde{\theta}^{k}(s^{*})}$ must also have
completed an upcrosssing of the interval
$\left[\frac{\rho^{1}}{\alpha},\rho^{2}\right]$. From (10a) – (10b), we can
check that $\frac{\rho^{1}}{\alpha}<\rho^{2}$ so that the interval
$\left[\frac{\rho^{1}}{\alpha},\rho^{2}\right]$ is valid. We denote
$\hat{U}^{k}(s)$ as the number of upcrossings of the sequence
$\left(\frac{\tilde{\theta}^{j}(s)}{\tilde{\theta}^{j}(s^{*})}\right)_{j=1}^{k}$
with respect to the interval $\left[\frac{\rho^{1}}{\alpha},\rho^{2}\right]$
until stage $k$. Then, $U^{k}(s)\leq\hat{U}^{k}(s)$ for all $k$. Therefore, we
can write:

$\displaystyle\mathrm{Pr}\left(U^{k}(s)\geq
1\right)\leq\mathrm{Pr}\left(\hat{U}^{k}(s)\geq
1\right)\leq\mathbb{E}\left[\hat{U}^{k}(s)\right],$ (33)

where the last inequality is due to Makov inequality.

From the proof of Lemma 1, we know that the sequence
$\left(\frac{\tilde{\theta}^{k}(s)}{\tilde{\theta}^{k}(s^{*})}\right)_{k=1}^{\infty}$
is a martingale. Therefore, we can apply the Doob’s upcrossing inequality as
follows:

$\displaystyle\mathbb{E}\left[\hat{U}^{k}(s)\right]\leq\frac{\mathbb{E}\left[\max\\{\frac{\rho^{1}}{\alpha}-\frac{\tilde{\theta}^{k}(s)}{\tilde{\theta}^{k}(s^{*})},0\\}\right]}{\rho^{2}-\frac{\rho^{1}}{\alpha}}\leq\frac{\frac{\rho^{1}}{\alpha}}{\rho^{2}-\frac{\rho^{1}}{\alpha}},\quad\forall
k.$ (34)

From (31), (32) – (34), and (10a) – (10b), we can conclude that:

$\displaystyle\mathrm{Pr}\left(\theta^{k}(s)\leq\rho^{2},~{}\forall s\in
S\setminus[\bar{\theta}],~{}\forall
k\right)=\mathrm{Pr}\left(\tilde{\theta}^{k}(s)\leq\rho^{2},~{}\forall s\in
S\setminus[\bar{\theta}],~{}\forall k\right)$ $\displaystyle\geq$
$\displaystyle
1-\frac{\frac{\rho^{1}}{\alpha}|S\setminus[\bar{\theta}]|}{\rho^{2}-\frac{\rho^{1}}{\alpha}}=1-\frac{\frac{\rho^{1}}{\bar{\theta}(s^{*})-\rho^{1}}|S\setminus[\bar{\theta}]|}{\rho^{2}-\frac{\rho^{1}}{\bar{\theta}(s^{*})-\rho^{1}}}>\gamma.$

$\square$

_Proof of Lemma 6._ From Assumption _(A2c)_ , we know that
$[\bar{\theta}]\subseteq S^{*}(q^{1})$ if $q^{1}\in
N_{\delta}\left(\mathrm{EQ}(\bar{\theta})\right)$. Hence,
$\phi^{s}(y^{1}|q^{1})=\phi^{s^{*}}(y^{1}|q^{1})$ for any $s\in[\bar{\theta}]$
and any realized payoff $y^{1}$. Therefore,

$\displaystyle\frac{\tilde{\theta}^{2}(s)}{\tilde{\theta}^{2}(s^{*})}=\frac{\tilde{\theta}^{1}(s)}{\tilde{\theta}^{1}(s^{*})}\frac{\phi^{s}(y^{1}|q^{1})}{\phi^{s^{*}}(y^{1}|q^{1})}=\frac{\tilde{\theta}^{1}(s)}{\tilde{\theta}^{1}(s^{*})},\quad
w.p.~{}1,\quad\forall s\in[\bar{\theta}].$ (35)

This implies that
$\frac{\sum_{s\in[\bar{\theta}]}\tilde{\theta}^{2}(s)}{\tilde{\theta}^{2}(s^{*})}=\frac{\sum_{s\in[\bar{\theta}]}\tilde{\theta}^{1}(s)}{\tilde{\theta}^{1}(s^{*})}$,
and for all $s\in[\bar{\theta}]$:

$\displaystyle\frac{\tilde{\theta}^{2}(s)}{\sum_{s\in[\bar{\theta}]}\tilde{\theta}^{2}(s)}=\frac{\tilde{\theta}^{2}(s)}{\tilde{\theta}^{2}(s^{*})}\frac{\tilde{\theta}^{2}(s^{*})}{\sum_{s\in[\bar{\theta}]}\tilde{\theta}^{2}(s)}=\frac{\tilde{\theta}^{1}(s)}{\tilde{\theta}^{1}(s^{*})}\frac{\tilde{\theta}^{1}(s^{*})}{\sum_{s\in[\bar{\theta}]}\tilde{\theta}^{1}(s)}=\frac{\tilde{\theta}^{1}(s)}{\sum_{s\in[\bar{\theta}]}\tilde{\theta}^{1}(s)}.$

Thus, we have

$\displaystyle\frac{\tilde{\theta}^{2}(s)}{\tilde{\theta}^{1}(s)}=\frac{\sum_{s\in[\bar{\theta}]}\tilde{\theta}^{2}(s)}{\sum_{s\in[\bar{\theta}]}\tilde{\theta}^{1}(s)},\quad
w.p.~{}1,\quad\forall s\in[\bar{\theta}].$

Since $\sum_{s\in[\bar{\theta}]}\tilde{\theta}^{1}(s)\leq 1$, if
$\tilde{\theta}^{2}(s)<\rho^{2}$ for all $s\in S\setminus[\bar{\theta}]$, then
we have
$\frac{\tilde{\theta}^{2}(s)}{\tilde{\theta}^{1}(s)}>1-|S\setminus[\bar{\theta}]|\rho^{2}$.
Additionally, since $\sum_{s\in[\bar{\theta}]}\tilde{\theta}^{2}(s)<1$ and
$\tilde{\theta}^{1}(s)<\rho^{3}$ for all $s\in[\bar{\theta}]$, we have
$\frac{\tilde{\theta}^{2}(s)}{\tilde{\theta}^{1}(s)}<\frac{1}{1-|S\setminus[\bar{\theta}]|\rho^{3}}$.
Since by (10c), $\rho^{3}\leq\bar{\theta}(s)$ for all $s\in
S\setminus[\bar{\theta}]$, any
$\tilde{\theta}^{1}(s)\in\left(\bar{\theta}(s)-\rho^{3},\bar{\theta}(s)+\rho^{3}\right)$
is a non-negative number for all $s\in[\bar{\theta}]$. Therefore, we have the
following bounds:

$\displaystyle\left(\bar{\theta}(s)-\rho^{3}\right)\left(1-|S\setminus[\bar{\theta}]|\rho^{2}\right)<\tilde{\theta}^{2}(s)<\frac{\bar{\theta}(s)+\rho^{3}}{1-|S\setminus[\bar{\theta}]|\rho^{3}}.$
(36)

Since

$\displaystyle\rho^{3}\stackrel{{\scriptstyle\eqref{eq:rho_three}}}{{\leq}}\frac{\hat{\epsilon}-|S\setminus[\bar{\theta}]||S|\rho^{2}\bar{\theta}(s)}{|S|-|S\setminus[\bar{\theta}]||S|\rho^{2}},\quad\forall
s\in[\bar{\theta}],$ (37)

we can check that
$\left(\bar{\theta}(s)-\rho^{3}\right)\left(1-|S\setminus[\bar{\theta}]|\rho^{2}\right)\geq\bar{\theta}(s)-\frac{\hat{\epsilon}}{|S|}$
for all $s\in[\bar{\theta}]$. To ensure the right-hand-side of (37) is
positive, we need to have
$\rho^{2}<\frac{\hat{\epsilon}}{|S\setminus[\bar{\theta}]||S|\bar{\theta}(s)}$
for all $s\in[\bar{\theta}]$, which is satisfied by (10b). Also, since
$\rho^{3}\stackrel{{\scriptstyle\eqref{eq:rho_three}}}{{\leq}}\frac{\hat{\epsilon}}{|S|+|S\setminus[\bar{\theta}]|\left(\bar{\theta}(s)|S|+\hat{\epsilon}\right)}$
for all $s\in[\bar{\theta}]$, we have
$\frac{\bar{\theta}(s)+\rho^{3}}{1-|S\setminus[\bar{\theta}]|\rho^{3}}<\bar{\theta}(s)+\frac{\hat{\epsilon}}{|S|}$
for all $s\in[\bar{\theta}]$. Therefore, we can conclude that
$\tilde{\theta}^{2}(s)\in\left(\bar{\theta}(s)-\frac{\hat{\epsilon}}{|S|},\bar{\theta}(s)+\frac{\hat{\epsilon}}{|S|}\right)$
for all $s\in[\bar{\theta}]$. Additionally, if
$\tilde{\theta}^{2}(s)\leq\rho^{2}<\frac{\hat{\epsilon}}{|S|}$ for all $s\in
S\setminus[\bar{\theta}]$, then $\tilde{\theta}^{2}\in
N_{\hat{\epsilon}}\left(\bar{\theta}\right)$. From (31), we have
$\theta^{2}\in N_{\hat{\epsilon}}\left(\bar{\theta}\right)$. From _(ii)_ in
Lemma 4, we know that $\mathrm{BR}(\theta^{2},q^{1})\in
N_{\delta}\left(\mathrm{EQ}(\bar{\theta})\right)$. Since $q^{1}\in
N_{\delta}\left(\mathrm{EQ}(\bar{\theta})\right)$, the updated strategy
$q^{2}$ given by ($q$-update) must also be in the neighborhood
$N_{\delta}\left(\mathrm{EQ}(\bar{\theta})\right)$.

We now use mathematical induction to prove that the belief of any
$s\in[\bar{\theta}]$ satisfies
$\tilde{\theta}^{k}(s)\in\left(\bar{\theta}(s)-\frac{\hat{\epsilon}}{|S|},\bar{\theta}(s)+\frac{\hat{\epsilon}}{|S|}\right)$
for stages $k>2$. If in stages $j=1,\dots,k$,
$|\tilde{\theta}^{j}(s)-\bar{\theta}(s)|<\frac{\hat{\epsilon}}{|S|}$ for all
$s\in[\bar{\theta}]$ and
$\tilde{\theta}^{j}(s)<\rho^{2}<\frac{\hat{\epsilon}}{|S|}$ for all $s\in
S\setminus[\bar{\theta}]$, then $\tilde{\theta}^{j}\in
N_{\hat{\epsilon}}\left(\bar{\theta}\right)$ for all $j=1,\dots,k$. Thus, from
(31) and _(ii)_ in Lemma 4, we have $\theta^{j}\in
N_{\hat{\epsilon}}\left(\bar{\theta}\right)$ and
$\mathrm{BR}\left(\theta^{j},q^{j-1}\right)\subseteq
N_{\delta}\left(\mathrm{EQ}(\bar{\theta})\right)$. Therefore, $q^{j}\in
N_{\delta}\left(\mathrm{EQ}(\bar{\theta})\right)$ for all $j=2,\dots,k$.

From Assumption _(A2c)_ , we know that $[\bar{\theta}]\subseteq S^{*}(q^{j})$
for all $j=1,\dots,k$. Therefore, for any $s\in[\bar{\theta}]$ and any
$j=1,\dots,k$, $\phi^{s}(y^{j}|q^{j})=\phi^{s^{*}}(y^{j}|q^{j})$ with
probability 1. Then, by iteratively applying (35), we have
$\frac{\tilde{\theta}^{k+1}(s)}{\tilde{\theta}^{1}(s)}=\frac{\sum_{s\in[\bar{\theta}]}\tilde{\theta}^{k+1}(s)}{\sum_{s\in[\bar{\theta}]}\tilde{\theta}^{1}(s)}$
for all $s\in[\bar{\theta}]$ with probability 1. Analogous to $k=2$, we can
prove that
$|\tilde{\theta}^{k+1}(s)-\bar{\theta}(s)|<\frac{\hat{\epsilon}}{|S|}$ for all
$s\in[\bar{\theta}]$. From (31), we also have
$|\theta^{k+1}(s)-\bar{\theta}(s)|<\frac{\hat{\epsilon}}{|S|}$ for all
$s\in[\bar{\theta}]$. From the principle of mathematical induction, we
conclude that in all stages $k$,
$|\theta^{k}(s)-\bar{\theta}(s)|<\frac{\hat{\epsilon}}{|S|}$ for all
$s\in[\bar{\theta}]$, and $q^{k}\in
N_{\delta}\left(\mathrm{EQ}(\bar{\theta})\right)$ for all $k$. Therefore, we
have proved (15).

$\square$

Finally, we are ready to prove Theorem 2.

_Proof of Theorem 2._ We combine Lemmas 4 – 6. For any $\gamma\in(0,1)$, and
any $\bar{\epsilon},\bar{\delta}>0$, consider $\delta^{1}=\delta$ and
$\epsilon^{1}\stackrel{{\scriptstyle\Delta}}{{=}}\min\\{\rho^{1},\rho^{3}\\}$
given by (10a) and (10c). If $\theta^{1}\in N_{\epsilon^{1}}(\bar{\theta})$,
then $|\theta^{1}(s)-\bar{\theta}(s)|<\epsilon^{1}$ for all $s\in S$. Recall
from _(iii)_ in Lemma 4, $\lim_{k\to\infty}\mathrm{Pr}\left(\theta^{k}\in
N_{\bar{\epsilon}}(\theta),~{}q^{k}\in
N_{\bar{\delta}}(\mathrm{EQ}(\bar{\theta}))\right)\geq\mathrm{Pr}\left(\theta^{k}\in
N_{\hat{\epsilon}}(\bar{\theta}),~{}q^{k}\in
N_{\delta}\left(\mathrm{EQ}(\bar{\theta})\right),~{}\forall k\right)$. Since