Some Applications of the Partially Observable Markov Decision Processes

Abstract

We give two examples of reduction of a POMDPs model to a MDP model with a complete information. In both MDP models, corresponding Bellman’s equations allow to construct optimal policies. The first example is the classical discrete time disorder problem. We include it into the framework of POMDPs in contrast to the standard approach based on optimal stopping rules. In the second model, we consider the steps of a transaction under threat as a trajectory of POMDP. We show how to define the elements of the model in order to achieve an optimal balance between the successful end of the transaction and minimum applications of mitigating actions.

1. Introduction

Methods based on the Markov decision process (MDP) have become an essential part of the reinforcement learning in environments in which we can observe directly the evolution of the controlled object. In many situations, however, we suffer from limited capabilities to do that. The partially observable Markov decision processes (POMDPs) extend the MDP framework allowing us for decision making under the conditions of uncertainty. The classical approach to POMDPs suggests that in order to find the optimal policy in that model one should perform its reduction to a MDP model with complete information which consists of the following steps:

1. Find suitable sufficient statistics that play the role of a controlled process in the MDP model with complete information;

2. Define all elements of the MDP model;

3. Solve Bellman’s equation for the model from step 2.

Unfortunately, there is a lack of examples for which this procedure can be completed successfully. In this chapter, we present two POMDPs models by focusing on the algorithm described above and show how the optimal policies for these POMDPs can be represented.

Firstly, we revisit the discrete time disorder problem which was stated and investigated in details by Shiryaev [1]. The formal setting of this problem is the following. On some measurable space $\left(\mathrm{\Omega },\mathcal{F}\right)$ are given random variables $\theta ,{\xi }_1,{\xi }_2,\dots$ and a probability measure $P^{\pi }$ such that

$$P^{\pi }\left(\theta =0\right)=\pi ,P^{\pi }\left(\theta =n\right)=\left(1-\pi \right)p{\left(1-p\right)}^{n-1},n\ge 1,$$

where $0<p<1,0\le \pi \le 1$ are some constants, and the probability of any event $A=\left\{\omega :{\xi }_1\le x_1,\dots ,{\xi }_n\le x_n\right\}$ is equal to

$$P^{\pi }\left(A\right)=$$

$$=\pi P^1\left(A\right)+\left(1-\pi \right)\sum _{i=0}^{n-1}p{\left(1-p\right)}^i{P}^0\left\{{\xi }_1\le x_1,\dots ,{\xi }_i\le x_i\right\}$$

$$\times P^1\left\{{\xi }_{i+1}\le x_{i+1},\dots ,{\xi }_n\le x_n\right\}+\left(1-\pi \right)\left(1-p\right)P^0\left(A\right).$$

In the last formula both measures $P^0$ and $P^1$ define c.d.fs. $F_i\left(x\right)=P^i\left({\xi }_1\le x\right),i=0,1$ with densities $p_i\left(x\right),i=0,1.$ W.r.t. $P^i,i=0,1$ all random variables ${\xi }_1,{\xi }_2,\dots$ are i.i.d.

Let ${\mathcal{F}}^{\xi }=\left\{{\mathcal{F}}_n^{\xi }\right\},{\mathcal{F}}_0^{\xi }=\left\{\varphi ,\mathrm{\Omega }\right\},{\mathcal{F}}_n^{\xi }=\sigma \left({\xi }_1,{\xi }_2,\dots ,{\xi }_n\right),n=1,2,\dots$ be a filtration adapted to the observations ${\xi }_1,{\xi }_2,\dots$. The problem is to find a ${\mathcal{F}}^{\xi }$-stopping time $\tau$ which minimizes the risk

$${\rho }^{\pi }\left(\tau \right)=P^{\pi }\left(\tau <\theta \right)+{\mathit{cE}}^{\pi }{\left(\tau -\theta \right)}^{+},$$

where $c$ is a positive constant. A solution to that problem in terms of optimal stopping rules and martingale techniques can be found in [1].

In Section 3, we present a different approach to this problem including it into the framework of POMDPs. We show that steps 1 and 2 of the reduction can be performed successfully. Moreover, we define asymptotic solutions to Bellman’s equation and describe a procedure which allows to find them for some densities $p_0\left(x\right)$ and $p_1\left(x\right)$.

Section 4 is devoted to applications of POMDPs in the cybersecurity. The Contemporary Intrusion Detection Systems (IDS) are widely used in network management and cybersecurity frameworks for detecting and classifying potential security threats of unauthorized intrusions. The unauthorized intrusions during transaction processing are particularly dangerous because they can lead to significant financial losses. There are a number of security measures which can be used to counteract, but the success of their use depends on the precision of the detection and the time. In both network-based IDS, which use signature information [2], and host-based IDS, which use behavioral information [3] the data analysis utilizes a variety of methods for Machine Learning (ML).

In our recent papers, see [4, 5], we developed an approach based on the POMDPs which allows to perform a quantitative assessment of the impact of the parameters of the model on different important characteristics of the transaction. A deficiency of the model presented in [4, 5] is the assumption for a constant intrusion rate. Here, we relax it. Moreover, we reveal the crucial role of the costs of counteractions in building the model. On the one hand, they should favor the successful end of the transaction, but, on the other hand, prevent the unnecessary use of counteractions when there is no an attack. We show that the costs can be found as optimal solutions of some linear program. We complete this section by solving Bellman’s equation and describing the optimal policy in the model.

In order to make this chapter selfcontained we make a general description of POMDPs models in Section 2.

2. A general description of models with incomplete information

We remind the general framework of the model with incomplete information for controlled Partially Observable Markov Decision Processes (POMDP). For more details we refer the reader to [6, 7]. The model consists of the following elements:

1. The state space $X$. A non-empty Borel space.

2. An action space $A$. A non-empty Borel space.

3. An observation space $Z$. A non-empty Borel space.

4. A transition kernel $t\left({\mathit{dx}}_{n+1}|x_n,a_n\right)$. A probability measure on $X$ depending on both the last state $x_n$ and the last action $a_n$.

5. An observation kernel $s\left({\mathit{dz}}_{n+1}|x_{n+1},a_n\right)$. A probability measure on $Z$ depending on both the current state $x_{n+1}$ and the last action $a_n$.

6. An initial observation $s_0\left({\mathit{dz}}_0|x_0\right)$.

7. A running reward function $g\left(x_n,a_n\right)$.

8. A horizon $N$. A positive integer or $\infty$. If $N<\infty$ we introduce also a final reward $R\left(x_N\right)$.

We assume that all transition kernels and rewards are measurable.

The evolution of the POMDP is the following. At time $n,n=\mathrm{0,1,2},\dots$ it jumps from state $x_n$ to state $x_{n+1}$ according to the law $t\left({\mathit{dx}}_{n+1}|x_n,a_n\right)$. We do not observe both $x_n$ and $x_{n+1}$. Instead, we observe $z_{n+1}$, whose distribution is $s\left({\mathit{dz}}_{n+1}|x_{n+1},a_n\right)$, and add this observation to the information available till time $n+1$: $i_{n+1}=z_0{a}_0\dots z_n{a}_n{z}_{n+1}$. The initial information $i_0$ coincides with the initial observation $z_0$ which depends on the initial state $x_0$. We assume that the initial distribution $p$ of $x_0$ is also known.

