  We present a model-free reinforcement learning algorithm to find an optimal
policy for a finite-horizon Markov decision process while guaranteeing a
desired lower bound on the probability of satisfying a signal temporal logic
(STL) specification. We propose a method to effectively augment the MDP state
space to capture the required state history and express the STL objective as a
reachability objective. The planning problem can then be formulated as a
finite-horizon constrained Markov decision process (CMDP). For a general finite
horizon CMDP problem with unknown transition probability, we develop a
reinforcement learning scheme that can leverage any model-free RL algorithm to
provide an approximately optimal policy out of the general space of
non-stationary randomized policies. We illustrate the effectiveness of our
approach in the context of robotic motion planning for complex missions under
uncertainty and performance objectives.
