  In many applications of Reinforcement Learning (RL), it is critically
important that the algorithm performs safely, such that instantaneous hard
constraints are satisfied at each step, and unsafe states and actions are
avoided. However, existing algorithms for ''safe'' RL are often designed under
constraints that either require expected cumulative costs to be bounded or
assume all states are safe. Thus, such algorithms could violate instantaneous
hard constraints and traverse unsafe states (and actions) in practice.
Therefore, in this paper, we develop the first near-optimal safe RL algorithm
for episodic Markov Decision Processes with unsafe states and actions under
instantaneous hard constraints and the linear mixture model. It not only
achieves a regret $\tilde{O}(\frac{d H^3 \sqrt{dK}}{\Delta_c})$ that tightly
matches the state-of-the-art regret in the setting with only unsafe actions and
nearly matches that in the unconstrained setting, but is also safe at each
step, where $d$ is the feature-mapping dimension, $K$ is the number of
episodes, $H$ is the number of steps in each episode, and $\Delta_c$ is a
safety-related parameter. We also provide a lower bound
$\tilde{\Omega}(\max\{dH \sqrt{K}, \frac{H}{\Delta_c^2}\})$, which indicates
that the dependency on $\Delta_c$ is necessary. Further, both our algorithm
design and regret analysis involve several novel ideas, which may be of
independent interest.