Definition 1 A policy is a sequence $\pi =\left({\mu }_0,{\mu }_1,\dots ,{\mu }_{N-1}\right)$ of measures ${\mu }_n\left({\mathit{da}}_n|p,i_n\right)$ such that ${\mu }_n\left(A_n|p,i_n\right)=1,$ where $A_n$ is the set of all admissible actions corresponding to the initial distribution $p$ and the information $i_n$.

Besides the information $i_n$, we consider also the set of all histories $H_n$ till time $n$. Each history $h_n\in H_n$ includes not only $i_n$ but also all states visited by the process till time $n:h_n=x_0{z}_0{a}_0{x}_1{z}_1{a}_1\dots x_n{z}_n{a}_n$. According to Ionesku-Tulchea’s theorem to each initial distribution $p$ and policy $\pi$ on the set $H_n$ there corresponds a measure $P_n^{\pi }\left(p\right)$ given by the formula:

$$P_n^{\pi }\left(p\right)\left(X_0{Z}_0{A}_0\dots X_n{Z}_n{A}_n\right)=$$

$$={\int }_{X_0}{\int }_{Z_0}{\int }_{A_0}\dots {\int }_{X_n}{\int }_{Z_n}{\mu }_n\left(A_a|p,i_n\right)\times$$

$$\times s\left({\mathit{dz}}_n|x_n,a_{n-1}\right)t({\mathit{dx}}_n\mid x_{n-1},a_{n-1}\dots {\mu }_0\left({\mathit{da}}_0|p,z_0\right)s_0\left({\mathit{dz}}_0|x_0\right)p\left({\mathit{dx}}_0\right).$$

Here $X_0{Z}_0{A}_0\dots X_n{Z}_n{A}_n$ is a cylindrical subset of $H_n$. The problem is to find a policy $\pi$ which maximizes the total reward

$$J_N^{\pi }\left(p\right)=E_N^{\pi }\left(p\right)\left(\sum _{n=0}^{N-1}g\left(x_n,a_n\right)+R\left(x_N\right)\right),$$E1

where $E_N^{\pi }\left(p\right)$ is an expectation w.r.t. the measure $P_N^{\pi }\left(p\right)$, and the term $R\left(x_N\right)$ is missing if $N=\infty$.

If $N=\infty$, then in order to ensure convergence in (1) often introduce a discounting. However, the infinite horizon model which we study here is such that in (1) with probability $1$ there are a finite number nonzero terms. So, we do not need to take care for the convergence.

The general approach to the optimal control of POMDP consists in a reduction of problem (1) to a MDP with a complete information. We pay no attention to that reduction in a full generality, referring the reader to [6, 7]. However, in the next section we consider in details all steps of the reduction.

3. The disorder problem

In this section we develop an approach to the discrete time disorder problem based on POMDPs. We define the elements of the general model described in Section 2 as follows:

1. The state space $X=\left\{\mathrm{0,1,2}\right\}$ consists of three states $0,1$ and $2$.

2. The action space $A=\left\{\mathit{\text{wait}},\mathit{\text{stop}}\right\}$ consists of the two possible actions we can apply.

3. The observation space $Z$ coincides with the support of both densities $p_0\left(z\right)$ and $p_1\left(z\right)$. We assume that the supports of $p_0\left(z\right)$ and $p_1\left(z\right)$ coincide for, otherwise, in some cases we will observe directly the current state of the controlled process.

4. We define the transition kernel $t$ by:

   $$t\left(1|0,\mathit{\text{wait}}\right)=p,t\left(0|0,\mathit{\text{wait}}\right)=1-p,t\left(1|1,\mathit{\text{wait}}\right)=1,$$
   $$t\left(2|0,\mathit{\text{stop}}\right)=t\left(2|1,\mathit{\text{stop}}\right)=t\left(2|2\right)=1.$$

5. The observation kernel is

   $$s\left(\mathit{dz}|0,\mathit{\text{wait}}\right)=p_0\left(z\right)\mathit{dz},s\left(\mathit{dz}|1,\mathit{\text{wait}}\right)=p_1\left(z\right)\mathit{dz}.$$

6. The running reward is:

   $$g\left(0,\mathit{\text{wait}}\right)=1,g\left(1,\mathit{\text{wait}}\right)=-c<0,g\left(0,\mathit{\text{stop}}\right)=g\left(1,\mathit{\text{stop}}\right)=0,g\left(2\right)=0.$$

7. The initial distribution on $X$ is

   $$P\left(x_0=0\right)=1-\pi ,P\left(x_0=1\right)=\pi ,P\left(x_0=2\right)=0.$$

8. The horizon $N=\infty$.

Let us clarify how this model relates to the disorder problem as stated above. The moment of disorder $\theta$ which is $\mathit{Ge}\left(p\right)$-distributed is in fact the time of the first visit of the controlled process at state $1$. Our goal is to fix $\theta$ as precisely as possible making use of the action $\mathit{\text{stop}}$. If we are in state $0$ then the disorder still not occur, and the right decision is to wait. This yields an income equal to $1$, and our total reward increases by the same amount. However, if we miss $\theta$ (and therefore being in state $1$) then applying the action $\mathit{\text{wait}}$ is certainly a wrong decision which results in paying a positive penalty $c>0$. The only way to avoid such a situation is to stop the process, and to go to the absorbing state $2$. Since we apply the action $\mathit{\text{stop}}$ once, say at time $\tau$, we can identify any policy with that time, and consider the following problem: Maximize the total expected reward

$$J^{\tau }\left(\pi \right)=E^{\pi }\sum _{n=0}^{\tau -1}g\left(x_n,\mathit{\text{wait}}\right),$$E2

where $E^{\pi }$ is an expectation corresponding to the initial distribution given by Element 7 of the model.

Remark. In contrast to the optimal stopping approach where we receive our income when applying the action $\mathit{\text{stop}}$, formula (2) shows that now the situation is completely different—the whole reward is a result of waiting actions whereas the action $\mathit{\text{stop}}$ yields no income.

3.1 Filtration equations. Sufficient statistics. Bellman’s equation

The total probability formula implies the following representation of $J^{\tau }\left(\pi \right)$:

$$J^{\tau }\left(\pi \right)=\left(1-\pi \right)J^{\tau }\left(0\right)+\pi J^{\tau }\left(1\right).$$E3

Evidently, $J^{\tau }\left(1\right)=0$ because, being aware that the process starts at state $1$, the optimal policy recommends an immediate stop. In order to find $J^{\tau }\left(0\right)$ we follow a standard procedure of reducing the POMDP model to a model with complete information.

The first step of this procedure consists in solving the filtration equations. Denote by $f_n\left(i\right),i=0,1,n=1,2,\dots$ (resp. $r_n\left(i\right),i=0,1,n=1,2,\dots$) the prior (resp. posterior) probabilities of states $i,i=0,1$ at time $n$. Namely, $f_n\left(i\right)$ is the probability of being in state $i$ before observing ${\xi }_n$ whereas $r_n\left(i\right)$ is the same probability after the observation has occur. Let ${\xi }_1=z$. Since at the beginning we certainly know that the process starts at state $0$, and applying the Bayes rule we get

$$f_1\left(0\right)=1-p,f_1\left(1\right)=p,$$E4

$$r_1\left(0\right)=\frac{f_1\left(0\right)p_0\left(z\right)}{f_1\left(0\right)p_0\left(z\right)+f_1\left(1\right)p_1\left(z\right)},r_1\left(1\right)=\frac{f_1\left(1\right)p_1\left(z\right)}{f_1\left(0\right)p_0\left(z\right)+f_1\left(1\right)p_1\left(z\right)}.$$E5

Similarly, under the assumption that ${\xi }_n=z$, for any $n>1$ one holds

$$f_n\left(0\right)=\left(1-p\right)r_{n-1}\left(0\right),f_n\left(1\right)={\mathit{pr}}_{n-1}\left(0\right)+r_{n-1}\left(1\right),$$E6

$$r_n\left(0\right)=\frac{f_n\left(0\right)p_0\left(z\right)}{f_n\left(0\right)p_0\left(z\right)+f_n\left(1\right)p_1\left(z\right)},r_n\left(1\right)=\frac{f_n\left(1\right)p_1\left(z\right)}{f_n\left(0\right)p_0\left(z\right)+f_n\left(1\right)p_1\left(z\right)}.$$E7

The general theory recommends using suitable posterior probabilities, say $r_n\left(1\right),n=1,2,\dots$, as sufficient statistics. However, in our case it is more convenient to introduce other sufficient statistics. Indeed, formulas (6) and (7) imply that

$$\frac{f_n\left(1\right)}{f_n\left(0\right)}=\frac{{\mathit{pr}}_{n-1}\left(0\right)+r_{n-1}\left(1\right)}{\left(1-p\right)r_{n-1}\left(0\right)}=\frac{p}{1-p}+\frac{1}{1-p}\frac{r_{n-1}\left(1\right)}{r_{n-1}\left(0\right)}.$$E8

$$\frac{r_n\left(1\right)}{r_n\left(0\right)}=\frac{p_1\left(z\right)}{p_0\left(z\right)}\frac{f_n\left(1\right)}{f_n\left(0\right)}=\frac{p_1\left(z\right)}{p_0\left(z\right)}\left(\frac{p}{1-p}+\frac{1}{1-p}\frac{r_{n-1}\left(1\right)}{r_{n-1}\left(0\right)}\right).$$E9

Let us set

$$X_n=\frac{r_n\left(1\right)}{{\mathit{pr}}_n\left(0\right)}+1,n=1,2,\dots$$E10

Then, (17) reduces to

$$X_n=X_{n-1}/a\left(z\right)+1,a\left(z\right)=\frac{\left(1-p\right)p_0\left(z\right)}{p_1\left(z\right)}.$$E11

The linear relation between $X_n$ and $X_{n-1}$ in (11) makes the process $\left(X_n\right)$ very convenient to work with, and suitable to be the sufficient statistics for our problem.

In order to complete the reduction to a fully observable MDP it remains to express the reward $g_n$ in terms of $X_n$, and to find the conditional distribution of ${\xi }_n$ provided that $X_{n-1}=y$. Making use of (10), and the fact that $r_n\left(0\right)+r_n\left(1\right)=1$, we get

$$r_n\left(0\right)=\frac{1}{1+p\left(X_n-1\right)},r_n\left(1\right)=\frac{p\left(X_n-1\right)}{1+p\left(X_n-1\right)}.$$E12

On the other hand, the expected reward of the waiting action at step $n$ is equal to $r_n\left(0\right)-{\mathit{cr}}_n\left(1\right)$. Thus, in view of (12), the reward in the reduced MDP model should be

$$g\left(X_n\right)=1-\left(c+1\right)\frac{p\left(X_n-1\right)}{1+p\left(X_n-1\right)}.$$E13

Comparing (8) and (10) we get

$$\frac{f_n\left(1\right)}{f_n\left(0\right)}=\frac{p}{1-p}{X}_{n-1}.$$E14

Making use of the first equalities in (6), (12), as well as (14), we obtain

$$P\left({\xi }_n\in \mathit{dz}|X_{n-1}=y\right)=\mathit{dz}\left(f_n\left(1\right)p_1\left(z\right)+f_n\left(0\right)p_0\left(z\right)\right)$$

$$={\mathit{dzf}}_n\left(0\right)\left(\frac{f_n\left(1\right)}{f_n\left(0\right)}{p}_1\left(z\right)+p_0\left(z\right)\right)$$E15

$$={\mathit{dzf}}_n\left(0\right)\left(\frac{\mathit{py}}{1-p}{p}_1\left(z\right)+p_0\left(z\right)\right)$$

$$=\mathit{dz}\left(\frac{\mathit{py}}{1+p\left(y-1\right)}{p}_1\left(z\right)+\frac{1-p}{1+p\left(y-1\right)}{p}_0\left(z\right)\right).$$

Thus, in the reduced fully observable MDP model the controlled process is the Markov chain $X_n=X_{n-1}/a\left({\xi }_n\right)+1$. Its transitions are according to formula (15), and each waiting action yields an income (3). The action $\mathit{\text{stop}}$ yields no income and terminates the process. We want to maximize the total reward

$$R^{\tau }\left(y\right)=E\left(\sum _{n=1}^{\tau -1}g\left(X_n\right)|X_1=y\right),\sum _1^0=0,$$

where $\tau$ is the time when we apply the action $\mathit{\text{stop}}$. Let us set

$$V\left(y\right)=\underset{\tau }{sup}{R}^{\tau }\left(y\right).$$

The function $V\left(y\right)$ satisfies Bellman’s equation

$$V\left(y\right)=\left(1-\left(c+1\right)\frac{p\left(y-1\right)}{1+p\left(y-1\right)}\right.$$

$$+{\left.{\int }_{Z}V\left(y/a\left(z\right)+1\right)\left(\frac{{\mathit{pyp}}_1\left(z\right)}{1+p\left(y-1\right)}+\frac{\left(1-p\right)p_0\left(z\right)}{1+p\left(y-1\right)}\right)\mathit{dz}\right)}^{+}.$$E16

It is strictly positive on some interval $\left(1,y_0\right),y_0=y_0\left(c,p\right)$, and is equal to zero if $y\ge y_0$. If the threshold $y_0$ is known, then the optimal stopping rule is

$$\tau =min\left(n\ge 1:X_n>y_0\right).$$

3.2 Asymptotic solutions to Bellman’s equation

Multiplying (16) by $1+p\left(y-1\right)$ we get

$$\left(1+p\left(y-1\right)\right)V\left(y\right)={\left(1-\mathit{cp}\left(y-1\right)+{\int }_{Z}V\left(\frac{y}{a\left(z\right)}+1\right)\left({\mathit{pyp}}_1\left(z\right)+\left(1-p\right)p_0\left(z\right)\right)\mathit{dz}\right)}^{+}.$$E17

Making use of representation $\mathit{py}=\left(1+\mathit{py}/a\left(z\right)-1\right)a\left(z\right)$, and taking into consideration the second equality in (11) we see that the integral in the right-hand side of (17) is equal to

$${\int }_{Z}V\left(\frac{y}{a\left(z\right)}+1\right)\left(1+\mathit{py}/a\left(z\right)\right)a\left(z\right)p_1\left(z\right)\mathit{dz}.$$

The substitution $a\left(z\right)=t$ reduces the last integral to

$${\int }_{a\left(Z\right)}V\left(\frac{y}{t}+1\right)\left(1+p\frac{y}{t}\right)t^2\left(p_1\circ a\right)\left(t\right)\frac{\mathit{dt}}{t},$$E18

where $\left(p_1\circ a\right)\left(t\right)=p_1\left(a^{-1}\left(t\right)\right)/a^{\prime }\left(a^{-1}\left(t\right)\right)$ is the transformation of the density $p_1$ with the function $a\left(t\right)$.

Let us introduce a new unknown function $U\left(y\right)=\left(1+p\left(y-1\right)\right)V\left(y\right)$. Then, in terms of $U\left(y\right)$, and in view of (18), Eq. (17) reduces to

$$U\left(y\right)={\left(1-\mathit{cp}\left(y-1\right)+{\int }_{a\left(Z\right)}U\left(\frac{y}{t}+1\right)t^2\left(p_1\circ a\right)\left(t\right)\frac{\mathit{dt}}{t}\right)}^{+}.$$E19

Let $c=0$. Then, the optimal policy does not recommend using the action $\mathit{\text{stop}}$ at all, since then both states $1$ and $2$ become indistinguishable and we can only lose if the process is in state $0$. Therefore, in this case the function $U$ satisfies the equation

$$U\left(y\right)=1+{\int }_{a\left(Z\right)}U\left(\frac{y}{t}+1\right)t^2\left(p_1\circ a\right)\left(t\right)\frac{\mathit{dt}}{t}.$$

This observation motivates us to introduce asymptotic solutions to Eq. (16).

Definition 2 The function $V\left(y\right)={\left(U\left(y\right)/\left(1+p\left(y-1\right)\right)\right)}^{+},y\ge 1$ is an asymptotic solution to the eq. (16) as $c\to 0,$ if the function $U\left(y\right)$ satisfies the equation

$$U\left(y\right)=1-\mathit{cp}\left(y-1\right)+{\int }_{a\left(Z\right)}U\left(\frac{y}{t}+1\right)t^2\left(p_1\circ a\right)\left(t\right)\frac{\mathit{dt}}{t}.$$E20

The asymptotic optimal threshold $y_0$ is the root of the equation $U\left(y\right)=0$.

We are going to apply Mellin’s transform to Eq. (20). In order to be consistent with that transform, we assume that the set $a\left(Z\right)$ (and therefore $Z$) does not intersect with the negative part of the real line.

Let us recall that the Mellin transform $M\left[f\right]\left(s\right)$ of function $f\left(x\right),x>0,$ is defined by the formula

$$M\left[f\right]\left(s\right)={\int }_0^{\infty }{x}^{s-1}f\left(x\right)\mathit{dx},s\in {\mathrm{\Omega }}_f.$$E21

It is an analytical function inside domain ${\mathrm{\Omega }}_f$ which is usually either a half-plane or a stripe of the complex plane parallel to the imaginary axis. The Mellin transform is invertible and the inversion formula is

$$f\left(x\right)=\frac{1}{2\mathit{\pi i}}{\int }_{\gamma -i\infty }^{\gamma +i\infty }M\left[f\right]\left(s\right)x^{-s}\mathit{ds},\gamma \in {\mathrm{\Omega }}_f.$$E22

We are looking for solutions to Eq. (20) which belong to the class of Meyer’s $G$-functions. These functions have the property of their Mellin’s transform being

$$\mathrm{\Gamma }\left[\begin{array}{l}{b}_1+s,\cdots ,b_m+s,1-a_1-s,\cdots ,1-a_n-s\\ a_{m+1}+s,\cdots ,a_r+s,1-b_{m+1}-s,\cdots ,1-b_q-s\end{array}\right]$$

$$≔\frac{{\prod }_{i=1}^m\mathrm{\Gamma }\left(b_i+s\right){\prod }_{i=1}^n\mathrm{\Gamma }\left(1-a_i-s\right)}{{\prod }_{i=m+1}^r\mathrm{\Gamma }\left(a_i+s\right){\prod }_{i=m+1}^q\mathrm{\Gamma }\left(1-b_i-s\right)},$$E23

where $\mathrm{\Gamma }\left(\cdot \right)$ is the Euler gamma function, $0\le m\le q,0\le n\le r,$ and $a_i$ and $b_j,i=1,\dots ,r,j=1,\dots ,q$ are numbers. Formally, Meyer’s $G$-function is given by the integral

$$G_{\mathit{rq}}^{\mathit{mn}}\left(z|\left(a_r\right);\left(b_q\right)\right)=G_{\mathit{rq}}^{\mathit{mn}}\left(z|a_1,\dots ,a_r;b_1,\dots ,b_q\right)=$$

$$\frac{1}{2\mathit{\pi i}}{\int }_{\gamma -i\infty }^{\gamma +i\infty }\mathrm{\Gamma }\left[\begin{array}{l}{b}_1+s,\dots ,b_m+s,1-a_1-s,\dots ,1-a_n-s\\ a_{m+1}+s,\dots ,a_r+s,1-b_{m+1}-s,\dots ,1-b_q-s\end{array}\right]z^{-s}\mathit{ds},$$E24

where $\gamma$ is a number such that all poles $-b_j-k,k=0,1,\dots$ (resp. $1-a_i+k,k=0,1,\dots$) remain in the left (resp. right) half-plane w.r.t. the line $\mathit{Re}\left(s\right)=\gamma$. The properties of Meyer’s $G$-function as well as tables containing representations of many elementary and special functions in terms of Meyer’s $G$-functions can be found in [8], Chapter 8.

The following formulas represent Meyer’s $G$-functions in terms of generalized hypergeometric functions:

$$G_{\mathit{rq}}^{\mathit{mn}}\left(z\left|\begin{array}{c}\left(a_r\right)\\ \left(b_q\right)\end{array}\right.\right)$$

$$=\sum _{k=1}^m\mathrm{\Gamma }\left[\begin{array}{l}{b}_1-b_k,\widehat{\cdots },b_m-b_k,1+b_k-a_1,\dots ,1+b_k-a_n\\ a_{n+1}-b_k,\dots ,a_r-b_k,1+b_k-b_{m+1},\dots ,1+b_k-b_q\end{array}\right]z^{b_k}$$

$${\times }_r{F}_{q-1}\left(1+b_k-\left(a_r\right);1+b_k-{\left(b_q\right)}^{\text{'}};{\left(-1\right)}^{r-m-n}z\right),$$E25

$$r\le q,b_j-b_k\ne 0,\pm 1\pm 2,\dots$$

$$=\sum _{k=1}^n\mathrm{\Gamma }\left[\begin{array}{l}{a}_k-a_1,\widehat{\cdots },a_k-a_n,1+b_1-a_k,\dots ,1+b_m-a_k\\ a_k-b_{m+1},\dots ,a_k-b_q,1+a_{n+1}-a_k,\dots ,1+a_r-a_k\end{array}\right]z^{a_k-1}$$

$${\times }_q{F}_{r-1}\left(1+\left(b_q\right)-a_k;1+{\left(a_r\right)}^{\text{'}}-a_k;{\left(-1\right)}^{s-m-n}{z}^{-1}\right)$$E26

$$r\ge q,a_j-a_k\ne 0,\pm 1,\pm 2,\dots$$

Here, ${\left(a_r\right)}^{\prime }-a_k=a_1-a_k,\dots ,a_{k-1}-a_k,a_{k+1}-a_k,\dots ,a_r-a_k$ and $\mathrm{\Gamma }\left[a_1-a_k,\widehat{\cdots },a_m-a_k\right]≔\mathrm{\Gamma }\left(a_1-a_k\right)\dots \mathrm{\Gamma }\left(a_{k-1}-a_k\right)\mathrm{\Gamma }\left(a_k+1-a_k\right)\dots \mathrm{\Gamma }\left(a_m-a_k\right)$.

In order to apply the Mellin transform to Eq. (12), we need the following lemma for the Mellin transform of the composition of two functions.

Lemma 1 Let $f\left(x\right)$ and $\phi \left(x\right)$ be two functions, $F\left(s\right)=M\left[f\right]\left(s\right)$ and assume that the Mellin transform of function ${\left(\phi \left(x\right)\right)}^{-u}$ exists for all $u$ from the line $\mathit{Re}\left(u\right)=\beta$ which belongs to ${\mathrm{\Omega }}_f$. Let us set $G\left(s,u\right)=M\left[{\left(\phi \left(x\right)\right)}^{-u}\right]\left(s\right)$. Then

$$M\left[f\left(\phi \left(x\right)\right)\right]\left(s\right)=\frac{1}{2\mathit{\pi i}}{\int }_{\beta -i\infty }^{\beta +i\infty }G\left(s,u\right)F\left(u\right)\mathit{du}.$$E27

Proof. We apply the inversion formula (22) to the right-hand side of (27) taking $\gamma$ to be such that line $\mathit{Re}\left(s\right)=\gamma$ belongs to ${\mathrm{\Omega }}_{{\phi }^{-u}}$. Changing the order of integration, we get

$$\frac{1}{2\mathit{\pi i}}{\int }_{\gamma -i\infty }^{\gamma +i\infty }{x}^{-s}\mathit{ds}\frac{1}{2\mathit{\pi i}}{\int }_{\beta -i\infty }^{\beta +i\infty }G\left(s,u\right)F\left(u\right)\mathit{du}$$

$$=\frac{1}{2\mathit{\pi i}}{\int }_{\beta -i\infty }^{\beta +i\infty }F\left(u\right)\mathit{du}{\int }_{\gamma -i\infty }^{\gamma +i\infty }G\left(s,u\right)x^{-s}\mathit{ds}$$

$$=\frac{1}{2\mathit{\pi i}}{\int }_{\beta -i\infty }^{\beta +i\infty }F\left(u\right){\left(\phi \left(x\right)\right)}^{-u}\mathit{du}=f\left(\phi \left(x\right)\right),$$

which ends the proof.

Let us set $F\left(s\right)=M\left[U\right]\left(s\right),A\left(s\right)=M\left[t^2\left(p_1\circ a\right)\left(t\right)\right]\left(s\right)$. Applying Mellin’s transform to (20), and making use of the formula for the transform of a convolution, we get

$$F\left(s\right)=\frac{\mathit{cp}}{s+1}-\frac{1+\mathit{cp}}{s}+M\left[W\left(y+1\right)\right]\left(s\right)A\left(s\right).$$E28

Applying Lemma 1 to both functions $U\left(y\right)$ and $y+1$ we obtain

$$M\left[W\left(y+1\right)\right]\left(s\right)=\frac{1}{2\mathit{\pi i}}{\int }_{\beta -i\infty }^{\beta +i\infty }B\left(s,u-s\right)F\left(u\right)\mathit{du},$$

where $B\left(s,u-s\right)$ is the beta-function, and $\beta$ is such that the line of integration belongs to ${\mathrm{\Omega }}_U$. Substituting the last formula in (28) we come to the equation

$$F\left(s\right)=\frac{\mathit{cp}}{s+1}-\frac{1+\mathit{cp}}{s}+\frac{1}{2\mathit{\pi i}}{\int }_{\beta -i\infty }^{\beta +i\infty }B\left(s,u-s\right)F\left(u\right)\mathit{duA}\left(s\right).$$E29

If $U\left(y\right)$ is a $G$-function, then $F\left(s\right)$ is of the form (23), and so is the function under the integral in (29). The integral itself can be found by formula (24), and evaluated according to formulas (25) and (26). Thus, we can find $A\left(s\right)$, $\left(p_1\circ a\right)\left(t\right)$, and finally densities $p_0\left(z\right)$ and $p_1\left(z\right)$ which correspond to the function $\left(p_1\circ a\right)\left(t\right)$. The function $V\left(y\right)={\left(U\left(y\right)/\left(1+p\left(y-1\right)\right)\right)}^{+}$ will be an asymptotic solution to Eq. (16), corresponding to these densities.

This approach has been applied in [9], where we have found the stationary distribution of the Markov chain $X_n={\xi }_n{X}_{n-1}+1$ in case of some special i.i.d. random variables ${\xi }_n,n=1,2,\dots$.

4. The role of the cost functions for preventing intrusions in transactions under threat

Here, we briefly describe the model studied in [4, 5] which we denote by $M$. It consists of the following elements:

1. State space $S=\left\{\mathit{\text{safe}},\mathit{\text{danger}},\mathit{\text{deadend}}\right\}$—corresponds to the different types of situations from the point of view of the risk they pose:

   1. $\mathit{\text{safe}}$ Situations along the transactions in absence of any threats;

   2. $\mathit{\text{danger}}$ Situations in which the system is under the influence of security threats but still able to recover and

   3. $\mathit{\text{deadend}}$ Situations in which the system experiences severity and crashes completely under the security threats.

2. Action space $A=\left\{\mathit{\text{noact}},\mathit{\text{respond}}\right\}$—corresponds to the two types of actions from risk perspective:

   1. $\mathit{\text{noact}}$—no action intervention, the system goes straight to the next situation according to the recommended action and continues the normal track of execution of the current transaction, and

   2. $\mathit{\text{respond}}$—counteraction, which brings the system back to a safe situation after malicious action deviating the transaction from its normal course.

3. Observation space $Z=\left\{\mathit{\text{nothreat}},\mathit{\text{threat}},\mathit{\text{crash}}\right\}$—corresponds to the different types of events from risk viewpoint:

   1. $\mathit{\text{nothreat}}$—asynchronous event, which is non-threatening and does not require counteraction;

   2. $\mathit{\text{threat}}$—detection of malicious intervention which requires counteraction, and

   3. $\mathit{\text{crash}}$—losing control of the system without chance for recovery.

4. Transition kernel $q\left(s_{n+1}|s_n,a_{n+1}\right)$—probability of the transition from situation $s_n$ to situation $s_{n+1}$ under control $c_{n+1}$, calculated as follows:

   • $q\left(\mathit{\text{safe}}|\mathit{\text{safe}}\right)=p$, $p$ is the probability for absence of threats after transition from a safe situation;

   • $q\left(\mathit{\text{danger}}|\mathit{\text{safe}}\right)=1-p$, $1-p$ is the probability for presence of threats after transition to from safe situation;

   • $q\left(\mathit{\text{safe}}|\mathit{\text{danger}},\mathit{\text{respond}}\right)=1$ because the counteraction in dangerous situation eliminates the threat;

   • $q\left(\mathit{\text{deadend}}|\mathit{\text{danger}},\mathit{\text{noact}}\right)=1$ because the absence of counteraction in dangerous situation leads to inevitable crash of the system, and

   • $q\left(\mathit{\text{deadend}}|\mathit{\text{deadend}}\right)=1$ since there is no way out of the crash.

5. Occurrence kernel $t\left(z_n|s_n\right)$—probability of the occurrence of event $z_n$ in situation $s_n$, calculated as follows:

   • $t\left(\mathit{\text{nothreat}}|\mathit{\text{safe}}\right)=p_{11}$—probability of not observing threat occurrence in a safe state (true negative);

   • $t\left(\mathit{\text{nothreat}}|\mathit{\text{danger}}\right)=p_{12}$—probability of not observing threat occurence in a dangerous stage (false negative);

   • $t\left(\mathit{\text{threat}}|\mathit{\text{safe}}\right)=p_{21}$—probability of observing threat occurrence in a safe state (false positive);

   • $t\left(\mathit{\text{threat}}|\mathit{\text{danger}}\right)=p_{22}$—probability of observing threat occurrence in a dangerous state (true positive), and

   • $t\left(\mathit{\text{crash}}|\mathit{\text{deadend}}\right)=1$—probability of observing the system crash under threat.

6. Costs—quantitative measures of the costs of taking actions which can be interpreted differently, depending on the needs; we are considering it to be the delay caused by the additional counteractions to neutralize the detected threats:

   1. Running cost $r\left(c\right)$ calculated as follows: $r\left(\mathit{\text{noact}}\right)=0$, $r\left(\mathit{\text{respond}}\right)=-c$ where $c>0$ is the penalty for executing counteraction $\mathit{\text{respond}}$;

   2. Final reward $R\left(s_F\right)$. This is the reward we get in the final state $s_F$. We define it as follows: $R\left(\mathit{\text{safe}}\right)=R\left(\mathit{\text{danger}}\right)=1,R\left(\mathit{\text{deadend}}\right)=0$. Thus, we consider the final state $s_F$ as an indicator whether the transaction was successful or not.

7. Horizon $N$—length of the transaction, measured by the number of situations along the transaction.

A security decision $\varphi \left(n\right)$ is a function which on each step $n$ of the transaction chooses either $\mathit{\text{noact}}$ or $\mathit{\text{respond}}$. Decision policy $\pi =\left(\varphi \left(1\right),\varphi \left(2\right),\dots ,\varphi \left(N\right)\right)$ is a collection of security decisions such that on each step $n$ of the transaction, $\varphi \left(n\right)$ depends only on the past observations, and the prior probabilities of the states before the transaction has begun. We assume that the prior probability of state $\mathit{\text{deadend}}$ is $0$, since otherwise any policy makes no sense. Therefore, the sum of the prior probabilities of the other two states is equal to $1$, and the prior distribution of the states is determined by the prior probability $x$ of state $\mathit{\text{safe}}$. In [4] we studied a problem with a criterion

$$v^{\pi }\left(x\right)=E_x^{\pi }\left(R\left(s_F\right)-\mathit{cK}\right),$$E30

where $E_x^{\pi }$ is the expectation, corresponding to the policy $\pi$ and the prior probability $x$, and $K$ is the total number of times when we apply the action $\mathit{\text{respond}}$. A value function of the POMDP model is the function

$$v\left(x\right)=\underset{\pi }{max}{v}^{\pi }\left(x\right).$$E31

The policy $\pi$ such that $v\left(x\right)=v^{\pi }\left(x\right)$ is an optimal policy.

Element 6 of the model $M$, the running cost, is crucial. The point is that if we allow it to be arbitrary, we can face the following two extreme situations:

• Case 1: $c$ is too small. Then the optimal policy may recommend applying mitigating action respond permanently, without taking into consideration any observations;

• Case 2: $c$ is too large. Then we would not be able to neutralize all threats even if we know exactly when they occur, i.e., when both the false positives and the false negatives are equal to 0. This could happen because the total cost of the mitigating actions may exceed $1$, which is the maximum reward we can get for a successful end of the transaction.

In [5], we suggested the following choice of $c$. Let $m$ be the maximum number when the action $\mathit{\text{respond}}$ can be used. Then, we have

$$\mathit{mc}\le 1,\left(m+1\right)c\ge 1,$$E32

and therefore,

$$\frac{1}{m+1}\le c\le \frac{1}{m}.$$E33

Since the number of attacks during the transaction has a Binomial distribution with parameters $1-p$ and $N$, a suitable choice of $m$ is it to be $1-\alpha$-quantile of this distribution for a given significance level $\alpha$.

Remark. Formula (33) assigns to $c$ values inside the interval to which it must belong. However, in fact we should select between the end points of that interval. If we take $c=1/\left(m+1\right)$, then we favor the successful end of the transaction. Otherwise, if $c=1/m$, we focus on avoiding a unnecessary use of mitigating actions.

In the model described above, the probability of attacks, $1-p$, remains unchanged during the transaction. This makes the model too restrictive. Indeed, in the real life, if the computer is infected before the transaction, it is more likely to expect intrusions at its early steps rather than in the end. Moreover, some transaction steps like entering an IBAN for money transfer or credentials, are more risky than the others, purely technical, steps of the transactions. Here, we relax this restriction assuming that $p=\left(p_1,p_2,\dots ,p_N\right)$ is a vector, whose entry $p_n$ is equal to the probability to stay in the state $\mathit{\text{safe}}$ at the $n$-th step of the transaction. It is worth noting that $p_1$ is exactly the prior probability $x$ in the model $M$, and $1-p_1$ is a probability of attacks which, however, occur not during the transaction, but before it. We shall refer to this model as a generalized model, and denote it by $M^{\prime }$.

Let us discuss the running costs in this model. As we have seen, they are very important, since they control the actions we apply on different steps of the transaction. If the probability $p_n$ is large, then the corresponding running cost $c_n$ should be large as well, in order to prevent a useless choice of a mitigating action. Evidently, such an action should be applied in case of a probability $p_n$ which is small enough, and we favor its application taking $c_n$ to be small, too. Thus, $c_n$ depends on $p_n$ (but not only), and we define the running costs in this model as a vector $c=\left(c_1,c_2,\dots ,c_N\right)$. The other elements of both models $M$ and $M^{\prime }$ coincide. Eq. (30) in model $M^{\prime }$ reads as

$$v^{\pi }\left(x\right)=E_x^{\pi }\left(R\left(s_F\right)-\sum _{i=1}^N{c}_{i}1\left(a_i=\mathit{\text{respond}}\right)\right).$$E34

We stress the dependence of $c_n$ on $p_n$, making the following basic assumption.

Assumption 1 For any two steps $i$ and $j$ of the transaction, one holds $c_i=c_j$ if $p_i=p_j$.

This assumption trivially holds in model $M$, and it implies that the running cost in that model is a constant.

4.1 Determining costs $c_1,c_2,\dots ,c_N$

Here, we are going to determine the costs $c_1,c_2,\dots ,c_N,$ trying to satisfy the following conditions:

• guarantee a successful end of the transaction with a probability which is large enough;

• avoid a useless application of the action $\mathit{\text{respond}}$ when the current state of the transaction is $\mathit{\text{safe}}$.

Unlike the model $M$ when, given $N,p$, and a significance level $\alpha$, one should take $c$ according to the remark after formula (33), here the situation is more complicated.

We shall consider the transaction as a random trial whose basic space $\mathrm{\Omega }$ is the set of all diadic representation of integers between $0$ and $2^N-1$:

$$\mathrm{\Omega }=\left\{\omega =w_1{w}_2\dots w_N,w_n=0\text{or}1,n=1,2,\dots ,N\right\}.$$

We assume that $w_n=1$ (resp. $w_n=0$) corresponds to the event when there is (resp. there is no) an intrusion on the $n$-th step of the transaction. Each elementary event $\omega \in \mathrm{\Omega }$ is determined by the set

$$A_{\omega }\in 2^{\left\{1,2,\dots ,N\right\}},A_{\omega }=\left\{n:w_n=1\right\},$$E35

where $2^{\left\{1,2,\dots ,N\right\}}$ is the set of all subsets of $\left\{1,2,\dots ,N\right\}$.

Formula (35) implies that there exists 1–1 correspondence between $\mathrm{\Omega }$ and $2^{\left\{1,2,\dots ,N\right\}}$. If necessary, we shall denote by ${\omega }_A$ the elementary event $\omega \in \mathrm{\Omega }$, that corresponds to the set $A\subseteq \left\{1,2,\dots ,N\right\}$. The probability $q_{\omega }$ of $\omega \in \mathrm{\Omega }$ can be calculated by the formula

$$q_{\omega }=\prod _{n=1}^N{p}_n^{1-w_n}{\left(1-p_n\right)}^{w_n}.\omega \in \mathrm{\Omega }.$$E36

Let us fix a significance level $\alpha$, and let

$$q^{\left(1\right)}\le q^{\left(2\right)}\le \dots \le q^{\left(2^N\right)}$$E37

be the ordered statistics of series $\left(q_{\omega }\right),\omega \in \mathrm{\Omega }$. Denote by $A_i$ the set given by (35), that corresponds to $q^{\left(i\right)}$¹, and define the integer $I$ by the formula:

$$I=min\left(i:\sum _{j=1}^i{q}^{\left(j\right)}>\alpha ,\text{and}{q}^{\left(i\right)}<q^{\left(i+1\right)}\right).$$E38

4.1.1 Case 1

All probabilities $p_n,n=1,2,\dots ,N$, are different.

First, we shall discuss the case when all probabilities $p_n,n=1,2,\dots ,N$ are different. Similarly to the inequalities in (32), we want that the costs $c_1,c_2,\dots ,c_N$ satisfy the constraint

$$\sum _{j=1}^N{w}_j{c}_j=\sum _{j\in A_i}{c}_j\ge 1,\omega ={\omega }_{A_i},i=1,2,\dots ,I,$$E39

$$\sum _{j=1}^N{w}_j{c}_j=\sum _{j\in A_i}{c}_j\le 1,\omega ={\omega }_{A_i},i=I+1,I+2,\dots ,2^N.$$E40

The mean cost of the transaction is equal to

$$C=\sum _{i=1}^N\left(1-p_i\right)c_i.$$E41

In view of the remark after formula (33) is natural to try to minimize $C$, in order to favor the successful end of the transaction. Thus, we come to the following linear program: minimize (41), under constraint (39) and (40). Evidently, if $N$ is large, this problem seems to become hopeless to solve even with the help of supercomputers.

4.1.2 Case 2

Some of the probabilities $p_1,p_2,\dots ,p_N$, coincide.

Now, assume that some of the probabilities $p_1,p_2,\dots ,p_N$ coincide. At a first glance in this case the problem becomes even more complicated, because, in view of Assumption 1, to the inequality constraint (40) and (41), one should add equality constraint $c_i=c_j$ for all pairs of states $\left(i,j\right)$ such that $p_i=p_j$. However, it turns out that the more equal probabilities among $p_1,p_2,\dots ,p_N$ there are, the simplier the problem becomes. Let

$$P_1<P_2<\dots <P_K,K<N,$$

be all different numbers among $p_1,p_2,\dots ,p_N$. Then, we can represent the set $\left\{1,2,\dots ,N\right\}$ as a union of disjoint subsets $B_1,B_2,\dots ,B_K$ such that

$$B_k=\left\{n:p_n=P_k\right\},k=1,2,\dots ,K.$$

Assumption 1 implies that not only the probabilities $\left(p_n\right),n=1,2,\dots ,N$, but also the costs $\left(c_n\right),n=1,2,\dots ,N$ coincide on each set $B_1,B_2,\dots ,B_K$. Denote them by $C_1,C_2,\dots ,C_K$. Then, in terms of $C_1,C_2,\dots ,C_K$, both the constraint (39) and (40) as well as formula (41) reduce to

$$\sum _{k=1}^K{d}_{\mathit{ik}}{C}_k\ge 1,i=1,2,\dots ,I,$$E42

$$\sum _{k=1}^K{d}_{\mathit{ik}}{C}_k\le 1,i=I+1,I+2,\dots ,2^N,$$E43

$$C=\sum _{k=1}^K{D}_k\left(1-P_k\right)C_k,$$E44

where $d_{\mathit{ik}},k=1,2,..,K,i=1,2,\dots ,2^N,$ and $D_k,k=1,2,..,K,$ are cardinalities of sets $A_i\cap B_k,$ and $B_k$, respectively. Thus, the problem becomes: minimize (44) under constraint (43) and (44). The dimensionality of this problem is $K$ rather than $N$. Moreover, the number of constraint will be less than $2^N$. In order to understand this, we give the following definition.

Definition 3 We say that the vector $a=\left(a_1,a_2,\dots ,a_K\right)$ majorates the vector $b=\left(b_1,b_2,\dots ,b_K\right)$, and write $a\succcurlyeq b$, if $a_k\ge b_k,k=1,2,..,K.$.

Denote by $\mathrm{\Delta }$ the matrix with entries $\left(d_{\mathit{ik}}\right)$, and let ${\delta }_i=\left(d_{i1},d_{i2},\dots ,d_{\mathit{iK}}\right),i=1,2,\dots ,2^N$, be its rows. If $i,j\le I$ and ${\delta }_i\succcurlyeq {\delta }_j$, then we can discard the constraint ${\delta }_i$, because it will hold automatically if we satisfy ${\delta }_j$. Similarly, if $i,j>I$, and ${\delta }_i\succcurlyeq {\delta }_j$, then we can discard the constraint ${\delta }_j$, because it will hold automatically if we satisfy ${\delta }_i$. Thus, the number of constraint in (5) (resp. (4)) is equal to the cardinality of the maximum subset of $\left\{1,2,\dots ,I\right\}$ (resp. $\left\{I+1,I+2,\dots ,2^N\right\}$) such that for any two $i$ and $j$ belonging to this subset neither ${\delta }_i\succcurlyeq {\delta }_j$ nor ${\delta }_j\succcurlyeq {\delta }_i$.

4.2 An example

A transaction consists of $N=12$ steps with probabilities

$$p=\left(\mathrm{0.6,0.9,0.9,0.8,0.7,0.9,0.9,0.9,0.9,0.9,0.8,0.9}\right).$$

We have $K=4,P=\left(\mathrm{0.6,0.7,0.8,0.9}\right),D=\left(\mathrm{1,1,2,8}\right).$ The linear program (42), (43) reduces to: minimize

$$0.4C_1+0.3C_2+0.4C_3+0.8C_4,$$

under constraint

$$C_1+3C_4\ge 1,$$

$$C_2+3C_4\ge 1,$$

$$C_3+3C_4\ge 1,$$

$$C_3+C_4\ge 1/2,$$

$$C_2+C_3+2C_4\ge 1,$$

$$C_1+C_3+2C_4\le 1,$$

$$C_1+C_2+2C_4\le 1,$$

$$C_1+C_2+2C_3+C_4\le 1,$$

where

$$0\le C_1\le 1,0\le C_2\le 1,0\le C_3\le 1/2,C_4=1/3.$$

Its solution is $C_1=0,C_2=C_3=1/6,C_4=1/3.$ Thus, in the first state of the transaction, which is most dangerous, one should pay a zero cost for counteracting. Therefore, we shall certainly prevent an attack in this state, if it occurs.

4.3 Description of the optimal policy

Here, we briefly describe the optimal policy in model $M^{\prime }$, referring the reader for more details to [4], where, in case of the model $M$, both the value function (31) and the optimal policy have been found by performing a standard reduction to a fully observable MDP. Sufficient statistics in this reduction are the posterior probabilities of the states of the transaction. Since the state $\mathit{\text{deadend}}$ is absorbing, the total probability of the other two states, $\mathit{\text{safe}}$ and $\mathit{\text{danger}}$, is 1, and we can consider the posterior probability of either of them, say $\mathit{\text{safe}}$, as a controlled process in the reduced MDP model. The state space of that process is $\left[0,1\right]\cup \left\{\ast \right\}$, where the isolated point ${}^{\ast }$ corresponds to state $\mathit{\text{deadend}}$. Consider the following functions defined for $x\in \left[0,1\right]$:

$${\mathrm{\Gamma }}^1\left(x,1-x\right)=\frac{p_{21}x}{p_{21}x+p_{22}\left(1-x\right)},{\mathrm{\Gamma }}^2\left(x,1-x\right)=\frac{p_{11}x}{p_{11}x+p_{12}\left(1-x\right)},$$E45

$$V_n\left(x\right)=\underset{\pi }{max}{E}_x^{\pi }\left(1\left(0\le x_{N+1}\le 1\right)-{\mathrm{\Sigma }}_{k=n}^N{c}_{k}1\left(a_k=\mathit{\text{respond}}\right)\right),n=1,\dots N,$$E46

where $x=x_n$ is the posterior probability of state $\mathit{\text{safe}}$ at time $n$. The function ${\mathrm{\Gamma }}^1\left(x,1-x\right)$ (resp. ${\mathrm{\Gamma }}^2\left(x,1-x\right)$) in (45) is the posterior probability of state $\mathit{\text{safe}}$, if we detect a $\mathit{\text{danger}}$ (resp. $\mathit{\text{nothreat}}$), and the prior probability of state $\mathit{\text{safe}}$ is $x$. The functions in (46) represent the maximum income we can get after the $n$-th step of the transaction. They satisfy Bellman’s equation

$$V_n\left(x\right)=max\left(V_n^{\prime }\left(x\right),{V^{\prime }}_n^{\prime }\left(x\right)\right),$$E47

and the final condition

$$V_{N+1}\left(x\right)=1.$$E48

In (47), $V_n^{\prime }\left(x\right)$ and ${V^{\prime }}_n^{\prime }\left(x\right)$ are one-step ahead estimates of both actions $\mathit{\text{noact}}$ and $\mathit{\text{respond}}$:

$$V_n^{\prime }\left(x\right)=x\left(p_n{p}_{21}+\left(1-p_n\right)p_{22}\right)V_{n+1}\left({\mathrm{\Gamma }}^1\left(p_n,1-p_n\right)\right)$$

$$+x\left(p_n{p}_{11}+\left(1-p_n\right)p_{12}\right)V_{n+1}\left({\mathrm{\Gamma }}^2\left(p_n,1-p_n\right)\right),$$

$${V^{\prime }}_n^{\prime }\left(x\right)=-c_n+\left(p_n{p}_{21}+\left(1-p_n\right)p_{22}\right)V_{n+1}\left({\mathrm{\Gamma }}^1\left(p_n,1-p_n\right)\right)$$

$$+\left(p_n{p}_{11}+\left(1-p_n\right)p_{12}\right)V_{n+1}\left({\mathrm{\Gamma }}^2\left(p_n,1-p_n\right)\right).$$

The optimal strategy ${\phi }_n$ at any moment of time $n=1,2,\dots ,N$ is the following:

$${\phi }_n\left(x\right)=\left\{\begin{array}{ll}\mathit{\text{noact}},& \text{if}{V}_n\left(x\right)=V_n^{\prime }\left(x\right)\\ \mathit{\text{respond}},& \text{if}{V}_n\left(x\right)={V^{\prime }}_n^{\prime }\left(x\right)\end{array}\right..$$

Eqs. (47) can be solved backwards, starting with the boundary condition (48). For example, for $n=N$ we get:

$$V_N\left(x\right)=max\left(1-c_N,x\right),$$

$${\phi }_N\left(x\right)=\left\{\begin{array}{ll}\mathit{\text{noact}},& \text{if}x\ge 1-c_N\left(\text{above}\text{the}\text{threshold}\right)\\ \mathit{\text{respond}},& \text{if}x<1-c_N\left(\text{bellow}\text{the}\text{threshold}\right)\end{array}.\right.$$

The remaining iterations until reaching the beginning of the transaction can be performed recursively, taking the previously calculated solution as terminal. It is worth noting that not only ${\phi }_N$, but also all ${\phi }_n,n=1,2\dots ,N-1$ are determined by thresholds $\left(y_n\right),n=1,2,\dots ,N-1,y_N=1-c_N$, and the optimal policy recommends using of a counteraction only if the posterior probability of state $\mathit{\text{safe}}$ in time $n,x_n,$ is less than $y_n$.

After all thresholds have been found, the optimal policy recommends the following optimal behavior:

1. At the beginning of transaction ($n=1$), depending on whether we detect a threat or not, we calculate the posterior probability $x_1$ of the state $\mathit{\text{safe}}$ by the formula

   $$x_1=\left\{\begin{array}{ll}{\mathrm{\Gamma }}^1\left(p_1,1-p_1\right),& \mathit{\text{if}}{z}_1=\mathit{\text{threat}}\\ {\mathrm{\Gamma }}^2\left(p_1,1-p_1\right),& \mathit{\text{if}}{z}_1=\mathit{\text{nothreat}}\end{array},\right.$$

   If $x_1$ is greater than the threshold $y_1$, then we do not apply the counteraction, $x_1$ remains unchanged, and with probability $1-x_1$ we fall into a state $\mathit{\text{deadend}}$. Otherwise, we use $\mathit{\text{respond}}$ after paying the cost $c_1$, and the posterior probability becomes $1$ since we certainly know that we are $\mathit{\text{safe}}$;

2. On the next step we start with a prior probability equal to the just found posterior probability ($x_1$ or $1$), multiplied by $p_2$, observe again if there is detection of a threat, calculate the posterior probability $x_2$, compare it with the threshold $y_2$, and so on till the end of the transaction.

5. Conclusions

We focus on two new applications of the theory of the Partially Observable Markov Decision Processes (POMDPs).

Firstly, we revisit the discrete time disorder problem. The classical approach to it is based on optimal stopping rules and martingale technique. We include it into the framework of POMDPs which improves the quality of detection, and allows, in some cases, to find solutions to Bellman’s equation.

The second application is in the cybersecurity. A basic problem here is the assessment of the security risk during transaction processing. We consider the transaction as a controlled POMDP and construct an optimal policy that recommends a best behavior for neutralizing the intrusions when they occur. We reveal the crucial role of the costs of counteractions in building the model. On the one hand, they should favor the successful end of the transaction, but, on the other hand, prevent the unnecessary use of counteractions when there is no an attack. We show that the costs can be found as optimal solutions of some linear program.

Abbreviations

POMDP	Partially Observable Markov Decision Processes
MDP	Markov Decision Processes
IDS	Intrusion Detection Systems
ML	Machine Learning