  We propose an automata-theoretic approach for reinforcement learning (RL)
under complex spatio-temporal constraints with time windows. The problem is
formulated using a Markov decision process under a bounded temporal logic
constraint. Different from existing RL methods that can eventually learn
optimal policies satisfying such constraints, our proposed approach enforces a
desired probability of constraint satisfaction throughout learning. This is
achieved by translating the bounded temporal logic constraint into a total
automaton and avoiding "unsafe" actions based on the available prior
information regarding the transition probabilities, i.e., a pair of upper and
lower bounds for each transition probability. We provide theoretical guarantees
on the resulting probability of constraint satisfaction. We also provide
numerical results in a scenario where a robot explores the environment to
discover high-reward regions while fulfilling some periodic pick-up and
delivery tasks that are encoded as temporal logic constraints.
