Automated Security Response through
Online Learning with Adaptive Conjectures

Kim Hammar 2, Tao Li3, Rolf Stadler2, and Quanyan Zhu3

Division of Network and Systems Engineering, KTH Royal Institute of Technology, Sweden

Department of Electrical and Computer Engineering, New York University, USA

Email: {kimham<EMAIL_ADDRESS>{tl2636<EMAIL_ADDRESS>
September 2, 2024

We study automated security response for an IT infrastructure and formulate the interaction between an attacker and a defender as a partially observed, non-stationary game. We relax the standard assumption that the game model is correctly specified and consider that each player has a probabilistic conjecture about the model, which may be misspecified in the sense that the true model has probability $0$. This formulation allows us to capture uncertainty about the infrastructure and the intents of the players. To learn effective game strategies online, we design a novel method where a player iteratively adapts its conjecture using Bayesian learning and updates its strategy through rollout. We prove that the conjectures converge to best fits, and we provide a bound on the performance improvement that rollout enables with a conjectured model. To characterize the steady state of the game, we propose a variant of the Berk-Nash equilibrium. We present our method through an advanced persistent threat use case. Simulation studies based on testbed measurements show that our method produces effective security strategies that adapt to a changing environment. We also find that our method enables faster convergence than current reinforcement learning techniques.

Cybersecurity, network security, advanced persistent threat, , game theory, Bayesian learning, rollout.

§ INTRODUCTION

An organization's security strategy has traditionally been defined and updated by domain experts. Though this approach can provide basic security for an organization’s IT infrastructure, a growing concern is that infrastructure update cycles become shorter and attacks increase in sophistication. To address this challenge, game-theoretic methods for automating security strategies have been proposed, whereby the interaction between an attacker and a defender is modeled as a game <cit.>. While such methods can produce optimal security strategies, they rely on unrealistic assumptions about the infrastructure. In particular, most of the current methods are limited to stationary and correctly specified games, which assume a static infrastructure that can be accurately modeled without uncertainty <cit.>. These assumptions are unrealistic for several reasons.

The target infrastructure and the actors involved in the Advanced Persistent Threat () use case.

First, IT infrastructures are dynamic: components fail, software packages are updated, new vulnerabilities are discovered, etc. As a consequence, the game between the attacker and the defender is non-stationary. Second, attacker and defender often have incorrect prior knowledge about the infrastructure and the opponent, which means that players generally have misspecified models. Third, the defender has limited knowledge about an attacker's presence and actions, which means that the game has partial observability.

In this paper, we address the above challenges and present a new game-theoretic method for online learning of security strategies that is applicable to dynamic IT environments where attacker and defender are uncertain about the environment and the opponent's strategy. Using this method, we formulate the interaction between an attacker and a defender as a non-stationary, partially observed game. We relax the standard assumption that the game model is correctly specified and consider the case where each player has a probabilistic conjecture of the model, i.e., a probability distribution over possible models, which may be misspecified in the sense that the true model has probability $0$. Both players iteratively adapt their conjecture using Bayesian learning and update their strategy using rollout <cit.>. We prove that the conjectures converge to best fits, and we provide a bound on the performance improvement that rollout enables with a conjectured model. To characterize the steady state of the game, we define a variant of the Berk-Nash equilibrium <cit.>, which represents a fixed point where players act optimally given their conjectures.

While the study of learning with misspecified models has attracted long-standing interest in economics <cit.>, engineering <cit.>, and psychology <cit.>, it remains unexplored in the security context. Related research in the security literature include (i) game-theoretic approaches based on bounded rationality <cit.>; and (ii) model-free learning techniques <cit.>. (A review of related work can be found in <ref>.) To our knowledge, we provide the first study of learning with misspecified models in a security context. The benefit of this approach is threefold. First, it provides a new methodology to capture uncertainty and misspecification in security games. Second, as we show in this paper, it is applicable to dynamic, non-stationary, and partially observed games. Third, the model conjectures produced by our method are guaranteed to converge under reasonable conditions and the worst-case performance of the learned strategies is bounded.

We present our method through a use case that involves an Advanced Persistent Threat () on an IT infrastructure (see Fig. <ref>). We emulate this infrastructure with a digital twin, on which we run actions and defender responses. During such runs, we collect measurements and logs, from which we estimate infrastructure statistics. This data is then used to instantiate simulations of the use case, based on which we evaluate our method. We find that the method produces effective security strategies that adapt to a changing environment. Simulation results further show that our method enables faster convergence than current reinforcement learning techniques.

* We introduce a novel game-theoretic formulation for the problem of automated security response where each player (i.e., attacker or defender) has a probabilistic conjecture about the game model. This formulation allows us to capture uncertainty about the environment and a player's intent.

* We present a new method for online learning of game strategies where a player iteratively adapts its conjecture using Bayesian learning and updates its strategy through rollout. This method allows us to automatically adapt security strategies to changes in the environment or the intent of the other player.

* We prove that, when using our method, the conjectures of both players converge, and we characterize the steady state as a variant of the Berk-Nash equilibrium <cit.>. We also provide a bound on the performance improvement that rollout enables with a conjectured model.

* We evaluate our method using simulation studies, which are based on measurements from a digital twin running $64$ virtualized servers and $10$ different types of s <cit.>. This evaluation provides insights into how our method performs under different conditions and shows that it outperforms current reinforcement learning techniques.

§ USE CASE: ADVANCED PERSISTENT THREATS (S)

We consider the problem of defending the IT infrastructure of an organization against s. The operator of the infrastructure, which we call the defender, takes measures to protect it against an attacker while providing services to a client population (see Fig. <ref>). The infrastructure includes a set of servers and an Intrusion Detection System () that logs events in real-time. Clients access the services through a public gateway, which is also open to the attacker.

The attacker's goal is to intrude on the infrastructure and compromise its servers. To achieve this goal, the attacker explores the infrastructure through reconnaissance and exploits vulnerabilities while trying to avoid detection.

The defender monitors the infrastructure through observing alerts and other statistics. It can recover potentially compromised servers (e.g., by upgrading their software), which temporarily disrupts service for clients. When deciding to take this response action, the defender balances two conflicting objectives: (i) maintain services to its clients; and (ii) recover compromised servers.

§ GAME MODEL OF THE APT USE CASE

We formulate the above use case as a zero-sum stochastic game with one-sided partial observability

\begin{align}
\Gamma \triangleq \langle \mathcal{N}, \mathcal{S}, (\mathcal{A}_i)_{i \in \mathcal{N}}, f, c, \gamma,  \mathbf{b}_1, \mathcal{O}, z \rangle, \label{eq:game_def}
\end{align}

where $\mathcal{N}$ is the set of players, $\mathcal{S}$ is the set of states, $(\mathcal{A}_i)_{i \in \mathcal{N}}$ are the sets of actions, and $\mathcal{O}$ is the set of observations; $f$ is the transition function, $c$ is the cost function, and $z$ is the observation function; $\gamma$ is the discount factor; and $\mathbf{b}_1$ is the initial state distribution <cit.>. $\Gamma$ is a discrete-time game with two players: the ($\mathrm{D}$)efender and the ($\mathrm{A}$)ttacker.

The attacker and the defender have different observability in the game. The defender observes alerts but has no certainty about the presence of an attacker. The attacker, on the other hand, has complete observability. It has access to all the information that the defender has access to, as well as the defender’s past actions. We can motivate this assumption in several ways. First, the assumption holds for many types of insider attacks <cit.>. Second, it reflects the fact that it is generally not known what information is available to the attacker <cit.>. Third, it significantly reduces the computational complexity of solving the game <cit.>.

In the following subsections, we define the components of the game, its evolution, and the objectives of the players.

\begin{equation}
\label{eq_belief_operator}
\mathds{B}(\mathbf{b}_{t-1}, a^{(\mathrm{D})}_{t-1}, o_t, \pi_{\mathrm{A}})(s_t) \triangleq \frac{z(o_{t} \mid s_{t})\sum_{s_{t-1} \in \mathcal{S}}\sum_{a^{(\mathrm{A})}_{t-1} \in \mathcal{A}_{\mathrm{A}}}\pi_{\mathrm{A}}(a^{(\mathrm{A})}_{t-1} \mid \mathbf{b}_{t-1},s_{t-1})\mathbf{b}_{t-1}(s_{t-1})f(s_{t} \mid s_{t-1}, a^{(\mathrm{D})}_{t-1},a^{(\mathrm{A})}_{t-1})}{\sum_{a^{(\mathrm{A})}_{t-1} \in \mathcal{A}_{\mathrm{A}}}\sum_{s^{\prime},s\in \mathcal{S}}z(o_{t}\mid s^{\prime})\pi_{\mathrm{A}}(a^{(\mathrm{A})}_{t-1} \mid s, \mathbf{b}_{t-1})f(s^{\prime} \mid s, a^{(\mathrm{D})}_{t-1},a^{(\mathrm{A})}_{t-1})\mathbf{b}_{t-1}(s)}.
\end{equation}

Notations. Boldface lower case letters (e.g., $\mathbf{x}$) denote column vectors; upper case calligraphy letters (e.g., $\mathcal{V}$) represent sets. The set of probability distributions over $\mathcal{V}$ is written as $\Delta(\mathcal{V})$. $\mathbbm{1}_{\mathcal{V}}(x)$ is the indicator function. $\delta_{i,j}$ is Kronecker's delta. $\delta_i(\cdot)$ is the Dirac delta function. A random variable is written in upper case (e.g., $X$), a random vector in boldface (e.g., $\mathbf{X}$). The expectation of $f$ with respect to $X$ is written as $\mathbb{E}_X[f]$. $x \sim f$ means that $x$ is sampled from $f$. If the expression $f$ includes many random variables that depend on $\pi$, we simply write $\mathbb{E}_{\pi}[f]$. We use $\mathbb{P}[x|y]$ as a shorthand for $\mathbb{P}[X=x|Y=y]$ and $-k$ as a shorthand for $\mathcal{N}\setminus \mathrm{k}$. Further notations are listed in Table <ref>.

Notation(s)     Description
$\Gamma, c, N$     The game (<ref>), cost function (<ref>), and # servers (<ref>)

$\mathrm{D}, \mathrm{A}$     The defender player and the attacker player (<ref>)

$\mathcal{N},\mathcal{S},\mathcal{O}$     Sets of players, states, and observations (<ref>)

$\mathcal{A}_{\mathrm{D}},\mathcal{A}_{\mathrm{A}}$     Sets of defender and attacker actions (<ref>)

$t, \gamma$     Time step and discount factor (<ref>)

$\pi_{\mathrm{D}},\pi_{\mathrm{A}}$     Defender and attacker strategies (<ref>)

$\Pi = \Pi_{\mathrm{D}} \times \Pi_{\mathrm{A}}$     Defender and attacker strategy spaces (<ref>)

$\tilde{\pi}_{\mathrm{D}},\tilde{\pi}_{\mathrm{A}}$     Best response strategies (<ref>)

$\bm{\pi}^{\star}=(\pi^{\star}_{\mathrm{D}},\pi^{\star}_{\mathrm{A}})$     Optimal strategies (<ref>)

$\mathscr{B}_{\mathrm{D}}, \mathscr{B}_{\mathrm{A}}$     Best response correspondences (<ref>)

$J_{\mathrm{D}}, J_{\mathrm{A}}$     Defender and attacker objectives (<ref>)

$f, z$     Transition function (<ref>) and observation function (<ref>)

$s_t, o_t$     State (<ref>) and observation (<ref>) at time $t$

$\mathbf{a}_t=(a_t^{(\mathrm{D})}, a_t^{(\mathrm{A})})$     Actions at time $t$ (<ref>)

$S_t,O_t$     Random variables with realizations $s_t$ (<ref>) and $o_t$ (<ref>)

$\mathbf{A}_{t}$     Random vector with realization $\mathbf{a}_t$ (<ref>)

$\mathbf{b}_t, \mathbf{B}_t$     Defender belief ($\mathbf{b}_t$ realizes the random vector $\mathbf{B}_t$) (<ref>)

$\mathcal{B}, \mathds{B}$     Belief space and belief operator of the defender (<ref>)

$\mathbf{h}^{(\mathrm{k})}_{t}, \mathbf{h}_{t}$     History of player $\mathrm{k}$ and joint history (<ref>)

$\mathbf{H}^{(\mathrm{k})}_{t}, \mathbf{H}_{t}$     Random vectors with realizations $\mathbf{h}^{(\mathrm{k})}_{t}$ and $\mathbf{h}_{t}$ (<ref>)

$\mathcal{H} = \mathcal{H}_{\mathrm{D}} \times \mathcal{H}_{\mathrm{A}}$     History spaces (<ref>)

$\mathsf{S}, \mathsf{C}$     Stop and continue actions (<ref>)

$\mathscr{R}$     Rollout operator for online learning (<ref>)

$\overline{\pi}_{-\mathrm{k}, t}$     Player $\mathrm{k}$'s conjecture of player $-\mathrm{k}$'s strategy (Alg. <ref>)

$\ell_{\D}, \ell_{\A}$     Lookahead horizons (Alg. <ref>)

$\overline{\ell}_{-\mathrm{k}, t}$     Player $\mathrm{k}$'s conjecture of player $-\mathrm{k}$'s lookahead (Alg. <ref>)

$\bm{\theta}_{t}$     Parameter vector of $\Gamma$ at time $t$ (<ref>)

$\overline{\bm{\theta}}^{(\mathrm{k})}_{t}$     Player $\mathrm{k}$'s conjecture of $\bm{\theta}_{t}$ at time $t$ (<ref>)

$\mathcal{L}, \Theta_{\mathrm{k}}$     Player $\mathrm{k}$'s sets of possible conjectures of $\ell_\A$ and $\bm{\theta}$ (<ref>)

$\mathcal{L}^{\star}, \Theta_{\mathrm{k}}^{\star}$     Sets of consistent conjectures (<ref>)

$\mathbf{i}_t^{(\mathrm{k})},\mathbf{I}_t^{(\mathrm{k})}$     Information feedback of player $\mathrm{k}$ at time $t$ (<ref>)

$\mu_t,\rho^{(\mathrm{k})}_t$     Posteriors $\mathbb{P}[\ell_{\A} \mid \mathbf{h}_t^{(\D)}]$ (<ref>) and $\mathbb{P}[\bm{\theta}^{(\mathrm{k})}_t \mid \mathbf{h}_t^{(\mathrm{k})}]$ (<ref>)

$\nu, K(\overline{\alpha},\nu)$     Occupancy measure and discrepancy of conjecture $\overline{\alpha}$ (<ref>)

$\pi_{1,\mathrm{k}}, \pi_{t,\mathrm{k}}$     Base and rollout strategy of player $\mathrm{k}$ at time $t$ (<ref>)

$\bm{\pi}_{\mathbf{h}_t}$     Strategy profile induced by Alg. <ref> at time $t$ (<ref>)

$\mathbb{P}^{\mathscr{R}}$     Distribution over $\mathcal{H}_\D \times \mathcal{H}_\A$ for $\bm{\pi}_{\mathbf{h}_t}$ (Thm. <ref>)

$K_{\mathcal{L}}^\star,K_{\Theta_{\mathrm{k}}}^\star$     Minimal discrepancy values for $\mathcal{L}$ and $\Theta_{\mathrm{k}}$ (<ref>)

§.§ Actions

Both players can invoke two actions: ($\mathsf{S}$)top and ($\mathsf{C}$)ontinue. The action spaces are thus $\mathcal{A}_{\mathrm{D}}\triangleq \mathcal{A}_{\mathrm{A}}\triangleq \{\mathsf{S},\mathsf{C}\}$. $\mathsf{S}$ triggers a change in the game state while $\mathsf{C}$ is a passive action that does not change the state. Specifically, $a^{(\mathrm{A})}_t=\mathsf{S}$ is the attacker's compromise action and $a^{(\mathrm{D})}_t=\mathsf{S}$ is the defender's recovery action (as defined in the use case <ref>).

§.§ Dynamics

The state $s_t \in \mathcal{S}\triangleq \{0,1,\hdots,N\}$ represents the number of compromised servers at time $t$, where $s_1=0$. The transition $s_t \rightarrow s_{t+1}$ occurs with probability $f\big(s_{t+1} \mid s_t, a^{(\mathrm{D})}_t, a^{(\mathrm{A})}_t\big)$:

\begin{align}
&f(S_{t+1}=0 \mid s_{t}, \mathsf{S}, a^{(\mathrm{A})}_t) \triangleq 1\label{transition_a}\\
&f(S_{t+1}=s_t \mid s_{t}, \mathsf{C}, \mathsf{C}) \triangleq 1\label{transition_b} \\
&f(S_{t+1}=s_t \mid s_{t}, \mathsf{C}, \mathsf{S}) \triangleq 1-p_{\mathrm{A}}\label{transition_c}\\
&f(S_{t+1}=\min[s_t+1,N] \mid s_{t}, \mathsf{C}, \mathsf{S}) \triangleq p_{\mathrm{A}}, \label{transition_d}
\end{align}

where $p_{\mathrm{A}}$ is the probability of a successful attack. All other transitions have probability $0$ (see Fig. <ref>).

(<ref>) defines the transition $s_t \rightarrow 0$, which occurs when the defender takes action $\mathsf{S}$. (<ref>)–(<ref>) define the recurrent transition $s_{t+1}=s_t$, which occurs when both players take action $\mathsf{C}$ or when the attacker is unsuccessful in compromising a server, which happens with probability $1-p_{\mathrm{A}}$. Lastly, (<ref>) defines the transition $s_t \rightarrow s_{t}+1$, which occurs with probability $p_{\mathrm{A}}$ when the attacker takes action $\mathsf{S}$ and the defender takes action $\mathsf{C}$.

§.§ Observability

The attacker has complete observability. It knows the game state, the defender's actions, and the defender's observations. In contrast, the defender has a finite set of observations $o_t \in \mathcal{O}$. Consequently, the information feedbacks for the attacker and the defender at time $t$ are

\begin{align}
\mathbf{i}_t^{(\mathrm{A})} \triangleq (o_t, s_t, a^{(\mathrm{D})}_{t-1}) \quad\text{and}\quad \mathbf{i}_t^{(\mathrm{D})} \triangleq (o_t),\label{eq:information_feedback}
\end{align}

respectively, where $o_t$ is drawn from a random variable $O_t$ whose distribution depends on the state, i.e.,

\begin{align}
o_t \sim z(\cdot \mid s_t).\label{eq:obs_fun}
\end{align}

Both players $\mathrm{k}$ have perfect recall, which means that they remember the play history $\mathbf{h}^{(\mathrm{k})}_t\triangleq (\mathbf{b}_1, a^{(\mathrm{k})}_{l}, \mathbf{i}_l^{(\mathrm{k})})_{l=1,2,\hdots} \in \mathcal{H}_{\mathrm{k}}$. Based on this history, the defender computes the belief state $\mathbf{b}_{t} \in \mathcal{B}$, which is defined as

\begin{align}
\mathbf{b}_{t}(s_{t}) &\triangleq \mathbb{P}[S_t=s_t\mid \mathbf{h}^{(\mathrm{D})}_t],\label{eq:belief_upd}
\end{align}

where $\mathbf{b}_t$ is computed recursively through the operator $\mathds{B}$ (<ref>), which is defined at the top of the page.

State transition diagram of the game: disks represent states; arrows represent state transitions; labels indicate probabilities and conditions for state transition; the initial state is $s_1=0$.

§.§ Strategies and Objectives

Since $\mathbf{b}_t$ is a sufficient statistic for the Markovian state $s_t$ (<ref>), we can define the players' behavioral strategies as $\pi_{\mathrm{D}} \in \Pi_{\mathrm{D}} \triangleq \mathcal{B} \rightarrow \Delta(\mathcal{A}_{\mathrm{D}})$ and $\pi_{\mathrm{A}} \in \Pi_{\mathrm{A}} \triangleq \mathcal{B} \times \mathcal{S} \rightarrow \Delta(\mathcal{A}_{\mathrm{A}})$.

The performance of a defender strategy is quantified using the following cost function

\begin{align}
c(s_t, a^{(\mathrm{D})}_t) &\triangleq \overbrace{s^{p}_t(1-\delta_{\mathsf{S},a^{(\mathrm{D})}_t})}^{\text{intrusion cost}} + \overbrace{\delta_{\mathsf{S},a^{(\mathrm{D})}_t}(q- r\operatorname{sgn}(s_t))}^{\text{response action cost}},\label{eq:cost_fun}
\end{align}

where $p$, $q$, and $r$ are scalar constants (see Fig. <ref>).

The goal of the defender is to minimize the expected cumulative cost and the goal of the attacker is to maximize the same quantity. Therefore, the objective functions are

\begin{align}
J^{(\pi_{\mathrm{D}}, \pi_{\mathrm{A}})}_{\mathrm{D}}(\mathbf{b}_1) &\triangleq \mathbb{E}_{(\pi_{\mathrm{D}}, \pi_{\mathrm{A}})}\left[\sum_{t=1}^{\infty}\gamma^{t-1}c(S_t, A^{(\mathrm{D})}_t) \mid \mathbf{b}_1\right] \label{eq:objective_1}\\
J^{(\pi_{\mathrm{D}}, \pi_{\mathrm{A}})}_{\mathrm{A}}(\mathbf{b}_1) &\triangleq -J^{(\pi_{\mathrm{D}}, \pi_{\mathrm{A}})}_{\mathrm{D}}(\mathbf{b}_1), \label{eq:objective_2}
\end{align}

where $\gamma \in [0,1)$ is a discount factor and $\mathbb{E}_{(\pi_{\mathrm{D}}, \pi_{\mathrm{A}})}$ is the expectation over the random vectors $(\mathbf{H}^{(\mathrm{D})}_t,\mathbf{H}^{(\mathrm{A})}_t)_{t \in \{1,2,\hdots\}}$ when the game is played according to $(\pi_{\mathrm{D}},\pi_{\mathrm{A}})$.

A defender strategy $\tilde{\pi}_{\mathrm{D}} \in \Pi_{\mathrm{D}}$ is a best response against $\pi_{\mathrm{A}}\in \Pi_{\mathrm{A}}$ if it minimizes $J^{(\pi_{\mathrm{D}},\pi_{\mathrm{A}})}_{\mathrm{D}}$ (<ref>). Similarly, an attacker strategy $\tilde{\pi}_{\mathrm{A}}$ is a best response against $\pi_{\mathrm{D}}$ if it maximizes $J^{(\pi_{\mathrm{D}},\pi_{\mathrm{A}})}_{\mathrm{D}}$ (<ref>). Hence, the best response correspondences are

\begin{align}
\mathscr{B}_{\mathrm{D}}(\pi_{\mathrm{A}}) &\triangleq \argmin_{\pi_{\mathrm{D}} \in \Pi_{\mathrm{D}}}J^{(\pi_{\mathrm{D}}, \pi_{\mathrm{A}})}_{\mathrm{D}}(\mathbf{b}_1)\label{eq:br_defender}\\
\mathscr{B}_{\mathrm{A}}(\pi_{\mathrm{D}}) &\triangleq \argmax_{\pi_{\mathrm{A}} \in \Pi_{\mathrm{A}}}J^{(\pi_{\mathrm{D}}, \pi_{\mathrm{A}})}_{\mathrm{D}}(\mathbf{b}_1).\label{eq:br_attacker}
\end{align}

When the infrastructure contains a single server ($N=1$), there exist best responses with threshold structure, as stated below.

If $N=1$ and $z$ (<ref>) is totally positive of order 2 (i.e., tp-2 <cit.>), then

* For any $\pi_{\mathrm{A}} \in \Pi_{\mathrm{A}}$, there exists a value $\alpha^{\star} \in [0,1]$ and a best response $\tilde{\pi}_{\mathrm{D}} \in \mathscr{B}_{\mathrm{D}}(\pi_{\mathrm{A}})$ (<ref>) that satisfies

\begin{align}
\tilde{\pi}_{\mathrm{D}}(b_{t}) &= \mathsf{S} \iff b_{t} \geq \alpha^{\star}. \tag{10a}\label{eq:defender_threshold_strategy}
\end{align}

* For any $\pi_{\mathrm{D}} \in \Pi_{\mathrm{D}}$ that satisfies (<ref>), there exists a value $\beta^{\star}\in [0,1]$ and a best response $\tilde{\pi}_{\mathrm{A}} \in \mathscr{B}_{\mathrm{A}}(\pi_{\mathrm{D}})$ (<ref>) that satisfies

\begin{align}
\tilde{\pi}_{\mathrm{A}}(s_t, b_{t}) &= \mathsf{S} \iff s_t=0, \text{ }b_t < \beta^{\star}.\tag{10b} \label{eq:attacker_threshold_strategy}
\end{align}

See Appendix <ref>.

The above theorem implies that, when $N=1$, the best responses can be parameterized by thresholds, which allows to formulate (<ref>)–(<ref>) as parametric optimization problems. Figure <ref> shows the convergence curves when performing these optimizations with the Cross-Entropy Method () <cit.>.

§.§ Equilibria

When the attacker and the defender play best response, their strategy pair is a Nash equilibrium and can be written as <cit.>

\begin{align}
\bm{\pi}^{\star}= (\pi_{\mathrm{D}}^{\star}, \pi_{\mathrm{A}}^{\star}) \in \mathscr{B}_{\mathrm{D}}(\pi_{\mathrm{A}}^{\star}) \times \mathscr{B}_{\mathrm{A}}(\pi_{\mathrm{D}}^{\star}).\label{eq:minmax_objective}
\end{align}

This equilibrium solves the following minimax problem <cit.>

\begin{align}
\minimize_{\pi_{\mathrm{D}} \in \Pi_{\mathrm{D}}}\maximize_{\pi_{\mathrm{A}} \in \Pi_{\mathrm{A}}}&\text{ } \text{ }J^{(\pi_{\mathrm{D}}, \pi_{\mathrm{A}})}_{\mathrm{D}}(\mathbf{b}_1)\\
\mathrm{subject}\text{ }\mathrm{to} &\text{ }\text{ }s_{t+1} \sim f\big(\cdot \mid s_t, \mathbf{a}_t\big) && \forall t \label{eq:dynamics_constraint}\\
&\text{ }\text{ }o_{t+1} \sim z\big(\cdot \mid s_t) && \forall t \label{eq:obs_constraint}\\
&\text{ }\text{ }a^{(\mathrm{A})}_{t} \sim \pi_{\mathrm{A}}\big(\cdot \mid s_t,\mathbf{b}_t\big) && \forall t\label{eq:attacker_strategy_constraint}\\
&\text{ }\text{ }a^{(\mathrm{D})}_{t} \sim \pi_{\mathrm{D}}\big(\cdot \mid \mathbf{b}_t\big) && \forall t\label{eq:defender_strategy_constraint}\\
&\text{ }\text{ }s_1 \sim \mathbf{b}_1, \label{eq:init_dist_a}
\end{align}

where (<ref>) is the dynamics constraint; (<ref>) describes the observations; (<ref>)–(<ref>) capture the actions; and (<ref>) defines the initial state distribution. (Remark: As a solution to (<ref>) exists <cit.>, we write $\min\max$ instead of $\inf\sup$.)

An example cost function $c(s_t, a^{(\mathrm{D})}_t)$ (<ref>) of $\Gamma$ (<ref>).

Best response learning when $N=1$ using <cit.> and the threshold parameterization expressed in Thm. <ref>; the curves show the mean and the $95\%$ confidence interval from evaluations with $20$ random seeds; hyperparameters are listed in Appendix <ref>.

While any strategy pair $\bm{\pi}^{\star}$ that satisfies (<ref>) is a Nash equilibrium, (<ref>) implies that $\bm{\pi}^{\star}$ together with $\mathds{B}$ (<ref>) form a stronger equilibrium, namely a perfect Bayesian equilibrium <cit.><cit.>.

$\bm{\pi}^{\star}$ (<ref>) and $\mathds{B}$ (<ref>) is a perfect Bayesian equilibrium iff

* $\bm{\pi}^{\star}$ is a Nash equilibrium in $\Gamma|_{\mathbf{h}^{(\mathrm{D})}_t}$ $\forall \mathbf{h}^{(\D)}_t\in \mathcal{H}_{\mathrm{D}}$,
where $\Gamma|_{\mathbf{h}^{(\mathrm{D})}_t}$ is the subgame starting from $\mathds{B}(\mathbf{h}^{(\mathrm{D})}_t,\pi^{\star}_\A)$.

* For any $\mathbf{h}^{(\D)}_t \in \mathcal{H}_{\mathrm{D}}$ with $\mathbb{P}[\mathbf{h}_t^{(\D)} \mid \bm{\pi}^{\star},\mathbf{b}_1]>0$, then

\begin{align*}
\mathds{B}(\mathbf{h}^{(\D)}_{t}, \pi^{\star}_{\A})=\mathds{B}(\mathds{B}(\mathbf{h}^{(\D)}_{t-1}, \pi^{\star}_{\A}), \pi^{\star}_{\mathrm{D}}(\mathds{B}(\mathbf{h}^{(\D)}_{t-1}, \pi^{\star}_{\A})), o_t, \pi^{\star}_{\mathrm{A}}).
\end{align*}

Given the instantiation of $\Gamma$ described in <ref>, the following holds.

* $|\mathscr{B}_{\mathrm{D}}(\pi_{\mathrm{A}})|>0$ and $|\mathscr{B}_{\mathrm{A}}(\pi_{\mathrm{D}})| > 0$ $\forall (\pi_{\mathrm{A}},\pi_{\mathrm{D}})$.

* $\Gamma$ has a a perfect Bayesian equilibrium (Def. <ref>).

Since $\Gamma$ is finite and $\gamma \in [0,1)$, (A) follows from <cit.><cit.>. We omit the proof as it is standard in Markov decision theory. Readers familiar with the literature are encouraged to consult <cit.> for the details. We prove (B) by construction. For any reachable subgame, a Nash equilibrium $\bm{\pi}^{\star}$ exists <cit.><cit.>. For any unreachable subgame $\Gamma|_{\mathbf{h}^{(\mathrm{D})}_k}$, we can construct another Nash equilibrium $\bm{\pi}^{\star,k}$. This follows because the proofs in <cit.><cit.> do not depend on $\mathbf{b}_1$. By combining $\bm{\pi}^{\star}$ with the equilibria of all unreachable subgames, we obtain a perfect Bayesian equilibrium (Def. <ref>).

Figure <ref> shows the value of a perfect Bayesian equilibrium (Def. <ref>) when $N=1$. Interestingly, the defender has the highest expected cost when the belief of compromise ($\mathbf{b}(1)$) is around $0.35$ rather than $0.5$.

The equilibrium value (<ref>) of $\Gamma$ when $N=1$ (computed with the algorithm <cit.>); hyperparameters are listed in Appendix <ref>.

§ PROBLEM STATEMENT

Time required to compute a perfect Bayesian equilibrium (Def. <ref>) of $\Gamma$ (<ref>) with <cit.> for different values of $N$ (Fig. <ref>) and $|\mathcal{O}|$ (Fig. <ref>); error bars indicate the $95\%$ confidence interval based on $20$ measurements; hyperparameters are listed in Appendix <ref>.

While the equilibrium defined above describes how the game ought to be played by rational players, computing it is intractable for any realistic instantiation of the game, as illustrated in Fig. <ref>. Further, the equilibrium assumes a stationary game where both players have correctly specified models, which is not the case in practice. To address these limitations, we relax the standard assumptions and consider a setting where the game is non-stationary and where players may have misspecified game models. In particular, we consider the following problem.
[Non-stationary game with misspecification]
We consider a game $\Gamma_{\bm{\theta}_t}$ based on (<ref>) that is parameterized by a time-dependent vector $\bm{\theta}_t$, which is hidden from the players. This vector can represent the transition function (<ref>), the observation function (<ref>), etc. Player $\mathrm{k}$ has a conjecture of $\bm{\theta}_t$, denoted by $\overline{\bm{\theta}}^{(\mathrm{k})}_t \in \Theta_{\mathrm{k}}$, which is misspecified if $\bm{\theta}_t \not \in \Theta_{\mathrm{k}}$. As $\bm{\theta}_t$ evolves, player $\mathrm{k}$ adapts its conjecture based on feedback $\mathbf{i}^{(\mathrm{k})}_t$ (<ref>) and uses the conjecture to update its strategy $\pi_{\mathrm{k},t}$, starting from a base strategy $\pi_{\mathrm{k},1}$. Strategy updates are parameterized by a lookahead horizon $\ell_{\mathrm{k}}$, which can be understood as a computational constraint. The defender conjectures $\ell_{\A}$ as $\overline{\ell}_{\mathrm{A}} \in \mathcal{L}$, which captures the defender's uncertainty about the attacker's intent. We assume that the attacker knows $\ell_\D$ and the defender's conjectures.

Solving the game described in Prob. <ref> leads to the following questions.

* What is an effective method for a player to update its conjecture and its strategy?

* Do the sequences of conjectures converge?

* Once the parameters $\bm{\theta}_t$ remain constant, how can the steady state of $\Gamma_{\bm{\theta}_t}$ be characterized?

§ ONLINE LEARNING WITH ADAPTIVE CONJECTURES

We address the above questions and define a game-theoretic method for online learning in $\Gamma_{\bm{\theta}_t}$ (Prob. <ref>). Using our method, each player iteratively adapts its conjecture through Bayesian learning and updates its strategy through rollout (see Fig. <ref>). The pseudocode of our method is listed in Alg. <ref>. The main steps of the algorithm are described below.

At time $t$, player $\mathrm{k}$ updates its base strategy $\pi_{\mathrm{k},1}$ as follows.

\begin{align}
&\pi_{\mathrm{k}, t}(\mathbf{b}_t) \in \mathscr{R}(\overline{\bm{\theta}}^{(\mathrm{k})}_{t}, \mathbf{b}_t, \overline{J}_{\mathrm{k}}^{(\bm{\pi}_t)}, \ell_{\mathrm{k}}) \triangleq \argmin_{a_t^{(\mathrm{k})}, a^{(\mathrm{k})}_{t+1},\hdots,a^{(\mathrm{k})}_{t+\ell_{\mathrm{k}}-1}}\label{eq:rollout_operator}\\
&\mathbb{E}_{\bm{\pi}_t}\left[\sum_{j=t}^{t+\ell_{\mathrm{k}}-1}\gamma^{j-t}c_{\mathrm{k}}(S_j, A_j^{(\mathrm{D})}) + \gamma^{\ell_{\mathrm{k}}} \overline{J}_{\mathrm{k}}^{(\bm{\pi}_t)}(\mathbf{B}_{t+\ell_{\mathrm{k}}}) \mid \mathbf{b}_t\right],\nonumber
\end{align}

where $\ell_{\mathrm{k}}$ is the lookahead horizon, $c_{\D}=c$ (<ref>), $c_{\A}=-c$, and $\overline{J}^{(\bm{\pi}_t)}_{\mathrm{k}}$ is the cost function induced by $\overline{\bm{\theta}}^{(\mathrm{k})}_t$ (line 19 in Alg. <ref>).

This rollout step depends on the strategy of the opponent, i.e., $\bm{\pi}_t = (\pi_{\mathrm{k}, 1}, \pi_{\mathrm{-k},t})$. Since the base strategies $(\pi_{\A,1}, \pi_{\D, 1})$ are known to both players, each player can obtain a conjecture of the opponent's strategy from $\overline{\ell}_{-\mathrm{k}}$ (lines 14–17 in Alg. <ref>).

Our method for online learning with adaptive conjectures (see also Alg. <ref>); the figure illustrates one time step during which player $\mathrm{k}$ updates its conjecture $\overline{\bm{\theta}}_t^{(\mathrm{k})}$ and its strategy $\pi_{\mathrm{k},t}$.

Illustration of Thm. <ref>; the x-axis indicates the lookahead horizon $\ell_{\mathrm{k}}$; the y-axis indicates the factor of the performance bound in (<ref>); the curves relate to different discount factors $\gamma$.

We know from dynamic programming that $\pi_{\mathrm{k},t}$ (<ref>) improves on the base strategy $\pi_{\mathrm{k},1}$ <cit.>. The extent of the improvement depends on the lookahead horizon and the accuracy of the conjectures as follows.

The conjectured cost of player $\mathrm{k}$'s rollout strategy $\pi_{\mathrm{k}, t}$ satisfies

\begin{align}
\overline{J}_{\mathrm{k}}^{(\pi_{\mathrm{k}, t}, \overline{\pi}_{\mathrm{-k},t})}(\mathbf{b}) \leq \overline{J}_{\mathrm{k}}^{(\pi_{\mathrm{k}, 1}, \overline{\pi}_{\mathrm{-k},t})}(\mathbf{b}) && \forall \mathbf{b} \in \mathcal{B}. \tag{15a}\label{eq:improvement_conjecture}
\end{align}

Assuming $(\overline{\bm{\theta}}^{(\mathrm{k})}_t, \overline{\ell}_{-\mathrm{k}})$ predicts the game $\ell_{\mathrm{k}}$ steps ahead, then

\begin{align}
\norm{\overline{J}_{\mathrm{k}}^{(\pi_{\mathrm{k}, t}, \overline{\pi}_{\mathrm{-k},t})}-J_{\mathrm{k}}^{\star}} \leq \frac{2\gamma^{\ell_{\mathrm{k}}}}{1-\gamma}\norm{\overline{J}_{\mathrm{k}}^{(\pi_{\mathrm{k}, 1}, \overline{\pi}_{\mathrm{-k},t})}-J_{\mathrm{k}}^{\star}},\tag{15b}\label{cost_conjecture_bound}
\end{align}

where $J_{\mathrm{k}}^{\star}$ is the optimal cost-to-go function when facing $\pi_{-\mathrm{k}, t}$. $\norm{\cdot}$ is the maximum norm $\norm{J}=\max_{x}|J(x)|$.

See Appendix <ref>.

Theorem <ref> states that the performance bound improves superlinearly when the lookahead horizon $\ell_{\mathrm{k}}$ increases or when the conjectured cost function $\overline{J}_{\mathrm{k}}$ moves closer to $J^{\star}_{\mathrm{k}}$ (<ref>), as shown in Fig. <ref>. In particular, (<ref>) suggests that $\ell_{\mathrm{k}}$ controls the trade-off between computational cost and rollout performance (see Fig. <ref>).

After computing (<ref>) and executing the corresponding action, player $\mathrm{k}$ receives the feedback $\mathbf{i}^{(\mathrm{k})}_t$ (<ref>) and updates its conjectures as $\overline{\bm{\theta}}^{(\mathrm{k})}_{t} \sim \rho^{(\mathrm{k})}_{t}$ and $\overline{\ell}_{\A, t} \sim \mu_t$ (line 14 in Alg. <ref>), where $\rho^{(\mathrm{k})}_{t}$ and $\mu_t$ are adapted through Bayesian learning as

\begin{align}
\rho^{(\mathrm{k})}_{t}(\overline{\bm{\theta}}_t^{(\mathrm{k})})&\triangleq \frac{\mathbb{P}[\mathbf{i}^{(\mathrm{k})}_{t}\mid\overline{\bm{\theta}}_t^{(\mathrm{k})}, \mathbf{b}_{t-1}]\rho^{(\mathrm{k})}(\overline{\bm{\theta}}_{t-1}^{(\mathrm{k})})}{\int_{\Theta_{\mathrm{k}}}\mathbb{P}[\mathbf{i}^{(\mathrm{k})}_{t}\mid\overline{\bm{\theta}}_t^{(\mathrm{k})}, \mathbf{b}_{t-1}]\rho^{(\mathrm{k})}_{t-1}(\mathrm{d}\overline{\bm{\theta}}_t^{(\mathrm{k})})} \label{eq:bayesian_estimator_game_1}\\
\mu_{t}(\overline{\ell}_{\A})&\triangleq \frac{\mathbb{P}[\mathbf{i}_t^{(\mathrm{D})}\mid  \overline{\ell}_{\A}, \mathbf{b}_{t-1}]\mu_{t-1}(\overline{\ell}_{\A})}{\sum_{\tilde{\ell}_{\A}\in \mathcal{L}}\mathbb{P}[\mathbf{i}_t^{(\mathrm{D})} \mid  \tilde{\ell}_{\A}, \mathbf{b}_{t-1}]\mu_{t-1}(\tilde{\ell}_{\A})}.\label{eq:bayesian-update}
\end{align}

These Bayesian updates are well-defined using the following assumption.

(i) $\mathcal{L}$ is finite and $\Theta_{\mathrm{k}}$ is a compact subset of an Euclidean space; (ii) $\rho^{(\mathrm{k})}_1$ and $\mu_1$ have full support; and (iii) for all feasible $(\mathbf{i}^{(\mathrm{k})},\mathbf{b}_t)$, there exists $\overline{\bm{\theta}} \in \Theta_{\mathrm{k}}$ and $\overline{\ell}_{\A} \in \mathcal{L}$ that assign positive probability to $\mathbf{i}^{(\mathrm{k})}$ in $\mathbf{b}_t$.

Forpin parallel fordo
DoParalleldo in parallelend

Initial belief $\mathbf{b}_1$, game model $\Gamma_{\bm{\theta}_1}$,

$\quad\quad\quad\text{ }$base strategies $\bm{\pi}_{1}\triangleq (\pi_{\mathrm{D},1}, \pi_{\mathrm{A},1})$, priors $(\mu_1, \rho^{(\D)}_1, \rho^{(\A)}_1)$,

$\quad\quad\quad\text{ }$discount factor $\gamma$, lookahead horizons $\ell_{\mathrm{D}},\ell_{\mathrm{A}}$.

A sequence of action profiles $\mathbf{a}_{1},\mathbf{a}_{2}, \hdots$.

Online learning with adaptive conjectures.

$\mathbf{h}^{(\D)}_1 \leftarrow (\mathbf{b}_1), \mathbf{h}^{(\A)}_1 \leftarrow (\mathbf{b}_1)$,
$s_1 \sim \mathbf{b}_1$
$\overline{\pi}_{\mathrm{A}, 1} \leftarrow \pi_{\A, 1}, \overline{\pi}_{\mathrm{D}, 1} \leftarrow \pi_{\D, 1}$
$a^{(\mathrm{D})}_{1} \sim \pi_{\mathrm{D},1}(\mathbf{b}_1), a^{(\mathrm{A})}_{1} \sim \pi_{\mathrm{A},1}(\mathbf{b}_1, s_1)$
$s_{2} \sim f(\cdot \mid s_1, (a^{(\mathrm{D})}_{1}, a^{(\mathrm{A})}_{1}))$
Defender learning
$o_t \sim z(\cdot \mid s_t)$
$\mathbf{i}^{(\mathrm{D})}_{t} \leftarrow (o_{t}), \quad \mathbf{h}^{(\mathrm{D})}_{t} \leftarrow (\mathbf{h}^{(\mathrm{D})}_{t-1}, \mathbf{i}^{(\mathrm{D})}_{t}, a^{(\mathrm{D})}_{t-1})$
Update $\rho^{(\D)}_t$ and $\mu_t$ (<ref>) and set $\overline{\bm{\theta}}^{(\mathrm{D})}_{t} \sim \rho^{(\D)}_t$ and $\overline{\ell}_{\mathrm{A}, t} \sim \mu_t$
$\mathbf{b}_{t} \leftarrow \mathds{B}(\mathbf{h}^{(\mathrm{D})}_{t}, \overline{\pi}_{\mathrm{A},t-1})$
Estimate $\overline{J}_{\mathrm{A}}^{(\pi_{\mathrm{D},t-1}, \pi_{\mathrm{A},1})}$ using $\Gamma_{\overline{\bm{\theta}}^{(\mathrm{D})}_{t}}$
Compute $\overline{\pi}_{\mathrm{A}, t}(\mathbf{b}_t) \in \mathscr{R}(\overline{\bm{\theta}}^{(\mathrm{D})}_{t}, \mathbf{b}_t, \overline{J}_{\mathrm{A}}^{(\pi_{\mathrm{D},t-1}, \pi_{\mathrm{A},1})}, \overline{\ell}_{\mathrm{A}, t})$
Estimate $\overline{J}_{\mathrm{D}}^{(\pi_{\mathrm{D},1}, \overline{\pi}_{\mathrm{A},t})}$ using $\Gamma_{\overline{\bm{\theta}}^{(\mathrm{D})}_{t}}$
$\pi_{\mathrm{D},t}(\mathbf{b}_t) \in \mathscr{R}(\overline{\bm{\theta}}^{(\mathrm{D})}_{t}, \mathbf{b}_t, \overline{J}_{\mathrm{D}}^{(\pi_{\mathrm{D},1}, \overline{\pi}_{\mathrm{A},t})}, \ell_{\mathrm{D}})$
Attacker learning

$\mathbf{i}^{(\mathrm{A})}_{t} \leftarrow (o_{t}, s_t, a^{(\mathrm{D})}_{t-1}), \quad \mathbf{h}^{(\mathrm{A})}_{t} \leftarrow (\mathbf{h}^{(\mathrm{A})}_{t-1}, \mathbf{i}^{(\mathrm{A})}_{t}, a^{(\mathrm{A})}_{t-1})$
Update $\rho^{(\A)}_t$ using (<ref>) and set $\overline{\bm{\theta}}^{(\mathrm{A})}_{t} \sim \rho^{(\A)}_t$
Estimate $\overline{J}_{\mathrm{A}}^{(\pi_{\mathrm{A},1}, \pi_{\mathrm{D},t})}$ using $\Gamma_{\overline{\bm{\theta}}^{(\mathrm{A})}_{t}}$
$\pi_{\mathrm{A},t}(\mathbf{b}_t) \in \mathscr{R}(\overline{\bm{\theta}}^{(\mathrm{A})}_{t}, \mathbf{b}_t, \overline{J}_{\mathrm{A}}^{(\pi_{\mathrm{A},1}, \pi_{\mathrm{D},t})}, \ell_{\mathrm{A}})$

$a^{(\mathrm{D})}_{t} \sim \pi_{\mathrm{D},t}(\mathbf{b}_t), \quad a^{(\mathrm{A})}_{t} \sim \pi_{\mathrm{A},t}(\mathbf{b}_t, s_t)$
$s_{t+1} \sim f(\cdot \mid s_t, (a^{(\mathrm{D})}_{t}, a^{(\mathrm{A})}_{t}))$

§.§ Convergence and Equilibrium Analysis

When player $\mathrm{k}$ updates its conjectures through (<ref>), the goal is to minimize the discrepancy between the feedback distributions induced by the conjectures and the true model (<ref>). We define this discrepancy as

\begin{align}
K(\overline{\alpha},\nu)&\triangleq \mathbb{E}_{\mathbf{b}\sim \nu}\mathbb{E}_{\mathbf{I}^{(\mathrm{k})}}\left[\ln\left(\frac{\mathbb{P}[\mathbf{I}^{(\mathrm{k})} \mid \alpha, \mathbf{b}]}{\mathbb{P}[\mathbf{I}^{(\mathrm{k})} \mid \overline{\alpha}, \mathbf{b}]}\right)\mid  \alpha, \mathbf{b}\right],\label{eq:discrepancy}
\end{align}

where $\alpha \in \{\bm{\theta}, \ell_{\A}\}$ and $\nu \in \Delta(\mathcal{B})$ is an occupancy measure. We say that conjectures that minimize (<ref>) are consistent with $\nu$ <cit.>[We use the standard convention that $-\ln 0 = \infty$ and $0\ln 0 = 0$.]. Hence, the sets of consistent conjectures at time $t$ are

Exact rollout.

Monte-Carlo rollout with $|\mathcal{O}|=26178$.

Compute time of the rollout operator (<ref>) for varying lookahead horizons $\ell_{\mathrm{k}}$ and observation space sizes $|\mathcal{O}|$; hyperparameters are listed in Appendix <ref>.

\begin{align}
\overline{\bm{\theta}}^{(\mathrm{k})}_t &\in  \Theta_{\mathrm{k}}^\star(\nu_{t}) \triangleq \argmin_{\overline{\bm{\theta}}^{(\mathrm{k})}_{t}\in \Theta_{\mathrm{k}}}K(\overline{\bm{\theta}}^{(\mathrm{k})}_{t}, \nu_{t})\label{eq:consistent_model_conjecture}\\
\overline{\ell}_{\A,t} &\in  \mathcal{L}^\star(\nu_t) \triangleq \argmin_{\overline{\ell}_{\A,t}\in \mathcal{L}}K(\overline{\ell}_{\A,t}, \nu_t),\label{eq:consistent_conjecture}
\end{align}

where $\nu_t\triangleq \frac{1}{t}\sum_{\tau=1}^{t}\mathbbm{1}_{\{\mathbf{b}\}}(\mathbf{b}_{\tau})$ is the empirical occupancy measure and $\bm{\pi}_{\mathbf{h}_t}$ is the empirical strategy profile induced by Alg. <ref> at time $t$.

Intuitively, $\Theta_{\mathrm{k}}^\star$ and $\mathcal{L}^\star$ contain the conjectures that player $\mathrm{k}$ considers possible after observing feedback generated by $\nu_t$ and $\bm{\pi}_{\mathbf{h}_t}$ <cit.>. A desirable property of the conjecture distributions (<ref>) is, therefore, that they concentrate on $\Theta_{\mathrm{k}}^\star$ and $\mathcal{L}^\star$ (<ref>). This property is guaranteed asymptotically under the following conditions.
[Regularity conditions]
For fixed values of $\mathbf{i}^{(\mathrm{k})}$ and $\bm{\theta}$,

* The mapping $\mathbf{b}\mapsto \ln\mathbb{P}[\mathbf{i}^{(\mathrm{k})} | \bm{\theta}, \mathbf{b}]$ is Lipschitz w.r.t. the Wasserstein-$1$ distance, and the Lipschitz constant is independent of $\mathbf{i}^{(\mathrm{k})}$ and $\bm{\theta}$.

* The mapping $\bm{\theta}\mapsto \ln\mathbb{P}[\mathbf{i}^{(\mathrm{k})} | \bm{\theta}, \mathbf{b}]$ is continuous and there exists an integrable function $g_{\mathbf{b}}(\mathbf{i}^{(\mathrm{k})})$ for all $\mathbf{b}\in \mathcal{B}$ such that $|\ln\frac{\mathbb{P}[\mathbf{i}^{(\mathrm{k})} \mid \bm{\theta}, \mathbf{b}]}{\mathbb{P}[\mathbf{i}^{(\mathrm{k})} \mid \overline{\bm{\theta}}, \mathbf{b}]}|\leq g_{\mathbf{b}}(\mathbf{i}^{(\mathrm{k})})$ for all $\overline{\bm{\theta}}\in \Theta_{\mathrm{k}}$.

Given Assumptions <ref>–<ref>, the following holds for any sequence $(\bm{\pi}_{\mathbf{h}_t}, \nu_t)_{t \geq 1}$ generated by Alg. <ref>

\begin{align}
\lim_{t\rightarrow\infty}\sum_{\overline{\ell}_{\A} \in \mathcal{L}} \left(K(\overline{\ell}_{\A},\nu_{t})-K_{\mathcal{L}}^\star(\nu_{t})\right)\mu_{t}(\overline{\ell}_{A})&=0\tag{A}
\end{align}

a.s.-$\mathbb{P}^{\mathscr{R}}$, and provided that $\bm{\theta}_t=\bm{\theta}_1$ for all $t$,

\begin{align}
\lim_{t\rightarrow\infty}\int_{\Theta_{\mathrm{k}}} \left(K(\overline{\bm{\theta}},\nu_{t})-K^\star_{\Theta_{\mathrm{k}}}(\nu_{t})\right)\rho^{(\mathrm{k})}_{t}(\mathrm{d}\overline{\bm{\theta}})&=0\tag{B}
\end{align}

a.s.-$\mathbb{P}^{\mathscr{R}}$, where $(K_{\mathcal{L}}^\star,K_{\Theta_{\mathrm{k}}}^\star)$ denote the minimal values of (<ref>) and $\mathbb{P}^{\mathscr{R}}$ is a probability measure over the set of realizable histories $\mathbf{h} \in \mathcal{H}_\D \times \mathcal{H}_\A$ that is induced by $(\bm{\pi}_{\mathbf{h}_t})_{t\geq 1}$.

See Appendices <ref>–<ref>.

Theorem <ref> states that the conjectures produced by Alg. <ref> are asymptotically consistent (<ref>). This asymptotic consistency means that, if the sequence $(\bm{\pi}_{\mathbf{h}_t}, \nu_t)_{t \geq 1}$ generated by Alg. <ref> converges, then it converges to an equilibrium of the following form.

$(\bm{\pi}, \nu) \in \Pi \times \Delta(\mathcal{B})$ is a Berk-Nash equilibrium of $\Gamma_{\bm{\theta}_t}$ (Prob. <ref>, Alg. <ref>) iff there exist a $\rho^{(\mathrm{k})} \in \Delta(\Theta_{\mathrm{k}})$ for each player $\mathrm{k} \in \{\D, \A\}$ such that

* bounded rationality. $\pi_{\mathrm{k}}$ is a best response against $\pi_{-\mathrm{k}}$ for any $\mathbf{b}$ given $(\nu, \rho^{(\mathrm{k})}, \rho^{(-\mathrm{k})})$, $(\ell_{\mathrm{k}},\ell_{-\mathrm{k}})$, and $\bm{\pi}_1$.

* consistency. $\rho^{(\mathrm{k})} \in \Delta(\Theta_{\mathrm{k}}^{\star}(\nu))$.

* stationarity. $(\bm{\pi}, \nu)$ is a limit point of some sequence $(\bm{\pi}_{\mathbf{h}_t}, \nu_t)_{t \geq 1}$ generated by Alg. <ref>, satisfying

\begin{align*}
\nu(\mathbf{b}^{\prime})= \int_{\mathcal{B}}\mathbb{E}_{A^{(\D)},O, \Gamma_{\bm{\hat{\theta}}}}\left[\delta_{\mathbf{b}^\prime}\big(\mathds{B}(\mathbf{b}, A^{(\D)}, O, \pi_{\A})\big)\right]\mathrm{d}\nu(\mathbf{b}),
\end{align*}

where $\mathds{B}$ is the belief operator defined in (<ref>) and $\Gamma_{\bm{\hat{\theta}}}$ is parameterized by $\bm{\hat{\theta}} \triangleq \int_{\Theta_{\D}}\overline{\bm{\theta}}\mathrm{d}\rho^{(\D)}(\overline{\bm{\theta}})$.

* If the sequence $(\bm{\pi}_{\mathbf{h}_t}, \nu_t)_{t \geq 1}$ generated by Alg. <ref> converges to $(\bm{\pi}, \nu)$, then $(\bm{\pi}, \nu)$ is a Berk-Nash equilibrium (Def. <ref>)

* Given a Berk-Nash equilibrium $(\bm{\pi}, \nu)$ and assuming

\begin{align}
&\overline{\bm{\theta}}^{(\mathrm{k})} \in \Theta_{\mathrm{k}}^{\star}(\nu) \implies \mathbb{P}[\mathbf{I}^{(\mathrm{k})}| \overline{\bm{\theta}}^{(\mathrm{k})},\mathbf{b}]=\mathbb{P}[\mathbf{I}^{(\mathrm{k})}| \bm{\theta},\mathbf{b}] \label{eq:corollary_cond_1}\\
\end{align}

then $(\bm{\pi}, \mathds{B})$ is a perfect Bayesian equilibrium (Def. <ref>).

Condition (i) in Def. <ref> is ensured by rollout (<ref>); condition (ii) is ensured asymptotically by Thm. <ref>; and condition (iii) is a consequence of convergence. Hence, statement (A) holds. Now consider statement (B). Condition 2) in Def. <ref> is satisfied by definition of $\mathds{B}$ (<ref>). To see why condition 1) also must hold, note that assumption (<ref>) together with condition (ii) of Def. <ref> implies that $\mathbb{P}[\mathbf{I}^{(\mathrm{k})}| \bm{\theta},\mathbf{b}]=\mathbb{P}[\mathbf{I}^{(\mathrm{k})}| \overline{\bm{\theta}}^{(\mathrm{k})},\mathbf{b}]$ for any $\overline{\bm{\theta}}^{(\mathrm{k})} \sim \rho^{(\mathrm{k})}$. Consequently, it follows from assumption (<ref>) that $\pi_{\A} \in \mathscr{B}_{\A}(\pi_\D)$ and $\pi_{\D} \in \mathscr{B}_{\D}(\pi_\A)$ for any $\mathbf{b}_1$ (<ref>).

