Beyond Optimism: Exploration With Partially Observable Rewards

Authors: simone  parisi
alireza  kazemipour
michael  bowling
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 19:19:36

Abstract: Exploration in reinforcement learning (RL) remains an open challenge.
RL algorithms rely on observing rewards to train the agent, and if informative rewards are sparse the agent learns slowly or may not learn at all. 
To improve exploration and reward discovery, popular algorithms rely on optimism. 
But what if sometimes rewards are unobservable, e.g., situations of partial monitoring in bandits and the recent formalism of monitored Markov decision process? 
In this case, optimism can lead to suboptimal behavior that does not explore further to collapse uncertainty.
With this paper, we present a novel exploration strategy that overcomes the limitations of existing methods and guarantees convergence to an optimal policy even when rewards are not always observable. 
We further propose a collection of tabular environments for benchmarking exploration in RL (with and without unobservable rewards) and show that our method outperforms existing ones.

Main paper: 
 introduction: 
 Reinforcement learning (RL) has developed into a powerful paradigm where agents can tackle a variety of tasks, including games [67] , robotics [31] , and medical applications [82] . Agents trained with RL learn by trial-and-error interactions with an environment: the agent tries different actions, the environment returns a numerical reward, and the agent adapts its behavior to maximize future rewards. This setting poses a well-known dilemma: how and for how long should the agent explore, i.e., try new actions and visit new states in search for rewards? If the agent does not explore enough it may miss important rewards. However, prolonged exploration can be expensive, especially in real-world problems where instrumentation (e.g., cameras or sensors) or a human expert may be needed to provide rewards. Classic dithering exploration [39, 47] is known to be inefficient [34] , especially when informative rewards are sparse [54, 60] . Among the many exploration strategies that have been proposed to improve RL efficiency, perhaps the most well-known and grounded is optimism. With optimism, the agent assigns to each state-action pair an optimistically biased estimate of future value and selects the action with the highest estimate [50] . This way, the agent is encouraged to explore unvisited states and perform different actions, where either its optimistic expectation holds -the observed reward matches the optimistic estimate -or not. If not, the agent adjusts its estimate and looks for rewards elsewhere. Optimistic algorithms range from count-based exploration bonuses [4, 16, 24, 25] , to model-based planning [3, 20, 21] , bootstrapping [15, 52] , and posterior sampling [50] . Nonetheless, optimism can fail when the agent has limited observability of the outcome of its actions. Consider the example in Figure 1b , where the agent observes rewards only under some condition and upon paying a cost. To fully explore the environment and learn an optimal policy the agent must first take a suboptimal action (to push the button and pay a cost) to learn about the rewards. However, optimistic algorithms would never select suboptimal actions, thus never pushing the button and never learning how to accumulate positive rewards [36] . While alternatives to optimism exist, such as intrinsic motivation [66] , they often lack guarantees of convergence and their efficacy strongly depends on the intrinsic reward used, the environment, and the task [7] . Figure 1 : When optimism is not enough. The agent starts in the second leftmost cell of a corridorlike gridworld and can move LEFT or RIGHT. The coin in the leftmost cell gives a small reward, the one in the rightmost cell gives a large reward, while all other cells give zero rewards. In (b), pushing the button is costly (negative reward) but is needed to observe coin rewards -if the agent collects a coin without pushing it first, the environment returns the reward but the agent cannot observe it. Given a sufficiently large discount factor, the optimal policy is to collect the large coin without pushing the button. Consider a purely optimistic agent, i.e., an agent that selects action greedily with respect to their value estimate, and these estimates are initialized to the same optimistically high value [17] . In (a) all rewards are always observable, therefore: the agent visits a cell; its optimistic estimate decreases according to the reward; the agent tries another cell. At the end, it will visit all states and learn the optimal policy. In (b), however, when the agent visits a coin cell without pushing the button first, it will not observe the reward and will not validate or prove wrong its optimistic estimate. Thus, the estimate for both coin-cells will stay equally optimistic, and between the two the agent will prefer to go to the leftmost cell because it is closer to the start. Optimistic model-based algorithms [3, 24] have the same problem. If all value estimates are optimistic and the agent knows that pushing the button is costly, between (1) push the button and collect the right coin, (2) do not push the button and collect the right coin, and (3) do not push the button and collect the left coin, the agent will always chose the third: the optimistic value is the same, but it does not incur in the button cost and the left coin is closer. Yet, this gives no information to the agent, because it cannot observe the reward and therefore cannot update its optimistic value. Note that the agent could replace the unobserved reward with an estimate from a model updated as rewards are observed. But how can this model be accurate if the agent cannot explore properly and observe rewards in the first place?How can we efficiently explore and learn to act optimally when rewards are partially observable, without relying on optimism and yet still have guarantees of convergence? In this paper, we present a novel exploration strategy based on the successor representation to tackle this question. Note that Lattimore and Szepesvari [36] already argued against optimism in partial monitoring [8] , a generalization of the bandit framework where the agent cannot observe the exact payoffs. Similarly, Schulze and Evans [68] and Krueger et al. [33] discussed the shortcomings of optimism in active RL, where rewards are observable upon paying a cost. While we follow the same line of research, we consider the more recent and general framework of Monitored Markov Decision Processes (Mon-MDPs) [55] , and we validate the efficacy of the proposed exploration on a collection of both MDPs and Mon-MDPs. A Markov Decision Process (MDP) (Figure 2 ) is a mathematical framework for sequential decision-making, defined by the tuple ⟨S, A, R, P, γ⟩. An agent interacts with an environment by repeatedly observing a state s t ∈ S, taking an action a t ∈ A, and observing a bounded reward r t ∈ R. These interactions are governed by the Markovian transition function P(s t+1 | a t , s t ) and the reward function r t ∼ R(s t , a t ), both unknown to the agent. The agent's goal is to act to maximize the sum of discounted rewards ∞ t=1 γ t-1 r t , where γ ∈ [0, 1) is the discount factor describing the trade-off between immediate and future rewards.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: In the abstract/introduction we highlighted the lack of practical algorithms with guarantees of convergence in MDPs with partially observable rewards. Later, we presented an algorithm to address this, proved its asymptotic convergence, and validated its efficacy on a collection of MPDs (with and without partially observable rewards). Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
