Location-based services (LBSs) have become widely popular. Despite their utility, these services raise concerns for privacy since they require sharing location information with untrusted third parties. In this work, we study privacy-utility trade-off in location sharing mechanisms. Existing approaches are mainly focused on privacy of sharing a single location or myopic location trace privacy; neither of them taking into account the temporal correlations between the past and current locations. Although these methods preserve the privacy for the current time, they may leak significant amount of information at the trace level as the adversary can exploit temporal correlations in a trace. We propose an information theoretically optimal privacy preserving location release mechanism that takes temporal correlations into account. We measure the privacy leakage by the mutual information between the user's true and released location traces. To tackle the history-dependent mutual information minimization, we reformulate the problem as a Markov decision process (MDP), and solve it using asynchronous actor-critic deep reinforcement learning (RL).