  We investigate the problem of optimal control synthesis for Markov Decision
Processes (MDPs), addressing both qualitative and quantitative objectives.
Specifically, we require the system to fulfill a qualitative surveillance task
in the sense that a specific region of interest can be visited infinitely often
with probability one. Furthermore, to quantify the performance of the system,
we consider the concept of efficiency, which is defined as the ratio between
rewards and costs. This measure is more general than the standard long-run
average reward metric as it aims to maximize the reward obtained per unit cost.
Our objective is to synthesize a control policy that ensures the surveillance
task while maximizes the efficiency. We provide an effective approach to
synthesize a stationary control policy achieving $\epsilon$-optimality by
integrating state classifications of MDPs and perturbation analysis in a novel
manner. Our results generalize existing works on efficiency-optimal control
synthesis for MDP by incorporating qualitative surveillance tasks. A robot
motion planning case study is provided to illustrate the proposed algorithm.