Corollary <ref> states that if the sequence $(\bm{\pi}_{\mathbf{h}_t}, \nu_t)_{t \geq 1}$ generated by Alg. <ref> converges, then it must converge to a Berk-Nash equilibrium. Further, under the conditions defined in (<ref>), this equilibrium is also a perfect Bayesian equilibrium (Def. <ref>). The converse is not necessarily true, however, since the perfect Bayesian equilibrium does not enforce condition (iii) of the Berk-Nash equilibrium (Def. <ref>). This condition requires that $\nu_t$ converges to a stationary distribution, which is not guaranteed to exist. We provide an example in Appendix <ref>.

§ DIGITAL TWIN AND SYSTEM IDENTIFICATION

To implement and evaluate the method described above for the use case (<ref>), we first estimate the parameters of $\Gamma$ (<ref>) using a digital twin of the target infrastructure shown in Fig. <ref>.

§.§ Creating a Digital Twin of the Target Infrastructure

The configuration of the target infrastructure is listed in Appendix <ref>. The topology is shown in Fig. <ref>. It consists of $N=64$ servers, some of which are vulnerable to s.

We create a digital twin of the target infrastructure using an open-source emulation system, which emulates servers with Linux containers and emulates network connectivity with Linux bridges <cit.>. Using this twin, we emulate the attacker using the actions listed in Table <ref> and we emulate the defender through hypervisor-based recovery of servers <cit.>.

