Optimal Sensor and Actuator Selection for Factored Markov Decision Processes: Complexity, Approximability and Algorithms

Many applications in large-scale networks like congestion control [12, 13], load-balancing [14, 15] and energy optimization in large data-centers [1, 2] suffer from limited sensing and actuating resources. In many autonomous systems, the number of sensors or actuators that can be installed is limited by a certain budget and system design constraints [16]. In robotics applications, system designers often face the challenge of achieving certain design objectives such as maximizing observability and performance of the robot [16] [17][18], under limited sensing or actuating resources.

Scenario 1: Consider a task where a team of mobile robots have to simultaneously localize themselves (i.e., estimate their state) and perform tasks in an environment (see Figure 1). The robots can communicate with sensors deployed in the environment to localize themselves. Each robot has an underlying MDP and receives rewards for successfully completing tasks. Due to limited budget, a central designer can only deploy a limited number of sensors in the environment. The designer has to select an optimal subset of sensors to be placed in order to localize (i.e., estimate the states of) the robots, which can maximize the overall reward obtained by the team of robots.

Scenario 2: Consider a complex electric distribution network consisting of interconnected micro-grid systems, each containing generation stations, substations, transmission lines and electric loads, as shown in Figure 2. Each node in the network is prone to electric faults (e.g., generator faults, short circuit faults in the load). Faults in a node can potentially cascade, and cause a catastrophic power blackout in the entire network. Due to limited budget, a grid safety designer has to select only a subset of nodes where sensors and actuators can be installed, which can help minimize fault percolation in the network, by identifying and isolating (known as islanding) certain critical nodes.

The multi-agent systems described above can be modelled as MDPs, and often have exponentially large state and action spaces in practice (e.g., a large number of nodes in the network). In such cases, one can leverage the internal structure of such systems and model them as fMDPs. If one can only measure a subset of state variables using a limited number of sensors or can only influence transitions of a subset of state variables using a limited number of actuators, one is faced with the problem of selecting the optimal set of sensors (or actuators) that can result in better performance of such systems (fMDPs), which has not been well studied in the literature.

In this paper, we focus on two problems related to fMDPs: (i) selecting the best set of sensors at design-time (under some budget constraints) for a fMDP which can maximize the optimal expected infinite-horizon return for the resulting optimal policy and (ii) selecting the best set of actuators at design-time (under some budget constraints) for a fMDP which can maximize the optimal expected infinite-horizon return provided by the optimal policy.

Sequential sensor placement/selection has been studied in the context of MDPs and its variants like POMDPs. In [20], the authors consider active perception under a limited budget for POMDPs to selectively gather information at runtime. However, in our problem, we consider design-time sensor/actuator selection for fMDPs, where the sensor/actuator set is not allowed to dynamically change at runtime. A body of literature considers the problem of sensor scheduling for sequential decision-making tasks and model the task of sensor placement itself as a POMDP [21, 22]. However, we consider the problem of selecting the optimal set of sensors (or actuators) a priori (at design-time) for an fMDP, and not sequentially.

The problem of selecting an optimal subset of sensors has also been very well studied for linear systems. In [9] and [10], the authors study the sensor selection and sensor attack problems for Kalman filtering of linear dynamical systems, where the objective is to reduce the trace of the steady-state error covariance of the filter. The authors of [10] show that these problems are NP-Hard and there exists no polynomial-time constant-factor approximation algorithms for such class of problems. In [23], the authors propose balanced model reduction and greedy optimization technique to efficiently determine sensor and actuator selections that optimize observability and controllability for linear systems. In [24], the authors show that the mapping from subsets of possible actuator/sensor placements to any linear function of the associated controllability or observability Gramian is a modular set function. This strong property of the function allows efficient global optimization.

