--- title: "Simplified Risk-aware Decision Making with Belief-dependent Rewards in Partially Observable Domains (Extended Abstract)" authors: - "Andrey Zhitnikov" - "Vadim Indelman" doi: "10.24963/ijcai.2023/798" url: "https://ijcai.org/proceedings/2023/798" pdf: "https://ijcai.org/proceedings/2023/0798.pdf" venue: "Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence" year: 2023 pages: "7001-7005" track: "Journal Track" keywords: - "Planning and Scheduling: PS: POMDPs" - "Uncertainty in AI: UAI: Sequential decision making" - "Robotics: ROB: Motion and path planning" - "Planning and Scheduling: PS: Planning under uncertainty" --- # Simplified Risk-aware Decision Making with Belief-dependent Rewards in Partially Observable Domains (Extended Abstract) Andrey Zhitnikov, Vadim Indelman *Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence*, pages 7001-7005. DOI: [10.24963/ijcai.2023/798](https://doi.org/10.24963/ijcai.2023/798) ## Abstract It is a long-standing objective to ease the computation burden incurred by the decision-making problem under partial observability. Identifying the sensitivity to simplification of various components of the original problem has tremendous ramifications. Yet, algorithms for decision-making under uncertainty usually lean on approximations or heuristics without quantifying their effect. Therefore, challenging scenarios could severely impair the performance of such methods. In this paper, we extend the decision-making mechanism to the whole by removing standard approximations and considering all previously suppressed stochastic sources of variability. On top of this extension, we scrutinize the distribution of the return. We begin from a return given a single candidate policy and continue to the pair of returns given a corresponding pair of candidate policies. Furthermore, we present novel stochastic bounds on the return and novel tools, Probabilistic Loss (PLoss) and its online accessible counterpart (PbLoss), to characterize the effect of a simplification. ## Full text ## 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. Figure 1: The Extended Belief Tree versus the standard. ![Image](https://ijcai.org/proceedings/2023/fulltext/798/image_000000_cf6d3be17e34d2dd5ddfc335f51a870b57ece915d9e27ee2aa974b1a8d94d53c.png) 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). Figure 2: Our extension and the simplification in the context of a single candidate policy. ![Image](https://ijcai.org/proceedings/2023/fulltext/798/image_000001_80f75ba0032b1e8b379161de81ca2640d59704dd41989a5a3e30a136f48d1d9c.png) ## 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 ν. 3. 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ℓ; ν ψ ℓ ). 4. 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 Figure 3: The simplification in our extended setting and its impact of the joint distribution of a pair of the returns corresponding to the pair of the candidate policies. ![Image](https://ijcai.org/proceedings/2023/fulltext/798/image_000002_6d2566b41920737e9b36b567810a94ecde5f1813110d6fde0dde67b325c4b4a0.png) 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. 2. 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). 3. 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]. ## References 1. [Araya et al., 2010] Mauricio Araya, Olivier Buffet, Vincent Thomas, and Franc ¸cois Charpillet. A pomdp extension with belief-dependent rewards. In Advances in Neural In- formation Processing Systems (NIPS), pages 64-72, 2010. 2. [Bertsekas, 1995] Dimitri Bertsekas. Dynamic programming and optimal control, volume 1. Athena scientific Belmont, MA, 1995. 3. [Defourny et al., 2008] Boris Defourny, Damien Ernst, and Louis Wehenkel. Risk-aware decision making and dy- namic programming. In NIPS Workshop on Model Un- certainty and Risk in RL, 2008. 4. [Dressel and Kochenderfer, 2017] Louis Dressel and Mykel J. Kochenderfer. Efficient decision-theoretic target localization. In Laura Barbulescu, Jeremy Frank, Mausam, and Stephen F. Smith, editors, Proceedings of the Twenty-Seventh International Conference on Auto- mated Planning and Scheduling, ICAPS 2017, Pittsburgh, Pennsylvania, USA, June 18-23, 2017, pages 70-78. AAAI Press, 2017. 5. [Elimelech and Indelman, 2022] Khen Elimelech and Vadim Indelman. Simplified decision making in the belief space using belief sparsification. The International Journal of Robotics Research, 41(5):470-496, 2022. 6. [Fehr et al., 2018] Mathieu Fehr, Olivier Buffet, Vincent Thomas, and Jilles Dibangoye. rho-pomdps have lipschitz- continuous epsilon-optimal value functions. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 6933-6943. 7. [Indelman et al., 2015] V. Indelman, L. Carlone, and F. Del- laert. Planning in the continuous domain: a general- ized belief space approach for autonomous navigation in unknown environments. Intl. J. of Robotics Research, 34(7):849-882, 2015. 8. [Indelman, 2016] V. Indelman. No correlations involved: Decision making under uncertainty in a conservative sparse information space. IEEE Robotics and Automation Letters (RA-L), 1(1):407-414, 2016. 9. [Kearns et al., 2002] Michael Kearns, Yishay Mansour, and Andrew Y Ng. A sparse sampling algorithm for near- optimal planning in large markov decision processes. Ma- chine learning, 49(2):193-208, 2002. 10. [Kitanov and Indelman, 2019] A. Kitanov and V. Indel- man. Topological information-theoretic belief space planning with optimality guarantees. arXiv preprint arXiv:1903.00927, 3 2019. 11. [Papadimitriou and Tsitsiklis, 1987] C. Papadimitriou and J. Tsitsiklis. The complexity of Markov decision pro- cesses. Mathematics of operations research, 12(3):441- 450, 1987. 12. [Shienman and Indelman, 2022a] M. Shienman and V. In- delman. D2a-bsp: Distilled data association belief space planning with performance guarantees under budget con- straints. In IEEE Intl. Conf. on Robotics and Automation (ICRA), 2022. 13. [Shienman and Indelman, 2022b] M. Shienman and V. In- delman. Nonmyopic distilled data association belief space planning under budget constraints. In Proc. of the Intl. Symp. of Robotics Research (ISRR), 2022. 14. [Sunberg and Kochenderfer, 2018] Zachary Sunberg and Mykel Kochenderfer. Online algorithms for pomdps with continuous state, action, and observation spaces. In Pro- ceedings of the International Conference on Automated Planning and Scheduling, volume 28, 2018. 15. [Sutton and Barto, 2018] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018. 16. [Sztyglic and Indelman, 2021] Ori Sztyglic and Vadim In- delman. Online pomdp planning via simplification. arXiv preprint arXiv:2105.05296, 2021. 17. [Sztyglic and Indelman, 2022] Ori Sztyglic and Vadim In- delman. Speeding up online pomdp planning via simplifi- cation. In IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems (IROS), 2022. 18. [Thrun et al., 2005] S. Thrun, W. Burgard, and D. Fox. Prob- abilistic Robotics. The MIT press, Cambridge, MA, 2005. 19. [Zhitnikov and Indelman, 2022] A. Zhitnikov and V. Indel- man. Simplified risk aware decision making with be- lief dependent rewards in partially observable domains. Artificial Intelligence, Special Issue on "Risk-Aware Au- tonomous Systems: Theory and Practice", 2022.