An important facet of reinforcement learning (RL) has to do with how theagent goes about exploring the environment. Traditional exploration strategiestypically focus on efficiency and ignore safety. However, for practicalapplications, ensuring safety of the agent during exploration is crucial sinceperforming an unsafe action or reaching an unsafe state could result inirreversible damage to the agent. The main challenge of safe exploration isthat characterizing the unsafe states and actions is difficult for largecontinuous state or action spaces and unknown environments. In this paper, wepropose a novel approach to incorporate estimations of safety to guideexploration and policy search in deep reinforcement learning. By using a costfunction to capture trajectory-based safety, our key idea is to formulate thestate-action value function of this safety cost as a candidate Lyapunovfunction and extend control-theoretic results to approximate its derivativeusing online Gaussian Process (GP) estimation. We show how to use thesestatistical models to guide the agent in unknown environments to obtainhigh-performance control policies with provable stability certificates.