§.§ Estimating the Observation Distribution

Following the use case described in <ref>, we define the observation $o_{t}$ (<ref>) to be the priority-weighted sum of the number of alerts at time $t$. For the evaluation reported in this paper, we collect about $M=10^5$ measurements of $o_t$ in the digital twin (the measurements are available at <cit.>, where $|\mathcal{O}|=26178$). Using these measurements, we estimate the observation distribution $z$ (<ref>) with the empirical distribution $\widehat{z}$, where $\widehat{z} \overset{\text{a.s.}}{\rightarrow} z$ as $M \rightarrow \infty$ (Glivenko-Cantelli theorem).

§ EXPERIMENTAL EVALUATION OF OUR METHOD

We implement our method (Fig. <ref>, Alg. <ref>) in Python and evaluate it through simulation studies based on measurements from the digital twin (Fig. <ref>). The source code of our implementation is available at <cit.>. The simulation environment runs on a server with a $24$-core intel xeon gold $2.10$ GHz cpu and $768$ gb ram. Hyperparameters for Alg. <ref> and $\Gamma$ (<ref>) are listed in Appendix <ref>.

The digital twin is a virtual replica of the target infrastructure; we use the twin for evaluation and data collection <cit.>.

Type     Actions
Reconnaissance      scan, port scan, scan

