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

Andrey Zhitnikov, Vadim Indelman

Introduction

Robots operating in uncertain, real-world environments rely on Partially Observable Markov Decision Processes (POMDPs) to navigate using "beliefs"—probability distributions over possible states. However, solving POMDPs optimally is often computationally prohibitive. To maintain real-time performance, practitioners frequently resort to approximations or heuristics. The critical challenge is that these simplifications often ignore the inherent randomness in the planning process itself, such as the noise in particle filter updates. This paper introduces a formal framework, the Probabilistic $\rho$-POMDP ($\mathbb{P}\rho$-POMDP), to quantify the risk associated with these computational shortcuts using a metric called Probabilistic Loss (PLoss).

The Extended Belief Tree

A fundamental departure from traditional models is the treatment of belief updates. Standard POMDPs assume that given a belief, an action, and an observation, the next belief is a single, deterministic point. In reality, the algorithms used to compute these updates (like particle filters) are themselves stochastic.

The Extended Belief Tree (bottom) acknowledges that a single belief update is actually a sample from a distribution of possible beliefs (top), a process termed "extension" (e).

By acknowledging this "distribution of distributions," the authors create an Extended Belief Tree. This structure allows for a more rigorous analysis of how randomness propagates through the decision-making process, especially when rewards depend directly on the belief state (e.g., information gain or safety constraints).

Simplification and Probabilistic Loss

To make planning tractable, the authors define Simplification Operators ($\nu$). These operators transform a complex, high-fidelity problem into a lighter version—for instance, by reducing the number of particles in a filter or using a simplified reward function.

Simplification (s) maps the original return distribution to a simplified one. The framework uses "extension" (e) to account for the stochasticity in both original and simplified processes.

The core innovation is Probabilistic Loss (PLoss). PLoss measures the probability that a simplification will cause a "preference flip"—where a robot mistakenly chooses a suboptimal policy because the simplification made it appear better than the true optimal one. Because calculating the exact PLoss is often impossible online, the authors derive PbLoss, a computable upper bound that provides safety guarantees during operation.

Key Results and Theoretical Bounds

The framework establishes three tiers of online bounds for rewards:

  1. Deterministic: Analytical bounds for closed-form updates (e.g., Gaussian beliefs).
  2. Stochastic (Prob. 1): Bounds that hold for any realization of a sample approximation.
  3. Stochastic (Prob. $1-\alpha$): Lenient bounds that hold with a specific confidence level, allowing for more aggressive simplification when risk tolerance is higher.

The authors prove that their online tool, PbLoss, is a conservative estimate of the true risk, ensuring that if the robot stays within the PbLoss bound, the actual probability of a dangerous decision remains controlled.

Conclusion

This framework moves beyond "guessing" with approximations by providing a mathematical bridge between computational speed and decision-making risk. While the Extended Belief Tree adds theoretical complexity, the introduction of computable bounds like PbLoss paves the way for robots that can adapt their level of "thinking" to the task at hand without flying blind. Future work will focus on reducing the overhead of calculating these bounds to enable seamless integration into real-time robotic systems.

Summary updated

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.
BibTeX
@inproceedings{zhitnikov2023simplified,
  author = {Andrey Zhitnikov and Vadim Indelman},
  title = {{Simplified Risk-aware Decision Making with Belief-dependent Rewards in Partially Observable Domains (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/798},
}
Figure