Simplified Risk-aware Decision Making with Belief-dependent Rewards in Partially Observable Domains (Extended Abstract)

1 Introduction

While operating in a partially observable setting, the robot repetitively performs actions and receives observations from the environment in an interleaving manner. The result of each action is a imprecise change in the robot's state. The robot has access to the probability density of the state, given the history of its actions and the observations alongside the prior. We call this probability density a belief. In each planning session, the robot shall reason about future beliefs and select an optimal action based on its current belief using beliefdependent rewards and the objective operator. The robot shall look into the future as far as possible. With the growing horizon, however, the computational burden is becoming unbearable for the robot due to exponential growth in complexity [Papadimitriou and Tsitsiklis, 1987]. Many research efforts in Artificial Intelligence (AI) and Robotics communities have tackled the described problem. In AI community, it received the name Partially Observable Markov Decision Process (POMDP), whereas, in the Robotics community, it is known as Belief Space Planning (BSP). In classical POMDP the belief-dependent reward is assumed to be the average of the state-dependent reward with respect to belief. While alleviating the solution, this assumption hinders the ability to actively decrease uncertainty over the belief using general belief-dependent operators. In BSP, general belief-dependent rewards are essential, e.g., navigation, sensor placement problems. The classical assumption in BSP is that the belief follows Gaussian distribution [Indelman et al., 2015].

∗The original journal paper: A. Zhitnikov and V. Indelman. Simplified Risk Aware Decision Making with Belief-dependent Rewards in Partially Observable Domains. Artificial Intelligence, Special Issue on "Risk-Aware Autonomous Systems: Theory and Practice", 2022.

The AI community began to introduce general beliefdependent rewards starting from the discrete domains [Araya et al., 2010], [Fehr et al., 2018], and limiting assumptions concerning the reward operators [Dressel and Kochenderfer, 2017]. More recent approaches such as Sparse Sampling (SS) [Kearns et al., 2002], and Monte Carlo Tree Search (MCTS) [Sunberg and Kochenderfer, 2018] build upon Belief-MDP (BMDP). These methods are suitable for continuous domains. Still, in the continuous setting of states and observations, these methods give an approximate solution with only asymptotical optimality guarantees. On the other hand, the BSP community introduced a concept of simplification [Indelman, 2016],[Elimelech and Indelman, 2022], [Shienman and Indelman, 2022b], [Kitanov and Indelman, 2019]. As opposed to approximations, the simplification paradigm substitutes various parts of the decision-making problem while providing guarantees on the impact of such a substitution.

In this work, we focus on the distribution of the rewards in a nonparametric setting. Our objective is to simplify the decision-making problem and analyze the impact of the simplification.

2 Notations and ProblemFormulation

Let P be the probability density and P the probability. In this paper, we focus on the finite horizon setting. Further, to shorten notations, we shall often use □k+ to denote □k+1:k+L, where L is the planning horizon. By ≡ we denote identity.

2.1 POMDP with Belief Dependent Rewards

ρ-POMDP [Araya et al., 2010] is an eight tuple

where X , A, Z are state, action, and observation spaces with x ∈ X, a ∈ A, z ∈ Z the momentary state, action, and observation, respectively, T(x, a, x′ ) ≜ PT (x′ |x, a) is the transition model from the past momentary state x to the next x′ through action a, O(z, x) ≜ PZ(z|x) is the observation model, ρ (b′ , z′ , a, b) is a scalar reward operator, γ ∈ (0, 1] is the discount factor, and b0 is the prior belief.

2.2 Belief Space Planning

The posterior belief at time instant k is given by

The usual assumption is that the belief is a sufficient statistic for decision making objective [Bertsekas, 1995]. However, in practice, the belief requires some representation. This representation is not perfect, e.g., parametric or sampled form; thus, in (2), we used the ≈ sign. In a real life scenario bk = ψ(ψ(. . . ψ(b0, a0, z1), ak-2, zk-1), ak-1, zk), where ψ is a method for updating the belief. By π ≜ πk:k+L-1 we denote a vector of policies for L time steps starting from time step k. Each such policy πℓ at time step ℓ maps belief to an action πℓ(bℓ) = aℓ. The general decision making under uncertainty objective function is of the following form

where L is the planning horizon, ρℓ is a random immediate reward, φ is an objective operator, and gk ≜ fgk (ρk+1:k+L) is the return [Sutton and Barto, 2018]. A common choice for φ is expectation over the distribution of future rewards given all data available [Defourny et al., 2008]. The return is a deterministic known function of the realization of ρk+1:k+L, e.g., it could correspond to the cumulative reward gk = ∑Lℓ=1 ρk+ℓ. Finally, ψ is a general method for propagating the belief with action and updating it with the received observation.

The objective (3) is ultimately based on the distribution of the return given all information available for planning under selected policy P(gk|bk, πk), which decomposes via marginalization over future observations zk+ ≡ zk+1:k+L as