vulnerability scanner, ping-scan

Brute-force     , , , ,

, , , ,

Exploit     -2017-7494, -2015-3306,

-2010-0426, -2015-5602,-2015-1427

-2014-6271, -2016-10033

-89 weakness on the web app dvwa <cit.>

Attacker actions on the digital twin (<ref>); when the attacker takes the stop action (<ref>), a randomly selected action is applied to every reachable server; actions are identified by the vulnerability identifiers in the Common Vulnerabilities and Exposures () database <cit.> and the Common Weakness Enumeration () list <cit.>.

§.§ Evaluation Scenarios

We define four scenarios to evaluate the performance properties of our method (Fig. <ref>, Alg. <ref>). Our aim in evaluating these scenarios is to assess the following: a) the computational requirements of rollout (<ref>); and b) the convergence rate of Alg. <ref> for different instantiations of $\Gamma_{\bm{\theta}_t}$ (Prob. <ref>).

[Defender is uncertain about $\ell_{\A}$]
In this scenario, the game is stationary (i.e., $\bm{\theta}_t=\bm{\theta}_1$ for all $t$) and $\bm{\theta}_1$ is known to both players (i.e., $\rho_{1}^{(\mathrm{k})}(\bm{\theta}_1)=1$), but the defender is uncertain about the attacker's lookahead horizon $\ell_{\A}$, i.e., $\mu_1(\ell_{\A}) < 1$.

[Non-stationary $\bm{\theta}_t$]
In this scenario, $\ell_{\A}$ is known to the defender but the game is non-stationary and $z$ (<ref>) is parameterized by $\bm{\theta}_t$, which represents the number of clients. Clients arrive following a Poisson process with the following rate function (see Figs. <ref>–<ref>) <cit.>

\begin{align}
\lambda(t) &= \exp\Biggl(\underbrace{\sum_{i=1}^{\mathrm{dim}(\bm{\psi})} \bm{\psi}_i t^i}_{\text{trend}} + \underbrace{\sum_{k=1}^{\mathrm{dim}(\bm{\chi})}\bm{\chi}_k \sin(\bm{\omega}_k t + \bm{\phi}_k)}_{\text{periodic}}\Biggr).\label{eq:eptmp}
\end{align}

[Misspecified model conjectures $\rho^{(\D)}_t,\rho^{(\A)}_t$]
In this scenario, the game is stationary (i.e., $\bm{\theta}_t=\bm{\theta}_1$ for all $t$) and $\bm{\theta}_1$ represents the compromise probability $p_{\mathrm{A}}$ (<ref>). Further, the attacker's lookahead horizon $\ell_{\A}$ is known to the defender but both players are uncertain about $\bm{\theta}_1$ and have misspecified conjectures, i.e., $\bm{\theta}_1 \not\in \Theta_{\A} \cup \Theta_{\D}$.

[Defender is uncertain about $\ell_{\A}$ and $\bm{\theta}_t$]
This scenario is the same as Scenario <ref>, except that the defender is uncertain about the attacker's lookahead horizon $\ell_{\A}$, i.e., $\mu_1(\ell_{\A}) < 1$.

The arrival rate function (<ref>) used in Scenario <ref>; the blue curve shows the arrival rate $\lambda(t)$; the red curve shows the trend of $\lambda(t)$ without the periodic effects; and the shaded black curve shows the number of arrivals.

§.§ Evaluation Results (Fig. <ref>)

Estimated distributions of the number of clients and the priority-weighted sum of alerts ($o_t$) during different arrival rates $\lambda(t)$ based on the apt actions listed in Table <ref> and the rate function shown in Fig. <ref>; the curves indicate mean values and the shaded areas indicate standard deviations from $3$ measurements.

Scenario <ref>.
Figures <ref>.a–b show the evolution of the defender's conjecture distribution $\mu_t$ (<ref>) and the discrepancy (<ref>) of the conjecture $\overline{\ell}_{\A,t}$ when $\mathcal{L}=\{1,2\}$ and $\ell_{\A}=1$. We observe that $\mu_t$ converges and concentrates on the consistent conjecture (<ref>) after $5$ time steps, as predicted by Thm. <ref>.A. Figure <ref>.d shows the rate of convergence for different $|\mathcal{L}|$, indicating that a larger $|\mathcal{L}|$ leads to a slower convergence. This is expected since a larger $|\mathcal{L}|$ means that the defender has a higher degree of uncertainty about $\ell_{\A}$.

Figure <ref>.c shows the expected cost of the defender as a function of $|\ell_\A - \overline{\ell}_{\A,t}|$, which quantifies the inaccuracy of the defender's conjecture $\overline{\ell}_{\A,t}$. We observe that the cost of the defender is increasing with the inaccuracy of its conjecture. Next, Fig. <ref>.e shows the evolution of the discrepancy (<ref>) of different conjectures. We observe that the discrepancies of the incorrect conjectures increase over time and that the discrepancy of the correct conjecture is $0$ (by definition).

Evaluation results; a)–f) relate to Scenario <ref>; g)–l) relate to Scenario <ref>; m)–n) relate to Scenario <ref>; and o) relate to Scenario <ref>; values indicate the mean; the shaded areas and the error bars indicate the 95% confidence interval based on $20$ random seeds; hyperparameters are listed in Appendix <ref>.

Evolution of $\rho_t^{(\D)}$ (<ref>) when $\Theta_{\D} = \{0.0, 0.05,\hdots,0.8\}$ and $\bm{\theta}_t=1$ for all $t$ (Scenario <ref>); hyperparameters are listed in Appendix <ref>.

Lastly, Fig. <ref>.f shows the expected cost of Alg. <ref> and the expected cost of best response reinforcement learning with <cit.> (i.e., best response dynamics <cit.>). We note that the expected cost of reinforcement learning oscillates. Similar behavior of reinforcement learning has been observed in related work <cit.>. By contrast, the expected cost of Alg. <ref> is significantly more stable and its behavior is consistent with convergence to a  Berk-Nash equilibrium (Def. <ref>).

Scenario <ref>. Figures <ref>.g–h show the evolution of the defender's conjecture distribution $\rho^{(\D)}_t$ (<ref>) and the discrepancy (<ref>) of the conjecture $\overline{\bm{\theta}}^{(\D)}_{t}$ when $\Theta_{\mathrm{D}}=\{12,9\}$ and $\bm{\theta}_t=12$ for all $t$. We observe that $\rho^{(\D)}_t$ converges and concentrates on the consistent conjecture (<ref>) after $18$ time steps, as predicted by Thm. <ref>.B. Figure <ref>.j shows the rate of convergence for varying $|\Theta_{\D}|$. As expected, when the defender's uncertainty about $\bm{\theta}_t$ increases (i.e., when $|\Theta_{\D}|$ increases), the time it takes for the sequence of conjectures to converge increases.

Figure <ref>.i shows the expected cost of the defender as a function of $|\bm{\theta}_t-\overline{\bm{\theta}}^{(\mathrm{D})}_{t}|$, which quantifies the inaccuracy of the defender's conjecture $\overline{\bm{\theta}}^{(\D)}_{t}$. We observe that the cost of the defender is increasing with the inaccuracy of its conjecture. Lastly, Figs. <ref>.k–l show the expected discrepancy (<ref>) of the posterior (<ref>) when $\bm{\theta}_t$ is changing at every time step, whereby $\rho^{(\D)}_t$ does not converge. (Note that Thm. <ref> only applies when $\bm{\theta}_t$ remains fixed.)

Scenario <ref>. Figures <ref>.m–n show the time for the defender's conjecture $\overline{\bm{\theta}}_t^{(\D)}$ to converge for different sizes of $\Theta_{\D}$ when $\bm{\theta}_t$ is fixed. We observe that the time to converge increases with the size of $\Theta_{\D}$, which is expected since the size of $\Theta_{\D}$ represents the defender's degree of uncertainty about $\bm{\theta}_t$. Figure <ref> shows the evolution of $\rho_t^{(\D)}$. We observe that $\rho_t^{(\D)}$ starts from a uniform distribution over $\Theta_{\D}$ and as $t\rightarrow \infty$, it concentrates on the set of consistent conjectures $\Theta_{\D}^{\star}$ (<ref>).

Scenario <ref>. Figure <ref>.o shows the evolution of the defender's conjecture distributions  $\mu_t$ and $\rho^{(\mathrm{D})}_t$ (<ref>). We see in the figure that both distributions converge, which is consistent with Thm. <ref>. The convergence of $\mu_t$ is significantly faster than that of $\rho^{(\mathrm{D})}_t$. We believe this difference is because $|\mathcal{L}| < |\Theta_{\D}|$, which means that the defender is more uncertain about $\ell_{\A}$ than about $\bm{\theta}_t$.

Comparison with baselines. The convergence times of our method (Alg. <ref>) and those used in prior work are listed in Table <ref>. While we observe that our method converges faster than the baselines, a direct comparison is not feasible for two reasons. First, the baselines do not consider the same solution concept as us, i.e., the Berk-Nash equilibrium (Def. <ref>). Second, the baselines make different assumptions about the computational capacity and information available to the players. For example, fictitious play <cit.>, which is a popular method among prior work, assumes that players a) have correctly specified models and b) have unlimited computational capacity. Similarly, popular reinforcement learning methods, such as <cit.> and <cit.>, are designed for offline rather than online learning.

Method     Fixed point     Time (min)
Alg. <ref>, $|\mathcal{L}|=2,|\Theta_{\mathrm{k}}|=1$     Berk-Nash equilibrium (Def. <ref>)     $6.7 \pm 0.7$

Alg. <ref>, $|\mathcal{L}|=3,|\Theta_{\mathrm{k}}|=1$     Berk-Nash equilibrium (Def. <ref>)     $11.4 \pm 0.9$

Alg. <ref>, $|\mathcal{L}|=4,|\Theta_{\mathrm{k}}|=1$     Berk-Nash equilibrium (Def. <ref>)     $39.1 \pm 1.3$

Alg. <ref>, $|\mathcal{L}|=4,|\Theta_{\mathrm{k}}|=1$     Berk-Nash equilibrium (Def. <ref>)     $137.3 \pm 2.8$

Alg. <ref>, $|\mathcal{L}|=1,|\Theta_{\mathrm{k}}|=2$     Berk-Nash equilibrium (Def. <ref>)     $12.9 \pm 0.9$

Alg. <ref>, $|\mathcal{L}|=1,|\Theta_{\mathrm{k}}|=32$     Berk-Nash equilibrium (Def. <ref>)     $17.9 \pm 1.0$

Alg. <ref>, $|\mathcal{L}|=1,|\Theta_{\mathrm{k}}|=192$     Berk-Nash equilibrium (Def. <ref>)     $29.9 \pm 1.2$

Alg. <ref>, $|\mathcal{L}|=4,|\Theta_{\mathrm{k}}|=192$     Berk-Nash equilibrium (Def. <ref>)     $194.6 \pm 3.7$

Best-response dynamics (Fig. <ref>.f)      $\epsilon$-Nash equilibrium <cit.>     dnc

<cit.> (Fig. <ref>)      $\epsilon$-Nash equilibrium <cit.>     dnc

<cit.>      $\epsilon$-Nash equilibrium <cit.>     $\approx 919$ min

Fictitious play <cit.>     $\epsilon$-Nash equilibrium <cit.>     $\approx 4800$ min

<cit.>, static $\pi_{\A}$      Best response (<ref>)     $9.2 \pm 0.4$ min

Comparison with baseline methods in terms of speed of convergence; dnc is short for “does not converge”; “$\approx$” means that the algorithm nearly converges; numbers indicate the mean and the standard deviation from evaluations with $3$ random seeds; hyperparameters are listed in Appendix <ref>.

§.§ Discussion of the Evaluation Results

The key findings from the evaluation can be summarized as follows.

* The conjectures produced by our method converges to consistent conjectures once the model parameters $\bm{\theta}_t$ remain fixed (<ref>) (Figs. <ref>.a,g,m,o, Thm. <ref>). The rate of convergence decreases as $|\mathcal{L}|$ and $|\Theta_{\mathrm{k}}|$ increase (Figs. <ref>.d,j,n).

* The cost of the defender increases as the distance between its conjecture and the true model increases (Figs. <ref>.c,i).

* Algorithm <ref> allows to configure the computational capacity and the uncertainty of each player $\mathrm{k}$ by tuning $\ell_{\mathrm{k}}$ (Fig. <ref>) and $(\mathcal{L},\Theta_{\mathrm{k}})$, respectively (Fig. <ref>).

* Algorithm <ref> leads to effective strategies (Thm. <ref>) that are more stable than those obtained through reinforcement learning (Fig. <ref>.f, Table <ref>).

* Computation of perfect Bayesian equilibria (Def. <ref>) and computation of exact rollout strategies is intractable for any non-trivial instantiation of $\Gamma$ (Fig. <ref>, Fig. <ref>).

* Approximate best response and rollout strategies of $\Gamma$ can be efficiently computed using stochastic approximation (Fig. <ref>, Fig. <ref>, Thm. <ref>).

The above findings suggest that our method can produce effective security strategies without relying on a correctly specified model of the environment. The practical implication of this result is that our method is suitable for dynamic IT infrastructures with short update cycles, which aligns with current trends of virtualization and zero-touch management.

§ RELATED WORK

Since the early 2000s, researchers have studied automated security through modeling attacks and response actions on an IT infrastructure as a game between an attacker and a defender (see textbooks <cit.>). The game is modeled in different ways depending on the use case. Examples include: apt games <cit.>, honeypot placement games <cit.>, resource allocation games <cit.>, distributed denial-of-service games <cit.>, jamming games <cit.>, and intrusion response games <cit.>. These games are formulated using various models from the game-theoretic literature. For example: stochastic games (see e.g., <cit.>), extensive-form games (see e.g., <cit.>), Blotto games (see e.g., <cit.>), hypergames (see e.g., <cit.>), (see e.g., <cit.>), Stackelberg games (see e.g., <cit.>), and evolutionary games (see e.g., <cit.>).

The main difference between this paper and the works referenced above is that we propose a method that allows to model non-stationary security games where players have probabilistic conjectures about the game model, which may be misspecified. By contrast, most of the referenced works assume that players have correctly specified models.

While the study of learning with misspecified models has attracted long-standing interest in economics <cit.>, engineering <cit.>, and psychology <cit.>, it remains unexplored in the security context. Related research in the security literature include a) game-theoretic approaches based on bounded rationality; and b) model-free learning approaches. In the following subsections, we describe how these two approaches relate to this paper, where the main differences are listed in Table <ref>.

Paper     Use case     Method     Equilibrium     Evaluation     Game type
<cit.> Zonouz, 2009     Intrusion response      Dynamic programming     -     Testbed     Stationary

<cit.> Zhu, 2009     Intrusion detection      Q-learning     Nash     Simulation     Stationary stochastic dynamic game

<cit.> Balcan, 2015     Resource allocation      No-regret learning     -     Analytical     Stationary repeated Stackelberg game

<cit.> Lisý, 2016     Resource allocation      No-regret learning     Nash     Analytical     Stationary nfgss

<cit.> Chen, 2019     Risk management     Proximal optimization     Gestalt Nash     Simulation     Stationary one-stage game

<cit.> Sanjab, 2020     Drone operation     Prospect theory     Stackelberg     Simulation     Stationary network interdiction game

<cit.> Bakker, 2020     Intrusion response     Analytical     Hyper Nash     Simulation     Stationary repeated hypergame

<cit.> Abdallah, 2020     Power grid     Analytical     Nash     Simulation     Stationary behavioral game

<cit.> Huang, 2020         Optimization     Perfect Bayes Nash     Simulation     Stationary

<cit.> Zhao, 2020     Intrusion response     Analytical     Nash     Simulation     Non-stationary Markov game

<cit.> Aydeger, 2021     ddos     Optimization     Perfect Bayes Nash     Testbed     Stationary signaling game

<cit.> Wan, 2022         Analytical     Hyper Nash     Simulation     Stationary hypergame

<cit.> Gabrys, 2023     Cyber deception     Analytical     Stackelberg     Simulation     Stationary Stackelberg game

<cit.> Hammar, 2023     Intrusion response     Fictitious play     Nash     Testbed     Stationary

<cit.> Mavridis, 2023     Cyber-physical security     Stochastic approximation     Nash     Simulation     Stationary differential game

<cit.> Ge, 2023     Zero-trust     Meta-learning     -     Simulation     Stationary

This paper, 2024         Bayesian learning & rollout     Berk-Nash     Testbed & simulation     Non-stationary and misspecified

Comparison between this paper and related work.

§.§ Security Games with Bounded Rationality

Research on security games with bounded rationality includes <cit.>. These works differ from this paper in three main ways. First, they do not consider model misspecification as we do in this paper. Second, they study different types of games, i.e., one-stage games <cit.>; network interdiction games <cit.>; differential games <cit.>; Stackelberg games <cit.>; behavioral games <cit.>; and hypergames <cit.>. Third, they study different types of equilibria, i.e., Nash equilibria <cit.>; Gestalt Nash equilibria <cit.>; Stackelberg equilibria <cit.>; and Hyper Nash equilibria <cit.>. By contrast, we study Berk-Nash equilibria <cit.> and a where players have misspecified models. The benefit of our game model and equilibrium concept is that they better capture the use case (<ref>).

§.§ Learning in Security Games

Prior work that study learning in security games includes <cit.>. This paper differs from these works in two main ways. First, we design a novel way to update strategies using rollout with a conjectured model. This contrasts with all of the referenced works which consider other types of strategy updates, e.g., offline learning <cit.>, meta-learning <cit.>, model-free learning <cit.>, and learning with perfect rationality <cit.>. The advantage of our approach is that it allows to model players with limited computational capacity and varying degrees of misspecification. Second, we design a convergent Bayesian mechanism for online learning. In comparison, most of the prior work considers other types of learning mechanisms, e.g., fictitious play <cit.>, reinforcement learning <cit.>, and no-regret learning <cit.>.

