Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper introduces a new specialisation of POMDPs in which actions are annotated with an option to perform additional sensing. Additional sensing incurs extra cost, but its observations are deterministic, which means that the planning agent receives full information about the underlying hidden state whenever the new sensing action is performed. This POMDP formulation is sensible, and there may be practical applications in which it could be used. The authors derive PAC bounds for planning with this new POMDP specialisation, and propose planning algorithms that can exploit the specific nature of their POMDP definition. Both the theory (i.e. PAC bounds) and the empirical results are encouraging.
main_review: The technical contribution is strong, and the overall quality of writing is excellent and most parts of the paper are very clear and easy to follow. I did not try to verify  the proofs, which means that I might have missed potential problems in the purely formal lines of reasoning. I believe that this could be a good NeurIPS paper, but I could suggest a few improvements.

Perhaps the authors could provide some basic intuitive justification as to why the ACNO-MDPs provide tighter bounds. Is this because observations are deterministic and the agent can gain full information about the hidden state whenever it chooses to do so? I am sure that one could find many POMDP benchmarks in which entropy of the belief state is always high. Here, the agent can reduce this entropy to zero if needed. I would be interested in knowing if this the main reason for tighter bounds, or maybe I am missing something and there are other reasons. Having a clear discussion on this in the paper would be highly beneficial.

The user-adaptive experience example has some weaknesses. As long as it is true that constant sensing on mobile devices is energy consuming, the energy requirements of running a POMDP policy itself can be much higher when a POMDP is solved using Monte Carlo planning or a deep neural network is involved. Over the last 10 years multiple research groups have observed that finite-state controllers could be more appropriate for executing POMDP policies on mobile devices. I would say that combining ACNO-MDPs with finite state controllers or equivalent could make the user-experience example more realistic. I cannot buy it in this form.  

On page 5, the authors said "While in our analysis we leverage algorithms that guarantee epsilon-optimal performance in POMDP planning [46, 10], these approaches are
often impractical for any reasonably-sized POMDP.". I think that this is a bold statement or it should be clarified. Does it mean that all the existing research on PAC-bounds is useless? Do the authors want to say that PAC bounds are impractical? This statement can be aggravating for some researchers.

The paragraph that is between lines 197-209 is a bit unclear for someone who does not know [33]. Could you please check it? For example, after reading the paragraph I am not sure why I see GRU units in algorithm 2. GRU was not mentioned in the description of the method in the text above the algorithm.

The paper mentions ethical concerns in line 362. The authors should explain what the reason for those concerns could be. I would assume that in contrast to what the authors said, refusing to use advanced technology to help people would be unethical.

Many acronyms in the references section are not capitalised, e.g., POMDP is always pomdp, Bayesian should start with a capital B, and the "US" shouldn't be "us". Every letter that should be capitalised could be simply put in curly braces in Bibtex. For example, if you type {B}ayesian in Bibtex, you will get Bayesian in your list of references in Latex.

Equations on pp. 22 and 23 have some formatting issues. Also, the table on p. 28 is too wide.

Time in line 1019 is in seconds whereas in line 1024 in days and hours. Please unify the time units. Note that tens of thousands of seconds are not easy to comprehend.

Assuming that the PAC proves are correct, this could be a nice NeurIPS contribution.
limitations_and_societal_impact: No need for improvement.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes action-contingent noiselessly observable MDPs (ACNO-MDPs), where the agent has option to fully observe the latent state after each of their action albeit with a cost. ACNO-MDPs are a special case of POMDPs and the additional structure enables authors to show tighter bounds on the number of episodes exhibiting worse than near-optimal performance.
main_review: Formulation of ACNO-MDPs is very novel and it models a highly important problem: how to balance the cost of collecting information and the returns gained through having additional information? The paper gives good examples of scenarios where this problem might arise.

However, the algorithms proposed to solve the ACNO-MDP problem lack novelty as they mostly rely on existing solutions to the general POMDP problem. The paper considers two frameworks: "observe before planning" and "observe while planning." While the observe-before-planning solution is EULER [62] followed by POMCP [49], the observe-while-planning solution is just POMCP with the added structure of ACNO-MDPs.

In the case of observe-before-planning, one novel question to answer could have been how to determine N optimally such that the cost of additional observation during the first N episodes is balanced with the performance gain in however more episodes the algorithm acts. However, the paper ignores the additional cost of the initial exploration phase completely and just bounds the number episodes needed to act near-optimally in the second phase (Theorem 1). Using this bound as N is not only impractical but also the bound only holds if the POMCP algorithm is replaced with other POMDP planning algorithm with optimality guarantees, which are also said to be impractical to use. (In the experiments, N is just set to be 1000 arbitrarily.)

