Reinforcement Learning with State Observation Costs in Action-Contingent Noiselessly Observable Markov Decision Processes 
Authors: HyunJi Nam
Scott L Fleming
Emma Brunskill
Venue: NeurIPS 2021 Poster (2021)
Keywords: Reinforcement Learning
Observation Cost
Markov Decision Process
MDP
Partially Observable Markov Decision Process
POMDP
Probably Approximately Correct
PAC
Healthcare
Health care

Abstract: Many real-world problems that require making optimal sequences of decisions under uncertainty involve costs when the agent wishes to obtain information about its environment. We design and analyze algorithms for reinforcement learning (RL) in Action-Contingent Noiselessly Observable MDPs (ACNO-MDPs), a special class of POMDPs in which the agent can choose to either (1) fully observe the state at a cost and then act; or (2) act without any immediate observation information, relying on past observations to infer the underlying state. ACNO-MDPs arise frequently in important real-world application domains like healthcare, in which clinicians must balance the value of information gleaned from medical tests (e.g., blood-based biomarkers) with the costs of gathering that information (e.g., the costs of labor and materials required to administer such tests). We develop a PAC RL algorithm for tabular ACNO-MDPs that provides substantially tighter bounds, compared to generic POMDP-RL algorithms, on the total number of episodes exhibiting worse than near-optimal performance. For continuous-state ACNO-MDPs, we propose a novel method of incorporating observation information that, when coupled with modern RL algorithms, yields significantly faster learning compared to other POMDP-RL algorithms in several simulated environments.

Reinforcement Learning with State Observation Costs in Action-Contingent Noiselessly Observable Markov Decision Processes
HyunJi Alex Nam*
Scott L. Fleming*
Department of Computer Science
Department of Biomedical Data Science
Stanford University hjnamocs. stanford. edu
Stanford University
scott scott.flemin fwe.rfflmmmnggcs...mm wwwpinggssssstaffrrooooooooe stanford. edu
Emma Brunskill
Department of Computer Science
Stanford University
ebrunêcs stanford edu
Abstract
Many real-world problems that require making optimal sequences of decisions under uncertainty involve costs when the agent wishes to obtain information about its enviromment. We design and analyze algorithms for reinforcement learning (RL) in Action-Contingent Noiselessly Observable MDPs AACNO-MDPs), special class of POMDPs which the agent can choose to either (1) fully observe the state at a cost and then act; (2) act without any immediate observation information, relying on past observations to infer the underlying state. ACNO-MDPs arise frequently in important real-world application domains like healthcare, in which clinicians must balance the value of information gleaned from medical tests (e.g., blood-based biomarkers) with the costs of gathering that information (e.g.. the costs of labor and materials required to administer such tests). We develop a Probably Approximately Correct (PAC) RL algorithm for tabular ACNO-MDP4 that provides substantially tighter bounds compared to generic POMDP-RP RL algorithms, the total number of episodes exhibiting worse than near-optimal performance. For continuous-state ACNO-MDPs, we propose a novel method of incorporating observation information that, when coupled with modern RL algorithms, yields significantly faster learning compared to other POMDP-RL algorithms in several simulated environments,
Introduction
Reinforcement learning (RL., which involves learning to make sequences of good decisions in stochastic environments, has had many impressive successes over the past decade 60 68). While many of the more visible successes have occurred in simulated environments, such Atari video games
58 reinforcement learning has increasingly been used to solve real-world problems
42 34 One key difference between reinforcement learning in simu- lated Vs. real-werree world environments is that, in most simulated environments, the agent can fully observe the underlying state each time step with additional observation costs. In contrast, real- world environments frequently entail state observations that are noisy and/or costly, but optional. Environ-
IC
47
37
51
*Equal contribution
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