problem formulation: 
 Environment AgentHow the agent acts is determined by the policy π(a | s), a function denoting the probability of executing action a in state s. A policy is optimal when it maximizes the Q-function, i.e.,π * := arg max π Q π (s, a),whereEQUATIONThe existence of at least one optimal policy and its optimal Q-function Q * is guaranteed under the following standard assumptions: finite state and action spaces, stationary reward and transition functions, and bounded rewards [58] . Q-Learning [81] is one of the most common algorithms to learn Q * by iteratively updating a function Q as follows,EQUATIONwhere α t is the learning rate. Q is guaranteed to converge to Q * under an appropriate learning rate schedule α t and if every state-action pair is visited infinitely often [13] . Thus, how the agent explores plays a crucial role. For example, a random policy eventually visits all states but is clearly inefficient, as states that are hard to reach will be visited less frequently (e.g., because they can be reached only by performing a sequence of specific actions). How frequently the policy explores is also crucialto behave optimally we also need the policy to act optimally eventually. That is, at some point, the agent should stop exploring and act greedy instead. For these reasons, we are interested in greedy in the limit with infinite exploration (GLIE) policies [69] , i.e., policies that guarantee to explore all state-action pairs enough for Q to converge to Q * , and that eventually act greedy as in Eq. ( 1). Mon-MDPs (Figure 3 ) are defined by the tuple⟨S E , A E , P E , R E , M, S M , A M , P M , R M , γ⟩,where ⟨S E , A E , P E , R E , γ⟩ is the same as classic MDPs and the superscript E stands for "environment", while ⟨M, S M , A M , P M , R M ⟩ is the "monitor", a separate process with its own states, actions, rewards, and transition. The monitor works similarly to the environment -performing a monitor action a M t ∈ A M affects its state s M t ∈ S M and yields a bounded reward r M t ∼ R M (s M t , a M t ). However, there are two crucial differences. First, its Markovian transition depends on the environment as well, i.e., P M (s M t+1 | s M t , s E t , a M t , a E t ). Second, the monitor function M stands in between the agent and the environment, dictating what the agent sees about the environment reward -rather than directly observing the environment reward r E t ∼ R E (s E t , a E t ), the agent observes a proxy reward rE t ∼ M(r E t , s M t , a M t ). Most importantly, the monitor may not always show a numerical reward, and the agent may sometime receive rE t = ⊥, i.e., "unobservable reward". In Mon-MDPs, the agent repeatedly executes a joint action a t := (a E t , a M t ) according to the joint state s t := (s E t , s M t ). In turn, the environment and monitor states change and produce a joint reward (r E t , r M t ), but the agent observes (r E t , r M t ). The agent's goal is to select joint actions to maximize ∞ t=1 γ t-1 (r E t + r M t ) even though it observes rE t instead of r E t . For example, in Figure 1b the agent can turn monitoring on/off by pushing the button: if monitoring is off, the agent cannot observe the environment rewards; if on, it observes them but receives negative monitor rewards. Formally,S M = {ON, OFF}, A M = {PUSH, NO-OP}, R M (ON, •) = -1, M(r E t , ON, •) = r E t , M(r E t , OFF, •) = ⊥.The optimal policy is to move to the rightmost cell without turning monitoring on -the agent still receives the positive reward even though it does not observe it. 1 The presence of the monitor and the partial observability of rewards highlight two fundamental differences between Mon-MDPs and existing MDPs variations. First, the observability of the reward is dictated by a "Markovian entity" (the monitor), thus actions can have either immediate or long-term effects on the reward observability. For example, the agent may immediately observe the reward upon explicitly asking for it as in active RL [68] , e.g., with a dedicated action a M = ASK. Or, rewards may become observable only after changing the monitor state through a sequence of actions, e.g., as in Figure 1b by reaching and pushing the button. Second, reward unobservability goes beyond reward sparsity. In sparse-reward MDPs [34] , rewards are always observable even though informative non-zero rewards are sparse. Mon-MDPs with dense informative observable rewards may still be challenging even if a few rewards are partially observable. Consider the Mon-MDP in Figure 1b , but this time zero-rewards of empty tiles are replaced with negative rewards proportional to the distance to the large coin (dense and informative). Because coin rewards are still observable only after pressing the button, an optimistic agent will still collect the small coin: the optimistic value of the small coin is as high as the optimistic value of the large coin, but collecting the small coin takes fewer steps, thus ending the series of dense negative rewards sooner. The agent must first push the button (a suboptimal action) to learn the optimal policy regardless of the presence of dense observable rewards.Mon-MDPs provide a comprehensive framework encompassing existing areas of research, such as active RL [33, 68] and partial monitoring [5, 8, 37, 41] . In their introductory work, Parisi et al. [55] showed the existence of an optimal policy and the convergence of a variant of Q-Learning under some assumptions. 2 Yet, many research questions remain open, most prominently how to explore efficiently in Mon-MDPs. In the next section, we review exploration strategies in RL and discuss their shortcomings, especially when rewards are partially observable as in Mon-MDPs. For the sake of simplicity, in the remainder of the paper we use the notation (s, a) to refer to both the environment state-action pairs (in MDPs) and the joint environment-monitor state-action pairs (in Mon-MPDs). All the related work on exploration for MDPs can be applied to Mon-MDPs as well (not albeit with limited efficacy, as we discuss below). Similarly, the exploration strategy we propose in Section 3 can be applied to both MDPs and Mon-MDPs.Optimism. In tabular MDPs, many provably efficient algorithms are based on optimism in the face of uncertainty (OFU) [35] . In OFU, the agent acts greedily with respect to an optimistic estimate composed of the action-value estimate (e.g., Q) and a bonus term that is proportional to the uncertainty of the estimate. After executing an optimistic action, the reward either validates the agent's optimism or proves it wrong, thus discouraging the agent from trying it again. RL literature provides many variations of these algorithms, each with different convergence bounds and assumptions. Perhaps the best known OFU algorithms are based on the upper confidence bound (UCB) algorithm [4] , where the optimistic value is computed from visitation counts (the lower the count, the higher the bonus). In model-free RL, Jin et al. [25] proved convergence bounds for episodic MDPs, and later Dong et al. [16] extended the proof to infinite horizon MDPs, but both are often intractable. In model-based RL, algorithms like R-MAX [10] and UCRL [3, 24] consider a set of plausible MDP models (i.e., plausible reward and transition functions) and optimistically select the best action over what they believe to be the MDP yielding the highest return. Unfortunately, this optimistic selection can fail when rewards are not always unobservable [33, 36, 68] , as the agent may have to select actions that are known to be suboptimal to discover truly optimal actions. For example, in Figure 1b pushing the button is suboptimal (the agent pays a cost) but is the only way to discover the large positive reward.Posterior sampling for RL (PSRL). PSRL adapts Thompson sampling [79] to RL. The agent is given a prior distribution over a set of plausible MDPs, and rather than sampling the MDP optimistically as in OFU, PSRL samples it from a distribution representing how likely an MDP is to yield the highest return. Only then, the agent acts optimally for the sampled MDP. PSRL can be orders of magnitude more efficient than UCRL [50] , but its efficiency strongly depends on the choice of the prior [32, 57, 73, 80] . Furthermore, the computation of the posterior (by Bayes' theorem) can be intractable even for small tasks, thus algorithms usually approximate it empirically with an ensemble of randomized Q-functions [15, 51, 52] . Nonetheless, if rewards are partially observable PSRL suffers from the same problem as OFU: the agent may never discover rewards if actions needed to observe them (and further identify the MDP) are suboptimal for all MDPs with posterior support [36] .Information gain. These algorithms combine PSRL and UCB principles. On one hand, they rely on a posterior distribution over plausible MDPs, on the other hand they augment the current value estimate with a bound that comes in terms of an information gain quantity, e.g., the difference between the entropy of the posterior after an update [28, 40, 62, 70] . This allows to sample suboptimal but informative actions, thus overcoming some limitations of OFU and PSRL. However, similar to PSRL, performing explicit belief inference can be intractable even for small problems [2, 29, 62] .Intrinsic motivation. While many of above strategies are often computationally intractable, they 2 The assumptions are: monitor and environment ergodicity, i.e., any joint state-action pair can be reached by any other pair given infinite exploration; monitor ergodicity, i.e., for every environment reward there exists at least one joint state-action pair for which the environment reward is observable given infinite exploration; truthful monitor, i.e., either the proxy reward is the environment reward (r E t = r E t ) or is not observable (r E t = ⊥).inspired more practical algorithms where exploration is conducted by adding an intrinsic reward to the environment. This is often referred to as intrinsic motivation [63, 66] . For example, the intrinsic reward can depend on the visitation count [9] , the impact of actions on the environment [60] , interest or surprise [1, 53] , information gain [22] , or can be computed from prediction errors of some quantity [11, 56, 71] . However, intrinsic rewards introduce non-stationarity to the Q-function (they change over time), are often myopic (they are often computed only on the immediate transition), and are sensitive to noise [56] . Furthermore, if they decay too quickly exploration may vanish prematurely, but if they outweigh the environment reward the agent may explore for too long [11] .It should be clear that learning with partially observable rewards is still an open challenge. In the next section, we present a practical algorithm that (1) performs deep exploration -it can reason long-term, e.g., it tries to visit states far away, (2) does not rely on optimism -addressing the challenges of partially observable rewards, (3) explicitly decouples exploration and exploitation -thus exploration does not depend on the accuracy of Q, which is known to be problematic (e.g., overestimation bias) for off-policy algorithms (even more if rewards are partially observable). After proving its asymptotic convergence we empirically validate it on a collection of tabular MDPs and Mon-MDPs. β t = log t /Nt(s G , a G ) if β t > β then return ρ(a | s t , s G , a G ) // explore else return arg max a Q(s t , a) // exploitAlgorithm 1 outlines our idea for step-wise exploration. 3 N (s, a) is the state-action visitation count and, at every timestep, the agent selects the least-visited pair as "goal" (s G , a G ). The ratio β t decides if the agent explores (goes to the goal) or exploits according to a threshold β > 0. If two or more pairs have the same lowest count, ties are broken consistently according to some deterministic ordering. For example, if actions are {LEFT, RIGHT, UP, DOWN}, LEFT is the first and will be selected if the count of all actions is the same. This ensures that once the agent starts exploring to reach a goal, it will continue to do so until the goal is visited -once its count is minimal under the deterministic tie-break, it will continue to be minimal until the goal is visited and its count is incremented. Exploration is driven by ρ(a | s t , s G , a G ), a goal-conditioned policy that selects the action according to the current state s t and goal (s G , a G ). Intuitively, as the agent explores, if every state-action pair is visited infinitely often, log t will grow at a slower rate than N t (s, a) and the agent will increasingly often exploit (formal proof below). Furthermore, infinite exploration ensures Q converges to Q * , i.e., that its greedy actions are optimal. Intuitively, the role of β t is similar to the one of ϵ t in ϵ-greedy policies [75] . However, rather than manually tuning its decay, β t naturally decays as the agent explores.The goal-conditioned policy ρ is the core of Algorithm 1. For efficient exploration we want ρ to move the agent as quickly as possible to the goal, i.e., we want to minimize the goal-relative diameter under ρ. Intuitively, this diameter is a bound on the expected number of steps the policy would take to visit the goal from any state (formal definition below). Moreover, we want to untie ρ from the Q-function, the rewards, and their observability. In the next section we propose a policy ρ that satisfies these criteria, but first we prove that Algorithm 1 is a GLIE policy under some assumptions on ρ. Definition 1 (Singh et al. [69] ). An exploration policy is greedy in the limit (GLIE) if (1) each action is executed infinitely often in every state that is visited infinitely often, and (2) in the limit, the learning policy is greedy with respect to the Q-function with probability 1.EQUATIONi.e., the maximum expected number of steps to reach (s G , a G ) from any state in the MDP. We say the goal-relative diameter is bounded byD if D ≥ max s G ,a G D ρ (s G , a G ).There exist goal-conditioned policies with bounded goal-relative diameter if and only if the MDP is communicating (i.e., for any two states there is a policy under which there is non-zero probability to move between the states in finite time; see Puterman [58] and Jaksch et al. [24] ). While not all goal-conditioned policies have bounded goal-relative diameter, one such policy is the random policy or similarly an ϵ-greedy policy for ϵ > 0 [69] . Different goal-conditioned policies will have different bounds on their goal-relative diameter D ρ (s G , a G ). 4Theorem 1. If the goal-relative diameter of ρ is bounded by D then Algorithm 1 is a GLIE policy.Proof. Let Z t (s, a) be the number of timesteps before time t that the agent is in an exploration step with (s G , a G ) = (s, a). Let X t = s,a Zt(s, a) /t be the fraction of time up to time t that the agent has spent exploring. We want to show that ∀ε > 0 lim t→∞ Pr[X t > ε] = 0, i.e., the probability that the agent explores as frequently as any positive ε approaches 0. Hence, the policy is greedy in the limit. Note that, if the agent's frequency of exploring approaches zero this also must mean that Once the agent starts exploring to visit (s, a), it will do so until it actually visits (s, a). Let I t (s, a) be the number of times the agent started exploring to visit (s, a) before time t. We know that I t (s, a) ≤ N t (s, a) + 1, as the agent must visit (s, a) before it starts exploring to visit it again. Let t ′ ≤ t be the last time it started exploring to visit (s, a). We haveβ t ∈ O(1), implying N t (s, a) → ∞ ∀(s,EQUATIONwhere the strict inequality is due to β t ′ > β (condition to explore). Since the agent cannot have started exploration log t / β + 1 times, and the goal-relative diameter of ρ is at most D, thenEQUATIONWe can now apply Markov's inequality with threshold 1 / √ t,EQUATIONSince 1 / √ t < ε for sufficiently large t,EQUATIONhence the Algorithm 1 is a GLIE policy.Corollary 1. As a consequence of Theorem 1, Q converges to Q * (infinite exploration) and therefore the algorithm's behavior converges to the optimal policy (greedy in the limit). 5While we have noted that the random policy is a sufficient choice for ρ to meet the criteria of Theorem 1, the bound in Equation 7shows a direct dependence on the goal-relative diameter D ρ (s G , a G ). Thus, the optimal ρ to explore efficiently in Algorithm1 is ρ * (a | s, s G , a G ) := arg min ρ D ρ (s G , a G ),i.e., we want to reach the goal from any state as quickly as possible in expectation. Furthermore, we want to untie ρ from the learned Q-function and the reward observability. However, learning such a policy can be challenging because the diameter of the MDP is usually unknown. In the next section, we present a suitable alternative based on the successor representation [14] .Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: We discuss limitations together with future directions of research in Section 5.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
successor-function: an exploration compass: 
 The successor representation (SR) [14] is a generalization of the value function, and represents the cumulative discounted occurrence of a state s i under a policy π, i.e., E[∞ k=t γ k-t 1{s k =si} | π, P, s t ],where 1{s k =si} is the indicator function returning 1 if s k = s i and 0 otherwise. The SR does not depend on the reward function and can be learned with temporal-difference in a model-free fashion, e.g., with Q-Learning. Despite their popularity in transfer RL [6, 19, 38, 61] , to the best of our knowledge, only Machado et al. [43] and Jin et al. [26] used the SR to enhance exploration by using it as an intrinsic reward. Here, we follow the idea of the SR -to predict state occurrences under a policy -to learn a value function that the goal-conditioned policy in Algorithm 1 can use to guide the agent towards desired state-action pairs. We call this the state-action successor-function (or S-function) and we formalize it as a general value function [76] representing the cumulative discounted occurrence of a state-action pair (s i , a j ) under a policy π, i.e.,EQUATIONwhere 1{s k =si,a k =aj } is the indicator function returning 1 if s k = s i and a k = a j , and 0 otherwise.Prior work considered the SR relative to either an ϵ-greedy exploration policy [43] or a random policy [38, 44, 61] . Instead, we consider a different "successor policy" for every state-action pair (s i , a j ), and define the optimal successor policy as the one maximizing the respective S-function, i.e.,EQUATIONThe switch from π to ρ is intentional: to maximize the S-function means to maximize the occurrence of (s i , a j ) under γ discounting, which can been seen as visiting (s i , a j ) as fast as possible from any other state. 6 Thus, Eq. ( 9) is a suitable goal-conditioned policy ρ * discussed in Algorithm 1. Similar to the Q-function, we can learn an approximation of the S-functions using Q-Learning, i.e., S siaj (s t , a t ) ← (1EQUATIONBecause the initial estimates of S siaj can be inaccurate, in practice we let ρ to be ϵ-greedy over S s G a G . That is, at every time step, the agent selects the action a = arg max a S s G a G (s t , a) with probability 1-ϵ, or a random action otherwise. As discussed in the previous section, any ϵ-greedy policy with ϵ > 0 is sufficient to meet the criteria of Theorem 1.Our exploration strategy can be applied to any off-policy algorithm where the temporal-difference update of Eq. ( 2) and ( 10) is guaranteed to convergence under the GLIE assumption (pseudocode for Q-Learning in Appendix A.5). Most importantly, our exploration does not suffer from the limitations of optimism discussed in Section 2.2 -the agent will eventually explore all state-action pairs even when rewards are partially observable, because exploration is not influenced by the Q-function (and, thus, by rewards), but fully driven by the S-function. Consider the example in Figure 1b again, and an optimistic agent (i.e., with high initial Q) that learns a reward model and uses its estimate when rewards are not observable. As discussed, classic exploration strategies will likely fail -their exploration is driven by Q that can be highly inaccurate, either because of its optimistic estimate or because the reward model queried for Q-updates is inaccurate (and will stay so without proper exploration). This can easily lead to premature convergence to a suboptimal policy (to collect the left coin). On the contrary, if the agent follows our exploration strategy it will always push the button, discover the large coin, and eventually learn the optimal policy -it does not matter if Q is initialized optimistically high and would (wrongly) believe that collecting the left coin is optimal, because the agent follows S. And even if S is initialized optimistically (or even randomly), the indicator reward 1 of Eq. ( 10) is always observable, thus the agent can always update S at every step. As S becomes more accurate, the agent will eventually explore optimally, i.e., maximizing visitation occurrences -it will be able to visit states more efficiently, to observe rewards more frequently and update its reward model properly, and thus to update Q estimates with accurate rewards. To summarize, the explicitly decoupling of exploration ( S) and exploitation ( Q) together with the use of SR (whose reward is always observable) is the key of our algorithm. Experiments in the next section empirically validate both the failure of classic exploration strategies and the success of ours. In Appendix B.4 we further report a deeper analysis on a benchmark similar to the example of Figure 1 .Related Work. In reward-free RL, Jin et al. [26] proposed an algorithm where the agent explores by maximizing SR rewards. After collecting a sufficient amount of data, the agent no longer interacts with the environment and uses the data to learn policies maximizing different reward functions. In model-based RL, the agent of Hu et al. [23] alternates between exploration and exploitation at every training episode. During exploration, the agent follows a goal-conditioned policy randomly sampled from a replay buffer with the goal of minimizing the number of actions needed to reach a goal. Finally, in sparse-reward RL, Parisi et al. [54] learn two value functions -one using extrinsic sparse rewards, one using dense visitation-count rewards -and combine them to derive a UCB-like exploration policy. While the use of SR of Jin et al. [26] , the goal-conditioned policies of Hu et al. [23] , and the interaction of two separate value functions of Parisi et al. [54] are related to our work, there are significant differences to what we presented in this paper. First, our directed exploration does not strictly separate exploration and exploitation into two phases [26] or between episodes [23] , but rather interleaves them step-by-step using either the Q-function or the S-functions. However, the two value functions are never combined together [54] , as the agent follows either one or the other according to the coefficient β t . Second, our goal-conditioned policy is chosen according to the least-visited state-action pair, rather than randomly sampled from a set [26] or from a replay buffer [23] . Third, none of them have considered the setting of Mon-MDPs and partially observable rewards.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experiments: 
 Empty Hazard One-WayFigure 4 : Environments. The goal is to collect the large coin (r E t = 1) instead of small "distracting" coins (r E t = 0.1). In Hazard, the agent must avoid quicksand (it prevents any movement) and toxic clouds (r E t = -10). In One-Way, the agent must walk over toxic clouds (r E t = -0.1) to get the large coin. In River Swim, the stochastic transition pushes the agent to the left. More details in Appendix A.2.We validate our exploration strategy on tabular MDPs (Figure 4 ) characterized by different challenges, e.g., sparse rewards, distracting rewards, stochastic transitions. For each MDP, we propose the following Mon-MDP versions of increasing difficulty. The first has a simple random monitor, where positive and negative rewards are unobservable (r E t = ⊥) with probability 50% and observable otherwise (r E t = r E t ), while zero-rewards are always observable. In the second, the agent can ask to observe the current reward at a cost (r M t = -0.2). In the third, the agent can turn monitoring ON/OFF by pushing a button in the top-left cell, and if s M t = ON the agent pays a cost (r M t = -0.2) and observes rE t = r E t . In the fourth, there are many experts the agent can ask for rewards from at a cost (r M t = -0.2), but only a random one is available at the time. In the fifth and last, the agent has to level up the monitor state by doing a correct sequence of costly (r M t = -0.2) monitor actions to observe rewards (a wrong action resets the level). In all Mon-MDPs, the optimal policy does not need monitoring (r M t = -0.2 to observe rE t = r E t ). However, prematurely doing so would prevent observing rewards and, thus, learning Q * . More experiments on more environments are presented in Appendix B.Baselines. We evaluate Q-Learning with the following exploration policies (details in Appendix A.5): (1) ours; (2) greedy with optimistic initialization; (3) naive ϵ-greedy; (4) ϵ-greedy with count-based intrinsic reward [9] ; (5) ϵ-greedy with UCB bonus [4] ; (6) ϵ-greedy with Q-Counts [54] . Note that if rewards and transitions are deterministic and fully observable, then (2) is very efficient [17, 75, 77] , thus serves as best-case scenario baseline. For all algorithms, γ = 0.99 and ϵ t starts at 1 and linearly decays to 0. Because in Mon-MDPs environment rewards are always unobservable for some monitor state-action pairs (e.g., when the monitor is OFF), all algorithms learn a reward model to replace rE t = ⊥, initialized to random values in [-0.1, 0.1] and updated when rE t ̸ = ⊥.7 Why Is This Hard? Q-function updates rely on the reward model, but the model is inaccurate at the beginning. To learn the reward model and produce accurate updates the agent must perform suboptimal actions and observe rewards. This results in a vicious cycle in exploration strategies that rely on the Q-function: the agent must explore to learn the reward model, but the Q-function will mislead the agent and provide unreliable exploration (especially if optimistic).Results. For each baseline, we test the greedy policy at regular intervals (full details in Appendix A). Figure 5 shows that Our exploration outperforms all the baselines, being the only one converging to the optimal policy in the vast majority of the seeds for all environments and monitors. When Figure 5 : Episode return (r E t + r M t ) of greedy policies averaged over 100 seeds (shades denote 95% confidence interval). Our exploration clearly outperforms all baselines, as it is the only one learning in all Mon-MDPs. Indeed, while all baselines learn relatively quickly when rewards are fully observable (first column), their performance drastically decreases with rewards partial observability. the environment is deterministic and rewards are always observable (first column), pure Optimism is optimal (as expected). However, if the environment is stochastic (River Swim) or rewards are unobservable, Optimism fails. Even just random observability of the reward (second column) is enough to cause convergence to suboptimal policies -without observing rewards the agent must rely on its model estimates, but these are initially wrong and mislead Q updates, preventing exploration. Even though mitigated by the ϵ-randomness, exploration with Q-Counts, UCB, Intrinsic Reward, and Naive is suboptimal as well, as these baselines learn suboptimal policies in most of the seeds, especially in harder Mon-MDPs. On the contrary, Our exploration is only slightly affected by the rewards unobservability because it relies on S rather than Q -the agent visits all state-action pairs as uniformly as possible, observes rewards frequently, and ultimately learns accurate Q that make the policy optimal. Figure 6 strengthens these results, showing that indeed Our exploration observes significantly more rewards than the baselines in all Mon-MDPs -because we decouple exploration and exploitation, and exploration does not depend on Q, Our agent does not avoid suboptimal actions and discovers more rewards. 8 More plots and discussion in Appendix B. Source code at https://github.com/AmiiThinks/mon_mdp_neurips24. 
discussion: 
 In this paper, we discussed the challenges of exploration when the agent cannot observe the outcome of its actions, and highlighted the limitations of existing approaches. While partial monitoring is a well-known and studied framework for bandits, prior work in MDPs with unobservable rewards is still limited. To fill this gap, we proposed a paradigm change in the exploration-exploitation trade-off and investigated its efficacy on Mon-MDPs, a general framework where the reward observability is governed by a separate process the agent interacts with. Rather than relying on optimism, intrinsic motivation, or confidence bounds, our approach explicitly decouples exploration and exploitation through a separate goal-conditioned policy that is fully in charge of exploration. We proved the convergence of this paradigm under some assumptions, presented a suitable goal-conditioned policy based on the successor representation, and validated it on a collection of MDPs and Mon-MDPs. Advantages. Directed exploration via the S-functions benefits from implicitly estimating the dynamics of the environment and being independent of the reward observability. First, the focus on the environment (states, actions, and dynamics) rather than on rewards or optimism (e.g., optimistic value functions) disentangles efficient exploration from imperfect or absent feedback -not observing the rewards may compromise exploratory strategies that rely on them. Second, the goal-conditioned policy learns to explore the environment regardless of the reward, i.e., of a task. This has potential application in transfer RL, in the same spirit of prior use of the successor representation [6, 19, 38, 61] . Third, the goal-conditioned policy can guide the agent to any desired goal state-action pair, and by choosing the least-visited pair as the goal the agent implicitly explores as uniformly as possible. Limitations and Future Work. First, we considered tabular MDPs, thus we plan to follow up on continuous MDPs. This will require extending the S-function and the visitation count to continuous spaces, e.g., by following prior work on universal value function approximators [64] , successor features [43, 61] , and pseudocounts [42, 46, 78] . For example, the finite set of S-functions S siaj (s t , a t ) could be replaced by a neural network S(s t , a t , s i , a j ). For discrete actions, the network would take the (current state, goal state) pair and output the value for all (action, goal action) pairs, similarly to how deep Q-networks [48] work. Extending visitation counts to continuous spaces is more challenging, because Algorithm 1 relies on the min operator to select the goal. To make it tractable, one solution would be to store samples into a replay buffer and prioritize sampling according to pseudocounts, similarly to what prioritized experience replay does with TD errors [65] . Second, our exploration policy requires some stochasticity to explore as we learn the S-functions. In our experiments, we used ϵ-greedy noise for a fair comparison against the baselines, but there may be better alternatives (e.g., "balanced wandering" [27] ) that could improve our exploration. Third, we assumed that the MDP has a bounded goal-relative diameter but this may not be true, e.g., in weakly-communicating MDPs [18, 59] . Thus, we will devote future work developing algorithms for less-constrained MDPs, following recent advances in convergence of reward-free algorithms [12] . Finally, we focused on model-free RL (i.e., Q-Learning) but we believe that our exploration strategy can benefit from model-based approaches. For example, we could use algorithms like UCRL [3, 24] to learn the S-functions (not the Q-function), whose indicator reward is always observable. And, by learning the model of the monitor, the agent could plan what rewards to observe (e.g., the leastobserved) rather than what state-action pair to visit. Furthermore, our strategy could be combined with model-based methods where exploration is driven by uncertainty [45, 74] rather than visits. That would allow the agent to plan visits to states where rewards are more likely to be observed. A Experiments DetailsSource code at https://github.com/AmiiThinks/mon_mdp_neurips24. We ran our experiments on a SLURM-based cluster, using 32 Intel E5-2683 v4 Broadwell @ 2.1GHz CPUs. One single run took between 3 to 45 minutes on a single core, depending on the size of the environment and the number of training steps. Runs were parallelized whenever possible.In all environments except River Swim, the environment actions are a E ∈ {LEFT, RIGHT, UP, DOWN, STAY}, and the agent starts in the position pictured in Figure 7 . The environment reward depends on the current state and action as follows.• Coin cells: STAY gives a positive reward (r E t = 0.1 for small coins, r E t = 1 for large ones) and end the episode.• Toxic cloud cells: any action gives a negative reward (r E t = -0.1 for small coins, r E t = -10 for large ones).• Any other cell: r E t = 0. The agent can move away from its current cell or stay, but some cells have special dynamics. • In quicksand cells, any action can fail with 90% probability. These cells can easily prevent exploration, because the agent can get stuck and waste time. • In arrowed cells, only the corresponding action succeeds. For example, if the agent is in a cell pointing to the left, the only action to move away from it is LEFT. In practice, they force the agent to take a specific path to reach the goal (e.g., in One-Way), or divide the environment in rooms (e.g., in Two-Rooms). In all environments, the goal is to follow the shortest path to the large coin and STAY there. Below we discuss the characteristics and challenges of the first seven environments. Episodes end when the agent collects a coin or after a step limit (in brackets after the environment name and its grid size).• Empty (6×6; 50 steps). This is a classic benchmark for exploration in RL with sparse rewards.There are no intermediate rewards between the initial position (top-left) and the large reward (bottom-right). Furthermore, the small coin in the bottom-left can "distract" the agent and cause convergence to a suboptimal policy. • Loop (3×3; 50 steps). The large coin can be reached easily, but if the agent wants to visit the top-right cell is forced to follow the arrowed "loop". Algorithms that explore inefficiently or for too long can end up visiting those states too often. • Hazard (4×4; 50). Because of the toxic clouds, the optimal path is to walk following the edges of the grid. Along the way, however, the agent may find the a small coin and converge to a suboptimal policie, or get stuck in the quicksand cell. • One-Way (3×4; 50 steps). The only way to reach the large coin is to walk past small toxic clouds.Because of their negative reward, shallow exploration strategies can prematurely decide not to explore further and never discover the large coin. The presence of an easy-to-reach small coin can also cause convergence to a suboptimal policy. • Corridor (20; 200 steps). This is a flat variant of the environment presented by Klissarov and Machado [30] . Because of the length of the corridor, the agent requires persistent deep exploration from the start (leftmost cell) to the large coin (rightmost cell) to learn the optimal policy. Naive dithering exploration strategies like ϵ-greedy are known to be extremely inefficient for this. • Two-Room (2×11; 200 steps). The arrowed cells divide the grid into two rooms, one with a small coin and one with a large coin. If exploration relies too much on randomness or value estimates, the agent may converge to the suboptimal policy collecting the small coin. • Two-Room (3×5; 50 steps). The arrowed cell divides the grid into two rooms, and moving from one room to another may be hard if the agent gets stuck in the quicksand cell.River Swim is different from the other seven environments because the agent can only move LEFT and RIGHT, and there are no terminal states. This environment was originally presented by Strehl and Littman [72] and later became a common benchmark for exploration in RL, although often with different transition and reward functions. Here, we implement the version in Figure 8 . There is a small positive reward for doing LEFT in the leftmost cell (acting as local optima) and a large one for doing RIGHT in the rightmost cell. The transition is stochastic and RIGHT has a high chance of failing in every cell, either not moving the agent or pushing it back to the left. The initial position is either state 1 or 2. Although this is an infinite-horizon MDP, i.e., no state is terminal, we reset episodes after 200 steps. The optimal policy always does RIGHT.0 1 2 3 4 5 (L, 1, 0.01) (R, 0.6, 0) (R, 0.6, 0) (R, 0.6, 0) (R, 0.6, 0) (L, 1, 0) (R, 0.05, 0) (L, 1, 0) (R, 0.05, 0) (L, 1, 0) (R, 0.05, 0) (L, 1, 0) (R, 0.05, 0) (L, 1, 0) (R, 0.4, 0) (R, 0.4, 0) (R, 0.6, 1) (R, 0.6, 0) (R, 0.35, 0) (R, 0.35, 0) (R, 0.35, 0) (R, 0.35, 0)Figure 8 : River Swim reward and transition functions. Each tuple represents (action, probability, reward) and arrows specify the corresponding transition. For example, doing RIGHT in state 0 has 60% chance of moving the agent to 1 and 40% chance of keeping it in 0. In both cases, the reward is 0. In state 5 the transition probability is the same, but if RIGHT succeeds the reward is 1.• Random Monitor. There is no monitor state, action, nor reward. Positive (coin) and negative (toxic cloud) environment rewards are unobservable with probability 50% (r E t = ⊥) and fully observable otherwise (r E t = r E t ). Zero-rewards in other cells are always observable. • Ask Monitor. The monitor is always OFF. The agent can observe the current environment reward with an explicit monitor action at a cost.S M := {OFF} A M := {ASK, NO-OP} s M t+1 = OFF, t ≥ 0 rE t = r E t if a M t = ASK ⊥ otherwise r M t = -0.2 if a M t = ASK 0 otherwise• Button Monitor. The monitor is turned ON/OFF by pushing a button in the starting cell (except for River Swim, where the button is in state 0). The agent can do that with a E = LEFT, i.e., the agent has no dedicated monitor action. Having the monitor ON is costly, and leaving it ON when collecting a coin results in an extra cost. Because the initial monitor state is random, the optimal policy always turns it OFF before collecting the large coin. S M := {ON, OFF} A M := {NO-OP} s M 1 = random uniform in S M s M t+1 =    ON if s M t = OFF and s E t = BUTTON-CELL and a E t = LEFT OFF if s M t = ON and s E t = BUTTON-CELL and a E t = LEFT s M t otherwise rE t = r E t if s M t = ON ⊥ otherwise r M t =    -0.2 if s M t = ON -2 if s M t = ONM t+1 = random uniform in S M , t ≥ 0 rE t = r E t if a M t = s M t ⊥ otherwise r M t = -0.2 if a M t = s M t 0.001 otherwise In our experiments, n = 4. An optimal policy collects the large coin while never matching monitor states and actions, in order to receive small positive monitor rewards along the way. However, prematurely deciding to be greedy with respect to monitor rewards will result in never observing environment rewards, thus not learning how to collect coins. We also note that this monitor has larger state and action spaces than the others, and a stochastic transition.• Level Up Monitor. The monitor has n states, each representing a "level", and n + 1 actions. The first n actions are costly and needed to "level up" the state, while the last is NO-OP. The initial level is random. To level up, the agent's action must match the state, e.g., if s M t = 1 and a M t = 1, then s M t+1 = 2. However, if the agent executes the wrong action, the level resets to s M t+1 = 1. Environment rewards will become visible only when the monitor level is n. Leveling up the monitor is costly, and only a M t = NO-OP is cost-free. S M := {1, . . . , n} A M := {1, . . . , n, NO-OP}s M t+1 =    max(s M t + 1, n) if s M t = a M t s M t if a M t = NO-OP 1 otherwise rE t = r E t if s M t = n ⊥ otherwise r M t = 0 if a M t = NO-OP -0.2 otherwiseThe optimal policy always does a M t = NO-OP to avoid negative monitor rewards. Yet, without leveling up the monitor, the agent cannot observe rewards and learn about environment rewards in the first place. Furthermore, the need to do a correct sequence of actions to observe rewards elicits deep exploration.All algorithms are trained over the same amount of steps, but this depends on the environment and the monitor as reported in Table 1 . As the agent explores and learns, we test the greedy policies at regular intervals for a total of 1,000 testing points. For example, in River Swim with the Button Monitor the agent learns for 40,000 steps, therefore we test the greedy policy every 40 training steps. Every testing point is an evaluation of the greedy policy over 1 episode (for fully deterministic environments and monitors) or 100 (for environments and monitors with stochastic transition or initial state, i.e., Hazard, Two-Room (3×5), River Swim; Button, Random Experts, Level Up). t , a E t , rE t , s E t+1 , s M t , a M t , r M t , s M t+1 }, α t , N r , R, Q, γ if rE t ̸ = ⊥ then N r (s E t , a E t ) ← N r (s E t , a E t ) + 1 R(s E t , a E t ) ← (N r (s E t ,a E t ) -1) R(s E t ,a E t ) + rE t N r (s E t ,a E t ) s t ← (s E t , s M t ) a t ← (a E t , a M t ) r t ← R(s E t , a E t ) + r M t return Q(s t , a t ) ← (1 -α t ) Q(s t , a t ) + α t r t + γmax a Q(s t+1 , a) A.All baselines evaluated in Section 4 use Q-Learning with reward model to compensate for unobservable rewards in Mon-MDPs (r E t = ⊥), as outlined in Algorithm 2. Because there is always a monitor state-action pair for which all environment rewards are observable, Q-Learning with reward model will converge given enough exploration [55] . The reward model is a table R(s E , r E ) initialized to random values in [-0.1, 0.1] that keeps track of the running average of observed proxy rewardevery time a reward is observed, a count N r (s E , s E ) is increased and the entry R(s E , r E ) is updated.The differences between the baselines lie in their exploration policies, as described below and outlined in Algorithms 3, 4 and 5.• Ours. As described in Algorithm 1, with β = 0.01. The goal-conditioned policy ρ is ϵ-greedy over S s G a G (s t , a). The S-function is initialized optimistically to S siaj (s, a) = 1 ∀(s, a, s i , a j ).• Optimism. Exploration is pure greedy, i.e., a t = arg max a Q(s t , a).• UCB. Exploration is ϵ-greedy over the UCB estimate Q(s t , a) + 2 log a N (st, a) /N(st, a) [4] .• Q-Counts. This baseline learns a separate Q-function Q C (s, a) using N (s t , a t ) as rewards, i.e.,EQUATION)This function is initialized to Q C (s, a) = 0 ∀(s, a), and intuitively estimates and minimizes "cumulative visitation counts" [54] . The exploration policy then replaces N (s, a) with Q C (s, a) in the UCB estimate, favoring actions that result in low cumulative counts rather than low immediate counts. Formally, the exploration is ϵ-greedy over Q(s t , a) + 2 log a QC(st, a)/ QC(st, a).• Intrinsic. Exploration is ϵ-greedy over Q(s t , a). The Q-function is trained with intrinsic reward 0.01 / N (st, at) [9] .• Naive. Exploration is ϵ-greedy over Q(s t , a).When two or more actions have the same value estimate -whetherQ(s t , a), S s G a G (s t , a), or Q(s t , a)with UCB bonuses) -ties are broken randomly.Below are the learning hyperparameters.• The schedule ϵ t starts at 1 and linearly decays to 0 throughout all training steps. For all algorithms, this performed better than the following schedules: linear decay from 0.5 to 0, linear decay from 0.2 to 0, constant 0.2, constant 0.1. • The schedule α t depends on the environment: constant 0.5 for Hazard and Two-Room (3×5) (because of the quicksand cell), linear decay from 0.5 to 0.05 in River Swim (because of the stochastic transition), and constant 1 otherwise. For the Random Experts Monitor we linearly decay the learning rate to 0.1 in all environments (0.05 in River Swim) because of the random monitor state. • Discount factor γ = 0.99.EQUATIONAlgorithm 4: Our Q-Learning with S-functionsEQUATIONs_update(s t , a t , s t+1 , α) // Eq. ( 10)EQUATIONq_count_update(s t , a t , s t+1 , N, α) // Eq. (11) Note that the discount factor γ and the learning rate α t in Eq. ( 2), (10) , and ( 11) can be different, e.g., a higher learning rate to update Q and a smaller for S. In our experiment, we use the same γ and α t for both Q, S, andQ C .The Q-function is initialized optimistically to Q(s, a) = 1 ∀(s, a) (first seven environments) and Q(s, a) = 50 ∀(s, a) (River Swim) for all algorithms except Ours, where it is initialized pessimistically to Q(s, a) = -10 ∀(s, a) (all environments). This performed better than optimistic initialization because it mitigates overestimation bias, that can be more prominent with optimism [49] . From our experiments, this is especially true in Mon-MDPs, where the reward model used to compensate for unobservable rewards can be inaccurate and lead to overly optimistic value estimates. We also tried the same pessimistic Q initialization for UCB, Q-Counts, Intrinsic, and Naive, but their performance was significantly worse. Most of the time, in fact, the "distracting" small coins were causing premature convergence to suboptimal policies. Figure 9 : Episode return (r E t + r M t ) of greedy policies averaged over 100 seeds (shades denote 95% confidence interval).Figure 10 shows how many rewards the agent observes (r E t ̸ = ⊥) during training. When rewards are fully observable (first column) this is equal to the number of training steps. If reward observability is random and the agent cannot control it (second column), all the baselines still perform relatively well. However, when the agent has to act to observe rewards -and these actions are suboptimal, e.g. costly requests or pushing a button -results clearly show that Optimism, UCB, Q-Counts, Intrinsic, and Naive do not observe many rewards. Most of the time, in fact, they explore the environment only when rewards are observable, and therefore converge to suboptimal policies. As discussed throughout the paper, in fact, if the agent must perform suboptimal actions to gain information, classic approaches are likely to fail. Our exploration strategy, instead, actively explores all state-action pairs uniformly, including the ones where actions are suboptimal yet allow to observe rewards. For the sake of clarity, we report it as β t = 10 in this plot. Even if it did not reach the threshold β = 0.01 (bottom line in black), the ratio clearly decreases over time, a further sign that the agent explores all state-action pairs uniformly (i.e., maximizing the occurrence of the least-visited pair). Note that in small environments (e.g., River Swim) β t decreases faster than in large environment (e.g., Empty).Training Steps (1e 3 )Figure 12 : Explore-exploit ratio β t = log t /min N (s, a) (in logscale) during a run on RiverSwim with Button Monitor. For the sake of clarity, we replaced β t = ∞ (when min N (s, a) = 0) with β t = 10. For roughly the first 8,000 steps, β t trend is "irregular" -it goes down when the current state-action goal is visited, and then up until the new goal is visited. Later, these "up/down steps" become smaller and smaller and β t consistently decreases. This denotes that S become more and more accurate, thus the policy ρ can bring the agent to the goal (i.e., the least-visited state-action pair) faster.Figure 11 shows the trend of the exploration-exploitation ratio β t (in log-scale) of Our exploration policy. The decay denotes that, indeed, the policy explores uniformly and efficiently, maximizing the occurrence of the least-visited state-action pair. The fact that β t did not reach the threshold β explains why in Figure 10 the agent keeps exploring and observing rewards, while the greedy policy in Figure 9 is already optimal. In Figure 12 we further show the trend of β t on one run on River Swim with the Button Monitor. After some time spent learning the S-functions S, the trend consistently decreases, denoting that the agent has learned to quickly visit any state-action pair. ). On the contrary, all the other baselines explore poorly (less smooth heatmaps and much larger range). Indeed, they do not visit most environment state-action pairs when the monitor is ON (some have never been visited and have count 0). Having the monitor ON, in fact, is suboptimal (r M t = -0.2), yet needed to observe rewards. This further explains why they observe much fewer rewards in Figure 10 .Here, we investigate more in detail the results for River Swim with Button Monitor, a benchmark similar to the example in Figure 1 discussed throughout the paper. States are enumerated from 0 to 5 as in Figure 8 , the agent starts either in state 1 or 2, the button is located in state 0 and can be turned ON/OFF by doing LEFT in state 0. Figure 13 shows the visitation count and Figure 14 the Q-function for all state-action pairs. Optimism barely explores with monitoring ON. This is expected, because observing rewards is costly (negative monitor reward), and pure optimistic exploration does not select suboptimal actions (but this is the only way to discover higher rewards). UCB, Q-counts, Intrinsic, and Naive mitigate this problem thanks to ϵ-randomness, but still do not explore properly and, ultimately, do not learn accurate Q-functions. On the contrary, Our policy explores the whole state-action space as uniformly as possible 9 , observes rewards frequently (because it visits states with monitoring ON), and learns a close approximation of Q * that results in the optimal greedy policy.  
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification: We provide all needed details in the Appendix.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes]Justification: For all plots we show the 95% confidence interval over 100 seeds.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [Yes] Justification: Computational details are provided in the Appendix. Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? Answer: [Yes] Justification: Our work is mostly theoretical and experiments are conducted on simple environments that do not involve human participants or concerning datasets. We believe that our contribution has no potential harmful impact. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] Justification: Our work is mostly theoretical, experiments are conducted on simple environments, and it is not tied to particular applications. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [NA] Justification: Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.This example is just illustrative. In general, the monitor states and actions can be more heterogeneous. For example, the agent could observe rewards by collecting and using a device or asking a human expert, and the monitor state could include the battery of the device or the location of the expert. Similarly, the monitor reward is not constrained to be negative and its design depends on the agent's desired behavior.Recall that s and a denote either the classic state and action in MDPs, or the joint state s := (s E , s M ) and action a := (a E , a M ) in Mon-MDPs.Jaksch et al.[24] defined a diameter that is a property of the MDP irrespective of any (goal-directed) policy. Their MDP diameter can be thought of as the smallest possible bound on the goal-relative diameter for any ρ.For Mon-MDPs, convergence is guaranteed under the assumptions discussed in Footnote 2 .In deterministic MDPs, maximizing discounted occurrences is equivalent to minimizing the (expected) time-to-visit. However, this is not always true in stochastic MDPs, with discounted occurrences tending to ignore long time-to-visit outliers, making the agent more risk-seeing than expected time-to-visit. Nonetheless, in both cases, goal-conditioned policies have bounded goal-relative diameter as long as the MDP is communicating.Because for every environment reward there is a monitor state-action pair for which the reward is observable (i.e., s M t = ON), Q-Learning is guaranteed to converge given infinite exploration[55].Note that Our agent keeps exploring and observing rewards (Figure6) because βt did not reach the exploit threshold β (but still decays quickly, see Appendix B.3), even if its greedy policy is already optimal (Figure5).Note that the agent starts in state 1 or 2 and the transition is likely to push the agent to the left, thus states on the left are naturally visited more often. 
 
 Appendix:  


Decision: The paper studies a recently introduced class of sequential decision problems called Monitored MDPs, and argues that the principle of optimism in the face of uncertainty leads to sub-optimal exploration when the rewards are unobservable. The authors show instead that a goal-conditioned exploration strategy can resolve uncertainty correctly even when rewards are unobserved, and show empirically across RL benchmarks (including new ones with partially observable rewards) that the proposed techniques outperform standard RL baselines.

The reviewers raised several clarifying questions, that the authors answered convincingly in their rebuttal. Including the discussions in the paper revision will substantially strengthen the paper. There is some uncertainty whether an additional baseline (separate Q-functions trained for a different intrinsic reward) will substantially change the conclusions from the experiments; but all the reviewers agree that nevertheless the paper's theoretical contributions to our understanding of Monitored MDPs (and partial monitoring bandits) are likely to be of independent interest to the RL community.

Reviews: review: paper_summary: paper_summary: This paper considers the Reinforcement Learning problem in Monitored MDPs. Monitored MDPs are a formalism that has been recently introduced by Parisi et al. (AAMAS 2024), in which the value of the policy is computed on the rewards generated by the environment and those produced by a "monitor". However, the agent cannot directly observe the rewards generated by the environment, because the monitor can modify the reward observed by the agent. The authors propose an algorithm for Monitored MDPs, which alternates explicit exploration and exploitation. The method has been validated against some classic RL algorithms and variants.
strength_weakness: strength_weakness: 1- Corollary 1 is the only formal guarantee regarding the performance of the algorithm that has been obtained in the paper. However, this only involves the asympotic convergence. Moreover, the proof relies on the fact that the algorithm is an exploratory policy that becomes greedy in the limit. This fact does not seem to suffice for obtaining $\hat{Q} \to Q^*$, because the monitor may arbitrarily modify the reward used for constructing $\hat{Q}$. I believe there is an implicit (but missing) assumption that the monitor may only hide rewards, and that rewards will be shown in all states an infinite number of times.

2- The evaluation compares the algorithm with other 4 baselines in some environments. However, none of the baselines have been specifically designed for Monitored MDP, nor for any component of partial observability on rewards, and it is unsurprising that many of these do not perform well. As such,the experimental evaluation gives little insights about the improvement that the proposed algorithm leads among Monitored MDP algorithms. If RL algorithms for this class do not exist yet, because the formalism is recent, then it should be also compared with algorithms are  aware that rewards are partially observable, or nonstationary. Finally, the black line, which is Q-learning with optimistic initialization, is taken as a representative of "optimism". However, this is only a specific instance of optimistic approaches, and I believe that "optimism" would be better represented by UCB-style RL algorithms.

3- The contribution of the paper is limited for the following reasons:

  a- The algorithm mostly succeeds because it tries to reach all states of the MDPs via explicit exploration. This is generally intractable for large state spaces, or MDPs with high (or infinite) diameter. Optimism solves this issue by avoiding exhaustive exploration. This makes the idea behind the algorithm more naive than other existing optimistic approaches, especially for larger state spaces or small probabilities. Indeed, the algorithm does not seem to directly address the fact that a monitor is present, even though it has this prior information available.

  b- The use of Successor Representation made in the paper is mostly standard in the literature. The authors say that only Machado et al. [40] used SR to drive exploration. However, we should consider that using SR as value functions is completely equivalent to placing unit rewards in goal states. Then, similar approaches are taken by the works in goal-conditioned RL that learn goals using unit rewards, even though SR are not explicitly mentioned in those papers.
questions: questions: 4- Why does the UCB baseline use an epsilon-greedy policy? I would expect bonuses to be sufficient for exploration. Epsilon-greedy may unnecessarily show it down.

The authors may also address any of the weaknesses above, especially number 1.
limitations: limitations: Most limitations have been already discussed in the paper. The work has no direct societal impact.
paper_summary: paper_summary: The authors propose a novel exploration strategy for Mon-MDPs based on two policies; a goal-conditioned exploration policy and an exploitation policy which maximizes the underlying reward. The proposed algorithm alternates between the two policies, naturally trading off exploration and exploitation.
They show that the proposed strategy is consistent and outperforms standard exploration approaches such as optimistic exploration.
strength_weakness: strength_weakness: There are works in reward-free RL [1, 2] and active learning in RL [3, 5] for general continuous state-action spaces that the authors should mention. Since their strategy is based on an explore and exploit approach, intuitively, it seems that works such as [4] can be seamlessly applied to the Mon-MDP setup. Also, from my understanding, the intrinsic reward proposed in [4] is not myopic and is also consistent, in the sense that it leads to convergence guarantees for learning the MDP. Hence, I am not sure I agree with the authors' statement on lines 154 -- 155.

There are also works on goal-conditioned RL such as [5, 6] that build on a similar idea for picking and exploring novel goals for exploration. While they do not consider the Mon-MDP setting, I think they are still somewhat relevant to prior work.

The authors should write the rate of convergence in the main theorem statement of Theorem 1.

[1] Jin, Chi, et al. "Reward-free exploration for reinforcement learning." International Conference on Machine Learning. PMLR, 2020.
[2] Chen, Jinglin, et al. "On the statistical efficiency of reward-free exploration in non-linear rl." Advances in Neural Information Processing Systems 35 (2022): 20960-20973.
[3] Mania, Horia, Michael I. Jordan, and Benjamin Recht. "Active learning for nonlinear system identification with guarantees." arXiv preprint arXiv:2006.10277 (2020).
[4] Sukhija, Bhavya et al. "Optimistic active exploration of dynamical systems." Advances in Neural Information Processing Systems 36 (2023): 38122-38153.
[5] Nair, Ashvin V., et al. "Visual reinforcement learning with imagined goals." Advances in neural information processing systems 31 (2018).
[6] Hu, Edward S., et al. "Planning goals for exploration." arXiv preprint arXiv:2303.13002 (2023).
questions: questions: 1. Instead of a goal-conditioned policy, could one not train a policy with $1/N_t(s, a)$ as reward (or $-N_t(s, a)$)? In essence, this policy will try to visit states that have a low visitation count. While the reward in this setting is non-stationary, empirically this might perform better. What do the authors think about it?

2. Could [4] from above be used for active learning of dynamics and then later exploitation for general continuous state-action spaces with Mon-MDPs? Moreover, I am curious if any general active learning/reward-free RL algorithm can be combined with greedy exploitation to obtain convergence guarantees for Mon-MDPs.


I am happy to increase my score if my concerns and questions above are adequately addressed.
limitations: limitations: The authors address the limitations of their work in the main paper (lines 336  -- 349).
paper_summary: paper_summary: This paper tackles the problem of exploration in MDPs where the reward is unobservable. For this, the authors perform goal conditioned exploration, i.e., the environment is explored according to how often a specified goal is reached.  The authors propose an exploitation-exploration mechanism based on learning goal-conditioned policies. Policies are switched as visitation counts increase for goal state-action pair for a give goal conditioned policy. Moreover, the authors propose learning separate value functions via successor features for each goal conditioned policy. Overall, this mitigates the unobserved reward problem since the reward is not crucial anymore to solving the environment.  In the environments proposed by the authors their approach outperforms other classic exploration methods especially when rewards unobserved, e.g., the reward is only given if the agent elicits a mechanism first.
strength_weakness: strength_weakness: - What makes the Mon-MDP different to a sparse rewards problem where a reward is only given at the end or reward free exploration for that matter? Shouldn’t your method be compared with other popular (intrinsic) exploration methods?
- Although the algorithm is effective in tabular spaces it seems non-trivial to expand it to continuous or high-dimensions. The author mention their intentions and cite papers but do not elaborate on for instance how to systematically choose goals in high-dimensional spaces.
- There seem to be no other Mon-MDP specific methods that have been compared against. Are there any other methods?
questions: questions: Questions: 
- What is the main contribution of the paper? Are the successor features crucial or is it the exploration-exploitation mechanism? The authors motivate the problem very well, but I feel it is not exactly explained why these two components are crucial to improved performance in Mon-MDPS
- The authors propose their own set of environments to test their method with success. Are there any other known environments that benefit from the paradigm of unobserved rewards?
- Why do the other methods struggle so much on the empty environment? Is it because the sparse reward problem is harder?
limitations: limitations: I think the authors have adequately addressed limitations in their work.
paper_summary: paper_summary: The paper studies the setting of finite state action MDPs with partially observable rewards. To formalize the framework they introduce Monitored MDPs. They introduce the algorithm that separates exploration and exploitation and prove that for a class of MDPs with finite goal-oriented diameter their algorithm is greedy in the limit with probability 1. For exploration they use Successor Function that maximizes the cumulative discounted occurrences of the targeted state-action pair. In their experiments they show that their algorithm successfully solves all the tried tasks, while the baselines in most cases don't, or solve with with considerably more training steps.
strength_weakness: strength_weakness: - When you introduce the "unobserved reward" it would be great to emphasize that that this is not a reward 0, but really the agent knows it hasn't observed it, i.e. he gets the reward $\perp$.
- For me it was not clear what is the agent state (i.e. what agents sees) in the setting of Monitored MDPs. Does he have acess to both the state of the environment and the monitor or just the environment? As far as I could understand it has to both and I would emhphasise that in the section where you introduce the Monitored MDPs.
- The statement that starts in line 174: "As the agent explores, if every state-action pair is visited infinitely often, $\log(t)$ will grow at a slower rate than $N_t(s, a)$, ..." is wrong. It might apply to your algorithm but as you state here is sounds like it holds in general, but that is not true. Consider the case when you visit one state only at the rate $\log(\log(t))$, you still visit it infinitely often but the visition rate is slower than $\log(t)$.
- To me corollary 1 is not clear why it holds. I understand the theorem 1, where you say that with your algorithm you will visit every state action pair infinitely often in the limit and that your policy is greedy in the limit, but I don't see why $\hat{Q}$ converges to $Q^*$, how do you update your $\hat{Q}$ from the data? Does the state in $Q$ function depend only on environment state or does it depends also on monitor state? (same for action)
- In line 240 you claim that with the policy that comes from successor-function you will visit the targeted state as fast as possible. I think that is not true. With this policy you will maximize the cumulative discounted occurrence. If you were to change your instance reward to $\mathbb{1} \\{(s_i, a_i) \in \cup_{j=t}^k \\{(s_j, a_j)\\}\\}$, i.e. the reward is 1 if you have reached the state action pair in the past, then you would solve the task faster, because in that case you don't care of staying in the state-action pair, but just going there as fast as possible.
- In line 280/281 you say that the agent will pay a cost of $-0.2$. Is the agent going to pay the price only when he pushes the button or in every step when the button is on?
questions: questions: Look at Weaknesses section.
limitations: limitations: Limitations have been adequately addressed.

Comments: title: Response to Author's rebuttal
About convergence rate and related work
Response to Author's rebuttal
comment: 1. I appreciate this important change. This assumption is very reasonable to assume and it would not limit the impact of the paper.

4. b) I said that this use of successor representations is mostly standard in goal-conditioned RL literature because from what concerns the policy $\rho$, the approach appears to be equivalent to learning $|SA|$ policies using Q-lerning, where a reward of 1 is placed in one state-action pair for each policy. The overall algorithm is still original, to the best of my knowledge. I mainly argue that the exploration strategy is not only related to directed exploration with SR features, but also goal-conditioned policies.

