Beyond Optimism: Exploration With Partially Observable Rewards

Thank you for your helpful insights and suggestions. Below, we discuss the main points you raised.

1. We will make the distinction between Mon-MDPs and sparse-rewards MDP more explicit.

2. You are correct, the agent sees both states. We will make it clearer in the final version.

3. 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.

4. 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)$. For 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.

5. 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. However, 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.

6. Every step the button is on.

Thank you for your helpful insights and suggestions. Below, we discuss the main points you raised.

1. 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". We 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). Since 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.

2. 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]$. We 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). Regarding 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).

3. 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.

4. 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). On 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.

5. 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.

6. 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”). The 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. This 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). Our 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. We will write a dedicated paragraph to this explanation in the final version.

I thank the authors for their exhaustive answer!

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

• I share the same concern as reviewer DPys, where all other baselines tested are not aware of the formalism and thus naturally perform worse.

• Also from reading the paper it does not become apparent to me why the goal directed exploration with successor representations is the best way to address the Mon-MDP formalism? I think this has to be very clear, since this seems to be the first concise method to address Mon-MDPs.

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

Thank you!

Thank you for your helpful insights and suggestions. Below, we discuss the main points you raised.

1. Thank you for the additional references, we will add them to the final version. In 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). We would like to stress, however, that [3], [4], and [6] propose model-based algorithms. In 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.

2. 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.

3. We agree that this is an interesting baseline, and we will add it to the final version.

4. 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.

Thank you for your helpful insights and suggestions. Below, we discuss the main points you raised.

1. 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. This 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").

2. 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. We 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. Also, we included a UCB-like baseline (orange line in Figure 5 and 6) that uses the UCB bonus to encourage exploration. We are happy to include more baselines if you have any suggestions.

3. 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. We 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.

4. 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. This 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. We are happy to cite more related work if you have any suggestions.

5. 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.