# Learning Deceptive Strategies in Adversarial Settings:
## 2 Problem Statement
### Mathematical Formulation  
We formulate the problem as a game on a discrete-time, grid-based environment defined over a finite two-dimensional lattice \(\mathcal{G}\subset\mathbb{Z}^{2}\) of size \(w\times h\). Each cell \((i,j)\in\mathcal{G}\)  
Figure 1: Schematic of the game where the police officer does not know the exit the robber is going to use to leave the city.  
represents the robber's possible location, with \(i\in\{0,\ldots,w\}\) and \(j\in\{0,\ldots,h\}\). The environment comprises two learning agents--the _robber_ (R) and the _police officer_ (P)--and a set of \(n\) goal locations  
\[G=\{g_{1},g_{2},\ldots,g_{n}\}\subset\mathcal{G},\]  
and a set of \(k\) static obstacles  
\[\mathcal{O}=\{\boldsymbol{o_{1}},\boldsymbol{o_{2}},\ldots,\boldsymbol{o_{k}} \}\subset\mathcal{G}.\]  
All goals lie in _free cells_; that is, \(G\cap\mathcal{O}=\emptyset\). Exactly one goal is the _true goal_, denoted \(g_{\tau}\), and the remaining goals form the set of _fake goals_, \(G_{F}=G\setminus\{g_{\tau}\}\) (Figure 2).  
Let \(\mathbf{x_{R}}(t)\in\mathcal{G}\) denote the robber's position at time \(t\in\mathbb{N}_{0}\), and his action set is  
\[A_{\text{R}}=\{\text{up},\text{down},\text{left},\text{right}\}.\]  
For each goal \(g_{i}\), let \(p_{i}(t)\in\Re_{+}\) denote the police reinforcement allocated at time \(t\), and define the police-reinforcement vector as  
\[\mathbf{x_{P}}(t):=[p_{1}(t),\,p_{2}(t),\ldots,p_{n}(t)].\]  
The police officer's action set is denoted by  
\[A_{\text{P}}\ =\ \Big{\{}[a_{1},a_{2},\ldots,a_{n}]\in\{0,1\}^{n}\ \Big{|}\ \sum_{i=1}^{n}a_{i}=1\Big{\}}. \tag{1}\]  
The environment is assumed to be deterministic: an action \(a\in A_{\text{R}}\) moves the robber one cell in the chosen direction, and an action \(a\in A_{\text{P}}\) updates the reinforcement vector by  
\[\mathbf{x_{P}}(t+1)=\mathbf{x_{P}}(t)+a(t).\]  
We denote the state of the game at time \(t\) by  
\[\boldsymbol{s}(t)=[\mathbf{x_{R}}(t),\,\mathbf{x_{P}}(t)]\in\mathcal{G} \times\Re_{+}^{n}, \tag{2}\]  
which results in the state space being \(\mathcal{S}=\mathcal{G}\times\Re_{+}^{n}\). Let \(\pi_{\text{R}}\) be the robber's policy, where \(\pi_{\text{R}}(a\mid s)\) is the probability of selecting action \(a\in A_{\text{R}}\) in state \(s\in\mathcal{S}\), and let \(\pi_{\text{P}}\) be the police officer's policy over \(A_{\text{P}}\).  
Figure 2: Sample environment with multiple goals and obstacles.  
Define the terminal time to be the first instance when the robber reaches its true goal:  
\[t_{f}(\tau_{\mathsf{R}},\pi_{\mathsf{P}},\mathbf{s}(0))=\min\{\,t\mid\mathbf{x}_{\mathsf{ R}}(t)=\mathbf{g}_{\textsc{T}}\},\]  
which depends on the policy pair \(\pi=(\pi_{\mathsf{R}},\pi_{\mathsf{P}})\) and the initial state \(\mathbf{s}(0)\). The robber seeks to minimize the reinforcement at the true goal, \(p_{\textsc{T}}(t_{f})\), while the police officer seeks to maximize it. In game-theoretic form, this objective can be expressed as  
\[\min_{\pi_{\mathsf{R}}}\max_{\pi_{\mathsf{P}}}\;\mathbb{E}_{\sim\pi}\big{[}p _{\textsc{T}}(t_{f})\big{]}, \tag{3}\]  
where the expectation is taken with respect to the randomization in the agents' strategies.  
This formulation differs from classical min-max games because the police officer does not know which goal is true and therefore cannot optimize \(p_{\textsc{T}}\) directly. We employ reinforcement learning techniques for both \(\mathsf{R}\) and \(\mathsf{P}\) to learn their policies \(\pi_{\mathsf{R}}\) and \(\pi_{\mathsf{P}}\). Our aim is to design reward structures so that \(\mathsf{R}\) can exploit its informational advantage to deceive \(\mathsf{P}\), while \(\mathsf{P}\) learns counter-deception strategies to mitigate \(\mathsf{R}\)'s deception.