Minimum-Cost State-Flipped Control
for Reachability of Boolean Control Networks
using Reinforcement Learning

Markov decision process provides the framework for reinforcement learning, which is represented as a quintuple $(\mathbf{X},\mathbf{A},\gamma,\mathbf{P},\mathbf{R})$. $\mathbf{X}=\{x_{t},t\in\mathbb{Z^{+}}\}$ and $\mathbf{A}=\{a_{t},t\in\mathbb{Z^{+}}\}$ denote the state space and action space, respectively. The discount factor $\gamma\in[0,1]$ weighs the importance of future rewards. The state-transition probability $\mathbf{P}_{x_{t}}^{x_{t+1}}(a_{t})=\Pr\left\{x_{t+1}\mid x_{t},a_{t}\right\}$ represents the chance of transitioning from state $x_{t}$ to $x_{t+1}$ under action $a_{t}$. $\mathbf{R}_{x_{t}}^{x_{t+1}}(a_{t})=\mathbb{E}\left[r_{t+1}\mid x_{t},a_{t},x_{t+1}\right]$ denotes the expected reward obtained by taking action $a_{t}$ at state $x_{t}$ that transitions to $x_{t+1}$. At each time step $t\in\mathbb{Z^{+}}$, an agent interacts with the environment to determine an optimal policy. Specificly, the agent observes $x_{t}$ and selects $a_{t}$, according to the policy $\pi:x_{t}\rightarrow a_{t},\forall t\in\mathbb{Z^{+}}$. Then, the environment returns $r_{t+1}$ and $x_{t+1}$. The agent evaluates the reward $r_{t+1}$ received for taking action $a_{t}$ at state $x_{t}$ and then updates its policy $\pi$. Define $G_{t}=\sum_{i=t+1}^{T}\gamma^{i-t-1}r_{t}$ as the return. The goal of the agent is to learn the optimal policy $\pi^{*}:x_{t}\rightarrow a_{t},\forall t\in\mathbb{Z^{+}}$, which satisfies

where $\mathbb{E}_{\pi}$ is the the expected value operator following policy $\pi$, and $\Pi$ is the set of all admissible policies. The state-value and the action-value are $v_{\pi}(x_{t})=\mathbb{E}_{\pi}[G_{t}|x_{t}]$ and $q_{\pi}(x_{t},a_{t})=\mathbb{E}_{\pi}[G_{t}|x_{t},a_{t}]$, respectively. The Bellman equations reveal the recursion of $v_{\pi}(x_{t})$ and $q_{\pi}(x_{t},a_{t})$, which are given as follows:

The optimal state-value and action-value are defined as

For problems under the framework of Markov decision process, the optimal policy $\pi^{*}$ can be obtained through $Q$L. In the following, we introduce $Q$L.

$Q$L is a classical algorithm in reinforcement learning. The purpose of $Q$L is to enable the agent to find an optimal policy $\pi^{*}$ through its interactions with the environment. $Q_{t}(x_{t},a_{t})$, namely, the estimate of $q^{*}(x_{t},a_{t})$, is recorded and updated every time step as follows:

where $\alpha_{t}\in(0,1],t\in\mathbb{Z^{+}}$ is the learning rate, and $TDE_{t}=r_{t+1}+\gamma\max\limits_{a\in\mathbf{A}}Q_{t}(x_{t+1},a)-Q_{t}(x_{t},a_{t})$ .

In terms of action selection, $\epsilon$-greedy method is used

where $P$ is the probability of selecting the corresponding action, $0\leq\epsilon\leq 1$, and $\operatorname{rand}(\mathbf{A})$ is an action randomly selected from $\mathbf{A}$.

Once $Q$L converges, the optimal policy is obtained:

The premise for using $Q$L is to structure the problem within the framework of Markov decision process. We represent Markov decision process by the quintuple $(\mathcal{B}^{n},\mathcal{B}^{m+|B|},\mathbf{P},\mathbf{R},\gamma)$, where $\mathcal{B}^{n}$ and $\mathcal{B}^{m+|B|}$ are the state space and action space, respectively. The state and the action are defined as $x_{t}=x(t)$ and $a_{t}=\big{(}u(t),\eta_{A(t)}\big{)}$, respectively. The reward is given as follows:

To incentivize the agent to reach $x_{t}\in\mathcal{M}_{d}$ as quickly as possible, we set the discount factor $\gamma\in(0,1)$.

Assuming the agent is aware of the dimensions of $\mathcal{B}^{n}$ and $\mathcal{B}^{m+|B|}$ but lacks knowledge of $\mathbf{P}$ and $\mathbf{R}$, meaning the agent does not comprehend the system dynamics (3). Through interactions with the environment, the agent implicitly learns about $\mathbf{P}$, $\mathbf{R}$, refines estimation of $q^{*}\left(x_{t},a_{t}\right)$, and enhances its understanding of $\pi^{*}$.

Under the reward setting (12), it is worthwhile to investigate methods for determining the reachability of BCNs defined by equation (3). To answer this question, we present Theorem 1.

As $Q$L iterates, all state-action-state pairs $(x_{t},a_{t},x_{t+1})$ are constantly visited [28]. Therefore, there can be a case where the state-action-state pairs $(x_{T},a_{T},x_{T+1})$, $(x_{T-1},a_{T-1},x_{T})$, $(x_{T-2},a_{T-2},x_{T-1})$, …,$(x_{0},a_{0},x_{1})$ are visited one after another, and in between, other state-action-state pairs can also exist. This case causes the values in the $Q$-table to transition from all zeros to some being positive. Furthermore, we assume that this case initially occurs at time step $t^{\prime}$. Then, the corresponding change of action-value from zero to positive is given by $Q_{t^{\prime}}\big{(}x_{T},a_{T}\big{)}\leftarrow\alpha_{t^{\prime}-1}(r_{t^{\prime}}+\gamma\max\limits_{a\in A}Q_{t^{\prime}-1}(x_{T+1},a))+(1-\alpha_{t^{\prime}-1})Q_{t^{\prime}-1}\big{(}x_{T},a_{T}\big{)}$, where $r_{t^{\prime}}=100$ since $x_{T+1}\in\mathcal{M}_{d}$. Additionally, due to the absence of negative rewards and the fact that initial action-values are all 0, it follows that $Q_{t^{\prime}-1}(x_{T+1},a)\geq 0$ for all $a\in\mathbf{A}$. Thus, after the update, we have $Q_{t^{\prime}}\big{(}x_{T},a_{T}\big{)}>0$. According to (9), at $t^{\prime}+1$, it follows that $Q_{t^{\prime}+1}\big{(}x_{T},a_{T}\big{)}>0$. Similarly, for any $t^{\prime\prime}>t^{\prime}$, it follows that $Q_{t^{\prime\prime}}\big{(}x_{T},a_{T}\big{)}>0$.

