# Long-Term Visitation Value for Deep Exploration in Sparse-Reward Reinforcement Learning
## 2 Preliminaries
### Reinforcement Learning and Markov Decision Processes  
We consider RL in an environment governed by a Markov Decision Process (MDP). An MDP is described by the tuple \(\langle\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\mu_{1}\rangle\), where \(\mathcal{S}\) is the state space, \(\mathcal{A}\) is the action space, \(\mathcal{P}(s^{\prime}|s,a)\) defines a Markovian transition probability density between the current \(s\) and the next state \(s^{\prime}\) under action \(a\), \(\mathcal{R}(s,a)\) is the reward function, and \(\mu_{1}\) is initial distribution for state \(s_{1}\). The state and action spaces could be finite, i.e., \(|\mathcal{S}|=d_{s}\) and \(|\mathcal{A}|=d_{s}\), or continuous, i.e., \(\mathcal{S}\subseteq\mathbb{R}^{d_{s}}\) and \(\mathcal{A}\subseteq\mathbb{R}^{d_{s}}\). The former case is often called _tabular_ MDP, as a table can be used to store and query all state-action pairs if the size of the state-action space is not too large. If the model of the environment is known, these MDPs can be solved exactly with dynamic programming. The latter, instead, requires function approximation, and algorithms typically guarantee convergence to local optima. In the remainder of the paper, we will consider only tabular MDPs and model-free RL, i.e., the model of the environment is neither known nor learned. Given an MDP, we want to learn to act. Formally, we want to find a _policy_\(\pi(a|s)\) to take an appropriate action \(a\) when the agent is in state \(s\). By following such a policy starting at initial state \(s_{1}\), we obtain a sequence of states, actions and rewards \((s_{t},a_{t},r_{t})_{t=1\ldots H}\), where \(r_{t}=\mathcal{R}(s_{t},a_{t})\) is the reward at time \(t\), and \(H\) is the total timesteps also called _horizon_, which can possibly be infinite. We refer to such sequences as _trajectories_ or _episodes_. Our goal is thus to find a policy that maximizes the expected return  
\[Q^{*}(s,a) :=\max_{\pi}\ \ \mathbb{E}_{\mu\pi(s)\pi(a|s)}[Q^{\pi}(s,a)], \tag{1}\] \[\text{where}\ \ Q^{\pi}(s_{t},a_{t}) :=\mathbb{E}_{\prod_{i=t}^{H}\pi(a_{i+1}|s_{i+1})\mathcal{P}(s_{ i+1}|s_{i},a_{i})}\!\!\left[\sum_{i=t}^{H}\gamma^{i-t}r_{i}\right], \tag{2}\]  
where \(\mu_{\pi}(s)\) is the (discounted) state distribution under \(\pi\), i.e., the probability of visiting state \(s\) under \(\pi\), and \(\gamma\in[0,1)\) is the discount factor which assigns weights to rewards at different timesteps. \(Q^{\pi}(s,a)\) is the action-state value function (or Q-function) which is the expected return obtained by executing \(a\) in state \(s\) and then following \(\pi\) afterwards. In tabular MDPs, the Q-function can be stored in a table, commonly referred to as Q-table, and in stationary infinite-horizon MDPs the greedy policy \(\pi^{*}(a|s)=\arg\max_{a}Q^{*}(s,a)\) is always optimal [21]. However, the Q-function of the current policy is initially unknown and has to be learned. **Q-learning. ** For tabular MDPs, Q-learning by [PERSON] and [PERSON] [22] was one of the most important breakthroughs in RL, and it is still at the core of recent successful algorithms. At each training step \(i\), the agent chooses an action according to a _behavior_ policy \(\beta(a|s)\), i.e., \(a_{t}\sim\beta(\cdot|s_{t})\), and then updates the Q-table according to  
\[Q^{\pi}_{i+1}(s_{t},a_{t}) =Q^{\pi}_{i}(s_{t},a_{t})+\eta\delta(s_{t},a_{t},s_{t+1}) \tag{3}\] \[\delta(s_{t},a_{t},s_{t+1}) = \begin{cases}r_{t}+\gamma\max_{a}Q^{\pi}_{i}(s_{t+1},a)-Q^{\pi}_ {i}(s_{t},a_{t})&\text{if $s_{t}$ is non-terminal}\\ r_{t}-Q^{\pi}_{i}(s_{t},a_{t})&\text{otherwise}\end{cases}  \tag{4}\]  
where \(\eta\) is the learning rate and \(\delta(s,a,s^{\prime})\) is the _temporal difference (TD) error_. The blue term is often referred to as _TD target_. This approach is called _off-policy_ because the policy \(\beta(a|s)\) used to explore the environment is different from the target greedy policy \(\pi(a|s)\). **The behavior policy and the \"exploration-exploitation dilemma\".