Many works have considered the problem of actuator selection for controlling and stabilizing large scale power grids. The authors of [25] consider the problem of optimal placement of High Voltage Direct Current (HVDC) links in a power system. HVDC links are actuators which are used to stabilize a power grid from oscillations. They propose a performance measure that can be used to rank different candidate actuators according to their behavior after a disturbance, which is computed using Linear Matrix Inequalities (LMIs). In [26], the authors propose an algorithm using Semi-Definite Programming (SDP) for placement of HVDC links, which can optimize the LMI-based performance measure proposed in [25]. The authors of [26] state that this technique can be applied to other actuator selection problems, such as Flexible AC Transmission (FACTS) controllers and Power System Stabilizers (PSS). However, these techniques use a linearized state-space model of the power system around the current operating point, whereas in this paper, we consider fMDP models which may not necessarily have a linear structure.

For combinatorially-hard sensor or actuator selection problems, various approximation algorithms have proven to produce near-optimal solutions [27][28]. In [29], the authors leverage the adaptive submodularity property of the sensor area coverage metric to learn an adaptive greedy policy for sequential sensor placement with provable performance guarantees. However, we consider the design-time sensor selection problem for fMDPs. The authors of [30] exploit the weak-submodularity property of the objective function and provide near-optimal greedy algorithms for sensor selection. In contrast to these results, we present worst-case in-approximability results and demonstrate how greedy algorithms for both sensor and actuator selection in fMDPs can perform arbitrarily poorly, and that the value function of a fMDP is not generally submodular in the set of sensors (or actuators) selected.

Our contributions are as follows. Firstly, we show that the problem of selecting an optimal subset of sensors at design-time for a general class of factored MDPs is NP-hard, and there is no polynomial time algorithm that can approximate this problem to within a factor of $n^{1-\epsilon}$ of the optimal solution, for any $\epsilon>0$, even when one has access to an oracle that can compute the optimal policy for any given instance (which itself is known to be PSPACE-hard [31]). Second, we show that the same inapproximability results hold for the problem of selecting an optimal subset of actuators at design-time for a general class of factored MDPs. Our inapproximability results directly imply that greedy algorithms cannot provide constant-factor guarantees for our problems, and that the value function of the fMDP is not submodular (in general) in the set of sensors (resp. actuators) selected. Our third contribution is to explicitly show how greedy algorithms can provide arbitrarily poor performance for fMDP-SS (resp. fMDP-AS) problems. Finally, through empirical results, we show that the greedy algorithm may provide near-optimal solutions for many instances in practice, despite the inapproximability results.

We considered the problem of optimal sensor selection for Mixed-Observable MDPs (MOMDPs) in the conference paper [32]. We proved its NP-hardness and provided insights into the lack of submodularity of the value function. However, in this paper, we present stronger inapproximability results for both sensor and actuator selection for a general class of factored MDPs, of which MOMDPs are a special case.

Consider the scenario where there are no sensors installed initially, and the agent does not have observability of the state variables $s_{i}$ of the f-MDP. Instead, the agent has to select a subset of sensors to install. Define $\Omega=\{\omega_{i}\mid i=1,2,\ldots,n\}$ to be a collection of sensors, where the sensor $\omega_{i}$ measures exactly the state variable $s_{i}$. Let $c_{i}\in\mathbb{R}_{\geq 0}$ be the cost we pay to measure state $s_{i}$ by placing the sensor $\omega_{i}$, and let $C\in\mathbb{R}_{>0}$ denote the total budget for the sensor placement. Let $\Gamma\subseteq\Omega$ be the subset of sensors selected (at design-time) that generates observations $y_{\Gamma}(t)=\{s_{i}(t)\mid\omega_{i}\in\Gamma\}$. At time $t$, the agent has the following information: observations $Y^{\Gamma}_{t}=\{y_{\Gamma}(0),y_{\Gamma}(1),y_{\Gamma}(2),\cdot\cdot\cdot,y_{\Gamma}(t)\}$, joint actions $A_{t}=\{a(0),a(1),a(2),\cdot\cdot\cdot,a(t-1)\}$ and rewards $R_{t}=\{r(0),r(1),r(2),\cdot\cdot\cdot,r(t-1)\}$. Since the agent does not have complete observability, it maintains a belief over the states of the fMDP, $b\in\mathcal{B}$, where $\mathcal{B}$ is the belief space, which is the set of probability distributions over the states in $\mathcal{S}$.

