  We study the synthesis of a policy in a Markov decision process (MDP)
following which an agent reaches a target state in the MDP while minimizing its
total discounted cost. The problem combines a reachability criterion with a
discounted cost criterion and naturally expresses the completion of a task with
probabilistic guarantees and optimal transient performance. We first establish
that an optimal policy for the considered formulation may not exist but that
there always exists a near-optimal stationary policy. We additionally provide a
necessary and sufficient condition for the existence of an optimal policy. We
then restrict our attention to stationary deterministic policies and show that
the decision problem associated with the synthesis of an optimal stationary
deterministic policy is NP-complete. Finally, we provide an exact algorithm
based on mixed-integer linear programming and propose an efficient
approximation algorithm based on linear programming for the synthesis of an
optimal stationary deterministic policy.
