Belief-State Query Policies for User-Aligned POMDPs
Authors: Daniel Richard Bramblett
Siddharth Srivastava
Venue: NeurIPS 2024 poster (2024)
Keywords: POMDPs
sequential decision making
user-preferences in POMDPs
Primary area: reinforcement_learning
TL;DR: A new framework showing feasibility results, algorithms and empirical analysis for policy representations that support user-aligned POMDP planning

Abstract: Planning in real-world settings often entails addressing partial observability while aligning with users' requirements. We present a novel framework for expressing users' constraints and preferences about agent behavior in a partially observable setting using parameterized belief-state query (BSQ) policies in the setting of goal-oriented partially observable Markov decision processes (gPOMDPs). We present the first formal analysis of such constraints and prove that while the expected cost function of a parameterized BSQ policy w.r.t its parameters is not convex, it is piecewise constant and yields an implicit discrete parameter search space that is finite for finite horizons. This theoretical result leads to novel algorithms that optimize gPOMDP agent behavior with guaranteed user alignment. Analysis proves that our algorithms converge to the optimal user-aligned behavior in the limit. Empirical results show that parameterized BSQ policies provide a computationally feasible approach for user-aligned planning in partially observable settings.

Belief-State Query Policies for User-Aligned POMDPs
Daniel Bramblett and Siddharth Srivastava Autonomous Agents and Intelligent Robots Lab School of Computing and Augmented Intelligence Arizona State University, AZ, USA {drbrambl, siddharths) Casu. edu
Abstract
Planning in real-world settings often entails addressing partial observability while aligning with users' requirements. We present novel framework for expressing users' constraints and preferences about agent behavior in partially observable setting using parameterized belief-state query (BSQ) policies in the setting of goal- oriented partially observable Markov decision processes (gPOMDPs), We present the first formal analysis of such constraints and prove that while the expected cost function of a parameterized BSQ policy w.r.t its parameters is not convex, it is piecewise constant and yields an implicit discrete parameter search space that is finite for finite horizons. This theoretical result leads to novel algorithms that optimize gPOMDP agent behavior with guaranteed user alignment. Analysis proves that our algorithms converge to the optimal user-aligned behavior in the limit. Empirical results show that parameterized BSQ policies provide a computationally feasible approach for user-aligned planning in partially observable settings.
Introduction
Users of sequential decision making (SDM) agents in partially observable settings often have require- ments and preferences expected behavior, ranging from safety concerns high-level knowledge of task completion requirements. However, users are ill-equipped to specify desired behaviors from such agents. For instance, although reward engineering can often encode fully observable preferences [Devidze et al. 2021] Gupta et af. 2023). it requires significant trial-and-error, and can produce unintended behavior even when done by experts working on simple domains (Booth al.) 2023] These challenges are compounded in partially observable environments, where the agent will not know the full state on which the users' requirements and preferences are typically defined. For example, defining a reward function on the belief state to align the agent's behavior with the user can result in wireheading (Everitt and Hutter 2016 (see Sec. 2 for further discussion on related work).
(Fig.Ta)) Ta)). A robot located on spaceship experiences communication error with the ship and needs to decide whether to attempt to repair itself or the ship. Importantly, while a robot error is harder to detect, the would rather risk repairing the robot than repairing the ship, each repair risks introducing additional failures. In other words, the user may expect the robot to work with the following goals and preferences: The objective is fix the communication channel. First, if there is a "high" " likelihood that the robot is broken, it should try to repair itself: otherwise, if there is a "high" likelihood that the ship broken, it should try repair that. Such preferences go beyond preferences in fully observable settings: they use queries on the current belief state for expressing users' requirements while using the conventional paradigm of stating objectives in terms of the true underlying state. Such a formulation avoids wireheading, allowing users to express their constraints and preferences in partially observable settings. Although such constraints on behavior are intuitive and common, they leave significant
Consider a simplified, minimal example designed to illustrate the key principles (Fig.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Robot Repeir Station
Spaceship
Repair Station
11.
-R
M
10.0
Spaceship Repair Problem
93
T (b; θ1 O2):
if Pr [nrroken(rrooo]] > O - repair(robot) Else if Pr [broken(shipp] > 22 repair(ship) Else waif()
64
0.5
(c) Expected Cumulaatve Cost Function is Piecewise Constant and Non-Convex
(b) Parameterized Belief-Staae Query Policy
Figure I: (a) Spaceship Repair running example. (b) parameterized BSQ policy for the user preference from the Introduction. (c) The expected cumulative cost function for (b) with a horizon of 12.
amount of uncertainty be resolved by the agent: it needs to optimize the threshold values "high" probability under which each rule would apply while attempting to achieve the objective.
We introduce mathematical and algorithmic foundations for addressing these problems by defining constraints on behaviors in terms of properties of the belief state, expressed through belief-state queries (BSQs). We prove the surprising result that although the space of possible threshold values in preferences such as the one listed above is uncountably infinite, only finite number of evaluations are required for computing optimal, user-aligned policies for finite-horizon problems. We use this result to develop probabilistically complete algorithm for computing optimal constrained policies. Our main contributions are:
1. A framework for encoding user requirements and preferences over agent behavior in goal- oriented partially observable Markov decision processes (Sec. 3)
2. Mathematical analysis proving that the expected cost function of parameterized BSQ policy w.r.t its parameters is piecewise constant but generally non-convex. (Sec.F)).
3. A probabilistically complete algorithm for computing optimal user-aligned policies in goal-oriented POMDPs (Sec.5)..
4. Empirical evaluation diverse set of problems showing both the efficiency of algorithm and the quality of the computed user-aligned policies. (Sec.) 7).
Related Work
Planning preferences has been well studied in fully observable settings [Baier et al. 2007 Aguas ct al., 2016). VVloshhn et al. [2022) present an approach for complying with an LTL specification while carrying reinforcement learning. Other approaches for using LTL specifications use the grounded state to create a reward function to teach reinforcement learning agents [Toro Icarte et al.) 2018 Vaezipoor et al. 2021). These approaches do not extend partially observable settings as they consider agents that can access the complete state.
In partially observable settings, existing approaches for using domain knowledge and preferences require extensive, error-prone reward design and/or do not guarantee compliance. LTL specifications have been incorporated either by designing reward function that incentivizes actions more likely to adhere to these specifications [Liu et al. 2021 Tuli et al. 2022 or by imposing a compliance threshold [Ahmadi et al.) 2020]. In both approaches, the user calibrates rewards for user alignment with those for objective completion; it is difficult to ensure user alignment. We focus on the problem of guarantecing user alignment without reward engineering.
Mazzi al. [2021 2023 proposed expressing domain control knowledge using belief state proba- bilities, Mazzi et al. [202]] used expert- provided rule templates and execution traces to construct
shield to prevent irregular actions. Mazzi et al. 2023 used execution traces and domain-specified belief-state queries to learn action preconditions over the belief state. Both approaches use input traces and focus on ensuring a policy is consistent with previously observed behavior. We address the complementary problem of computing user-all alegned policies without past traces.

---