In this case, the expected reward is belief-based, denoted as $\rho(b,a)$, and is given by $\rho(b,a)=\sum_{s}b(s)r(s,a)$, where $b(s)$ is the belief over the state $s$, $a$ is the action and $r(s,a)$ is the reward obtained for taking action $a$ in the state $s$. For any given choice of sensors, the agent seeks to maximize the expected infinite-horizon reward, given the initial belief $b_{0}$, by finding an optimal policy satisfying $\pi^{*}=$ $\arg\max_{\pi\in\Pi}V^{\pi}\left(b_{0}\right)$ with $V^{\pi}\left(b_{0}\right)=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}\rho_{t}\mid b_{0},\pi\right]$, where $\rho_{t}$ is the reward obtained at time $t$. The policy $\pi$ belongs to a class of policies $\Pi$ which map the history of observations, actions, and rewards to the next action. The value function $V^{\pi}_{n}(b)$ under the policy $\pi$ can be computed using the value iteration algorithm with $V^{\pi}_{0}(b)=0$, and $V^{\pi}(b)=\lim_{n\rightarrow\infty}V^{\pi}_{n}(b)$ (as in [8]).

Let $\mathcal{H}_{t}=\{Y^{\Gamma}_{t},A_{t},R_{t}\}$ denote the set containing all the information the agent has until time $t$. Define $\Pi_{\Gamma}=\{\pi_{\Gamma}\mid\pi_{\Gamma}:\mathcal{H}_{t}\rightarrow\mathcal{A}\}$ to be a class of history-dependent policies that map from a set containing all the information known to the agent until time $t$ to the action $a_{t}$ which the agent takes at time $t$. The goal is to find an optimal subset of sensors $\Gamma^{*}\subseteq\Omega$, under the budget constraint, that can maximize the expected value $V^{*}_{\Gamma}$ of the infinite-horizon discounted return obtained by the agent under the optimal policy for the resulting POMDP. Specifically, we aim to solve the optimization problem:

We now define the decision version for the above optimization problem as the Factored Markov Decision Process Sensor Selection Problem (fMDP-SS Problem).

Consider the scenario where there are no actuators installed initially, and the agent cannot influence the transitions of state variables $s_{i}$ of the fMDP. However, the agent has complete observability of the state variables $s_{i}$. In this case, the agent has to select a subset of actuators to install. Define $\Phi=\{\phi_{i}\mid i=1,2,\ldots,n\}$ to be a collection of actuators, where the actuator $\phi_{i}$ provides a set of actions $\mathcal{A}_{i}$, and action $a_{i}\in\mathcal{A}_{i}$ can influence the state transition of $s_{i}$. Let $k_{i}\in\mathbb{R}_{\geq 0}$ be the cost we pay to install the actuator $\phi_{i}$, and let $K\in\mathbb{R}_{>0}$ denote the total budget for the actuator placement. Let $\Upsilon\subseteq\Phi$ be the subset of actuators selected (at design-time).

Let $\mathcal{A}_{\Upsilon}=\Pi_{\phi_{i}\in\Upsilon}\mathcal{A}_{i}=\{\{{a}_{i}\}|\phi_{i}\in\Upsilon\}$ denote the joint action space available to the agent generated by selecting the actuator set $\Upsilon$. If an actuator is not selected, then the agent has a default action $a_{d}$, and by taking this action, the agent stays in its current state with probability 1. As the agent has complete observability of the state, the rewards depend on the joint state-action pairs, i.e., $r(s,\bar{a})$ is the reward obtained by the agent for taking the joint action $\bar{a}$ in state $s$. Define $\Pi_{\Upsilon}=\{\pi_{\Upsilon}\mid\pi_{\Upsilon}:\mathcal{H}_{t}\rightarrow\mathcal{A}_{\Upsilon}\}$ to be a class of history-dependent policies that map from a set containing all the information $\mathcal{H}_{t}$ known to the agent until time $t$ to action, $\bar{a}_{t}\in\mathcal{A}_{\Upsilon}$ which the agent takes at time $t$.