In the case of observe-while-planning, the paper proposes a belief encoder, which is an adaptation of the DVRL [33] belief encoder. Highlighting how this adaptation differs from the DVRL version could improve the novelty of the proposed solutions.

Other minor comments:
* How realistic is the assumption of being able to fully observe the state in domains given as examples? For instance, in healthcare, performing a test only reveals one aspect of how healthy the patient is.
* In Table 2, how about the sample complexity of an MDP-based algorithm. Similar to how ACNO-MDP is a special case of POMDPs, it can also be viewed as a generalization of MDPs. Seeing how much more challenging learning in this environment is compared with a simple MDP would also be informative.
* In Table 3, the returns of the policy reached after 2000 training episodes is not a fair metric to compare the observe-then-plan solution with the observe-while-planning solution. This metric does not consider the total cost incurred during the training phase hence it favors the former solution, which ignores cost of observing in the first 1000 episodes. A better metric (or an additional metric to consider) could be regret.
limitations_and_societal_impact: Authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper presents a framework to handle a class of problems where an agent, operating in an uncertain and partially observable environment, makes decisions that attempt to maximize a discounted finite-horizon reward. The framework assumes that the agent has some ability to fully infer the state of the system through a costly but concurrent action with the agent's planning function. The authors propose a novel RL algorithm whereby the agent initially learns elements of the dynamics and then applies the learned models to a POMDP planning framework. Additionally, they compare the proposed algorithms to modifications of existing RL algorithms in this unique setting.
main_review: --- after rebuttal: The authors addressed my main concerns, and clearly spent a strong effort on the rebuttal. I'm therefore raising my score. 

Originality: POMDP reinforcement learning is a very diverse field with a disparate understanding of model-types and model classes. Certainly, the authors should not be penalized for not covering every potential instance of mixed-observability Markov decision process. However, they are certainly not the only work where the agent may select an action, at a cost, to reduce uncertainty in their belief of the environment. While they do not exactly match this unique formulation, the following are a few examples (there are many) where similar ideas are explored:

Mixed observability MDPs (MOMDP), in particular, RockSample:

[1] Smith, Trey, and Reid Simmons. "Heuristic search value iteration for POMDPs." arXiv preprint arXiv:1207.4166, 2012.

Active perception frameworks: 

[2] Ghasemi, Mahsa, and Ufuk Topcu. "Perception-Aware Point-Based Value Iteration for Partially Observable Markov Decision Processes." IJCAI, 2018.

[3] Matthijs Spaan and Pedro ULima. A decision-theoretic approach to dynamic sensor selection in camera networks. In ICAPS, 2009

Also relevant:
Non-observable MDPs (NOMDP)

[4] Littlefield, Zakary, et al. "The importance of a suitable distance function in belief-space planning." Robotics Research. Springer, Cham, 2018. 683-700.

Quality:
The policy and optimal policy definitions as defined in lines 135-139 are for an MDP policy and its corresponding optimal policy, which do not hold for POMDPs. The optimal policy for a POMDP is the $\max_{\pi} V^{\pi}(b)$ for all beliefs $b$ in the belief space.

