We thank Reviewer TsqN for providing comprehensive and in-depth feedback! We are glad you found the paper well-written and easy to follow. Here, we try to address the points mentioned in order:

I’m wondering to what extent this assumption of full observability restricts potential applications of this theoretically compelling framework, and whether it might be relaxed into a partially observable state and reward setting (like Mon-POMDPs?)

As you have mentioned, the introduction of the Mon-MDPs is not a contribution of our work, but we find it useful to share our thoughts around your insightful scrutiny around the applicability of Mon-MDPs.

We agree that grid-world domains do not represent the real-world applicability of most algorithms. Our choice to run experiments on these domains is because the Mon-MDP framework is relatively new and controlled small-scale experiments help shed light on the understanding of various aspects of this framework. Following the original Mon-MDP paper [Parisi 2024b], we have assumed that the agent receives a joint state from the environment and the monitor. Since these are both MDPs, they could likely be modeled by POMDPs instead. In such a (novel) framework, we imagine the agent would receive the joint observation and techniques from the POMDP literature could be adapted in future work.

The definition of the equivalence class [M]_I for Mon-MDPs under reward observability is not quite self-contained here and should probably include a little clarification on state and action spaces being fixed as per [Parisi et al., 2024b] . The description “the set of all Mon-MDPs that the agent cannot distinguish” confused me for a second, since this may also include much larger but, e.g., bisimilar Mon-MDPs, also rendering the set not a singleton for solvable Mon-MDPs.

As you have pointed out, the definition is given by [Parisi et al 2024b]. But we revisit it in the appendix of the final version and further clarify the concept.

To what extent does the assumption of a fully observable monitor state space restrict the applicability of this approach in real-world scenarios? Are there practical examples where this assumption is clearly justified?

If the state of the monitor and the environment are fully observable to the agent, then Mon-MDPs would suffice. We feel that many monitored settings match the fully observable criteria. Often the RL practitioner is instrumenting the system that provides rewards, and so the full state is more easily known and possibly provided to the learning agent (e.g., the status of sensors that measure reward, or their locations in the world and under what conditions they provide signals). Human monitors, though, might be a good example that would not fit the fully observable setting as they typically would have internal state that could not be provided to the agent.

Would an extension of this to partially observable states (i.e., unobservable monitor states) be possible (like Mon-POMDPs)?

Likely - please see our answer above.

How does this approach scale to larger environments in higher dimensions? What are the limiting factors, e.g., compared to plain MBIE-EB?

The biggest limiting factor is the direct dependency on the counts of visiting state-action pairs or observing the environment rewards (which applies to other tabular methods, including MBIE-EB). As pointed out in the paper in Discussion section Iine 416, using pseudocounts could ameliorate this shortcoming to some extent, which have been applied to improve exploration with Deep RL methods [Bellemare et al., 2016; Tang et al., 2017]. The other limitation (distinct from MBIE-EB) is the computation time of the KL_UCB term, which does not have a closed-form. However, this term can be replaced with a typical $\frac{\alpha}{\sqrt{N(s, a)}}, \alpha > 0$ bonus. This new bonus again can be extended by pseudocounts.

We thank Reviewer gjFL for providing valuable feedback! We are glad you found the algorithmic derivation very well explained. Here, we try to address the points mentioned in order:

An additional theoretical result that the author could try to obtain is the regret from the initial distribution ( allowing the agent to reset from it). In this way the author could argue that they can recover a policy almost as good as the minmax policy in solving the Mon-MDP. The current guarantees only say that the recovered policy is as good as the minmax one for states that are visited by the learner after a long enough number of steps. I think that this is an interesting future direction that the authors could pursue.

We thank the author for the suggestion! We agree that would be an interesting future direction.

I think the authors should add a discussion motivating this metric and referring to these previous works.

We agree. We’ll cite the suggested works and elaborate more on the motivation behind sample complexity in the final version of the paper.

I think that the author should add a pseudocode of the algorithm.

We’ll add pseudocode to the appendix in the final version of the paper.

Have you tried to prove a lower bound to show that the dependence on $\rho^{-1}$ is necessary?

We felt the dependence was indeed necessary, but hadn’t thought about making the argument formal until your question. One can construct hard examples from simple single-state Mon-MDPs (embodying a bandit problem), where arm rewards are only observable with probability $\rho$. Intuitively, since it will take $O(1/\rho)$ pulls to observe any arm’s reward, this should give exactly this lower bound. We will aim to make this formal (building off of Mannor and Tsitsiklis’s (2004) bandit PAC-bounds) in the final version.

We thank Reviewer fk7j for providing valuable feedback! Here, we try to address the points mentioned in order:

It would have been nice to see some non Mon-MDP algorithms performance, especially on MDPs that are less obviously designed with these Mon-MDP algorithms in mind. Similarly, some ablation studies on parameter robustness and different versions of the proposed method would have been insightful and helpful.

In Figure 9 in Appendix B.3 the first column shows the performance on traditional MDPs. Parisi et al. (2024a) showed the superior performance of of Directed-$E^2$ against conventional exploration strategies such as $\varepsilon$-greedy, optimistic initialization, $\varepsilon$-greedy with count bonuses, $\varepsilon$-greedy with UCB bonus and $\varepsilon$-greedy with long-term UCB bonus [Parisi et al., 2022]. Our conclusion is that when our proposed algorithm, Monitored MBIE-EB, outperformed Directed-E$^2$, it simultaneously outperformed five other baselines as well. We will make this more explicit in the final version.

We have run ablation studies on the significance of pessimism and observe episodes in which the agent only seeks observability of the environment reward. The findings show that both are needed to achieve the results in the paper. We’ll add the ablation experiments to the appendix in the final version.

It would have been nice to introduce / describe KL-UCB in more depth, at least define it mathematically.

We have given the explicit formula of KL-UCB in Appendix E, page 26, line 1383. We will add a footnote to the main body of the paper with the formula and reference to the appendix.

We thank Reviewer VJG2 for providing valuable feedback! Here, we try to address the points mentioned in order:

Appendix B.4 states that with random initialization, essentially no learning occurs, but I think a Figure showing this and comparing the performance to MBIE-EB would be useful.

Figure 4.b and Figure 4.c show the lack of Directed-$E^2$'s learning and comparison with Monitored MBIE-EB. We will make a reference to these results in that section of the Appendix.

Figure 6: It looks to me like 4/24 of the environments have on par performance, not 2/24.

We agree with the reviewer that from Figure 6 alone, 4 of the environments look to have similar performance. Due to the scaling of the y-axis, the final performance on two of the plots are difficult to evaluate. You can find rescaled results in Figure 9 in Appendix B.3 where its clear 2/24 have on-par performance, which is the basis for the claim. We will update this figure.