The goal of the agent is to choose the best actuator set $\Upsilon^{*}\subseteq\Phi$ which can maximize the expected infinite-horizon discounted return under the optimal policy of the resulting MDP. The expected infinite-horizon discounted return is computed for the optimal policy satisfying $\pi^{*}=\arg\max_{\pi\in\Pi_{\Upsilon}}V^{\pi}$ with $V^{\pi}=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}r_{t}\mid\pi\right]$, where $r_{t}$ is the reward obtained at time $t$. Let $V_{\Upsilon}^{*}$ denote the expected infinite-horizon discounted return under the optimal policy for the actuator set $\Upsilon$. We aim to solve the optimization problem:

We now define the decision version of the above optimization problem as the Factored Markov Decision Process Actuator Selection Problem (fMDP-AS Problem).

We first review the following fundamental concepts from complexity theory [33].

The above definition indicates that if one had a polynomial time algorithm for an NP-complete (or NP-hard) problem, then one could solve every problem in NP in polynomial time. Specifically, suppose we had a polynomial-time algorithm to solve an NP-hard problem $\mathcal{P}_{1}$. Then, given any problem $\mathcal{P}_{2}$ in $\mathrm{NP}$, one could first reduce any instance of $\mathcal{P}_{2}$ to an instance of $\mathcal{P}_{1}$ in polynomial time (such that the answer to the constructed instance of $\mathcal{P}_{1}$ provides the answer to the given instance of $\mathcal{P}_{2}$), and then use the polynomial-time algorithm for $\mathcal{P}_{1}$ to obtain the answer to $\mathcal{P}_{2}$.

The above discussion also reveals that to show that a given problem $\mathcal{P}_{1}$ is NP-hard, one simply needs to show that any instance of some other NP-hard (or NP-complete) problem $\mathcal{P}_{2}$ can be reduced to an instance of $\mathcal{P}_{1}$ in polynomial time.

For NP-hard optimization problems, polynomial-time approximation algorithms are of particular interest. A constant factor approximation algorithm is defined as follows.

In [32], we showed that the problem of selecting sensors for MOMDPs (which are a special class of POMDPs and fMDPs) is NP-hard. In this paper, we show a stronger result that there is no polynomial-time algorithm that can approximate the fMDP-SS (resp., fMDP-AS) Problem to within a factor of $n^{1-\epsilon}$ for any $\epsilon>0$, even when all the sensors (resp. actuators) have the same selection cost. Specifically, we consider a well-known NP-complete problem, and show how to reduce it to certain instances of fMDP-SS (resp., fMDP-AS) in polynomial time such that hypothetical polynomial-time approximation algorithms for the latter problems can be used to solve the known NP-complete problem. In particular, inspired by the reductions from Set Cover problem to the influence maximization problems in social networks presented in [34] and [35], we use the Set Cover problem and provide polynomial-time reductions to the fMDP-SS and fMDP-AS problems in order to establish our inapproximability results.

The Set Cover Problem is a classical question in combinatorics and complexity theory. Given a set of $n$ elements $\mathcal{U}=\{u_{1},u_{2},\ldots,u_{n}\}$ called the universe and a collection of $m$ subsets $\mathbb{S}=\{S_{1},S_{2},\ldots,S_{m}|S_{i}\subseteq\mathcal{U}\}$, where each subset $S_{i}$ is associated with a cost $c(S_{i})\in\mathbb{R}_{\geq 0}$ and the union of these subsets equals the universe $\mathcal{U}=S_{1}\cup S_{2}\cup\cdots\cup S_{m}$, the set cover problem is to identify the collection of subsets in $\mathbb{S}$ with minimum cost, whose union contains all the elements of the universe. Let $\mathbb{S}_{c}$ denote the collection of subsets selected. We wish to solve the following optimization problem:

We will now define the decision version of this problem, under uniform set selection costs, as the SetCover Problem.

The SetCover Problem is NP-Complete [36].

In this section, we present the inapproximability results for fMDP sensor selection by reducing an instance of the SetCover problem to the fMDP-SS problem. We first present a preliminary lemma, which we will use to characterize the complexity of fMDP-SS.

Example 1: Consider an MDP $\bar{\mathcal{M}}:=\{\mathcal{S},\mathcal{A},\mathcal{T},\mathcal{R},\gamma,b_{0}\}$ with state space $\mathcal{S}=\{A,B,C,D\}$, actions $\mathcal{A}=\{0,1,2\}$, transition function $\mathcal{T}:\Biggl{\{}\mathcal{T}_{0}=\begin{bmatrix}0.5&0.5&0&0\\ 0.5&0.5&0&0\\ 0&0&1&0\\ 0&0&0&1\end{bmatrix};\mathcal{T}_{1}=\begin{bmatrix}0&0&1&0\\ 0&0&0&1\\ 0&0&1&0\\ 0&0&0&1\end{bmatrix};\mathcal{T}_{2}=\begin{bmatrix}0&0&0&1\\ 0&0&1&0\\ 0&0&1&0\\ 0&0&0&1\end{bmatrix}\Biggr{\}}$ for $a=0$, $a=1$ and $a=2$, respectively, reward function $\mathcal{R}(s,a)=(r(A,0)=0,r(B,0)=0,r(A,1)=R,r(B,1)=-(1+\delta)R,r(A,2)=-(1+\delta)R,r(B,2)=R,r(C,\cdot)=R,r(D,\cdot)=-(1+\delta)R)$ with $R,\delta>0$, discount factor $\gamma\in(0,1)$ and initial distribution $b_{0}=[0.5,0.5,0,0]$. Fig. 3 describes state-action transitions along with their probabilities. The state space of this MDP corresponds to only one state variable $s$ and the agent can measure this by selecting a noiseless sensor $\omega=s$. The initial state of the MDP at $t=0$ is either $s(0)=A$ or $s(0)=B$, with equal probability.

We are now in place to provide the following result characterizing the complexity of the fMDP-SS problem.

In this section, we present the inapproximability results for fMDP actuator selection by reducing an instance of the SetCover problem to the fMDP-AS problem. We first present a preliminary lemma, which we will use to characterize the complexity of fMDP-AS.

Example 2: Consider an MDP given by $\tilde{\mathcal{M}}:=\{\mathcal{S},\mathcal{A},\mathcal{T},\mathcal{R},\gamma\}$. The state space is given by $\mathcal{S}=\{A,B,C,D\}$. If there is no actuator, the agent can only take the default action $a=0$, i.e., the action space is $\mathcal{A}=\{0\}$ and if there is an actuator installed, then the agent can take one of three actions 0,1, or 2, i.e., the action space is $\mathcal{A}=\{0,1,2\}$. The transition function and reward function are as defined in Example 1. Note that this MDP is similar to the MDP defined in Example 1, but only differs in its action space.

We have the following result characterizing the complexity of the fMDP-AS problem.

Consider the following instance of the fMDP-SS problem.

