  This work studies a multi-agent Markov decision process (MDP) that can
undergo agent dropout and the computation of policies for the post-dropout
system based on control and sampling of the pre-dropout system. The
controller's objective is to find an optimal policy that maximizes the value of
the expected system given a priori knowledge of the agents' dropout
probabilities. Finding an optimal policy for any specific dropout realization
is a special case of this problem. For MDPs with a certain transition
independence and reward separability structure, we assume that removing agents
from the system forms a new MDP comprised of the remaining agents with new
state and action spaces, transition dynamics that marginalize the removed
agents, and rewards that are independent of the removed agents. We first show
that under these assumptions, the value of the expected post-dropout system can
be represented by a single MDP; this "robust MDP" eliminates the need to
evaluate all $2^N$ realizations of the system, where $N$ denotes the number of
agents. More significantly, in a model-free context, it is shown that the
robust MDP value can be estimated with samples generated by the pre-dropout
system, meaning that robust policies can be found before dropout occurs. This
fact is used to propose a policy importance sampling (IS) routine that performs
policy evaluation for dropout scenarios while controlling the existing system
with good pre-dropout policies. The policy IS routine produces value estimates
for both the robust MDP and specific post-dropout system realizations and is
justified with exponential confidence bounds. Finally, the utility of this
approach is verified in simulation, showing how structural properties of agent
dropout can help a controller find good post-dropout policies before dropout
occurs.