§ CONCLUSION AND FUTURE WORK

This paper presents a new game-theoretic method for online learning of security strategies that is applicable to dynamic IT environments where attacker and defender are uncertain about the environment and the opponent's strategy. We formulate the interaction between an attacker and a defender as a non-stationary game where each player has a probabilistic conjecture about the game model, which may be misspecified in the sense that the true model has probability $0$. Both players iteratively adapt their conjecture using Bayesian learning and update their strategy using rollout. We prove that the conjectures converge to best fits (Thm. <ref>), and we provide a bound on the performance improvement that rollout enables with a conjectured model (Thm. <ref>). To characterize the steady state of the game, we propose a novel equilibrium concept based on the Berk-Nash equilibrium, which represents a stable point where each player acts optimally given its conjecture (Def. <ref>). We present our method through an use case (<ref>). Simulation studies based on testbed measurements show that our method produces effective security strategies that adapt to a changing environment (Fig. <ref>). We also find that it leads to faster convergence than current reinforcement learning techniques (Table <ref>).

This paper opens up for several directions of future work. One direction is to extend our method and make it applicable to additional use cases. In particular, this paper considers an attacker with inside information – in future work we plan to investigate use cases with less capable attackers. Another direction of future work is to complement our asymptotic results (Thm. <ref>) with finite sample bounds, and to relate our definition of the Berk-Nash equilibrium (Def. <ref>) with other equilibrium concepts.

§ ACKNOWLEDGMENTS

The authors would like to thank Forough Shahab Samani and Xiaoxuan Wang for their constructive comments on a draft of this paper. The authors are also grateful to Branislav Bosanský for sharing the code of the algorithm.

§ PROOF OF THEOREM <REF>

Given $(\pi_{\mathrm{A}},\pi_{\mathrm{D}})$, the best response strategies $(\tilde{\pi}_{\mathrm{D}},\tilde{\pi}_{\mathrm{A}})$ are optimal strategies in two s $\mathcal{M}_{\D}^{P}$ and $\mathcal{M}_{\A}^{P}$. Hence, it suffices to show that there exists optimal strategies $(\pi_{\mathrm{D}}^{\star}, \pi_{\mathrm{A}}^{\star})$ in $\mathcal{M}_\D^{P}$ and $\mathcal{M}_{\A}^{P}$ that satisfy (<ref>) and (<ref>). Towards this proof, we state the following five lemmas.

$\mathcal{M}_\D^{\mathrm{P}}$ can be formulated as a repeated optimal stopping problem.

By definition, any optimal strategy $\pi_{\mathrm{D}}^{\star}$ in $\mathcal{M}_\D^{P}$ satisfies

