  Safety in reinforcement learning has become increasingly important in recent
years. Yet, existing solutions either fail to strictly avoid choosing unsafe
actions, which may lead to catastrophic results in safety-critical systems, or
fail to provide regret guarantees for settings where safety constraints need to
be learned. In this paper, we address both problems by first modeling safety as
an unknown linear cost function of states and actions, which must always fall
below a certain threshold. We then present algorithms, termed SLUCB-QVI and
RSLUCB-QVI, for episodic Markov decision processes (MDPs) with linear function
approximation. We show that SLUCB-QVI and RSLUCB-QVI, while with \emph{no
safety violation}, achieve a
$\tilde{\mathcal{O}}\left(\kappa\sqrt{d^3H^3T}\right)$ regret, nearly matching
that of state-of-the-art unsafe algorithms, where $H$ is the duration of each
episode, $d$ is the dimension of the feature mapping, $\kappa$ is a constant
characterizing the safety constraints, and $T$ is the total number of action
plays. We further present numerical simulations that corroborate our
theoretical findings.