Next, we prove that there exists $t^{*}$ such that $Q_{t^{*}}\big{(}x_{\overline{t}},a_{\overline{t}}\big{)}>0$, where $\overline{t}=T,\ T-1,\ ...,\ 0$, based on mathematical induction. The proof is divided into two parts. Firstly, there exists $t^{\prime}$ such that $Q_{t^{\prime}}\big{(}x_{\overline{t}},a_{\overline{t}}\big{)}>0$ where $\overline{t}=T$, according to the proof in the previous paragraph. Second, we prove that if $(x_{\overline{t}},a_{\overline{t}},x_{{\overline{t}}+1})$ is visited at time step $t^{\prime\prime}$ and $Q_{t^{\prime\prime}}\big{(}x_{{\overline{t}}+1},a_{{\overline{t}}+1}\big{)}>0$, then $Q_{t^{\prime\prime}+1}\big{(}x_{\overline{t}},a_{\overline{t}}\big{)}>0$. Since $(x_{\overline{t}},a_{\overline{t}},x_{{\overline{t}}+1})$ is visited at time step $t^{\prime\prime}$, it follows that $Q_{t^{\prime\prime}+1}\big{(}x_{\overline{t}},a_{\overline{t}}\big{)}\leftarrow\alpha_{t^{\prime\prime}}(r_{t^{\prime\prime}+1}+\gamma\max\limits_{a\in\mathbf{A}}Q_{t^{\prime\prime}}(x_{{\overline{t}}+1},a))+(1-\alpha_{t^{\prime\prime}})Q_{t^{\prime\prime}}\big{(}x_{{\overline{t}}},a_{{\overline{t}}}\big{)}$. In the updated formula, we have $r_{t^{\prime\prime}+1}\geq 0$, and $Q_{t^{\prime\prime}}\big{(}x_{{\overline{t}}},a_{{\overline{t}}}\big{)}\geq 0$. Furthermore, since $Q_{t^{\prime\prime}}(x_{{\overline{t}}+1},a_{{\overline{t}}+1})>0$, it implies that $\max\limits_{a\in\mathbf{A}}Q_{t^{\prime\prime}}(x_{{\overline{t}}+1},a)>0$. Consequently, we have $Q_{t^{\prime\prime}+1}\big{(}x_{\overline{t}},a_{\overline{t}}\big{)}>0$. According to mathematical induction, there exists $t^{*}$ such that $Q_{t^{*}}\big{(}x_{0},a_{0}\big{)}>0$. Since $a_{0}\in\mathbf{A}$ holds, we have $\max\limits_{a\in\mathbf{A}}Q_{t^{*}}(x_{0},a)>0$.

(Sufficiency) Suppose that there exists $t^{*}$ such that $\max\limits_{a\in\mathbf{A}}Q_{t^{*}}(x_{0},a)>0,\ \forall x_{0}\in\mathcal{M}_{0}$. Without loss of generality, we assume that there is only one $x_{0}\in\mathcal{M}_{0}$ as well as one $x_{d}\in\mathcal{M}_{d}$, $\text{arg}\max\limits_{a\in\mathbf{A}}Q_{t^{*}}(x_{0},a)=a_{t}$, and $\max\limits_{a\in\mathbf{A}}Q_{t^{*}-1}(x_{0},a)=0$. Then, according to the updated formula $Q_{t^{*}}\big{(}x_{0},a_{t}\big{)}\leftarrow\alpha_{t^{*}-1}(r_{t^{*}}+\gamma\max\limits_{a\in\mathbf{A}}Q_{t^{*}-1}(x_{0\text{next}},a))+(1-\alpha_{t^{*}-1})Q_{t^{*}-1}\big{(}x_{0},a_{t}\big{)}$, where $x_{0\text{next}}$ is the subsequent state of $x_{0}$, at least one of the following two cases exists:

• •

  Case 1. There exist $a_{t}$ and $x_{0\text{next}}$ such that $r_{t^{*}}(x_{0\text{next}},a_{t})$ $>0$.

• •

  Case 2. $x_{0\text{next}}$ satisfies $\max\limits_{a\in\mathbf{A}}Q_{t^{*}-1}(x_{0\text{next}},a)>0$.

In Case 1, we have $x_{0\text{next}}\in\mathcal{M}_{d}$. It implies that system (3) from state $x_{0}$ is reachable to state set $\mathcal{M}_{d}$ in one step.

