Beyond Optimism: Exploration With Partially Observable Rewards
Authors: Simone Parisi
Alireza Kazemipour
Michael Bowling
Venue: NeurIPS 2024 poster (2024)
Keywords: reinforcement learning
partial observability
exploration
successor representations
Primary area: reinforcement_learning
TL;DR: Directed exploration with the successor representation for MDPs with partially observable rewards

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.

Beyond Optimism:
Exploration With Partially Observable Rewards
Simone Parisi University of Alberta; Amii parisiQualberta.co
Alireza Kazemipour University of Alberta
Michael Bowling
University of Alberta; Amii
kazemipo@@ulleerta..
mboulingdnalberta.ccm
Abstract
Exploration in reinforcement learning (RI.) remains an open challenge. RI. algo- rithms rely on observing rewards to train the agent, and if informative rewards are sparse the agent learns slowly may not learn 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 uncer- tainty. 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 collection of tabular environments for benchmarking exploration in RL (with and without unobservable rewards) and show that our method outperforms existing ones.
Introduction
Reinforcement learning (RL.) has developed into powerful paradigm where agents can tackle variety tasks, including games [67], robotics [31], and medical applications [82]. Agents trained with RL learn by trial-and-errov 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 well-known dilemma: how and for how long should the agent explore, ie., 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 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] 660 Among the many exploration strategies that have been proposed improve RI. 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 count-based exploration bonuses [ [6] 24 22),, model-based planning
be expensive, especially in
[2]211, bootstrapping [5] 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 Tb] 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 suboptimal action (to push the button and pay 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 intrinsic motivation [66], they often lack guarantees of convergence and their efficacy strongly depends on the intrinsic reward used, the environment, and the task [
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

(a) Rewards given for collecting a coin are al- ways observable.
(b) The agent must first push a button and pay a cost to observe coin rewards.
When optimism is not enough. The agent starts in the second leftmost cell of a corridor- like gridworld and can move LEFT or RIGHT. The coin in the leftmost cell gives a small reward, the one in the rightmost cell gives 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 coin without pushing it first, the enviroument 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 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 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 22 have the same problem. If 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) 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 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?
Figure I:
How can we efficiently explore and learn to act optimally when rewards are partially observable, with- out relying on optimism and yet still have guarantees of convergence? In this paper, we present a novel exploration strategy based on the successor representation tackle this question. Note that Lattimore and Szepesvari [36] already argued against optimism in partial monitoring [8] a generalization
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 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 collection of both MDPs and Mon-MDPs.
2 Problem Formulation
A Markov Decision Process (MDP) (Figure 2) is mathemat- ical framework for sequential decision-making defined by the tuple (8, A, R. Y). An agent interacts with environment by repeatedly observing a state 8, E S, taking an action a, E A, and observing bounded reward r; E R. These interactions governed by the Markovian transition function P(s |a, st) and the reward function ri R(s at). both unknown to the agent. The agent's goal is to act to maximize the sum of discounted rewards E y Tr, where Y E [0, 1) is the discount factor describing the trade-off between immediate and future rewards.
Environment
Agent
Figure 2: The MDP framework.
- yy-rr,,
How the agent acts is determined by the policy T {a| 8), a function denoting the probability of executing action in state s. A policy is optimal when it maximizes the Q-function, i.e.,
(I) The 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
arg max Q" (s, a), where Q" (st, =
k TT R, F,,,,,t, 81, a.)

---

learn Q" by iteratively updating a function ; as follows,
greedy policy
(se, 0r) + (1 αe) ( ar) a (re + Y max ((s4))))),
(2)
where o, is the learning rate. Q is guaranteed to converge to Q" under an appropriate learning rate schedule o, and if every state-action pair is visited infinitely often [33. 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 crucial to behave optimally we also need the policy 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 explore all acttinaction pairs enough for Q to converge to Q", and that eventually act greedy as in Eq. ① While a large body of work in RL, literature has been devoted to developing efficient GLIE policies in MDPs, an important problem still remains largely unaddressed: the agent explores in search of rewards, but what if rewards are not always observable? MDPs, fact, assume rewards are always observable. Thus, we consider the more general framework of Monitored MDPs (Mon-MDDs) [55]
2.1 Monitored MDPs: When Rewards Are Not Always Observable
Mon-MDPs (Figure 3 are defined by the tuple (S AE, PE RE, M,, AA pM, RM y), where (St, AE, PE, RE Y) is the same as classic MDPs and the su- perscript E stands for "environment", while (M,S" ,M,, PM, PM, is the "monitor", a separate process with its own states, actions, rewards, and transition. The monitor works similarly the environment - performing monitor ac- tion af E AM affects its state sy E S and yields a bounded reward rM ~ (M a However, there are two crucial differences. First, its Markovian transition depends on the environment as well, i.e., (MM, |sM, st a², a.). 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 rf ~ (s aF), the agent observes proxy reward P. ~ M sM a²"). Most importantly, the monitor may not always show numerical reward, and the agent may sometime receive f = i.... "umobservable reward".
Environment
a²
Monitor
[a", a²)
(f".)"))
Agent
Figure 3: The Mon-MDP framework.
In Mon-MDPs, the agent repeatedly executes joint action a == (af, af) according to the joint state s, = (sf. sy ). In turn, the environment and monitor states change and produce a joint reward (ry (.f.r)), r2)). but the agent observes r.)) The agent's goal is to select joint actions to maximize Et=rY'' 1 (r. + r even though it observes if instead of rf. For example, in Figure 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, SM {ON, OFF), A {PUSH, NO-OP RM (ON, -) 11 M(r ON, .) = rt. MMr.. OFF, :) L. 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!
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 dictated by "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 [b] by reaching and pushing the button. Second, reward unobservability goes beyond reward sparsify. 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 few rewards are partially observable. Consider the Mon-MDD in Figure [b] but
'This example is just illustrative. general, the monitor states and actions can 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.
3

---

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-MDPss provide a comprehensive framework encompassing existing areas of research, such as active RL
33 68 and partial monitoring [ g 37 In their introductory work, Parisi et al. [55] showed the existence of an optimal policy and the convergence of variant of Q-Learning under some assumptions Yet, many research questions remain open, most prominently how explore efficiently in MDDs. 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-monee
state-action pairs (in Mon-MPDs). All the related work 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 can be applied to both MDPs and Mon-MDPs.
2.2 Related Work
Optimism. In tabular MDPs, many provably efficient algorithms are based on optimism in the face of uncertainty (OFU) 33 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 '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 14), where the optimistic value is computed from visitation counts (the lower the count, the higher the bonus). In model-free RI, 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 33 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 select actions that are known to be suboptimal to discover truly optimal actions. For example, in Figure Ib 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 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 B32 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 f-fuctiooss [I3 51 (52.. Nonetheless, if rewards
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 62).
Intrinsic motivation. While many of above strategies are often computationally intractable, they
"The assumptions are: monitor and environment ergodicity, i.c., 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; trathful monitor, ie.. either the proxy reward is the environment reward (ff = rf) or is not observable (fī 1).

---

