  We study risk-sensitive reinforcement learning in episodic Markov decision
processes with unknown transition kernels, where the goal is to optimize the
total reward under the risk measure of exponential utility. We propose two
provably efficient model-free algorithms, Risk-Sensitive Value Iteration (RSVI)
and Risk-Sensitive Q-learning (RSQ). These algorithms implement a form of
risk-sensitive optimism in the face of uncertainty, which adapts to both
risk-seeking and risk-averse modes of exploration. We prove that RSVI attains
an $\tilde{O}\big(\lambda(|\beta| H^2) \cdot \sqrt{H^{3} S^{2}AT} \big)$
regret, while RSQ attains an $\tilde{O}\big(\lambda(|\beta| H^2) \cdot
\sqrt{H^{4} SAT} \big)$ regret, where $\lambda(u) = (e^{3u}-1)/u$ for $u>0$. In
the above, $\beta$ is the risk parameter of the exponential utility function,
$S$ the number of states, $A$ the number of actions, $T$ the total number of
timesteps, and $H$ the episode length. On the flip side, we establish a regret
lower bound showing that the exponential dependence on $|\beta|$ and $H$ is
unavoidable for any algorithm with an $\tilde{O}(\sqrt{T})$ regret (even when
the risk objective is on the same scale as the original reward), thus
certifying the near-optimality of the proposed algorithms. Our results
demonstrate that incorporating risk awareness into reinforcement learning
necessitates an exponential cost in $|\beta|$ and $H$, which quantifies the
fundamental tradeoff between risk sensitivity (related to aleatoric
uncertainty) and sample efficiency (related to epistemic uncertainty). To the
best of our knowledge, this is the first regret analysis of risk-sensitive
reinforcement learning with the exponential utility.