In terms of Case 2, let us consider the condition under which $\max\limits_{a\in\mathbf{A}}Q_{t^{*}-1}(x_{0\text{next}},a)>0$, meaning that there exists an action $a\in\mathbf{A}$ such that $Q_{t^{*}-1}(x_{0\text{next}},a)>0$. We define the $i^{th}$ action-value, which changes from 0 to a positive number, as $Q_{t_{i}}(x_{i},a_{i})$. Here, $t_{i}$ denotes the time step of the change of the $i^{th}$ action-value, and $(x_{i},a_{i})$ corresponds to the state-action pair. Since the initial $Q$-values are all 0, it follows that $Q_{t_{1}}(x_{1},a_{1})>0$ if and only if $x_{1\text{next}}\in\mathcal{M}_{d}$. This implies that system (3) from state $x_{1}$ is reachable to state set $\mathcal{M}_{d}$ within one step, leading to $r_{t_{1}}>0$. Next, for any $i>1$, $Q_{t_{i}}(x_{i},a_{i})>0$ occurs if and only if $x_{i\text{next}}\in\mathcal{M}_{d}$, or $x_{i\text{next}}=x_{j},\ j<i$, where $x_{j}$ is a state that has satisfied $Q_{t_{j}}(x_{j},a_{j})>0$ for $t_{j}<t_{i}$ based on the previously defined conditions. This means that for $Q_{t_{i}}(x_{i},a_{i})>0,\ \forall i$, at least one of the following two events has taken place: either $\mathcal{M}_{d}$ is reachable from $x_{i}$; or a state $x_{j},j<i$, which can reach $\mathcal{M}_{d}$, is reachable from $x_{i}$. In both cases, it implies that $\mathcal{M}_{d}$ is reachable from $x_{i}$. Thus, if $Q_{t^{*}-1}(x_{0\text{next}},a)>0$, it follows that $\mathcal{M}_{d}$ is reachable from $x_{0\text{next}}$. This, in turn, implies that $\mathcal{M}_{d}$ is also reachable from $x_{0}$. Based on the analysis of Cases 1 and 2, if $\max\limits_{a\in\mathbf{A}}Q_{t^{*}-1}(x_{0},a)$ $>0$ holds for all $x_{0}\in\mathcal{M}_{0}$, then $\mathcal{M}_{d}$ is reachable from $\mathcal{M}_{0}$. $\hfill\blacksquare$

Based on Theorem 1 and Lemma 2, we present Algorithm 1 for finding flipping kernels. First, we provide the notation definitions used in Algorithm 1. $C_{|A|}^{k}$ denotes the combinatorial number of flip sets with the given $k$ nodes in $A$. $B_{k_{i}}$ represents the $i^{th}$ flip set with the given $k$ nodes. $ep$ denotes the number of episodes, where ``Episode" is a term from reinforcement learning, referring to a period of interaction that has passed through $T_{max}$ time steps from any initial state $x_{0}\in\mathcal{M}_{0}$. $T_{max}$ is the maximum time step, which should exceed the length of the trajectory from $\mathcal{M}_{0}$ to $\mathcal{M}_{d}$. One can refer to Lemma 2 for the setting of $T_{max}$.

The core idea of Algorithm 1 is to incrementally increase the flip set size from $|B|$ to $|B|+1$ in step 18 when reachability isn't achieved with flip sets of size $|B|$. Specifically, step 4 fixes the flip set $B$, followed by steps 5-16 assessing reachability under that flip set, guided by Theorem 1. Upon identifying the first flipping kernel (when the condition in step 12 is met), the cardinality of the kernel is determined. This leads to setting $K=|B|$ as per step 13, along with step 2 to prevent ineffective access to a larger flip set. After evaluating system reachability under all flip sets with $K$ nodes, steps 20-24 present the algorithm's results.

Although Algorithm 1 is efficient, there is room for improvement. The next section outlines techniques to enhance its convergence efficiency.

In this subsection, we propose Algorithm 2, known as fast iterative $Q$L for finding the flipping kernels, which improves the convergence efficiency. The main difference between Algorithm 2 and Algorithm 1 can be classified into two aspects. 1) Special initial states: Algorithm 2 selects initial states strategically instead of randomly. 2) TL: Algorithm 2 utilizes the knowledge gained from achieving reachability with smaller flip sets to search for flipping kernels for larger flip sets.

In this subsection, we present Algorithm 3, named small memory iterative $Q$L, which is inspired by the work of [20]. This algorithm serves as a solution for identifying flipping kernels in large-scale BCNs. The core idea behind Algorithm 3 is to store action-values only for visited states, instead of all $x_{t}\in\mathcal{B}^{n}$, to reduce memory consumption. To implement this idea, we make adjustments to step 5 in Algorithm 1 and introduce additional steps 10-12 in Algorithm 3. Subsequently, we offer detailed insights into the effectiveness of Algorithm 3 and its applicability.