Example 3: An fMDP $\mathcal{M}=\{\mathcal{S},\mathcal{A},\mathcal{T},\mathcal{R},\gamma,b_{0}\}$ consists of 4 MDPs $\{\mathcal{M}_{1},\mathcal{M}_{2},\mathcal{M}_{3},\mathcal{M}_{4}\}$. Each of these are the single-state variable MDPs as defined in Example 1, except for their reward functions. We will now explicitly define the elements on the tuple $\mathcal{M}$
State Space $\mathcal{S}$: The state space of the fMDP $\mathcal{M}$ is the product of the state-spaces of the MDPs $\mathcal{M}_{i}$, i.e., $\mathcal{S}=\mathcal{S}_{1}\times\mathcal{S}_{2}\times\mathcal{S}_{3}\times\mathcal{S}_{4}$. The state of fMDP consists of 4 independently evolving state variables and is given by $s=[s_{1},s_{2},s_{3},s_{4}]$, where each state variable $s_{i}$ is as defined in Example 1. We encode the states into a binary representation over $4$ bits as follows: $(A=1000,B=0100,C=0010,D=0001)$;
Action Space $\mathcal{A}$: The action space of the fMDP $\mathcal{M}$ is the product of the action-spaces of the MDPs $\mathcal{M}_{i}$, i.e., $\mathcal{A}=\mathcal{A}_{1}\times\mathcal{A}_{2}\times\mathcal{A}_{3}\times\mathcal{A}_{4}$;
Transition Function $\mathcal{T}$: The probabilistic transition function $\mathcal{T}$ of the fMDP $\mathcal{M}$ is a collection of the individual transition functions $\{\mathcal{T}_{1},\mathcal{T}_{2},\mathcal{T}_{3},\mathcal{T}_{4}\}$ for $s_{1},s_{2},s_{3},s_{4}$ respectively, where each $\mathcal{T}_{i}$ is as defined in Example 1;
Reward Function $\mathcal{R}$: The reward functions of $\{\mathcal{M}_{1},\mathcal{M}_{2},\mathcal{M}_{3}\}$ are independent of each other and are as defined in Example 1 with $R=R_{1}$ for $\mathcal{M}_{1}$, $R=R_{2}$ for $\mathcal{M}_{2}$ and $R=R_{3}$ for $\mathcal{M}_{3}$ respectively. The reward function of $\mathcal{M}_{4}$ depends on the states $s_{2}$ and $s_{3}$ and is defined as:

Let $R_{4}>R_{1}>R_{2}>R_{3}>0$ and $R_{1}=R_{2}+\epsilon$ for an arbitrarily small $\epsilon$. Let the value of $\delta$ in the individual reward functions for each MDP be such that $\delta>R_{4}/R_{3}-1$. The overall reward function for the fMDP $\mathcal{M}$ is given by

Discount Factor $\gamma$: Let the discount factors of all $\mathcal{M}_{i}$ be equal to each other and that of $\mathcal{M}$, i.e., $\gamma_{1}=\gamma_{2}=\gamma_{3}=\gamma_{4}=\gamma$.

Let $\Omega=\{\omega_{1},\omega_{2},\omega_{3},\omega_{4}\}$ be the set of sensors which can measure states, $s_{1},s_{2},s_{3},s_{4}$ respectively. Let the cost of the sensors be $\mathcal{C}=(c_{1}=1,c_{2}=1,c_{3}=1,c_{4}=3)$ and the sensor budget be $C=2$. Assume uniform initial beliefs ($b_{0}$) for all the fMDPs $\mathcal{M}_{i}$ and $\mathcal{M}$. Since $c_{4}>C$, we apply the greedy algorithm described in Algorithm 1 to this instance of the fMDP-SS with $X=\Omega\setminus\{\omega_{4}\}$ and $M=C$. Let the output set $Y=\Gamma$. For any such instance of fMDP-SS, define $r_{gre}(\Gamma)=\frac{V_{\Gamma}^{gre}}{V_{\Gamma}^{opt}}$, where $V_{\Gamma}^{gre}$ and $V_{\Gamma}^{opt}$ are the infinite-horizon expected return obtained by the greedy algorithm and the optimal infinite-horizon expected return, respectively. Define $h=R_{4}/R_{2}$.

