Reference-Based POMDPs
Authors: Edward Kim
Yohan Karunanayake
Hanna Kurniawati
Venue: NeurIPS 2023 poster (2023)
Keywords: POMDP
planning under uncertainty
long horizon
TL;DR: Expanding Linearly Solvable MDPs to POMDPs

Abstract: Making good decisions in partially observable and non-deterministic scenarios is a crucial capability for robots. A Partially Observable Markov Decision Process (POMDP) is a general framework for the above problem. Despite advances in POMDP solving, problems with long planning horizons and evolving environments remain difficult to solve even by the best approximate solvers today. To alleviate this difficulty, we propose a slightly modified POMDP problem, called a Reference-Based POMDP, where the objective is to balance between maximizing the expected total reward and being close to a given reference (stochastic) policy. The optimal policy of a Reference-Based POMDP can be computed via iterative expectations using the given reference policy, thereby avoiding exhaustive enumeration of actions at each belief node of the search tree. We demonstrate theoretically that the standard POMDP under stochastic policies is related to the Reference-Based POMDP. To demonstrate the feasibility of exploiting the formulation, we present a basic algorithm RefSolver. Results from experiments on long-horizon navigation problems indicate that this basic algorithm substantially outperforms POMCP.

Peference-Baseer POMDPs
Edward Kim School of Computing Australian National University Canberra, Australia edward. kimčanu. edu. au
Yohan Karunanayake
School of Computing
Australian National University
Canberra, Australia
yohan. karunanayakeaanu lecaaamueedu.ee. edu. au
Hanna Kurniawati
School of Computing
Australian National University
Canberra, Australia
hanna. hanna.kurniasan www.kuannniiaannn.aaa edu.
Abstract
Making good decisions in partially observable and non-deterministic scenarios is crucial capability for robots. A Partially Observable Markov Decision Process (POMDP) is general framework for the above problem. Despite advances in POMDP solving, problems with long planning horizons and evolving enviromments remain difficult to solve even by the best approximate solvers today. To alleviate this difficulty, we propose a slightly modified POMDP problem, called a Reference- Based POMDP, where the objective is to balance between maximizing the expected total reward and being close given reference (stochastic) policy. The optimal policy of a Reference-Bas Based POMDP can be computed via iterative expectations using the given reference policy, thereby avoiding exhaustive enumeration actions at each belief node of the search tree. We demonstrate theoretically that the standard POMDP under stochastic policies is related to the Reference-Baan POMDP. To demonstrate the feasibility of exploiting the formulation, we present a basic algorithm REFSOLVER. Results from experiments on long-horizon navigation problems indicate that this basic algorithm substantially outperforms POMCP.
Introduction
Computing motion strategies that are robust to uncertainty is a fundamental problem in robotics. robot often needs strategically plan in environment where only has partial knowledge about itself and the state of the world due to actuator disturbances, limited knowledge about the environment, and imperfect sensory information. Such planning problems can generally be framed as a Partially Observable Markov Decision Process (POMDP) [7 [2)), which is general mathematical framework for planning in partially observable and non-deterministic scenarios. POMDPs explicitly model partial observability using a probability distribution over the state space, called a belief. and compute the best strategy with respect beliefs. Finding the exact solution to a POMDP problem is computationally intractable in the worst case [15] [7] for two main reasons. Firstly, the size of the belief space grows exponentially with respect to the size of the state space. Secondly, the number of oosioooobservattio histories grows exponentially with respect to the planning horizon. These challenges are known as the curse of dimensionality and the curse of history respectively. To deal with these challenges, many practical solvers have been proposed in the past few decades 9.. Sampling-basse based approximate solvers 12 21 29 have made good progress on both curses by employing particle filters to maintain a belief search tree and judiciously exploring a subset of histories in this search tree.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Notwithstanding these advances, some partially observed problems, such as those involving long planning horizons and progressively evolving environments remain relatively difficult to solve by even the best approximate POMDP solvers today. In particular, all of the aforementioned solvers struggle with a planning horizon of more than 15 steps primarily because, to infer the best action, they rely on exhaustive enumeration of actions at each belief node in the search tree.
To alleviate the above difficulties, and hence further improve POMDP solving capabilities, we propose the idea of a Reference- Based POMDP. A Reference- Based POMDP is a modification of the standard POMDP where, in addition to maximising total rewards, an agent's 's objective function is penalised for deviating too far from a given stochastic reference policy. This approach leads to an interesting interpretation where the agent must trade off between two possibly competing objectives. The agent should respect the given initial stochastic policy unless deviating substantially from it leads to much higher rewards.
A key outcome of this formulation is that solving a Reference- Based POMDP does not require exhaustive enumeration of the actions at each belief node. Rather, optimisation can be performed analytically because: (i) the space of policies is relaxed to include stochastic policies; and (ii) the form of the penalty is represented as the KL divergence from the reference policy, Under suitable transformations, this leads to linear Bellman backup (Theorem 3.1 where the sampling distribution the reference policy itself. As the reference policy is known priori, the above insight facilitates algorithms where the actions can be sampled (as opposed to enumerated) at each step which, in turn, can be efficiently computed using Monte Carlo methods.
This work can be viewed as an extension of body of literature related to Linearly Solvable Optimal
Control [2 26 27 19 28 3 in fully observable environments (see Section 7 for brief summary) to partially observable ones. While it is true that a POMDP can be viewed as an MDP in the belief space 77). extending the aforementioned works to partially observable domains non-trivial because of the infinite and continuous nature of the belief space and the difficulty of computing belief updates. To the authors' knowledge, the approaches outlined above have not yet been extended partially observable domains.
The paper is organised as follows. Section 2 recounts the basic setup of POMDP. Section in- troduces the Reference-Basse POMDP and outlines the relevant theory. Section 4 demonstrates that the standard POMDP can be related the Reference- Based POMDP via embedding. Sec- tion 5 presents REFSOLVER a preliminary approximate solver for the Reference- Based POMDP. Experimental results on long-horizon 2D and 3D navigation problems are presented in Section 6 and indicate that our solver can be employed to substantially outperform POMCP [21]. Note that the problems we have presented, are not trivial due to the long planning horizon and the challenges of partial observability and transition uncertainty. Finally, we outline the relevant literature in Section 7 and summarise the contributions, limitations and future directions of the paper in Section g
2 POMDP Preliminaries
In this paper, we focus on an infinite-horizon formulation of the POMDP. Formally, a standard POMDP is completely specified by tuple A, O, Z, R. 7)- Here, S denotes the set of all possible states of the agent and its environment, AA denotes the set of all possible actions the agent can perform, and O denotes all the possible observations that the agent can perceive. Although our transformation could be applied to POMDPs with continuous state, action, and observation spaces, for simplicity, in this paper, we will assume that S, A and O are all discrete.
At each time step, the agent occupies a state s e S and executes an action a E A, after which its state transitions to new state s' S. The outcome of this execution is non-deterministic, and this uncertainty is represented in the Markovian transition function T as a conditional probability function (s' s, a). At the new state s', the agent perceives observation E O. Uncertainty in the observation perceived- - having undertaken action a E AA and transitioned to state s' - is described by the conditional probability function 2(o s', a), referred to the observation function. The agent's action incurs a reward, which is defined by a bounded real-valued function R ::3 S x A R. The parameter 7 E (0, 1) represents the discount factor.
As the agent does not know its true state, at each time step, the agent maintains a belief about its state. A belief, denoted as b, is a probability distribution over the state space S. The set of all possible

---

beliefs forms belief space of (|S) 1) dimeensional simplex, which we denote as B. The belief the agent maintains is updated via Bayesian inference using the transition and observation models 2 and T, respectively. The exact belief update is completely determined by action-observation pair. Formally, 1' =(b, a, o) denotes the agent's 's next belief after taking action and perceiving observation then D' is defined as:
('(s') 2(ols
[(sssss,a)b
(1)
$ES
where 1y is a normalising factor. The solution to a POMDP problem is an optimal policy x² B + A that maximises the value function, defined as:
V* (b) = max aEA R(b,a) +
Σ
P(ola, (ro0,.
OEO
where
R(b,a)= = [(s,a)
is the expected reward under the belief b. The notation P(o 6) is the probability the agent perceives an observation o E O having performed the action a E A under the belief b, and is defined as
P(o a. b) = Σ 2(ols',a) [{s(s|s,,))sss)) S'ES
T(s' (T(ss's,,))0 (s,))(ss))
Computing the exact solution '² and optimal value function V is intractable 14 15 17 and therefore state-of-the of-the-art art solvers approximate solutions via sampling 9
in general,
3 Reference-Basee POMDP
We now extend the analytical approach for the Linearly Solvable MDP (see Appendix Section A. to the POMDP. To this end, we define a Reference- Based POMDP, which is specified by the tuple (S, A, O, 2, T, R. 7: U). Similar the standard POMDP, S, A. and O refer the state, action, and observation spaces respectively. We denote by Z. T, and R the observation, transition, and reward functions. respectively, while Y (0, 1) denotes the discount factor. Assumption 3.1. A reference belief-to-belief transition probability:
bb) E A(Ax
(5)
is given for all b E B.
This reference transition is assumed by the problem and could constructed in multiple ways. At the most abstract the level this could be given in top-down fashion (e.g. an offline policy that has been generated for a similar version of a POMDP problem). On the other hand, it could also be constructed from the ground up. For example, one could take fully observed policy =0 S A and infer reference stochastic action 7(. (b) according to
* 7(a b) = 17 a Σ ((- b(s) +1 a) p(abb))
(6)
where p some default distribution for sampling actions and the parameter a (0, indicates the saturation level of the fully observed policy. The exact choice of fully observed policy depends on the context. Examples might include: an MDP policy for the fully observed version of the problem, policy induced by feasible paths generated by motion planners, a policy induced by all source shortest path in the case navigation problem, and even a policy representing the passive dynamics of system at any given state. Regardless of how the reference stochastic action is constructed, in ground-up construction, the reference belief-to-belief transition probability will take on the more specific form:
Üaa b) = P(o| a, b) ((a)) ()
(7)
where P(ol aa b) is given by (4.
Inspired by Linearly-Solvable MDPs (Section A. D. a Siterence-Based POMDP asserts that, for any belief 6 B, we can realise "belief-to-beliee transition probabilities U(,,' A(A x O) of
3

---

our choosing. Note that this is an ideal transition probability which may not actually be realisable in practice even by a stochastic policy (see Se. and Section for further commentary). To prohibit arbitrary transitions, at any belief & E B, we will further restrict our choice of distribution U to one that satisfies the property
ob) =
U(a,olb)= =0 Va A,0EO.
Denote the class of such distributions by (b) C A(A x O) which will form our admissible reference transition probabilities (which be viewed as admissible controls) from given belief. Then, % = UsEs 2 (b) is the class of all admissible reference transition probabilities. Similar
to 225 we penalise choices of (-) that represent large deviations from ((,-16) 6) using KL
divergence: KL (U (8) (1. 16)).
Now, the above reference transition probability affects the definition of the reward function too. At the most abstract level, the reward function R : B x A - parameterised by belief -ctionn pairs. Hence, the expected immediate cost of taking stochastic belief-to-beliee belief transition governed by 66) E (6) is given by
R(b = -) R10
(8)
where again R(b, a) R(s, a ())( The solution Reference- BetereeceeBBeeeddd POMDP problem is then an optimal stochastic policy x² B + V that maximises:
(b)
sup
(R(bUU) KL (0),,-1) 6))
UGy-1 ())
[((ao)i))(( (9)
3.1 Existence and Uniqueness of the Solution
One might ask if the reformulation p is satisfied uniquely by some function V R. The following lemma ensures that there exists unique (up to -ll
bounded function B + I satisfying the Bellman equation. Its proof is deferred to Appendix A.2
Lemma 3.1. Consider the Banach space [BB) of bounded functions V B - R. equipped with the supremum norm || lloc. Let & (B)) + (B) be self-mapping defined by the Reference- Based POMDP backup operator described by equation (9). Then, for y (0, 1), the mapping & is contraction and
1 21/22 S 7 1 V2lloc
(10)
Hence, by the Banach fixed point theorem in this space whenever y 1).
g the solution to the Bellman equation exists uniquely
3.2 Transforming the Value Function
Here, we show that under an appropriate transformation, the value function of Reference-Batte POMDP g can also be linearised. Its proof is given in Appendix A.3
Theorem 3.1. Define the transformation W(b) ;= e. v(b) for any b E B. The value function p of the Reference-Basee POMDP (S, A, Z, R, 7, U) is equivalent to
W(b) Σ Üaa b)e (bb (T(b.
(11)
The solution W to equation exists and is unique. And, the optimal stochastic "belief-to-beliee" transition to the Bellman equation ( is given by
U U'(a, o)) Ü(a, o (l), (ba))
(12)
D(W~?1(b)
where D(W* := Ea. ( b) R(0.)) (7(b, 6)) is normaliser.

---

Intuitively, the solution W represents the desirability of given belief (or history of action- observation sequences) where, [2] represents distorting the reference dynamics higher desirability scores. Moreover, Theorem 3.1 shows that we can converge to W by iterating the transformed Reference- Bariee POMDP backup operator (1T). Lemma 3.1 indicates that the speed of convergence
depends on the size of y with faster convergence as "y tends to 0. Moreover, Theorem 3.1 also implies that once W is computed, U* can be computed exactly via (12).
Unlike the linearly solvable MDP, exactly computing W is still intractable in practice due to the continuity of the belief space and the cost of belief estimation. However, we leverage the advances made by sampling-base based POMDP solvers and assume that the belief space is sufficiently represented by a finite number of beliefs, then this quantity can be approximated. Of course, finding such a set of beliefs is in itself difficult. Nevertheless, the fact that the optimal value function of Reference- Based POMDP is equivalent to [1T implies that the optimal value function of Reference- -aaeed POMDP can be computed by purely computing expectations under the reference transition probabilities recursively, which can be approximated efficiently (e.g. via Monte Carlo approximation).
3.3 Recovering the Stochastic Actions
While restricting the agent's transition probabilitiess to V/ (b) limits the agent's 's level of control, U* as given in (12 is still ideal transition probability and may therefore not be realisable under stochastic action in general. In other words, one cannot guarantee the existence of a stochastic action A and O.
[a [a| b) such that U Uaa o b) == P(o| a, b) a[a b) U (a, o b) for every
Nevertheless, we can still find a raa () such that and U are close in some sense. suitable way to formulate the problem is to minimise the KI. divergence between U and U. That is, for each b E B, we minimise
Plola a. b) m(a
PPool a, b) [aaa(aab)) log
P(ol
(13)
(a(a.
over all stochastic actions (- (b) E A(A). Solving the constrained minimisation problem using Lagrange multipliers yields the following result. See Appendix A..4 for its proof.
Proposition 3.1. The minimiser of (13 is
exp [Taa b)]
x (a b) = EoEA exp|-II(a b)]
Va E A
(14)
where
P(o P(ola,6) U+(a, o((
Ia (b) = Σ b(ola, log
(15)
4 Relating the Reference-Based POMDP and the Standard POMDP
In A.1 we recount a procedure for embedding the standard MDP (S,A,7 T. R, inside the refor- mulated MDP (S, p. p. 7). The key advantage of this is to apply the more efficient machinery of the reformulation to quickly determine good approximate solutions to the standard MDP. Furthermore, establishes theoretical basis to relate the two formulations. Here, we present an analogous embedding for the POMDP. Proofs are deferred to Section for conciseness.
Suppose an initial belief bo B is given and let Lho be the set of all reachable beliefs from bo. Let (B),,) denote the set of all bounded functions from Ri, to R. Consider the family of Reference-Basee POMDPs with purely belief-dependent rewards p E IB ((Dr)))
( O, 2, T, ..7, P)BB)(())))))))))))))))) (.B(
(16)
and a standard POMDP of the form
(S. A. A,A.O,,,.. 2,T, R.
(17)
For fixed (p. U) E B BBrr)) ) x V. their respective Bellman equations are:
(p(b) - KL (U(,,- (()))))))
V(6) =
sup
5(. (b)
+ [ua.oli)(((0oo)) (18)
0,0
5

---

and
V(b) = max aEA
R(b,a) +7 Σ Plolaa
(19)
OEO
for all b E Rio
Definition 4.1. Let [B (r) be the set of all bounded functions from Rrg R. We say that the pair (p, U) E (B..))) x a is an embedding of the standard POMDP (7) in the Reference- Based
POMDP T6) with purely beliee-de rewards if. for each à A and b B there exists (.. E V such that:
Σ AEA
= PPolaa))
(20)
and
R(b, â) = p(b)
((.,,,1)))
(21)
Proposition 4.1. Suppose p E ((Brr)) is such that
p(b) = log
R(baa)
(22)
àeA
holds where R(b.a) a) = Exee R(s, ()).)))(s)) Then, is
B(bia)
U(a,0l P((ooa))
4b ebel B
(23)
EGes R(bba
the pair (p. U) E ((Br.) x V is an embedding of the standard POMDP in the Refsrence-Based POMDP with purely belief-dependee rewards.
An Online Planning Algorithm
We have developed preliminary on-line solver REFSOLVER for Reference-Based POMDP to demonstrate some of the advantages of the formulation presented in Section 3 Pseudo code for an implemented algorithm where the reference policy constructed using a fully-observed policy -0 is presented in the Appendix Section A.6 Algorithm Note that although our description of REPSOLVER very specific terms of the reference policy and reference stochastic action, they can readily be replaced with other types of policies and induced reference stochastic actions.
Similar to many state-of ffate-of-the-are art on- on-line POMDP solvers (e.g., (21 29 ) REFSOLVER constructs
search tree of action-observation histories and uses particles to represent the beliefs. The key insight of REFSOLVER, however, is exploit the additional information afforded by the fully observed policy to limit exploring every possible action at each history node. Instead, as each backup of the transformed value (9) essentially expectation under the reference policy, actions are sampled using the reference policy and the backup is estimated via a straightforward Monte Carlo method. This allows sparser sampling and simulations resemble depth-first search traversing to a pre- specified depth before rolling out the leaf nodes using the fully observed policy. Hence, rather than expanding all the actions as POMCP (II). ABT[12] and DESPOT 229 do, REFSOLVER constructs deeper tree thereby exploiting more information about the long-term behaviour of the system.
To allow for REFSOLVER also search forward for actions that not supported by the fully observed policy, some additional noise can be added according to (6) so that (1 - -a) can be interpreted as exploration constant. In our implementation the noise p is uniform distribution over the actions. The parameter (1 aa) can thus be interpreted as REFSOLVER 's belief that the fully observed policy can be trusted.
6 Experiments
We tested REFSOLVER against the implementation of POMCP 21 in the pomdp_pt ppy library 44] in two different 60 60 long-horizon grid- grid-world navigation problems. As REFSOLVER is written in Python, the implementation of POMCP was de- le-Cyytonised for fair comparison.
Note that Dn is common both formulations their observation and transition models the same.

---

We did not compare with DESPOT 29 planning horizon that DESPOT can perform is much lower than POMCP because of requirement to construct a tree of size | Kd where d is the depth of the DESPOT (this difficulty has also been observed [6]] Given the long horizon nature of the problems, one may question comparison with solvers specifically designed for long horizon problems (as summarised in [9]. Most, if not all, of such solvers rely on reducing the effective planning horizon by constructing macro actions sub-policies. Since REFSOLVER does not change the overall structure of action and observation spaces and transition and observation functions, is trivial to apply most techniques that reduce the effective planning horizon Reference- Based POMDP solvers (including REFSOLVER), which in turn will further improve the performance REFSOLVER too.
because the problem scenarios require long horizons and the
All experiments were performed on a desktop computer with an 8 Core Intel Xeon Silver 4110 Processor and 128GB DDR4 RAM.
6.1 Problem Scenarios and Testing Parameters
51
$2
S1 (b) Navigation2: Initial map
S2
(a) Navigation
51
(c) Navigation2:
Modified (b)
(d) Navigation3: 3D Environment
Figure 1: Illustration testing scenarios. (a) Navigationl: landmarks (pink), goal states (green), obstacles (black), danger zones (yellow), initial belief (light blue). (b) and (c) Navigation2: landmarks (pink), goal states (green), obstacles that are present in hoth the initial map and the modified environment (black), additional obstacles that were not known in the initial map (grey), initial belief (bluc). The map in (b) represents the environment used to generate the * policy. The map in (c) represents the environment used for planning and execution. Navigation3: 3D navigation scenario with uneven terrain, goal area (red).

---

6.1.1 Navigation1: Long Horizon
The environment is 60 x 60 static gridworld populated with obstacles, danger zones, and land- marks, as illustrated in Figure la Details of the actions, observations and reward are presented in Section A..7.
POMCP's rollout policy and REFSOLVER'S fully observed policy the A* policy for the fully observed and deterministic version of the problem. POMCP was run with an exploration constant of 300 and maximum depth of 180 this maximum depth is the upper bound for (tree depth + rollout steps). For REFSOLVER, the maximum tree depth was 90, the maximum rollout depth was 180 and 0.5. Both methods were executed for a maximum of 180 steps.
6.1.2 Navigation2: Slightly Perturbed Environment
The environment is a 60 x 60 gridworld populated with obstacles and landmarks. The robot is provided with an initial environment map that was slightly different from the environment used during execution. Details of the scenario (actions, observations, and reward) are presented in Section A.7.2
For testing purposes, we generated 64 different initial maps with randomly placed obstacles and landmarks. For each initial map, randomly generate four slight modifications of the initial map by adding obstacles at random. An illustration of an initial environment map and a corresponding environment used during execution are illustrated in Figure Tb and Ic
Both the POMCP rollout policy and REFSOLVER'S fully observed policy are the A policy for the fully observed and deterministic version of the robot operating in the initial environment map. However, the dynamics, observation, and reward that the robot experiences and receives during execution follow the deformed map, which is different from the initial map.
POMCP was run with an exploration constant of 300 and maximum depth of this maximum depth is the upper bound for (tree depth + rollout steps). For REFSOLVER, the maximum tree depth was 30, the maximum rollout depth was 60 and a 0.5.
6.1.3 Navigation3: 3D Navigation Environment
Navigation3 is 3D environment where drone has to fly over uneven terrain. The drone starts the location illustrated in Tigure|IdJane needs to reach the red goal region, which is located behind the hill. State and observation spaces continuous, while actions are discrete. See Appendix Section
A.7.3 for details.
The rollout and fully observed policy recommend the action that minimises the Euclidean distance between the current state and goal location with no consideration of obstructing terrain. POMCP was run with exploration constant of 400 and maximum depth of 1,50 (upper bound for tree depth + rollout depth). For REFSOLVER, the maximum tree depth was 150, the maximum rollout depth was 200, and
0.4. Both methods were exccuted for maximum of 200 steps.
6.2 Performance Comparison
To evaluate the performance on REFSOLVER, we ran each method on each problem scenario 256 times. For each scenario, each method was given 30 seconds planning time step. The initial policy generation used by POMCP for rollout and by REFSOLVERfor the 2D experiments took an average of 45 minutes for each scenario. We only need to compute this initial policy once for Navigation and as many as the number of initial maps for Navigation2.
For Navigation3, the initial policy generated on-line and takes small fraction of the planning time per step. The initial policy is derived from a simple shortest path distance policy that assumes the environment is totally empty, allowing to be computed fast. Note that this way of generating the initial policy substantially alleviates the
Figure 2: The red line indicates the short- est path from the initial to the goal po- sitions, while the blue line indicates trajectory trace of executing the policy generated by REFSOLVER.
8

---

computational cost, especially for complex problems. The quality of such an initial policy is of course relatively low, as indicated by the red-line in F However, our results indicate that REFSOLVER is able to iteratively deform the initial policy to generate a good strategy for the environment the robot operates in. Note that the trace of the deformed policy indicates that the agent aware of the potential collision danger quite early, even though it requires more than 100 steps lookahead.
Table D compares the success rates and the average total discounted reward (with a 95% confidence interval) achieved by POMCP and REFSOLVER, respectively. To better understand the performance improvement with respect to the planning time, we also ran Navigation2 with different planning times per step. The results of 256 runs are presented in Table 2 The results indicate that in all instances and for all planning times, the basic implementation of REFSOLVER was able to reach the goal with a significantly greater likelihood and average total discounted reward.
One may be discouraged by the success rate presented. However, all the problem scenarios presented here have a horizon of over 60 steps, which remains a tremendous challenge for many general approximate on-line POMDP solvers today, as indicated by the performance of POMCP.
Table 1: POMCP vs REFSOLVER with 30 sec planning time per step
Navigation1
Navigation2
Navigation3
Avg Tot Dis Rw
Avg Tot Dis Rw
Avg Tot Dis Rw
Solver
% Succ.
% Succ.
% Succ.
POMCP
-284 + 5
11
- 181 + 13
0
87 + 0
REFSOLVER
-201 = 24
49
-95 = 16
64
5 + 21
Table 2: POMCP vs REFSOLVER in Navigation2 with different planning time per step.
Planning Time Per Step (Seconds)
10
20
30
Avg Tot
Avg Tot Disc Rw
Avg Tot Disc Rw
Solver
% Succ.
% Suce.
% Succ.
Dis Rw
POMCP
-205 +
7
-208 +-2 4
11
-181 + 13
REFSOLVER
30
137 + 15
36
-128 + 15
49
-95 16
7
Related Work
7.1 MDPs with KL Divergence Minimisation and Reinforcement Learning
The idea of using KL divergence minimisation in fully observable environments goes back to series of works on Linearty Solvable MDP 24 25 26 2 who used it to efficiently approximate
solutions to certain classes of (fully-controllabbee) MDPs. A learning- based algorithm (Z-Learning) was also proposed for problems where the model was not available (24]. Azar al. I extended the approach to general MDPs with stochastic policies and introduced Dynamic Policy Programming which converges asymptotically to the optimal (stochastic) policy of the MDP. The authors also demonstrated that the formulation could be suitably adapted using basis functions to deal with large-scale (continuous) state-action problems. unifying perspective on this approach was then offered by Rawlik al. [19] who demonstrated that the stochastic control formulation can be related to approximate inference control in trajectory optimisation (28) and provided further experimental validation for Z Z-Learning-lin minimisation is closely related to Maximum Entropy RL where some recent theoretical developments
algorithm. Finally, we note that the literature on KL divergence
3 have demonstrated robustness the model (i.e. dynamics and rewards) in fully observable domains.
See Section A.l for brief summary of the theory.

---

As far as the authors are aware, all of the above papers have no parallel in purtially-observalee environments as of yet. As such, this paper can be seen as first step to extending the above results to such environments.
7.2 Sampling-Basee Approximate POMDP Solvers
Methods for finding exact solutions to POMDPs [6] are impractical for realistic robotics problems due to their computational complexity. In recent decades, sampling basslnng-based approximate methods have significantly scaled up the capabilitiess of both online and offline POMDP solvers [T8 21 29 [2]
(see [9] for a comprehensive survey). A major constraint in all state-of-the-an methods is that they rely on a dynamic programming paradigm which necessitates enumeration of actions every belief node of the search tree. As such, existing solvers cannot effectively deal with the curse of history because they do not have sufficient compuational resources to perform a sufficiently long look-ahead.
To deal with this problem, methods that abstract the problem using macro-actions have been proposed 23 5 3 10] where the agent only plans with respect judiciously chosen sequences of actions, called macro actions, or sub-policies. They reduce the effective planning horizon, but can be sensitive the class of macro-actions or sub-policy chosen. In contrast, propose to alleviate the issue via slight reformulation of the POMDP, which allows numerical computation to infer close to optimal policy via sparse sampling of both the action and observation spaces. Moreover, existing techniques that reduce the effective planning horizon can also be applied to Siferenne-BBssee POMDPs, which will further improve its ability to compute good solutions to POMDPs with long planning horizons.
Discussion and Further Work
We have introduced the Reference- BrrerenceeBBseed POMDP, which is modification of the standard POMDP. This modified formulation enables the problem of computing the optimal policy to be analytically transformed into problem of computing expectations, which can be approximated without exhaustive enumeration of the actions. We showed that, under mild assumptions, the standard POMDP can be related Reference- Befeee POMDP via an embedding (Proposition 1. We also presented a preliminary solver REFSOLVER which solves a Reference-Baseeee comparisons on 2D and 3D navigation problems indicate that this preliminary method is promising and can be employed to substantially outperform state-of-the-ar solvers in long-horizon problems.
POMDP. Initial performance
By introducing KI. minimisation with respect to reference probabilities, Reference-Baseee POMDPs are likely to be suitable for problems with dynamically changing POMDP models with long planning horizons where one needs to deform the policy being followed without making abrupt changes to the policy. We also see applications of this kind of framework the context of artificial agents that are guided by a human to make responsible decisions while also judiciously transgressing guidance in the case of significant human error.
One limitation of this paper is that the formulation of Reference-Basseee POMDP asserts that arbitrarly "belief-to-belie set out in Todorov (24) too closelyß This assumption can be relaxed by stating the Bellman equation with respect to stochastic policies over actions a manner similar to Azar et al. ① rather than abstract belief-to-belee to-lliff transitions. Such an approach yields very similar analytical results and avoids the need to recover approximate stochastic actions as set out in Scction 3.3 these results in a subsequent paper.
transitions can be realised which is remnant of following the approach
We expect to set out
The above limitation is just one of the many possible directions for expanding this work. We hope this paper opens new avenues to further scale the capability of POMDP solvers.
Acknowledgements
This work is done collaboration with Safran Electronics & Defense Australia Pty Ltd and Safran Group under the ARC Linkage project LP200301612.
See 19 for further commentary.
10

---

References
[1] M. G. Azar, V. Gómez, and B. Kappen. Dynamic policy programming with function approxi- mation. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pages 119-127, 2011.
[2] K. Dvijotham and E. Todorov. Inverse optimal control with linearly-solvable MDPs. In Proceedings of the 27th International conference on machine learning (ICML.-10), pages 335- 342, 2010.
[3] B. Eysenbach and S. Levine. Maximum entropy RL (provably) solves some robust RL problems. In International Conference on Learning Representations, 2022.
[4] H2RLab. pomdp_py.
[5] R. He, E. Brunskill, and N. Roy. PUMA: planning under uncertainty with macro-actions. In M. Fox and D. Poole, editors, Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, July 11-15, 2010, pages 1089-1095. AAAI Press, 2010.
[6] M. Hoerger, H. Kurniawati, and A. Elfes. Multilevel Monte-Carlo for solving POMDPs online. International Journal of Robotics Research (IJRR), 2022.
[7] L. Kaelbling, M. Littman, and A. Cassandra. Planning and acting in partially observable stochastic domains. Artificial Intelligence, 101(1-2):99-13 134, 1998.
[8] A. N. Kolmogorov and S. V. Fomin. Introductory Real Analysis. Dover, 1970.
[9] H. Kurniawati. Partially observed Markov decision processes and roboties. Annual Review of Control, Robotics, and Autonomous Systems, 5:254-277, 2022.
[10] H. Kurniawati, Y. Du, D. Hsu, and W. S. Lee. Motion planning under uncertainty for robotic tasks with long time horizons. In C. Pradalier, R. Siegwart, and G. Hirzinger, editors, Robotics Research, pages 151-168, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.
[11] H. Kurniawati, D. Hsu, and W. S. Lee. SARSOP: efficient point-based POMDP planning by approximating optimally reachable belief spaces. C. S. W. Burgard, O. Brock, editor, Robotics: Science and Systems III, pages 65-72. MIT Press, 2008.
[12] H. Kurniawati and V. Yadav. An online POMDP solver for uncertainty planning in dynamic environment. In Robotics Research: The 16th International Symposium ISRR, pages 61 1-629, 2013.
[13] Z. Lim, L. Sun, and D. Hsu. Monte Carlo value iteration with macro-actions. In J. Shawe Shawe-Taylor, R. Zemel, P. Bartlett, F, Pereira, and K. Weinberger, editors, Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
[14] C. Lusena, J. Goldsmith, and M. Mundhenk. Nonapproximability results for partially observable Markov decision processes. Journal of Artificial Intelligence Research, 14:83-103, 2001.
[15] O. Madani, S. Hanks, and A. Condon. On the undecidability of probabilistic planning and related stochastic optimization problems. Artificial Intelligence, 147:5-34, 2003.
[16] G. E. Monahan. State of the art a survey of partially observable Markov decision processes: theory, models, and algorithms. Manag. Sci., 28:128:1111 1-61, 1982.
[17] C. H. Papadimitriou and J. N. Tsitsiklis. The complexity of Markov decision processes. Mathematics of Operations Research, (13):41-45000 1987.
[18] Pineau, G. Gordon, and T. Point-based value iteration: an anytime algorithm for POMDPs. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, volume 3, pages 1025-1032, 2003.
[19] K. Rawlik, M. Toussaint, and Vijayakumar. On stochastic optimal control and reinforcement learning by approximate inference. Proceedings of Robotics: Science and Systems VIII. 2012.
11

---

[20] S. M. Ross. Applied Probability Models with Optimization Applications. Dover, New York, 1970.
[21] D. Silver and J. Veness. Monte-Carlo planning in large POMDPs. J. Lafferty, C. Williams,
J. Shawe-Taylor, R. Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 23. Curran Associates, Inc., 2010.
[22] R. D. Smallwood and E. J. Sondik. The optimal control of partially observable Markov processes finite horizon. Operations Research, 21(5):007-11088 1973.
[23] G. Theocharous and Kaelbling. Approximate planning in POMDPs with macro-actions. In S. Thrun, L. Saul, and B. Schölkopf, editors, Advances in Neural Information Processing Systems, volume 16. MIT Press, 2003.
[24] E. Todorov. Linearly-solvable Markov decision problems. In B. Schölkopf, J. Platt, and T. Hoffman, editors, Advances in Neural Information Processing Systems, volume 19, MIT Press, 2006.
[25] E. Todorov. Sciences, 106(28); 1478-1 1483, 2009.
Efficient computation of optimal actions. Proceedings of the National Academy of
[26] E. Todorov. Eigenfunction approximation methods for linearly-solvable optimal control prob- lems. In 2009 JEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, pages 161-168. IEEE, 2009.
[27] E. Todorov and W. Li. generalized iterative LQG method for locally-optimal feedback control of constrained nonlinear stochastic systems. In Proceedings of the 2005 American Control Conference, 2005, pages 300-306, 2005.
[28] M. Toussaint. Robot trajectory optimization using approximate inference. In Proceedings of the 26th International Conference Machine Learning, 2009.
[29] N. Ye, A. Somani, D. Hsu, and W. S. Lec. DESPOT: Online POMDP planning with regulariza- tion, Journal of Artificial Intelligence Research, 58:231-266, 2017.
12

---

A Appendix
A.1 Background on Linearly Solvable MDP
Since the Reference- Based POMDP expands the Linearly Solvable (fully observed) MDPs 24 25 26 to POMDPs, for completeness, here, summarise Linearly Solvable MDPs.
standard infinite horizon MDP is specified by tuple A, A, R. 7), where S and A are the state and action spaces, Tss, s') is the conditional probability function that specifies the probability the agent arrives at state 8' E after performing action a A at state & E S, R is the reward function, and E (0, 1) is the discount factor. The solution to MDP problem is a an optimal policy T S - A that maximises the value function:
V*(s) max aεA
R(s,a)+ +7 Σ T(s.
(24)
s'ES
The works in 24 25 26
consider a class of MDPs where, the state space S is finite and for any states 8, E S, there exists one-step (not necessarily homogeooggeneous) transition probability p(s' s) representing the passive dynamics of the system. They propose new formulation of MDPs, called Linearly Solvable MDPs, to be specified by (S. r, 7), where r : + R is the reward function. A solution to the Linearly Solvable MDP is stochastic state-to-state transition probability u(. s) that maximises:
e(s)= =
sup u(- (()
(r(s) KL (u( [s) (())) +y
Σ u(s' s)e((s)) EEES
(25)
where (s) the set of admissible controls. An admissible control uu-1 is one that prohibits state transitions that are not feasible under the passive dynamics p(- ()-1s).
Now, suppose ws)) == c(()) for any E S, then 25
is equivalent to
w (5) (s)
Σ S'ES
p(s' (s').
(26)
Moreover, the solution w" to the above equation exists and is unique. The optimal stochastic transition to the equation (25) is given by
p(. s)w (-) D 1w (s)
" a'(11))
(27)
where "Iw" := Ee (s) s)w "s') is a normaliser. Intuitively, one can view w" as the desirability score, that (27) represents distorting the passive dynamics transition dynamics that favour transitioning to states with higher desirability scores. Of course, w* is not known priori but it can be determined by iterating the Bellman backup operator given by (26). This computation
essentially reduces to taking expectations under the reference dynamics, which can be computed faster than searching for the optimal value function in (24) directly.
standard MDP can be embedded a linearly solvable MDP. This implies that, for given standard instance of linearly solvable MDP, use
MDP problem (S, T, R, 7),, one embed the above efficient machinery to determine the solution to the linearly solvable MDP u² (-1s). and
then choose the symbolic action a" A such that T(s' s,a") is as close possible to u" (-1 ())
Empirical results in (25) indicate that there is a close correspondence between the optimal value of the embedded standard MDP A, T, R, 7) and the optimal value of the linearly solvable MDP.
A.2 Proof of Lemma 3.1
Step I. We first need to verify that maximiser to the supremum in g exists. To this end, define W(b) e (b)) for any b B and notice that the terms inside the supremum in the RHS of equation
13

---

p can be rewritten as
Σ U(aa, R(bba) [(((,olb((((b.)
(aa o b) Üa, b)
log
+ ? Σ
V(T(b,a,o))
0,0
=- Σ U(a, o(a,o))) [10g log o (100)
U(a,0l8)
4,0
0 ((1,o()))))111))
Σ
0( () log
-log (D]MT((1}}
=- KL (U(..10)) (l.- (r
(6)
+ +og (D[WT](6) (28)
where (b) == Ea. (a, o () (r (b, a, o)) is a normalising factor. Only the KL. divergence term in the last line above depends on U. We know that the KL divergence is minimised when its two component distributions are identical. That is, when
b) = U(a o B(b WT (T(b, a))
(29)
D(WT((6)
is clear that U belongs to the space 2 (b) since (a, of b) = 0 implies that (* o = too. Therefore, conclude that the supremum attained and that U is the maximiser.
Step 2. Now, we can essentially repeat the classical argument from Ross (0 (see e.g. Theorem 6.5). Namely, let Φ (BB)) + BBB) be the Bellman backup operator
(bb = sup (R(b, U) - KL (1] 7 Eu [VT,..)))] (E
(30)
where, for brevity, we write
KL(U I=
= KL (U;: ((.-
(31)
and
Ey (TT(,)))) = Σ ((a
(32)
0.0
We want show that o is contraction. For any b B and any V1, V/ B(B), (b) (b)
- ( ))])
sup
(E
(R(b,() =L
sup
()
(R(b,U*) (T( +10++>Er> (2] (1)
- KL(U"" (0) +70)+ (V>
? Σ U' (((.oo/b) (a) ((0.000)))) 1/ (T(b,,))))))
a.o
I Y 1 V2
(33)
where U is the maximiser of Reversing the roles of Vi and V22 and using the fact that E B is arbitrary, we conclude that | 11/2l00 < 7 V V2lloo.
R(b, U) (U(UI| + By (T)(T.)))) ))]
(34)
(35)
Since assumed that y (0, 1), we conclude that & is contraction.
14

---

A.3 Proof of Theorem 3.1
Repeating the argument in Step
A.2
we see that the Bellman equation reduces to
(bb) log D [6)] log Σ
W
(36)
which, after taking exponents, justifies the equivalence to Given this equivalence and Lemma it is clear that (TT) has unique solution. To be more explicit, suppose for a contradiction that solutions). Then by the equivalence between the two Bellman equations, (9) would either have solutions or more than solution which contradicts the existence and uniqueness guaranteed by Lemma 3.1 Finally, 12 follows from the form of the maximiser at each Bellman step.
does not have exactly one solution (up to Illl-qquivalence
A.4 Proof of Proposition 3.1
For brevity, we will fix b and drop it from our notation. Also write π = Ta = T(a b). The Lagrangian for the constrained problem is
=-(-=111 T(-16) and
P(ola)
C(T, A) ( P(ola)TT log
+N 1). U~
(37)
a,o
We require, in addition, that the minimiser n² (which exists due to the Weierstrass extreme value theorem) is such that nे 2 0 for each E A. The first order necessary conditions gives
na (1+ exp]-I[(a] Va A
(38)
and the constraint equation gives
ETe Ta ma=
Σ exp exp(-II(a)]-
(39)
Hence the only candidate for the minimiser is π such that
expl [[]]]]]
Va A.
(40)
Σ ZAEA expl exp]-I1(a)]
The Hessian of positive definite for any À and π E A(A), so we conclude that n² a minimiser. Finally, that n 2 0 for every a A is clear from 44
A.5 Proof of Proposition 4.1
Proof. Fix â E A and b E B. If we set
1, a=å
(a =
(41)
0. otherwise
and
U (a, (a, o b) = P(o à () (a|b) (b) E %
(42)
then the constraint (20) satisfied trivially. Straightforward computations show that the constraint 21 is satisfied by (a, o/ b) with (p, U) as defined in (22) and 233)
15

---

A.6
Algorithm REFSOLVER
Algorithm 1 REFSOLVER
parameters:
(S,A, T, 7)
22:
procedure SIMULATE(s, h, depth)
max-depth
23:
if E G or depth > max max-depth then
max-rollout-depti
24:
return exp(ROLLOUT(ss, h, max-depth))
expl const
25:
end if
require: 7 E 10, 1)
26:
B(h) B(h) U {+}
27:
N(h) +- (hh) +1
PRE-PROCESS (OFFLINE)
28:
X ~ (erroulll(())
29:
(x) Unif-ActO [(X-o)
I: + FENERRTTEFF-POLICYYI A,T, R,))
30:
(s', Rt ~ (s((s,))
31:
N(ha)= N(ha) +1
2: RUNTIME (ONLINE)
32:
R(ha) - R(ha)
N(ha
R(ba)
W f W+ Riha' SOMULATE( hao dopth 1)-(
3:
procedure PLAN-AND-EXECUTE(() EXECUTE(1)
33:
N(h)
4: repeat
34:
return W(h)?
if = 0 then
35:
end procedure
6: 8~ I
7:
else
36: procedure OPTNAAL-STOCHHATTIC-PPLL.L
8:
end B(h)
37:
+
b Normaliser
38:
for a E A and o E do if hao & T then
10:
SIMULATE(S, h,
39:
11:
until TIMEOUT)
40:
ú' ('(hao)
12:
return SPTIMAL-STOCHASTIC-PPP POLICC)))))))))C
41:
else
13:
end procedure
42:
O' ('(hao) + N(hoo) N(A) e (")
43:
end if
14:
procedure ROLLOUTSS,, h, depth)
44:
D + D + (hhoo))
15:
if +- (s)
45:
end for
16:
depth max-rollout-depth then return R(s,a)
46:
for A do
47:
II(a)) +
N(hoo) log N(aa)
N(hao)
18:
end if
[haa) (hao))
19:
(s', R) [(, generative model
48:
end for
20:
return R(s, ROLLOUT(S hao, depth +
49:
n² + {a (xp[-Maa)/DD"
50: return RANDOM -AMOMMSSMMPE(TT
21:
end procedure
51:
end procedure
A.7 Details of Experimental Scenarios
A.7.1
Details Navigationl Scenario
The robot can move in the four cardinal directions with 0.1 probability of actuator failure. realised movement leads to collision with an obstacle or the edge of the map, movement occurs and the robot remains in current position. If the robot's true state a landmark, the robot receives position reading uniformly in the 9 x 9 grid around the robot's true state. Outside the landmarks, the robot receives no observation. The robot receives penalty of -100 for entering a danger zone and reward of +300 for entering goal state. In both cases, the problem terminates. Every other state incurs a reward -1. The discount parameter was 0.99. The robot's initial belief was equally distributed between two initial positions that were uniformly sampled from the southern-most of the map.
A.7.2 Details Navigation2 Scenario
Similar to Navigationl, the robot's action space consists moves anywhere in the four cardinal directions NORTH, SOUTH, EAST, WEST. To simulate noise in the robot's 's actuator's, actions fail with 0. probability, and this occurs, the robot moves randomly in a direction orthogonal to the one specified. If the realised movement leads to collision with an obstacle or the edge of the
16

---

map, no movement occurs and the robot remains in its current position. If the robot's 's true state is landmark, the robot receives a position reading uniformly in the 9 grid around the robot's true state. Otherwise, the robot receives no observation. The robot receives reward of +600 for being in a goal state, and for being any other state. The discount parameter was ? = 0.99. The robot's initial belief was equally distributed between two initial positions that were uniformly sampled from the southernmmos row the map.
A.7.3 Details of Navigation3 Scenario
The state and observation spaces have six dimensions which represent the position (I, y, 2) and orientation (roll, pitch, yaw) the drone. There are 12 actions that increase or decrease one dimension by 0.2 units. Action and observation noise is sampled from multivariate Gaussian distribution with 0 mean and 0.032 standard deviation. If an action results in a collision with the terrain, the robot receives -500 penalty, and the world terminates. Reaching the goal area receives a 1000 reward, and each step incurs a -1 penalty. The drone's initial configuration ( (-4.0, -1.0, 0.0, 0.0, 0.0, 0.0) and the goal are is the ball with centre (10.4, 3.0, 0.45) and radius 0.25. The start and goal not in a direct line and the robot needs to go over the hill near the goal area to reach its destination. The discount parameter was 7 0.99. The robot's initial belief is populated with its exact start position.
A.8
Source Code
We include the source code for REFSOLVER, which is developed on top of pomdp_py as a Supple- mentary Material. https://githu/: cwm off.e//aeeoooollooabeebeee.eee.e pondp_neurips23
17


Reviews:
[{"review_id": "CMNcPQEtBC", "reviewer": "Reviewer_NtUC", "summary": "The paper is well written, clear and concise, with a well defined scope and goal.\n\nThis work extends prior work on Linearly Solvable MDPs (LS-MDPs) to the partially observable setting.  LS-MDPs are alternate decision processes whose control paradigm is shifted (w.r.t. standard MDPs) such that the system defines passive state dynamics (as in Markov chains or HMMs), and control is performed by applying smooth modifications to these passive dynamics that directly alter the state dynamics.  The theory of LS-MPDs already contains efficient solution methods for such decision processes.  The formulation of LS-MDPs can then be exploited to solve MDPs by embedding the MDP as an LS-MDP, and choosing the action from the action-set that most closely resembles the optimal control associated with the LS-MDP.\n\nIn this work, the authors extend LS-MDPs to the partially observable setting in a fairly straightforward way:  by applying the LS-MDPs framework to the belief-MDP associated with the POMDP at hand.  LS-MDPs operate in terms of state-to-state transitions and distributions U(s'|s), which in the POMDP case become belief-to-belief transitions U(b'|b), or, equivalently, U(a, o|b) (since the tuple (b,a,o) uniquely determines the next belief b').  Aside from this notational simplification, the resulting method seems to reflect the basic LS-MDP very straightforwardly.\n\nPossibly the main difficulty remains that some computations remain complex in belief-space, as the authors also note, w.r.t W^*.  The authors therefore propose to employ sampling-based solvers to estimate W^*, resulting in RefSolver, their proposed planning algorithm for POMDPs.\n\n- Minor notes:\n-- Border cells are cut off from Figure 1;  remake graphics showing them in full.\n-- Probably as a consequence of the above, the initial belief (in blue) is not visible in Figs 1a and 1b.\n", "questions": "- both the POMCP baseline and the proposed RefSolver use the fully observable policy obtained by A* in one way or another.  POMCP uses it exclusively as a rollout policy, while RefSolver uses it in what seems a much more impactful manner by having it determine the passive dynamics of the reference-based POMDP formulation. WHat is the impact of this choice?  Would the algorithm work well enough even if a worse policy were chosen?  what about a random one?", "limitations": "- The final paragraph already identifies a few limitations of the proposed method concerning the computational methods employed.\n\n- My question to the authors might also highlight another limitation of the resulting method, depending on the authors' answer.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- theoretically sound\n- shows significant improvements against POMCP baseline on reasonably stochastic and partially observable gridworld navigation tasks", "weaknesses": "- the evaluation is run only on 2d navigation tasks where the actions chosen by the optimal fully osbervable agent strongly correlate with the optimal actions chosen by a partially observable agent (see question below).  Given the role and influence that the optimal fully observable policy has on RefSolver, it's unclear how much the optimality of the passive policy influences the overall method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the positive review and feedback.\n \nJust as a clarification, you mentioned in your review that the extension of LS-MDPs to partially observable domains is “very straightforward”.  We do note however that there are some interpretive challenges of formulating “belief-to-belief” stochastic transitions in the context of POMDPs as it requires relaxing the action space to provide for stochastic actions.  We believe that this insight is what makes the extension possible and useful and should be considered a contribution as well.\n \nRE “Remake graphics in Figure 1”: Note that each grid is 60x60 cells and so some cells look very small. The cells are there but are different grades of blue depending on the intensity of the belief. E.g. in Navigation1 the initial belief is spread out uniformly over 12 cells adjacent to S1 and S2 while in Navigation2 all the mass is concentrated on 2 cells adjacent to S1 and S2. We can make a note to explain this in the caption and increase the image sizes in the final version. There is no initial belief on Fig1b as this map is only used to construct the fully observed A* policy and is not used for planning under partial observations.\n \nRE Weaknesses: We recognise that the experimental results are preliminary at this early stage. We are currently working on how the algorithm could be scaled up to higher-dimensional navigation tasks as well as to motion planning tasks but the role of this paper was just to demonstrate that the approach is promising and to lay down the theoretical underpinnings. As mentioned in the general comments, we note again that even in this relatively simple environment, POMCP and DESPOT have difficulty managing the size of the search tree.  RefSolver on the other hand relies on analytical properties to selectively sample the tree.\n \nRE Questions: We do acknowledge that a judicial choice for the reference policy needs to be made as the problem formulation, by definition, rewards respecting the reference policy (see eq 10). However, a solution to a Ref-POMDP will also ignore the reference policy if greater rewards are available by deviating from it (also eq 10). As such, there is a level of robustness against the reference policy baked in to the formulation. We acknowledge the method should therefore be carefully applied to situations where it's apparent that a \"good\" reference policy exists (e.g. minimise energy) or can be justified (e.g. using an embedding as outlined in Sec 4). As noted in the summary, we envisage RefSolver to be suitable for problems with dynamically changing POMDP models where one needs to deform the policy being followed without making abrupt changes to the policy. We also hope that for more general problems we can substantially revise the algorithm by iteratively improving the reference policy.\n \nWith respect to POMCP using the A* policy, this is an advantage over simply using a standard uniform rollout especially in a long-horizon problem. With the A* policy there is a good chance that the rollout will realise the large rewards toward the tail end of the time horizon, whereas there is almost no chance using a uniform rollout given the long horizon.\n \nAs a general point, note that most complex problems in optimisation require a heuristic or initial policy that can be iteratively improved so we do not believe that the requirement of a reference policy is too restrictive.    Generally, as we suspect it is the case here, the proximity of the “guess” to the final solution also determines the speed of convergence."}, {"review_id": "BBF57NvF6L", "reviewer": "Reviewer_poha", "summary": "The paper introduces and investigates the concept of reference-based POMDP, which addresses the challenge of finding an optimal policy in partially observable environments. The main objective is to simplify this problem by leveraging a baseline fully observed policy. The authors propose that solving a reference-based POMDP can be achieved by iteratively computing expectations using the provided reference (stochastic) policy. They further argue that this approach can be viewed as an extension of Linearly Solvable MDPs to scenarios involving partial observability.", "questions": "1. The paper presents a systematic way to solve POMDPs, albeit with some heavy assumptions on:\n\n    a. availability of a reference belief-to-belief transition probability - a distribution which is constructed using a fully observed policy. \n\n    b. knowledge of admissible reference transition probabilities. computing iterative expectations using the given reference (stochastic) policy.\n\nIt would be nice to highlight these assumptions and exact contributions in the introduction. \n\n2. Is  the second paragraph in Introduction just an interpretation of the paper’s formulation/ main algorithm (Alg. 1 included in appendix 8.7)? If it is just an interpretation, the logical flow of paragraph seems conflicting because: \n\n    a. The paragraph starts by saying the problem of reward maximization in POMDPs is challenging. And then proposes to use constrained optimization as a solution - when in general constrained optimization problems are more complex than unconstrained ones.\n\n    b. Since the optimal value function of the Reference-Based POMDP can be computed by purely computing expectations under the reference transition probabilities recursively using Monte Carlo approximation, where exactly is constrained optimization coming into picture? \n\n\n3. In paragraph 3 in Introduction, authors mention “the standard POMDP can be related to the Reference-Based POMDP via an embedding” - what does an embedding mean here? I would be nice to elaborate this. \n\n\n4. The paper does not include a section on related works. If it was because of space constraints, I strongly recommend adding this section in Appendix. From reading the paper, it is unclear to me what the state-of-the-art in solving POMDPs is - both algorithms and evaluation environments. For example, the paper does not comment about this recent work [1] on solving POMDPs using approximate information state. \n\n\n5. For the evaluation environments considered, I believe one could also solve these problems using meta-RL (VariBAD [2]) or robust-RL. Can the authors comment on why is it better to cast these problems as POMDPs as opposed to meta-RL or robust-RL? \n\n\nI would be happy to increase my score if the authors could clarify the queries above. \n\n\nReferences:\n\n[1] Subramanian, J., Sinha, A., Seraj, R., & Mahajan, A. (2022). Approximate information state for approximate planning and reinforcement learning in partially observed systems. *The Journal of Machine Learning Research*, *23*(1), 483-565.\n\n[2] Zintgraf, L., Schulze, S., Lu, C., Feng, L., Igl, M., Shiarlis, K., ... & Whiteson, S. (2021). Varibad: Variational bayes-adaptive deep rl via meta-learning. *The Journal of Machine Learning Research*, *22*(1), 13198-13236.", "limitations": "A more detailed discussion on limitation of the solution approach to very high dimensional problems can be included. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Solving POMDPs is a challenging problem.\n- The authors present a new problem formulation for POMDPs called Reference-based POMDPs that uses a reference baseline policy. \n- The authors present solution approach to this new problem formulation. ", "weaknesses": "- It is hard to place the work in current state of the literature in this field because of a lack of discussion on related works. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review and feedback.\n \nRE Weaknesses. We will provide additional related work, in relation to Max Entropy RL and stochastic control on top of those already provided. The paper is inspired by an interesting series of papers by Todorov (see ref 18-20), namely Linearly Solvable MDPs, which is summarised in 8.1. These works focused on MDPs whereas we generalise the approach to POMDPs and provide some ways of dealing with the infinite-dimensionality of the belief space using an approximate solver for the Ref POMDP.\n \nRE Question 1. We do not need a reference belief-to-belief transition probability that is constructed using a fully-observed policy. Our fully-observed policy was just one example of a bottom up approach to construct such a policy.  Rather, it is enough to have any initial reference policy which (stochastically) transitions from belief to belief that serves as an initial guess to the problem. The state transition of the reference policy need not be known; only the belief-to-belief level needs to be known.  For instance, the reference policy could be sampled under some generative model.  Some good guesses might be sampled free dynamics or human inputs or an offline POMDP policy from a similar environment.  Of course, as in any optimisation problem, if this initial guess is close to the optimal solution this is useful, but guesses can be iteratively improved upon. \n\nRE Question 2. I wonder if you could clarify what you mean by “constrained optimisation”. For a precise formulation of the modified problem see equation (10). We stress that this is an entirely different problem to the standard POMDP where a \"reference transgression term\" is introduced by the KL term. It turns out that, under suitable transformations, each Bellman step can be optimised analytically (12) which is why the Bellman equation can be solved by taking pure expectations under the reference measure.  Note that, we do mention “constrained optimisation” in line 185 but this is in the context of the recovering stochastic actions rather than with respect to the formulation.\n \nRE Question 3. See Definition 4.1 and Section 4 for a complete explanation. This was inspired by Todorov’s idea which is briefly summarised in Section 8.1 (lines 403-408).  Intuitively, we say that a standard POMDP can be embedded in a Reference-Based POMDP if we can choose parameters to the Ref-Based POMDP such that, for any action in the standard POMDP, there are points in the relaxed space of stochastic actions where the objective functions align.  The idea is that if an embedding can be found, there is a hope that the solution to the Ref-Based POMDP should be close to that of the standard POMDP and so the more efficient machinery of the Ref-Based POMDP can be readily applied.\n \nRE Question 4. Thank for for this feedback. We provided the background in Appendix (8.1) and will expand the scattered related work into a section in the Appendix too. Briefly regarding state of the art, while POMCP and DESPOT are relatively old algorithms, they still represent the canonical benchmarks to beat for online POMDP solvers especially for discrete models. See reference [9] for a recent survey of the field and various extensions of these main algorithms.\n \nRE Question 5. For problems such as Navigation1 where we need a long planning horizon and identification of the use of uncertainty reduction to solve the problem, general RL methods (including [2]) that do not represent uncertainty explicitly, when confronted with long horizons, will face difficulties. As for [1], it is actually very related to POMDP. Information state is an established concept that can be viewed as a more general representation to the concept of beliefs in POMDP[e.g.,  M. Hauscrecht. Value-Function Approximations for Partially Observable Markov Decision Processes. JAIR 2000]. In this sense, POMDP can be viewed as providing a more compact representation of uncertainty compared to  Information states. In fact, [1] proposes to frame PORL based on approximate POMDP planning. Therefore, we foresee that a method that improves POMDP solving or reformulates POMDP into something that can be solved with less computational resources could in turn be useful for PORL too. "}, {"review_id": "x9LTLDraNI", "reviewer": "Reviewer_RFcX", "summary": "The authors propose reference based POMDPs, where the agent needs tradeoff between achieving environment rewards and following a reference policy.", "questions": "1 As for the definition of the policy, is that $\\pi(a|b)$ or $\\pi(a,o|b)$? In L143 it seems to be the latter. Then, is the belief-to-belief transition $U(a,o|b)$ equals to a policy ? However, the $p(o|a,b)$ seems to contain the environment observation probability which is the intrinsic nature of the environment. As for the reference policy, is it correct to say the reference based pomdps only requires it to provide $p(a|b)$ as in Eq.6? I think this part is somehow confusing for me and I suggest further clarification.\n\n2 According to Eq 10 and Eq 19, the policy chooses sup $U$ while the standard POMDP chooses max $a$. can you further explain the differences between the two? Is it correct to see the reference based POMDP equals to a standard POMDP with different reward function?\n\n3 In section 5 and experiments, the reference policy mainly restricted to a fully-observed based policy. I think reference-based pomdp setting pretty much relies on the performance of the reference policy, and in real world, the base policy might be much worse since the fully observation might not be accessible. It will be interesting to see whether the methods can run well with different initial policy, especially when the initial policy is not that good. Can the methods still benefit from it?\n\n", "limitations": "\nN/A\n", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "generally, I think the reference based pomdps are a good idea and can solve some real world problems;", "weaknesses": "see below", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review and feedback.\n \nRe Question 1. It should be $\\pi(a, o | b)$ or equivalently $\\pi(b’ | b)$.  By definition of the problem, one chooses belief-to-belief distributions over next beliefs (or, equivalently, action-observation pairs). This is a relaxation of the concept of picking a single action (i.e. point mass) as is classical. A policy is a mapping from a given belief to a distribution over action-observation pairs.\n \nAt the most abstract level the reference policy could be given in the top-down form (5) – e.g. a noisy version of an offline POMDP policy computed on a similar environment.  However, in some cases it might be more appropriate to construct the reference policy from the ground up as in (6) and (7).  We acknowledge that the notation in $U^p$ in (5) is a little misleading as it seems to assume that some reference $p$ is given a priori.  This could be changed in the final paper e.g. $\\bar{U}$ to denote a top-down policy versus $U^p$ to denote a policy generated from the ground-up.\n \nRe Question 2. We stress again that the two problem formulations are different but related.  The main difference is that a Ref POMDP tries to balance trading off respecting a reference policy while also achieving higher rewards - see (10) while a standard POMDP does not. As noted in the general comments and the paper, this leads to computational advantages which can be exploited to deal with standard POMDPs.\n\nThe reason for the supremum is that  a Ref POMDP requires choosing a distribution over action-observation pairs rather than a specific action. As the space of distributions is infinite-dimensional and objective functions are only assumed to be bounded, a supremum is taken. It turns out that the maximiser is actually attained (see Step 1 in Proof of Lemma 3.1) but this is not known a priori.\n \nMoreover, the Bellman equations differ so Ref POMDPs and classical POMDPs really are not the same thing. Compare (2) and (10). However, we demonstrate in Section 4 that a classical POMDP can be embedded inside a Ref POMDP provided the reachable belief space is not too complex. This means that one could approximate solutions to classical POMDPs by casting them as Ref POMDPs. Because solving RefSolver is innately faster than standard POMDPs, we could take advantage of this idea to find efficient solvers for some POMDPs. We are currently further investigating this idea.\n \nRe Question 3. We do acknowledge that a judicial choice for the reference policy needs to be made as the problem formulation, by definition, rewards respecting the reference policy (see eq 10). Of course, if the initial reference policy is very misleading, then this would not lead to useful solutions for the POMDP. However, a solution to a Ref-POMDP will also ignore the reference policy if greater rewards are available by deviating from it (also eq 10). As such, there is a level of robustness against the reference policy baked in to the formulation. A good way to think of the reference policy is as a “heuristic” or “initial guess” which can be jettisoned by the Ref-POMDP’s solution if it is advantageous to do so. As noted in the summary, we envisage RefSolver to be suitable for problems with dynamically changing POMDP models where one needs to deform the policy being followed without making abrupt changes to the policy. We also hope that for more general problems we can substantially revise the algorithm by iteratively improving the reference policy.\n\nAs a general point, note that most complex problems in optimisation require a heuristic or initial policy that can be iteratively improved so we do not believe that requiring a reference policy is too restrictive.    Generally, as we suspect it is the case here, the proximity of the “guess” to the final solution also determines the speed of convergence."}, {"review_id": "qNqoMT8LDj", "reviewer": "Reviewer_Kh8M", "summary": "The paper proposes to regularize online policy search in POMDP by providing a reference stochastic policy. The idea is illustrated on two synthetic grid domains.", "questions": "How is the proposed approach related to methods developed for stochastic control with latents? Seems to be the same setting.", "limitations": "The limitations are addressed adequately.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper attempts to systematically incorporate prior knowledge to improve online POMDP planning.", "weaknesses": "1) The proposed approach is not well placed in the literature. The approach is not new --- the reference policy is what is known as policy prior in Bayesian approach or policy regularizer in frequentist approach. There are quite some works on that. If the work provides a new formalism to these notions, this should be properly related to prior work.\n\n2) The empirical evaluation is insufficient. The approach is evaluated on two synthetic grid worlds only, on which it outperformed some implementations of POMCP, and was not compared with DESPOT. It is easy to craft problem instances for any algorithm so that the algorithm looks the best, this is a fact known as 'no free breakfast theorem' in computer science. For an informative evaluation, the algorithm should be compared on domains and settings on which POMCP and DESPOT were compared.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to provide feedback. See responses below.\n \nOn “ The approach is not new – the reference policy is what is known …” We respectfully disagree.\n\nFirst, we would like the clarify the main contributions of the paper by referring you to the general comments of our rebuttal above.\n\n Second, we like to note that although at the very high level, the mechanism may seem like a policy prior in a Bayesian approach, the reformulation and implication of the reformulation to solving POMDPs is, to the best of our knowledge, novel and distinct to existing approaches.   We emphasise that the major contribution of the paper is that we propose a reformulation of POMDPs, such that the  optimisation for solving POMDPs no longer requires exhaustive enumeration of the action space (this enumeration is required by almost any POMDP planning method today). Instead, optimisation can be performed analytically as a consequence of the relaxation which, under suitable transformations, leads to a linearisation of the Bellman equation (Theorem 3.1) and allows the Bellman equation to be computed as an expectation, which in turn can be more efficiently computed using Monte Carlo methods relative to other state-of-the-art POMDP solvers.\n\nThis contribution represents an extension of the theory of Linearly Solvable MDPs (see Todorov [18-20]) to partially observable domains. Note that Linearly Solvable MDPs are closely related to Max Ent RL as noted in Section 7 Summary of the paper, where some recent theoretical developments have demonstrated robustness to the model (i.e. dynamics and rewards) in fully observable domains (see [2]) but again we are not aware of a parallel in partially-observable domains as of yet.  Of course, model uncertainty could be explored at a later stage and is important for real-life applications, but this paper's scope was simply to demonstrate both theoretically and experimentally the feasibility of Ref POMDPs in the context of partial observability where the model itself (i.e. transition, observation and rewards) are known.\n \nRe Weakness 2. We agree that further experiment on higher-dimensional environments should be done to further validate this approach. However, it should be noted that we have not manufactured problems to yield good results. E.g. If the A* policy were blindly observed in Navigation1, this would consistently yield poor results. What both our experiments demonstrate is that RefSolver can improve on “good” (albeit suboptimal) reference policies which is the main point. We did not compare RefSolver to DESPOT due to the long-horizon environments as stated in the paper (see lines 264-267). Constructing a DESPOT for 4 actions with a max depth of 60 is very expensive because each action needs to be visited at each observation branch. This issue has also been highlighted in [5]. However, we do agree that it would be appropriate to run experiments in higher-dimensional environments with shorter planning horizons.\n \nRe Questions: Please refer to our clarification on the main contribution in the general comment."}, {"review_id": "HpBrcVErKl", "reviewer": "Reviewer_Hi3x", "summary": "This paper presents a method to solve POMDPs by considering a reference policy. The solution of a reference-based POMDP is presented. Then the existence and uniqueness of the solution are proved. Then the author shows the connections between a reference-based POMDP and a standard POMDP. In the end, an online planning algorithm is developed.", "questions": "Does the reference policy always exist and available? \n\nWhat's the purpose of theorem 3.1?\n\nWhen a standard POMDP can not be approximated by a reference-based POMDP?\n\nIs there any other baseline that came up in the past 13 years? The baseline seems to be out of date.\n\n", "limitations": "A reference policy must be available. \n\n", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The POMDP problem is worth exploring, starting from the case that a reference policy is available is a good start.\n\nThe general idea is easy to follow.\n\nTheorems are developed for reference-based POMDP. Although some steps rely on approximation, the logic chain of the analysis is complete.", "weaknesses": "It is a bit hard to understand all the math details. It is unclear to me what is the purpose of theorem 3.1.\n\nHow to get the initial reference policy can be a major barrier to applying this method. For example, the author mentioned a way to get the reference policy from a fully observable environment seems to be a leak of the optimal solution, which I think is inappropriate.\n\nPlease present the assumptions explicitly.\n\nThe experiment is relatively simple and not convincing enough. It is unfair to compare the baseline with the method when the reference policy is derived from a fully observable environment.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive review and for your questions.\n \nRe “Weaknesses: purpose of theorem 3.1”. This is the main Theorem in this paper and is a straightforward extension of the LS-MDP of Todorov (see eq 31 and 32) to the POMDP. It’s main point is to demonstrate that: 1) the Bellman equation for a Ref-POMDP can be represented as an expectation under the passive dynamics\n; 2) the optimal policy (by definition, a belief-to-belief transition probability) can be obtained explicitly after solving the Bellman equation. As noted in the paper, these facts can be leveraged to efficiently approximate the solution.\n \nRe ”Weaknesses, how to get the initial reference policy…” We do acknowledge that a judicial choice for the reference policy needs to be made as the problem formulation, by definition, rewards respecting the reference policy (see eq 10). However, a solution to a Ref-POMDP will also ignore the reference policy if greater rewards are available by deviating from it (also eq 10). As such, there is a level of robustness against the reference policy baked in to the formulation. A good way to think of the reference policy is as a “heuristic” or “initial guess” which can be jettisoned by the Ref-POMDP’s solution if it is advantageous to do so. Note also, in our environments, the reference policy generated by the A* policy is suboptimal in general due to partial observability and transition noise (e.g. starting at S1 in Navigation 1 and proceeding via the A* policy almost certainly leads to very negative results). As noted in the summary, we envisage RefSolver to be suitable for problems with dynamically changing POMDP models where one needs to deform the policy being followed without making abrupt changes to the policy. We also hope that for more general problems we can substantially revise the algorithm by iteratively improving the reference policy.\n\nAs a general point, note that most complex problems in optimisation require a heuristic or initial policy that can be iteratively improved so we do not believe that such the requirement for a reference policy is too restrictive.  Generally, as we suspect it is the case here, the proximity of the “guess” to the final solution also determines the speed of convergence.\n \nRe \"Please present the assumptions explicitly.\" Agreed that we can state assumptions and scope of application clearly upfront. This can be updated in the final version.  The key assumptions of our formulation is that a stochastic belief-to-belief transition reference policy needs to be given and that the model is known.\n \nRe ”Weaknesses, the experiment is relatively simple…” We acknowledge that the experiments are preliminary, but they demonstrate some key advantages of our approach. Both navigation problems have a long horizon, and we demonstrate in Navigation 2 that the modified environment can be successfully navigated even when the A* policy is generated off the initial map (i.e. A* policy is suboptimal). This is one application of Ref POMDPs which we think could be leveraged in applications where there is some uncertainty about the real environment. Note also that, while we used a fully observable policy as a reference here, this is not a requirement to employ the formulation (e.g. an offline POMDP policy from a similar environment could be used).\n \nRe ”Q, “When a standard POMDP can not be approx….” See lines 230 – 234. Essentially the result says that the representation of the belief space needs to be simple.   More explicitly, the size of the representation should be small with respect to the number of states.\n \nRe \"Q, is there any other baseline...\" While POMCP and DESPOT are relatively old algorithms, they still represent the canonical benchmarks to beat for online POMDP solvers especially for discrete models. See reference [9] for a recent survey of the field and various extensions of these main algorithms."}]

Author rebuttal:
We would like to thank all the reviewers for their contributions and respond to some general points here.

First, we would like to emphasise again the key contributions of this paper.  The major contribution of the paper is that we propose a reformulation of POMDPs, such that the  optimisation for solving POMDPs no longer requires exhaustive enumeration of the action space (this enumeration is required by almost any POMDP planning method today). Instead, optimisation can be performed analytically as a consequence of a relaxation which, under suitable transformations, leads to a linearisation of the Bellman equation (Theorem 3.1) and allows the Bellman equation to be computed as an expectation, which in turn can be more efficiently computed using Monte Carlo methods relative to other state-of-the-art POMDP solvers.

We call this general reformulation of POMDPs a Reference-Based POMDP. The solution of a Reference-Based POMDPs needs to respect some given reference policy (e.g. heuristic, initial guess) while also searching for high rewards. A key idea in the formulation is to relax the space of optimisation such that policies are no longer mappings from beliefs to deterministic actions but rather stochastic actions.  This means that the Bellman value can be computed as an expectation under the reference stochastic policy, which leads naturally to Monte Carlo methods where the sample distribution is the reference policy itself.  As the reference policy is known a priori, the above insight facilitates algorithms where actions can be sampled, as opposed to enumerated, at each step.  This substantially reduces computation time as demonstrated in our preliminary algorithm. It is important to note that the mechanisms used in our algorithm is fundamentally different to that of the state-of-the art solvers.  Simulations resemble a depth-first search so that a sparse tree is constructed by sampling actions rather than a full enumeration as POMCP and DESPOT do.

In summary, our main contribution is a theoretical justification that decent (albeit suboptimal) reference policies can lead to fast algorithms for solving general POMDP problems substantially better than existing state-of-the-art solvers.  Note that the 2D problem we have presented, while simple, is not trivial even for state-of-the-art solvers like POMCP and DESPOT due to the long horizon and the enormous size of the search tree.  We alleviate this problem by sampling under the reference policy in our algorithm.

Finally, to place this appropriately in the literature, we are not aware of any papers that have extended Linearly Solvable MDPs (see Todorov [18-20]) to partially observable domains. Note that Linearly Solvable MDPs are closely related to Max Ent RL[2] where some recent theoretical developments have demonstrated robustness to the model (i.e. dynamics and rewards) in fully observable domains (see [2]) but again this has no parallel in partially-observable domains as of yet.

Re the Ethics Reviews, thank you for your insights and citations.  We do see, for instance, applications of this kind of framework in the context of artificial agents that are guided by a human to make responsible decisions while also judiciously transgressing guidance in the case of significant human error. Such systems may, at a future stage, be implemented in equipment that may be extremely difficult to manage without automated assistance and, of course, should be thoroughly tested and understood before final commissioning.  We agree it is appropriate to address your recommendations in the final version of the paper.


Meta-review: This paper presents Reference-Based POMDPs, which is a reformulation of a standard POMDP where an agent tries to solve the POMDP while also trying to respect the reference policy. This new formulation also extends linearly solvable MDPs to the POMDP case. The formulation is described and solution methods, which no longer need to iterate over all actions, are introduced. 

The setting and methods are novel and significantly different from standard POMDP ideas. There are also strong assumptions about having suitable reference policy and belief dynamics, but the method seems promising for improved solutions in a large class of realistic POMDPs. 

Because the method is very different from standard POMDP literature, more details and discussion of related work should be included. Currently, it is difficult to follow some of the details and assumptions in the method. The author response and discussion were helpful in this regard but these clarifications should be included in the paper. 

Furthermore, there are some concerns about scalability and generality of the method. More comprehensive results with larger and more complex domains and different quality reference policies would be helpful but, at the least, discussion about these topics should be included.
Decision: Accept (poster)