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.
Paper
Similar papers
Peer review
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.
Strengths
- The algorithm is simple and and intuitive - The paper is generally well-written and I didn't have issues with understanding. - 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$. - For me it was not clear what is the agent state (i.e. what agents sees) in the setting of Monitored MDPs. Does he have acess to both the state of the environment and the monitor or just the environment? As far as I could understand it has to both and I would emhphasise that in the section where you introduce the Monitored MDPs. - The statement that starts in line 174: "As the agent explores, if every state-action pair is visited infinitely often, $\log(t)$ will grow at a slower rate than $N_t(s, a)$, ..." is wrong. It might apply to your algorithm but as you state here is sounds like it holds in general, but that is not true. Consider the case when you visit one state only at the rate $\log(\log(t))$, you still visit it infinitely often but the visition rate is slower than $\log(t)$. - To me corollary 1 is not clear why it holds. I understand the theorem 1, where you say that with your algorithm you will visit every state action pair infinitely often in the limit and that your policy is greedy in the limit, but I don't see why $\hat{Q}$ converges to $Q^*$, how do you update your $\hat{Q}$ from the data? Does the state in $Q$ function depend only on environment state or does it depends also on monitor state? (same for action) - In line 240 you claim that with the policy that comes from successor-function you will visit the targeted state as fast as possible. I think that is not true. With this policy you will maximize the cumulative discounted occurrence. If you were to change your instance reward to $\mathbb{1} \\{(s_i, a_i) \in \cup_{j=t}^k \\{(s_j, a_j)\\}\\}$, i.e. the reward is 1 if you have reached the state action pair in the past, then you would solve the task faster, because in that case you don't care of staying in the state-action pair, but just going there as fast as possible. - In line 280/281 you say that the agent will pay a cost of $-0.2$. Is the agent going to pay the price only when he pushes the button or in every step when the button is on?
Questions
Look at Weaknesses section.
Rating
6
Confidence
3
Soundness
3
Presentation
3
Contribution
2
Limitations
Limitations have been adequately addressed.
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.
Strengths
- The paper is generally well written. I found the illustrations to be useful in understanding the ideas. - The authors perform good experiments, describing baselines the baselines appropriately putting their method’s performance in to context. - 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? - Although the algorithm is effective in tabular spaces it seems non-trivial to expand it to continuous or high-dimensions. The author mention their intentions and cite papers but do not elaborate on for instance how to systematically choose goals in high-dimensional spaces. - There seem to be no other Mon-MDP specific methods that have been compared against. Are there any other methods?
Questions
Questions: - What is the main contribution of the paper? Are the successor features crucial or is it the exploration-exploitation mechanism? The authors motivate the problem very well, but I feel it is not exactly explained why these two components are crucial to improved performance in Mon-MDPS - The authors propose their own set of environments to test their method with success. Are there any other known environments that benefit from the paradigm of unobserved rewards? - Why do the other methods struggle so much on the empty environment? Is it because the sparse reward problem is harder?
Rating
6
Confidence
3
Soundness
2
Presentation
3
Contribution
3
Limitations
I think the authors have adequately addressed limitations in their work.
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!
The fact that other baselines are not aware of the formalism highlights a hole in RL literature, i.e., the lack of algorithms for MDPs with partially-observable rewards (that are not trivial, e.g., the observability of rewards is not just binary but given by another MDP). While there exists reward-free algorithms, they split exploration and exploitation: first, a general exploration policy is learned (environment rewards do not exists at that time), and then tasks are learned. In our paper, we are interested in solving a given task for which rewards **do exists** but are not observable --- the agent is still being evaluated even though it cannot see (sometimes) the evaluation. We argue that this is an important hole in RL literature, and we discussed more on this in the general rebuttal. In particular, a major advantage of our algorithm is indeed not having two separate exploration/exploitation phases: even if sub-optimal at firtst, the goal-conditioned policies are still better visitation policies than classic ones. In this paper, we strived for simplicify and efficiency when we designed our algorithm. The main contribution is to highlight the failure of optimism in Mon-MDPs and the introduction of the general explore-exploit algorithm. SFs naturally satisfy the requirements of our goal-conditioned policy $\rho$ (Section 3, paragraph after Corollary 1) while being simple and straightfoward to implement. A policy maximizing the SFs will maximize the visitation of state-action pairs, while being completely independent from the Q-function (that, as discussed in our previous reply, can be highly inaccurate at the beginning). We don't claim this is the **best** way to address Mon-MPDs but certainly is effective, and it is a first step to fill the hole in RL literature.
Summary
The authors propose a novel exploration strategy for Mon-MDPs based on two policies; a goal-conditioned exploration policy and an exploitation policy which maximizes the underlying reward. The proposed algorithm alternates between the two policies, naturally trading off exploration and exploitation. They show that the proposed strategy is consistent and outperforms standard exploration approaches such as optimistic exploration.
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. There are also works on goal-conditioned RL such as [5, 6] that build on a similar idea for picking and exploring novel goals for exploration. While they do not consider the Mon-MDP setting, I think they are still somewhat relevant to prior work. The authors should write the rate of convergence in the main theorem statement of Theorem 1. [1] Jin, Chi, et al. "Reward-free exploration for reinforcement learning." International Conference on Machine Learning. PMLR, 2020. [2] Chen, Jinglin, et al. "On the statistical efficiency of reward-free exploration in non-linear rl." Advances in Neural Information Processing Systems 35 (2022): 20960-20973. [3] Mania, Horia, Michael I. Jordan, and Benjamin Recht. "Active learning for nonlinear system identification with guarantees." arXiv preprint arXiv:2006.10277 (2020). [4] Sukhija, Bhavya et al. "Optimistic active exploration of dynamical systems." Advances in Neural Information Processing Systems 36 (2023): 38122-38153. [5] Nair, Ashvin V., et al. "Visual reinforcement learning with imagined goals." Advances in neural information processing systems 31 (2018). [6] Hu, Edward S., et al. "Planning goals for exploration." arXiv preprint arXiv:2303.13002 (2023).
Questions
1. Instead of a goal-conditioned policy, could one not train a policy with $1/N_t(s, a)$ as reward (or $-N_t(s, a)$)? In essence, this policy will try to visit states that have a low visitation count. While the reward in this setting is non-stationary, empirically this might perform better. What do the authors think about it? 2. Could [4] from above be used for active learning of dynamics and then later exploitation for general continuous state-action spaces with Mon-MDPs? Moreover, I am curious if any general active learning/reward-free RL algorithm can be combined with greedy exploitation to obtain convergence guarantees for Mon-MDPs. I am happy to increase my score if my concerns and questions above are adequately addressed.
Rating
6
Confidence
5
Soundness
3
Presentation
3
Contribution
3
Limitations
The authors address the limitations of their work in the main paper (lines 336 -- 349).
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.
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. (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. (reproducibility) The authors provided a full, well-documented Python source code of the algorithm, which ensures reproducibility. They also provided the necessary configuration files. (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. 2- The evaluation compares the algorithm with other 4 baselines in some environments. However, none of the baselines have been specifically designed for Monitored MDP, nor for any component of partial observability on rewards, and it is unsurprising that many of these do not perform well. As such,the experimental evaluation gives little insights about the improvement that the proposed algorithm leads among Monitored MDP algorithms. If RL algorithms for this class do not exist yet, because the formalism is recent, then it should be also compared with algorithms are aware that rewards are partially observable, or nonstationary. Finally, the black line, which is Q-learning with optimistic initialization, is taken as a representative of "optimism". However, this is only a specific instance of optimistic approaches, and I believe that "optimism" would be better represented by UCB-style RL algorithms. 3- The contribution of the paper is limited for the following reasons: a- The algorithm mostly succeeds because it tries to reach all states of the MDPs via explicit exploration. This is generally intractable for large state spaces, or MDPs with high (or infinite) diameter. Optimism solves this issue by avoiding exhaustive exploration. This makes the idea behind the algorithm more naive than other existing optimistic approaches, especially for larger state spaces or small probabilities. Indeed, the algorithm does not seem to directly address the fact that a monitor is present, even though it has this prior information available. b- The use of Successor Representation made in the paper is mostly standard in the literature. The authors say that only Machado et al. [40] used SR to drive exploration. However, we should consider that using SR as value functions is completely equivalent to placing unit rewards in goal states. Then, similar approaches are taken by the works in goal-conditioned RL that learn goals using unit rewards, even though SR are not explicitly mentioned in those papers.
Questions
4- Why does the UCB baseline use an epsilon-greedy policy? I would expect bonuses to be sufficient for exploration. Epsilon-greedy may unnecessarily show it down. The authors may also address any of the weaknesses above, especially number 1.
Rating
6
Confidence
4
Soundness
3
Presentation
4
Contribution
2
Limitations
Most limitations have been already discussed in the paper. The work has no direct societal impact.
Response to Author's rebuttal
2. I think not having convergence rates is a drawback of the work. What is it that limits the authors from doing so? Intuitively, wouldn't a rate on the visitation frequency directly result in a rate for Theorem 1? This is what is at least shown in [4] (c.f., Lemma 13) 4. I am not sure if this is true for methods such as [3, 4]. In the end, they are similar in spirit to the proposed algorithm -- they visit the states where they have the highest uncertainty/lowest visitation count (exploration phase). In principle, they could be combined with a similar exploitation phase as proposed by the authors. Am I missing something here? In the end, this approach would be equivalent to the baseline discussed in the third point. Whereas, the algorithm in [6] is similar to what the authors propose. Could the authors comment more on this?
About convergence rate and related work
**About the convergence rate** Getting a non-trivial convergence rate is likely not possible. The algorithm as presented uses $\epsilon$-greedy as the exploration method to learn the goal-conditioned S-functions. In the worst-case, this will admit $\epsilon$-greedy's poor convergence rate (and may take exponential-time in MDP size to even just visit the goal once). We could give a competitive convergence rate if optimal goal-conditioned S-functions are known in advance, but that didn't feel particularly informative. We could also replace the exploration mechanism (i.e., to follow $\rho$ and S-functions) within the exploration phase to use a more sophisticated mechanism, but we are explicitly aiming for a model-free algorithm so many choices common in literature are not suitable (e.g. MBIE, UCRL). For example, in [4], Lemma 13 refers to Eq. 16 where the problem considers the true transition function $f^*$, and the make use of it in Corollary 7. On the contrary, we don't learn any model, and we don't know the true S-function $S^*$ either. Even knowing $S^*$, we don't think Lemma 13 can be straightforwardly applied to our case. We choose a model-free algorithm (Q-learning) because we wanted to keep the method as simple as possible, while demonstrating its effectiveness through experimentation rather than theory, particularly showing that it can handle partially observable reward settings like Mon-MDPs (where traditional MDP exploration mechanisms can fail). Maybe a middle-ground might be to present a convergence rate that implicitly depends on the convergence rate of whatever algorithm is used to learn the goal-conditioned S-functions. This could show how much is lost due to the goal-directed exploration component that is needed to handle Mon-MDPs. We would then continue with experiments showing its performance with the simple $\epsilon$-greedy mechanism (even though it's not theoretically well-motivated) showing its strong performance across the tested environments. There is another angle of analysis that is distinctly more difficult as it likely would need new theoretical machinery (beyond the scope of this work). In particularly, we believe that most of the advantage of our algorithm comes from the goal-conditioned policies finding sub-optimal but still useful visitation policies. These policies can still be used to dramatically accelerate the learning of the Q-functions, allowing fast exploitation possibly even before the S-functions have identified optimal exploration policies $\rho$. We believe that this is a great advantage of not breaking the problem into some explicit exploration-only phase (e.g., as in [1]). This would almost certainly need some instance-specific analysis, though. Would the middle-ground option of a convergence rate that depended on the convergence rate of the goal-conditioned policy learning be a sufficient addition? In any case, we can add a more thorough discussion of this in the paper. **About related work** Yes, they could be combined with our approach. Maybe there has been some misunderstanding: we didn't mean that [3], [4], and [6] are unrelated, but just that they are different being model-based. For example, [3] estimates uncertainty in the feature space and uses a model to plan a trajectory to high-uncertainty states. We use counts (rather than uncertainty) and don't plan trajectory, but instead follow one-step S-function values. While replacing uncertainty with counts could be straightforward, [3] still has an extra component (the model) that allows for more powerful long-term reasoning. We believe that combining our algorithm with [3] and [4] could be promising for future work. Regarding [6], the main similarity is the presence of a goal-conditioned policy for exploration, but their algorithm is still quite different (beside being model-based). First, [6] alternates between exploration and exploitation at every episode, while ours uses a more grounded criterion (the ratio $\beta). Second, the goal of their goal-conditioned policy is randomly sampled from the replay buffer and optimized via MPPI, while ours is the state-action pair with the lowest count. Third, their reward for training the goal-conditioned policy is given only at the end of the trajectory and depends on the number of actions needed to reach the goal, while ours is given at every step by SRs. We'd like to stress once more, however, that we didn't mean to say that [3], [4], and [6] are unrelated, and we will reference them in the final version.
Response to Author's rebuttal
Thanks, my concerns are clarified. While I would like to stick to my score for the paper, I have gained more confidence in the paper, i.e., I have increased my confidence from 3 to 5.
1. I appreciate this important change. This assumption is very reasonable to assume and it would not limit the impact of the paper. 4. b) I said that this use of successor representations is mostly standard in goal-conditioned RL literature because from what concerns the policy $\rho$, the approach appears to be equivalent to learning $|SA|$ policies using Q-lerning, where a reward of 1 is placed in one state-action pair for each policy. The overall algorithm is still original, to the best of my knowledge. I mainly argue that the exploration strategy is not only related to directed exploration with SR features, but also goal-conditioned policies. The other replies are also relevant. My main remaining concern is that the technique "is generally intractable for large state spaces, or MDPs with high (or infinite) diameter.", given that the algorithm must learn a distinct policy for each state and action in the MDP. Despite this significant limitation, the paper is well written, clear, correct and the results appear to be mostly reproducible. So, I have increased my evaluation to weak accept.
Decision
Accept (poster)