EEPORL [12], the structure upon which the authors build their observe before planning algorithm make a strong assumption about the POMDP domain. Assumption 2 - It is possible to achieve a non-zero probability of being in any state in two steps from the initial belief.
The examples used in this paper do not follow this assumption, which is quite strong.
The simplifying assumption in Definition 3 (line 655 of Appendix) is not sound. The $\alpha$-vector, which represents your t-step conditional policy, is not stationary in this instance since it depends on $\alpha^{\pi_{t-1}_{t-1}(s)$. Further the observation function is effectively eliminating non-observation actions from your analysis so the bound will only apply when an observable action is taken, which reverts to MDP-RL.

Clarity:
The authors are operating with significantly truncated and imprecise definitions of key elements in the framework. For instance, introducing the MDP first would ease the understanding of ``control actions''. Then, explaining how this fits into your particular POMDP, where the action space is modified to account for the observation, would be a more succinct method than introducing the concept of ``missingness''. While occasionally such truncation is required to effectively fit all the material they were attempting to cover into the 9 page limit, in this instance I believe they would have been better served shortening section 6 to provide additional clarity in section 3. Section 3 does not give enough context to conduct the analysis in Section 5 - attempting to provide both analysis and extended experiments in the one paper involves a truncation in both and does justice to neither.

Significance:
The work presents interesting directions for analysis, in particular, the ANCO-MDP model is an useful structure - albeit complicated to convey formally. However, the comparisons to existing learning approaches are still arbitrary (switching between observing and planning in the tabular settings) and problem specific to justify publication.
limitations_and_societal_impact: The healthcare example that the authors list is definitely a good fit with the approach and the formulation. They also do acknowledge the implications and limitations of performing online reinforcement learning in a hospital ICU, which is an important point.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper concerns the class of POMDPs where the agent may obtain a perfect measurement about the hidden state at a cost. The paper argues such POMDPs, called ACNO-POMDPs, appear in many realistic domains such as healthcare. The paper proposes a probably approximately correct (PAC) learning algorithm for ACNO-POMDPs, and proves a finite sample complexity guarantee for it. The sample complexity guarantee is better than in general POMDPs. Further, the paper proposes an extension of the proposed ideas to a more realistic continuous-state and continuous-action setting. The performance of all proposed methods is empirically quantified in three experimental domains, showing that ACNO-POMDP specific methods provide improvements over general POMDP solvers.
main_review: ### Strengths

- The work here attempts to isolate the hardness in POMDP learning due to partial observability by considering a less general but still interesting case where the state is perfectly observable to the agent by paying a sensing cost. The paper coins the term ACNO-POMDP for such domains, and argues that they appear in many realistic applications. This is a novel angle and differs from other proposals in POMDPs dealing with sensing and information gathering, such as using belief-dependent rewards (Araya-Lopez et al., NIPS 2010).

- By consider the (very special) case of a costly perfect measurement channel, the paper is able to bring into play results from fully-observable MDPs which helps the analysis. This technical approach is new to me and it might have further uses in analyzing POMDPs.

- I lack the expertise to fully verify the proofs, but the techniques and overall results appear plausible. The sample complexity result is quite interesting, concretely showing that leveraging knowledge about the observation model leads to improvements over the general POMDP case.

- I also appreciate the extension of the ideas to the continuous-state and continuous-action case, which shows that the results here also have potential impact in large-scale problems.

- The paper is well written and easy to follow.


### Limitations

1. The idea of the sepsis domain experiment is sound, and it would be very useful to demonstrate benefits of ACNO-POMCP in a simple case, as in the other domains (Sect 6.2) there are many other potentially conflating factors. But, I am not sure if the sepsis domain is the best choice. Considering the tabular setting of Table 1, ACNO-POMCP performs within error bounds of generic DRQN, with no significant improvement. That "observe-then-plan" that uses much more exploration works better, which is not wholly surprising considering the algorithmic differences. But again, the sepsis domain is also one example of a high-stakes domain where such exploration might not be feasible, as appropriately acknowledged in the conclusion of the paper.

2. The theoretical results concern the "observe before planning" setting, which requires extensive exploration. This could be impossible in some domains (see also point above), which somewhat diminishes the potential impact of these results.

3. The experimental results reported could be a bit deeper. They do report good overall performance, but some additional ablation studies could shed further light into the POMCP-style or A2C-flavoured methods proposed. It would be interesting to see for example the effect of different belief encodings vs. using a Bayes filter with the learned models. Another interesting baseline might be a planning solution in the tabular domain, to determine the gap between an optimal solution and the "observe-then-plan" or ACNO-POMCP solutions. Reporting any qualitative differences between the policies found by the proposed method versus generic POMDP RL would help understand the methods better. To be clear, I do not demand that specifically these ablations be conducted, rather that any such experiments to provide additional insight would be valuable.


### Minor comments
- From Line 134 onwards, it seems ill-suited to define the policy as a mapping from states to distributions over actions. After all, in the ACNO-POMDP setting the agent might does not necessarily have access to the state. More appropriate would be to define the policy as mapping from action-observation histories or beliefs states.
- Reference numbering in the appendix does not seem to match the main paper, e.g., [62] vs. [63]. This should be corrected.

### After author reply
I am happy with the author response to my comments. I welcome the proposed changes to the manuscript and remain by my accept rating.
limitations_and_societal_impact: The limitations and societal impact are adequately addressed.
review_title: null

Meta-review: The paper proposes a new framework for partially observable RL where agents can pay an additional price to fuilly observe the environment.  This is a useful paradigm for several application domains.  The paper makes contributions both at the algorithmic and theoretical level.  Well done!
Decision: Accept (Poster)