A common assumption is that P(gk|bk, π, zk+, ) is a Dirac delta function.

3 Foundations

In this section we introduce probabilistic ρ-POMDP and rigorously define the simplification paradigm. We further continue to the formulation of the general bounds on the reward/return which can be analytical or stochastic.

3.1 Extended Setting, Probabilistic ρ-POMDP

Sometimes the belief bℓ-1 has a simple parametric form, where θℓ-1 is a vector of parameters, e.g., a Gaussian belief. In this case, belief update ψ can be deterministic, and is denoted by ψdt(θℓ-1, πℓ-1(θℓ-1), zℓ). In more general and challenging scenarios the belief bℓ-1 is given by a set of weighted samples {(wiℓ-1 , xiℓ-1 )}Ni=1 . Therefore, ψ is a stochastic method, e.g., a particle filter [Thrun et al., 2005]. Applying multiple times ψ on the same input will yield different sets of samples approximating the same distribution of the posterior belief. We denote the stochastic ψ by ψst(bℓ-1, πℓ-1(bℓ-1), zℓ). Another form to formulate the above is that the distribution

is not a Dirac delta function. This aspect was disregarded so far, to the best of our knowledge. Note that in a Belief MDP (BMDP) formulation, the assumption is that B is a Dirac delta function. Similar arguments hold for the momentary reward operator of the belief. We extend ρ (b′ , z′ , a, b) to

To our knowledge, we are the first who treat these aspects as random.

Before introducing simplification formally and analyzing its impact, we shall account for all potential sources of variability. We remove conventional approximations by extending (1) to a probabilistic reward model R (6) and probabilistic belief update B (5), and introduce

which we name probabilistic ρ-POMDP (Pρ-POMDP). The rationale behind these conditional distributions (R and B) is to capture additional sources of stochasticity, such as stochastic belief update, stochastic calculation of a given reward operator or simply not knowing the operator reward in an explicit analytic form.

As discussed earlier, the value function (3) is based on (4). These previously overlooked sources of stochasticity impact the likelihood of the observations

as well as the joint reward distribution P(ρk+|bk, π, zk+) ≡ P(ρk+1:k+L|bk, πk:k+L-1, zk+1:k+L) given a realization of future observations. In contrast, in the regular setting of POMDP and ρ-POMDP P(ρk+|bk, π, zk+) is Dirac's delta function. If B is a Dirac function, a sample from (8) uniquely defines the corresponding posterior beliefs bk+1:k+L. This, therefore, corresponds to the classical belief tree (R could still be non a Dirac function). In contrast, our Pρ-POMDP (7), corresponds to an extended belief tree, which, due to (5), allows many samples of the beliefs bk+1:k+L for each sample of zk+1:k+L from (8) ( See Fig. 1).

3.2 Simplification Formulation

To formally define the simplification procedure, we augment the Pρ-POMDP tuple (7) with a simplification operator ν ≜

νk, . . . , νk+L,

This general operator defines any possible modification of the original problem defined by (7) alongside with (3) to a new, simpler to solve, problem. The definition (9) allows us to retain the connection to the original nonsimplified problem (7) and examine the impact of the simplification on (7). The operator ν can be for example, sparsification of the initial belief bk [Elimelech and Indelman, 2022], replacing the reward by its topological signature [Kitanov and Indelman, 2019], direct calculation of lightweight reward bounds [Sztyglic and Indelman, 2022], selecting a subset of hypotheses in a hybrid or mixture belief [Shienman and Indelman, 2022a], to name a few.

Generally, M and Mν are different decision making problems. We shall be interested in working online with the latter while providing the guarantees with respect to the former. To distinguish a simplified reward from the original reward, we denote the former by ˘ ρ instead of ρ; similarly, we denote the simplified belief by ˘b instead of b. Note the operator ν can be stochastic, as discussed below. Specifically, belief simplification is described by the distribution

In general, the distribution (10) over the simplified belief ˘bℓ corresponds to a stochastic simplification operator ν b ℓ . This is the case, for example, when bℓ is represented by a set of N weighted samples and ν b ℓ is the operation of subsampling n samples according to weights; i.e., applying this operation on bℓ multiple times leads to different sets of n samples, each representing another realization of ˘bℓ from (10). Overall there are (Nn ) such combinations. For a deterministic operator ν b ℓ , (10) is a Dirac function.

Further, there are several cases of how a simplification affects belief update (5) from time ℓ - 1 to ℓ.

1. Without any simplification we have PB(bℓ|bℓ-1, πℓ-1, zℓ) from (5).
2. Given a simplified belief ˘bℓ-1, while keeping the original stochastic belief update ψst, we have
3. PB(˘bℓ|˘bℓ-1, πℓ-1, zℓ), where each realization of ˘bℓ is obtained via ψst. Thus, given ˘bℓ-1, this distribution is not a function of ν.
4. We can also simplify the belief update operator, ψst, to ˘ ψst. Denoting the corresponding simplification operator ν ψ ℓ , this yields P ˘B (˘bℓ|˘bℓ-1, πℓ-1, zℓ; ν ψ ℓ ).
5. Finally, one can decide at time ℓ to apply simplification on the belief (determined by ν b ℓ ) via (10). The corresponding belief update can be written as