The other replies are also relevant.
My main remaining concern is that the technique "is generally intractable for large state spaces, or MDPs with high (or infinite) diameter.", given that the algorithm must learn a distinct policy for each state and action in the MDP.

Despite this significant limitation, the paper is well written, clear, correct and the results appear to be mostly reproducible. So, I have increased my evaluation to weak accept.
The fact that other baselines are not aware of the formalism highlights a hole in RL literature, i.e., the lack of algorithms for MDPs with partially-observable rewards (that are not trivial, e.g., the observability of rewards is not just binary but given by another MDP).  
While there exists reward-free algorithms, they split exploration and exploitation: first, a general exploration policy is learned (environment rewards do not exists at that time), and then tasks are learned. In our paper, we are interested in solving a given task for which rewards **do exists** but are not observable --- the agent is still being evaluated even though it cannot see (sometimes) the evaluation.  
We argue that this is an important hole in RL literature, and we discussed more on this in the general rebuttal.  
In particular, a major advantage of our algorithm is indeed not having two separate exploration/exploitation phases: even if sub-optimal at firtst, the goal-conditioned policies are still better visitation policies than classic ones.  
In this paper, we strived for simplicify and efficiency when we designed our algorithm. The main contribution is to highlight the failure of optimism in Mon-MDPs and the introduction of the general explore-exploit algorithm.  