\begin{align*}
&\pi_{\mathrm{D}}^{\star} \in \argmin_{\pi_{\mathrm{D}} \in \Pi_{\mathrm{D}}} \mathbb{E}_{(\pi_{\mathrm{D}},\pi_{\mathrm{A}})}\left[\sum_{t=1}^{\infty}\gamma^{t-1}c(S_t, A_t^{(\mathrm{D})}) \mid S_1 = 0 \right]\\
&\numeq{a} \argmin_{\pi_{\mathrm{D}} \in \Pi_{\mathrm{D}}} \Biggl[\mathbb{E}_{(\pi_{\mathrm{D}},\pi_{\mathrm{A}})}\left[\sum_{t=1}^{\tau_1}\gamma^{t-1}c(S_t, A_t^{(\mathrm{D})}) \mid S_1=0 \right] + \\
&\quad\quad\mathbb{E}_{(\pi_{\mathrm{D}},\pi_{\mathrm{A}})}\left[\sum_{t=\tau_1+1}^{\tau_2}\gamma^{t-1}c(S_t, A_t^{(\mathrm{D})}) \mid S_{\tau_1} = 0 \right] + \hdots \Biggr]\\
&\numeq{b} \argmin_{\pi_{\mathrm{D}} \in \Pi_{\mathrm{D}}} \Biggl[\mathbb{E}_{(\pi_{\mathrm{D}},\pi_{\mathrm{A}})}\left[\sum_{t=1}^{\tau_1}\gamma^{t-1}c(S_t, A_t^{(\mathrm{D})}) \mid S_1=0 \right],
\end{align*}

where $\tau_1, \tau_2, \hdots$ are the stopping times; (a) follows by linearity of expectation; and (b) follows because all elements inside the infinite sum are equivalent up to a constant factor.

The optimal cost-to-go function $J_{\mathrm{D}}^{\star}(\mathbf{b})$ in $\mathcal{M}_\D^{\mathrm{P}}$ is piecewise linear and concave with respect to $\mathbf{b} \in \mathcal{B}$.

This property was originally proven by E.J. Sondik <cit.>. A more accessible version of the proof can be found in <cit.>. For brevity we omit it here.

Let $\mathscr{S} \subseteq \mathcal{B}$ denote the subset of the belief space in $\mathcal{M}_\D^{\mathrm{P}}$ where it is optimal to stop, i.e., $\mathbf{b} \in \mathscr{S} \iff \pi_{\D}^{\star}(\mathbf{b}) = \mathsf{S}$. If $N=1$, then $\mathscr{S}$ is a convex set.

As $N=1$, we have that $\mathcal{B}=[0,1]$ and $b_t = \mathbb{P}[S_t=1 \mid \mathbf{h}^{(\mathrm{D})}_t]$. To show that $\mathscr{S}$ is convex, we need to show that $b_1,b_2\in \mathscr{S} \implies \lambda b_1 + (1-\lambda)b_2 \in \mathscr{S}$ for any $\lambda \in [0,1]$. Since $J_\D^{\star}(b)$ is concave (Lemma <ref>), we have

\begin{align*}
J_{\mathrm{D}}^{\star}(\lambda b_1 + (1-\lambda)b_2) &\geq \lambda J_{\mathrm{D}}^{\star}(b_1) + (1-\lambda)J_{\mathrm{D}}^{\star}(b_2).
\end{align*}

As $b_1,b_2 \in \mathscr{S}$ by assumption, the optimal action given $b_1$ or $b_2$ is $\mathsf{S}$. Thus $J_{\mathrm{D}}^{\star}(b_1)=Q_{\D}^{\star}(b_1,\mathsf{S})$ and $J_{\mathrm{D}}^{\star}(b_2)=Q^{\star}(b_2,\mathsf{S})$, where $Q_{\D}^{\star}$ is the optimal Q-function in $\mathcal{M}_\D^{\mathrm{P}}$. Since $Q_{\D}^{\star}(b_t,\mathsf{S})=\mathbb{E}_{S_t}[c(S_t, \mathsf{S}) \mid b_t] = bc(1,\mathsf{S}) + (1-b)c(0,\mathsf{S})$, we obtain

\begin{align*}
&J_{\mathrm{D}}^{\star}(\lambda b_1 + (1-\lambda)b_2) \geq \lambda J_{\mathrm{D}}^{\star}(b_1) + (1-\lambda)J_{\mathrm{D}}^{\star}(b_2)\\
&\geq \lambda Q_{\D}^{\star}(b_1, \mathsf{S}) + (1-\lambda)Q_{\D}^{\star}(b_2, \mathsf{S})\\
&\geq \lambda\big(b_1c(1,\mathsf{S}) + (1-b_1)c(0,\mathsf{S})\big) + \\
&\quad\quad(1-\lambda)\big(b_1c(1,\mathsf{S}) + (1-b_1)c(0,\mathsf{S})\big)\\
&\geq (\lambda b_1 + (1-\lambda)b_2)c(1,\mathsf{S}) + (1-(\lambda b_1+ (1-\lambda)b_2))c(0,\mathsf{S})\\
&\geq Q_{\D}^{\star}\big(\lambda b_1 + (1-\lambda)b_2, \mathsf{S}\big)\\
&\numgeq{a} J_{\mathrm{D}}^{\star}\big(\lambda b_1 + (1-\lambda)b_2\big),
\end{align*}

where (a) follows because $J_{\mathrm{D}}^{\star}$ is optimal. This shows that if $b_1,b_2 \in \mathscr{S}$ then $Q_{\D}^{\star}(\lambda b_1 + (1-\lambda)b_2, \mathsf{S}) = J_{\mathrm{D}}^{\star}(\lambda b_1 + (1-\lambda)b_2)$, which means that $\lambda b_1 + (1-\lambda)b_2 \in \mathscr{S}$ for any $\lambda \in [0,1]$. Hence, $\mathscr{S}$ is convex <cit.>.

If $s_t=N$, then $a^{(\mathrm{A})}_t=\mathsf{C}$ is a best response for any $\mathbf{b}_t \in \mathcal{B}$ and $\pi_{\D} \in \Pi_{\D}$.

Assume by contradiction that $a^{(\mathrm{A})}_t=\mathsf{C}$ is not a best response. Then the expected cost of $a^{(\mathrm{A})}_t=\mathsf{S}$ must be lower than that of $a^{(\mathrm{A})}_t=\mathsf{C}$, i.e.,

\begin{align*}
&Q_{\A}^{\star}((\mathbf{b}_t,N),\mathsf{S}) < Q_{\A}^{\star}((\mathbf{b}_t,N),\mathsf{C}) \numimp{a} -c(s_t, a^{(\D)}_t) + \\
&\gamma^{t-1}\mathbb{E}_{A_t^{(\mathrm{D})},O_t}[J^{\star}_\A(\mathbf{B}_{t+1}) \mid s_t=N,a_t^{(\A)}=\mathsf{S}] < -c(s_t, a^{(\D)}_t) + \\
&\gamma^{t-1}\mathbb{E}_{A_t^{(\mathrm{D})},O_t}[J^{\star}_\A(\mathbf{B}_{t+1}) \mid s_t=N,a_t^{(\A)}=\mathsf{C}]\numimp{b} \\
&\mathbb{E}_{A_t^{(\mathrm{D})}}\left[\sum_{o \in \mathcal{O}}z(o \mid \mathbf{b}_t, A^{(\mathrm{D})})J^{\star}_\A(\mathds{B}(\mathbf{b}_{t}, a^{(\mathrm{D})}_{t}, o_t, \pi_{\mathrm{A}}))\mid s_t=N\right]\\
&<\mathbb{E}_{A_t^{(\mathrm{D})}}\left[\sum_{o \in \mathcal{O}}z(o| \mathbf{b}_t, A^{(\mathrm{D})})J^{\star}_\A(\mathds{B}(\mathbf{b}_{t}, a^{(\mathrm{D})}_{t}, o_t, \pi_{\mathrm{A}}))| s_t=N\right]\\
&\numimp{c} 0 < 0 \quad\quad \text{(contradiction)},
\end{align*}

where $Q_{\A}^{\star}((\mathbf{b}_t,N),\mathsf{S})$ is the optimal Q-function in $\mathcal{M}_\A^{P}$, $\pi_\A$ is the attacker strategy assumed by $\pi_\D$, and $\mathds{B}$ is defined in (<ref>). Step (a) follows from Bellman's optimality equation <cit.>; (b) follows because $c$ (<ref>) is independent of $a^{(\A)}_t$; and (c) follows because both $a^{(\mathrm{A})}_t=\mathsf{C}$ and $a^{(\mathrm{A})}_t=\mathsf{S}$ lead to the same state when $s_t=N$ (<ref>).

If $\pi_\D(\mathsf{S}\mid \mathbf{b}_t)=1$ for some $\mathbf{b}_t \in \mathcal{B}$, then $a^{(\mathrm{A})}_t=\mathsf{C}$ is a best response.

Assume by contradiction that $a^{(\mathrm{A})}_t=\mathsf{C}$ is not a best response. Then the expected cost of $a^{(\mathrm{A})}_t=\mathsf{S}$ must be lower than that of $a^{(\mathrm{A})}_t=\mathsf{C}$, i.e.,

\begin{align*}
Q_{\A}^{\star}((\mathbf{b}_t,s_t),\mathsf{S}) &< Q_{\A}^{\star}((\mathbf{b}_t,s_t),\mathsf{C})\\
\numimp{a} \gamma^{t-1} J^{\star}_\A(\mathbf{e}_1) &< \gamma^{t-1} J^{\star}_\A(\mathbf{e}_1)\\
\numimp{b} 0 &< 0 \quad\quad \text{(contradiction)},
\end{align*}

where (a) follows because $c$ (<ref>) is independent of $a^{(\mathrm{A})}_t$ and because $\pi_\D(\mathsf{S}| \mathbf{b}_t)=1 \implies \mathbf{b}_{t+1}=\mathbf{e}_1$ (<ref>).

§.§ Proof of Theorem <ref>.A

Lemma <ref> and the assumption that $N=1$ means that $\mathscr{S}=[\alpha^{\star}, \kappa]$, where $0 \leq \alpha^{\star} \leq \kappa \leq 1$. Thus it suffices to show that $\kappa=1$. Bellman's optimality equation <cit.> implies that

\begin{align*}
\pi^{\star}_{\mathrm{D}}(1) &\in \argmin_{a \in \{\mathsf{S}, \mathsf{C}\}}\left[\overbrace{c(1, \mathsf{S})}^{\mathsf{S}}, \overbrace{c(1, \mathsf{C}) + \gamma J_{\mathrm{D}}^{\star}(1)}^{\mathsf{C}}\right]\\
&\numeq{a}\argmin_{a \in \{\mathsf{S}, \mathsf{C}\}}\left[c(1, \mathsf{S}), c(1, \mathsf{S}) + \sum_{t=1}^{\tau}\gamma^{t}c(1, \mathsf{C})\right]\\
&\numeq{b}\argmin_{a \in \{\mathsf{S}, \mathsf{C}\}}\left[c(1, \mathsf{S}), c(1, \mathsf{S}) + \frac{1-\gamma^{\tau-1}}{1-\gamma}\right] = \mathsf{S},
\end{align*}

where $\tau \geq 1$ denotes the stopping time. Step (a) follows because $s=1$ is an absorbing state and (b) follows from (<ref>). As a consequence, $\pi^{\star}_{\mathrm{D}}(1) = \mathsf{S} \implies \mathscr{S}=[\alpha^{\star},1]$.

§.§ Proof of Theorem <ref>.B

Since $N=1$, we have that $\mathcal{B}=[0,1]$ and $b_t = \mathbb{P}[S_t=1 \mid \mathbf{h}^{(\mathrm{D})}_t]$. Given Lemma <ref>, it suffices to consider the case when $s_t=0$. From Lemma <ref> and the assumption that $\pi_\D$ satisfies (<ref>), we know that $a_t^{(\A)}=\mathsf{S}$ is a best response iff $b_t \in [0,\alpha^{\star})$, where $\alpha^{\star} \leq 1$. It further follows from Lemma <ref> that $\alpha^{\star}=0 \implies \beta^{\star}=0$. Thus Thm. <ref>.B holds when $\alpha^{\star}=0$. Now consider the case when $\alpha^{\star}>0$. We know from Lemma <ref> and (<ref>) that the difference in expected cost for the attacker when $a_t^{(\A)}=\mathsf{S}$ and when $a_t^{(\A)}=\mathsf{C}$ is negatively proportional to the next stopping time of the defender $T^{(\D)}$. We will show that $\mathbb{E}[T^{(\D)}]$ is decreasing in $\mathbf{b}_t$.

The transition matrices of $\mathcal{M}_\A^{P}$ are

\begin{align}
\kbordermatrix{
& 0 & 1  \\
0 & 1 & 0\\
1 & q & 1-q \\
\kbordermatrix{
& 0 & 1 \\
0 & q & 1-q \\
1 & q & 1-q \\
\end{align}

where $q\triangleq \pi_\D(\mathsf{S}| b_t)$. The left matrix in (<ref>) relates to $a_t^{(\A)}=\mathsf{C}$ and the right matrix relates to $a_t^{(\A)}=\mathsf{S}$. The determinants of these matrices are $(1-q)$ and $0$, which means that they are tp-2 <cit.>. By assumption, $z(o_t | s_t)$ (<ref>) is also tp-2. This means that $\mathds{B}$ (<ref>) is non-decreasing in $b_t$ <cit.>. Consequently, $\mathbb{E}[T^{(\D)}]$ is decreasing in $b_t$. Hence, if there is some $b_t$ where $a_t^{(\A)}=\mathsf{S}$ is a best response, then for any $b^{\prime}_t < b_t$, $a_t^{(\A)}=\mathsf{S}$ must also be a best response. We know from Lemma <ref> and Lemma <ref> that the stopping set for the attacker is a convex subset $[0, \beta^{\star}) \subset [0,\alpha^{\star})$. Thus there exists a threshold $\beta^{\star} \in [0,\alpha^{\star})$ such that $a_t^{(\A)}=\mathsf{S}$ is a best response iff $b_t > \beta^{\star}$.

§ PROOF OF THEOREM <REF>

As (<ref>) implements one step of the policy iteration algorithm <cit.>, (<ref>) follows from standard results in dynamic programming theory, see e.g., <cit.>.

To prove (<ref>) we adapt the proof in <cit.>. Let $\tilde{\bm{\pi}}\triangleq (\pi_{\mathrm{k}, t}, \overline{\pi}_{\mathrm{-k},t})$ and let $\bm{\pi}\triangleq (\pi_{\mathrm{k}, 1}, \overline{\pi}_{\mathrm{-k},t})$. Then define

\begin{align*}
(T_{\mathrm{k},\bm{\pi}}J_{\mathrm{k}})(\mathbf{b}_t) &\triangleq \mathbb{E}_{\bm{\pi}}[c(S_t, A^{(\mathrm{D})}_t) + \gamma J_{\mathrm{k}}(\mathbf{B}_{t+1}) \mid \bm{\pi}] && \forall \mathbf{b} \in \mathcal{B}.
\end{align*}

Since $J_{\mathrm{k}}^{(\bm{\pi})}$ is a fixed point of $T_{\mathrm{k},\bm{\pi}}$, i.e., $T_{\mathrm{k},\bm{\pi}}J_{\mathrm{k}}^{(\bm{\pi})}=J_{\mathrm{k}}^{(\bm{\pi})}$, and since $T^k_{\mathrm{k},\bm{\pi}}$ is a contraction mapping <cit.>, we have that $\lim_{j\rightarrow \infty}T^j_{\mathrm{k},\bm{\pi}}J=J_{\mathrm{k}}^{(\bm{\pi})}$ for any $J$ <cit.>. As a consequence

\begin{align}
\norm{\overline{J}_{\mathrm{k}}^{(\tilde{\bm{\pi}})}-J_{\mathrm{k}}^{\star}} &= \lim_{j \rightarrow \infty}\norm{T^j_{\mathrm{k},\tilde{\bm{\pi}}}J_{\mathrm{k}}^{\star}-J_{\mathrm{k}}^{\star}}.\label{eq:cost_bound_1}
\end{align}

By repeated application of the triangle inequality:

\begin{align*}
\norm{T^j_{\mathrm{k},\tilde{\bm{\pi}}}J_{\mathrm{k}}^{\star}-J_{\mathrm{k}}^{\star}} &\leq \norm{T^{j}_{\mathrm{k},\tilde{\bm{\pi}}}J_{\mathrm{k}}^{\star}-T^{j-1}_{\mathrm{k},\tilde{\bm{\pi}}}J_{\mathrm{k}}^{\star}} + \norm{T^{j-1}_{\mathrm{k},\tilde{\bm{\pi}}}J_{\mathrm{k}}^{\star}-J_{\mathrm{k}}^{\star}}\\
&\leq \hdots \leq \sum_{m=1}^{j}\norm{T^{m}_{\mathrm{k},\tilde{\bm{\pi}}}J_{\mathrm{k}}^{\star}-T^{m-1}_{\mathrm{k},\tilde{\bm{\pi}}}J_{\mathrm{k}}^{\star}}.
\end{align*}

Since $T_{\mathrm{k},\tilde{\bm{\pi}}}$ is a contraction mapping with modulus $\gamma < 1$,

\begin{align*}
\norm{T_{\mathrm{k},\tilde{\bm{\pi}}}(T_{\mathrm{k},\tilde{\bm{\pi}}}J_{\mathrm{k}}^{\star})-T_{\mathrm{k},\tilde{\bm{\pi}}}J_{\mathrm{k}}^{\star}} &\leq \gamma\norm{T_{\mathrm{k},\tilde{\bm{\pi}}}J_{\mathrm{k}}^{\star}-J_{\mathrm{k}}^{\star}}\\
\implies \norm{T^j_{\mathrm{k},\tilde{\bm{\pi}}}J_{\mathrm{k}}^{\star}-T^{j-1}_{\mathrm{k},\tilde{\bm{\pi}}}J_{\mathrm{k}}^{\star}} &\leq \gamma^{j-1}\norm{T_{\mathrm{k},\tilde{\bm{\pi}}}J_{\mathrm{k}}^{\star}-J_{\mathrm{k}}^{\star}}.
\end{align*}

The above inequality means that

\begin{align*}
\sum_{m=1}^{j}\norm{T^{m}_{\mathrm{k},\tilde{\bm{\pi}}}J_{\mathrm{k}}^{\star}-T^{m-1}_{\mathrm{k},\tilde{\bm{\pi}}}J_{\mathrm{k}}^{\star}} &\leq \sum_{m=1}^{j}\gamma^{m-1}\norm{T_{\mathrm{k},\tilde{\bm{\pi}}}J_{\mathrm{k}}^{\star}-J_{\mathrm{k}}^{\star}}.
\end{align*}

Since non-strict inequalities are preserved by limits,

\begin{align}
\lim_{j \rightarrow \infty}\norm{T^j_{\mathrm{k},\tilde{\bm{\pi}}}J_{\mathrm{k}}^{\star}-J_{\mathrm{k}}^{\star}} &\leq \lim_{j \rightarrow \infty}\sum_{m=1}^{j}\gamma^{m-1}\norm{T_{\mathrm{k},\tilde{\bm{\pi}}}J_{\mathrm{k}}^{\star}-J_{\mathrm{k}}^{\star}}\nonumber\\
&= \frac{\norm{T_{\mathrm{k},\tilde{\bm{\pi}}}J_{\mathrm{k}}^{\star}-J_{\mathrm{k}}^{\star}}}{1-\gamma}.\label{eq:cost_bound_2}
\end{align}

Now let $\widehat{J}^{(\tilde{\bm{\pi}})}_{\mathrm{k}} \triangleq T^{\overline{\pi}_{\mathrm{-k}, t}}_{\mathrm{k},\ell_{\mathrm{k}}}\overline{J}_{\mathrm{k}}^{(\tilde{\bm{\pi}})}$, where $T^{\overline{\pi}_{\mathrm{-k}, t}}_{\mathrm{k},\ell_{\mathrm{k}}}$ is defined in (<ref>). Note that $T_{\mathrm{k},\tilde{\bm{\pi}}}\widehat{J}^{(\tilde{\bm{\pi}})}_{\mathrm{k}}=T^{\overline{\pi}_{\mathrm{-k}, t}}_{\mathrm{k},1}\widehat{J}^{(\tilde{\bm{\pi}})}_{\mathrm{k}}$ and $T^{\overline{\pi}_{\mathrm{-k}, t}}_{\mathrm{k},1}J^{\star}_{\mathrm{k}}=J^{\star}_{\mathrm{k}}$ by definition <cit.>.

Applying the triangle inequality to the numerator in (<ref>),

\begin{align}
&\norm{T_{\mathrm{k},\tilde{\bm{\pi}}}J_{\mathrm{k}}^{\star}-J_{\mathrm{k}}^{\star}} \leq  \norm{T_{\mathrm{k},\tilde{\bm{\pi}}}J_{\mathrm{k}}^{\star}- T_{\mathrm{k},\tilde{\bm{\pi}}}\widehat{J}^{(\tilde{\bm{\pi}})}_{\mathrm{k}}}+ \nonumber\\
&\norm{T_{\mathrm{k},\tilde{\bm{\pi}}}\widehat{J}^{(\tilde{\bm{\pi}})}_{\mathrm{k}} - T^{\overline{\pi}_{\mathrm{-k}, t}}_{\mathrm{k},1}\widehat{J}^{(\tilde{\bm{\pi}})}_{\mathrm{k}}} + \norm{T^{\overline{\pi}_{\mathrm{-k}, t}}_{\mathrm{k},1}\widehat{J}^{(\tilde{\bm{\pi}})}_{\mathrm{k}} - J_{\mathrm{k}}^{\star}}\nonumber\\
&= \underbrace{\norm{T_{\mathrm{k},\tilde{\bm{\pi}}}J_{\mathrm{k}}^{\star}- T_{\mathrm{k},\tilde{\bm{\pi}}}\widehat{J}^{(\tilde{\bm{\pi}})}_{\mathrm{k}}}}_{\leq \gamma \norm{\widehat{J}^{(\tilde{\bm{\pi}})}_{\mathrm{k}}-J_{\mathrm{k}}^{\star}}} + \underbrace{\norm{T^{\overline{\pi}_{\mathrm{-k}, t}}_{\mathrm{k},1}\widehat{J}^{(\tilde{\bm{\pi}})}_{\mathrm{k}} - T^{\overline{\pi}_{\mathrm{-k}, t}}_{\mathrm{k},1}J_{\mathrm{k}}^{\star}}}_{\leq \gamma\norm{\widehat{J}^{(\tilde{\bm{\pi}})}_{\mathrm{k}}-J_{\mathrm{k}}^{\star}}}\nonumber\\
&\leq 2\gamma \norm{\widehat{J}^{(\tilde{\bm{\pi}})}_{\mathrm{k}}-J_{\mathrm{k}}^{\star}}=2\gamma \norm{T^{\overline{\pi}_{\mathrm{-k}, t}}_{\mathrm{k},\ell_{\mathrm{k}}}\overline{J}_{\mathrm{k}}^{(\tilde{\bm{\pi}})}- T^{\overline{\pi}_{\mathrm{-k}, t}}_{\mathrm{k},\ell_{\mathrm{k}}}J_{\mathrm{k}}^{\star}}\nonumber\\
&\leq 2\gamma^{\ell_{\mathrm{k}}}\norm{\overline{J}_{\mathrm{k}}^{(\bm{\pi})}-J_{\mathrm{k}}^{\star}}. \label{eq:cost_bound_3}
\end{align}

Combining (<ref>)–(<ref>) gives (<ref>).

§ PROOF OF THEOREM <REF>.A

The idea behind the proof of Thm. <ref>.A. is to express $\mu_t$ (<ref>) in terms of log-likelihood ratios, which can be shown to converge using the martingale convergence theorem <cit.>. Towards this proof, we state the following two lemmas.

Any sequence $(\bm{\pi}_{\mathbf{h}_t})_{t\geq 1}$ generated by Alg. <ref> induces a well-defined probability measure $\mathbb{P}^{\mathscr{R}}$ over the set of realizable histories $\mathbf{h} \in \mathcal{H}_\D \times \mathcal{H}_\A$.

Since the sample space of the random vectors $(\mathbf{I}_t^{(\D)}, \mathbf{I}_t^{(\A)})$ (<ref>) is finite (and measurable) for each $t$, the space of realizable histories $\mathbf{h} \in \mathcal{H}_{\D,t} \times \mathcal{H}_{\A,t}$ is countable. By the Ionescu-Tulcea extension theorem it thus follows that a measure $\mathbb{P}^{\mathscr{R}}$ over $\mathcal{H}_{\D,t}\times \mathcal{H}_{\A,t}$ exists for $t=1,2,\hdots$ <cit.>.

For any $\overline{\ell}_{\A}\in \mathcal{L}$ and any sequence $(\nu_t, \bm{\pi}_{\mathbf{h}_t})_{t \geq 1}$ generated by Alg. <ref>, the following holds a.s.-$\mathbb{P}^{\mathscr{R}}$ as $t \rightarrow \infty$

\begin{align*}
\bigg|\underbrace{t^{-1}\sum_{\tau=1}^t \ln \frac{\mathbb{P}[\mathbf{i}^{(\D)}_{\tau+1} \mid \ell_{\A}, \mathbf{b}_\tau]}{\mathbb{P}[\mathbf{i}^{(\D)}_{\tau+1} \mid \overline{\ell}_{\A}, \mathbf{b}_\tau]}}_{\triangleq Z_{t+1}(\overline{\ell}_{\A})}-K(\overline{\ell}_{\A}, \nu_{t})\bigg|=0.
\end{align*}

By definition of $Z_{t}$ and $\nu_t$,

\begin{align*}
&Z_{t+1}(\overline{\ell}_{\A}) = \sum_{\mathbf{b} \in \mathcal{B}}\sum_{\tau=1}^{t}t^{-1}\mathbbm{1}_{\{\mathbf{b}\}}(\mathbf{b}_{\tau})\ln \frac{\mathbb{P}[\mathbf{i}^{(\D)}_{\tau+1} \mid \ell_{\A}, \mathbf{b}_\tau]}{\mathbb{P}[\mathbf{i}^{(\D)}_{\tau+1} \mid \overline{\ell}_{\A}, \mathbf{b}_\tau]}\\
&=\mathbb{E}_{\mathbf{b}\sim \nu_t}\left[\sum_{\tau=1}^{t}\frac{\ln \mathbb{P}[\mathbf{i}^{(\D)}_{\tau+1} \mid \ell_{\A}, \mathbf{b}]}{t} - \sum_{\tau=1}^{t}\frac{\ln \mathbb{P}[\mathbf{i}^{(\D)}_{\tau+1} \mid \overline{\ell}_{\A}, \mathbf{b}]}{t}\right].
\end{align*}

This means that if the left sum above converges to $\mathbb{E}_{\mathbf{I}^{(\D)}}[\ln \mathbb{P}[\mathbf{I}^{(\D)} | \overline{\ell}_{\A}, \mathbf{b}]]$ and the right sum converges to $\mathbb{E}_{\mathbf{I}^{(\D)}}[\ln \mathbb{P}[\mathbf{I}^{(\D)} | \ell_{\A}, \mathbf{b}]]$, we obtain $Z_t \xrightarrow[t \to \infty]{} K(\overline{\ell}_{\A}, \nu_{t})$, which yields the desired result. As these two proofs are almost identical we only provide the first proof here.

Let $X_{\tau} \triangleq \ln\mathbb{P}[\mathbf{i}^{(\D)}_{\tau+1} | \ell_\A, \mathbf{b}_{\tau}] - \mathbb{E}_{\mathbf{I}^{(\D)}}\left[\ln\mathbb{P}[\mathbf{I}^{(\D)} | \ell_\A, \mathbf{b}_{\tau}]\right]$. We will show that $(X_{\tau})_{\tau \geq 1}$ is a martingale difference sequence (). To show this, we need to prove that (i) $\mathbb{E}[X_{\tau} | \mathbf{h}_{\tau-1}]=0$; and (ii) $\mathbb{E}[|X_{\tau}|] < \infty$. We start with (i),

\begin{align*}
&\mathbb{E}[X_{\tau} | \mathbf{h}_{\tau-1}]\\
&=\mathbb{E}_{\mathbf{I}^{(\D)}}\left[\ln\mathbb{P}[\mathbf{I}^{(\D)} |\ell_\A, \mathbf{b}_{\tau}] - \mathbb{E}_{\mathbf{I}^{(\D)}}\left[\ln\mathbb{P}[\mathbf{I}^{(\D)} | \ell_\A, \mathbf{b}_{\tau}]\right] | \mathbf{h}_{\tau-1}\right]\\
&\numeq{a}\mathbb{E}_{\mathbf{I}^{(\D)}}\left[\ln\mathbb{P}[\mathbf{I}^{(\D)} | \ell_\A, \mathbf{b}_{\tau}]\right] -\mathbb{E}_{\mathbf{I}^{(\D)}}\left[\ln\mathbb{P}[\mathbf{I}^{(\D)} | \ell_\A, \mathbf{b}_{\tau}]\right]=0,
\end{align*}

where (a) follows because $\mathbf{I}^{(\D)}$ is conditionally independent of $\mathbf{h}_{\tau-1}$ given $\mathbf{b}_{\tau}$ (<ref>).

To prove (ii) we will write $X_{\tau}$ as an expression of the form $(\ln \mathbb{P}[\varphi])^2\mathbb{P}[\varphi]$, which is bounded by $1$ [We use the standard convention that $(\ln 0)^20=0$.]. Towards this end, we start by applying Jensen's inequality to obtain

\begin{align}
\mathbb{E}[|X_{\tau}|]=(\mathbb{E}[|X_{\tau}|]^2)^{1/2}\leq (\mathbb{E}[X_{\tau}^2])^{1/2},\label{eq:jensen}
\end{align}

which means that it suffices to bound $\mathbb{E}[X_{\tau}^2]$.

Next, we write $\ln\mathbb{P}[\mathbf{i}^{(\D)}_{\tau+1} |\ell_\A, \mathbf{b}_{\tau}]$ as

\begin{align*}
&\sum_{\mathbf{I}^{(\D)}}\mathbbm{1}_{\{\mathbf{I}^{(\D)}\}}(\mathbf{i}^{(\D)}_{\tau+1})\frac{\mathbb{P}[\mathbf{I}^{(\D)} \mid \ell_\A, \mathbf{b}_{\tau}]}{\mathbb{P}[\mathbf{I}^{(\D)} \mid \ell_\A, \mathbf{b}_{\tau}]}\ln\mathbb{P}[\mathbf{I}^{(\D)} \mid \ell_\A, \mathbf{b}_{\tau}]\\
&=\frac{\mathbb{E}_{\mathbf{I}^{(\D)}}\left[\mathbbm{1}_{\{\mathbf{I}^{(\D)}\}}(\mathbf{i}^{(\D)}_{\tau+1})\ln\mathbb{P}[\mathbf{I}^{(\D)} \mid \ell_\A, \mathbf{b}_{\tau}]\right]}{\mathbb{P}[\mathbf{i}_{\tau+1}^{(\D)} \mid \ell_\A, \mathbf{b}_{\tau}]},
\end{align*}

which means that we can write $X_{\tau}$ as

\begin{align}
\frac{\mathbb{E}_{\mathbf{I}^{(\D)}}\left[\kappa \left(\mathbbm{1}_{\{\mathbf{I}^{(\D)}\}}(\mathbf{i}^{(\D)}_{\tau+1}) - \mathbb{P}[\mathbf{i}_{\tau+1}^{(\D)} | \ell_\A, \mathbf{b}_{\tau}]\right) \mid \ell_\A, \mathbf{b}_{\tau}\right]}{\mathbb{P}[\mathbf{i}_{\tau+1}^{(\D)} | \ell_\A, \mathbf{b}_{\tau}]},\label{eq:x_tau_1}
\end{align}

where $\kappa\triangleq \ln\mathbb{P}[\mathbf{I}^{(\D)} | \ell_\A, \mathbf{b}_{\tau}]$.

Since we focus on realizable histories, we have that $\mathbb{P}[\mathbf{i}_{\tau+1}^{(\D)} | \ell_\A, \mathbf{b}_{\tau}] \in (0,1]$, which means that it is safe to suppress the denominator in (<ref>). Consequently, the square of (<ref>) can be bounded by the Cauchy-Schwarz inequality as

\begin{align*}
\leq \mathbb{E}_{\mathbf{I}^{(\D)}}\Big[\kappa^2 \big(\underbrace{\mathbbm{1}_{\{\mathbf{I}^{(\D)}\}}(\mathbf{i}^{(\D)}_{\tau}+1) - \mathbb{P}[\mathbf{i}_{\tau+1}^{(\D)} | \ell_\A, \mathbf{b}_{\tau}]}_{\triangleq \chi}\big)^2 | \ell_\A, \mathbf{b}_{\tau}\Big].
\end{align*}

Next, since $\kappa \geq 0$ and $\chi \in [0,1]$, we obtain that

\begin{align*}
X^2_{\tau} \leq \mathbb{E}_{\mathbf{I}^{(\D)}}\left[\kappa^2 \chi^2 | \ell_\A, \mathbf{b}_{\tau}\right] \leq \mathbb{E}_{\mathbf{I}^{(\D)}}\left[\kappa^2 | \ell_\A, \mathbf{b}_{\tau}\right],
\end{align*}

which means that

\begin{align*}
\mathbb{E}[X_{\tau}^2] &\leq \mathbb{E}_{\mathbf{I}^{(\D)}}\left[\mathbb{P}[\mathbf{I}^{(\D)} | \ell_\A, \mathbf{b}_{\tau}]\ln^2\mathbb{P}[\mathbf{I}^{(\D)} | \ell_\A, \mathbf{b}_{\tau}] | \ell_\A, \mathbf{b}_{\tau}\right] \leq 1\\
&\numimp{a} \mathbb{E}[|X_{\tau}|] \leq 1,
\end{align*}

where (a) follows from (<ref>). Therefore, $(X_{\tau})_{\tau \geq 1}$ is an . Consequently, the sequence $Y_{t} \triangleq \sum_{\tau=1}^{t}\frac{X_{\tau}}{\tau}$ is a martingale. By the martingale convergence theorem, $(Y_{\tau})_{\tau \geq 1}$ converges to a finite and integrable random variable a.s.-$\mathbb{P}^{\mathscr{R}}$ <cit.>. This convergence means that we can invoke Kronecker's lemma, which states that $\lim_{t \rightarrow \infty}t^{-1}\sum_{\tau=1}^tX_{\tau}=0$ a.s.-$\mathbb{P}^{\mathscr{R}}$ <cit.>. As a consequence, the following holds a.s.-$\mathbb{P}^{\mathscr{R}}$ as $t \rightarrow \infty$

\begin{align*}
\mathbb{E}_{\mathbf{b} \sim \nu_t}\sum_{\tau=1}^t\frac{\ln\mathbb{P}[\mathbf{i}^{(\D)}_{\tau+1} | \ell_\A, \mathbf{b}]}{t} = \mathbb{E}_{\mathbf{b} \sim \nu_t}\mathbb{E}_{\mathbf{I}^{(\D)}}\left[\ln\mathbb{P}[\mathbf{I}^{(\D)} | \ell_\A, \mathbf{b}]\right].
\end{align*}

§.§ Proof of Theorem <ref>.A

To streamline analysis we treat $\mu_t$ as a probability measure over $\mathcal{L}$ and use integral language.
From Bayes rule and the Markov property of $\mathbb{P}[\mathbf{I}^{(\D)}\mid \overline{\ell}_{\A},\mathbf{b}_t]$, we have that

\begin{align}
\mu_{t+1}(\overline{\ell}_{\A}) &= \frac{\mathbb{P}[\overline{\ell}_{\A}]\mathbb{P}[\mathbf{i}^{(\D)}_2,\hdots,\mathbf{i}^{(\D)}_{t+1} \mid \overline{\ell}_{\A}, \mathbf{h}^{(\mathrm{D})}_t]}{\mathbb{P}[\mathbf{i}^{(\D)}_2,\hdots,\mathbf{i}^{(\D)}_{t+1} \mid \mathbf{h}^{(\mathrm{D})}_t]}\nonumber\\
&\numeq{a} \frac{\mu_1(\overline{\ell}_{\A})\prod_{\tau=1}^t\mathbb{P}[\mathbf{i}^{(\D)}_{\tau+1} \mid \overline{\ell}_{\A},\mathbf{b}_{\tau}]}{\int_{\mathcal{L}}\mu_1(\mathrm{d}\overline{\ell}_{\A})\prod_{\tau=1}^t\mathbb{P}[\mathbf{i}^{(\D)}_{\tau+1} \mid \overline{\ell}_{\A},\mathbf{b}_{\tau}]}\nonumber\\
&=\frac{\mu_1(\overline{\ell}_{\A})\exp\left(\ln\left(\prod_{\tau=1}^t\frac{\mathbb{P}[\mathbf{i}^{(\D)}_{\tau+1} \mid \overline{\ell}_{\A},\mathbf{b}_{\tau}]}{\mathbb{P}[\mathbf{i}^{(\D)}_{\tau+1} \mid \ell_{\A},\mathbf{b}_{\tau}]}\right)\right)}{\int_{\mathcal{L}}\mu_1(\mathrm{d}\overline{\ell}_{\A})\exp\left(\ln\left(\prod_{\tau=1}^t\frac{\mathbb{P}[\mathbf{i}^{(\D)}_{\tau+1} \mid \overline{\ell}_{\A},\mathbf{b}_{\tau}]}{\mathbb{P}[\mathbf{i}^{(\D)}_{\tau+1} \mid \ell_{\A},\mathbf{b}_{\tau}]}\right)\right)}\nonumber\\
\end{align}

where $Z_t$ is defined in Lemma <ref>. Step (a) above is well-defined by Assumption <ref> and follows because $\mathbf{I}^{(\mathrm{D})}$ is conditionally independent of $\mathbf{h}^{(\mathrm{D})}_{t-1}$ given $\mathbf{b}_{t-1}$.

Using the expression in (<ref>), we obtain that

\begin{align}
&\mathbb{E}_{\overline{\ell}_{\A} \sim \mu_{t+1}}\Big[\overbrace{K(\overline{\ell}_{\A},  \nu_{t})-K_{\mathcal{L}}^\star(\nu_{t})}^{\triangleq \Delta K(\overline{\ell}_{\A}, \nu_{t})}\Big] \label{eq:sigma_proof}\\
&= \frac{\int_{\mathcal{L}}\Delta K(\overline{\ell}_{\A}, \nu_{t})\mu_1(\mathrm{d}\overline{\ell}_{\A})\exp\left(-tZ_{t+1}(\overline{\ell}_\A)\right)}{\int_{\mathcal{L}}\mu_1(\mathrm{d}\overline{\ell}_{\A})\exp\left(-tZ_{t+1}(\overline{\ell}_\A)\right)}\nonumber \\
&=\frac{\int_{\mathcal{L}}\overbrace{\Delta K(\overline{\ell}_{\A}, \nu_{t})\mu_1(\mathrm{d}\overline{\ell}_{\A})\exp\left(-t(Z_{t+1}(\overline{\ell}_\A)-K^{\star}_{\mathcal{L}}(\nu_{t+1}))\right)}^{\triangleq \sigma}}{\int_{\mathcal{L}}\mu_1(\mathrm{d}\overline{\ell}_{\A})\exp\left(-t(Z_{t+1}(\overline{\ell}_\A)-K^{\star}_{\mathcal{L}}(\nu_{t+1}))\right)}.\nonumber
\end{align}

By defining $\mathcal{L}_{\epsilon} \triangleq \{\overline{\ell}_A \mid \Delta K(\overline{\ell}_{\A}, \nu_{t+1}) \geq \epsilon\}$ we can write the numerator in (<ref>) as

\begin{align}
&\int_{\mathcal{L}\setminus \mathcal{L}_{\epsilon}}\sigma + \int_{\mathcal{L}_{\epsilon}}\sigma \leq \epsilon + \int_{\mathcal{L}\setminus \mathcal{L}_{\epsilon}}\sigma.\label{eq:thm4_eps_bound}
\end{align}

Given this bound, it suffices to show that, for arbitrarily small $\epsilon > 0$,

\begin{align*}
\lim_{t\rightarrow \infty} \frac{\int_{\mathcal{L}_{\epsilon}}\sigma}{\int_{\mathcal{L}}\mu_1(\mathrm{d}\overline{\ell}_{\A})\exp\left(-t(Z_{t+1}(\overline{\ell}_\A)-K^{\star}_{\mathcal{L}}(\nu_{t+1}))\right)} = 0.
\end{align*}

Towards the proof of the limit above, we note that the exponent in $\sigma$ (<ref>) can be written as

\begin{align}
&-t(Z_{t+1}(\overline{\ell}_\A)-K^{\star}_{\mathcal{L}}(\nu_{t+1})) \nonumber\\
&=-t(Z_{t+1}(\overline{\ell}_\A)-K^{\star}_{\mathcal{L}}(\nu_{t+1})) + K(\overline{\ell}_{A},\nu_{t+1}) -K(\overline{\ell}_{A},\nu_{t+1})\nonumber\\
&=-t(\Delta K(\overline{\ell}_{\A}, \nu_{t+1}) + Z_{t+1}(\overline{\ell}_\A) -K(\overline{\ell}_{A},\nu_{t+1})). \label{eq:numerator_wrangling_thm_4}
\end{align}

Next, we recall from Lemma <ref> that for any $\epsilon > 0$, there exists $\eta > 0$ and $t_{\eta}\geq 1$ such that, for all $t \geq t_{\eta}$ and $\overline{\ell}_{\A} \in \mathcal{L}$, $|Z_t(\overline{\ell}_{\A} - K(\overline{\ell}_\A, \nu_{t+1}))| < \eta$. ($t_{\eta}$ is uniform as $|\mathcal{L}| < \infty$, Assumption <ref>.) This fact together with (<ref>) implies that

\begin{align}
&\frac{\int_{\mathcal{L}_{\epsilon}}\Delta K(\overline{\ell}_{\A}, \nu_{t+1})\mu_1(\mathrm{d}\overline{\ell}_{\A})\exp\left(-t(Z_{t+1}(\overline{\ell}_\A)-K^{\star}_{\mathcal{L}}(\nu_{t+1}))\right)}{\int_{\mathcal{L}}\mu_1(\mathrm{d}\overline{\ell}_{\A})\exp\left(-t(Z_{t+1}(\overline{\ell}_\A)-K^{\star}_{\mathcal{L}}(\nu_{t+1}))\right)}\nonumber\\
&\leq \frac{\int_{\mathcal{L}_{\epsilon}}\Delta K(\overline{\ell}_{\A}, \nu_{t+1})\mu_1(\mathrm{d}\overline{\ell}_{\A})\exp\left(-t(\Delta K(\overline{\ell}_\A, \nu_{t+1}) -\eta)\right)}{\int_{\mathcal{L}}\mu_1(\mathrm{d}\overline{\ell}_{\A})\exp\left(-t(\Delta K(\overline{\ell}_\A, \nu_{t+1}) + \eta)\right)}\nonumber\\
&= e^{2t\eta}\frac{\int_{\mathcal{L}_{\epsilon}}\Delta K(\overline{\ell}_{\A}, \nu_{t+1})\mu_1(\mathrm{d}\overline{\ell}_{\A})e^{-t\Delta K(\overline{\ell}_\A, \nu_{t+1})}}{\int_{\mathcal{L}}\mu_1(\mathrm{d}\overline{\ell}_{\A})e^{-t\Delta K(\overline{\ell}_\A, \nu_{t+1})}} & \tag{*}\label{eq:thm4_a_bound_pf1}
\end{align}

for all $t \geq t_{\eta}$.

Now consider the numerator in (<ref>). Since $xe^{-tx}$ is decreasing for all $x>t^{-1}$ and since $\Delta K(\overline{\ell}_{\A}, \nu_{t+1}) \geq \epsilon$ for all $\overline{\ell}_{\A} \in \mathcal{L}_{\epsilon}$, we have that

\begin{align*}
\int_{\mathcal{L}_{\epsilon}}\Delta K(\overline{\ell}_{\A}, \nu_{t+1})\mu_1(\mathrm{d}\overline{\ell}_{\A})e^{-t\Delta K(\overline{\ell}_\A, \nu_{t+1})} \leq \epsilon e^{-t\epsilon}
\end{align*}

for any $t \geq \max [t_{\eta}, \frac{1}{\epsilon}]$.

Next consider the denominator in (<ref>). By definition, $\exists \overline{\ell}_{\A} \in \mathcal{L}$ such that $K(\overline{\ell}_{\A},  \nu_{t})=K_{\mathcal{L}}^\star(\nu_{t}) \forall t$. This fact together with the assumption that $\mu_1$ has full support (Assumption <ref>) means that the denominator is a positive constant, which we denote by $k$. As a consequence, $(*) \leq e^{2t\eta}\epsilon e^{-t\epsilon}k^{-1}$. Let $\eta=\frac{\epsilon}{4}$. Then $e^{2t\eta}\epsilon e^{-t\epsilon}k^{-1}=e^{\frac{-t\epsilon}{2}}\epsilon k^{-1}$, which converges to $0$ as $t \rightarrow \infty$. Consequently, $\lim_{t \rightarrow \infty}\mathbb{E}_{\overline{\ell}_{\A}\sim \mu_t}[\Delta K(\overline{\ell}_{\A}, \nu_{t})] = 0$ a.s.-$\mathbb{P}^{\mathscr{R}}$.

§ PROOF OF THEOREM <REF>.B

The proof of Thm. <ref>.B follows the same procedure as that of Thm. <ref>.A, with the difference that $\Theta_{\mathrm{k}}$ is allowed to be non-finite, whereas $\mathcal{L}$ in Thm. <ref>.A is finite (Assumption <ref>).

Define $\Theta^{+}_{\mathrm{k},\epsilon}\triangleq \{\overline{\bm{\theta}} | \Delta K(\overline{\bm{\theta}}, \nu_{t})\geq \epsilon\}$ and $\Theta_{\mathrm{k},\frac{\epsilon}{2}}^{-}\triangleq \{\overline{\bm{\theta}} | \Delta K(\overline{\bm{\theta}}, \nu_{t})\leq \frac{\epsilon}{2}\}$. It then follows from (<ref>) that

\begin{align}
&\int_{\Theta_{\mathrm{k}}} \Big(\overbrace{K(\overline{\bm{\theta}},  \nu_{t})-K_{\Theta_{\mathrm{k}}}^\star(\nu_{t})}^{\Delta K(\overline{\bm{\theta}}, \nu_{t})}\Big)\rho^{(\mathrm{k})}_{t}(\mathrm{d}\overline{\bm{\theta}}) \leq \epsilon + \label{eq:thm4b_11}\\
& \underbrace{\frac{\int_{\Theta^{+}_{\mathrm{k},\epsilon}}\Delta K(\overline{\bm{\theta}}, \nu_{t})\exp\left(-t\left(Z_t(\overline{\bm{\theta}})-K_{\Theta_{\mathrm{k}}}^\star(\nu_{t})\right)\right)\rho^{(\mathrm{k})}_1(\mathrm{d}\overline{\bm{\theta}})}{\int_{\Theta_{\mathrm{k},\frac{\epsilon}{2}}^{-}}\exp\left(-t\left(Z_t(\overline{\bm{\theta}})-K_{\Theta_{\mathrm{k}}}^\star(\nu_{t})\right)\right)\rho^{(\mathrm{k})}_1(\mathrm{d}\overline{\bm{\theta}})}}_{\triangleq \text{\ding{73}}},\nonumber
\end{align}

where 73 is well-defined by Assumptions <ref>–<ref>.

(<ref>) implies that it suffices to prove that $\text{\ding{73}}\xrightarrow[]{t\rightarrow\infty} 0$ for arbitrarily small $\epsilon$. Applying Lemma <ref> and (<ref>), we obtain

\begin{align*}
\text{\ding{73}}&\numleq{a} e^{2t\eta} \frac{\int_{\Theta^{+}_{\mathrm{k}, \epsilon}}\Delta K(\overline{\bm{\theta}}, \nu_{t})e^{-t\Delta K(\overline{\bm{\theta}}, \nu_{t})}\rho^{(\mathrm{k})}_1(\mathrm{d}\overline{\bm{\theta}})}{\int_{\Theta_{\mathrm{k}, \frac{\epsilon}{2}}^{-}}e^{-t\Delta K(\overline{\bm{\theta}}, \nu_{t})}\rho^{(\mathrm{k})}_1(\mathrm{d}\overline{\bm{\theta}})}\\
&\numleq{b} e^{2t\eta} \frac{\epsilon e^{-t\epsilon}}{\int_{\Theta_{\mathrm{k}, \frac{\epsilon}{2}}^{-}}e^{-t\Delta K(\overline{\bm{\theta}}, \nu_{t})}\rho^{(\mathrm{k})}_1(\mathrm{d}\overline{\bm{\theta}})}\\
&\numleq{c} e^{2t\eta} \frac{\epsilon e^{-t\epsilon}}{e^{-t\frac{\epsilon}{2}}\int_{\Theta_{\mathrm{k}, \frac{\epsilon}{2}}^{-}}\rho^{(\mathrm{k})}_1(\mathrm{d}\overline{\bm{\theta}})} = e^{2t\eta} \frac{\epsilon e^{-t\frac{\epsilon}{2}}}{\rho^{(\mathrm{k})}_1(\Theta_{\mathrm{k}, \frac{\epsilon}{2}}^{-})}
\end{align*}

for all $t\geq \max[t_\eta, \epsilon^{-1}]$, where (a) follows from (<ref>); (b) follows because $xe^{-tx}$ is decreasing for all $x>t^{-1}$; and c) follows because $e^{-t\Delta K(\overline{\bm{\theta}}, \nu_{t})}\geq e^{-t\frac{\epsilon}{2}}$.

Let $\eta=\epsilon/8$. Then the numerator in the final expression above becomes $\epsilon e^{-t\frac{\epsilon}{4}}$, which converges to $0$ as $t \rightarrow \infty$. Thus what remains to show is that the denominator is positive in the limit, i.e., $\lim_{t\rightarrow\infty}\rho^{(\mathrm{k})}_1(\Theta_{\mathrm{k}, \frac{\epsilon}{2}}^{-})>0$. We prove this statement by establishing uniform continuity of $\Delta K(\overline{\bm{\theta}},\nu)$. Towards this end, we prove the following two lemmas.

$\mathcal{B}$ (<ref>) is a compact subset of $\mathbb{R}^{|\mathcal{S}|}$ with the Euclidean metric $d$ and $\Delta(\mathcal{B})$ a compact metric space with the Wasserstein-$p$ distance $W_p$ ($p \geq 1$).

Since $\mathcal{S}$ is finite, $\mathcal{B}=\Delta(\mathcal{S})$ is a compact subset of $\mathbb{R}^{|\mathcal{S}|}$. To prove that $(\Delta(\mathcal{B}), W_p)$ is compact we will show that every sequence $(\nu_n)_{n=1}^\infty\subset \Delta(\mathcal{B})$ admits a subsequence converging to some limit point in $\Delta(\mathcal{B})$. This collection of measures is tight as $\exists \mathcal{C}\subseteq \mathcal{B}$ such that $\nu_n(\mathcal{C})=1>1-\epsilon$ for any $\epsilon>0$ and $\nu_n$. As a consequence, $(\nu_n)_{n=1}^\infty$ admits a limit point $\nu^{\star}\in \Delta(\mathcal{B})$ w.r.t the topology of weak convergence (Prokhorov's theorem <cit.>).

We will show that $\nu^{\star}$ is also a limit point under $W_p$. By Skorokhod's representation theorem <cit.>, there exists a sequence of $\mathcal{B}$-valued random variables $\{V_1,\ldots, V_n,\ldots, V^{\star} \}$ such that $V_n$ has the probability law $\nu_n$ and $\lim_{n\rightarrow\infty}d(V_n, V^{\star})=0$ almost surely. By the dominance convergence theorem and the facts that $\mathcal{B}$ is compact and $d$ is continuous, $\lim_{n\rightarrow \infty}\mathbb{E}[d(V_n, V^{\star})^p]= 0$. Consequently, for any coupling $\xi$ between $\nu_n$ and $\nu^{\star}$,

\begin{align*}
\lim_{n\rightarrow\infty}\left(\int d(x,y)^p d\xi(x,y)\right)^{\frac{1}{p}}=0.
\end{align*}

Since $W_p(\nu_n, \nu^{\star})$ is the infimum of the left-hand side above, $\lim_{n\rightarrow\infty}W_p(\nu_n, \nu^{\star})=0$. Hence $(\Delta(\mathcal{B}), W_p)$ is compact.

$\Delta K(\overline{\bm{\theta}}, \nu)\triangleq K(\overline{\bm{\theta}},\nu)-K_{\Theta_{\mathrm{k}}}^\star(\nu)$ is a continuous map from $(\Theta_{\mathrm{k}}, d)\times (\Delta(\mathcal{B}), {W}_1)$ to $\mathbb{R}$, where $d$ and $W_1$ denote the Euclidean and the Wasserstein-$1$ distance, respectively.

We start by showing that $K(\overline{\bm{\theta}}, \nu)$ is continuous by proving that for any convergent sequence $(\overline{\bm{\theta}}_n, \nu_n) \xrightarrow[n \to \infty]{} (\overline{\bm{\theta}}, \nu)$, the difference $|K(\overline{\bm{\theta}}_n, \nu_n)-K(\overline{\bm{\theta}}, \nu)|$ converges to $0$. This difference can be bounded as

\begin{align*}
&|K(\overline{\bm{\theta}}_n, \nu_n)-K(\overline{\bm{\theta}}, \nu)|\leq \\
&\underbrace{|K(\overline{\bm{\theta}}_n, \nu_n)-K(\overline{\bm{\theta}}_n, \nu)|}_{\triangleq \text{\ding{172}}}+\underbrace{|K(\overline{\bm{\theta}}_n, \nu)-K(\overline{\bm{\theta}}, \nu)|}_{\triangleq \text{\ding{173}}}.
\end{align*}

Consider the left expression above (172). (<ref>) implies that

\begin{align*}
\text{\ding{172}}=&\left|\int_\mathcal{B}\mathbb{E}_{\mathbf{I}^{(\mathrm{k})}}\left[\ln\left(\frac{\mathbb{P}[\mathbf{I}^{(\mathrm{k})} \mid \bm{\theta}, \mathbf{b}]}{\mathbb{P}[\mathbf{I}^{(\mathrm{k})} \mid \overline{\bm{\theta}}_n, \mathbf{b}]}\right)\right]\nu_n(\mathrm{d}\mathbf{b} )\right.\\
&\left. -\int_\mathcal{B}\mathbb{E}_{\mathbf{I}^{(\mathrm{k})}}\left[\ln\left(\frac{\mathbb{P}[\mathbf{I}^{(\mathrm{k})} \mid \bm{\theta}, \mathbf{b}]}{\mathbb{P}[\mathbf{I}^{(\mathrm{k})} \mid \overline{\bm{\theta}}_n, \mathbf{b}]}\right)\right]\nu(\mathrm{d}\mathbf{b})\right|,
\end{align*}

which is an integral probability metric () with the testing function $f(b)\triangleq \mathbb{E}_{\mathbf{I}^{(\mathrm{k})}}\left[\ln\left(\frac{\mathbb{P}[\mathbf{I}^{(\mathrm{k})} \mid \bm{\theta}, \mathbf{b}]}{\mathbb{P}[\mathbf{I}^{(\mathrm{k})} \mid \overline{\bm{\theta}}_n, \mathbf{b}]}\right)\right]$. This function is assumed to be Lipschitz continuous (Assumption <ref>.1). Without loss of generality, we assume that the Lipschitz constant is $1$. Since the Wasserstein distance is equivalent to the w.r.t the class of 1-Lipschitz functions, 172 is upper-bounded by $W_p(\nu_n,\nu)$. Hence, as $\nu_n$ converges to $\nu$ in $W_p$, 172 converges to $0$.

We now show that 173 converges. Using Assumption <ref>.2 and the dominated convergence theorem, we obtain that

\begin{align*}
\lim_{n\rightarrow\infty}&\mathbb{E}_{\mathbf{b}\sim \nu}\mathbb{E}_{\mathbf{I}^{(\mathrm{k})}}\left[\ln\left(\frac{\mathbb{P}[\mathbf{I}^{(\mathrm{k})} \mid \bm{\theta}, \mathbf{b}]}{\mathbb{P}[\mathbf{I}^{(\mathrm{k})} \mid \overline{\bm{\theta}}_n, \mathbf{b}]}\right)\right]\\
=& \mathbb{E}_{\mathbf{b}\sim \nu}\mathbb{E}_{\mathbf{I}^{(\mathrm{k})}}\left[\ln\left(\frac{\mathbb{P}[\mathbf{I}^{(\mathrm{k})} \mid \bm{\theta}, \mathbf{b}]}{\mathbb{P}[\mathbf{I}^{(\mathrm{k})} \mid \overline{\bm{\theta}}, \mathbf{b}]}\right)\right],
\end{align*}

which implies that $\overline{\bm{\theta}}\mapsto K(\overline{\bm{\theta}},\nu)$ is continuous and that 173 converges to $0$ as $n\rightarrow\infty$.

Finally, applying Berge's maximum theorem <cit.> to $K(\overline{\bm{\theta}},\nu)$ w.r.t. $\overline{\bm{\theta}}$ yields that the mapping $\nu\mapsto K_{\Theta_{\mathrm{k}}}^\star(\nu)$ is continuous, which implies continuity of $\Delta K$.

§.§ Proof of Theorem <ref>.B

Lemmas <ref>–<ref> imply uniform continuity of $\Delta K(\overline{\bm{\theta}}, \nu)$ and Berge's maximum theorem implies that $|\Theta^\star_{\mathrm{k}}(\nu)|>0$ <cit.>. Therefore, $\exists \delta_m$ such that $d(\overline{\bm{\theta}}_\nu, \overline{\bm{\theta}}')< \delta_m$ and $W_1(\nu, \nu')< \delta_m$. This means that $\Delta K(\overline{\bm{\theta}}',\nu')\leq \Delta K(\overline{\bm{\theta}}_\nu, \nu)+m=m$, where the last equality follows because $\overline{\bm{\theta}}_\nu\in \Theta^\star_{\mathrm{k}}(\nu) \implies \Delta K(\overline{\bm{\theta}}_\nu, \nu)=0$. As a consequence, for any $\nu\in \Delta(\mathcal{B})$ and $\nu'\in B(\nu, \delta_m)\triangleq \{\nu'| W_1(\nu,\nu')< \delta_m\}$,

\begin{align*}
\underbrace{\{\overline{\bm{\theta}}'| d(\overline{\bm{\theta}}',\overline{\bm{\theta}}_\nu)< \delta_m\}}_{\Theta_{\nu}(\delta_m)} \subset \underbrace{\{\overline{\bm{\theta}}'| \Delta K(\overline{\bm{\theta}}',\nu')\leq m \}}_{\Theta_{\nu^{\prime}}(m)}.
\end{align*}

Thus, for any $\nu$ and $\nu'\in B(\nu, \delta_m)$,

\begin{align*}
\rho_1^{(\mathrm{k})}(\Theta_{\nu^{\prime}}(m))&\geq \rho_1^{(\mathrm{k})}(\Theta_{\nu}(\delta_m))>0,
\end{align*}

where the strict inequality follows because $\rho_1^{(\mathrm{k})}$ has full support (Assumption <ref>).

The set $\{B(\nu,\delta_m)\}_{\nu\in \Delta(\mathcal{B})}$ forms an open cover for a compact space, which means that there exists a finite subcover $\{B(\nu_i,\delta_m)\}_{i=1}^M$. As a consequence, $\nu'\in \Delta(\mathcal{B})$ belongs to some Wasserstein ball $B(\nu_i,\delta_m)$. Let $r \triangleq \min_{i}\rho^{(\mathrm{k})}_1(\Theta_{\nu_i}(\delta_m)) > 0$. We then have that

\begin{align*}
\rho_1^{(\mathrm{k})}(\Theta_{\nu^{\prime}}(m))&\geq \rho_1^{(\mathrm{k})}(\Theta_{\nu_i}(\delta_m)) \geq r,
\end{align*}

which yields $\rho_1^{(\mathrm{k})}(\Theta_{\mathrm{k}, \frac{\epsilon}{2}}^{-})\geq r>0$ with $m=\frac{\epsilon}{2}$.

§ EXAMPLE DERIVATION OF A BERK-NASH EQUILIBRIUM

We use the following example to illustrate the steps required to find a Berk-Nash equilibrium.

Consider Prob. <ref> with $N=1$, $p_{\mathrm{A}}=1$, $\mathcal{O}=\{0,1\}$, $z_{\bm{\theta}_t}(\cdot | 0) = \operatorname{Ber}(p)$, $z_{\bm{\theta}_t}(1 | 1) = \operatorname{Ber}(q)$, and $c$ being defined as in Fig. <ref>. Let the rollout parameters be ($\ell_{\mathrm{A}}=0$, $\ell_{\mathrm{D}}=1$) and let $\bm{\pi}_1$ be threshold strategies with $\beta \geq 0$ and $\alpha \leq 1$ (Thm. <ref>). Finally, let $\mathcal{L}=\{\ell_{\mathrm{A}}\}$, $\Theta_{\mathrm{A}}=\{\bm{\theta}_1\}$, and $\Theta_{\mathrm{D}}=\{\overline{\bm{\theta}}_{a}, \overline{\bm{\theta}}_b\}$, where $z_{\overline{\bm{\theta}}_{a}}(0 | 0)=z_{\overline{\bm{\theta}}_{a}}(1 | 1)=z_{\overline{\bm{\theta}}_{b}}(1 | 0)=z_{\overline{\bm{\theta}}_{b}}(0 | 1)=1$.

We start with condition (i) in Def. <ref>. Since $\ell_{\A}=0$, it suffices to consider $\pi_{\D}$. By the principle of optimality

\begin{align*}
\pi_\D(b) \in \argmin_{a \in \mathcal{A}_{\D}}\mathbb{E}_{S, B^{\prime}}\left[c(S,a) + \gamma \overline{J}^{(\bm{\pi}_1)}_{\D, \overline{\bm{\theta}}}(B^{\prime}) \mid b, \bm{\pi}_1\right],
\end{align*}

where $\overline{J}^{(\bm{\pi}_1)}_{\D}(B^{\prime}) = (1-\gamma\mathbf{P}_{\overline{\bm{\theta}},\bm{\pi}_1})^{-1}\mathbf{c}_{\bm{\pi}_1}$. From the definition of $\Theta_{\mathrm{D}}$ we obtain that $b=\mathbb{P}[S=1] \in \{0,1\}$ and that

\begin{align*}
\mathbf{P}_{\overline{\bm{\theta}}_a,\bm{\pi}_1} =
\begin{bmatrix}
1-q & q\\
1 & 0
\end{bmatrix},
\text{ }
\mathbf{P}_{\overline{\bm{\theta}}_b,\bm{\pi}_1} =
\begin{bmatrix}
1-p & p\\
1 & 0
\end{bmatrix},
\text{ }
\mathbf{c}_{\bm{\pi}_1} =
\begin{bmatrix}
\end{bmatrix}.
\end{align*}

Simple algebra yields

\begin{align*}
\overline{J}^{(\bm{\pi}_1)}_{\D,\overline{\bm{\theta}}_a} &=
\frac{1}{(\gamma-1)(1+\gamma q)}
\begin{bmatrix}
\gamma q\\
1+ \gamma (q-1)
\end{bmatrix},
\end{align*}

where $q$ is exchanged for $p$ when the conjecture is $\overline{\bm{\theta}}_b$. Hence, to meet condition (i), the defender's rollout strategy must satisfy $\pi_{\D}(0)=\mathsf{C}$ and $\pi_{\D}(1)=\mathsf{S}$, which is ensured by (<ref>). As a consequence, $\bm{\pi}=\bm{\pi}_1$ in any Berk-Nash equilibrium.

Now consider condition (ii); (<ref>) can be written as

\begin{align*}
K(\overline{\bm{\theta}},\nu)&= \mathbb{E}_{b\sim \nu}\mathbb{E}_{\mathbf{I}^{(\mathrm{D})}}\left[\ln\left(\frac{\mathbb{P}[\mathbf{I}^{(\mathrm{D})} \mid \bm{\theta}, b]}{\mathbb{P}[\mathbf{I}^{(\mathrm{D})} \mid \overline{\bm{\theta}}, b]}\right)\mid  \bm{\theta}, b\right]\\
&=-\sum_{b \in \{0,1\}}\nu(b)\sum_{o \in \{0,1\}}z_{\bm{\theta}}(o\mid b)\ln z_{\overline{\bm{\theta}}}(o\mid b) +\operatorname{const.}
\end{align*}

Minimizing the above expression with respect to $\bm{\overline{\theta}}$ yields $\Theta^{\star}_\D=\{\overline{\bm{\theta}}_a\}$ if $(p=0,q=1)$, $\Theta^{\star}_\D=\{\overline{\bm{\theta}}_b\}$ if $(p=1,q=0)$, and $\Theta^{\star}_{\mathrm{D}}(\nu)=\{\overline{\bm{\theta}}_a,\overline{\bm{\theta}}_b\}$ otherwise.

Lastly, condition (iii) is satisfied iff $\mathbf{P}^T_{\overline{\bm{\theta}},\bm{\pi}_1}\nu = \nu$. Solving this equation yields

\begin{align}
\nu(0) = -\left(-1-p + \rho^{(\D)}(\overline{\bm{\theta}}_a)p -\rho^{(\D)}(\overline{\bm{\theta}}_a)q\right)^{-1},\label{eq:stationary_cond_berk}
\end{align}

which means the Berk-Nash equilibrium is not unique and may not exist (see Fig. <ref>). For example, if $p=1$ and $q=0$, then (<ref>) requires that $\rho^{(\D)}(\overline{\bm{\theta}}_a)=1$, but this means that $\rho^{(\D)} \not \in \Delta(\Theta^{\star}(\nu)$, which violates condition (ii).

Berk-Nash equilibria of Example <ref> when $p=\frac{1}{2}$.

§ HYPERPARAMETERS

Figures and Tables     Values

Fig. <ref>     $\mathcal{O}=\{0,\hdots,9\}$, $p_{\mathrm{A}}=0.1, \gamma=0.99$,

$z(\cdot \mid 0) = \mathrm{BetaBin}(n=10,\alpha=0.7,\beta=3)$,

$z(\cdot \mid 1) = \mathrm{BetaBin}(n=10,\alpha=1,\beta=0.7$

Fig. <ref>     $\mathcal{O}=\{0,\hdots,9\}$, $p_{\mathrm{A}}=0.1$, $N=1$, $\gamma=0.99$

$z(\cdot \mid 0) = \mathrm{BetaBin}(n=10,\alpha=0.7,\beta=3)$,

$z(\cdot \mid 1) = \mathrm{BetaBin}(n=10,\alpha=1,\beta=0.7$

Fig. <ref>     $N=10$, $p_{\mathrm{A}}=0.1, \gamma=0.99$

$\pi_{\D, 1}(\mathsf{S} \mid \mathbf{b}_t) = 1 \iff \mathbb{P}[S_t \geq 1 \mid \mathbf{b}_t] \geq 0.75$

$\pi_{\A,1}(\mathsf{S} \mid \mathbf{b}_t,s_t) = 0.5$

Cost function of base strategy estimated

using $100$ MC samples w. horizon $50$

Figs. <ref>.a–e     $\ell_{\mathrm{A}}=\ell_{\mathrm{D}}=1, \mathcal{L}=\{1,2\}, p_{\mathrm{A}}=1$

$\pi_{\D, 1}(\mathsf{S} \mid \mathbf{b}_t) = 1 \iff \mathbb{P}[S_t \geq 1 \mid \mathbf{b}_t] \geq 0.75$

$\pi_{\A,1}(\mathsf{S} \mid \mathbf{b}_t,s_t) = 0.05$

$N=10$, $\mathcal{O}, z$ (Fig. <ref>)

using $100$ MC samples w. horizon $50$

Fig. <ref>, Fig. <ref>.f     $\mathcal{O}, z$ (Fig. <ref>), $p_{\mathrm{A}}=0.1, \gamma=0.99$,

$\mathcal{L}={0,1,2}$, $N=10$

$\pi_{\D, 1}(\mathsf{S} \mid \mathbf{b}_t) = 1 \iff \mathbb{P}[S_t \geq 1 \mid \mathbf{b}_t] \geq 0.75$

$\pi_{\A,1}(\mathsf{S} \mid \mathbf{b}_t,s_t) = 0.05$

Best response computation: <cit.>

Best responses parameterized following Thm. <ref>

Figs. <ref>.g–o, <ref>     $\ell_{\mathrm{A}}=\ell_{\mathrm{D}}=1, p_{\mathrm{A}}=1, \gamma=0.99$

$\pi_{\D, 1}(\mathsf{S} \mid \mathbf{b}_t) = 1 \iff \mathbb{P}[S_t \geq 1 \mid \mathbf{b}_t] \geq 0.75$

$\pi_{\A,1}(\mathsf{S} \mid \mathbf{b}_t,s_t) = 0.05$

$N=10$, $\mathcal{O}, z$ (Fig. <ref>)

using $100$ MC samples w. horizon $50$

Fig. <ref>.k     $\Theta_{\D} = \{0,\hdots, 200\}$

Table <ref>     $\ell_{\mathrm{A}}=\ell_{\mathrm{D}}=1, p_{\mathrm{A}}=1, \gamma=0.99$

$\pi_{\D, 1}(\mathsf{S} \mid \mathbf{b}_t) = 1 \iff \mathbb{P}[S_t \geq 1 \mid \mathbf{b}_t] \geq 0.75$

$\pi_{\A,1}(\mathsf{S} \mid \mathbf{b}_t,s_t) = 0.05$

$N=10$, $\mathcal{O}, z$ (Fig. <ref>, $t=10$)

using $100$ MC samples w. horizon $50$

Fig. <ref>     $\bm{\psi} = (\frac{1}{2}, 10^{-2}, -10^{5})$, $\bm{\chi} = (1.0593)$,

$\bm{\phi}=(-0.5193)$, $\bm{\omega} = (0.054\pi)$,

time-step: $30$s, service time: $\operatorname{Exp}(\mu=4)t$.

Confidence intervals     computed using the Student-t distribution

Base strategies $\pi_{\D,1}\pi_{\A,1}$     Approximate threshold best responses

against randomized opponents (Fig. <ref>)

Priors $\mu_1,\rho_1^{(\mathrm{D})},\rho_1^{(\mathrm{A})}$     uniform

Cost function (<ref>), Fig. <ref>     $p=5/4$, $q=1$, $r=2$

$\epsilon$     $0.1$

Cross-entropy method <cit.>

$\lambda$ (fraction of samples to keep)     $0.15,100$

$K$ population size     $100$

$M$ number of samples for each evaluation     $50$

<cit.> parameters

lr $\alpha$, batch, # layers, # neurons, clip $\epsilon$     $10^{-5}$, $4\cdot 10^{3}t$, $4$, $64$, $0.2$,

GAE $\lambda$, ent-coef, activation     $0.95$, $10^{-4}$, ReLU

<cit.> parameters

lr RL, lr SL, batch, # layers,# neurons, $\mathcal{M}_{RL}$     $10^{-2}$, $5\cdot 10^{-3}$, $64$, $2$,$128$, $2\times 10^{5}$

$\mathcal{M}_{SL}$,$\epsilon$, $\epsilon$-decay, $\eta$     $2\times 10^{6}$, $0.06$, $0.001$, $0.1$

The hyperparameters used for the evaluation in this paper are listed in Table <ref> and were obtained through grid search.

§ CONFIGURATION OF THE INFRASTRUCTURE IN FIG. <REF>

The configuration of the target infrastructure (Fig. <ref>) is available in Table <ref>.

ID(s)     Type     Operating system     Zone     Services     Vulnerabilities
$1$     Gateway     20     -     (ruleset v2.9.17.1), , v1.3, controller     -

$2$     Gateway     20         (ruleset v2.9.17.1), , v2.16, v1.3     -

$28$     Gateway     20         (ruleset v2.9.17.1), , v2.16, v1.3     -

$3$,$12$     Switch     22         , v1.3 , v2.16    -

$21,22$     Switch     22     -     , v1.3, v2.16     -

$23$     Switch     22         , v1.3, v2.16     -

$29$-$48$     Switch     22         , v1.3, v2.16     -

$13$-$16$     Honeypot     20         , , ,     -

$17$-$20$     Honeypot     20         , , , ,     -

$4$     App node     20         , ,     -1391

$5$, $6$     App node     20         , , ,     -

$7$     App node     20         , ,     -1391

$8$     App node             , , 2,    -2015-3306

$9$,$10$     App node     20         , , , ,     -

$11$     App node             2, ,     -2016-10033

$24$     Admin system     20         , ,     -1391

$25$     Admin system     20         , , , , 3,     -

$26$     Admin system     20         , , ,     -

$27$     Admin system     20         , , , , 3,     -1391

$49$-$59$     Compute node     20         ,     -

$60$     Compute node             , , 2,,     -2014-6271

$61$     Compute node     9.2         , 2,     -89

$62$     Compute node             , , 3, ,     -2010-0426

$63$     Compute node             , ,     -2015-5602

$64$     Compute node             , , , ,     -2017-7494

Configuration of the target infrastructure shown in Fig. <ref>; vulnerabilities in specific software products are identified by the vulnerability identifiers in the Common Vulnerabilities and Exposures () database <cit.>; vulnerabilities that are not described in the database are categorized according to the types of the vulnerabilities they exploit based on the Common Weakness Enumeration () list <cit.>.