Belief-state queries have been used to solve POMDPs with uniform parameter sampling (Srivastaval ct al., 2012] but formal analysis, feasibility of optimizing BSQ policies, and the existence of provably convergent algorithms have remained open as research questions prior to this work.
Formal Framework
This section formally defines the BSQ framework, which expresses user requirements on an agent's belief and is designed for relational goal-oriented partially observable Markov decision processes.
3.1 Goal-Oriented Partially Observable Markov Decision Process
Partially observable Markov decision processes (POMDPs) constitute standard mathematical framework for modeling SDM problems in partially observable, stochastic settings (Kaelbling et al.
1998
[Smallwood and Sondik [973]. Sfate-of-the-art POMDP solvers often rely approximate online approaches [Silver and Veness 2010, (Somani et al. 2013] where recent work addresses the
problem of obtaining performance bounds [Barenboim and Indelman 2023
Lim al. 2023).
We use goal-oriented POMDPs (gPOMDPs), where the agent aims to complete one of the tasks/goals. This eliminates the burden of error-prone reward engineering by using default cost function that associates a constant cost for each timestep before reaching the goal. E.g., the Spaceship Repair problem (Sec. has two objects: the robot and the spaceship. A state is defined using a Boolean function (o) representing whether object o needs repair and an integer- valued function rlocation() representing the robot's location. Both functions not observable. The agent has two types of actions: try to repair object o (repair(o) or wait (wait(). A transition function expresses the distribution of rlocation() depending location. At each timestep, the robot receives a noisy observation obs_ obs_err(o) regarding the status of object o. The set of observations can be expressed as {obs_ (obs__rr(robot)) obs (eeeeerrrr))) perception, obs_ teeeeerrrrrr may not match broken(o), (o). An observation function denotes the probability of each observation conditioned on the (hidden) current state. The goal is to reach the repair station corresponding to the truly broken component. We define gPOMDPs formally as follows.
the action taken and the robot's previous
Due noisy
Definition 1. A goal-oriented partially observable Markov decision process P is defined as {C, F. A. O, T, S2 9, Cost, H, bu) where C is the finite set of constant symbols and is the finite set of functions. The set of state variables for F. Vp, is defined as all instantiations of functions in F with objects in O. The set of states S the set of all possible valuations for Ve: A is finite set of actions, O is subset of F of observation predicates, ' S x A x S - [0. 1] is the Pr(s'(a: s); 9 = S is the set of goal states that are also sink states, Pr(ols, a), Cost(s) = [0 if s E Grelse 1} is the cost function, H is the horizon, and bo is the initial belief state. A solution for a
transition function T(s, a.
Ω : U:S.. x A x O [0, is the observation function; L2(s, a,
gPOMDP is policy that has non-zero probability of reaching G in H - 1 timesteps.
3.2 Belief-State Queries and Policies
Computing policy for any gPOMDP requires planning around state uncertainty. This is done using the concept of a belief state, which is a probability distribution over the currently possible states. Formally, the belief state constitutes a sufficient statistic for observation-actio histories [Astrom] et al. 1965). We express user requirements using queries on the current belief state.
For any belief state b, when action a is taken and observation is observed, the updated belief state is computed using d'(s') = ast(s', a, o) Σ. T(s, a, 8')6(s) where a is the normalization factor. We refer to this belief propagation as b' bp(b, a, o). We extend the notation to refer to the sequential application of this equation to arbitrary bounded histories as 6p* (bo, a1, 01, Ons On) =
bp(....p(bp(( bu. a1, 0z), a2, ...).
For example, the Spaceship Repair problem user preference has the expression "a high likelihood that the robot is broken". This can be expressed as a query on belief state b: Pr[brokent ([fbroken(rooot]] [robot)] > Ortb where Orob is a parameter. If rlocalioon) is fully observable, the expression "the robot location is smaller than O₁ in belief state b" can be expressed as Pr[rlocation)) < O.]o == 1. We can combine both queries to express "a high likelihood the robot is broken and its location is lower than O," ", as: [[bbokke((rboo]] > Orob A Pr Pr(rlocation() < Oi]B == 1.
3

---

Formally, BSQs use the vocabulary of the underlying gPOMDP. There are two types of queries we can ask: (1) whether formula op is true with a probability that satisfies threshold θ; (2) whether the fully observable portion of the state satisfies a formula yp containing threshold O These thresholds represent the parameters of a parameterized BSQ policy. The agent must optimize these parameters to achieve the goal while aligning with the user's requirements. BSQs can be combined using conjunctions or disjunctions to express more complex requirements, which we define as a compound BSQ in Def. 3 We omit subscripts when clear from context.
Definition 2. A belicf-state query Xp (b; o,,o, ②), where b is a belief state, ip is a first-order logic formula composed of functions in gPOMDP P. o is any comparison operator, and ④ E RR is parameter, is defined Xp (b; s c, ①) Pr|[g] e.
Definition 3. A compound BSQ L (b; 3) where b is a belief state and O e R", either a conjunction or a disjunction of BSQs that contain n. total parumeters.
We use BSQs formally express user requirements of the form discussed in the introduction by mapping BSQs with variable parameters to actions. Fig. Tb) illustrates this with a parameterized BSQ policy for the Spaceship Repair problem. Formally,
Definition 4. Let b be a belief state and be a tuple of n. parameter variables over R. An n- parameter Parameterized Belief-State Query policy x(b () is tuple of rules {Ti, Tm) where each r; = V + a; is composed of a compound BSQ Vú and an action a, E A. The set { (V 1,... Vm is mutually exclusive and covers the n-dimensional parameter space IR..
In practice, mutually exclusive coverage is easily achieved using an if... then... else structure, where each condition includes a conjunction of the negation of preceding conditions and the list of rules includes terminal else with the catchall BSQ True (Fig. 1). Any assignment of values 1 R." the parameters θ of parameterized BSQ policy produces an executable policy that maps every possible belief state to an action:
Definition 5. BSQ policy rbb, F) is a parameterized BSQ policy (b, Q) with an assignment in IR to each of the n parameters G.
Let Pri (9) be the probability that an execution of a policy क reaches a state in G within timesteps. BSQ policy (6, 8) is said to be a solution to gPOMDP with goal and horizon iff Pr=-1 Pr.(0.0)
(g)= 0. The quality of BSQ policy is defined as its expected cost; due to the uni- form cost function in the definition of gPOMDPs, the expected cost of a BSQ policy is the ex- pected time taken to reach a goal state. Formally, the expected cost of a BSQ policy T(b 8) is Er H)- ΣH t Prç.:[m(b, R),, where H is the horizon and Prg.[[ (b 0) is the probability of policy (b, P) reaching a goal state for the first time timestep t. Thus, given a gPOMDP P, with goal G. and parameterized BSQ policy (b, +), the objective is to compute:
(bb,)) argmin F.x (0: H) H- (g) > 0}
4 Formal Analysis
Our main theoretical result is that the continuous space of policy parameters is, in fact, partitioned into finitely many constant-valued convex sets. This insight allows the development scalable algorithms for computing low-cost user-aligned policies. We introduce formal concepts and key steps in proving this result here; complete proofs for all results are available in the Appendix. We begin with the notion of strategy trees to conceptualize the search process for BSQ policies.
4.1 Strategy Trees
Every parameterized BSQ policy rb, ②) and gPOMDP P defines a strategy tree (e.g., Fig. (a)) that captures the possible decisions at each execution step. Intuitively, the tree starts at belief node representing the initial belief state. Outgoing edges from belief nodes represent rule selection in r θ), resulting in action nodes. Outgoing edges from action nodes represent possible observations,

---

82
7:
73
repair(rolod)
wails
1
0.75
(7.3)
(T.F)
(F,3)
(F.F)
(T.
(F.T))
(F.P)
Ra Kadaadufa
35
0.50
4
4
4
4
4
4
En
la
lu
fit
fu
(a) Spaceship repair H-2 strategy tree (red and blue correlate to two distinct braids)
0.403.066
(b) Partitioned parameter space
Figure 2: (a) Strategy tree created from parameterized BSQ policy in Fig. [ Spaceship Repair gPOMDP with horizon of 2. (b) Complete partitions of parameter space with two of the braids highlighted. Error detection sensor accuracy for the robot and ship is 60% and 75%, respectively.
leading to belief nodes representing the corresponding updated belief. If the tree is truncated at horizon H, each leaf represents the outcome of a unique trajectory of rules from ((b, +) and observations.
Each belief node represents a belief state that can be calculated using the rule-observation trajectory leading to that node. A labeling function / VB U VA - B o maps the set of belief nodes VB to belief states in B and the set of action nodes VA to actions in A. For ease of notation we define D I(v:) for all belief nodes U; E VB and az I(u;) for all action nodes U/ VA.
Definition Let P be a gPOMDP, π (b, θ) be a parameterized BSQ policy for P. and by be the initial belief state. The strategy tree Ta (b,)) is defined as (b,) (V, E') where set V = =VB B VA nodes nodes VB and action nodes VA. whereas. set EB u EA contains edges from belief from EB is defined as (VV,, r, uy E VB, U2 E VA, n(b, Q), and 3T as {(um, O, Un))
contains
nodes to action nodes (E, S VB x Va) and edges from action nodes to belief nodes (E S VA x VB).
047)- En is defined V
Vm (mm VA, Un VB, o O, 3(pp: r = a, Um) E Es; b = bp a, 0)}.
Non-convexity of the expected cost function Each parameterized BSQ policy permits infinitely many BSQ policies, one for each assignment of real values to its parameters. Unfortunately. the expected cost of parameterized BSQ policies is not a convex function of these parameters. Fig [c) shows this with a counterexample using the parameterized BSQ policy from Fig. (b). a horizon of 12, and setting the robot's initial distance from each repair station to 5. This plot was constructed by sampling the expected cost for 251,001 equally-spaced parameter assignments to the Fig. aa) parameterized BSQ policy. (x)"; H) is clearly not convex: the expected cost along the line θ₂
O, 0.25 has two inflection points at O 0.6 and O 0.8. This creates two local minima: + & 0.16 and θ > 0.83 ^ O2 & 0.1. Intuitively, this is due to the short horizon, which causes the optimal strategy to be selecting repair station and traversing This complicates finding good BSQ policies using existing solvers. However, every possible BSQ policy can be associated with set of strategy tree leaves that are reachable under that policy. Thus, for given horizon, there are only finitely many expected costs for BSQ policies for given problem.
regardless of the observations.
The main challenge in computing good BSQ policies is that the of possible BSQ policies with distinct expected costs grows exponentially with the horizon and good BSQ parameters could be distributed arbitrarily in the high-dimensional, continuous space of parameter values. We strategy trees to define groups of leaves called braids, which we will then use to prove that the space of BSQ policy parameters turns
be well-structured in terms of the expected cost function.
Braids We refer to the set of all leaves reachable under a policy (6, 2) as the braid of 0. Due to the mutual exclusivity of rules for every assignment of parameter values to a parameterized BSQ policy, at most, one outgoing edge can be taken from each belief node (as these correspond to the rules and actions). However, the stochasticity of dynamics and observations allows for multiple outgoing edges to be possible from action nodes. E.g., in the strategy tree for the Spaceship Repair problem (Fig. ((ag) leaves & and f cannot both be reachable under a BSQ policy because that would require rules ri and r2 to satisfied at the same belief. However, both e and Es may be reachable under the same BSQ policy since their paths diverge action node. Formally,
5

---

Definition 7. Let H be the horizon, and let T(b, be parameterized BSQ policy for gPOMDP P. The braid of a parameter assignment 0. braidz,n()), is the set of all leaves in strategy tree T=(bb) rooted at the initial belief by that can be reached while executing r(b, F): braid,, (1 = {eH the path to H (r1,01, TH. T.. T2 v2 - ag bj bp (bo, T1, 01, Tt, 0;) and i satisfies v
The unique interval of parameter values where leaf is reachable can be calculated by taking the intersection of the parameter intervals needed to satisfy each rule on the path to that leaf. This is because for any compound BSQ V we can compute the unique interval of parameter values T(D) under which b will satisfy T(V) by substituting each BSQ in Vi with its corresponding inequality:
Lemma 1. Ler v (b; 3) be an n-dimensional compound BSQ. There exists a set of intervals T (VV) = IT s.t. (b; θ) evaluates to true iff G e I(
We can utilize this result to compute the unique interval of parameter values consistent with a braid by taking the intersection of the intervals of each leaf contained in that braid (Def. :):
Definition 8. Let π (b, θ) be parameterized BSQ policy, P be gPOMDP, be be the initial belief state, and H be the horizon. The interval of leaf E, [(f), is defined as the intersection of intervals n& ( ()) of the conditions of each rule r; that occurs in the path that leaf. The interval for a set of leaves L is defined as [[L) = Ne,eL I(f;).
Any leaf or braid with an empty parameter interval does not align with the user's 's requirements. For example, in Fig. 2 note that r1 is the only rule satisfiable if r1 is selected from by and the robot is observed to be broken. Using the Fig. [bb) policy and assuming the sensor accuracy is 60%, picking a rule other than ri implies that 50% likelihood was high enough to fix the robot yet 60% was not, which is contradiction. Removing misaligned leaves and braids prunes the tree.
4.2 BSQ Policies are Piecewise Constant
We now use the concept of braids to prove that the continuous, high-dimensional space of parameter values of a parameterized BSQ policy reduces to a finite set of contiguous, convex partitions with each partition having a constant expected cost. This surprising result implies that although the expected cost of BSQ policies is not a convex function of parameter assignments, optimizing a parameterized BSQ policy requires optimization over a finite set rather than over a continuous space. We first define a notion of similarity over assignments to parameterized BSQ policies that define BSQ policies:
Definition 9. Let π (b, θ) be a parameterized BSQ policy, P be a gPOMDP, and H be the horizon. Two assignments 01, 02 E ① are said to be similar, 01 = 12 iff broid=, (01) = braid H (72).
It is trivial to show =H H is transitive, symmetric, and reflexive, making it an equivalence relation over RT. As such, = defines a partition over the same space:
Theorem 1. Let π (b, θ) be a parameterized BSQ policy, P be a gPOMDP, by be the initial belief state, and H be the horizon. The operator h partitions R
However, this result is not sufficient define the structure of partitions induced in R", which will be required for an efficient optimization algorithm. Based on Sec. [4. we know that leaves whose trajectories diverge due to different rules must not be in the same braid. Furthermore, belief state can only lead to one set of possible observations for an action regardless of the BSQ policy being followed. Intuitively, this prevents braids from being proper subsets of each other, which implies that the parameter intervals for two braids can never have overlapping parameter intervals. This gives us the desired structure for partitions induced in the space of parameter values for parameterized BSQ policies: there are parameter intervals corresponding to distinct braids in the policy tree. In other words, the set of braids partitions the parameter space into contiguous, digessiinni intervals. This can be proved formally and stated as follows:
Theorem 2.
Let (b. θ) be a parameterized BSQ policy, by be the initial belief state, and H be the horizon. Each partition p created by operator = partitioning R"' is the disjoint intervals, p S R. where vo p. braid=, H (7) I. where I is a fixed set of leaves.
Since each partition corresponds to braid and each braid corresponds to a fixed set of leaves, which defines the expected cost for all policies corresponding that braid. all policies defined by partition

---

of the parameter space have constant expected cost. As such, the domain of the expected cost function En (1; H) for gPOMDP P can be represented as the disjoint intervals of each braid partition. Thus, (0; H) is piecewise constant. The following result formalizes this.
Theorem 3. Let π Tbb ④) be a parameterized BSQ policy, P be a gPOMDP, by be the initial belief state, and H. be the horizon. Each partition created by = H on R has a constant expected cost.
In some situations, the braids that partition the parameter space can calculated closed form (e.g., see the Appendix for partitions for the Spaceship Repair problem). The next section develops general approach for computing the braids and intervals corresponding to parameterized BSQ policy, for evaluating the expected cost for each such partition, and for optimizing over these partitions.
5 Partition Refinement Search
In this section, we present a novel algorithm for op- timizing the parameters for a parameterized BSQ policy using the theory of braids developed above.
Algorithm Partition Refinement Search (PRS)
1: Inputs: gPOMDP P, parameterized BSQ
The Partition Refinement Search (PRS) algorithm (Algo.[) constructs the set of partitions using hier- archical partition selection and refinement, where a partition is selected to be refined, a leaf that can occur in that partition is sampled and evalu- ated, and the partitions are refined to isolate the interval the braid corresponding to the sample. The hypothesized optimal partition is tracked and returned as the final result after timeout.
policy π (b, +), horizon /
2: Output: Minimum cost partition and its ex-
pected cost <Popt. E[Poptl>
3: Pinit - Xee De
4: X KDimitt 00) }. X (Pinit, o0)
while (Time do
6:
(p. Elpl> - Select Partiiinot
7:
0, ~ UniformSSmple(p))
8:
f, E - Rollout (b,, H)
PRS constructs the first parameter space interval as the domain of all possible parameter values (line 3). This is set as the initial hypothesized optimal partition (line 4). each iteration, a par- tition p is selected using approaches discussed in Sec. (lines 6). leaf é is sampled from by uniformly sampling pa- rameter value H from p's parameter intervals and performing rollouts from the initial belief state to a reachable leaf using the BSQ policy (b, T) (lines 7 and 8). The sampled leaf is used refine partition P using the insight braids cannot overlap Sec..4.2) If there exists a subinterval of p where f does not occur, a new partition for this subinterval constructed containing p's previous leaves and expected cost (line 9). The remaining portion of where l can occur, is used to construct a partition with an updated expected cost representing p's previous leaves and (line 10). The hypothesized optimal partition is then updated (line 11).
9:
X - (XVs,, (x))),Epp)) u (pII(E), Elpl>
10:
X - -uuup I(8), Elol Es)
11:
X Xopt arg min F(p]]
(oDexx
12: end while
13: return Xopt
PRS converges to the true optimal BSQ policies in the limit:
Theorem Let (b. θ) be parameterized BSQ policy, P be a gPOMDP, by the initial belief state, and H be the horizon. The likelihood of the Partition Refinement Search algorithm returning the optimal parameter interval converges to one in the limit of infinite samples.
Complexity analysis While the theoretical space and time complexity are linear in the number of leaves, due to PRS grouping leaves from the strategy tree (Def. there good reason expect better performance in practice. As discussed in Sec. 4.1 strategy trees can get pruned with the removal of branches and leaves that do not align with the user's requirements. For example, in the Spaceship Repair problem using the Fig. [ parameterizeed BSQ policy, third of the possible leaves are pruned at a horizon of two, and the pruning becomes even more significant for longer horizons. Additionally, empirical results suggest that rules earlier in rule-observation trajectories are more important in dictating the partitions. Furthermore, selecting and refining partitions can be performed in parallel, further improving performance.
7

---

6 Partition Selection Approaches
We explored multiple partition selection approaches with a multiprocessing version of PRS. Each approach used the same dynamic exploration rate e, that diminished over time. Each thread managed a subset of partitions X' = X and updated a global hypothetical optimal partition. Additionally, we warm start PRS by randomly selecting 20 points in the parameter search space and evaluating them 40 times to build an initial set of partitions. Also, partitions that have lower expected cost than the hypothesize optimal are sampled up to 40 before updating the hypothesize optimal. In this paper, we focus on three selection approaches and discuss two others in the Appendix.
Epsilon Greedy (PRS-Epsilon) We explore e, percent of the time by uniformly sampling Up and checking if s & Cr. If we are exploring, we uniformly at random select a partition from X'. Otherwise, the partition with minimum expected cost, arg (p. [[p]. is selected.
Boltzmann Exploration (PRS-Bolt) Partitions are selected in weighted random fashion with the probability of selecting partition p a x exp( [[p]/er) with being the normalization factor.
Local Thompson Sampling (PRS-Local) Each thread treats the problem as a multi-armed bandit problem where the expected cost for the next sample from each partition is simulated using M( о.) with μe and de being the partition's 'sso mean and standard deviation, respectively. The partition with the lowest estimated expected cost is selected.
7 Empirical Results
We created implementation of PRS and evaluated it four challenging risk-averse problems. Complete source code is available in the supplementary material. We describe the problems and user preferences here; further details, including parameterized BSQ policy, can be found in the Appendix.
Lane merger (LM) In this problem, an autonomous vehicle driving on a two-lane road must switch lanes safely before reaching a lane merger. However, there is currently a car in the other lane that the agent does not know the location or speed of. Switching lanes too close to this car risks a severe accident. The autonomous vehicle has noisy detection system that returns whether a vehicle is located in regions around the car. The user's preference is: If there's 's a high likelihood of safely switching lanes, do so. If there is high likelihood of the other car being in close proximity and it is possible to slow down, slow down. Otherwise, keep going.
Spaceship repair (SR) This is modified version of the running example with parameterized BSQ policy Fig. [bb). The robots start 7 steps and steps away from the robot and ship repair stations, respectively. Additionally, the robot's sensor is 75% accurate at detecting errors with the robot and only 55% for the ship. With the short horizon = 12, this results in the parameter space being not convex with multiple local minimums with differing expected costs.
Graph rock sample (GRS) We modified the classic RockSample(n, k) problem (Smith and Simmons 2004] by replacing the grid with a graph with waypoints where some waypoints contain rocks. Additionally, we introduced risk by causing the robot to break beyond repair if it samples a rock not worth sampling. We also categorized the rocks into types, and the rover's 's goal is to bring a sample of each type to the desired location if safe rock for that type exists. This goal requires a longer horizon to reach compared to the other problems. The user's preference is: Evaluating rocks of types not sampled in order Ti....: Tno if the rock has a high likelihood of being safe to sample, go and take sample of it. Else, if the rock has a high likelihood of being safe to sample, gel close enough and scan it. Otherwise, move towards the exit if no rocks are worth sampling or scanning.
Store visit (SV) This problem is based on the partially observable OpenStreetMap problem in Liu al. 202T]) A robot located in city where some locations are unsafe (e.g., construction, traffic). which can terminally damage the robot. The robot is initially uncertain of its location but it can scan its surroundings to determine its general location. The agent traverses the city and can visit the closest building. The goal is to visit a bank and then a store. This problem features nuanced parameterized BSQ policy: If you are significantly unsure of your current location, scan the area. If you have visited a bank, do the following to visit a store; otherwise, do it to visit bunk. If you are sufficiently sure the current location has the building you are looking for, visit it. Otherwise, move towards where you think that building is while avoiding unsafe locations. If all else fails, scan the current area.
8

---

PRS (Ours)
Nelder-Mead
Particle Swarm
Lane Merger
Graph Rock Sample Ser...paaeesppp Repair
Store Visit
% Goal Achievement Expected Cost
30
40
10.0
10.0
60
30
7.5
20
40
20
5.0
10
20
10
2.5
0
0.0
100
100
100
100
75
50
50
50
50
25
25
25
25
0
0
40
80
120
0
40
80
120
0
10
20
30
50
100
150
200
Time (Seconds)
Figure 3: Empirical results evaluating the hypothesized optimal partition performance tracked. Equally spaced samples across PRS evaluation time are taken while a sample taken each iteration of Nelder-Meat and Particle Swarm. The enror displayed is the standard deviation error.
7.1 Baselines
We evaluated PRS against three different types of baselines.
RCompliant Select random parameter values uniformly at random from the parameter space produce user-aligned policies.
Hyperparamter optimization algorithms To measure the benefits of PRS against existing hyper- parameter optimization algorithms, we implemented both Nelder-Mead [Nelder and Mead 1965] and Particle Swarm [Knnedy and Eberhart 1995). The expected cost of parameter space point for parameterized BSQ policy R, was computed by averaging 1,000 parallel runs of the policy π ((6; Ø). For Nelder-Mcad optimization, we used simplex that had vertices numbering one more than the number parameters in the parameterized BSQ policy being optimized. We warm start by initially evaluating a 100 random points to construct the initial simplex using the best- best-performing points. For Particle Swarm optimization, 10 particles were used with the location and momentum of each particle clipped to the search space. The coefficients changed based on steps since the last improvement.
Unconstrained POMDP solvers To measure the differences between BSQ policies and uncon- strained POMDP solvers, we implemented variations of our problems into POMDPX and solved them with DESPOT (Somani et al. 2013) and SARSOP [Kurniawati al. 2009 for 1,000 evaluation runs. To measure whether an observattoeiotioon trajectory produced with these solvers aligns with the user's s requirements, we check if there exist parameter values where policy x <b;; i) could produce that trajectory. We use this evaluate the solutions produced.
7.2 Analysis of Results
For each problem, we evaluated each baseline and PRS variant ten times. The horizon was 12 for Spaceship Repair and 100 for the other problems. The timeout for PRS was set on a problem-by- problem basis. Timeout for Nelder-Men expected cost is equal to the horizon due to the default cost function. The performance of each PRS partition selection approach can be found in Figure and the quality of solutions over time compared to the baselines are shown in Figure 3
and Particle Swarm was one hour. Note that the highest
Partition selection approach evaluations PRS partition selection approaches converged similar quality policy. The only difference was the time taken with approaches that did not rely on the standard deviation converging faster due there being a lower standard deviation near the optimal solution, causing selection approaches that used the standard deviation to explore the wrong partitions. We use PRS-Bolt as a representative when comparing against the other baselines.

---

PRS solution quality PRS produced a higher- quality policy compared to the ones produced by RCompliant. For Spaceship Repair, the simplest problem solved on the shortest horizon, poli- cies produced by PRS- Bolt had a 15.68% lower expected cost and 3.47% higher goal achieve- ment rate. For the other problems, policies pro- duced by RCompliant had more than triple the expected cost and achieved only half the success rate on both Graph Rock Sample and Store Visit. These results demonstrate that optimizing BSQ parameter values has a significant impact on the performance of user-aligned policies.
PRS-Bolt
PRS-Epsilon
PRS-Local
% Goal Achievement
100
Expected Cost
20-
15-
50
10-
LM
GRS
SR
SV
LM
GRS
SR
SV
Domains
Figure 4: Results for PRS with different partition
selection approaches from Section 6
Hyperparameter optimization evaluation Compared to traditional hyperparameter optimization algorithms, PRS always found the user-aligned policy with the lowest expected cost with little performance deviation. This is due to Nelder-Mead and Particle Swarm struggling to optimize a non- convex piecewise-constan function using noisy data, resulting in known problems with local-search algorithms: problems of getting stuck in sub-optimal local minima and exploring the incorrect space. Additionally, PRS converged first since it is more sample-efficient It is computationally expensive to update the belief state, resulting in poor-quality solutions being more expensive to evaluate due to taking longer reach the goal. PRS only requires couple of evaluations before spending the computational resources on more promising areas.
An interesting result is that, in Spaceship Repair, solutions found by Nelder-Mead and Particle Swarm both had a 7.73% higher expected cost and 18.31% higher goal achievement rate than the PRS-Eppilon solutions. There is likely high negative correlation between the expected cost and goal achievement rate. PRS is better at optimizing the stated objective of minimizing the expected cost.
Unconstrained solver evaluation Without guiding from the parameterized BSQ policies, DESPOT and SARSOP struggled with this set of problems. SARSOP failed to converge to policy due the long problem horizon. DESPOT could not run on Lane Merger, which had the largest state space and branching factor. DESPOT also only achieved the goal 0.5% of the time on Graph Rock Sample. DESPOT achieved a lower expected cost of 20.0% and 13.3% on variations of Spaceship Repair and Store Visit, respectively. However, DESPOT's policy never aligned with the user's requirements on Store Visit and only 7.3% of the time on Spaceship Repair. This indicates that the BSQ framework offers new approach for expressing both domain knowledge and user requirements.
Conclusion
We presented the BSQ policy framework for expressing users' requirements over the belief state in partially observable settings for computing user-aligned agent behavior. We performed a formal analysis of these policies, proving that the parameter value space introduced in the parameterized BSQ policies can be partitioned, resulting in parameterized BSQ policies being optimizable through a hierarchical optimization paradigm. We introduced the probabilistically complete Partition Refine- ment Search algorithm to perform this optimization. Our empirical results show that it converges to the optimal user-aligned policy quicker and more consistently than existing approaches. Results indicate that parameterized BSQ policies provide a promising approach for solving diverse real-world problems requiring user alignment.
Limitations and future work There are many interesting directions for future work based on the current BSQ policy framework. BSQ representations can be made more expressive by allowing deterministic functions, which would not compromise the presented theoretical results. Furthermore, there exists a natural extension of this work into finite memory controllers that allows temporally extended requirements to be encoded with the same theoretical results. Relaxing the constraints on mapping each belief state to a single action would expand the usability. For more complex problems, a belief-state approximation approach would be required, but the underlying strategy tree discussed in this work would remain mostly unchanged. Another interesting research direction is to develop methods that help users express their requirements in the BSQ framework.
10

---

Acknowledgments and Disclosure of Funding
This work was supported in part by ONR grant N000142312416 and NSF grant IIS 1942856.
References
Rati Devidze, Goran Radanovic, Parameswaran Kamalaruban, and Adish Singla. Explicable reward design for reinforcement learning agents. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 20- Curran Associates, Inc., 2021. URL wtw.hhttps:tt htttps:/pproceediiiiii wwwr:gs.......p....... cc/ paper http:///w..aa.ee//////////////// htt.:///000..........e.eeeeee... sapaprrppfff
Dhawal Gupta, Yash Chandak, Scott Jordan, Philip S. Thomas, and Bruno C. da Silva. Behavior aligmment via reward function optimization. In A. Oh, T. Nau- mann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neu- ral Information Processing Systems, volume 36, pages 52759-52791. Curran Associates, Inc., 2023. URL https::/pprceeeeeeeeee iewpoeeeeddinnn.e.ner........epe neurips wwwr.ps..ccpppeeaeee.. cw/paper.pp.pc..c. fww.sllllppppe pttppppppe///////////// Paper Ponereoeee pdf
Serena Booth, W. Bradley Knox, Julie Shah, Scott Niekum, Peter Stone, and Alessandro Allievi. The perils of trial-and-error reward design: Misdesign through overfitting and invalid task specifications. Proceedings the AAAI Conference Artificial Intelligence, 3765):520055929, Jun. 2023. doi: 10. N0.1660/aai...3755.555555 URL attpss//ojjs aaai. org/indee. phpp Dhtp/AAAI/aticle//rte 25733
Tom Everitt and Marcus Hutter. Avoiding wireheading with value reinforcement learning. In Artificial General Intelligence: 9th International Conference, AGI 2016, New York, NY, USA, July 16-19, 2016, Proceedings 9, pages 12-22. Springer, 2016.
Jorge A Baier, Christian Fritz, and Sheila A Mcllraith. Exploiting procedural domain control knowledge in state-of-the-art planners. In ICAPS, pages 26-33, 2007.
Javier Segovia Aguas, Sergio Jiménez Celorrio, and Anders Jonsson. Generalized planning with pro- cedural domain control knowledge. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 26, pages 285-293 2016
Cameron Voloshin, Hoang Le, Swarat Chaudhuri, and Yisong Yue. Policy optimization with linear temporal logic constraints. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 17690-17702. Cur- Associates, Inc., 2022. URL httpp:::/proceeednnggg neurips 0022/ffl.00060004788883377788883 Paper- www.erenneeecepccoooecee
Rodrigo Toro Icarte, Toryn Q Klassen, Richard Valenzano, and Sheila A Mcllraith. Teaching multiple tasks to an rl agent using Itl. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pages 452 461, 2018.
Pashootan Vaezipoor, Andrew Li, Rodrigo A Toro Icarte, and Sheila A. Mcilraith. Ltl2action: Generalizing Itl instructions for multi-task rl In Marina Meila and Tong Zhang. editors, Proceedings of the 38th International Conference on Machine Learning. volume 139 of Pro- ceedings of Machine Learning Research, pages 10597-10508. PMLR, 18-24 Jul 2021. URL
mlr wwt.sp/ess/eeeeeeeeeeeee http:///1////22ooor2...aa.. html
Jason Liu, Eric Rosen, Suchen Zheng, Stefanie Tellex, and George Konidaris. Leveraging temporal structure in safety-critical task specifications for pomdp planning. 2021.
Mathieu Tuli, Andrew Li, Pashootan Vaezipoor, Toryn Klassen, Scott Sanner, and Sheila Mcllraith.
Learning to follow instructions in text-based games. Advances in Neural Information Processing Systems, 35:19441-19455. 2022.
Mohamadreza Ahmadi, Rangoli Sharan, and Joel Burdick. Stochastic finite state control of pomdps with ltl specifications. arXiv preprint arXiv:0001.07679, 2020.
11

---

Giulio Mazzi, Alberto Castellini, and Alessandro Farinelli. Rule-based shielding for partially observable monte-carlo planning. Proceedings of the International Conference on Automated Planning and Scheduling, volume 31, pages 243-251, 2021.
Giulio Mazzi, Daniele Meli, Alberto Castellini, and Alessandro Farinelli. Learning logic specifications for soft policy guidance in pomcp. arXiv preprint arXiv:2303.09172, 2023.
Siddharth Srivastava, Xiang Cheng, Stuart Russell, and Avi Pfeffer. First-order open-universe pomdps: Formulation and algorithms. Technical report, Technical report, 2ECS-2003-243, EECS Department, UC Berkeley, 2012.
Leslie Pack Kaelbling, Michael L Littman, and Anthony R Cassandra. Planning and acting in partially observable stochastic domains. Artificial intelligence, 101(1-2)99--34, 1998.
Richard D Smallwood and Edward J Sondik. The optimal control of partially observable markov 1973.
processes over a finite horizon. Operations research,
David Silver and Joel Veness. Monte-carie planning in large pomdps. In J. Lafferty, C. Williams, Shawe-Taylor, R. Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 23. Curran Associates, Inc., 2010. URL /tpp: neurips cc/ pdf
paper_ faper_files/
Adhiraj Somani, Nan Ye, David Hsu, and Wee Sun Lee. Despot: Online pomdp planning with regularization. Advances in neural information processing systems, 26, 2013.
Moran Barenboim and Vadim Indelman. Online pomdp planning with anytime deterministic guar- antees. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36. pages sociates, Inc., 2023. URL http:atttts/pprrceeedinng newriss cc/ paper files/eeeee/ wwwesilepppseeeee pptps//ppprrr/2//.////// file/fc6bd0eeff 04500000000005555507777777666111 wwwee-aooeeeeeeeeeeaa pdf
Curran As-
Michael Lim, Tyler J Becker, Mykel Kochenderfer, Claire J Tomlin, and Zachary N Sunberg. Optimality guarantees for particle belief approximation of pomdps. Journal of Artificial Intelligence Research, 77:1591-16366 2023.
Karl Astrom et al. Optimal control of markov decision processes with incomplete state estimation. Journal of mathematical analysis and applications, 10(1):174-205, 1965.
Trey Smith and Reid Simmons. Heuristic search value iteration for pomdps. In Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence, UAI '04, page 520-527, Arlington, Virginia, USA, 2004. AUAI Press. ISBN 0974903906.
John Nelder and Roger Mead, simplex method for function minimization. The computer journal, 7(4):308-3) -33,, 1965.
James Kennedy and Russell Eberhart. Particle swarm optimization. In Proceedings of ICNN'95- international conference on neural networks, volume 4, pages 1942-1948. ieee, 1995.
Hanna Kurniawati, David Hsu, and Wee Sun Lee. Sarsop: Efficient point-based pomdp planning by approximating optimally reachable belief spaces. 2009.
12

---

A Appendix Organization
The Appendix is organized as follows. Appendix B contains the proofs for showing the expected cost function is piecewise constant. Appendix contains the proof that PRS is probabilistically complete. Appendix D discusses the evaluation problems and provides the parameterized BSQ policies used. Appendix T discussed additional implementation details of both Nelder- Mead and Particle Swarm. Appendix discusses two additional partition selection approaches we tested and provides additional analysis of our results. Appendix G discusses the experimental setup and computational cost of our experiments. Appendix H contains the calculated closed-foo form solution of the partitionn for the Spaceship Repair problem. Appendix pereendixxdisse discusses the broader impacts of our work. Finally, Appendix g discusses additional limitations not discussed in the main paper.
B Lemmas and Proofs From Formal Analysis [Section 3
In this section, we provide the formal proofs for Lemma | Theorem T Theorem 2 and Theorem from Section 3] where we proved that braids partition the parameter space resulting in the expected cost function of a parameterized BSQ policy w.n. its parameter being piecewise constant. We define and prove Lemmas
3
4
and S
in this section for building these proofs.
First, we prove that the similarity operator = for braids (Def. () has the properties of being reflexive, symmetric, and transitive. As such, = defines an equivalence relation over the n-dimensional parameter space IR,, meaning defines a partition over I.."
Theorem 1.
Let T(, 0) be a parameterized BSQ policy, P be a gPOMDP by be the initial belief state, and H be the horizon. The operator = partitions R"
Proof. Let T R" be n-parameter values and be the horizon. By way of contradiction, let's assume that 0 is not similar itself, 7 V. This would mean that braidn,1 (7) braidn,2( As such, there must exist a leaf f, which is one but not the other braid. Note that represents a unique rule-observation trajectory (ri, 01, .... TH; : 0. Additionally, for f to be in one of these braids would need be true that Vi, (bb ?) must be satisfied, where by hp* (bo,, 01,-..;' 0;)
(Def. However, note that this would hold true for the other braid as well, making it a contradiction for l to be exclusive in either braid ( or braidH,2( As such, must be similar to itself meaning the similarity property holds.
Let 01, 02 J3 I= where 0, = 82 and D2 = Uz. Therefore, braidz H (F1) = braidx. (72) and braid,, (02) = braid,, (T))) (Def 7 Using substitution, braid,, (D,) = braid H (J)) meaning 11 = Øz. As such, the transitive property holds.
Due to set equality being symmetric, the symmetric property holds. Thus, the operator = is an equivalence relation over IR" causing и to define partition over R
For compound BSQs V, we now prove that there exist unique intervals of the parameter space where is satisfied that we can calculate.
Lemma 1. Let (b: +) be n-dimensional compound BSQ. There exists set of intervals I(V) S RD s.I. T (b; θ) evaluates true iff G T(
Proof. Let P be a gPOMDP, be belief state, O E R be parameter, be comparison operator, and yp be a first-order logic formula composed of functions from P. There exist two possible forms for BSQ (Def. 2). Let Ap(b; yp, (p, o, +) = Pr[p]] o O. Note that Pr[sp]o evaluates into the probability of sp being satisfied in a belief state Therefore, we can simplify Ap yp, o, +) to po Q where p E [O, 1]. meaning this type of BSQ simplifies to inequality. Now, let (p y2, o, θ) Pr[ye, == 1 where o is composed of θ and fully observable functions in P. We assume that e cannot be used as a function parameter, meaning that it must be operand of relational operator in s. Since the functions are fully observable, they can be evaluated for b, leaving the inequalities involving θ to dictate whether yp is satisfied. Thereby, BSQs evaluate inequalities involving O.
compound BSQ V comprises conjunctionssdiiijunttiii of BSQs by Definition 3 By substituting each BSQ with its incqualities, we can calculate the interval of v, [(V).
13

---

Let us assume that θ E [V).. By way of contradiction, let us assume that θ does not satisfy V. If v is a conjunction of BSQs, there exists at least one BSQ that is not satisfied by +. If v is a disjunction, all the BSQs are unsatisfied by O. However, this would mean that θ cannot satisfy the inequalities from these BSQs, so θ cannot be T(V) since T(V) is constructed using the regions of the parameter space that satisfy the necessary BSQs, which is a contradiction.
Conversely, let us assume that O satisfies V. This means one or all the BSQs are satisfied by O depending on if V is a conjunction or disjunction. If e was not in (V), there could not exist a set of BSQs satisfied for V to be satisfied.
Thus, for a belief state b, a p-rammeter compound BSQ has an interval in the parameter space ( s.t. AA R,, θ (V) iff ( +) evaluates true.
As mentioned in Section 3 braids cannot be proper subsets of each other, which we will now prove in Lemma [ As high-level intuition, removing leaf can only occur if rule along that leaf's s mule-observation trajectory is not satisfied, which would mean another rule must be satisfied since Def. Def. guarrattees coverage of the belief state and parameter space. This results in at least one leaf being added to a braid that removes this first leaf, making this new braid not a subset of the other one.
Lemma 2. Let TT(, b) be a parameterized BSQ policy, P be a gPOMDP, by be the initial belief. and H be the horizon. v01, 02 E RR, if broida, H (81) = braidz, (iiidx,H(b) (22) then braidz, HH (01) braidn, H (82).
Proof. Assume there exists 01, D2 E R" s.t. braidz,Ht H (01) c braidx H (82) implying there exists leaf la where Eg E braid,, (T2) braids,
Let é E braida, H (01) be the leaf with the largest rul-oobservation trajectory to prefix shared with & before differing. The trajectory for l can be expressed TuTI where Tı the remaining trajectory for reaching 41 Similarly, the trajectory for εg can be expressed as ToT2- Note To represents the actions executed and observations observed from the initial belief state till right before the diversion resulting in the the belief state b being the same for both leaves up to this point.
If the first element in Ti and T2 is a rule, note that braidg, H (,,,H(1))) (12) must also contain L1 This would imply that T (b; F2) is not mutually exclusive since two rules can occur in one element of the strategy tree. This is contradiction by Def. 4 If the first element in Ti and T2 is an observation, different observations occurred after executing the last shared action in 7D- Due to the observation model and sharing the belief state b this point, both observations must be possible. This means leaf in braid,, 1s (71) must have larger shared trajectory prefix than l,, which is contradiction. Thus, braids cannot be strict subsets of each other.
Since braids cannot be proper subsets of each other, can now prove that both braids must contain leaves the other does not have. In turn, this prevents the interval of braids from overlapping. Note that the interval of braid can be calculated by taking the intersections of the intervals of each leaf contained in that braid (Def. 8 [(braid H (7)) (kebraid,, I(e).
Lemma 3. Let (b, Q) be parameterized BSQ policy, P be gPOMDP, by be the initial belief, and H be the horizon. 401, D2 E RR",, if braidd.. (71) n braid=,u( + Ø and braid (T.) + bruid H (02) then I (braidx HI (0))) I(braid, H (02) Ø.
Proof. Let T2 D2 R" where braidr,H1 braid (T2) * Ø and braidz. H (7,) #
braid HI (F2). Both braids cannot be proper subsets (Lemma 2 meaning both braids must contain leaves that are not in the other braid: braid H 12) (raid=. braid,, 1I (i: (brrdddd, ye Ø.
# and
By Definition 8 the interval of a braid is the conjunction of the intervals of each leaf it contains. Using the associative and commutative properties, this can be rewritten as the conjunction of two sets: the interval of leaves shared and the interval of leaves not.
I(braidz, H (T.)) [(braid,, H (Tr) n braid H (72)) I(braid,, H (7z) (bba)drrr (Fz) I lbbradd, n (J2)) [[braid, H (7i) o braidd, H (22)) n 1 (braid, H (02) (braid, H (T1)
14

---

A braid's interval must exclude these unreachable leaves since braid is all reachable leaves 7 As such, [[braid (82)) must not overlap with [(braidz.I1() braddz, Hr (Ø2) and I (braidx, (((aidz,((V))) must not overlap with 1 (braida,, (82))braixxx, (V1). However, due to the con- junctions of intervals, I(braidx, n (0)) s [(braidz, n1 ( (bbrddd (82) and I(braida, (#2) S I (braidd (02) Abbaid,, H (0)). Thus, the intervals of I (braid,, H (0) and I [braid, H (82) cannot overlap.
The fact that two braids cannot have overlapping intervals allows us to prove that the sets of parameter values are similar iff they share the same braid interval.
Lemma 4. V0 82 RR" 01 =# 12 iff ((baidd, (02)) = I(braidz, (82)).
Proof. Let 17 = G2. meaning braidg.H (. braid,, H (z2) L where L is the set of reachable leaves (Defs. and 9 By Definition 8 the interval of a set of leaves is the intersection of each leaf contained in the set, meaning both braids must have the same interval.
Let I(braid=,H (#.)) = I(braid,, H (72)). By way of contradiction, assume braid=, (v1) * broid=, (02). By Lemma this would mean I(braida, nI (Q1) e ((b)) 8, which is contradiction. Thus, braid(O,) 02)) meaning d1 = d2 (Def.
We can now prove that partitions produced by = partitioning the parameter space IR each represent a single braid, causing each partition to have a disjoint interval where a constant set of leaves is reachable.
Theorem 2.
Let (b, θ) be a parameterized BSQ policy, be be the initial belief state, and H be the horizon. Each partition created by operator = partitioning R² is the disjoint intervals, S IR" where VO p, braid,, 1I (0) = L where L is a fixed set of leaves.
Proof. Let be a partition produced by = partitioning the parameter space R". Note that this means that parameter value sets contained in must be similar (Def. 9): 101, 82 E p, 01 = 82. As such, all parameter values have the same braid (Def. [7,, meaning there exists
leaves L that are
reachable in By 8 this set's interval must be I [L) = N Ntger. / (LH). By Lemma 3 the interval of other braids cannot overlap with (L). Also, there are no proper subsets (Lemma meaning that no other braid can occur in I()) making disjoint.
By Def.8 (TI.) must be contained in due to all parameter value sets in [(I.) having the same braid of L leaves. If contained parameter value sets not in [[)), this would imply there exists outside of [L) where just the leaves in L are reachable, which is contradiction due to [LL) being the only interval space where all the leaves of L are reachable. Meaning the interval of is actually (L).
Thus, each partition represents disjoint interval where only all leaves in L are reachable.
Due to the braid intervals not overlapping, we can prove that parameter value sets contained in that braid's interval must have a constant expected cost.
Lemma S. Let T(b, be a parameterized BSQ policy and H be the horizon. Vi, R V82, Og ((brad(())) E. (02; H) = Exx (03(03;1 (1).
Proof. Let J2, D3 e [(braid,, (0 where 1T R is a tuple of parameters. Note that braid (.)) (3))
braid U2)) due there being no strict subsets (Lemma 2 and leaves in d2 and 03 would have to be reachable in U. Each braid represents policy tree (Def. 5 and the expected cost is based on the probability distribution of leaves in the braid. Since both dh and d3 represent the same policy tree, they must have identical expected cost values.
It is now trivial to show that each partition represents a disjoint interval of the parameter space where the expected cost is constant.
Theorem 3. Let π (b, θ) be a parameterized BSQ policy, P be a gPOMDP, by be the initial belief state, and H be the horizon. Each partition created by и I2'h has a constant expected cost.
15

---

Proof. Let p be a partition created by partitioning I with # By Theorem 2. all parameter value sets in the disjoint interval of p must have the same braid. As such, by Lemma the expected cost constant for all the parameter sets. Thus, the disjoint interval of each partition must have a constant expected cost.
C Proofs For Partition Refinement Search [Section 5
In this section, we provide the formal proof for Theorem proving that the Partition Refinement Search algorithm introduced Section ilis probabilistically complete. We define and prove Lemmas 7 and for building this proof.
When PRS refines a partition p using a leaf e, it can produce up to two possible partitions: a partition for P where É is reachable and partition for where E is not (if it exists). We now show that this process prevents empty partitions.
Lemma 6. Let Thb Q) be a parameterized BSQ policy, P be gPOMDP, bo be the initial belief state, and H be the horizon. For each partition p constructed by Partition Refinement Search, p 2.
Proof. Let p I be partition constructed by PRS. Since PRS creates partitions based on whether sampled leaves are included or excluded, let L, be the leaves PRS included in partition p and Le be the leaves excluded. Therefore,
I(L, [(L.)
By way of contradiction, let p Ø. There two cases where this could occur: (1) excluding leaf & caused م = Ø or (2) including & caused p = Ø. For case (1), we explicitly do not add partitions excluding the leaf results in an empty interval, meaning this cannot happen. For case (2), this implies that there exists previous partition Po where sampling leaf to resulted in the partition constructed from po including to creating p where p = Ø, Due to ég being uniformly sampled from po. to must be reachable in Po meaning Po n I (fo) # Ø. However, line 10 of Algo. calculates the interval of as Po on I (fo) meaning p + Ø, which a contradiction. Thus, all partitions must be not empty. C
A critical property of PRS is that each partition constructed converges to represent a single braid.
Lemma 7. Let (b, b) be a parameterized BSQ policy, P be gPOMDP, by be the initial belief state, and be the horizon. Let p be a partition constructed by Partition Refinement Search. If all leaves reachable in p S RR have been sampled, V0 p. I(bradd H (0)) =
Proof. Let p I. be partition constructed by PRS. Let I.p [f1, .... Cn) be the n-sampled unique leaves for p. Let all leaves reachable from p be sampled, VE, L, [30 p, l E braid H (?)].
Due to p * Ø (Lemma and parameterized BSQ policies covering R.'h (Def. 4. there must exist a non-empty set of leaves L reachable within p. Since all leaves sampled, we know that L S Lp- However, there cannot be proper subsets (Lemma(2) meaning L L= Lp. This means that the interval of p must also equal the interval of leaves I (L). Thus, p must represent braid.
Since partitions are constructed by including/excluding sampled leaves hierarchically, we can prove that this makes each partition represent unique braid.
Lemma 8. Let (b, θ) be a parameterized BSQ policy, P be a gPOMDP, by be the initial belief state, and H be the horizon. Let Pl, P2 = Th" be partitions constructed by Partition Refinement Search. If all leaves reachable in p1 and P2 have been sampled, V0 E P1, V02 E Pt, braid H (81) # bruidz, (82).
Proof. Let Pl. P2 S R be two different partitions constructed by PRS. Note that the PRS partitions In by refining one partition using leaf into two by explicitly including / I(e) in one partition and excluding I(E) in the other (Algorithm D.. Meaning P1 and pz cannot overlap.
Since both partitions represent a possible non-empty braid (Lemma there exists set of leaves reachable in both partitions. However, by the partition construction process, there must exist at least one leaf included in one but excluded in the other. Due to there being no interval overlap between braids, two different braids must be reachable in each partition (Lemma[2). Thus, all partitions must represent unique braid.
D
16

---

Using the property that each partition in PRS represents unique braid, we can now prove that PRS probabilistically complete.
Theorem 4. Let (b, )) be parameterized BSQ policy, P be a gPOMDP. bo the initial belief state, and H be the horizon. The likelihood of the Partition Refinement Search algorithm returning the optimal parameter interval converges to one in the limit of infinite samples.
Proof. Note that gPOMDPs have a finite set of observations and finite horizon [De and param- eterized BSQ policies have finite number of rules (Def. As such, there exists a finite number of unique rule-observation trajectories in the strategy tree ( Therefore, there exists a finite number of leaves due to each leaf having a unique rule-observation trajectory. This results in there only being a finite set of braids being all possible combinations of reachable leaves (Def.) 77. Since each partition represents unique braid (Lemma8). the number of partitions must be finite.
p S R" be partition constructed by PRS that not equivalent a braid. By Lemma 7 this means there exists leaf reachable in p that has not been sampled yet. This also means there must exist a non-empty interval p n (() where sampling from p can reach E. Due uniform sampling selecting parameter values when sampling a leaf for refining the partition (line 7 of Algorithm[]] the probability of selecting a parameter value that could sample E can be calculated as poI(0) Pr(I(()lp)
Note that l represents unique rule-observation trajectory (1,,01, .......... HH 04 Note the probability of an observation o being observed in belief state b after action a is executed is Pr(olb, a) E. ( a. 0) Σ, T(s, a, s' (.)( Meaning that the probability of reaching & during rollout is Pr(() = 11; (r( where b; = bp* (bo, T1, 01, ... Fi, 0,). Since we know that is reachable, Pr(() > 0.
We assume that partition selection approaches discussed in Section have a non-zero probability of refining any partition. Let Pr(p) be the probability of being selected. This means that in any refinement step, the probability of sampling leaf É is being greater than zero, the probability of any non-sampled Icaf being sampled must be greater than zero. Therefore, with enough refinement steps, all the leaves will be sampled since there is only a finite number of leaves. Thus, the set of partitions will be refined to the set of braids the number of samples increases to infinite.
(r())))))(((p) Due to each probability
Note that each partition represents a unique braid (Lemma with set probability distribution of outcomes based on the reachable leaves. Due to a non-zero probability of refining partition Pr(p). the sampled expected cost of partition will converge to the actual expected cost due to the law of large numbers.
Therefore, within finite number of samples, the partitions constructed by PRS will accurately represent the set of braids with an accurate representation of their expected costs. Thus, PRS will find the minimal expected cost partition as the number of samples increases to infinite.
D Evaluation Problem's Belief-State Query Preferences
In this section, we provide the parameterized BSQ policies for the Lane Merger, Graph Rock Sample, and Store Visit problems discussed in Section To do this, we first describe the functions that compose each problem's 's states and actions. We use loops and quantifiers in the parameterized BSQ policies for clarity that can be unrolled on problem-by- brobblle basis.
D.1 Lane Merger
The Lane Merger problem is that there are two lanes, and the agent must merge into the other lane within a certain distance. In this other lane, there is another car whose exact location and speed are unknown. Therefore, there exist two objects in the environment: the agent (agent) and the other car (other). For either object o, the location and speed are tracked using the unary integer functions loc(o) and sp) For actions, the agent can increase their speed (speed_up()), decrease their speed aelow_downic to merge lanes (merge()). Using these functions, the parameterized BSQ policy Tim O1, O2) formally defined as follows.
remain in their current lane at their current speed [keep_speed[ or attempt
17

---

Tim (b; 1 O2)
If Pr(loc(agend) > loc(olher) + speed(llher) + 2v
loc(agent) + speed(agent) + 2 < loc(other) [|b > O₂ - merge()
Else if Pr[lloc(agent) - locl (oc(other) & 1]1 22
Pr [r[speed( agent) > 0],
slow [
Else spee_)
D.2 Graph Rock Sample
The Graph Rock Sample problem is that there is a rover with pre-programmed waypoints, where some waypoints contain rocks. These rocks have been categorized into types, and whether is safe for the rover to sample them is unknown. The objective of the rover is to sample each type with safe rock before traversing to a dropoff location. The objects are the waypoints, including the rocks (ri...., .n)] and the dropoff location (dropoff). The rover knows if or if it is not located at waypoint w using the unary Boolean function loc(w). The rover also knows whether needs to sample rocks of type using the unary Boolean function needed(t). For any rock the distance from the rover, whether the rock type f, and if the rock is safe to sample are tracked using the unary double function distance(r) and the Boolean functions type(r, t), and safe(r), respectively. The rover can move to neighboring waypoint w (move(w)), sample rock r at its current waypoint (sample(()) )), and scan any rock (scon(r)). For clarity, use the function golo(w) to specify taking the edge that moves the rover closer to waypoint w. Using these functions, the parameterized BSQ policy (bb 01. O2, θ₂) is formally defined follows.
Agra 01, O2, Os)=
For ra E (ri,...,na
If Prp Pr[p//pperrr () needed(() loc(re) a safe(ra]s 2 O1 - samplel(r))
Else if Pr[st]type(res t) needed(t) A -loc(re) safe(rz)lo > O₁ goto(re)
Else if (r((((upe(ree))) f) needed(t) a safe(ra]] >> O₂Λ
Pr Pr[distance((r)) Ool, == 1- scan(r.)
Else if Pr[st(type(re,t)) t) needed(t) a safe(re)le > θ2Λ
Pr Pr[distance((r)== O3]b == 1 goto(re)
Else goto dropof
D.3
Store Visit
The Store Visit problem involves an agent in a city with a grid-based layout. Some locations are unsafe, while others contain bank or a store. The objective is for the agent to visit a bank safely and then store. The objects are the agent, the set of stores {s1, sn and the set of banks {bi.... 6m)- Labeling functions bank(o) and store(o) check whether object o is bank or store, respectively. The ternary Boolean function keeps track of the current (x, y) location of the object o, loc(o, x, v). Similarly, whether location (a. y) safe tracked by the binary Boolean function is _s_afee(z, y). Lastly, the state keeps track of whether the agent has visited a bank using the nullary Boolean function obank(() The agent can move left (lef(()) right (right()) up (up), and down (down()) in the grid. The agent can also visit building in its current location (visil()) or scan its surroundings to figure out its location (scan()). Using these functions, the parameterized BSQ policy T.n (b; O₁ O2 O2) formally defined as follows.
18

---

Tsn 1, 22 93)
If Vz, yl (errlloo(aggettt a, y)1s O3 scan()
Else Pr[Bs,, v, y ()bank(() A store(s) a loo(s, v) a loc(agent, z, y)l 7 01 - visit((
For 8. {81, 11))....))
Else if Pr[ M1, 22, vblbbank() A store(s.) A loelagent, T1, v1) a lod sc: 22 V2)
21 < 22 is_sa 1, 1,) > 02 right()
Else if Pr[3ar, 9/ 22, w/2 (b A store(s.) A loclagent, xi, x1) a lod 8c; 22 V2)
11 > 22 is_safe 1, θ left()
Else if Pr[Bmr 1/. 22 A store((s) loc(agent, Iı, v1) a loo 8c; 22, y2)
y1 1/2 iissase((I,,v/ 1)] 0 downl)
Else if Pr[ Bz U1. 22. 3/2 (bbnk())) A store(s.) loc(agent, T1, v1) a lod 22 122
y1 1/2 A is is_saf((mn
1)]b, 32 θ₂ up()
Else Pr[[k; 2., yl obbank) bank((k)) loc(k; v, v) a loc(agend, n, M)bb 2 01 - vissil)
For k e {Ki, .... km
Else if Pr 3z, 1/1 22 1/2 ub)kk() bank((:e)) a loc(agent, 21, 91) loo Ros I2, y22
21 < 22 ^ is s0__saff(aa + 1, 1,, > θ₂ right()
Else if Pr[Bx1, V/. 22 3/2 - vbank() bank(ke) ^ loc(agent, T1, v1) loc(ke, T2, 12,
31 > 22 is is_saffe(a)
1, 1, > θ₂ - left()
Else if Pr[ 1/. 22 y/ vbbakk() bank(k:) a loc( 21, loo T2, 82)
V1 > 1/2 A is is_safe(Z1,11 1)]l > O₂ - down()
Else if Pr Pr[32],, 22 22 3/2 vbllkkkkk() bank(ke) a loolagent, 31) loo I2n 822
V1 < V/2 A is ss__afe(E1, 1)]b > O2 - up(
Else scan()
E Hyperparameter Optimization Algorithms Implementation
As baseline comparison, we implemented Nelder-Mead and Particle Swarm hyperparameter optimization algorithms to compare solving for the optimal parameter values for a parameterized BSQ policy to minimize the expected cost of the resulting BSQ policy. Both algorithms evaluate points in the parameter space to decide which areas to explore next. For both, we evaluate a parameter point by taking thousand parallel runs of the BSQ policy with those values to approximate the expected cost.
We used simplex that has edges numbering one more than the number of parameters in the parameterized BSQ policy being optimized. To start with better initial simplex, we randomly sampled hundred points and tracked the points that had lower expected costs and were 0.4 distance away from each of the better-performing points. The closer points were saved but were given a lower priority. Each iteration followed the standard Nelder-Mead steps with the sum quality of all the edges in the simplex calculated. If five iterations pass without an increase in quality, the run is deemed to have converged, and the best quality point of the simplex is returned the solution.
Nelder-Mead
Particle Swarm Particle swarm used 10 particles randomly selected from within the parameter space with a random velocity. Let t be the number of iteration steps since the last improvement in the best quality point found. For each iteration, the cognitive coefficient is 1.0 0.1t, and the social coefficient is 0.1 + 0t, which causes the particles to become more greedy as time since the last improvement increases. The momentum is statically set to 0.6 with the velocity clipped between +0.5. The location of points is also clipped to the parameter search space. If 10 iteration steps pass without seeing an improvement, the run is deemed to have converged, and the best quality point of the swarm is returned as the solution.
19

---

PRS-Bolt
PRS-Epsilon
PRS-Local
PRS-Global
PRS-Max
Lane Merger
Graph Rock Sample Spaceship Repair
Store Visit
30
40
10.0
60
% Goal Achievement Expected Cost
30
7.5
20
40
20
5.0
10
10
2.5
0
0.0
100
100
100
100
75
75
75
75
50
50
50
25
25
25
25
0
40
80
120
0
40
80
120
0
10
20
30
50
100
150
200
Time (Seconds)
Figure 5: Performance of the hypothesized optimal partition while solving for the Lane Merger, Spaceship Repair, and Store Visit problems. Each line is the average over independent runs with the standard deviation error shown.
F Additional Results
In this section, we provide additional results from the experiments performed. This includes intro- ducing additional partition selection approaches we evaluated: Global Thompson Sampling and Maximum Confidence. We also provide graphs of the performance of the hypothesized optimal partition across all PRS variants. Finally, provide results table for all five partition selection approaches and the baseline RCompliant.
PRS is implemented for multiprocessing by having each process manage subset of the partitions X' S X but share a global hypothesis of the optimal partition. Also, a dynamic exploration rate e, is used that diminishes approaches were explored.
the solving time. Using this framework, two additional partition selection
Maximum Confidence (PRS-Max) We explore e, percent of the time by uniformly sampling 8 Uj and checking if er- If exploring, we uniformly at random select partition from X'. Otherwise, the partition with maximum standard deviation, arg min, p,,leee a [p) is selected.
Global Thompson Sampling (PRS-Global) Unlike the other partition selection approaches, each processor iterates over all partitions manages before selecting multiple partitions refine. Partitions are chosen for two reasons: (1) they are below the minimum number of samples, or (2) the partition has the potential of being better than the current global hypothesized optimal partition. This is simulated for each partition using A (pe, oe x 6x) with fte and de being the mean and standard deviation of that partition, respectively. If the sample taken from this normal distribution has lower expected cost than the hypothesized optimal partition, this partition is selected for refinement.
Performance of the hypothesized optimal In Figure the hypothesized optimal over the runtime of PRS for each partition selection approach is shown. On Lane Merger and Spaceship Repair, the performance of each PRS variant is quite similar, with the solver quickly converging to near-optimal policy. However, PRS PRS-Global has a much slower convergence rate due to trying to evaluate all promising partitions rather than focusing not converging before timeout on Store Visit. PRS-Max is expected to perform poorly due to its poor partition-selection strategy. These results highlight that, with a competent seelition-sllection strategy, PRS will converge to the optimal policy that minimizes the expected cost, with the main variation being the convergence time.
the most promising ones. This resulted in PRS-Globar
Tabulated performance In Tad Table the expected cost the goal achievement rate have been tabulated, showing the near identical performance of four of the partition refinement approaches. The solution for Nelder-Mead and Particle Swarm are taken at PRS's timeout time give each solver the same solving time. For all the problems, the more effective
approaches
20

---

Problems
Lane Merger
Graph Rock Sample
Spaceship Repair
Store Visit
PRS-Bolt
4.39 + 0.04
18.19 + 0.82
8.52 0.00
19.81 2.09
PRS-Epsilon
4.40 + 0.04
17.84 + 0.25
8.52 + 0.00
22.20 + 4.70
PRS-Global
4.40 + 0.03
18.47 + 1.72
8.61 0.31
38.07 + 13.63
PRS-Local
4.39 + 0.03
20.61 2.96
8.57 0.05
21.57 5.80
PRS-Max
4.48 + 0.08
34.12 + 7.00
8.58 0.07
58.16 + 18.33
Nelder-Mead
4.89 f 0.65
19.56 + 1.44
8.82 0.38
22.39 8.24
Particle Swarm
4.91 + 0.56
21.12 + 2.34
8.69 0.33
18.95 + 2.42
RCompliant
22.10 + 15.70
60.91
18.46
9.97 0.77
56.64 33.04
Table I: Expected cost of Partition Refinement Search, Nelder-Mead, Particle Swarm, and RCom- pliant on the Lane Merger, Graph Rock Sample, Spaceship Repair, and Store Visit problems. The performance measured over ten runs to calculate the performance average and standard deviation.
Problems
Lane Merger
Graph Rock Sample
Spaceship Repair
Store Visit
PRS-Bolt
99.6% + 0.1%
96.0% + 1.8%
49.8% 0.0%
95.6% t 2.7%
PRS-Epsilon
99.6% + 0.1%
97.3% + 1.3%
49.8% 0.0%
92.0% i 5.8%
PRS-Global
99.6% + 0.0%
96.3% + 2.9%
50.6% 2.6%
72.6% + 16.3%
PRS-Local
99.6% + 0.1%
92.2% + 4.0%
49.3% 0.4%
92.7% + 7.2%
PRS-Max
99.5% + 0.2%
83.6% + 9.6%
49.3% 0.6%
48.2% + 21.3%
Nelder-Mead
98.9% + 1.2%
94.0% + 2.7%
52.7% + 7.9%
92.4% t 10.6%
Particle Swarm
99.0% + 1.1%
91.3% 3.5%
52.0% 5.2%
96.6% + 3.5%
RCompliant
86.9% + 16%
41.3% 20.5%
48.1% + 10.2%
49.8% + 38.4%
Table 2: Goal achievement rate of Partition Refinement Search, Nelder-Mead, Particle Swarm, and RCompliant the Lane Merger, Graph Rock Sample, Spaceship Repair, and Store Visit problems. The performance was measured over ten runs to calculate the performance average and standard deviation.
discussed the main paper achieved equal, better, performance than Nelder- Jelder-Mead and Particle Swarm.
G Experimental Setup And Computational Cost
In this section, we go through the empirical setup of the experiments performed in Section 7 and include an estimate the computation cost for running the experiments for this paper.
All experiments were performed on an Intel(R) Xeon(R) W-2102 CPU 2.90GHz without using a GPU. The Partition Refinement Search algorithm implemented using manager- manager-worker design pattern where 8 workers were initialized when solving. The manager maintained the hypothesized optimal partition and current exploration each problem for PRS. PRS was allowed to use an addition minute beyond timeout in the case the hypothesized optimal partition had less than the minimum allowed samples, however this case did not occur.
shows the timeout and sample used for
Both solutions and recorded hypothesized optimal partitions were evaluated using the same random seed to ensure that the same initial states were assessed. This evaluation process was carried out in parallel using manager- design pattern with 16 workers. 25,000 independent conducted for each solution to determine the expected cost and goal achievement rate. Additionally,
Problem
Timeout (seconds)
Sample Rate (seconds)
Lane Merger
120
0.5
Graph Rock Sample
120
Spaceship Repair
30
0.125
Store Visit Table 3: The timeout and the sample rate of the hypothesized optimal partition for PRS for the evaluation problems.
300
2.5
21

---

for each recorded hypothesized optimal partition, 10,000 runs were performed. The average perfor- mance and standard deviation error were calculated by averaging the results of ten runs for each combination of problem and solver. A similar approach was used to evaluate the random-paramen user-compliant policy RCompliant. Instead of using solved policies, ten parameter value sets were uniformly selected randomly from the parameter space, and each set was evaluated for 25,000 runs. These results are presented in 3
For constructing the Spaceship Repair heatmap (Figure I. all combinations of parameters θ and O₂ were evaluated with parameter values sampled from 0 with increments of 0.002. This produced 251,001 equally-spaced parameter values. Parameter values were evaluated on 300 runs with a horizon of 12 to calculate the expected cost.
Computational cost Running the Partition Refinement Search algorithm for the empirical evalua- tion section (Section 7 involved nine processes running simultaneously for 25 minutes across ten trials for each of the five partition-selection approaches. This resulted 1.58 hours of CPU usage when run in parallel, equivalent 14.22 hours if executed sequentially. Evaluation complexities were significant, such as the variance in time per run and problem type. For instance, evaluating the solutions and hypothesized optimal partitions for the Lane Merger problem using 17 processes took approximately 48 hours in parallel. The overall CPU usage for the main experiment approximates to 360 hours (15 days) in parallel, translating to about 6,288 hours (262 days) if run sequentially. Additionally, constructing the Spaceship Repair heatmap (Figure [ required approximately 24 hours of CPU time using 11 processes. These experiments were conducted thrice, culminating in an estimated total computational cost of 2, 160 hours (90 days) using an Intel(R) Xeon(R) W-2102 CPU 2. 2.90GHz, or 19,656 hours (819 days) if operations were performed sequentially.
H Spaceship Repair Partitions Closed Form
In this section, we calculate the braids that partition the parameter space for the Spaceship Repair problem with the parameterized BSQ policy from Fig. [
First, we give the exact observation model used. From Section the Spaceship Repair state is composed of two functions: broken(o) and rlocation(). This means each state is expressed as (broken(robo) broken (ship), rlocation().. Additionally, the set of observations can be expressed as pobs_err(robol), obs ciss_errssh err(ship)). Let pr and p, be the probability of the observation reflecting the actual state of the robot and spaceship, respectively. The probability of observation o in state after action is executed is calculated follows.
Pr(o= = {obs_ _erb_sbrrrrobo, obs ((s_err(shhip) s = (aroken(rroo))) bww.errship) rtocatiooo)
PrPe,
if broken(robol) obs_err( obs_err(robol)) ^ (roken(shhip) obs (is_error(ship) if broken(robot) obs (bs_err(rooot)) ^ broken(ship) * obs_error(shh) (ship)
Pr -ps),
(1- Pr) Pr)pss
if broken(robot) obs (bs_err(robot)) ^ broken(ship) obs_error((( (ship)
(1) (1-pr)
-
ps),
otherwise
(1)
Note observations are independent of the robot's location and actions. For clarity, we express the states as whether not the robot and spaceship means there are four possible states depending on whether the robot and ship are broken. For ease of notation, we represent these states S = {STT, STF, STF,SFT, SFF), where STF represents that state where the robot is broken and the spaceship is not. Similar, let the four possible observations be represented O- {OTT, (OTT,OTF, OFT, OFF).
broken, (broken(robol
(roken(ship)) ). This
The precondition of the first rule of the Spaceship Repair problem parameterized BSQ policy is [broken(robot]] & θ₁ (Figure I). For any belief state b, the probability of the robot being broken is the probability of the states where that is true: [broken(robot)) = b(srr) + b( b(STF).
Let {a), .... (t 0t) be an action-observation trajectory for timesteps where at each timestep an action is executed followed by an observation being observed. We can calculate the probability of the state where the robot and spaceship are broken, STT, follows.
22

---

(5(TT) aPr(ollsT,, STr)
Note that, due to the observations being independent of the robot's location, the observation and transition functions are independent of the action. For example, there action the robot can perform to change whether the robot or spaceship is broken due to the problem being to reach a broken component rather than fixing it. We can simplify Equation significantly follows.
b((TT)) www(aa/lsrrrrb--io_
(3)
We can now rewrite Equation unrolling the recursion. Note that ar is the normalization factor meaning don't 't need to calculate each timestep because the final normalization will factor in all these changes. Additionally, due to the probability cach initial state being uniform, we don't need to keep track of the initial belief. Also, note there exist four possible observations. Due to the commutativity of multiplication, we can rearrange to get the following. Let CTT, CTF, CrT, and OFF be the counts of the number of each observation where CrT + CTF CFT CFF = t.
(((T)) a (Pr((rr(ssT) Porrrlor Pr(oFr|STT) SPT Pr(OFF(sTT)
(4)
Using Equation the probability of this state can be written in terms of p, and ps.
(STT)) a(p.p.) oTT (pr (1)))))( ((1- p+)(1 pa))
(5)
be(ST)) wpprr+ere perrterr (1 pr) -.)) (1 pa) terpter
(6)
This same process can be applied to the other three states to get the equation of their likelihoods.
b((TT) = op, oor terf crp tepF (1 p.)) ).r))rr (err topF (1 p2)) CTTTerT
ps perptere
(7)
b((FFT cerrtery perereerppeetttee terterr (1 (0)))r) certere (1 ps) crrtees
(8)
b((sFF) = apper+ toFF orF porr-OFF
(orrrr torF (1 --)) OTTTFFF
(9)
We can group the states into two groups depending on whether or not the robot broken. By factoring we can get the following.
be(ST)) b((STF) op, uprTTtorF (1 DorT [p CrT teFT (1 pb) TOFF + p prr (1 pa) (rr
(10)
be(SFT) + b.(ssr) apeerter (1- pt) jrrr
(11)
(11---)erterre p certerr (1 p.) tore + + peretcre ([-ppp)errtere) perreer)
ps)
Note that in Equations 10 and 11 everything in the brackets shared, which is due to the individual observations of the spaceship and robot being independent of each other. Also, for normalization. we just divide the sum of Equations I0 and 11 which is equivalent to the sum probability of all states. Additionally, note that Equation is is equivalent to the BSQ precondition [broken(robot]] Substituting into this BSQ and simplifying we get the following.
p. perT+ere (1 )2) CFFT+FFFF +OFF
[broken(robot)]o.
(12)
Pr certerr (1 py certeer + p. FCR (1 perterr
Note that there the number is not. Let d, = erT + CrF err cpr be the difference the number of times that the robot is observed to be broken to not. If d,, > O, then the robot has been observed be broken more often than not. By substituting d, + CFTCFF CTT + CTF into Equation 12 the equation simplifies down.
exponent values: the number of times the robot is observed be broken and
dd.
[booote
(13)
de + (1 - pr)d
23

---

Following similar process, the BSQ from the second rule in the parameterized BSQ policy from Figure can be written similarly. Let d, be the difference in the number of times the spaceship is observed to be or not. If dg 0, then the spaceship has been observed to be broken more often than not.
[broken(ship]]a. p (1 pa)
(14)
Note that the observation model used = 0.6 and p. 0.75 for the heatmap in Figure The horizontal thresholds be calculated using Equation 14 and the vertical with Equation 13
1
Therefore, a partition is specific value of d, E Z and dg that is equivalent to saying: The objective is to fix the communication channel. If the difference in the number of times the robot has been observed being broken than not is greater than dy, it should try to repair itself: otherwise, if the difference in the number of times the spaceship has been observed being broken than not is greater than d,, it should try to repair that. Formally, this partition represents the parameter space where 1-r
d
p2"+(1-p.)+ and P2 p2--1+( pd & O p. +1--p11 where all parameter value sets that satisfy both inequalities similar. Due to d, and dg being the difference between observation counts, the set of possible partitions is finite for finite horizons.
- - & 1 pc.
We explored solving the Spaceship Repair problem directly using these inequalities. The belief state reflects the probability of each outcome, meaning the main challenge is calculating the average number of timesteps to reach the goal. This can be solved by finding the average length of time of the Gambler's Ruin problem. One possible direction of future work is exploring solving parameterized BSQ policies and gPOMDPs this way.
I Broader Impacts
The primary positive impact of parameterized BSQ policies is their accessibility to non-experts, allowing them input their requirements directly into solver that optimizes the completion of tasks while aligning with the user. Moreover, parameterized BSQ policies enable encoding safety constraints with enforceable guarantees over the belief state. Thus, this paper represents important step in making AI more usable for non-experts, particularly in encoding constraints and preferences, while addressing safety concerns in real-world applications."
potential negative impact of making Al more accessible through parameterized BSQ policies is that it could also be exploited by bad actors who might encode harmful preferences. To mitigate this risk, one approach is to design goals such that negative outcomes inherently prevent goal completion, thereby teaching the agent avoid these outcomes. Additionally, future work can explore methods for prioritizing certain constraints to ensure that the Al does not align with harmful intentions.
J Additional Limitations
While we discussed in Section g some of the limitations of this work, one additional limitation is an essential direction of future work: aligning user and problem objectives. For example, in Graph Rock Sample, if the encoded goal for the gPOMDP did not require collecting rocks but the user still wanted to collect one rock of each type using the parameterized BSQ policy in Appendix [D.2] PRS would optimize the parameters to make it so no rocks are worth scanning or sampling to exit as fast as possible to minimize the expected cost. While this case is an obvious misalignment between the gPOMDP and parameterized BSQ policy, these misalignments can be more subtle, leading to the optimal policy not behaving as intended. Therefore, future work needs to be done to explore catching misalignments to allow the user to understand and fix them.
24

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims made in both the abstract and introduction reflect the paper where introduced new framework for user preferences (Section 3. performed formal analysis it (Section 4, introduced piecewise constant algorithm (Section 5). and empirically evaluated this algorithm (Section 7
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Please refer both Section g and Appendix
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
25

---

Answer: [Yes]
Justification: Refer to Appendix and Appendix for the formal proofs the lemmas and theorems defined in the paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Both the code has been provided in the supplementary material and the detailed methodology can be found in Appendix G
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
26

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The code used for this paper has been provided the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ prijss.cc/ubbliccguudeee CoodeSubeeieeeeee ssi iessonPolll molyicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
Refer to Appendix Gfoo a detailed methodology.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: In both Section and Appendix F all shown results are shown with standard deviation error. Additionally, we make it clear in both sections that we are using standard deviation error.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
27

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Refer to Appendix G
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't I make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: We have reviewed and can confirm our research conforms to NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Refer to Appendix !
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
28

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification:
This paper poses no risk of being misused.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
29

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Documentation the code used in this paper is provided with the code. Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moddl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
30


Reviews:
[{"review_id": "p6KvPePtmN", "reviewer": "Reviewer_isnx", "summary": "The paper presents a new way of encoding preferences using so-called belief state queries in goal-oriented POMDPs. The modelling allows for optimising agent behaviour while complying to those preferences. In a formal analysis, the paper shows that the expected value function, although non-convex (abstract) / non-concave (main body), is piecewise constant, enabling a finite partitioning of the parameter search space. The experiments show that the theoretical potential is realisable in an implementation for the given examples.", "questions": "-", "limitations": "The limitations are discussed in the appendix. It would be great to have at least some discussion / acknowledgement of it in the main paper.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "- The paper tackles an interesting problem by looking at goal orientation and preferences in combination.\n- The framework appears sound and well-rounded.", "weaknesses": "- The presentation could be improved. There are some (minor) details that need fixing for a final version, should the paper be accepted:\n\t* Please use abbreviations consistently. Introduce an abbreviation once when the term occurs for the first time in the main text and then use the abbreviation only (exception: headings). At least one abbreviation is introduced several times (BSQ, PRS), at least one is not introduced upon first occurrence of the term (gPOMDP), one is not introduced at all in the main body (POMDP).\n\t* It usually is a sign of a weak text structure if sections have single subsections as seen with 5.1 and 6.1 (as also argued in most style guides). In the cases here, the first part of the sections deserve their own subsection headings. If the space does not permit this, consider making 5.1 and 6.1 part of the section, maybe using \\paragraph to further structure the overall section.\n\t* I recognise that space is scarce but the figures are very small, especially the experiments figures are hard to read. Please make sure that a colour-blind person can also read the figures.\n\t* It could be more explicitly stated which parts of the formalisation is new and which part is already existing. The way it is formulated right now, it could be read as gPOMDPs and BSQ being existing concepts used for the first time for preference encoding or that both are new concepts.\n\t* Again a question of available space but wrapping an algorithm in text is highly uncommon in academic AI papers.\n\n(Not sure where this needs to go in the review form; minor comments: \n- For the sake of consistency: align convexity / concavity between the abstract and the main body of the paper\n- In Def. 1, the $F$ in line 104 is not defined. Should it be $\\mathcal{F}$?\n- p. 7, line 276: missing space between (PRS)(Algo. 1) // abbreviate Algorithm by Alg. to save the space of the 'o'?\n)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed feedback and suggestions. We will incorporate these changes in the final version of the paper. We also plan to use the extra page to update the figures and add a portion of the limitations into the conclusion section. \n\nOur work is the first to formally define a BSQ framework for partially observable environments and to conduct a formal analysis of BSQs. We are the first to prove the surprising result that the parameter space for these preferences is piecewise constant and non-convex. Leveraging these properties, we developed a probabilistically complete algorithm for computing policies that match user intentions that balance goal achievement rate and average goal achievement time.", "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": "", "extra_scores": {}}, {"review_id": "3CLpuMk7YF", "reviewer": "Reviewer_NodM", "summary": "This paper introduces a method for partially observable policy optimization under belief-state query (BSQ) policy constraints (or in the author's terminology, preferences). A BSQ preference, as defined by the authors, is a class of policies parameterized by probability thresholds $\\theta$ on beliefs about certain propositions. Fixing the thresholds to particular values results in a BSQ policy --- a policy that branches on (conjunctions of) threshold-based predicates about the agent's belief state, taking certain actions if the agent believes with high enough probability that some proposition $\\phi$ if true, and going into another branch if the condition is not met.\n\nAfter introducing these definitions, the paper proves a number of theoretical results, including the result that the expected cost-to-go of a BSQ policy is a piece-wise constant function of the threshold parameters $\\theta$ for finite-horizon goal-POMDPs. In particular, the parameter space can be partitioned into a finite number of intervals, within which the cost-to-go is constant. This motivates the development of a BSQ policy optimization algorithm based on partition refinement --- by repeatedly selecting intervals of the parameter space, then trying to refine them by sampling a concrete set of threshold parameters, it is possible to eventually find the optimal (multi-dimensional) interval of threshold values. In experiments, the authors show that this approach leads to better performance than a baseline with randomly sampled threshold values.", "questions": "POST-REBUTTAL: I have adjusted my score to a 6 given the additional baseline comparisons in the author's rebuttal, which show that PRS outperforms less naive parameter search methods, as well as unconstrained policy optimization methods like POMCP and DESPOT.\n\n===\n\nIn light of the issues with framing and evaluation, I am currently recommending a paper score of 4. If only the framing issues existed, I would give a score of 5. But unfortunately the combination of issues leads me to think this paper isn't ready for publication in NeurIPS yet, even though the theory portion is interesting and sound.\n\nTo address these issues, here are my recommendations / questions:\n\n- Consider renaming \"BSQ preference\" to \"BSQ policy class/sketch/constraint\". Minimally, please discuss these alternative interpretations of a \"BSQ preference\".\n- If the \"BSQ preference\" terminology and framing is kept, there should be more rhetorical and empirical justification for why BSQ policies are a useful way of specifying user preferences, and more discussion of the notion of preferences as ordering relations.\n- Why is PRS not compared against stronger policy optimization baselines, e.g. grid search, random search, or coordinate ascent?\n- Consider comparing PRS against unconstrained policy optimization to more clearly show the benefits of BSQ policy constraints as a form of policy guidance.\n- If the \"BSQ preference\" framing is kept, consider comparing user specified BSQ preferences against user specified reward functions or reward models fitted to pairwise comparison data.\n\nMinor Comments:\n\n- In the description of PRS, the terms \"partition\" and \"optimal partition\" seem to be used in place of \"interval\" / \"optimal interval\", which led to some confusion when I was reading that section. I think the authors should try to keep to the standard notion of \"partition\" as a way of splitting a set into mutually exclusive and exhaustive subsets, and use \"interval\" to refer to one of those (continguous) subsets.", "limitations": "A number of important limitations are discussed in Appendix H. There are other limitations that I've pointed out above that should be either addressed or discussed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "BSQ polices haven't received attention for some time, so it's good to see a paper developing the theory and practice of BSQ policy evaluation and optimization. My concerns about the framing and motivation around \"preferences\" aside (see Weaknesses), the paper is technically sound, and elucidates the structure of the BSQ policy value function in a much deeper way than previously studied by Srivastava et al (2012). Given the piecewise constant nature of this value function, the partition-based policy optimization algorithm is a natural but principled approach. The proofs that I checked appear to be correct, and the experiments indicate that convergence to the optimal policy is indeed achieved. Insofar as BSQ policies provide a tractable and interpretable alternative to more direct approaches to solving POMDPs (though to me this remains to be seen), this paper is a step towards improving their practical applicability, and is likely of interest to others working on POMDPs.\n\n**References:**\n\nSrivastava, S., Cheng, X., Russell, S., & Pfeffer, A. (2012). First-order open-universe POMDPs: Formulation and algorithms. Technical report, EECS-2013-243, EECS Department, UC Berkeley.", "weaknesses": "My concerns about this paper center around two main issues (i) motivation and framing around \"preferences\" (ii) the strength of the evaluation.\n\n**Motivation and Framing**\n\nBuilding upon the concept of BSQ policies introduced in Srivastava et al (2012), this paper introduces the concept of \"BSQ preferences\", which are basically BSQ policies without fixed probability thresholds $\\theta$. In other words, a \"BSQ preference\" is just a parameterized family of BSQ policies -- a *policy class* -- which can alternatively be interpreted as a *policy constraint* (Hasanbeig et al, 2018), a *policy sketch* (Andreas et al, 2017; Verma et al, 2018) or a *partial (policy) program* (Andre & Russell, 2002; Hahn et al, 2022) where branch conditions take the form of belief-state queries.\n\nGiven these other interpretations of what a \"BSQ preference\" is -- which, in my opinion, are much more natural -- it is strange to me that the paper adopts the terminology of \"preferences\" instead. This leads to a motivation in the Introduction that feels quite at odds with the actual technical content: While it's undoubtedly the case that reward engineering is difficult, especially in partially observable settings, it's far from obvious that specifying BSQ policy constraints actually address these specification challenges. Indeed, the paper does not study whether humans find it easier to specify BSQ policy constraints rather than (a) rewards or (b) the more common notion of preferences as pairwise comparisons (used in e.g. RLHF).\n\nI understand that the authors are building upon the literature of \"planning with preferences\" in the way they use the term \"preferences\", but IMO that choice of terminology was always unfortunate*, and people should really have called stuff like LTL specifications \"constraints\" rather than \"preferences\". This is especially important if the authors are hoping to learn BSQ policies from human preference data in the future (as they suggest in the Discussion) --- it will be very confusing for the term \"preference\" to both refer to a class of (BSQ) policies, and also the more standard notion of a pairwise comparison between trajectories / choices.\n\nAt the very least, I think the authors should discuss the alternative interpretations of a \"BSQ preference\" that I have listed above -- and cite the relevant literature -- though I think it would be ideal to just move away from the \"preference\" terminology altogether.\n\n(*Note that even in the \"planning with preferences\" literature, a preference specification is understood to introduce an ordering relation over plans, in accordance with the standard notion of preferences. This notion of an ordering relation isn't discussed by the definition of a \"BSQ preference\" in this paper. I would be happier with the \"preference\" terminology if ordering relations were actually discussed, and if the paper said something about how to handle *multiple* BSQ policy constraints, each with different priorities, since this would introduce a richer ordering relation than the trivial one that prefers all policies that satisfy the constraint.)\n\n**Strength of Evaluation**\n\nWhile the Partition Refinement Search (PRS) algorithm is well explained and motivated, the evaluation is unfortunately quite limited, only comparing PRS variants to a baseline where the probability thresholds are sampled at random, with no policy optimization at all. I think minimally, there should be some kind of grid-search baseline similar to the one in Srivastava et al (2012), which more clearly shows the benefits of a search strategy based on partition refinement, compared to one which enumerates over the full space of thresholds until the time limit is up. I think there should also be a random search baseline --- i.e. one which repeatedly samples random threshold values, evaluates the resulting policies, and returns the best threshold combination so far. An even stronger baseline would be some kind of coordinate-ascent or Gibbs sampling algorithm, which optimizes one threshold at a time (via gridding or sampling) while keeping the other thresholds fixed.\n\nThe above suggestions only pertain to policy optimization under the assumption that we know for sure we want to satisfy the constraint induced by the BSQ policy class. But if the authors really want to show the benefits of BSQ policies as either (i) a way of specifying user constraints or (ii) a way of avoiding downsides of unconstrained policy optimization in POMDPs, then I think more experiments are in order.\n\nFor example, to show that BSQ policy constraints might be a more concise way of communicating user requirements than alternatives, it would be great to see a comparison with reward engineering, or with fitting and then optimizing a reward model learned from pairwise trajectory preferences (as in RLHF). I think this would be especially important if the authors want to keep the \"preference\" oriented framing of the paper.\n\nAnd to show that BSQ policies have practical engineering value over direct POMDP solution approaches like POMCP or PBVI, it would be good to find some way of comparing the solution quality of PRS vs. those other approaches --- for example, it might be the case that BSQ policy optimization actually produces better outcomes in less solution time because it allows users/developers to constrain the space of policies (i.e. provide \"policy guidance\"), similar to the benefits of HTN planning over classical planning.\n\n**References:**\n\nSrivastava, S., Cheng, X., Russell, S., & Pfeffer, A. (2012). First-order open-universe POMDPs: Formulation and algorithms. Technical report, EECS-2013-243, EECS Department, UC Berkeley.\n\nHasanbeig, M., Abate, A., & Kroening, D. (2018). Logically-constrained reinforcement learning. arXiv preprint arXiv:1801.08099.\n\nAndreas, J., Klein, D., & Levine, S. (2017, July). Modular multitask reinforcement learning with policy sketches. In International conference on machine learning (pp. 166-175). PMLR.\n\nVerma, A., Murali, V., Singh, R., Kohli, P., & Chaudhuri, S. (2018, July). Programmatically interpretable reinforcement learning. In International Conference on Machine Learning (pp. 5045-5054). PMLR.\n\nAndre, D., & Russell, S. J. (2002, July). State abstraction for programmable reinforcement learning agents. In AAAI/IAAI (pp. 119-125).\n\nHahn, E. M., Perez, M., Schewe, S., Somenzi, F., Trivedi, A., & Wojtczak, D. (2022). Recursive reinforcement learning. Advances in Neural Information Processing Systems, 35, 35519-35532.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments and for appreciating the strength of technical contributions in the paper. We agree that the BSQ framework deserves a much-needed deeper analysis, and the framework developed here takes key steps towards it. We believe that presenting this new analytical paradigm and the surprising result about piecewise-constant parameter spaces to a broad community such as NeurIPS will enable faster theoretical and algorithmic development in this direction.\n\n**Q1 and Q2:** We agree with you on both points, that (a) the notion of preferences used in this paper has been established in prior alliteration in AI, and (b) this existing choice of terminology is rather unfortunate due to the reasons you elaborate. We used it to be consistent in situating our work and acknowledging past scholarship. \n\nPartial programs [Andres et al., 2017], Alisp programs [Marthi et al., 2005], and this work represent different evolutions of the idea of using partial specifications, and all these directions draw upon Hierarchical abstract machines [Parr and Russell, 1997], albeit in fully observable settings. In fact, BSQ templates can express finite-state machine based partial specifications as well. They also specify an implicit ordering induced by the if-then-else structure.  Considering this broader context, we will use the term BSQ guidelines instead of BSQ preferences to better reflect this nature.\n\nWe respectfully maintain that terminological choices aside, this work presents a novel technical contribution whose dissemination at this stage will greatly help advance research on the topic.\n\n**Q3:** We extensively evaluated for competitive baselines, including methods such as grid-search on preliminary simpler toy problems. PRS is significantly faster than grid-search making it challenging to compare the two on the same time scale. For example, constructing the non-convex example of Spaceship Repair shown in Figure 1(c) is equivalent to doing a brute-force search, and it took 159.65 minutes to evaluate all parameter combinations with 0.01 precision. In comparison, PRS converged on a longer horizon version of Spaceship Repair within 4 minutes (Figure 4). Furthermore, to match the performance of PRS would require significantly higher precision (e.g., PRS consistently found the solution $0.600000024 < \\Theta_1 ≤ 0.600000143$ and $0.49999994 < \\Theta_2 ≤ 0.50000006$ for Spaceship Repair).\n\nDuring our evaluation, we observed that estimating the expected cost is challenging due to the high variability in sampling noise, necessitating numerous samples per point, which is computationally expensive. For instance, evaluating a random point in the Lane Merger problem with 200 samples takes, on average, 22.07 seconds. The average coefficient of variation for the expected cost for this point is 135.88%, suggesting that even more samples are required.\n\nTo address this, we also tried Nelder Mead and particle swarm optimization, which are significantly more advanced than vanilla parameter search. PRS outperformed them both, with the better of the two, Nelder Mead, having an expected cost coefficient of variation of 78.8% on a toy example, 11 times higher than PRS.\n\nThese experiments and analyses are not in the paper, but we will add them to the supplementary for the final version.\n\n**Q4:** We evaluated unconstrained policy optimization using both POMCP [Silver and Veness, 2010] and DESPOT [Somani et al., 2013]. POMCP failed to converge. DESPOT could not run on Lane Merger and only reached the goal 0.5% of the time in Graph Rock Sample. This supports your hypothesis that BSQ templates can help guide the solver. On the other two problems, DESPOT achieved lower expected costs (20.0% and 13.3% for Store Visit and Spaceship Repair, respectively). However, we evaluated the trajectories produced by DESPOT and only 7.3% and 0% of the time do they align with the user’s intentions in Spaceship Repair and Store Visit, respectively. We will add these experiments and analyses to the supplementary for the final version.\n\n**Q5:** This paper focuses on developing a formal framework and key technical results, illuminating the nature of the problem and solution directions for further research in an area that has been rather understudied. Human subject studies constitute a valuable direction for future work beyond the scope of this current paper.\n\n**Partition Terminology:** The PRS algorithm uses partition terminology to emphasize that the set of partitions $X$ is always mutually exclusive and covers the parameter space. Additionally, a partition can represent multiple disjoint intervals due to the disjunction or the negation of a conjunction of BSQs.  \n\n**References:**\n\nAndreas, Jacob, Dan Klein, and Sergey Levine. \"Modular multitask reinforcement learning with policy sketches.\" International conference on machine learning. PMLR, 2017.\n\nMarthi, Bhaskara, Stuart Russell, and David Latham. \"Writing Stratagus-playing agents in concurrent ALisp.\" Reasoning, Representation, and Learning in Computer Games (2005): 67.\n\nParr, Ronald, and Stuart Russell. \"Reinforcement learning with hierarchies of machines.\" Advances in neural information processing systems 10 (1997).\n\nSilver, David, and Joel Veness. \"Monte-Carlo planning in large POMDPs.\" Advances in neural information processing systems 23 (2010).\n\nSomani, Adhiraj, et al. \"DESPOT: Online POMDP planning with regularization.\" Advances in neural information processing systems 26 (2013).", "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": "", "extra_scores": {}}, {"review_id": "k7GcRLdAjp", "reviewer": "Reviewer_aWyU", "summary": "This paper provides a method for computing policies with user preferences called belief state queries (BSQ). A BSQ consists of a condition and a desired action and can be used for expressions like: \"Given a high likelihood of a, do b.\" To express this, the condition of a BSQ compares the probability of a first-order logic formula over the belief to a threshold. This paper aims to find the threshold values for a BSQ and the corresponding policy that minimizes the number of steps required to reach the goal states with a positive probability.\n\nThe authors give a theoretical analysis, showing that the expected cost function, i.e., the number of steps to reach the goal states for the first time, for a BSQ-compliant policy is piecewise constant. These piecewise constant areas of the expected cost function can be used to partition the parameter space. Using this result, they develop an algorithm for computing the threshold values for the optimal BSQ-compliant policy. They try various partition refinement algorithms and compare their resulting BSQ-compliant policies against a policy using uniformly selected random partitions (RCompliant). The results show that their BSQ-compliant policies have a lower expected cost and a higher probability of goal achievement than the RCompliant policies.", "questions": "1. What is the motivation for minimizing the cost instead of maximizing the probability of reaching the goal states?\n2. Is there a reason for not comparing your approach to other existing approaches? Can you give some intution on how the approaches would compare to each other?\n3. What are the sizes of the problems used for the experimental evaluation? What makes them challenging (L327)?\n4. Why is the comparison sign not an input for the BSQ?\n5. Definition 1 (goal-oriented POMDPs) uses unintroduced symbols (the non-curly F, O, and T). Is this correct? If so, what do they mean?\n6. Can you clarify Definition 1 (goal-oriented POMDP)? See weaknesses for the unclear parts.", "limitations": "The authors addressed the limitations of their work, discussing the impact on their results.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The problem of user-preference compliant policy computation in a partially observable setting is interesting. It allows specifying additional objectives for the agent that cannot be directly expressed with LTL, as the agent cannot observe the complete state of the model.\n- The definition of BSQs allows the specification of user preferences in more natural language, making it accessible to non-experts.\n- The paper removes limitations from previous works: the difficulty of guarantees in reward calibration approaches, the need for past traces in the works of Mazzi et al., and the lack of a formal analysis in the work of Srivastava et al.", "weaknesses": "-- I raise my score after the rebuttal of the authors with an additional evaluation of the method -- \n\n- The experimental comparison is limited. It would have been interesting to see how the approach compares to the reward calibration approaches that do not guarantee preference compliance or the referenced works of Mazzi et al. There is no mention of why this comparison would not be possible. Another interesting comparison would be to compare to a non-BSQ-compliant policy and analyze the difference in probability of reaching the goal states and satisfying the BSQ. Such a comparison would give insight into the gains and losses of being BSQ-compliant.\n- Information about the sizes of the problems used for the experiments is missing, making it difficult to estimate the strength of the approach.\n- The definition of the goal-oriented POMDPs is hard to follow. It is still unclear to me where the constant symbols are used, why the states S are defined as valuations for Vf, how the set of state variables for a function F follows from instantiations of F, and what the type of F is. The second part, starting with the definition of the transition function, is clear. The part before that is not.\n\nI list a couple of questions related to these weaknesses, and I am happy to reconsider the score depending on the answers.\n\nMinor comments:\n- The paper mentions relational goal-oriented POMDPs at the start of section 3, but afterward, only goal-oriented POMDPs are explained.\n- Grounded state is mentioned without explanation (L59). This term is not familiar to me.\n- Figure 2a contains a lot of information introduced in different parts of the text. Perhaps this can be split into two iterative figures for clarity.\n- I think the input theta for the compound BSQ in lemma 1 (L220) should be a capital theta.\n- Definition 9 (L204) contains a curly P to many.\n- The R with superscript 1 and subscript 0 (L503) was not introduced.\n- The union between the expected cost of a partition and the expected cost of a leaf in Algorithm 1 line 10 seems a bit weird. Is this the correct operator? If so, a small explanation would be helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the feedback and questions. \n\n**Q1:** Maximizing the probability of reaching the goal does not factor in the time required for goal completion. Therefore, the optimal strategy would be to use the maximum allowed time for gathering information before choosing to reach the goal. By minimizing the time to achieve the goal, we balance the probability of goal achievement and the average goal completion time without reward engineering.\n\n**Q2:**  We experimented with various algorithms for comparing against PRS that are not included in the paper, which can be categorized into parameter search and unconstrained POMDP solvers. The main challenge with parameter search is that we are optimizing over a non-convex continuous search space that does not have a gradient. Additionally, we observed that evaluating the expected cost accurately requires numerous samples of the same point and is computationally expensive. For example, evaluating a parameter value in Lane Merger by taking 200 samples on average requires 22.07 seconds, and the average coefficient of variation of the expected cost is 135.88%, meaning more samples are needed. Therefore, we explored using more advanced parameter search algorithms like Nelder Mead and particle swarm optimization. However, they were inconsistent, with Nelder Mead having a high expected cost coefficient of variation of 78.8% on a toy example. PRS is taking advantage of the structure of the expected cost function, allowing it to consistently and quickly converge on a solution.\n\nFor unconstrained POMDP solvers, we evaluated POMCP [Silver and Veness, 2010] and DESPOT [Somani et al., 2013]. POMCP failed to converge. DESPOT was unable to run on Lane Merger. On Graph Rock Sample, DESPOT only reached the goal 0.5% of the time due to a farther goal and sparse rewards. On Spaceship Repair, DESPOT achieved a 7.57% higher goal achievement rate and 13.3% lower expected cost. On Store Visit, DESPOT achieved a 0.58% higher goal achievement rate and 20.0% lower expected cost. We evaluated the alignment with the BSQ preferences and found that DESPOT was compliant 7.3% and 0% of the time on Spaceship Repair and Store Visit, respectively. Therefore, we can conclude that (1) BSQ preferences can help solve problems that unconstrained solvers cannot and (2) the unconstrained solver can perform better on some problems, but their policies are unlikely to comply with the user’s intentions.\n\nMazzi et al.'s work solves a different problem of normalizing behavior, so we could not compare our approach to theirs.\n\nWe will include these experiments and analyses in the supplementary for the final version of the paper.\n\n**Q3:** The size of the evaluation problems are as follows:\n* Spaceship Repair: 44 states, 3 actions, 4 observations \n* Lane Merger: 307,040 states, 4 actions, 32 observations\n* Store Visit: 30 states, 5 actions, 27 observations\n* Graph Rock Sample: 128 states, 13 actions, 3 observations\n\nThese problems are challenging due to the long horizon and safety risks. Evaluating for a horizon of 100 makes it intractable to explore the entire strategy tree (Definition 6). Each problem contains potential risks, such as merging into another car or entering unsafe areas, which would prevent the agent from completing the goal. As these risks are partially observable and relate to the goal, no policy guarantees goal completion. Therefore, the agent must balance the trade-off between taking longer to reach the goal (to gather more information) and the associated risks.\n\n**Q4:** We excluded the comparison operator as an input into a BSQ since it is constant after initialization. Note only the belief state and the parameter values vary after. To remain consistent, we will either remove the first-order logic formula as an input for the same reason or add the comparison operator as an input. Thank you for pointing this out.\n\n**Q5:** In Definition 1, non-curly $F$ and $T$ are syntax errors and have been corrected. Non-curly $O$ is the set of objects, which we will clarify in the next version of the paper. Thank you for pointing these errors out.\n\n**Q6:** Our gPOMDP definition draws upon existing literature on expressive languages for specifying POMDPs [Sanner, 2010, Srivastava, 2012]. This representation allows us to specify large POMDPs by reusing functions from the set of functions $\\mathcal{F}$ and instantiating them from the set of objects $O$. For example, whether each rock is safe to sample in Graph Rock Sample can be represented as $safe(rock_i)$. To build the set of states $\\mathcal{S}$, we first construct all the state variables $\\mathcal{V}_f$, which are all the combinations of function parameters using $O$. Each state in $\\mathcal{S}$ represents a set of values setting each state variable.\n\n**References:**\n\nSanner, Scott. \"Relational dynamic influence diagram language (rddl): Language description.\" Unpublished ms. Australian National University 32 (2010): 27.\n \nSilver, David, and Joel Veness. \"Monte-Carlo planning in large POMDPs.\" Advances in neural information processing systems 23 (2010).\n\nSomani, Adhiraj, et al. \"DESPOT: Online POMDP planning with regularization.\" Advances in neural information processing systems 26 (2013).\n\nSrivastava, Siddharth, et al. First-order open-universe POMDPs: Formulation and algorithms. Technical report, EECS-2013-243, EECS Department, UC Berkeley, 2012.", "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": "", "extra_scores": {}}, {"review_id": "ObT7LOMLsi", "reviewer": "Reviewer_Mo3a", "summary": "This paper proposes a method for computing optimal policy in a given POMDP and a specific policy class (the class of BSQ policies).", "questions": "N/A", "limitations": "N/A", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "In this work, to ensure compliance with user's preference, the policies are directly parameterized by the preferences (formalized by boolean formulas). This approach is quite different from the more well-known approach of including preferences in the objective function, and it is worth investigating.", "weaknesses": "(1) Readability: This paper introduces many heavy notations. The definitions (of BSQ, policies, etc.) are pretty abstract.\n\n(2) The policies are defined using BSQ. The expressiveness of such a policy class is not well-justified: it is not clear whether this policy class includes all policies that comply with the agent's preferences.\n\n(3) The experiments are performed on several different environments, but the uniformly random baseline (RCompliant) is probably too weak.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. \n\n**Weakness 2:** We assume that a policy must comply with a BSQ preference to align with the user’s intentions. Therefore, we can prove that all aligning policies are included in the policy class.\n\n**Weakness 3:** The baseline RCompliant is there to (1) show the BSQ preferences alone are insufficient for solving the evaluation problems and (2) to evaluate how much the solution of PRS can improve the solution. \n\nWe did run experiments searching for a competitive baseline that we excluded from the paper. We found that a brute-force grid search requires significantly more time than PRS because evaluating the expected cost of a point in the parameter space requires numerous samples. For smarter parameter optimization algorithms (Nelder Mead and particle swarm), we found that the sampling cost, along with optimizing over a non-convex continuous parameter space that lacks a gradient, made these algorithms too unreliable. POMDP solvers would be an unfair comparison to use as a baseline since PRS receives additional information on the problem.  Otherwise, there is no existing work that we can directly compare against. We will add experiments and analyses on this into the supplementary for the final version.", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their detailed reviews and comments. We answer the questions posed by the reviewers separately. Please find them in the response below the reviews.

Meta-review: This paper addresses the use of POMDP policies formulated using belief-state queries (BSQs) and how user constraints or guidance (in the authors’ terminology, preferences) using BSQs can be solved effectively. The paper provides a novel formulation, decent theoretical analysis and empirical validation of the effectiveness of the proposed method. This paper generated considerable discussion, especially around two main weaknesses identified by the reviewers: (1) the motivation and presentation, specifically, the use of the term “preferences” rather than, say, “policy constraints,” “policy class restrictions,” “user (behavior/policy) guidance,” etc.  (2) the inadequate comparison to suitable (albeit natural, easy-to-test) baselines. 

The authors and reviewers engaged in significant discussion, including the authors provided a substantial collection of new empirical results in the rebuttal, and agreeing to recharacterize the framing and motivation of the paper. This resulted in an overall raise in the reviewers’ (aggregate) assessment and scores. As such, I believe this paper makes a valuable contribution to NeurIPS. But it is critical that, if the paper is accepted, the authors’ make all of the revisions discussed (incl. incorporation of the new empirical results, ideally, not stashed away in an appendix).
Decision: Accept (poster)