SFs naturally satisfy the requirements of our goal-conditioned policy $\rho$ (Section 3, paragraph after Corollary 1) while being simple and straightfoward to implement. A policy maximizing the SFs will maximize the visitation of state-action pairs, while being completely independent from the Q-function (that, as discussed in our previous reply, can be highly inaccurate at the beginning).  
We don't claim this is the **best** way to address Mon-MPDs but certainly is effective, and it is a first step to fill the hole in RL literature.
I thank the authors for their exhaustive answer!

* I understand the relevance of Mon-MDPs and how they differ from sparse-rewards exploration much better now. 


* I share the same concern as reviewer DPys, where all other baselines tested are not aware of the formalism and thus naturally perform worse.  
* Also from reading the paper it does not become apparent to me why the goal directed exploration with successor representations is the best way to address the Mon-MDP formalism? I think this has to be very clear, since this seems to be the first concise method to address Mon-MDPs.

* Could you maybe elaborate on this? I think this would help me gain more confidence in the paper. 


Thank you!
Thanks for your explanation! My concerns have been addressed. I will raise my score accordingly.
Thanks, my concerns are clarified. While I would like to stick to my score for the paper, I have gained more confidence in the paper, i.e., I have increased my confidence from 3 to 5.
**About the convergence rate**

Getting a non-trivial convergence rate is likely not possible. The algorithm as presented uses $\epsilon$-greedy as the exploration method to learn the goal-conditioned S-functions. In the worst-case, this will admit $\epsilon$-greedy's poor convergence rate (and may take exponential-time in MDP size to even just visit the goal once). We could give a competitive convergence rate if optimal goal-conditioned S-functions are known in advance, but that didn't feel particularly informative.   
We could also replace the exploration mechanism (i.e., to follow $\rho$ and S-functions) within the exploration phase to use a more sophisticated mechanism, but we are explicitly aiming for a model-free algorithm so many choices common in literature are not suitable (e.g. MBIE, UCRL).  
For example, in [4], Lemma 13 refers to Eq. 16 where the problem considers the true transition function $f^*$, and the make use of it in Corollary 7. On the contrary, we don't learn any model, and we don't know the true S-function $S^*$ either. Even knowing $S^*$, we don't think Lemma 13 can be straightforwardly applied to our case.

