Long-Term Visitation Value for Deep Exploration in Sparse-Reward Reinforcement Learning

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}\left(s^{\prime }|s,a\right)$ defines a Markovian transition probability density between the current s and the next state $s^{\prime }$ under action a, $\mathcal{R}\left(s,a\right)$ is the reward function, and ${\mu }_1$ is initial distribution for state $s_1$. The state and action spaces could be finite, i.e., $\left|\mathcal{S}\right|=d_s$ and $\left|\mathcal{A}\right|=d_a$, or continuous, i.e., $\mathcal{S}\subseteq {\mathbb{R}}^{d_s}$ and $\mathcal{A}\subseteq {\mathbb{R}}^{d_a}$. 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 \left(a\right|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\dots 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 where ${\mu }_{\pi }\left(s\right)$ 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 }^{*}\left(a\right|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 Watkins and Dayan [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 \left(a\right|s)$, i.e., $a_t\sim \beta (·|s_t)$, and then updates the Q-table according to 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 \left(a\right|s)$ used to explore the environment is different from the target greedy policy $\pi \left(a\right|s)$.

The behavior policy and the “exploration-exploitation dilemma”. As discussed in Section 1, an important challenge in designing the behavior policy is to account for the exploration-exploitation dilemma. Exploration is a long-term endeavor where the agent tries to maximize the possibility of finding better rewards in states not yet visited. On the contrary, exploitation maximizes the expected rewards according to the current knowledge of the environment. Typically, in continuous action spaces Gaussian noise is added to the action, while in discrete spaces actions are chosen $ϵ$-greedily, i.e., optimally with probability $1-ϵ$ and randomly with probability $ϵ$. In this case, the exploration-exploitation dilemma is simply addressed by having larger noise and $ϵ$ at the beginning, and then decaying them over time. This naive dithering exploration is extremely inefficient in MDPs with sparse rewards, especially if some of them are “distractors”, i.e., rewards that create suboptimal modes of the objective function. In the remainder of this section, we review more sophisticated approaches addressing exploration with sparse rewards. We first show theoretically grounded ideas for tabular or small MDP settings which are generally computationally intractable for large MDPs. We then give an overview of methods that try to apply similar principles to large domains by making approximations.

Since finding high-value states is crucial for successful RL, a large body of work has been devoted to efficient exploration in the past years. We begin by discussing an optimal solution to exploration, then continue with confidence-bound-based approaches. Then, we discuss methods based on intrinsic motivation and describe posterior optimality value-distribution-based methods. We conclude by stating the main differences between our approach and these methods.

Optimal solution to exploration. In this paper, we consider model-free RL, i.e., the agent does not know the MDP dynamics. It is well-known that in model-free RL the optimal solution to exploration can be found by a Bayesian approach. First, assign an initial (possibly uninformative) prior distribution over possible unknown MDPs. Then, at each time step, the posterior belief distribution over possible MDPs can be computed using the Bayes’ theorem based on the current prior distribution, executed action, and made an observation. The action that optimally explores is then found by planning over possible future posterior distributions, e.g., using tree search, sufficiently far forward. Unfortunately, optimal exploration is intractable even for very small tasks [7,23,24]. The worst-case computational effort is exponential w.r.t. the planning horizon in tabular MDPs and can be even more challenging with continuous state-action spaces.

Optimism. In tabular MDPs, many of the provably efficient algorithms are based on optimism in the face of uncertainty (OFU) [25]. In OFU, the agent acts greedily w.r.t. an optimistic action value estimate composed of the value estimate and a bonus term that is proportional to the uncertainty of the value estimate. After executing an optimistic action, the agent then either experiences a high reward learning that the value of the action was indeed high, or the agent experiences a low reward and learns that the action was not optimal. After visiting a state-action pair, the exploration bonus is reduced. This approach is superior to naive approaches in that it avoids actions where low value and low information gain are possible. Under the assumption that the agent can visit every state-action pair infinitely many times, the overestimation will decrease and almost optimal behavior can be obtained [6]. Most algorithms are optimal up to a polynomial amount of states, actions, or horizon length. RL literature provides many variations of these algorithms which use bounds with varying efficacy or different simplifying assumptions, such as [6,10,11,12,26,27].

Upper confidence bound. Perhaps the best well-known OFU algorithm is the upper confidence bound (UCB1) algorithm [28]. UCB chooses actions based on a bound computed from visitation counts: the lower the count, the higher the bonus. Recently, Jin et al. [16] proved that episodic Q-learning with UCB exploration converges to a regret proportional to the square root of states, actions, and timesteps; and the square root of the cube of the episode length. Dong et al. [17] gave a similar proof for infinite horizon MDPs with sample complexity proportional to the number of states and actions. In our experiments, we compare our approach to Q-learning with UCB exploration as defined by Auer et al. [28].

Intrinsic motivation. The previously discussed algorithms are often computationally intractable, or their guarantees no longer apply in continuous state-action spaces, or when the state-action spaces are too large. Nevertheless, these provably efficient algorithms inspired more practical ones. Commonly, exploration is conducted by adding a bonus reward, also called auxiliary reward, to interesting states. This is often referred to as intrinsic motivation [29]. For example, the bonus can be similar to the UCB [15,30], thus encouraging actions of high uncertainty of low visitation count. Recent methods, instead, compute the impact of actions based on state embeddings and reward the agent for performing actions changing the environment [31].

Other forms of bonus are based on the prediction error of some quantity. For example, the agent may learn a model of the dynamics and try to predict the next state [19,20,32,33,34]. By giving a bonus proportional to the prediction error, the agent is incentivized to explore unpredictable states. Unfortunately, in the presence of noise, unpredictable states are not necessarily interesting states. Recent work addresses this issue by training an ensemble of models [35] or predicting the output of a random neural network [36].

As we will discuss in Section 3.2, our approach has similarities with the use of auxiliary reward. However, the use of auxiliary rewards can be inefficient for long-horizon exploration. Our approach addresses this issue by using a decoupled long-horizon exploration policy and, as the experiments in Section 4 show, it outperforms auxiliary-reward-based approaches [30].

Thompson sampling. Another principled well-known technique for exploration is Thompson sampling [37]. Thompson sampling samples actions from a posterior distribution which specifies the probability for each action to be optimal. Similarly to UCB-based methods, Thompson sampling is guaranteed to converge to an optimal policy in multi-armed bandit problems [38,39], and has shown strong empirical performance [40,41]. For a discussion of known shortcomings of Thompson sampling, we refer to [42,43,44].

Inspired by these successes, recent methods have followed the principle of Thompson sampling in Q-learning [4,45,46]. These methods assume that an empirical distribution over Q-functions—an ensemble of randomized Q-functions—is similar to the distribution over action optimalities used in Thompson sampling. Actions are thus sampled from such ensemble. Since the Q-functions in the ensemble become similar when updated with new samples, there is a conceptual similarity with the action optimality distribution used in Thompson sampling for which variance also decreases with new samples, while there are no general proofs for randomized Q-function approaches, Osband et al. [4] proved a bound on the Bayesian regret of an algorithm based on randomized Q-functions in tabular time-inhomogeneous MDPs with a transition kernel drawn from a Dirichlet prior, providing a starting point for more general proofs.

Other exploration methods approximating a distribution over action optimalities include for example the work of Fortunato et al. [47] and Plappert et al. [48], which apply noise to the parameters of the model. This may be interpreted as approximately inferring a posterior distribution [49], although this is not without contention [50]. Osband et al. [9] more directly approximates the posterior over Q-functions through bootstrapping [51]. The lack of a proper prior is an issue when rewards are sparse, as it causes the uncertainty of the posterior to vanish quickly. Osband et al. [52] and Osband et al. [4] try to address this by enforcing a prior via regularization or by adding randomly initialized but fixed neural network on top of each ensemble member, respectively.

Methods based on posterior distributions have yielded high performance in some tasks. However, because of the strong approximations needed to model posterior optimality distributions instead of maintaining visitation counts or explicit uncertainty estimates, these approaches may often have problems in assessing the state uncertainty correctly. In our experiments, the proposed approach outperforms state-of-the-art methods based on approximate posterior distributions, namely the algorithms proposed by Osband et al. [4,9] and D’Eramo et al. [46].

Above, we discussed state-of-the-art exploration methods that (1) use confidence bounds or distribution over action optimalities to take the exploration into account in a principled way, (2) modify the reward by adding an intrinsic reward signal to encourage exploration, and (3) approximate a posterior distribution over value functions. The main challenge that pertains to all these methods is that they do not take long-term exploration into account explicitly. Contrary to this, similarly to how value iteration propagates state values, we propose an approach that uses dynamic programming to explicitly propagate visitation information backward in time. This allows our approach to efficiently find the most promising parts of the state space that have not been visited before, and avoid getting stuck in suboptimal regions that at first appear promising.

Consider the toy problem of an agent moving in a grid, shown in Figure 2. Reward is 0 everywhere except in $(1,1)$ and $(3,1)$, where it is 1 and 2, respectively. The reward is given for executing an action in the state, i.e., on transitions from reward states. The agent’s initial position is fixed in $(1,3)$ and the episode ends when a reward is collected or after five steps. Any action in the prison cells $(2,2)$ has only an arbitrarily small probability of success. If it fails, the agent stays in $(2,2)$. In practice, the prison cell almost completely prevents any further exploration. Despite its simplicity, this domain highlights two important challenges for exploration in RL with sparse rewards. First, there is a locally optimal policy collecting the lesser reward, which acts as a distractor. Second, the prison state is particularly dangerous as it severely hinders exploration.

Assume that the agent has already explored the environment for four episodes performing the following actions: (1) left, down, left, down, down (reward 1 collected); (2) up, down, right, right (fail), right (fail); (3) right, left, right, down, down (fail); (4) right, down, left (fail), up (fail), right (fail). The resulting state-action visitation count is shown in Figure 3a. Given this data, we initialize $Q^{\pi }(s,a)$ to zero, train it with Q-learning with $\gamma =0.99$ until convergence, and then derive three greedy policies. The first simply maximizes $Q^{\pi }(s,a)$. The second maximizes the behavior $Q^{\beta }(s,a)$ based on UCB1 [28], defined as where $n(s,a)$ is the state-action count, and $\kappa$ is a scaling coefficient. Note that in classic UCB, the reward is usually bounded in $[0,1]$ and no coefficient is needed. This is not usually the case for MDPs, where Q-values can be larger/smaller than 1/0. We thus need to scale the square root with $\kappa =(r_{max}-r_{min})/(1-\gamma )$, which upper-bounds the difference between the largest and smallest possible Q-value). The third maximizes an augmented Q-function $Q^{+}(s,a)$ trained by adding the intrinsic reward based on the immediate count [30], i.e., where $\alpha$ is a scaling coefficient set to $\alpha =0.1$ as in [15,30]. Figure 3a shows the state-action count after the above trajectories, and Figure 3b–d depict the respective Q-functions (colormap) and policies (arrows). Given the state-action count, consider what the agent has done and knows so far.

In terms of exploration, the best decision would be to select new actions, such as “up” in (1,2). However, what should the agent do in states where it has already executed all actions at least once? Ideally, it should select actions driving it to unvisited states, or to states where it has not executed all actions yet. However, none of the policies above exhibits such behavior.

Despite its simplicity, the above toy problem highlights the limitations of current exploration strategies based on the immediate count. More specifically, (1) considering the immediate count may result in shallow exploration, and (2) directly augmenting the reward to train the Q-function, i.e., coupling exploration and exploitation, can have undesired effects due to the non-stationarity of the augmented reward function. To address these limitations, we propose an approach that (1) plans exploration actions far into the future by using a long-term visitation count, and (2) decouples exploration and exploitation by learning a separate function assessing the exploration value of the actions. Contrary to existing methods that use models of reward and dynamics [13], which can be hard to come by, our approach is off-policy and model-free.

Visitation value. The key idea of our approach is to train a visitation value function using the temporal difference principle. The function, called W-function and denoted by $W^{\beta }(s,a)$, approximates the cumulative sum of an intrinsic reward $r^W$ based on the visitation count, i.e., where ${\gamma }_w$ is the visitation count discount factor. The higher the discount, the more in the future the visitation count will look. In practice, we estimate $W^{\beta }(s,a)$ using TD learning on the samples produced using the behavior policy $\beta$. Therefore, we use the following update where $\eta$ is the learning rate, and ${\delta }^W(s_t,a_t,s_{t+1})$ is the W-function TD error, which depends on the reward $r^W$ (can be either maximized or minimized). Subsequently, following the well-known upper confidence bound (UCB) algorithm [25], the behavior policy is greedy w.r.t. the sum of the Q-function and upper confidence bound, i.e., where $U_W(s,a)$ is an upper confidence bound based on $W^{\beta }(s,a)$, and $\kappa$ is the same exploration constant used by UCB1 in Equation (5). This proposed approach (1) considers long-term visitation count by employing the W-function, which is trained to maximize the cumulative—not the immediate—count. Intuitively, the W-function encourages the agent to explore state-actions that have not been visited before. Given the current state s, in fact, $W^{\beta }(s,a)$ specifies how much exploration we can expect on (discount-weighted) average in future states if we choose action a. Furthermore, since the Q-function is still trained greedily w.r.t. the extrinsic reward as in Q-learning, while the W-function is trained greedily on the intrinsic reward and favors less-visited states, our approach (2) effectively decouples exploration and exploitation. This allows us to more efficiently prevent underestimation of the visitation count exploration term. Below, we propose two versions of this approach based on two different rewards $r^W$ and upper bounds $U_W(s,a)$.

W-function as long-term UCB. The visitation reward is the UCB of the state-action count at the current time, i.e., This W-function represents the discount-weighted average UCB along the trajectory, i.e., and its TD error is Notice how we distinguish between terminal and non-terminal states for the reward in Equation (10). The visitation value of terminal states, in fact, is equal to the visitation reward alone, as denoted by the TD target in Equation (10). Consequently, the visitation value of terminal states could be significantly smaller than the one of other states, and the agent would not visit them again after the first time. This, however, may be detrimental for learning the Q-function, especially if terminal states yield high rewards. For this reason, we assume that the agent stays in terminal states forever, getting the same visitation reward at each time step. The limit of the sum of the discounted reward is the reward in Equation (10). Furthermore, given proper initialization of $W_{\mathrm{UCB}}^{\beta }$ and under some assumptions, the target of non-terminal states will still be higher than the one of terminal states despite the different visitation reward, if the count of the former is smaller. We will discuss this in more detail later in this section.

Another key aspect of this W-function regards the well-known overestimation bias of TD learning. Since we can only update the W-function approximately based on limited samples, it is beneficial to overestimate its target with the max operator, while it is known that in highly stochastic environments the overestimation can degrade the performance of value-based algorithm [53,54], it has been shown that underestimation does not perform well when the exploration is challenging [55], and for a wide class of environments, overestimation allows finding the optimal solution due to self-correction [56].

Assuming identical visitation over state-action pairs, the W-function becomes the discounted immediate UCB, i.e., thus, we can use $W_{\mathrm{UCB}}^{\beta }(s,a)$ directly in the behavior policy In Section 3.3, we discuss how to initialize $W_{\mathrm{UCB}}^{\beta }(s,a)$. Finally, notice that when ${\gamma }_w=0$, Equation (13) is the classic UCB, and Equation (14) is equivalent to the UCB1 policy in Equation (5).

W-function as long-term count. The visitation reward is the state-action count at the current time, i.e., This W-function represents the discount-weighted average count along the trajectory, i.e., and its TD error is Once again we distinguish between terminal and non-terminal states, but in the TD error the max operator has been replaced by the min operator. Contrary to the previous case, in fact, the lower the W-function the better, as we want to incentivize the visit of lower-count states. If we would use only the immediate count as reward for terminal states, the agent would be constantly driven there. Therefore, similarly to the UCB-based reward, we assume that the agent stays in terminal states forever getting the same reward.

In the TD target, since we want to prioritize low-count state-action pairs, the min operator yields an optimistic estimate of the W-function, because the lower the W-function the more optimistic the exploration is. Assuming identical visitation over state-action pairs, the W-function becomes the discounted cumulative count, i.e., We then compute the pseudocount $\hat{n}(s_t,a_t)=(1-{\gamma }_w)W_{\mathrm{N}}^{\beta }(s_t,a_t)$ and use it in the UCB policy When the counts are zero, $W_{\mathrm{N}}^{\beta }(s,a)=0$, thus we need to initialize it to zero. We discuss how to avoid numerical problem in the square root in Section 3.3. Finally notice that when ${\gamma }_w=0$, Equation (19) is equivalent to the UCB1 policy in Equation (5).

Example of Long-Term Exploration with the W-function. Consider again the toy problem presented in Section 3.1. Figure 4 shows the behavior policies of Equation (14) and Equation (19) with ${\gamma }_w=0.99$. The policies are identical and both drive the agent to unvisited states, or to states where it has not executed all actions yet, successfully exhibiting long-term exploration. The only difference is the magnitude of the state-action pair values (the colormap, especially in unvisited states) due to their different initialization.

In UCB bandits, it is assumed that each arm/action will be executed once before actions are executed twice. In order to enforce this, we need to make sure that the upper confidence bound $U_W(s,a)$ is high enough so that an action cannot be executed twice before all other actions are executed once. Below, we discuss how to initialize the W-functions and set bounds in order to achieve the same behavior. For the sake of simplicity, below we drop subscripts and superscripts, i.e., we write $Q(s,a)$ in place of $Q^{\pi }(s,a)$, and $W(s,a)$ in place of $W_{\mathrm{UCB}}^{\beta }(s,a)$ or $W_{\mathrm{N}}^{\beta }(s,a)$.

$W_{\mathrm{UCB}}^{\beta }$upper bound. To compute the initialization value we consider the worst-case scenario, that is, in state s all actions a but $\overline{a}$ have been executed. In this scenario, we want that $W(s,\overline{a})$ is an upper bound of $W(s,a)$. Following Equations (12) and (14), we have where the blue term is the TD target for non-terminal states, and $\sqrt{2log\left(\right|\mathcal{A}|-1)}$ is the immediate visitation reward for executing $\overline{a}$ in the worst-case scenario (all other $\left|\mathcal{A}\right|-1$ actions have been executed, and $\hat{a}$ has not been executed yet). In this scenario, $W(s,\overline{a})$ is an upper bound of $W(s,a)$ under the assumption of uniform count, i.e., We can then write Equation (20) as In order to guarantee to select $\overline{a}$, which has not been select yet, we need to initialize $W(s,\overline{a})$ such that the following is satisfied where $Q_{min}$ denotes the smallest possible Q-value. We get Initializing the W-function according to Equation (24) guarantees to select $\overline{a}$.

$W_{\mathrm{N}}^{\beta }$upper bound. Since this W-function represents the discounted cumulative count, it is initialized to zero. However, numerical problems may occur in the square root of Equation (19) because the pseudocount can be smaller than one or even zero. In these cases, the square root of negative numbers and the division by zero are not defined. To address these issues, we add +1 inside the logarithm and replace the square root with an upper bound when $\hat{n}(s,a)=0$. Similarly to the previous section, the bound needs to be high enough so that an action cannot be executed twice before all other actions are executed once. Following Equation (19), we need to ensure that However, here assuming uniform count does not guarantee a uniform pseudocount, i.e.,

To illustrate this issue, consider the chain MDP in Figure 5. The agent always starts in A and can move left, right, and down. The episode ends after eight steps, or when terminal state E is reached. The goal of this example is to explore all states uniformly. In the first episode, the agent follows the blue trajectory ($A,D,E$). In the second episode, it follows the red trajectory ($A,C,D,D,C,B,B,B$). In both trajectories, an action with count zero was always selected first. At the beginning of the third episode, all state-action pairs have been executed once, except for “left” in A, i.e., $n(s,a)=1\forall (s,a)\ne (A,left),n(A,left)=0$. Thus, we need to enforce the agent to select it. However, the discounted cumulative count $\hat{n}(s,a)=(1-{\gamma }_w)W(s,a)$ is not uniform. For example, with ${\gamma }_w=0.9$, $\hat{n}(A,right)=3.8$ and $\hat{n}(A,down)=4.52$.

More in general, the worst-case scenario for satisfying Equation (25) is the one where (1) action $\overline{a}$ has not been executed yet, (2) an action $\dot{a}$ has been executed once and has the smallest pseudocount, and (3) all other actions have been executed once and have the highest pseudocount. In this scenario, to select $\overline{a}$ we need to guarantee $U_W(s,\overline{a})>U_W(s,\dot{a})$. Assuming that counts are uniform and no action has been executed twice, the smallest pseudocount is $\hat{n}(s,\dot{a})=1-{\gamma }_w$, while the highest is 1. Then, Equation (25) becomes Replacing $U_W(s,a)$ in Equation (19) with Equation (27) when $n(s,\overline{a})=0$ guarantees to select $\overline{a}$.

Example of exploration behavior under uniform count. Consider our toy problem again. This time, all state-action pairs have been executed once except for “left” in (1,3). The Q-table is optimal for visited state-action pairs, thus the greedy policy simply brings the agent to (3,1) where the highest reward lies. Figure 6 shows baseline and proposed behavior policies in two scenarios, depending on whether reward states are terminal (upper row) or not (bottom row).

Finally, if the count is uniform for all state-action pairs, including for “left” in (1,3), then all policies look like the greedy one (Figure 6a).

In this section, we discuss the uniform count assumption used to derive the bounds, the differences between the proposed W-functions and intrinsic motivation, the benefit of using the count-based one, and potential issues in stochastic environments and continuous MDPs.

Uniform count assumption. In Section 3.3, we derived an initialization for $W_{\mathrm{UCB}}^{\beta }$ and a bound for $W_{\mathrm{N}}^{\beta }$ to guarantee that an action is not executed twice before all actions are executed once. For that, we assumed the visitation count to be uniform for all state-action pairs. We acknowledge that this assumption is not true in practice. First, the agent may need to revisit old states in order to visit new ones. Second, when an episode is over the state is reset and a new episode starts. This is common practice also for infinite horizon MDPs when usually the environment is reset after some steps. Thus, the agent’s initial state will naturally have a higher visitation count. Nonetheless, in Section 4.2.1, we empirically show that our approach allows the agent to explore the environment as uniformly as possible.

W-function vs. auxiliary rewards. Using an auxiliary reward such as an exploration bonus or an intrinsic motivation signal has similarities with the proposed approach, especially with $W_{\mathrm{UCB}}^{\beta }$, but the two methods are not equivalent. Consider augmenting the reward with the same visitation reward used to train the W-function, i.e., $r_t^{+}=r_t+\alpha r_t^W$. Using TD learning, the augmented Q-function used for exploration can be rewritten as Then consider the behavior policy derived from $W_{\mathrm{UCB}}^{\beta }$ in Equation (14), and decompose it where we considered $\alpha =\kappa (1-{\gamma }_w)$. Red terms are equivalent, but blue terms are not because of the max operator, since ${max}_x\{f\left(x\right)+g\left(x\right)\}\ne {max}_x\left\{f\left(x\right)\right\}+{max}_x\left\{g\left(x\right)\right\}$.

This explicit separation between exploitation (Q) and exploration (W) has two important consequences. First, it is easy to implement the proposed behavior policy for any off-policy algorithm, as the exploration term is separate and independent from the Q-function estimates. This implies that we can propagate the exploration value independently from the action-value function. With this choice, we can select a discount factor ${\gamma }_w$ that differs from the MDP discount $\gamma$. By choosing a high exploration discount factor ${\gamma }_w$, we do long-term exploration allowing us to find the optimal policy when exploration is crucial. By choosing a low exploration discount factor ${\gamma }_w$, instead, we perform short-term exploration which may converge faster to a greedy policy. In the evaluation in Section 4.2, we show experiments for which the discount factors are the same, as well as experiments where they differ. Furthermore, we investigate the effect of changing the W-function discount while keeping the Q-function discount fixed.

Second, auxiliary rewards are non-stationary, as the visitation count changes at every step. This leads to a non-stationary target for the Q-function. With our approach, by decoupling exploration and exploitation, we have a stationary target for the Q-function while moving all the non-stationarity to the W-function.

Terminal states and stochasticity. The visitation rewards for training the W-functions penalize terminal state-action pairs (Equations (10) and (15)). Thus, the agent will avoid visiting them more than once. One may think this would lead to poor exploration in stochastic environments, where the same state-action pair can lead to either terminal or non-terminal states. In this case, trying the same action again in the future may yield better exploration depending on the stochastic transition function. Yet, in Section 4.2.5 we empirically show that stochasticity in the transition function does not harm our approach.

Pseudo-counts and continuous MDPs. In the formulation of our method—and later in the experiments section—we have considered only tabular MDPs, i.e., with discrete states and actions. This makes it easy to exactly count state-action pairs and accurately compute visitation rewards and value functions. We acknowledge that the use of counts may be limited to tabular MDPs, as real-world problems are often characterized by continuous states and actions. Nonetheless, pseudo-counts [57] have shown competitive performance in continuous MDPs and can be used in place of exact counts without any change to our method. Alternatively, it is possible to replace counts with density models [58] with little modifications to our method. Finally, if neural networks would be used to learn the visitation-value function $W(s,a,s^{\prime })$, it may be necessary to introduce target networks similarly to deep Q-networks [1].

We use the following environments: deep sea [4,52], taxi driver [59], and four novel benchmark gridworlds. All the environments have sparse discounted rewards, and each has peculiar characteristics making it challenging to solve.

Evaluation Criteria. For each environment, we evaluate the algorithms on varying two different conditions: optimistic vs. zero initialization of the behavior Q-tables, and short vs. long horizon, for a total of four scenarios. For each of them, we report the expected discounted return of $\pi \left(a\right|s)$, which is greedy over $Q^{\pi }(s,a)$, and the number of visited states over training samples. In all environments, the initial state is fixed.

Optimistic initialization [25] consists of initializing the Q-tables to a large value. After visiting a state-action pair, either the agent experiences a high reward confirming their belief about its quality, or the agent experiences a low reward and learns that the action was not optimal and will not execute it again in that state. By initializing the Q-tables to the upper bound $r_{max}/(1-\gamma )$ we are guaranteed to explore all the state-action pairs even with just an $ϵ$-greedy policy. However, this requires prior knowledge of the reward bounds, and in the case of continuous states and function approximation the notion of a universally “optimistic prior” does not carry over from the tabular setting [4]. Thus, it is important that an algorithm is able to explore and learn even with a simple zero or random initialization.

The length of the horizon is also an important factor for exploration. If the agent can perform a limited number of actions during an episode, it has to carefully choose them in order to explore as efficiently as possible. Prominent examples in this regard are real-world tasks such as videogames, where the player has limited time to fulfill the objective before the game is over, or robotics, where the autonomy of the robot is limited by the hardware. Thus, it is important that an algorithm is able to explore and learn even when the training episode horizon is short. In the “short horizon” scenario, we allow the agent to explore for a number of steps slightly higher than the ones needed to find the highest reward. For example, if the highest reward is eight steps away from the initial position, the “short horizon” is ten steps. The “long horizon” scenario is instead always twice as long.

Results are first presented in plots showing the number of states discovered and discounted return against training steps averaged over 20 seeds. Due to the large number of evaluated algorithms, confidence intervals are not reported in plots. At the end of the section, a recap table summarizes the results and reports the success of an algorithm, i.e., the number of seeds the algorithm learned the optimal policy, and the percentage of states visited at the end of the learning, both with 95% confidence interval.

In this section, we present an in-depth analysis of issues associated with learning with sparse rewards, explaining in more detail why our approach outperformed existing algorithms in the previous evaluation. We start by reporting the visitation count at the end of the learning, showing that our algorithms explore the environment uniformly. We continue with a study on the impact of the visitation discount ${\gamma }_w$, showing how it affects the performance of the W-function. Next, we present the empirical sample complexity analysis of all algorithms on the deep sea domain, showing that our approach scales gracefully with the number of states. Finally, we evaluate the algorithms in the infinite horizon setting and stochastic MDPs, evaluating the accuracy of the Q-function and the empirical sample complexity. Even in these scenarios, our approach outperforms existing algorithms.