inspired more practical algorithms where exploration is conducted by adding an intrinsic reward to the environment. This 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 [ 53 information gain [22 or can be computed from prediction errors of some quantity [1 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 they outweigh the environment reward the agent may explore for too long M..
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- aff-policy algorithms (even more if rewards are partially observable). After proving its asymptotic convergence we empirically validate it collection of tabular MDPs and Mon-MDPs.
3 Directed Exploration-Exxpoitatioo With The Successor Representation
Algorithm 1: Directed Exploration-EExplotttii.
(s", ad) = arg min.,a (x(ssa)) 3: log loRt/N.("",0*
// bre-b by deterministic ordering
3 if B, > 3 then return p(al se, 89, a9) se, else return arg max, ((s;,a) a)
// explore
// exploit
Algorithm| outlines our idea for step-wise exploration [ss,, a) is the state-action visitation count and, at every timestep. the agent selects the if the agent explores (goes to the goal) or exploits according to a threshold / > O. 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, 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 incremented. Exploration is driven by p(a) [ sa ad). a goal-conditn conddiiioned policy that selects the action according to the current state s; and goal (s a)). Intuitively, as the agent explores, if every state-action pair is visited infinitely often, log & will grow at slower rate than Ne(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 optimal. Intuitively, the role of B, is similar to the one of e, in e-greedy policies (75). However, rather than manually tuning its decay, 3e naturally decays as the agent explores.
pair as "goal" (s a.). The ratio 8e decides
The goal- goal-conditioned policy p is the core of Algorithm I For efficient exploration we want p move the agent as quickly as possible to the goal, i.e., we want to minimize the goal- relative diameter under p. Intuitively, this diameter is 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 untic p from the Q- Q-function, the rewards, and their observability. In the next section propose a policy p that satisfies these criteria, but first we prove that Algorithm| Tis a GLIE policy under some assumptions on p.
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.
Definition 2. Let p be a goal-conditionel policy p(a 8, 8,,", (,a)). Let T(s a 8) be the first timestep t in which (st, ax) (5 ,aa)) given 8o 8 and ot p(a st, S ,a)). The goal-relative diameter of p with respect to (s ",)),, if exists, is
Ds d²) = m ((ppss)
(3)
i.e., the maximum expected number of steps reach (s aa), ffom any state in the MDP. We say the goal- goal-relative diameter is bounded by D if D Z max. Do do).
RReall that and a denote either the classic state and action in MDPs, or the joint state == (55, (. and action a == (aF, a²) in MDPs.
5

---

There exist goal-conditioned policies with bounded goal goal-relative diameter if and only if the MDP is communicating (i.e., for any two states there is a policy under which there 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 the random policy
or similarly an c-greedy policy for > 0 [69]. Different goal-conditioned policies will have different bounds on their goal-relative diameter (s {
Theorem 1. If the goal-relative diameter of p bounded by D then Algorithm I is a policy.
Proof. Let (s, a) be the number of timesteps before time that the agent is in an exploration step with (s a²) = (s, a). Let X; = Σ... Z.(5, a)/s / be the fraction of time up to time / that the agent has spent exploring. We want to show that Ay > 0 lim,- Pr| xX2 > 5] = 0, i.e., the probability that the agent explores as frequently as any positive e approaches O. Hence, the policy is greedy in the limit. Note that, if the agent's 's frequency of exploring approaches zero this also must mean that Bg E O()),
implying (s, a) + oo V(s, a). i.e., all state-action pairs are visited infinitely often.
Let us focus on [E] (s, a).. Once the agent starts exploring visit (s,a), it will do until it actually visits (8, a). Let (2 a) be the number of times the agent started exploring to visit (8, a) before time t. We know that (s, a) I N,(s,a) 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
log 1'
log
L( =
< (v
+1
+1,
(4)
3
B
where the strict inequality is due to Byr > 3 (condition to explore). Since the agent cannot have started exploration log 1/8 logt/8 + times, and the goal-relative diameter of p is at most D, then
a)) < D logt +1) and thus B[X,] <
(
|
log
+11
(5)
t
3
We now apply Markov's inequality with threshold 1/V1,
Pr
X 2 Vi
&viB[X,)
< |
( (log
+1)
(6)
Vt
B
Since 1/vi < for sufficiently large 1,
| D
loogt t
lim Pr[X, 2 2] S lim Pr (1000
X Vi
S
lim 1000
B +
= 0,
(7)
1-000
vi
hence the Algorithm I is a GLIE policy.
Corollary 1. As a consequence of Theorem 7 Q converges to Q" (infinite exploration) and therefore
the algorithm's 's behavior converges to the optimal policy (greedy in the limit) $
While we have noted that the random policy is a sufficient choice for p to meet the criteria of Theo- rem]] [ the bound in Equation 7 shows direct dependence on the goal-relative diameter (s a²) Thus, the optimal to explore efficiently in Algorithm | is p² (a s, .d)) == arg min, (sa do). i.e. we want to reach the goal from any state as quickly as possible in expectation. Furthermore, we want to untie p from the learned f-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 [1].
3.1 Successor-Function: An Exploration Compass
The successor representation (SR) [4] is generalization of the value function, and represents the cumulative discounted occurrence of a state s; under policy n, i.e., 7 where 1 {s is the indicator function returning if s = s; and 0 otherwise. The SR does not depend on the reward function and can be learned with temporal-differene
T,, T,P,ss st),
in a model-free fashion, e.g., with Q-L-arningg Despite their popularity in transfer RI. 6, 19 38 61], to the best of our knowledge, only Machado al. (3) and Jin 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
$ Jaksch et al. [24 defined diameter that a property of MDP irrespective of any egoal-directed, policy. Their MDP diameter can he thought of as the smallest possible hound on the geal-velative diameter for any p. For MDDs convergence is guaranteed under the assumptions discussed in Footnote

---

policy - to learn value function that the goal-conditioned policy in Algorithm I 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 state-action pair (8i, under policy n, i.e.,
Saaa (st, a+) = EE 1 ((a== N., T,,, St, az
(8)
where 1 ( the indicator function returning if 8k - 5; and a2 aj. and 0 otherwise.
Prior work considered the SR relative to either an é-greedy exploration policy [4 or a random policy [38] 44 [1]. Instead, we consider different "successor policy" for every state-action pair (st, az), ). and define the optimal successor policy as the one maximizing the respective S-function, i.c.
Pziay = arg max Saia, (s, a)-
The switch from и to p is intentional: to maximize the S-function means maximize the occurrence of (st, az) under discounting, which can been seen as visiting (s; Qz) as fast as possible from any other state 6 Thus, Eq. (9) is a suitable goal-conditioned policy pa discussed in Algorithm Similar to the Q-function, we can learn an approximation of the S-functions using Q-Learning, i.c.,
Saaa (8t, ax) (1 04 S..,,, (st, 0z) + a1(1 (smmsrarmo) ymax Sa,a, (8++1,
(10)
Because the initial estimates of Sa.e, can be inaccurate, in practice we let p to be e-greedy over S,00a. That is, at every time step, the agent selects the action a arg max, Se (st: a) with probability
1-e, e, or a random action otherwise. As discussed in the previous section, any e-greedy policy with 0 is sufficient to meet the criteria of Theorem |
3.2 Directed Exploration via Successor-Functioon A Summary
Our exploration strategy can be applied to any off- off-policy algorithm where the 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 Ib again, and an optimistic agent (i.c., 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 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 is initialized optimistically (or even randomly), the indicator reward of Eq. (10p 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 deeper analysis on a benchmark similar to the example of Figure
difference
Related Work. In reward-free RL, Jín al. (26) proposed 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
'In deterministic MDPs, maximizing discounted occurrences is equivalent to minimizing the (expected) time-to- viivistt. However, this is not always true in stochastic MDPs, with discounted occurrences tending to ignore long time-to-visi outliers, making the agent more risk-seeing than expected time-to-vishe Nonetheless, in both cases, gonl-conditioned policies have bounded geal-relative diameter as long the MDP is communicating.
7

---

from a replay buffer with the goal of minimizing the number of actions needed to reach goal. Finally, in sparse-reward RL, Parisi et al. [54] learn two value functions one using extrinsic sparse rewards, one using dense visitation-coum 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 never combined together (54), as the agent follows either one or the other according to the coefficient 3t. Second, our coal-conditioned policy is chosen according to the least-visited state-action pair, rather than randomly sampled from set [26] or from replay buffer [23]. Third, none of them have considered the setting of Mon-MDPs and partially observable rewards.
4 Experiments
We validate our exploration strategy on tabular MDPs (Figure 4 characterized by different challenges, e.g., sparse re- wards, 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 posi- tive and negative rewards are unobserv- able (FE = 1) with probability 50% and observable otherwise (ff = rf), while zero-rewards are always observ- able. In the second, the agent can ask to observe the current reward at cost (r²" = -0.2). In the third, the agent can turn monitoring ON/OFF by pushing button in the top-left cell, and if sM = ON the agent pays cost (r²" = - -0.2) and observes P. = rt. In the fourth, there are many experts the agent can ask for rewards from at a cost (v = -022), 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²" -022) monitor actions to observe rewards (a wrong action resets the level). In all Mon-MDPs, the optimal policy does not need monitoring (r²² = -0.2 to observe f. rf). However, prematurely doing so would prevent observing rewards and, thus, learning Q More experiments on more environments are presented in Appendix B
Empty
Hazard
One-Way
River Swim
c c
Figure 4: Environments. The goal is to collect the large coin (rf 1) instead of small "distracting" coins (rf 0.1). In Hazard, the agent must avoid quicksand (it prevents any movement) and toxic clouds (rî - 10). One-Way, the agent must walk over toxic clouds (rā = 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
Baselines. We evaluate Q-Learning with the following exploration policies (details in Appendix A.5)
(1) ours; (2) greedy with optimistic initialization; (3) naive c-greedy; (4) c-greedy with count-based intrinsic reward 9 (5) <-greddy with UCB bonus 44) (6) e-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 best-case scenario baseline. For all algorithms, Y = 0.99 and e, starts at I and linearly decays to O. 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 reward model to replace A. L, initialized to random values in [-0.1, 0.1] and updated when A. *
Why Is This Hard? Q-function updates rely 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 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
Because for every environment reward there is monitor state-action pair for which the reward is observable (i.e., s = ON). Q-Learning is guaranteed to converge given infinite exploration (5
8

---

Ours
Optimism
UCB
Intrinsic Reward
Q-Counts
Naive
Full Observ.
Random Observ.
Ask
Button
Random Experts
Level Up
13
Hazard Empty
15
30
30
100
168
One Way
River Swim
50
190
200
Training Steps (1e.)
Figure 5: Episode return Err + r of greedy policies averaged over 100 seeds (shades denote 95% % confidence interval). Our exploration clearly outperforms all baselines, 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 optimal (as expected). However, if the environment 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 e-randomness, exploration with Q-Counts, UCB, Intrinsic Reward, and Naive is suboptimal as well, these baselines learn suboptimal policies in most of the seeds, especially 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 strengthsss 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 Q. Our agent does not avoid suboptimal actions and discovers more rewards." 8 More plots and discussion Appendix B Source code at https:// gi thub. com/ mmmiihinks..o wwo_mmoooomooooe hodd__nerrps24
5 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 exploration-explottttin trade-off
still limited. To fill this gap, we proposed a paradigm change 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, confidence bounds, our approach explicitly decouples exploration and exploitation through a separate goal-conditione 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.
'Note that Our agent keeps exploring and observine rewards (Figure 6 because 3r did not reach the exploit threshold 3 (but still decays quickly. see Appendix B.3). even if its greedy policy is already optimal (Figure 5)

---

Ours
Optimism
UCB
Intrinsic Reward
Q-Counts
Naive
Full Obeerv.
Random Observ.
Aak
Button
Random Experts
Level Up
st9
9239
1299
34.9
7.5
13599
10N22
79,900
07991
2327
2075
7784
0211
13025
23915
10
15
10
20.
50
300
106
200
40235
River One
5340
1906
30790
18757
31399
2100%
15684
50
40.0
Training Steps (1c")
Figure 6: Number rewards observed (f) * L) during training by the exploration policies. In
Mon-MDPs, only Ours observes enough rewards because it does not avoid suboptimal actions.
Advantages. Directed exploration via the S S-functions benefits from implicitly estimating the dynam- ies of the environment and being independent of the reward observability, First, the focus on the environment (states, actions, and dynamics) rather than on rewards 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 task. This has potential application in transfer RI,, in the same spirit of prior use of the successor representation [9 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 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, c.g., by following prior work on universal value function approximators [64, successor fea- tures 43 61], and pseudocounts 42
46 78]. For example, the finite set of S-functions Saea, (8t, az) could be replaced by neural network S(s,, at, 8;, a.). 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 chal- lenging, because Algorithm [ relies the min operator 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 c-greedy noise for fair comparison against the baselines, but there may be better alternatives (e.g.. "balanced wandering"
that could improve our exploration.
Third, we assumed that the MDP has a bounded goal-relative diameter but this may not true, e.g.. in reakly-communicatinn MDPs [18 59]. Thus, will devote future work developing algorithms for less-constrained MDPs, following recent advances convergence reward-fres 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 approuches. For example, we could use algorithms like UCRL B 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 observe (e.g., the least- observed) rather than what state-action pair to visit. Furthermore, our strategy could be combined with model-based methods where exploration driven by uncertainty [45 74 rather than visits. That would allow the agent to plan visits to states where rewards more likely to be observed.
10

---

Acknowledgments and Disclosure of Funding
This research was supported by grants from the Alberta Machine Intelligence Institute (Amii); Canada CIFAR AI Chair, Amii; Digital Research Alliance of Canada; and NSERC.
References
[1] Achiam and S. Sastry. Surprise-based intrinsic motivation for deep reinforcement learning.
arXiv:1703.01332 2017.
[2] A. Aubret, L. Matignon, and S. Hassas. An information-theorrticc perspective intrinsic
motivation in reinforcement learning: A survey. Entropy, 25(2):327, 2023.
[3] P. Auer and R. Ortner. Logarithmic online regret bounds for undiscounted reinforcement learning. In Advances in Neural Information Processing Systems (NIPS), 2007.
[4] Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Leurning, 47(2-3):235-25 256, 2002.
[5] P. Auer, N. problem. SIAM Journal on Computing, 32(())48-77) 2002.
Y. Freund, and R. E. Schapire. The nonstochastic multiarmed bandit
[6] A. Barreto. W. Dabney, R. Munos, J. J. Hunt, T. Schaul, H. Van Hasselt, and D. Silver. Successor features for transfer reinforcement learning. In International Conference on Neural Information Processing Systems (NeurIPS), 2017.
[7] A. G. Barto. Intrinsic motivation and reinforcement learning. Intrinsically motivated learning in natural and artificial systems, pages 17-47, 2013.
[8] G. Bartók, D. P. Foster, D. Pál, A. Rakhlin, and C. Szepesvári. Partial monitoring - classificatinn regret bounds, and algorithms. Mathematics of Operations Research, 39(4):967-99) 2014.
[9] M. G. Bellemare, S. Srinivasan, G. Ostrovski, T. Schaul, D. Saxton, and R. Munos. Unifying count-based exploration and intrinsic motivation. In Advances in Neural Information Processing Systems (NIPS), 2016.
[10] R. I. Brafman and Tennenholtz. R-MAX - general polynomial time algorithm for near- optimal reinforcement learning. Journal of Machine Learning Research (JM1,,,3:213322)) 3:213-231, 2002.
[11] Y. Burda, H. Edwards, A. Storkey, and O. Klimov. Exploration by random network distillation. In International Conference on Learning Representations (ICLR), 2019.
[12] Chen, A. Modi, Krishnamurthy, N. Jiang, and A. Agarwal. On the statistical efficiency of reward-free exploration in non-linear RL. Advances in Neural Information Processing Systems (NeurIPS), 2022.
[13] Dayan. The convergence of TD(A) for general X. Machine Learning, 8:341-362, 1992.
[14] Dayan. Improving generalization for temporal difference learning: The successor representa- tion. Neural Computation, 5(4):613-63 1993.
[15] C. D'Eramo, A. Cini, and M. Restelli. Exploiting Action- Action-Value uncertainty to drive exploration in reinforcement learning. In International Joint Conference on Neural Networks (IJCNN, 2019.
[16] K. Dong, Y. Wang, Chen, and L. Wang. Q-learning with UCB exploration sample efficient for Infinite-Horizon MDP. In International Conference Learning Representation (ICLR), 2020.
[17] E. Even-Dar and Y. Mansour. Convergence of optimistic and incremental Q-learning In Advances in Neural Information Processing Systems (NIPS), 2001.
[18] R. Fruit, M. Pirotta, and A. Lazaric. Near optimal exploration-explooittion in non- communicating Markov decision processes. In Advances in Neural Information Processing Systems (NeurIPS). 2018
[19] S. Hansen, W. Dabney, Barreto, Van de Wiele, D. Warde-Farley, and V. Mnih. Fast task inference with variational intrinsic successor features. In International Conference Learning

---

Representations (ICLR), 2020.
[20] M. Henaff. Explicit explore-exploit algorithms in continuous state spaces. In Advances in Neural Information Processing Systems (Newr[PS), 2019.
[21] T. Hester and P. Stone. TEXPLORE: Real-time sample-efficient reinforcement learning for robots. Machine Learning, 9063) 2013.
[22] R. Houthooft, X. Chen, Y. Duan, Schulman, F. De Turck, and P. Abbeel. VIME: Variational information maximizing exploration. In Advances in Neural Information Processing Systems (NIPS), 2016.
[23] E. S. Hu, R. Chang, O. Rybkin, and D. Jayaraman. Planning goals for exploration. In International Conference on Learning Representations (ICLR), 2023.
[24] T. Jakseh, R. Ortner, and P. Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research (JMLR), 11: 11:1563-100,, 2010.
[25] C. Jin, Z. Alu, S. Bubeck, and M. I. Jordan. Is Q-learning provably efficient? In Advances in Neural Information Processing Systems (NIPS), 2018.
[26] C. Jin, A. Krishnamurthy, M. Simchowitz, and Yu. Reward-free exploration for reinforcement learning. In International Conference Machine Learning (ICML), 2020.
[27] M. Kearns and S. Singh. Near-optimal reinforcement learning in polynomial time. Machine Learning, 49(2-3):209 2000999-222202 2002.
[28] J. Kirschner, T. Lattimore, and A. Krause. Information directed sampling for linear partial monitoring. In Conference on Learning Theory, 2020.
[29] Kirschner, T. Lattimore, and A. Krause. Linear partial monitoring for sequential decision making: Algorithms, regret bounds and applications. Journal of Machine Learning Research (JMLR), 24:346, 2023.
[30] M. Klissarov and M. C. Machado. Deep Laplacian- based Options for Temporally-Extent Extennee Exploration. In International Conference on Machine Learning (ICML., 2023.
[31] Kober, A. Bagnell, and J. Peters. Reinforcement learning robotics: A survey, The International Journal of Robotics Research (IJRR), 32(11): 2013.
[32] J. Z. Kolter and A. Y. Ng. Near-Bayesian exploration in polynomial time. In International Conference on Machine Learning (ICML), 2009.
[33] D. Krueger, Leike, O. Evans, and J. Salvatier. Active Reinforcement Learning: Observing Rewards Cost. 10Xiv:2011.06709 2020.
[34] Ladosz, L. Weng, M. Kim, and H. Oh. Exploration in deep reinforcement learning: A survey. Information Fusion, 85:1-22, 2022.
[35] T. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Adv. Appl. Math., 6 (1):4-22, 1985.
[36] T. Lattimore and C. Szepesvari. The end of optimism? An asymptotic analysis of fimite-armed linear bandits. In Artificial Intelligence and Statistics, 2017.
[37] T. Lattimore and C. Szepesvári. An information-theorret approach to minimax regret in partial monitoring, In Conference on Learning Theory, 2019.
[38] L. Lehnert and M. L. Littman. Successor features combine elements of model-free and model- based reinforcement learning. Journal of Machine Learning Research (JMLR), 21(196): 2020.
[39] T. P. Lillierap, J. J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, and D. Wierstra. Continuous control with deep reinforcement learning. In International Conference on Learning Representations (ICLR), 2016.
[40] D. Lindner, M. Turchetta, S. Tschiatschek, K. Ciosek, and A. Krause. Information directed reward learning for reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
12

---

[41] N. Littlestone and M. K. Warmuth. The weighted majority algorithm. Information and computation, 108(2):1122611 1994.
[42] S. Lobel, A. Bagaria, and G. Konidaris. Flipping coins to estimate pscudocounts for exploration in reinforcement learning. In International Conference Machine Learning (ICML), 2023.
[43] M. C. Machado, M. G. Bellemare, and M. Bowling. Count-based exploration with the successor representation. In AAAI Conference on Artificial Intelligence, 2020.
[44] M. C. Machado, A. Barreto, and D. Precup. Temporal abstraction in reinforcement learning with the successor representation. Journal of Machine Learning Research (JMLR), 24(80):1 69, 2023.
[45] H. Mania, M. I. Jordan, and B. Recht. Active learning for nonlinear system identification with guarantees. Journal of Machine Learning Research (JMLR), 23(32):1-30, 2022.
[46] J. Martin, S. S. Narayanan, T. Everitt, and M. Hutter. Count-based exploration in feature space for reinforcement learning. In International Joint Conference on Artificial Intelligence (IJCAI), 2017.
[47] V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller. Playing Atari With Deep Reinforcement Learning. In NIPS Workshop on Deep Learning, 2013.
[48] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al. Human-level control through deep rein- forcement learning. Nature, 518(7540):599-533, 2015.
[49] T. Moskovitz, J. Parker-Holder A. Pacchiano, M. Arbel, and M. Jordan. Tactical optimism and pessimism for deep reinforcement learning. Advances in Neural Information Processing Systems (NeurIPS), 2021.
[50] I. Osband and B. Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In International Conference on Machine Learning (ICMI.), 2017.
[51] I. Osband, D. Russo, and B. Van Roy. (More) efficient reinforcement learning via posterior sampling. In Advances in Neural Information Processing Systems (NIPS), 2013.
[52] I. Oshand, B. V. Roy, D. J. Russo, and Z. Wen. Deep exploration via randomized value functions. Journal of Machine Learning Research (JMLR), 20(124): 2019.
[53] S. Parisi, V. Dean, D. Pathak, and A. Gupta. Interesting object, curious agent: Learning task- agnostic exploration. In International Conference on Neural Information Processing Systems (NeurIPS), 2021.
[54] S. Parisi, D. Tateo, M. Hensel, C. D'Eramo J. Peters, and J. Pajarinen. Long-term visitation value for deep exploration in sparse reward reinforcement learning. Algorithmss, 15(3), 2022.
[55] S. Parisi, M. Mohammedalamen, A. Kazemipour, M. E. Taylor, and M. Bowling. Monitored Markov Decision Processes. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2024.
[56] D. Pathak, P. Agrawal, A. A. Efros, and T. Darrell. Curiosity-driven exploration by self- supervised prediction. In International Conference on Machine Learning (ICML), 2017.
[57] P. Poupart, N. Vlassis, J. Hoey, and K. Regan. An analytic solution to discrete Bayesian reinforcement learning. In International Conference on Machine Learning (ICML), 2006.
[58] M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley-Interscieence, 1994.
[59] J. Qian, R. Fruit, M. Pirotta, and A. Lazaric. Exploration bonus for regret minimization in discrete and continuous average reward MDPs. In Advances Neural Information Processing Systems (NeurIPS), 2019.
[60] R. Raileanu and T. Rocktäschel. RIDE: Rewarding Impact- Driven Exploration for Procedurally- Generated Environments. In International Conference on Learning Representations (ICLR), 2020.
[61] C. Reinke and X. Jameda-Pineda. Successor feature representations. Transactions on Machine Learning Research (TMLR), 2023.
13

---

[62] D. Russo and B. Van Roy. Learning to optimize via information dirrectdd sampling. In Advances in Neural Information Processing Systems (NIPS), 2014.
[63] R. M. Ryan and E. L. Deci. Intrinsic and extrinsic motivations: Classic definitions and new directions. Contemporary Educational Psychology, 25(1):54-67, 2000.
[64] T. Schaul, D. Horgan, K. Gregor, and D. Silver. Universal value function approximators. In International Conference on Machine learning (ICML), 2015.
[65] T. Schaul, J. Quan, I. Antonoglou, and D. Silver. Prioritized experience replay. In International Conference on Learning Representations (ICLR), 2016.
[66] Schmidhuber. Formal theory of creativity, fun, and intrinsic motivation (1990-2010), IEEE Transactions Autonomous Mental Development, 2(3):230-247, 2010.
[67] J. Schrittwieser, I. Antonoglou, T. Hubert, K. Simonyan, L. Sifre, S. Schmitt, A. Guez, E. Lock- hart, D. Hassabis, 'T. Graepel, et al. Mastering Atari, Go, chess and shogi by planning with a learned model. Nature, 588(7839):004-699 2020.
[68] S. Schulze and O. Evans. Active reinforcement learning with Monte-Carlo tree search. 2018.
arXiv:
[69] S. Singh, T. Jaakkola, M. L. Littman, and C. Szepesvári. Convergence results for single-step on-policy reinforcement-leammieg algorithms. Machine Learning, 38:287-308, 2000.
[70] N. Srinivas, A. Krause, S. M. Kakade, and M. Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In International Conference Machine Learning (ICML), 2010.
[71] B. C. Stadie, S. Levine, and P. Abbeel. Incentivizing exploration in reinforcement learning with deep predictive models. NIPS Workshop on Deep Reinforcement Learning, 2015.
[72] A. L. Strehl and M. L. Littman. An analysis of model--ased interval estimation for Markov decision processes. Journal of Computer and System Sciences (JCSS), 74(8):1309-1333 2008.
[73] M. Strens. A Bayesian framework for reinforcement learning. In International Conference on Machine Learning (ICML), 2000.
[74] B. Sukhija, L. Treven, C. Sancaktar, S. Blaes, S. Coros, and A. Krause. Optimistic active explo- ration of dynamical systems. Advances in Neural Information Processing Systems (NeurIPS), 2023.
[75] R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT Press, 2018.
[76] R. S. Sutton, J. Modayil, M. Delp, T. Degris, P. M. Pilarski, A. White, and D. Precup. Horde: scalable real-time architecture for learning knowledge from unsupervised sensorimotor interaction. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2011.
[77] I. Szita and A. Lőrinez. The many faces of optimism: a unifying approach. In International Conference on Machine Learning (ICML), 2008
[78] H. Tang, R. Houthooft, Foote, A. Stooke, O. X. Chen, Y. Duan, J. Schulman, F. DeTurek, and P. Abbeel. #Exploration: A study of count-based exploration for deep reinforcement learning. In Advances in Neural Information Processing Systems (NIPS), 2017.
[79] W. R. Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 25(3-4):285-294, 1933.
[80] Wang, Lizotte, M. Bowling, and D. Schuurmans. Bayesian sparse sampling for on- on-line reward optimization. In International Conference on Machine Learning (ICML), 2005.
[81] C. J. Watkins and P. Dayan. Q-learning. Machine Learning, 833-4)279-292,, 1992.
[82] C. Yu, J. Liu, S. Nemati, and G. Yin. Reinforeement learning in healthcare: A survey. ACM Computing Surveys (CSUR), 55(1):1-36, 2021.
14

---

Empty (6x 6)
Loop (3x3)
Hazard (4x4)
One-Way (3x4)
Two-Room (3
Two-Room (2x11)
Corridor (20)
River Swim (6)
Figure 7: Full set of the tabular environments used for experiments. Loop (3x3), Two-Room (3x5), Two-Room (2x and Corridor (20) were not included in Section 4 due to page limits.
A Experiments Details
A.1 Source Code and Compute Details
Source code at htttps://githie wtt.t/u...oommmmiiiiiiisssses/ http://ooommmmmnuurp222224 neurips24
We ran our experiments on a SLURM-based cluster, using 32 Intel E3-2683 v4 Broadwell @ 2. 2HH CPUs. One single run took between 3 to 45 minutes on single core, depending the size of the environment and the number of training steps. Runs were parallelized whenever possible.
A.2 Environments
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 current state and action as follows.
The environment reward depends
Coin cells: STAY gives a positive reward (rf 0.1 for small coins, r for large ones) and end the episode.
Toxic cloud cells: any action gives negative reward (rf = -0.1 for small coins, rf = 10 for large ones).
Any other cell: rf = O.
The agent can move away from its current cell 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 get stuck and waste time.
In arrowed cells, only the corresponding action succeeds. For example, if the agent is in 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 reach the goal (e.g., One- (ne-Way), divide the environment in rooms (e.g., in Two-Rooms).
environments, the goal is 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 coin or after step limit (in brackets after the environment name and its grid size).
Empty (6x6; 50 steps). This is a classic benchmark for exploration in RL with sparse rewards. There 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 suboptimal policy.
Loop (3x3; 50 steps). The large coin can be reached easily, but if the agent wants to visit the top-right cell forced follow the arrowed "loop". Algorithms that explore inefficiently for too long can end up visiting those states too often.
Hazard (4x4; 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 small coin and converge to a suboptimal policie, get stuck in the quicksand cell.
One-Way (3x4; 4; steps). The only way to reach the large coin walk past small toxic clouds. Because of their negative reward, shallow exploration strategies can prematurely decide not to
15

---

explore further and never discover the large coin. The presence of an casy-to-reach small coin can also cause convergence
suboptimal policy.
Corridor (20; 200 steps). This 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 e-greedy are known be extremely inefficient for this.
Two-Room (2 x1;11; 200 steps). The arrowed cells divide the grid into two rooms, one with a small coin and one with large coin. If exploration relies too much randomness or value estimates, the agent may converge to the suboptimal policy collecting the small coin.
Two-Room (3x5, 50 steps). The arrowed cell divides the grid into two rooms, and moving from one room to another may 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, implement the version in Figure There is small positive reward for doing LEFT in the leftmost cell (acting as local optima) and large one for doing RIGHT in the rightmost cell. The transition is stochastic and RIGHT has 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 or 2. Although this is an affnite-horizon MDP, i.e., no state terminal, we reset episodes after 200 steps. The optimal policy always does RIGHT.
IR. 0.40.4.01
IR. 0.6006.01
0.6.0.
IR.0
0..00.6.0
4
5
[R. 0.8,
[R. 0.35, D)
0.35,
[R. 0.35,
0.35, D)
IL. 1, 0.01)
1.
1. 0. 0.050.0500
(L. 0, 0.00. 01
[L. 1, 0.05, 0)
IL 1, 0R.0.4.
0.05,
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 in In both cases, the reward is 0. In state 5 the transition probability is the same, but if RIGHT succeeds the reward is 1.
A.3
Monitored-MDPs
Random Monitor.
There is monitor state, action, nor reward. Positive (coin) and negative
(toxic cloud) environment rewards are unobservable with probability 50% (f = L) and fully observable otherwise (fF rf). Zero-rewards in other cells are always observable.
Ask Monitor. The monitor always OFF. The agent can observe the current environment reward with explicit monitor action at cost.
SM {OFF)
AM == (ASK, NO-OP)
M OFF, 2
if a ASK otherwise
-02
if a ASK otherwise
0
Button Monitor. The monitor is turned OWOFF by pushing button in the starting cell (except for River Swim, where the button in state 0). The agent can do that with a = LEFT, i.e., the agent has 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.
SM
{ON,
]FF
A = {NO-OP}
s random uniform SM
ON
if MM if SM
OFF and si = BUTTON- CELL and of LEFT ON and sf BUTTON-CER and of LEFT otherwise
OFF
s
16

---

0.2
8t ON
F7 1
of ON
M
- if st ON and of is terminal
otherwise
0
otherwise
At every step, the monitor state is random. If the agent's 'ss monitor action matches the state, observes itt = -rt but receives a negative monitor reward. Otherwise, receives f but receives smaller positive monitor reward.
Random Experts Monitor.
SM = [l.....n] n} A [I....,m) n}
$141 random uniform in SM,
0
1 if az 8 r
0.2 if a = s
otherwise
0.001
otherwise
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.
In our experiments, n
Level Up Monitor. The monitor has n states, each representing a "level", and n + 1 actions. The first actions
costly and needed to "level up" the state, while the last is ND-OP. The initial level is random. To level up, the agent's action must match the state, e.g., if s = and ot = then 8t+1 2. However, if the agent executes the wrong action, the level resets s 1. Environment rewards will become visible only when the monitor level n. Leveling up the monitor is costly, and only a NO-OP is cost-free.
SM {1, [1.....n]] n} AM {l...., NO-OP}
max N + 1,
if s = dt
if aM = ND-OP otherwise
641
r if s =
a = NO-OP
F
otherwise
-02
otherwise
The optimal policy always does at = 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 correct sequence actions observe rewards elicits deep exploration.
A.4 Training Steps and Testing Episodes
All algorithms are trained over the same amount of steps, but this depends on the environment and the monitor reported in Table As the agent explores and learns, we test the greedy policies at regular intervals a total of 1,000 testing points. For example, 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 the greedy policy over episode (for fully deterministic environments and monitors) or 100 (for environments and monitors with stochastic transition initial state, i..., Hazard, Two-Room (3 x)), River Swim; Button, Random Experts, Level Up).
Table 1:
Number of training steps. For each environment, we decided default number of train- ing steps. Then, we multiplied this number for constant de- pending on the difficulty of the monitor. For example, agents are trained for 30,000 steps in the Corridor environment without any monitor, 60,000 with the But- ton Monitor, and 600,000 with the Level Up Monitor.
Environment
Default Steps
Monitor
Multiplier
Empty (6x6)
5,000
Loop (3x3)
5,000
Full Obs.
Hazard (4x4)
10,000
Random
x1
One- One-Way (3
10,000
Ask
x3
Corridor (20)
30,000
Button
x2
Two-Room (2x 11)
5,000
Rnd. Experts
x10
Two-Room (3x5)
10,000
Level Up
x20
River Swim (6)
20,000
17

---

Algorithm 2: Q-Update With Reward Model for Mon-MDPs
input: : {5) ai PB 1441, Sy oN rt, s 8441 de, Nº, R, Q,
if i + 1 then
NT af) + (T ; af +1
R(s{,af) f (N"()))))) ((
8, (s8,
ag (di )
R(s a.) + rrk
return (8t, az) 5 11-1,, (1x))(((s), at) + *a(rr: ymax, ())+1,a)
A.5 Baselines
All baselines evaluated in Section 4 use Q-Learning with reward model to compensate for unobserv- able rewards in Mon-MDPs (f = =], 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 table R(s r²) initialized to random values in [-0.1, 0.1] that keeps track of the running average observed proxy reward every time reward is observed, count N ( is increased and the entry R(sE, r²) is updated.
The differences between the baselines lie in their exploration policies, described below and outlined in Algorithms 3 and 5
Ours. As described in Algorithm with 3 0.01. The goal-conditioned policy is e-greedy over Sma (3t, a). The S-function initialized optimistically to Saja, (s, V(s, s;,
Optimism. Exploration is pure greedy, i.e., d, arg max, @(+,, a).
UCB. Exploration is e-greedy over the UCB estimate Q(+,, a) + 2log E. N(tt, al/NNaa))) 4
Q-Counts. This baseline learns a separate Q-function Qe a) using N(s ar) as rewards, i.e., (c(s,, a.) + (1 - ox (. ox) + (N(s ar) + ymin Qc(s(+1)
(11)
This function is initialized to (c, a) 0 V(s, a). and intuitively estimates and minimizes "cu- mulative visitation counts" [54]. The exploration policy then replaces (Nss a) with (s a) in the UCB estimate, favoring actions that result in low cumulative counts rather than low immediate counts. Formally, the exploration is e-greedy over (55,, a) Vo Qe (e..o..
Intrinsic. Exploration e-greedy over ((s,, a). The Q-function is trained with intrinsic reward 0.01//N(o...)
Naive. Exploration is e-greedy over ((ss, a).
When two or more actions have the same value estimate - whether Q(s,. a), Sec (s), or Q(st, a) with UCB bonuses) ties are broken randomly.
Below are the learning hyperparameters.
The schedule e, starts at and linearly decays to 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 O, constant 0.2, constant 0.I.
The schedule 0g depends on the environment: constant 0.5 for Hazard and Two-Room (3x5) (because of the quicksand cell), linear decay from 0.5 to 0.05 in River Swim (because of the stochastic transition), and constant 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.
18

---

Algorithm 3: Q-Learning Baselines
input: a, Q
50 k- environment.cc start () for MMx do
d; = explore (st. N) N)
N)) - ((,,, 4) +1 8141 - envir mawirrommen..seep
st is terminal then
81+1 f environment.sten start ()
q_update (s;, az, 81+1.00 x.)
// Eq.
Algorithm 4: Our Q-Learning with S-functions
input: N, Q 3
1 50 - environment. www.oommet..sartt........ () 2 for f = Max do
explore (8t, Q N, 3.
N(s,, < (st,, (x) +
Tt, + environment.co staeeenttttttteee (a,)
if s; is terminal then
St+1 environment.stane ()
q_update (s,, a2 f, $141, o)
// Eq.
s_update (82, de, 8,4 oc)
// Eq.
Algorithm 5: Q-Learning with Q-Counts S4
input: N, Q. 8o <- anvironment.state ()
for ? 0 to txxx do
a: ( Q, Q.)
aa) N(s,, a4) +1 8t4 f- www.rroeeet.steeppeeeeee..
s; is terminal then
St+1 + environment. ()
quupdate (82, at, ft, 81+1, x)
// Eq. // Eq.
cocunt_update (sy, ar, S141, N, x)
Note that the discount factor and the learning rate &r in Eq. ( and |1 can be different, e.g., higher learning rate to update Q and smaller for S. In experiment, use the same and 0, for both Q S, and Qc.
The Q-function is initialized optimistically to ((s = (s,,a) (first seven environments) and ((s, a) 50 ((s.)) a) (River Swim) for all algorithms except Ours, where initialized pessimisti- cally to (s, = - 10 a) (all environments). This performed better than optimistic initialization because it mitigates overestimation bias, that be more prominent with optimism [4]] 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.
19

---

B Additional Results
B.1 Greedy Policy Return
Figure is extended version of Figure with all eight environments (we showed only four in the main paper due page limit). Results Loop (3x3), Two-Room (3x5), Two-Room (2x 11), and Corridor (20) are aligned with the remainder, showing that Our exploration strategy outperforms all the baselines. Note that only River Swim, Ours did not significantly outperformed the baselines. Its highly stochastic transition, indeed, makes learning harder and is the reason why Optimism fails even the MDP version (in spite of fully observable rewards). Nonetheless, Ours did not perform worse than any baseline in any version of River Swim (MDP and Mon-MDPs).
Optimism
UCB
Intrinsic Reward
Q-Counts
Naive
Full Observ.
Random Observ.
Ask
Random Experts
Empty
Loop
00
15
06
3.5
18
00
14
150
50
53
Hazard
15
100
168
One Way
180
Corridor
Two Two Room 3x5 Two Room 2x11
1.
027
150
River Swim
50
Training Steps (1ea)
Figure 9: Episode return Err + r) of greedy policies averaged over 100 seeds (shades denote 95% confidence interval).
20

---

Optimism
Intrinsic
Q-Counts
Full Observ.
Random Observ.
Button
Random Experts
Up
5238
Empty
2296
2009
0608
1779
00
50
00
2.
5- 00
755
15.0
10
300
6197
2008
2044
3504
33395
18123
15999
10432
2377
5211
20016
40225
0397
5090
1997
3240
13006
20159
15
30
33
10.
50
300
180
200
Two-Room 3x5 Two-Room Corridor
3390
5308
7W37
2994
2013
10333
15577
2139
21004
River Swim
33395
0073
15684
10033
42352
10
30
20
40.0 180
300
600
Training Steps (1e2)
Figure 10: Number of rewards observed (F + L) during training by the exploration policies averaged over 100 seeds (shades denote 95% confidence interval). In Mon-MDPs, all baselines except Ours do not observe enough rewards because they do not perform suboptimal actions to explore. Thus, they often converge suboptimal policies, also shown in Figure 9 The ratio between training steps and number of observed rewards also hints that Our policy truly explores uniformly. For example, in Ask the agent can observe rewards only in half of the Mon-MDP state space (only when s = ON). Indeed, in the plots in the third column, the number of observed rewards roughly half of the number of timesteps (e.g., in Empty (Ask) the agent trained for 15,000 steps and Our agent ends up observing 7,500 rewards). The same 1/2 ratio is consistent across all Ask plots. Similarly, in Random Experts the agent can observe rewards only in 1/4 of the state space (there are four monitor states and only by matching the current state the agent can observe the reward), and indeed the agent ends up observing rewards ~1/a of the time (e.g.. 12.500 out of 50,000 steps in Empty (Random Experts)). In Figure 13 we confirm exploration uniformity with heatmaps.
21

---

B.2 Reward Discovery
Figure 10 shows how many rewards the agent observes (f) * 1) 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 (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 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.
Full Observ.
Random Observ,
Ask
Button
Random Experts
Level Up
UPP
XP
13"
107
307
307
130
147
307
10P
18a
18'
187
Hazard
127
137
127
30
30
300
187
384
18"
Two-Rm Corridor
32"
137
1."
30-1
3011
18"
18
13'0
197
137
1.0
301
301
18
River Swim Two-
141
Training Steps (1e3)
Figure 11: Trend of the exploration-explottaae ratio Sr (in log-scale) during training by Our exploration policy averaged over 100 seeds (shades denoting 95 % confidence are too small to be seen). Until the agent has visited every state-action pair once, min N(s, = 0, thus 3, = co. For the sake of clarity, we report it as 3, = 10 in this plot. Even if did not reach the threshold 3 = 0.01 (bottom line in black), the ratio clearly decreases over time, further sign that the agent explores all state-action pairs uniformly (i.c., maximizing the occurrence of the visttev pair). Note that in small environments (e.g., River Swim) Br decreases faster than in large environment (e.g., Empty).
22

---

10
Figure 12: Explore-exploit ratio 3, log logt/min ((s,a) (in log- scale) during a run on RiverSwim with Button Monitor, For the sake of clarity,
replaced 3 (when min (s, 0) with Bg = 10. For roughly the first 8,000 steps, St 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 8 consistently decreases. This denotes that become more and more accurate, thus the policy p can bring the agent the goal (i.e., the least-visited state-action pair) faster.
10
10
10
8
12
16
20
24
28
32 36 40
Training Steps (1e²)
B.3
Goal-Conditioned Threshold St
Figure I1 ssows the trend of the 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 8 did not reach the threshold B explains why in Figure the agent keeps exploring and observing rewards, while the greedy policy in Figure iss already optimal. In Figure 12 we further show the trend of 8, 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.
ratio 3, (in log-scale) of Our exploration
Monitor ON
Monitor OFF
17.09
Ours
11.41
2
15894
1.-
7046 C--
Optimism
R-
UCB
6414 2
Q-Counts
7063
L.
Intrinsic
Reward
R
2
7063
1.
Naive
Figure 13: State-action visitation counts ((s, a) after one run (40,000 steps) on River Swim with the Button Monitor. Only Our agent visits the state-action space uniformly as possible, as shown by the smooth heatmap and its range 1374-3,4255 poorly (less smooth heatmaps and much larger range). Indeed, they do 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, suboptimal (r = -0.2), yet needed observe rewards. This further explains why they observe much fewer rewards in Figure T0
On the contrary, all the other baselines explore
23

---

B.4 River Swim With Button Monitor: A Deeper Analysis
Here, investigate more in detail the results for River Swim with Button Monitor, benchmark similar to the example in Figure [ discussed throughout the paper. States are enumerated from in Figure 8 the agent starts either in state or 2, the button located in state and can be turned ON/OFF by doing LEFT in state O. 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 select suboptimal actions (but this is the only way discover higher rewards). UCB, Q-counts, Intrinsic, and Naive mitigate this problem thanks e-randomness, but still do not explore properly and, ultimately, do not learn accurate Q-functions.
the contrary, Our policy explores the whole state-action space as uniformly possible observes rewards frequently (because it visits states with monitoring ON), and learns a close approximation of Q" that results in the optimal greedy policy.
Monitor ON
Monitor OFF
25.87
Optimal Q*
1
R-
19.50
Ours
2
24.12
Optimism
-0.58
29.94
UCB
0.51
Q-Counts
20.29
1
2
1
29.96
1.-
Intrinsic
Reward
0.55
Naive
2 3
Figure 14: Q-function approximators Q(s, a) after one run (40,000 steps) on River Swim with the Button Monitor. Only Our agent learns close approximation of the true optimal Q-function (on the top) that produces the optimal behavior - (55, OFF, RIGHT) and Q0, ON, LEFT) have the highest Q-value for monitoring OFF/OM respectively, and the value of other state-action pairs smoothly decreases as the agent is further away from those states. Doing RIGHT state in fact, gives r. but the optimal policy turns monitoring OFF first by doing LEFT in state 0 (to stop r -0.2). On contrary, Optimism learns completely wrong Q-function that cannot turn monitoring OFF This is not surprising given the poor visitation count of Figure 13 UCB, Intrinsic, and Naive learn smoother Q-function, but end up overestimating the Q-values due to the optimistic initialization and overestimation bias (see the range of their Q-functions).
"ote 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.

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: In the abstrrct/introduutton we highlighted the lack of practical algorithms with guarantees of convergence in MDPs with partially observable rewards. Later, presented an algorithm to address this, proved its asymptotic convergence, and validated its efficacy 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 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 is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations 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 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 separate "I "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 the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or 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 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
25

---

Answer:
[Yes]
Justification:
We claim and prove asymptotic convergence of our algorithm in Section 3
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide full details of the environments, algorithms, and hyper- parametrs in the Appendix. Source code at lattps://githi:: com/ Ami Thinkssin///// /moon
mdp_ [ip_neeurip24
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
26

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Source code at No extra data is needed.
mon http://wwmmnnuuuiiss////2
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
oolic) for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.cc/pbble pwwppppguuuiieeeeep Sodi:////uiddd//deeuuuubuiii
(CodeSubiisss wwtauubmmsssooni ssiiiioicccy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, 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 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, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
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, confi-
dence intervals, statistical significance tests, 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 with given experimental conditions).
27

---

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.
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 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 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.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
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 failed experiments that didn't make it into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://wwwrrp...coooo//.ccctccaa
Question:
Answer: [Yes]
Justification: Our work 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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations 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 mostly theoretical, experiments conducted simple environ- ments, and it is not tied to particular applications.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
28

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 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 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe 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)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have 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 best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include 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 use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
29

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
30


Reviews:
[{"review_id": "fr6iL1wON7", "reviewer": "Reviewer_DPys", "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.", "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.\n\nThe authors may also address any of the weaknesses above, especially number 1.", "limitations": "Most limitations have been already discussed in the paper. The work has no direct societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "(quality) The paper is very well-written. The topics are presented very clearly and the text can be read from top to bottom whithout any major misunderstanding. The related work section covers the essential work in the area (at least, the ones I am aware of), and the papers are described well. The main contribution is motivated and it is described completely.\n\n(relevance) The study of Monitored MDPs has important relations with partially observable environments, and it is very relevant for the broad RL community. Moreover, it clarifies the difference between observing rewards and being only evaluated on them.\n\n(reproducibility) The authors provided a full, well-documented Python source code of the algorithm, which ensures reproducibility. They also provided the necessary configuration files.\n\n(soundness) The proposed algorithm appears to be appropriate for the class of domains and the monitors considered in the experimental section. Also, the evaluation considers 5 monitors for each of the 4 environments, which is an interesting composition.", "weaknesses": "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.\n\n2- 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.\n\n3- The contribution of the paper is limited for the following reasons:\n\n  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.\n\n  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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful insights and suggestions. Below, we discuss the main points you raised.\n\n1. You are correct, we consider only \"truthful monitors\" (as formalized in *\"Parisi et al., “Monitored Markov Decision Processes, 2023”*), i.e., monitors that either hide the reward or show it as is. We wrote in page 3, footnote 2 that *\"the monitor does not alter the environment reward\"*. We will make it more explicit in Corollary 1.\nThis is needed for our proof of convergence. The investigation of monitors that can change the reward are out of the scope of this paper and relates other directions of research (e.g., *\"Ng et al., Policy invariance under reward transformations: Theory and application to reward shaping, 1999”*). Relaxing this condition, in fact, poses an additional challenge that could be addressed by having a belief over the reward (e.g., *\"Marom and Rosman. Belief reward shaping in reinforcement learning, 2018\"*).\n\n2. You are correct that no baselines exist yet for Mon-MDPs because the formalism is recent. For a fair comparison against existing baselines, we included standard MDPs in our evaluation (\"Full Observ.\" environments in Figures 5 and 6). The results show that even in classic MDPs our approach works better than existing ones: most baselines converge but they need a significantly larger amount of data. In Mon-MDPs, only ours converges in most seeds and the baselines fail most of the time. \nWe didn't include UCB-based RL algorithms like UCRL because they are model-based and we considered only model-free methods for a fair comparison. Model-free alternatives (e.g., *“Dong et al., Q-learning with UCB exploration is sample efficient, 2020”*) usually provide guarantees of convergence (with convergence rates) but are impractical and lack evaluation on even simple domains. \nAlso, we included a UCB-like baseline (orange line in Figure 5 and 6) that uses the UCB bonus to encourage exploration. \nWe are happy to include more baselines if you have any suggestions. \n\n3. a) We agree and we already discussed extending our algorithm to larger/continuous Mon-MDP and to model-based approach (e.g., learning the monitor model) in Section 5. We are currently working on extending it to larger/continuous domains using UVFA and alternative to counts, and we plan to submit a follow-up soon. Please refer to the response to reviewer **zrqd** for more details.\nWe argue, however, that these limitations should not overshadow the contribution of the paper. We believe that the whole Mon-MDP framework is still very new and unexplored, and that our approach, proof of convergence, and evaluation are novel and thorough enough, and set the stage for many future directions of research.\n\n3. b) Thank you for this insight. How would it be equivalent to place unit rewards in goal states, though? In our algorithm, one SF places unit rewards in **one** state, and then we learn a SF for **every** state. We see similarities between the classic use of SF and our approach, but usually SF are given an explicit goal (or features representing it) and are applied in the context of transfer learning. In our case, there are as many goals as state-action pairs. \nThis is why we wrote that only Machado et al. applied SF for exploration, since their work was tailored to encourage visitation of state-action pairs. \nWe are happy to cite more related work if you have any suggestions.\n\n4. Greedy UCB performed better in some environments but very poorly in others. The average performance was best with the addition of $\\epsilon$-greedy action-selection.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8FKuyATUHc", "reviewer": "Reviewer_ajhV", "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.\nThey show that the proposed strategy is consistent and outperforms standard exploration approaches such as optimistic exploration.", "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?\n\n2. 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.\n\n\nI am happy to increase my score if my concerns and questions above are adequately addressed.", "limitations": "The authors address the limitations of their work in the main paper (lines 336  -- 349).", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is very well written. Particularly, the analysis of explore and exploit strategies for Mon-MDPs is interesting and novel. The empirical results are also good.", "weaknesses": "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.\n\nThere 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.\n\nThe authors should write the rate of convergence in the main theorem statement of Theorem 1.\n\n[1] Jin, Chi, et al. \"Reward-free exploration for reinforcement learning.\" International Conference on Machine Learning. PMLR, 2020.\n[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.\n[3] Mania, Horia, Michael I. Jordan, and Benjamin Recht. \"Active learning for nonlinear system identification with guarantees.\" arXiv preprint arXiv:2006.10277 (2020).\n[4] Sukhija, Bhavya et al. \"Optimistic active exploration of dynamical systems.\" Advances in Neural Information Processing Systems 36 (2023): 38122-38153.\n[5] Nair, Ashvin V., et al. \"Visual reinforcement learning with imagined goals.\" Advances in neural information processing systems 31 (2018).\n[6] Hu, Edward S., et al. \"Planning goals for exploration.\" arXiv preprint arXiv:2303.13002 (2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful insights and suggestions. Below, we discuss the main points you raised.\n\n1. Thank you for the additional references, we will add them to the final version. \nIn particular, we think that [1] is indeed close to our approach in the use of SF. It is different, however, as it has two separate stages for exploration and exploitation, while ours balances between the two using the coefficient $\\beta_t$ (Algorithm 1, line 2). \nWe would like to stress, however, that [3], [4], and [6] propose model-based algorithms. \nIn our paper, we focused on model-free RL and thus evaluated our algorithms against model-free baselines. As discussed in Section 5, we will devote future work on model-based versions of our algorithm.\n\n2. We don't have a rate of convergence for Theorem 1, only an asymptotic convergence proof. Evidence for the practicality, in terms of sample efficiency, of our proposed algorithm is instead given by our thorough empirical experiments. Provable rates of convergence often don't imply practical algorithms (e.g., [1] and [2], which don't include any experimental results), which was one of the goals for our paper.\n\n3. We agree that this is an interesting baseline, and we will add it to the final version. \n\n4. Active RL (ARL) is perhaps the closest framework to Mon-MDPs but its setting is simpler. To the best of our knowledge, ARL considers only binary actions to request rewards, constant request costs, and perfect reward observations. By contrast, in Mon-MDPs (a) the observed reward depends on the monitor — a process with its own states, actions, and dynamics; (b) there may be no direct action to request rewards, and requests may fail; (c) the monitor reward is not necessarily a cost. For these reasons, ARL can be seen as a special case of Mon-MDPs, and therefore cannot fully capture the complexity of Mon-MDPs.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "B5vtyvtgHE", "reviewer": "Reviewer_zrqd", "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.", "questions": "Questions: \n- 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\n- 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?\n- Why do the other methods struggle so much on the empty environment? Is it because the sparse reward problem is harder?", "limitations": "I think the authors have adequately addressed limitations in their work.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- The paper is generally well written. I found the illustrations to be useful in understanding the ideas. \n- The authors perform good experiments, describing baselines the baselines appropriately putting their method’s performance in to context.\n- The idea of selecting goals systematically based on the count and then following a goal conditioned policy seems effective for the Mon-MDP setting.", "weaknesses": "- 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?\n- 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.\n- There seem to be no other Mon-MDP specific methods that have been compared against. Are there any other methods?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful insights and suggestions. Below, we discuss the main points you raised.\n\n1. In sparse-reward RL, rewards are mostly 0 with very few exceptions (\"meaningful rewards\"). In Mon-MDPs, the agent cannot see the rewards, not even the 0s. While intrinsic rewards may improve exploration, they cannot replace $r_e = \\bot$ (unobservable), thus the agent cannot directly maximize the sum of environment rewards. There is a need for a mechanism to learn even in the absence of rewards. This is what Mon-MDPs are for, as introduced by *\"Parisi et al., Monitored Markov Decision Processes, 2023\"*. \nWe also argue that most intrinsic rewards induce non-stationarity (e.g., counts change over time), and are myopic (counts rewards only immediate visits, not long-term visits). \nSince our evaluation is limited to discrete MDPs, we used intrinsic rewards based on counts (*\"Bellemare et al, Unifying count-based exploration and intrinsic motivation, 2016\"*). To the best of our knowledge, in fact, count-based rewards are the go-to choice for discrete MDPs, while other intrinsic-reward algorithms (e.g., RIDE by Raileanu and Rocktäschel, 2020; RND by Burda et al., 2018; Curiosity-driven by Pathak et al, 2017) are more suited for continuous MDPs and deep RL. In our follow-up on continuous Mon-MDPs, we will evaluate the latest deep RL intrinsic-reward algorithms.\n\n2. We are currently working on extending our algorithm, as promised in Section 5. Here are more details that we will be happy to add to the paper as well. First, Universal Value Function Approximators (UVFA, Schaul et al., 2015) will replace the set of S-function. That is, while first we had one S-function for every state-action (each implemented as a table) now we have one single neural network that takes the goal state and the current state as input, and outputs the action value for each goal action. That is, $S(s_{goal}, s_t) = [a_{goal}, a_t]$.\nWe have already implemented this and it works nicely, but we are still investigating UFVA (there are different versions, and we may even propose a novel one). \nRegarding the use of counts, the main challenge is the presence of $\\arg\\min N(s,a)$. To make it tractable, we plan to either use Random Network Distillation (RND, Burda et al., 2018), or a version of prioritized experience replay (Shaul, 2016) that takes into account either pseudocount or RND prediction errors (rather than TD errors). \n\n3. There is indeed no other Mon-MDP method yet. Mon-MDPs were introduced very recently (Parisi et al, 2023) and ours is the first work addressing exploration in Mon-MDPs.\n\n4. The main contribution is the explore-exploit paradigm that overcomes the limitations of optimism and therefore is effective for problems where rewards are unobservable. In order to make it work, SFs are a necessary component, as they allow to decouple exploration (SF: visit a desired state-action pair) from exploration (Q-function: maximize return). \nOn one hand, Algorithm 1 formalizes how to decouple exploration and exploitation, and the mechanism to balance the two (i.e., the ratio $\\beta_t$). Theorem 1 further proves its convergence. On the other hand, Algorithm 1 depicts a general approach that uses a generic “goal-conditioned policy $\\rho$”. To make it practical, we propose S-functions. While using SFs as value functions is not novel in RL literature, we argue that the way we use them is. \n\n5. We believe that Mon-MDPs better capture the complexity of real problems, and therefore any MDP can be extended to Mon-MDPs. In a follow-up work, we are modeling a roborace problem as Mon-MDP: the agent receives rewards for a trajectory only upon explicitly asking for it, and the availability of the feedback is modeled as a monitor. This relates to RL from human feedback, with the difference that the availability of the feedback follows a Markovian process and the agent can exploit it. The goal is that using Mon-MDP the agent can ask for feedback more effectively, and in the end will learn to race without never asking for it.\n\n6. All algorithms (ours and baselines) learn a reward model to compensate for unobservable rewards: since the benchmark Mon-MDPs are ergodic, and because every environment reward is observable for at least one monitor state (e.g., when the button is on), given infinite exploration Q-learning is guaranteed to convergence (this was proven in “Parisi et al., Monitored Markov Decision Processes, 2023”). \nThe problem with the baselines (not ours) is that they use the Q-function to explore. In $\\epsilon$-greedy (red) and intrinsic reward (green), the greedy operator is over Q; UCB-like (orange) still considers Q in its greedy operator; optimism (black) is pure greedy over Q.\nThis is a problem in Mon-MDP because Q-function updates are based on the reward model that is inaccurate at the beginning (if the reward is unobservable, the agent queries the reward model). To learn the reward model and produce accurate updates the agent must perform suboptimal actions and observe rewards. This creates 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). \nOur algorithm, instead, builds its exploration over the S-function, whose reward is always observable (either 1 or 0). This allows the agent to quickly learn accurate S-functions, which will then produce efficient and uniform exploration (as much as possible, at least, since visitation also depends on the initial state and the transition function). By visiting all environment and monitor states efficiently, the agent can also observe environment rewards quickly, learn an accurate reward model, and finally the optimal Q-function.\nWe will write a dedicated paragraph to this explanation in the final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WzyQk1vzmL", "reviewer": "Reviewer_Y2Vd", "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.", "questions": "Look at Weaknesses section.", "limitations": "Limitations have been adequately addressed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The algorithm is simple and and intuitive\n- The paper is generally well-written and I didn't have issues with understanding.\n- In the experiment section the algorithm is tested on several environments with different monitors, and they show significant improvements in terms of performance compared to the baselines.", "weaknesses": "- 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$.\n- 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.\n- 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)$.\n- 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)\n- 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.\n- 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful insights and suggestions. Below, we discuss the main points you raised.\n\n1. We will make the distinction between Mon-MDPs and sparse-rewards MDP more explicit. \n\n2. You are correct, the agent sees both states. We will make it clearer in the final version. \n\n3. You are correct that, generally speaking, $\\log(t)$ may not grow at a slower rate than $N_t(s,a)$. However, this holds in our case and that sentence was just an informal statement to give the reader an intuition of why our algorithm converges. Indeed, in line 175 right after that sentence we wrote “(formal proof below)”. We apologize for the confusion, and we will make it clearer in the final version.\n\n4. Theorem 1 is formalized using the classic MDP notation for the sake of simplicity, and we now see how this may actually cause confusion. $Q(s,a)$ depends on both the monitor and the environment, i.e., its explicit notation for Mon-MDPs would be $Q(s_e, s_m, a_e, a_m)$. \nFor Q-learning to converge in Mon-MDPs we need the following assumption: that the monitor is “truthful”, i.e., it either hides the reward or shows it as is (Parisi et al., Monitored Markov Decision Processes, 2023). Given a truthful monitor, under ergodicity and infinite exploration (proved in Theorem 1), then $\\widehat Q$ converges to $Q^*$. We mentioned the notion of “truthful monitor” in footnote 2, page 3, but we will now make it explicit in Corollary 1. We apologize for the confusion.\n\n5. Our reference to “as fast as possible” is imprecise, although not for the reason given, and we will clarify this in future revisions. The expected return from further visits to $s_i, a_j$ upon reaching the state-action pair under the optimal policy is a fixed positive value (as the environment is Markovian and rewards are all non-negative). Therefore, the optimal policy for accumulating visit counts to the state-action pair is still to visit the state action as quickly as possible, as this results in minimizing the discount factor on the visit reward and the fixed positive future return. And this is exactly what your proposed reward function would also do (just not include the fixed positive future return), while avoiding the non-Markovian property of your specification. \nHowever, the “as fast as possible” phrasing is imprecise because of how it handles stochasticity.  One might expect “as fast as possible” to minimize the expected time to reach the state-action pair, which the SR only does if the environment is deterministic. It is still incentivized to visit the state-action pair quickly, just with a different tradeoff between distributions of visit times.\n\n6. Every step the button is on.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their feedback and helpful suggestions. We are pleased to see that all reviewers appreciate the core idea of our paper — a novel exploration algorithm for Mon-MDPs, where rewards are partially observable — and the thorough evaluation against different baselines on many environments/monitors. We are also happy to see that all reviewers find our paper intuitive and very well-written.

We have replied to each reviewer separately to address some specific clarifications. In this comment, we recap what we will introduce in the final version of the paper after taking into account the reviews.

* We will make it clearer why Mon-MDPs are different from sparse-rewards MDPs (**zrqd** and **Y2Vd**).
* We will add more related work (**ajhV**).
* We will clarify that the agent sees both the environment and the monitor state (**Y2Vd**).
* We will make it more explicit that convergence is guaranteed under a “truthful monitor” (**DPys** and **Y2Vd**).
* Will will rephrase why S-functions lead the agent to the goal state “as fast as possible” (**zrqd**).
* We will add another baseline that learns a separate Q-function with intrinsic reward $1 / N(s,a)$ (**ajhV**).
* We will discuss more why Mon-MDPs are so challenging and why all baselines perform poorly (**zrqd**).
* We will discuss more about future work and how we plan to extend our algorithm to continuous spaces (**DPys** and **zrqd**).

We further thank reviewer **DPys** for saying that *"the main contribution is motivated and it is described completely”* and *“the study of Monitored MDPs has important relations with partially observable environments, and it is very relevant for the broad RL community. Moreover, it clarifies the difference between observing rewards and being only evaluated on them”*. 
We would like to follow-up on this, and emphasize that our paper highlights an important hole in the RL literature: MDPs assume rewards are observable, and areas of research that investigate cases where rewards are not observable (e.g., Active RL) still consider limiting assumptions. Mon-MDPs do not place limitations and formalize the observability of rewards as a separate Markov process, giving great freedom on how to model real-world problems. 
At the same time, however, Mon-MDPs highlight the lack of efficient algorithms with guarantees of convergence and the failure of optimism. While this is well-known for bandits (*“Lattimore and Szepesvari, The end of optimism? An asymptotic analysis of finite-armed linear bandits, 2017”*), RL literature lacks a similar analysis on MDPs. With this paper, we want to contribute to filling this gap with the introduction of an algorithm with guarantees of convergence and a collection of benchmarks, and set the stage for more exciting future research.

Meta-review: 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.
Decision: Accept (poster)