We choose a model-free algorithm (Q-learning) because we wanted to keep the method as simple as possible, while demonstrating its effectiveness through experimentation rather than theory, particularly showing that it can handle partially observable reward settings like Mon-MDPs (where traditional MDP exploration mechanisms can fail).   
Maybe a middle-ground might be to present a convergence rate that implicitly depends on the convergence rate of whatever algorithm is used to learn the goal-conditioned S-functions. This could show how much is lost due to the goal-directed exploration component that is needed to handle Mon-MDPs. We would then continue with experiments showing its performance with the simple $\epsilon$-greedy mechanism (even though it's not theoretically well-motivated) showing its strong performance across the tested environments.  

There is another angle of analysis that is distinctly more difficult as it likely would need new theoretical machinery (beyond the scope of this work). In particularly, we believe that most of the advantage of our algorithm comes from the goal-conditioned policies finding sub-optimal but still useful visitation policies. These policies can still be used to dramatically accelerate the learning of the Q-functions, allowing fast exploitation possibly even before the S-functions have identified optimal exploration policies $\rho$. 
We believe that this is a great advantage of not breaking the problem into some explicit exploration-only phase (e.g., as in [1]). This would almost certainly need some instance-specific analysis, though.

Would the middle-ground option of a convergence rate that depended on the convergence rate of the goal-conditioned policy learning be a sufficient addition? In any case, we can add a more thorough discussion of this in the paper.



**About related work**

Yes, they could be combined with our approach. Maybe there has been some misunderstanding: we didn't mean that [3], [4], and [6] are unrelated, but just that they are different being model-based.

For example, [3] estimates uncertainty in the feature space and uses a model to plan a trajectory to high-uncertainty states. We use counts (rather than uncertainty) and don't plan trajectory, but instead follow one-step S-function values. While replacing uncertainty with counts could be straightforward, [3] still has an extra component (the model) that allows for more powerful long-term reasoning. 
We believe that combining our algorithm with [3] and [4] could be promising for future work. 

Regarding [6], the main similarity is the presence of a goal-conditioned policy for exploration, but their algorithm is still quite different (beside being model-based). 
First, [6] alternates between exploration and exploitation at every episode, while ours uses a more grounded criterion (the ratio $\beta). 
Second, the goal of their goal-conditioned policy is randomly sampled from the replay buffer and optimized via MPPI, while ours is the state-action pair with the lowest count.
Third, their reward for training the goal-conditioned policy is given only at the end of the trajectory and depends on the number of actions needed to reach the goal, while ours is given at every step by SRs. 

We'd like to stress once more, however, that we didn't mean to say that [3], [4], and [6] are unrelated, and we will reference them in the final version.
2. I think not having convergence rates is a drawback of the work. What is it that limits the authors from doing so? Intuitively, wouldn't a rate on the visitation frequency directly result in a rate for Theorem 1? This is what is at least shown in [4] (c.f., Lemma 13)

4. I am not sure if this is true for methods such as [3, 4]. In the end, they are similar in spirit to the proposed algorithm -- they visit the states where they have the highest uncertainty/lowest visitation count (exploration phase). In principle, they could be combined with a similar exploitation phase as proposed by the authors. Am I missing something here? In the end, this approach would be equivalent to the baseline discussed in the third point. Whereas, the algorithm in [6] is similar to what the authors propose.
Could the authors comment more on this?