Remark 1: Proposition 1 means that if we make $R_{4}$ arbitrarily larger than $R_{2}$, and $R_{1}$ slightly larger than $R_{2}$, the expected return obtained by the greedy algorithm can get arbitrarily small compared to the expected value obtained by the optimal selection of sensors. This is because greedy picks sensors $\omega_{1}$ and $\omega_{2}$ due to its myopic behavior. It does not consider the fact that, in spite of $R_{3}$ being the least reward, selecting $\omega_{3}$ in combination with $\omega_{2}$ would eventually lead to the highest reward $R_{4}$. An expected consequence of the arbitrarily poor performance of the greedy algorithm is that the optimal value function of the fMDP is not necessarily submodular in the set of sensors selected.

Consider the following instance of fMDP-AS.

Example 4: An fMDP $\mathcal{M}=\{\mathcal{S},\mathcal{A},\mathcal{T},\mathcal{R},\gamma\}$ consists of 4 MDPs $\{\mathcal{M}_{1},\mathcal{M}_{2},\mathcal{M}_{3},\mathcal{M}_{4}\}$. Each of these are the single-state variable MDPs as defined in Example 2, except for their reward functions. We will now explicitly define the elements on the tuple $\mathcal{M}$.
State Space $\mathcal{S}$: The state space of the fMDP $\mathcal{M}$ is the same as that in Example 3;
Action Space $\mathcal{A}$: The action space of the fMDP $\mathcal{M}$ is the product of the action-spaces of the MDPs $\mathcal{M}_{i}$, i.e., $\mathcal{A}=\mathcal{A}_{1}\times\mathcal{A}_{2}\times\mathcal{A}_{3}\times\mathcal{A}_{4}$. The action spaces $\mathcal{A}_{i}$ depend on the placement of actuators, as detailed in Example 2;
Transition Function $\mathcal{T}$: The probabilistic transition function $\mathcal{T}$ of the fMDP $\mathcal{M}$ is a collection of the individual transition functions $\{\mathcal{T}_{1},\mathcal{T}_{2},\mathcal{T}_{3},\mathcal{T}_{4}\}$ for $s_{1},s_{2},s_{3},s_{4}$ respectively, where each $\mathcal{T}_{i}$ is as defined in Example 2;
Reward Function $\mathcal{R}$: The reward function of the fMDP $\mathcal{M}$ is the same as that in Example 3 (see Equation 7);

Discount Factor $\gamma$: Let the discount factors of $\mathcal{M}_{i}$ be equal to the discount factor of $\mathcal{M}$ i.e., $\gamma_{1}=\gamma_{2}=\gamma_{3}=\gamma_{4}=\gamma$.

Let $\Phi=\{\phi_{1},\phi_{2},\phi_{3},\phi_{4}\}$ be the set of actuators with costs $\mathcal{K}=(k_{1}=1,k_{2}=1,k_{3}=1,k_{4}=3)$, that can influence the transitions of states, $s_{1},s_{2},s_{3},s_{4}$ respectively. Let the actuator selection budget be $K=2$. Since $k_{4}>K$, we apply the greedy algorithm described in Algorithm 1 to this instance of the fMDP-AS with $X=\Phi\setminus\{\phi_{4}\}$ and $M=K$. Let the output set $Y=\Upsilon$. For any such instance of fMDP-AS, define $r_{gre}(\Upsilon)=\frac{V_{\Upsilon}^{gre}}{V_{\Upsilon}^{opt}}$, where $V_{\Upsilon}^{gre}$ and $V_{\Upsilon}^{opt}$ are the infinite-horizon expected return obtained by the greedy algorithm and the optimal infinite-horizon expected return respectively. Define $h=R_{4}/R_{2}$.

Remark 2: Proposition 2 means that if we make $R_{4}$ arbitrarily larger than $R_{2}$, and $R_{1}$ almost equal to $R_{2}$, the expected return obtained by greedy can get arbitrarily small compared to the expected value obtained by optimal selection of actuators. This is because greedy picks actuators $\phi_{1}$ and $\phi_{2}$ due to its myopic behavior. It does not consider the fact that, in spite of $R_{3}$ being the least reward, selecting $\phi_{3}$ would eventually lead to the highest reward $R_{4}$. An expected consequence of the arbitrarily poor performance of the greedy algorithm is that the optimal value function of the fMDP is not necessarily submodular in the set of actuators selected.