ments in which state information at each time step can be noisy or missing are more appropriately modeled as partially observable Markov decision processes (POMDPs) rather than MDPs (29
In this paper, we provide theory and algorithms for a special class of POMDPs in which state information is complete/noiseless when observed, but may be missing any given time step if the agent chooses not to observe the state. We call this class of POMDPs Action Continn-nnttnentt Noiselessly Observable MDPs (ACNO-MDPs), which can be useful for capturing number of important real- world settings, such as:
ACNO-MDPs in healthcare. Clinicians in Intensive Care Units (ICUs) frequently have to make sequences of treatment decisions under uncertainty for patients at risk. While accurate laboratory tests can inform such decisions, administration of these tests carry significant cost for the patient and the health system
[25]_ These costs, together with the fact that frequent testing may be redundant and wasteful 212 appropriately lead clinicians refrain from constantly observing the patient state (i.e., ordering laboratory tests) [7 Similarly, other settings such as glucose monitoring to assist in insulin dosing recommendations [ or white blood cell count monitoring to assist in anti-HIV drug dosing [ have modern tools for accurate observations of biomarkers and could be appropriately modeled by our ACNO-MDP framework.
ACNO-MDPs for user-adaptive experiences. Applications on mobile phones and other personal devices can collect information on the user's 's status, such as location, motion, inter-user contact, and background noise, in order to adaptively suggest features that enhance the user's 's experience [69 770 While these sensors can in theory always be kept active, battery consumption due constant sensing would make such applications less desirable to the user. Modeling this problem as an ACNO-MDP could enable policy that balances battery usage with personalizing the user's experience. |
Our contributions. Our main contributions are:
Proposing a Probably Approximately Correct "Observe-then-Plan algorithm for tabular ACNO-MDPs that fully observes while exploring, then employs POMDP planning using learned models. The resulting policy can select when to observe to achieve high expected reward in environments with state observations that are costly but optional.
Providing finite sample guarantee for the above algorithm in environments with discrete states and actions, such that the number of episodes exhibiting worse than near-optimal be- havior is no larger than O 5 A H Rovs 2,4 with = OIn (SAH/ with high probability. This improves over prior work targeted towards more general POMDP problems (Table 4
Developing an algorithm that extends these ideas to ACNO-MDPP with continuous state and action spaces. We introduce novel belief state encoder that can be coupled with many modern deep RL. algorithms to solve problems with observation costs, which we demonstrate with several simulation experiments.
2
Related work
Learning in POMDPs without known model of the environment (i.c., with neither model of state-to-state transition dynamics nor a model of observations conditioned on states) is significantly
more difficult than learning in MDPs 2 Thus while there is rich literature on planning in
POMDPs with a known environment model 3 7
23
35
39
40
50
53
54
57
59
62
including in Mixed Observability MDPs (MOMDPs) 61.. active perception frameworks 19 63
and Non-Obbervvale MDPs (NOMDPs) 38), fewer approaches exist for RL POMDPs (POMDP- RL). One key difficulty in general POMDP-RL is that, without known observation model, the agent can never know with certainty which states were actually visited. Approximating a transition model for use in subsequent planning thus becomes infeasible without additional assumptions the observation model. Many approaches in POMDP-RL, such as the Addys--e POMDP (BA- assume access to an informative prior distribution over the observation model and maintain posterior distributions over the environment model parameters. These algorithms plan using belief distributions over states rather than the states themselves. More recent
POMDP) (2 56 and its variants 31 3
While some of the POMDP-RU RL methods proposed in this paper may not be energy efficient, recent approaches for compiling and compressing policies into approximately equivalent finite-state controllers could enable energy efficient adaptive applications that both sense and change behaviors adaptively (20]

---

approaches like Deep Recurrent Q-Networks (DRQN) 22 70 and Deep Variational Reinforcement
Learning (DVRL) 4 use neural network- based sequence models learn a condensed representation of the agent's s action and observation history and apply modern RI. algorithms (e.g., DQN 44 A2C
(72) on this learned representation. These approaches show promising empirical performance but lack theoretical guarantees and do not leverage the specific structure of ACNO-MDPs.
Theoretical guarantees on a POMDP-RL algorithm's performance can be beneficial when gathering samples under a suboptimal policy is costly. Though recent works have been able to provide theoretical guarantees in surprisingly broad classes of POMDPs, these works either provide regret guarantees (not sample complexity guarantees) 244 (o), or make assumptions about the structure of the observation matrix which do not hold in ACNO-MDPs (e.g.. that the observation matrix is full rank [2 or its singular value is bounded away from 0 (7)). To the best of our knowledge, our work therefore provides sample complexity guarantees for a subelass of POMDPs in which no such prior guarantees existed.
Closely related to our work, Klima et 3 consider RL in environments where the state is fully observed, but only intermittently. However, whereas Klima et al. 33 consider environments in which the agent cannot control state observation frequency, we address RL in environments where the agent can decide when to observe, albeit at a cost. Similarly, Yoon et al. 74] and Chang et al. | use RL methods to learn policies for active sensing/dynamic measurement scheduling. these works, however, the reward is directly tied to prediction accuracy and agents have no influence on the underlying state beyond observation whereas we focus on agents that can influence the state.
Since acceptance, it has come to our attention that earlier work by Zubek and Dietterich 80. Zubek et al. [8]] and Bellinger et al. 4 proposed RL approaches for learning optimal policies that both modify and observe the state at each time step, as in our problem setup. However, these prior works only provide algorithms for tabular environments and do not provide any theoretical analysis bounding the sample complexity. Related contemporaneous works by Yin et al. 73 and Bellinger al. (5] tackle the problem of RL with observation costs in continuous-state POMDPs and MDPs, respectively: Yin et al. A considers setting where individual elements of the state vector can be observed at each point in time and Bellinger al. [5] performs a more in-depth qualitative analysis of agents' measurement patterns throughout training.
3 Problem setting
Action-contingent noiselessly observable Markov decision processes (ACNO-MDPS). A discounted, finite-horizon ACNO-MDP is an environment detined by a tuple M A, O, r, b, If), where S and A are state and action spaces with cardinalities S and A. respectively. The action space A consists of tuples (control actions) x (observe, not observe). As in POMDPs, the observation space, O, has cardinality O, and is related to S by the observation/emiision function p(ols'a) a). which defines the probability of observing o if the agent has taken action a and is now in s'. In ACNO-MDPs, however, the observation space is specifically constrained to be O= S (missingness), where the "missingness" observation provides no information whatsoever about the underlying state. 'The "action-contingent noiselessly observable" aspect of ACNO-MDPs derives from the fact that p(o]s' (loberre) if and only if o = 8', while p(o'|s', (lohserve) = 0 for all other observations o' * s'. Similarly, p(o|s', Onot observe) = 1 if and only if o = "missingness".
While observations in ACNO-MDPs are deterministic, transition dynamics may be stochastic. The probability of transitioning to state s' after taking action a from state s is given by p(s'|s (s,a). We let b represent a belief distribution over possible states, subscript the time step within the episode, and H the episode length. We denote the number of times the state-action pair (s, is visited across episodes as n(s,a).
At each time step, the agent receives expected reward r(s, a), which includes the control-associated reward from executing action in state 8 plus an observation cost c(s,a) S 0. If the state is not observed, c(s, a) = O. Thus, for any action a, r(s, (ohuerve) = r(s, Gnot observe) + c(8, Gobserve). Observation costs are assumed to be known in advance. Without loss of generality, we assume 0 < r(s, a) < Rmax for all states s and actions a. We assume stationary dynamics, observations, and rewards, but allow for nonstationary policies in light of the fixed horizon length. A t-step policy, T-)-), is a function that maps belief state distributions to distributions over actions. We let 3 (bo) ~e ΣE=> 7 E.es (s)r(s,, a:) represent the expected return obtained from
3

---

starting in by and following t-step policy, Tr, with discount factor E [0, 1]. An optimal policy, T"" is policy for which V (b) max= V (b) for all beliefs b in the belief space. The goal of ACNO-MDP learning is to find the policy æ that maximizes V (bo). We evaluate our algorithms using the notion of sample complexity [30 [651 a measure of how much data is needed to learn near-optimal policy. An algorithm Probably Approximately Correct (PAC) if its sample complexity 65
is polynomial in relevant quantities (e.g., S, A, H) with high probability
Leveraging the specific observation structure of ACNO-MDPs can improve data efficiency in two ways: (1) when the agent observes during exploration. it can more rapidly learn an accurate approxi- mate transition model; and (2) this improved transition model can be used for better state estimation during POMDP planning, as the underlying state transitions for observed and unobserved states are identical. Faster convergence an accurate model of the environment and subsequently better planning reduce sample complexity bounds, as we demonstrate both theoretically and empirically.
4 Algorithms
We propose two high-level frameworks for finding near-optimal policy in ACNO-MDP settings. The first is "Observe before planning" (Algorithm D]. which initially spends fixed number of timesteps always observing states in order learn accurate models of the transition dynamics and rewards, as if in MDP, then switches to computing near-optimal POMDP policy using these models. The second "Observe while planning", which incorporates the known ACNO-MDP observation structure (i.e., that observation emissions are identical to underlying states following choice to observe) into an existing POMDP-RL algorithm.
Our proposal for "Observe before planning" follows the structure of EEPORL 21 which devotes a fixed number of episodes to exploration in order to accurately estimate models of transition dynamics, rewards, and the function mapping states to observations. We highlight three key differences between EEPORL and our approach: (1) our "Observe before planning" framework only needs learn models of the transition dynamics and reward function, since the observation model is known and every transition can be exactly identified the agent chooses to observe; (2) our method can track exactly which state-action pairs are observed during the initial full observabllity-epiodde in which the setting effectively an MDP; and (3) our method does not require EEPORL's 's assumptions about state transition probabilities, observations, and rewards (their Assumptions & 3), whereas EEPORL depends on these to guarantee that outcomes of every action are uniquely identified.
The motivation for "Observe while planning" is that any POMDP-RI. algorithm can be simplified in ACNO-MDP settings by leveraging the known ANCO-MDP observation function, which gives the true underlying state if the agent chooses to observe. and an uninformative state otherwise.
The purpose of both frameworks is improve sample efficiency by leveraging the known observation structure in ACNO-MDP settings, empirically and/or theoretically.
Algorithm 1 Observe before planning
1: Set dataset D < 0
2:
for episode = to N do > N is # of episodes spent exploring (e.g., Thml gives one example of N)
3: Reset to initial state 80
4: for step 1 to H do
5: Pay to observe every (8, ,,,''r) and store into
6: end for
7:
end for
8: Calculate maximum likelihood estimates of transitions p(s, a, and rewards f(s, a) using D
9: Return policy a from POMDP planning under p, f
In our experiments, we instantiate these frameworks into specific algorithms and compare them against MDP-RL methods, which learn an always-observing policy regardless of the cost of observation, as well as sate-offthe-arr
FOMDP-RL algorithms (e.g., DRQN (22] and DVRL 4 which do not leverage any knowledge about the ACNO-MDP observation function. summary of all algorithms used for comparison is shown in Table I and training details are provided in the Appendix.

---

Table 1: Summary of our algorithms and baseline approaches.
Framework
Algorithm name
Setting
Observe before planning
Observe-then-Plon Plan (Ours)
Tabular
Observe while planning
ACNO- (Ours)
Tabular
Generic POMDP-RL
DRQN P2
Tabular
MDP-RL
EULER VI 76
Tabular
Observe while planning
ACNO-A2C (Ours)
Continuous States/Actions
Generic POMDP-RL
DVRL 15
Continuous States/Actions
MDP-RL
A2C
45
72
Continuous states/Actions
4.1 Observe-then-llan algorithm for tabular ACNO-MDPs ("Observe before Planning")
For tabular ACNO-MDP domains, we provide the Observe-then-Plan algorithm an instantiation of the "Observe before planning" framework. Observe-then-Plan decouples exploration from planning, following prior work EEPORL [1 and reward-free exploration PS In contrast to this prior work, which addresses non-stationary domains, we focus on domains with stationary dynamics and rewards in finite episodic setting. The first key algorithmic step Observe-then-Ploe relevant state-action pairs sufficiently many times, while observing at every time step, so as to learn accurate models of the transition dynamics and rewards. For the purposes of our theoretical analysis, we employ EULER 776 in this exploration phase, as it provides state-of- of-the-art algorithm cumulative regret guarantees for episodic MDPs. We note, however, that any MDP-RL algorithm can be used for this step. The second key algorithmic step in
to visit all
is to use the models of transitions and rewards estimated from exploration data for POMDP planning. While our analysis we leverage algorithms that guarantee e-optimal performance in POMDP planning [56 16, these approaches quickly become computationally challenging or intractable for any reasonably-sized POMDP [49] In our experiments therefore POMCP, popular and fast POMDP planning algorithm [59
4.2 ACNO-POMCP/ACNO--2E alggooosss ("Observe while Planning"))
Although our theoretical guarantce (Theorem D requires the agent to initially spend a fixed number of episodes exploring while observing every time step, this extensive exploration and observation may be unnecessary for obtaining near-optimal performance in practice. This motivates our second framework "Observe while planning." under which we incorporate the known observation structure into an existing state-of- of the--rterrtt art POMDP-RU RL method.
For tabular settings, we instantiate the "Observe while planning" framework with the ACNO-POMCP algorithm. CCCO-PPOME simultaneously (1) uses online POMCP to plan optimal trajectories based on simulated rollouts with the models learned so far, and (2) updates the approximate reward and transition models used in these simulations every time new sample (s, a, s', is observed from the true environment. Note the observation function does not need to be learned because the algorithm leverages the fact that p(ottp(oaaaaaaaa Gubserve s') d')= = and only if o = s' and p(o)ap Apot observe. s') = 1 if and only if o "missingness"" Thus model estimation in MAMN-PPMCPPPM.M reduces to MDP model estimation, but the algorithm does not quantify the policy's 's degree sub-optimality because when and how often to observe are determined by the online RL agent.
For ACNO-MDPs with continuous state spaces, we instantiate the "Observe while Planning" frame- work with the ACNO-A2C algorithm by modifying DVRL, state-of-the-arr POMDP-RI algorithm for continuous state space settings. As in the DVRL algorithm, ACNO-A2C relies on (1) a belief encoder model (a Gated Recurrent Unit-Recurne ing histories of past actions, observations, and inferred states; (2) a belief updating model (also a GRU-RNN) that updates the encoded history based on the current observation, inferred state, and prior history; (3) a stochastic transition model, (0 h4- a)-1), representing the probability of visiting underlying state 2 given encoded history h and action a;-1, which is instantiated as multivariate normal distribution whose mean and diagonal variance are governed by neural network; and (4) A2C for policy learning [43]
Neural Network, GRU-RNN [)] for encod-
In our work, we modify the DVRL belief encoder model to incorporate the known observation
structure follows: The original DVRL belief encoder maintains (weighted) set of belief particles,
5

---

each of which represents an encoding of the agent's 's state and action history based on past observations and actions. When a new state observation received, each particle is updated with latent state sampled from a stochastic transition model conditioned on the past history and current observation. Each particle then assigned weight proportional to both the likelihood of the agent being in the sampled state and the likelihood of that particle emitting the received observation from that state. In ACNO-MDPs, we split this updating process into two cases. First, if the agent chooses to observe, then there is no uncertainty in the underlying state; every belief particle is updated with the same, observed state and the weights for these particles are distributed uniformly. On the other hand, if the agent chooses not observe, underlying states are stochastically sampled from learned transition model, as in DVRL, but in this case the learned transition model does not incorporate information about the observation because it will always be the "missingness" state following a non non-observing action. Weights assigned to each particle following a no-observation action are proportional to the probability of reaching the sampled state given the encoded history and action chosen in the previous time step. The belief encoder model is only updated after each observing action, in which case the model loss is the negative log likelihood of visiting the observed state under the transition model.
Algorithm 2 ACNO-A2C belief encoder
Input Previous belief set by-1, observation or, action at-1- Output b,, and belief encoder loss Lime
_1:K 11-11 11-11 t- b 1: Unpack w 10-1:
2:
for every particle k = ..... K do
3: Resample previous context hi
h.-4 based on weights
4: if' aa-1 = observe then
5:
2t = 0;, w K
6:
Le Le log palpoo (c-1)
Approx. density, stochastic transition model
7:
else
8:
Sample of (=(= ( a W. + p2(2 [ a)-1)
Sample from the stochastic transition model
9:
Estimate density under stochastic transition model
10: end if
GRU 2hi Oc, ax-1) h
Belief updating model
12: end for
13: hy -GRU(Concat(rrf 2t l1t)
Belief encoder model
14: Pack be + -wil KK 22 h1 h4) and include 2 a; = observe.
5 Analysis
Observe-then- Plan outperforms ofate-of-thh-art PAC POMDP-RL sample complexity bounds (OOM- UCB (26,, Table 4 by factor of S0 in ACNO-MDP settings, while increasing these bounds by factor of H and logarithmic quantities. We note, however, that prior state-of-the-art PAC POMDP-RL algorithms make assumptions on the structure of the observation matrix that do not hold in ACNO-MDP thus limiting the utility of direct comparisons. Specifically, when agent chooses not to observe in the tabular ACNO-MDP setting, the observation matrix O E R($+1)x5 has single row with values corresponding to the "missingness" observation and all other rows are zero (since each column vector represents P(o) s',, a) for given (s', a) and Gnot observe deterministically returns o "missingness", ) This leads to rank deficiency in the observation matrix, violating assumptions made in Guo et al. [21] and o min (0) O, violating the assumptions made in Jin et al. [26]. Thus, to the best of our know ledge our results provide sample complexity guarantees for a class of POMDPs not covered by prior POMDP-RL work. These guarantees hold for ACNO-MDPs with arbitrary state dynamics and hard-to-reate states.
Theorem 1.
Let M be any ACNO-MDP with observation cost c(s, Gobscrv)) O for all (s, a) e
S x A. and reward bounded between [0, Rmax]. Let by be the initial belief, and let and 8 be two positive real numbers. Following Observe-then-Plaa will achieve an expected episodic reward
of (bb) 2 V (bp) - after a number of episodes that bounded by O S A² Ri where = O(n (8)H with probability at least - 8.

---

Table 2: Sample complexity comparisons
Algorithm
Setting
Transition
Sample Complexity
OOM-UCB 26
POMDP
non-stationary
H 1'0 Oum e
H Yan A R'O's"
EEPORL 21
POMDP
stationary
Caaal (5 J (T. (Ta)a (R, (0.13
Observe-then-Plat
ACNO-MDP
stationary
Ö
Proof sketch. (Full proof' provided the Appendix). First, we note that prior work on POMDP-RL provides guarantees on expected performance, i.e. V(bb) > V* (bo) -, e, provided that value function estimates are sufficiently close to the true value function 2II. With sufficiently accurate estimates of the ACNO- transition and rewards models, we can bound the enror of the value function
estimates computed under those models (following the EEPORL analysis) 16 21 [55. Prior work on Model-based Interval Estimation 64 i allows us bound model estimate errors (i.e., llğ pll1 and f r|) in terms of the number of visits, n(s, a). Using this, we can find the number of times each state-action pair must be visited in order to guarantee sufficiently accurate ACNO-MDP model estimates. Call this number m. Reward- free exploration [28] with EULER (76] guaranteess that, with high probability, the agent will visit each state-action pair least times after a certain number of
episodes, N. We show that this number N is O
5 A H² Re ); in other words, after N episodes of EULER for exploration, the agent has visited sufficiently many state-action pairs, (s, a), learn near-optimal policy that trades off between observing and not observing.
ea
Only the exploration phase of Observe-Ihen-Plan contributes its sample complexity, as planning requires no additional sample collection. In generic POMDP settings where the true underlying states are inaccessible, bounding the estimated model errors is difficult because the number of times each state-action pair is visited cannot be measured. In ACNO-MDP settings, transition and reward models can be estimated via simple MLE if the agent is willing to initially pay the cost observation. Note that in ACNO-MDD settings, each control action has two versions: an observed version and an unobserved version. In both versions, the influence of the action on the state identical (i.e., p(s' |s. Gabserve) = p(s'l p(s'|s, Gnnt observe)), )), and the cost of observation is assumed to be known. Therefore the learned dynamics and reward models from the observed version of an action can also be used for its unobserved counterpart, and when planning an optimal action sequence, the agent can determine whether the value of deterministically observing the true state, instead of relying on the estimated state transition model, outweighs the cost of observation.
6 Experimental results
In order to analyze the empirical performance of our proposed methods in both tabular and continuous state-action spaces, we evaluate the algorithms from Table [n (1) tabular ACNO-MDP environment designed to simulate patient care in the Intensive Care Unit; (2) a continuous- state, discrete-action "Cart Pole" environment; and (3) a continuous-state, continuous-action "Mountain Hike" environment.
6.1 Algorithms for tabular ACNO-MDPs
Sepsis simulator Our first environment simulates a Sepsis patient and the effects of several common treatments. Adapted from Oberst and Sontag 48 our "Sepsis simulator" defines the state space as (heart rate, blood pressure, oxygen concentration, glucose level], each of which can take on several discretized state values (so in total, tabular S 720). The action space is defined of binary treatment options consisting of aantibiotics, vasopressors, ventillation), J, each of which can either be "on" "off". We augment the action space by coupling each action with options of observing and not observing. A reward of 0 is given if the patient reaches a terminal "death" state, if the patient reaches a terminal "discharge" state, and 0.25 otherwise. We provide results for each algorithm under two different fixed observation costs, -0.1 and -0.05.
combination
Algorithms We compare four different methods for learning an optimal policy in the Sepsis simulator. For learning a POMDP policy, the algorithm selects the highest rewarding action from Monte-Carlo rollouts for computational tractability instead of computing the exact policy.
7

---

Table 3: Average discounted returns (mean + standard error) on Sepsis. Standard errors represent the standard error of the mean return obtained from 3 separate seeds, each with rewards averaged across 50 simulated rollouts at the end of 2000 training episodes using greedy action selection.
Observation Cost
Observe-then-PPee Plan
ACNO-POMOS
DRQN (Generic POMDP-RL)
BULER-VI VI (MDP-RL)
(Observe before planning)
(Observe while planning)
-0.1
0.754 + 0.011 0.740 + 0.017
0.602 + 0.029
0.593 + 0.079 0.593 + 0.036
0.492 - 0.011 0.638 + 0.025
-0.05
0.625 + 0.024
Observe-then-Plan (instantiation of "Observe before Planning") is our originally proposed Observe- then-Plas Plan algorithm (Section 4.1 with reduced number of episodes (compared to the proposed H S A² A²/c² episodes) spent on exploration, in order to make the algorithm computationally tractable.
(instantiation of "Observe while Planning") is an adaptation of the POMCP online planning algorithm to the learning setting based on the open-sourced POMCP codehase 14 At each time step, ACNO-POMCT uses Monte Carlo tree search to select actions (including observing and non-observing actions) using an approximated model of the environment and an E-greedy exploration strategy, with a decaying Whenever A ACNO-POMCT chooses to observe the state twice in a row, the observed (s, a, s'.r) tuple is used to update the parameters of its approximate transition and rewards models. ACNO-POMC its reward and transition estimates over states. Unlike Observe-then- theeree-hen--lan, ACNO-POMCP does not specify the number of necessary observations to be made prior to planning.
treats emitted observations as ground truth state observations and updates
DRON (Generic POMDP-RL) leverages an LSTM layer to encode sequences of one-hot-encoded observations into single hidden state encoding [22 The algorithm learns mapping from this hidden state to Q estimates, which are used for action selection under decaying e-greedy strategy.
EULER-VI VI (A (Always observing MDP-RL) chooses to observe at every time step, essentially treating the ACNO-MDP as MDP with constant observation costs. Initially, EULER-VI uses EULER [76 to strategically explore the state-action space. After a fixed number of "exploration" episodes, EULER-VI computes Value Iteration under maximum likelihood estimates of the transition dynamics and rewards models to learn an optimal five-step nonstationary policy assuming the observation cost applied at every step.
We evaluate the policy obtained from each method with 50 rollouts in the true environment and report the obtained discounted returns including the observation costs (Table B
Results We ran each of the above methods for 2000 episodes on the Sepsis simulator domain. The "exploration" phases of the Observe-then-Plan and FU algorithms were fixed to be 1000 episodes, at which point learning stopped. ACNNO-POMPP and DRQN learned continuously for all 2000 episodes. Learning curves for each algorithm are shown in Figure and performance of the final policies (i.e., after 2000 episodes) for each algorithm are shown in Table
Figure I shows that the algorithms without any explicit "exploration" phase (i.e., DRQN and ACNO- POMCP) achieved higher returns during the first 1000 episodes compared to algorithms that used the first 1000 episodes to actively explore the state-action space while always observing (i.e., Observe- then-Plan, EULER- V/). Rewards under both the Observe-then-Peee improved dramatically after switching from "exploration" to "planning". but EULER-V VI continued to observe at every time step and suffered in performance as a result. We note that, in the Sepsis simulator, any policy that prevents the patient from dying or being discharged for all 5 steps achieves a discounted return of 0.693. Observe-then- Plan is the only algorithm that outperforms this neutral policy in expectation. The gray horizontal line indicates the average returns from POMCP planning with the true model parameters, which suffers from reward approximation errors during planning due to its use of Monte Carlo simulations. Despite the potential error in planning due to stochastic rollouts, we chose POMCP as a computationally tractable POMDP planning algorithm.
and EULER-V algorithms
For implementation. we modified the open-sourced code at lhttps://iithuu com http:/thhhbb.co///gggggg43333 -TTorch-Deep. Beforrch-Depp-Recrreen--- Recurrent- Learning- DRQN Our code base is available at ham630/acno_mdyy
com/
8

---

Learning curves on sepois with observation cOst 0.1
Cymu alive performance scross episodes on sepsis with cost
Obex Seeeeenteeat
10WC>
0.7
1000
steatung!
600
400
ADMO PEMIC
Oiservve we-theeee than--iinn
200
DULOR-A1 (always cbsuninn!!
250
550
750
3200
2200
1200
2000
220
732
1000
3250
1200
3220
1020
Train ppoodd (ialling evereiing windor
Tral 0p acde
Figure 1: Sepsis learning curves under the observation cost -0.1, with a rolling average window of size 50. Shaded regions indicate + standard enror over 3 simulated runs. The dotted vertical line 1000 indicates the episode at which Observe-then-Plan and EULER-V VI switch to planning. DRQN and ACNO-POMCP continue learning. The æ--axis shows the number of training episodes and the y-axis shows (Left) acquired returns per episode and (Right) cumulative returns across episodes. The gray horizontal line (Left) shows the average returns from POMCP planning with the true model parameters. Note that approximate planning with POMCP, which was chosen over exact POMDP planning for computational tractability, imperfect even with a perfect model.
6.2 Algorithms for ACNO-MDPs with continuous state-action spaces
Explicit reward-free exploration is difficult do in continuous state and action spaces where the number of times an agent visits unique state-action pair cannot be measured effectively. Our ACNO- A2C algorithm instantiates the second framework of "Observe while Planning" to simultaneously learn accurate model of the environment while maximizing discounted episode returns. The results suggest that our proposed belief state encoder based on "Observe while Planning" empirically outperforms of--th--rtttt algorithms without having to explore all of the state and action spaces.
Experimental domains
Modified CartPole simulator We test on OpenAl gym CartPole-vO v0 d with the following modifi- cations: (1) the action space is doubled in size (push left, push right) x fobserve, not observe ;; (2) a cost -0.4 is applied to every reward r(s, Gobserve) in which the agent chooses to fully observe the state; and (3) if a state is observed, then the environment returns all zeros for the observation.
Mountain Hike simulator: We also test on a two-dimensional Mountain Hike environment, as described and implemented by Maximilian et al. 43 The goal of this task is to follow a high reward path along a "mountain ridge". The state space is defined by the current position, (x, y), and the action a is defined any possible vector (Áz, Ay) E IR² with bounded ε -norm. The agent starts from sampled coordinates (Iu, yo) ~ (--8.5l2x2 12x2). Observations returned are exactly the underlying state, except when the agent chooses not to observe in which case observations are vector of zeros. Transitions are defined as (z',)')= (z, y) + (Ax, Ly) + E, ~ (0 0.25 The reward is given by (xx y) 0.01||//la + (a), where (2x y) is the reward associated with the agent's 'ss proximity to the "mountain ridge" and Coha (a) is the cost of fully observing the state, such that Coke (Qobserve) -0.5 if the agent chooses to observe and Cohos (Frox observe) 0 otherwise.
Algorithms
ACNO-A2C ("Observe while Planning") is the algorithm instantiating the belief encoder in Algorithm with A2C, well-known actor-critic reinforcement learning method 45 72
DVRL (Generic PLM uses an implementation the Deep Variational Reinforcement Learning
algorithm by Maximilian et al. [R) As state-of-the-arr POMDP-RI RL approach for general POMDPs, this algorithm does not leverage the special observation model given in ACNO-MDPs and must learn
both the transition dynamics and the observation model online.
A2C (Always observing MDP-RL) applies the actor-critic method ing the agent always chooses to observe the underlying state and incurs the associated observation
45 r2
directly to the state, assum-

---

cost. We use the A2C implementation by Maximilian et al. 433 but modified to be defined over states, assuming every action outcome observed at the fixed cost.
Both the ACNO-A2C and DVRL algorithms use an encoder that returns an array of aggregated belief particles. This set of belief particles is then used for learning an A2C policy and value function.
Results Figure 2 shows the learning curves for our proposed algorithm (ACNO-A2C), the Deep Variational Reinforcement Learning algorithm (DVRL), and the always-observing A2C algorithm. Results are averaged over 5 random seeds. Shaded regions show standard deviations over the runs. Given equal number of training steps, our ACNO-A26 algorithm achieved higher-reward final policy, in expectation, and found this high-reward policy in almost half the time that took for the DVRL algorithm to find its reward policy. Running standard A2C while always observing achieved high returns faster than ACNO-A2C (Mountain Hike) or about as fast as ACNO-A2C (CartPole-vO), but achieved an inferior final policy relative to ACNO-A2C.
Learing Clevees on Caripo
Leariigg Curvann on MELITTAI EERM
-150
AZC Eoanrrarrrrg
AFC
300
28-
15
3.5
2.0
Figure 2: Left: CartPole-vO with observation cost 0.4. Right: Mountain Hike with cost 0.5.
Our findings suggest that leveraging information about the structure of the observation model can lead to improved learning efficiency (in terms of sample complexity) and higher-reward policies compared to ofate-of-the-art generic POMDP-RL algorithms which make minimal assumptions about the structure of the observation model.
7 Conclusion
We illustrated how assumptions made by many existing PAC POMDP-RL algorithms regarding the observation function are violated in ACNO-MDPs, a special class of POMDPs. We proposed and analysed a PAC RL. Observe-then- algorithm for efficient learning in such settings. We also proposed method for encoding belief states in ACNO-MDPs, and meta- algorithm that can couple this belief representation with deep RL algorithms to learn policies that balance the cost of observing with the benefits of observing for exploration and planning.
We focused on obtaining a sample complexity result under the probably approximately correct (PAC) framework, which has been extensively considered in MDPs, but this approach ignores potentially significant costs incurred during the exploration phase. In contrast, the regret framework incorporates costs incurred at all stages of learning into notions of optimality. One research direction for constraining the cost of strategic exploration would to develop ACNO-MDP RL algorithms that optimize regret.
We considered the online setting in this work, but offline RL could help mitigate concerns regarding online exploration in safety-critical domains. Exploring extensively to learn dynamics before planning may be infeasible and/or unethical in some settings. For example, in the context of using RL in the ICU to learn optimal policies for Sepsis management, strategic exploration may require the agent to take actions that do not match best practices or existing clinical guidelines; leveraging our ideas to learn optimal policies using data collected from suboptimal behavior policies could help in achieving practical policies with limited online exploration. However, we believe that our work takes a useful step towards characterizing the provable benefits in sample efficiency of ACNO-MDP RL compared to generic tabular POMDP-RL. generic continuous-see settings, sample complexity analysis and regret analysis for POMDPs or even MDPs remain important open areas of research.
10

---

Acknowledgments and Disclosure of Funding
This work was supported by a NSF CAREER Grant (Emma Brunskill), National Defense Science and Engineering Graduate Fellowship (Scott Fleming), and a Stanford Graduate Fellowship (Scott Fleming).
References
[1] Denis Agniel, Isaac S Kohane, and Griffin M Weber. Biases in electronic health record data due to processes within the healthcare system: retrospective observational study. Bmj. 361, 2018,
[2] Kamyar Azizzadenesheli, Alessandro Lazaric, and Animashree Anandkumar. Reinforcement learning of pomdps using spectral methods, In Conference on Learning Theory, pages 193-256. PMLR, 2016.
[3] Haoyu Bai, David Hsu, and Wee Sun Lee. Integrated perception and planning in the continuous space: A pomdp approach. The International Journal of Robotics Research, 33(9): 2014.
[4] Colin Bellinger, Rory Coles, Mark Crowley, and Isaac Tamblyn. Active measure reinforcement learning for observation cost minimization. Proceedings of The 34th Canadian Conference on Artificial Intelligence, volume 19, 2009.
[5] Colin Bellinger, Andriy Drozdyuk, Mark Crowley, and Isaac Tamblyn. Scientific discovery and the cost of measurementt-allee balancing information and cost in reinforcement learning. arXiv preprint arXiv:2112.073: 2021.
[6] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint 1606vv:606.01:55 2016.
[7] Anthony R Cassandra, Michael L Littman, and Nevin Lianwen Zhang. Incremental pruning: A simple, fast, exact method for partially observable markov decision processes. Proceedings of the Thirteenth Annual Conference on Uncertainty in Artificial Intelligence (UAI-97), pages 54-61, 1997.
[8] Chun-Hao Chang, Mingjic Mai, and Anna Goldenberg. Dynamic measurement scheduling for event forecasting using deep rl. In International Conference on Machine Learning, pages 951-960 PMLR, 2019.
[9] Kyunghyun Cho, Bart Van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio. On the properties of neural machine translation: Encoder-decoder approaches. arXiv preprint 1:Xivv/409..0 2259 2014.
[10] Antonio Coronato, Muddasar Naeem, Giuseppe De Pietro, and Giovanni Paragliola. Rein- forcement learning for intelligent healthcare applications: A survey. Artificial Intelligence in Medicine, 109:101964 2020.
[11] Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. 30, 2017. URL https://proceeddin pdf
neurips.cc/ htw.g//....pppeeeo/////////aaaas
[12] Kevin P Eaton, Kathryn Levy, Christine Soong. Amit K Pahwa, Christopher Petrilli, Justin B Ziemba, Hyung J Cho, Rodrigo Alban, Jaime F Blanck, and Andrew S Parsons. Evidence- based guidelines to eliminate repetitive laboratory testing. JAMA internal medicine, 177(12):
1833-1839, 2017.
[13] Maxim Egorov, Zachary N Sunberg, Edward Balaban, Tim A Wheeler, Jayesh K Gupta, and Mykel J Kochenderfer. Pomdps. jl: A framework for sequential decision making under uncertainty. The Journal of Machine Learning Research, 18(1):8318835. 2017.
[14] Emami, AJ Hamlet, and C Crane. Pomdpy: An extensible framework for implementing pomdps in python. 2015. URL httpe////gihaubb.coo//maaaaaaaae
11

---

[15] Damien Ernst, Guy-Bart Stan, Jorge Goncalves, and Louis Wehenkel. Clinical data based optimal sti strategies for hiv: a reinforcement learning approach. In Proceedings of the 45th IEEE Conference on Decision and Control, pages 667-672. IEFE, 2006.
[16] Mahdi Milani Fard, Joelle Pineau, and Peng Sun. variance analysis for pomdp policy evaluation. In AAAI, pages 1056-1061, 2008.
[17] Scott L Fleming, Kuhan Jeyapragasan, Tony Duan, Daisy Ding, Saurabh Gombar, Nigam Shah, and Emma Brunskill. Missingness as stability: Understanding the structure of missingness, in longitudinal ehr data and its impact on reinforcement learning in healthcare. arXiv preprini arXiv: 1.07084 2019.
[18] Ian Fox, Joyce Lee, Rodica Pop-Busui, and Jenna Wiens. Deep reinforcement learning for closed-loop blood glucose control. In Machine Learning for Healthcare Conference, pages 508-536. PMLR, 2020.
[19] Mahsa Ghasemi and Ufuk Topeu. Perception-aware point-based value iteration for partially observable markov decision processes. 2018.
[20] Marek Grzeš, Pascal Poupart, Xiao Yang, and Jesse Hoey. Energy efficient execution of pomdp policies. IEEE Transactions on Cybernetics, 45(1 1):2114:4444444 2497, 2014.
[21] Zhaohan Guo, Shayan Doroudi, and Emma Brunskill. A PAC RL algorithm for episodic pomdps. CoRR, abs/1605.08062, 2016. URL http::/arxiii org/ www.abb..........a 08062
[22] Matthew Hausknecht and Peter Stone. Deep recurrent q-learning for partially observable mdps.
AAAI Fall Symposium on Sequential Decision Making for Intelligent Agents, 2015.
[23] Milos Hauskrecht. Value-function approximations for partially observable markov decision processes. Journal of artificial intelligence research, 13:33 94, 2000.
[24] Mehdi Jafarnia-Jahromi, Rahul Jain, and Ashutosh Nayyar. Online learning for unknown partially observable mdps. arXiv preprint arXiv:2102.12661, 2021.
[25] Ashish K Jha, David C Chan, Abigail B Ridgway, Calvin Franz, and David W Bates. Improving safety and eliminating redundant tests: cutting costs in us hospitals. Health affairs, 28(5): 1484, 2009.
[26] Chi Jin, Sham Kakade, Akshay Krishnamurthy, and Qinghua Liu. Sample-efficient reinforce- ment learning of undercomplete pomdps. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 18530-1855 18539, Curran Associates, Inc., 2020.
[27] Chi Jin, Sham M Kakade, Akshay Krishnamurthy, and Qinghua Liu. Sample-efficien reinforce- ment learning of undercomplete pomdps. arXiv preprint arXiv:2006. 2020.
[28] Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. 0194880-44877 13-18 Jul 2020. URL http://pproceedings
mlr. pptpss//11///nn20d. html html
[29] Leslie Pack Kaelbling, Michael L Littman, and Anthony R Cassandra. Planning and acting in partially observable stochastic domains. Artificial intelligence, 101(1-2):99-134, 1998.
[30] S. Kakade, On the sample complexity of reinforcement learning. 2003.
[31] Sammie Katt, Frans Oliehoek, and Christopher Amato. Learning in pomdps with monte carlo tree search. In International Conference on Machine Learning, pages 1819-1827. PMLR, 2017.
[32] Sammie Katt, Frans Olichock, and Christopher Amato. Bayesian reinforcement learning in factored pomdps. arXiv preprint arXiv: /8/ 1.05612, 2018
[33] Richard Klima, Karl Tuyls, and Frans A Oliehoek. Model-based reinforcement learning under periodical observability. In 2018 AAAI Spring Symposium Series, 2018.
12

---

[34] Petar Kormushev. Sylvain Calinon, and Darwin G Caldwell. Reinforcement learning in robotics: Applications and real-world challenges. Robotics, 2(3): 122-:122-48, 2013.
[35] Hanna Kurniawati, David Hsu, and Wee Sun Lee. Sarsop: Efficient point-based pomdp planning by approximating optimally reachable belief spaces. In Robotics: Science and systems, volume 2008. Citeseer, 2008
[36] Lei Lei, Yue Tan, Kan Zheng, Shiwen Liu, Kuan Zhang, and Xuemin Shen. Deep reinforce- ment learning for autonomous internet of things: Model, applications and challenges. IEEE Communications Surveys & Tutorials, 222))1722-1760, 2020.
[37] Yuxi Li. Deep reinforcement learning. arXiv preprint arXiv:/810.06333/ 2018.
[38] Zakary Littlefield, Dimitri Klimenko, Hanna Kurniawati, and Kostas E Bekris. The importance of a suitable distance function in belief-space planning. In Robotics Research, pages 683-700. Springer, 2018
[39] Michael L Littman, Anthony R Cassandra, and Leslie Pack Kaelbling. Learning policies for partially observable environments: Scaling up. In Machine Learning Proceedings 1995, pages 362-378 370. Elsevier, 1995.
[40] William S Lovejoy.
Computationally feasible bounds for partially observed markov decision processes. Operations research, (9(1):162-175 1991.
[41] Nguyen Cong Luong, Dinh Thai Hoang. Shimin Gong, Dusit Niyato, Ping Wang, Ying-Chang Liang, and Dong In Kim. Applications of deep reinforcement learning in communications and networking: A survey. IEEE Communications Surveys & Tutorials, 113333313333 2019.
[42] Mufti Mahmud, Mohammed Shamim Kaiser, Amir Hussain, and Stefano Vassanelli. Appli- cations of deep learning and reinforcement learning to biological data. IEEE transactions on neural networks and learning systems, 29(6):2033-2073 2018
[43] Igl Maximilian, Luisa Zintgraf, Tuan Anh Le, Frank Wood, and Shimon Whiteson. Deep variational reinforcement learning for pomdps. CoRR, 002./1806.00226, 2018. URL http wawxiv.org/abs////o.
02426, https//httss////iiaau http://iiwub.ccoaaaaiiiiaaaaaaaa
[44] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):599-53,, 2015.
[45] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforce- ment learning. In International conference on machine learning, pages 1928-1937. PMLR. 2016.
[46] Rui Nian, Jinfeng Liu, and Biao Huang. A review on reinforcement learning: Introduction and applications in industrial process control. Computers & Chemical Engineering, page 106886, 2020.
[47] Farzad Niroui, Kaicheng Zhang, Zendai Kashino, and Goldie Nejat. Deep reinforcement learn ing robot for search and rescue applications: Exploration unknown cluttered environments. IEEE Robotics and Automation Letters, 4(2):610-617, 2019.
[48] Michael Oberst and David Sontag. Counterfactual off-policy evaluation with Gumbel-max structural causal models. 97:4881 48900 09-15 Jun 2019. URL.http::/proceedings .mrr
html, //atts::/giiteee http://gtthhh.coooooaaaaaaaaaaaa htt.g//mmmmmmmmmmmeeeeeem scm
com/
[49] Christos H Papadimitriou and John N Tsitsiklis. The complexity of markov decision processes. Mathematics of operations research, 12(3):441-450, 1987.
[50] Joelle Pineau, Geoff Gordon, Sebastian Thrun, et al. Point-based value iteration: An anytime algorithm for pomdps. In IJCAI, volume 3, pages 1025-1032. Citeseer, 2003.
[51] Athanasios S Polydoros and Lazaros Nalpantidis. Survey of model-based reinforcement learning: Applications robotics. Journal of Intelligent & Robotic Systems, 16(2):153-173.201
13

---

[52] Stephane Ross, Brahim Chaib-draa, and Joelle Pineau. Bayes-adaptine pomdps. In NIPS, pages 1225-1232, 2007.
[53] Stéphane Ross, Brahim Chaib-Draa, et al. Aems: An anytime online search algorithm for approximate policy refinement in large pomdps. In IJCAI, pages 2592-2598, 2007.
[54] Stéphane Ross, Joelle Pineau, Sébastien Paquet, and Brahim Chaib-Dras Draa. Online planning algorithms for pomdps. Journal of Artificial Intelligence Research, 32:663-704, 2008.
[55] Stephane Ross, Masoumeh Izadi, Mark Mercer, and David Buckeridge, Sensitivity analy- sis of pomdp value functions. In 2009 International Conference on Machine Learning and Applications, pages 317-323. IEEE, 2009.
[56] Stéphane Ross, Joelle Pineau, Brahim Chaib-draa, and Pierre Kreitmann. A bayesian approach for learning and planning in partially observable markov decision processes. Journal of Machine Learning Research, 12(5), 2011.
[57] Guy Shani, Joelle Pineau, and Robert Kaplow. A survey of point-based pomdp solvers. Au- tonomous Agents and Multi-Agent Systems, 27(1):1-51, 2013.
[58] Kun Shao, Zhentao Tang, Yuanheng Zhu, Nannan Li, and Dongbin Zhao. A survey of deep reinforcement learning in video games. arXiv preprint arXiv:1912.10944, 2019.
[59] David Silver and Joel Veness. Monte-carlo planning in large pomdps. Neural Information Processing Systems, 2010.
[60] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419)::140-- 144, 2018.
[61] Trey Smith and Reid Simmons. Heuristic search value iteration for pomdps. arXiv preprint /20.v: 2012.
[62] Adhiraj Somani, Nan Ye, David Hsu, and Wee Sun Lee. Despot: Online pomdp planning with regularization. In NIPS, volume 13, pages 1772-1780, 2013.
[63] Matthijs Spaan and Pedro Lima. A thcoreic- approach to dynamic sensor selection in camera networks. Proceedings of the International Conference on Automated Planning and Scheduling, volume 19, 2009.
[64] Alexander Strehl and Michael Littman. A theoretical analysis of model-based interval estimation. page 856-863, 2005, doi:
URL https://doi. 1145/
1102351.
[65] Alexander Strehl, Lihong Li, and Michael Littman. Reinforcement learning in finite mdps: Pac analysis. Journal of Muchine Learning Research, 10(84):2413-2444, 2009. URL http
//jmlr www.oo///gaao/ wwwppapggg////pppt/o/.......ssa/ iinerss/vie
html
[66] Jayakumar Subramanian, Amit Sinha, Raihan Seraj, and Aditya Mahajan. Approximate information state for approximate planning and reinforcement learning partially observed systems. arXiv preprint arXiv:2010.08843 2020.
[67] Zachary Sunberg and Mykel Kochenderfer. Online algorithms for pomdps with continuous state, action, and observation spaces. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 28, 2018.
[68] Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Jun- young Chung, David Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782)3300-3544 2019.
14

---

[69]
Yi Wang, Jialiu Lin, Murali Annavaram, Quinn A. Jacobson, Jason Hong, Bhaskar Krishna- machari, and Norman Sadeh. A framework of energy efficient mobile sensing for automatic user state recognition. In Proceedings of the 7th International Conference Mobile Systems, Applications, and Services, MobiSys '09, page 179-192, New York, NY, USA, 2009. Associa- tion for Computing Machinery. ISBN 9781 605585666. doi: 10.1 00.1145/1555816 1555835. URL 1555835
org/10. https://doi..org10...1
[70] Yi Wang, Bhaskar Krishnamachari, Qing Zhao, and Murali Annavaram. Markov-optimal sensing policy for user state estimation in mobile devices. In Proceedings of the 9th ACM/IEEE Interna- tional Conference on Information Processing in Sensor Networks, IPSN 100 page 268-278, New York. NY. USA, 2010. Association for Computing Machinery. ISBN 978 1605589886. doi: 10.1145/1911122.199124, URL hattps://dat org/ 11..1...1111111111111 1791244
[71] Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marco Weinberger. Inequalities for the 11 deviation of the empirical distribution. 2003.
[72] Yuhuai Wu, Elman Mansimov, Shun Liao, Roger Grosse, and Jimmy Ba. Scalable trust-region method for deep reinforcement learning using kronecker-factored approximation. arXiv preprint urXiv:/708.05144 2017.
[73] Haiyan Yin, Yingzhen Li, Sinno Jialin Pan, Cheng Zhang, and Sebastian Tschiatschek. Rein- forcement learning with efficient active feature acquisition. arXiv preprint arXiv:2011.0082, 2020.
[74] Jinsung Yoon, James Jordon, and Mihaela Schaar. Asac: Active sensing using actor-critic models. In Machine Learning for Healthcare Conference, pages 451-473, PMLR, 2019.
[75] Chao Yu, Jiming Liu, and Shamim Nemati. Reinforcement learning in healthcare: A survey, arXiv preprint arXiv: 1000::990.00000 908.98996. 2019.
[76] Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. Proceedings of the 36th International Conference on Machine Learning, Long Beach, California, PMLR 97, 2019, abs/1901.002 10,000, 2019. URL http:://aariiii wwweriivvorgg.ooo aaaaabas/999 1901. 00210
[77] Nevin L Zhang and Wenju Liu. Planning in stochastic domains: Problem characteristics and approximation. Technical report, Technical Report HKUST-CS96-31, Hong Kong University of Science and Technology, 1996.
[78] Ming Zhi, Eric I. Ding, Jesse Theisen-TToupl, Julia Whelan, and Ramy Arnaout. The landscape of inappropriate laboratory testing: a 15-year meta-analysis. PloS one, 8(11):77962, 2013.
[79] Pengfei Zhu, Xin Li, Pascal Poupart, and Guanghui Miao. On improving deep reinforcement learning for pomdps. arXiv preprint arXiv:1704.000 07997, 2017.
[80] Valentina Bayer Zubek and Thomas Dietterich. pomdp approximation algorithm that antici- pates the need to observe. In Pacific Rim International Conference on Artificial Intelligence, pages 521-532. Springer, 2000.
[81] Valentina Bayer Zubek, Thomas Glen Dietterich, et al. Two heuristics for solving pomdps having delayed need to observe. 2004.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], , or [N/A]. You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
15

---

Did you include the license to the code and datasets? [Yes] All our algorithms and ex- perimental domains are open-source (e.g.. POMDPy [9]. DVRL/mountainn hike [33], Sep- sis simulator [38], CartPole from OpenAI-Gym [4), DRQN is modified from https:/ // github. www.com////a// haep////////ooo--eeeeeeee Dewp--eeureeeet------ Q- (eaarinngDRRUU) The link to our codebase is included in the Appendix.
Did you include the license to the code and datasets? [Yes] See above.
Did you include the license to the code and datasets? [Yes] All algorithms and experimental domains are open-source. Links cited and our codebase will be relcased/linked after
review.
Please do not modify the questions and only the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Limitations are discussed through- out (e.g., sample complexity only for tabular domains), in addition to the conclusion section.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] In our conclusion, we caution against using online algorithms solve high-stake problems like Sepsis, which would be infeasible and/or unethical.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] These included the Appendix A. Proofs
(b) Did you include complete proofs of all theoretical results? [Yes] These are included in the Appendix A. Proofs
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [Yes] A GitHub repo with code and instructions needed to reproduce the main experimental results is provided in the Appendix, along with more de- tailed pseudocodes. DRQN is based on PyTorch-Deeyy DeTTuur-Deep-Recuureett -e-Lerning--RRA
com
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] These are included in the Appendix B. for Sepsis, CartPole, and Mountain Hike experiments, and associated links are cited.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] All results are reported with mean and standard error over multiple runs with different random seeds.
(d) Did you include the total amount of compute and the type of resourees used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes] Computation was performed on internal university servers. Wall clock-time for the experiments is included in the Appendix B along with other training details.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] Algorithms used in our work, including DVRL, DRQN, POMCP, etc., and environments, including Sepsis simulator, OpenAl CartPole, and DVRL mountain hike, are all cited in our manuscript.
(b) Did you mention the license of the assets? [N/A] All considered algorithms and experimental domains are open-source (e.g., OpenAl-Gym, Sepsis) and require no additional license.
16

---

(c) Did you include any new assets either in the supplemental material or as URL? [Yes] Code is provided via publicly accessible GitHub link, as described above.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] We did not use any data from human subjects.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] We used simulated data only.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] No human subjects data was used in this project.
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A] See above.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A] See above.
17


Reviews:
[{"review_id": "qeEknMIy9B", "reviewer": "Reviewer_GV21", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "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.\n\nHowever, 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.\n\nIn 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.)\n\nIn 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.\n\nOther minor comments:\n* 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.\n* 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.\n* 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "aNb9I0Aba0R", "reviewer": "Reviewer_7nyK", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "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. \n\nOriginality: 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:\n\nMixed observability MDPs (MOMDP), in particular, RockSample:\n\n[1] Smith, Trey, and Reid Simmons. \"Heuristic search value iteration for POMDPs.\" arXiv preprint arXiv:1207.4166, 2012.\n\nActive perception frameworks: \n\n[2] Ghasemi, Mahsa, and Ufuk Topcu. \"Perception-Aware Point-Based Value Iteration for Partially Observable Markov Decision Processes.\" IJCAI, 2018.\n\n[3] Matthijs Spaan and Pedro ULima. A decision-theoretic approach to dynamic sensor selection in camera networks. In ICAPS, 2009\n\nAlso relevant:\nNon-observable MDPs (NOMDP)\n\n[4] Littlefield, Zakary, et al. \"The importance of a suitable distance function in belief-space planning.\" Robotics Research. Springer, Cham, 2018. 683-700.\n\nQuality:\nThe 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.\n\nEEPORL [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.\nThe examples used in this paper do not follow this assumption, which is quite strong.\nThe 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.\n\nClarity:\nThe 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.\n\nSignificance:\nThe 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5.5"}, "extra_text": {}}, {"review_id": "FuNIR-TT7OY", "reviewer": "Reviewer_pVS8", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "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.\n\nPerhaps 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.\n\nThe 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.  \n\nOn 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\noften 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.\n\nThe 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.\n\nThe 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.\n\nMany 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.\n\nEquations on pp. 22 and 23 have some formatting issues. Also, the table on p. 28 is too wide.\n\nTime 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.\n\nAssuming that the PAC proves are correct, this could be a nice NeurIPS contribution.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No need for improvement.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "AYuYXv0TAAM", "reviewer": "Reviewer_f13f", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "### Strengths\n\n- 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).\n\n- 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.\n\n- 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.\n\n- 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.\n\n- The paper is well written and easy to follow.\n\n\n### Limitations\n\n1. 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.\n\n2. 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.\n\n3. 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.\n\n\n### Minor comments\n- 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.\n- Reference numbering in the appendix does not seem to match the main paper, e.g., [62] vs. [63]. This should be corrected.\n\n### After author reply\nI am happy with the author response to my comments. I welcome the proposed changes to the manuscript and remain by my accept rating.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations and societal impact are adequately addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

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)