where ˜bℓ is the integration variable.

We combine these cases and write

Similarly, reward simplification could be, in general, stochastic, leading to the distribution

Thus, given a simplified belief ˘bℓ and ˘bℓ-1, and recalling (6), the distribution over ˘ ρℓ is

which we denote as the simplified reward model,

Throughout the document we assume that operator ν does not affect the observations likelihood. In other words, the measurements are sampled as in the original problem as in (8). For the further discussion we make the following shorthand notation. Let Hk+L ≜ {bk, π, zk+} be future history at the time index k + L.

3.3 Online Stochastic and Analytical Bounds

We turn now to the joint distribution over original and simplified rewards, given the future history and operator ν, namely P (ρk+, ˘ ρk+|Hk+L, ν). In an online setting we do not have access to the original rewards as calculating them explicitly defeats the purpose of simplification. Instead, we shall now utilize simplification to provide bounds over the original rewards. These bounds can be used to provide performance guarantees, and should be cheaper to calculate than the original unsimplified rewards. Further, the bounds can be analytical as in previous simplification approaches, e.g, [Elimelech and Indelman, 2022]. Ultimately for each realization of the return we are interested in the following relation

One way to do that is to develop analytical bounds, which will hold for any possible observation zk+1:k+L received and any corresponding return, e.g, as in [Sztyglic and Indelman, 2021].

Our extension allows R and B, as well as ˘R and ˘B to be any distributions. They can remain Dirac functions, e.g., if belief update and the reward calculation have a closed form. Successively, P(gk|bk, π, zk+, ) remains Dirac delta. However, in the more general case, following our extension, there is a joint distribution of original and simplified returns given a realization of the future and the present

as illustrated in Fig. 2. Given the history Hk+L, the return gk as well as the simplified return ˘ gk has variability, in contrast to the conventional approach. Ordinarily, the belief update is commenced once and treated as deterministic. So as the rewards and return do not have variance given the history of the actions and the observations. Since (15) is no longer a Dirac function, we can use knowledge about this distribution to design bounds, which will hold with some probability. In the main paper [Zhitnikov and Indelman, 2022], we show that it is possible to harness the structure of (15) to design the mentioned more lenient online bounds. Moreover, analytical bounds, designed in a conventional setting, can be used in our extended setting without any revision. In our extended setting, they will bound with probability one.

Having introduced the novel stochastic bounds, we proceed to the formulation of the constraints, that these bounds shall fulfill to be meaningful. Let the parameter controlling the confidence level be α ∈ [0, 1). For every possible sample ˘ gk we do not know which sample gk one could obtain in the original problem. However, if the bounds are designed such that P(gk, l, u|Hk+L, ν) render

these bounds can be useful. Notably, the above equation does not involve simplified return, so is applicable also in the case bounds are directly formulated (and not via a simplified return). However, in this case the bounds are analytical and α = 0. To summarize, there are three types of online reward/return bounds:

1. Deterministic bounds. These analytical bounds exist in case of a closed form belief update ψdt and a deterministic operator reward, e.g., belief is a Gaussian and the
2. reward is differential entropy. In this case, even in our extended setting R and B remain Dirac functions.
3. Stochastic bounds that hold with probability one, namely α = 0. These are also analytical bounds. In our extended setting R and B are no longer Dirac functions. However, these bounds hold for any realization of sample approximation, as stated around (14).
4. Stochastic bounds that hold at least with probability 1α. They exist only in our extended setting when R and B are not Dirac functions.

4 The Return Given a Candidate Policy

Applying the marginalization over the observations we obtain the distribution of the original and the simplified return given the candidate policy and the operator ν (See Fig. 2).

For further discussion please see [Zhitnikov and Indelman, 2022].

5 The Pair of the Returns Corresponding to the Pair of Candidate Policies

Imagine a pair of a candidate policies. In such a setting we are interested in the following distribution (See Fig. 3)

On top of (17) we propose a tool to examine the simplification impact on the original not simplified problem. We call it Probabilistic Loss.

5.1 Probabilistic Loss (PLoss)

Consider a random variable L : Ω → R over the events space Ω defined as such

The realization of random variable L(ω) = ∆ differs from zero if the simplification have switched the ordering of the original returns and the original difference between returns was ∆.

5.2 Online Bound on Probabilistic Loss (PbLoss)

Since the PLoss is inaccessible online we propose another random variable which is accessible.

To give to the reader a glimpse into the connection between PLoss and PbLoss suppose the bounds (14) are analytical. This implies that L(ω) ≤ ¯ L(ω) ∀ω ∈ Ω and this implies

To the impact of the proposed ideas onto Decision Making please refer to the journal paper [Zhitnikov and Indelman, 2022].