We consider the problem of selecting an optimal subset of actuators which can minimize fault percolation in an electric network, which we will refer to as the Actuator Selection in Electric Networks (ASEN) Problem. Consider a distributed micro-grid network (e.g., see Figure 2) represented by a graph $G=(V,E)$, where each node $i\in V$ represents a micro-grid system and each edge $e_{ij}\in E$ is a link between nodes (or micro-grids) $i$ and $j$ in the electric network. The state of each micro-grid system (or node) $i\in(1,\ldots,|V|)$ is represented by the variable $s_{i}\in\{\texttt{healthy},\texttt{faulty}\}$. If a particular node $i$ is faulty, a neighboring node $j\in\mathcal{N}_{i}$, where $\mathcal{N}_{i}$ represents the non-inclusive neighborhood of the node $i$, will become faulty with a certain probability $p_{ji}$. This is known as the Independent-Cascade diffusion process in networks, and has been well-studied in the network science literature. Given an initial set of faulty nodes $S\subset V$, as the diffusion/spread process unfolds, more nodes in the network will become faulty. In large-scale distributed micro-grid networks, a central grid controller can perform active islanding of micro-grids (or nodes) using islanding switches (or actuators), in order to prevent percolation of faults in the network. Given that only a limited number of islanding switches can be installed, the goal is to determine the optimal placement locations (nodes) in the distributed micro-grid, which can minimize the fault percolation. This problem is similar to the problem of minimizing influence of rumors in social networks studied in [39]. Similar to [39], we wish to identify a blocker set, i.e., a set of nodes which can be disconnected (islanded) from the network, which can minimize the total number of faulty nodes.

Given a budget $K$, the problem of selecting the optimal subset of $K$ nodes on which actuators, i.e., islanding switches, can be installed, which can maximize the number of healthy nodes in the network (i.e., minimize the spread of faults) is an instance of the fMDP-AS problem presented in this paper. Each node $i\in(1,\ldots,|V|)$ corresponds to an MDP with state $s_{i}\in\{\texttt{healthy},\texttt{faulty}\}$. The state transition of a node depends on the state transitions of its neighboring nodes and is governed by the influence probabilities $p_{ji}$, for each pair of nodes $(j,i)$. Thus, the overall state of the fMDP can be factored into $n=|V|$ state variables. If a node is in healthy state, it receives a reward of $+1$, and if it is in faulty state, it receives a reward of $0$. The overall reward of the fMDP at any time step is the sum of the rewards of each node. If an actuator is installed on a particular node $i\in V$, it can perform active islanding to disconnect from the network, and this is denoted by the factored action space $\mathcal{A}_{i}=\{\texttt{island},\texttt{na}\}$. In case of no actuator on a node $i\in V$, it has a default action (do nothing), and this is denoted by the factored action space $\mathcal{A}_{i}=\{\texttt{na}\}$. The action space of the fMDP is the product of the action spaces of the MDPs corresponding to each node.

We set the discount factor $\gamma=0.95$ and $p_{ji}=0.3$ for all node pairs $(i,j)\in V\times V$, and compute the infinite-horizon discounted return for the fMDP (electric network) as the fault percolation process unfolds over the network, according to the independent cascade model. We use a greedy influence maximization (IM) algorithm under the independent cascade model to identify the initial set $S$ of faulty nodes with maximum influence for fault propagation. We consider two types of random graph models to generate instances of the electric network: (i) Erdős-Rényi (ER) random graph denoted by $G(n,p)$, where $n$ represents the number of nodes and $p$ represents the edge-probability and (ii) Barabási-Albert (BA) random graph denoted by $G(n)$, where $n$ represents the number of nodes. We perform the following experiments to evaluate the greedy algorithm and plot the performance of greedy with respect to optimal (computed using brute-force search) along with the performance of random selection with respect to optimal in Figure 5.