--- title: "ConstrainedZero: Chance-Constrained POMDP Planning Using Learned Probabilistic Failure Surrogates and Adaptive Safety Constraints" authors: - "Robert J. Moss" - "Arec Jamgochian" - "Johannes Fischer" - "Anthony Corso" - "Mykel J. Kochenderfer" doi: "10.24963/ijcai.2024/746" url: "https://ijcai.org/proceedings/2024/746" pdf: "https://ijcai.org/proceedings/2024/0746.pdf" venue: "Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence" year: 2024 pages: "6752-6760" track: "Main Track" keywords: - "Planning and Scheduling: PS: Planning under uncertainty" - "Planning and Scheduling: PS: POMDPs" - "Machine Learning: ML: Partially observable reinforcement learning and POMDPs" --- # ConstrainedZero: Chance-Constrained POMDP Planning Using Learned Probabilistic Failure Surrogates and Adaptive Safety Constraints Robert J. Moss, Arec Jamgochian, Johannes Fischer, Anthony Corso, Mykel J. Kochenderfer *Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence*, pages 6752-6760. DOI: [10.24963/ijcai.2024/746](https://doi.org/10.24963/ijcai.2024/746) ## Abstract To plan safely in uncertain environments, agents must balance utility with safety constraints. Safe planning problems can be modeled as a chance-constrained partially observable Markov decision process (CC-POMDP) and solutions often use expensive rollouts or heuristics to estimate the optimal value and action-selection policy. This work introduces the ConstrainedZero policy iteration algorithm that solves CC-POMDPs in belief space by learning neural network approximations of the optimal value and policy with an additional network head that estimates the failure probability given a belief. This failure probability guides safe action selection during online Monte Carlo tree search (MCTS). To avoid overemphasizing search based on the failure estimates, we introduce Δ-MCTS, which uses adaptive conformal inference to update the failure threshold during planning. The approach is tested on a safety-critical POMDP benchmark, an aircraft collision avoidance system, and the sustainability problem of safe CO₂ storage. Results show that by separating safety constraints from the objective we can achieve a target level of safety without optimizing the balance between rewards and costs. ## Full text ## 1 Introduction When developing safety-critical agents to make sequential decisions in uncertain environments, planning and reinforcement learning algorithms often formulate the problem as a partially observable Markov decision process (POMDP) with the objective of maximizing a scalar-valued reward function [Kochenderfer et al., 2022]. POMDP solution methods find a policies that maximizes this reward. To ensure adequate safety, the scalar reward is tuned to balance the goals of the agent while penalizing undesired behavior or failures. Recently, chance-constrained POMDPs (CC-POMDPs) have been used to frame the safe planning problem by separating the reward function into a constrained problem [Santana et al., 2016]. The objective of CC-POMDPs is to maximize the goal rewards while satisfying the safety constraints. To solve CC-POMDPs, online algorithms such as RAO∗ use heuristic forward search to find policies that maximize the reward and estimate the risk of constraint violation [Santana et al., 2016]. RAO∗ plans over the reachable belief space for discrete state, action, and observation CC-POMDPs. The iterative RAO∗ (iRAO∗ ) extends the heuristic search algorithm to multi-agent settings and handles continuous states and actions through Gaussian process regression and probabilistic flow tubes [Huang et al., 2018]. Lauri et al. [2022] highlight the limitations of such chance-constrained POMDP algorithms and the need for scalable approaches to solve largescale, long-horizon CC-POMDPs in practice. Figure 1: Elements of ConstrainedZero for CC-POMDP planning. ![Image](https://ijcai.org/proceedings/2024/fulltext/746/image_000000_604d28b51a85a1ff8f56823f71e1add4b6b8374c84ab630bda85f3117596db3b.png) To address scalability and applicability to continuous state and observation spaces, we introduce the ConstrainedZero policy iteration algorithm that combines offline neural network training of the value function, the action-selection policy, and the failure probability predictor with online Monte Carlo tree search (MCTS) to improve the policy through planning. ConstrainedZero is a direct extension to the POMDP belief-state planning algorithm BetaZero [Moss et al., 2024] and the family of AlphaZero algorithms [Silver et al., 2018], with extensions shown in red in fig. 1. Along with an opensource implementation, 1 our main contributions are threefold: 1. We introduce ∆-MCTS, an anytime algorithm for MDPs (applied to belief-state MDPs) that estimates failure probabilities along with Q-values and adjusts the failure probability threshold using adaptive conformal inference [Gibbs and Candes, 2021]. ∆-MCTS selects actions by maximizing the Q-value while satisfying that the failure probability constraint is below the adapted threshold using the introduced CC-PUCT criterion. 2. We introduce ConstrainedZero, a policy iteration algorithm that extends BetaZero for CC-POMDPs. ConstrainedZero includes an additional network head that estimates the failure probability given a belief and uses ∆-MCTS with the neural network surrogate to prioritize promising safe actions, replacing expensive rollouts or domain-specific heuristics. Framing the problem as a CC-POMDP means a target safety level can be specified instead of balancing penalties in the reward function. 3. We empirically evaluate ConstrainedZero and ∆-MCTS on three challenging safety-critical benchmark CCPOMDPs: a long-horizon localization task (LightDark [Platt Jr. et al., 2010]), an aircraft collision avoidance system (modeled after ACAS X [Kochenderfer et al., 2012]), and a CO2 storage agent [Corso et al., 2022]. ## 2 ProblemFormulation This section formulates the safe planning problem as a beliefstate CC-MDP. Background is also provided on Monte Carlo tree search and the BetaZero policy iteration algorithm. POMDPs and belief-state MDPs. The partially observable Markov decision process (POMDP) is a framework for sequential decision making problems where the agent has uncertainty over their state in the environment [Kochenderfer et al., 2022]. The POMDP is a 7-tuple ⟨S,A,O, T,R,O, γ⟩ consisting of a state space S, an action space A, an observation space O, a transition model T, a reward model R, an observation model O, and a discount factor γ ∈ [0, 1]. When solving POMDPs, the objective is to find a policy π(b) given a belief b over the unobserved state and return an action a ∈ A that maximizes the value of the belief, which is the expected discounted sum of rewards (i.e., the expected discounted returns) when continuing to follow the policy π: where b0 is the initial belief, often using the initial state distribution, and the belief-based reward is defined as [1 https://github.com/sisl/ConstrainedZero.jl](https://github.com/sisl/ConstrainedZero.jl) Every POMDP can be cast as an MDP by simply treating the belief as the state. In doing so, one can construct a beliefstate MDP (BMDP) with the belief space B of the original POMDP as the MDP state space, while using the same action space A, the belief-based reward model Rb from eq. (2), and a transition function b′ ∼ Tb(· | b, a) that takes the current belief b and action a and returns a stochastic updated belief b′ . The belief transition function first samples a hidden state s ∼ b(·) and transitions that state through the POMDP transition function s′ ∼ T(· | s, a). Then an observation is sampled from the observation model o ∼ O(· | a, s′ ) and finally the belief is updated to get the posterior The belief update may be done exactly as in eq. (3) or using approximations such as a Kalman filter [Wan and Van Der Merwe, 2000] or particle filter [Thrun et al., 2005]. The belief-state MDP tuple of ⟨B, A, Tb, Rb, γ⟩ can also be defined using a generative model (b′ , r) ∼ Gb(b, a) instead of an explicit belief transition model Tb and belief reward model Rb. The underlying POMDP can also use a generative model (s′ , r, o) ∼ G(s, a). Our work uses the generative POMDP ⟨S, A, O, G, γ⟩ and the generative BMDP ⟨B, A, Gb, γ⟩. Chance-constrained planning. When dealing with safetycritical sequential decision making problems, separating safety constraints from the objective allows for solvers to target an adequate level of safety while simultaneously maximizing rewards. This is in contrast to designing a single reward function to balance the rewards from the goals and penalties from violating safety. The chance-constrained POMDP (CC-POMDP) defines a failure set F that includes all state-action pairs (s, a) ∈ S × A that fail and a bound ∆ ∈ [0, 1] on the probability, or chance, of a failure event occurring. Chance constraints are intuitive for users to define as they translate to the target failure probability of the agent, which is often the requirement for systems in industries such as aviation [Busch, 1985] and finance [Flannery, 1989]. The objective when solving CC-POMDPs is to maximize the value function while ensuring that the failure probability, or the chance constraint, is below the target threshold ∆: The failure probability F π (bt) is often called the execution risk of the policy π computed from the belief bt. Therefore, the CC-POMDP is defined as the tuple ⟨S, A, O, F, T, R, O, γ, ∆⟩ which may also use a generative model G to replace ⟨T,R,O⟩. Our work casts the chanceconstrained POMDP to a chance-constrained belief-MDP (CC-BMDP). The CC-BMDP tuple ⟨B,A, Fb, Tb,Rb, γ,∆⟩ extends BMDPs with an immediate failure probability function Fb : B×A → [0, 1] and a failure probability threshold ∆. The immediate failure probability is computed as using the failure set F. The CC-BMDP can also be defined with a generative model (b′ , r, p) ∼ Gb(b, a) that also returns the failure probability p = Fb(b, a) with notation overloading of Gb, resulting in the tuple ⟨B,A,Gb, γ,∆⟩. Monte Carlo tree search. The best-first search algorithm, Monte Carlo tree search (MCTS), is designed to solve MDPs [Coulom, 2007] and has been applied to solve POMDPs cast as belief-state MDPs [Sunberg and Kochenderfer, 2018; Fischer and Tas, 2020; Moss et al., 2024]. MCTS is an online algorithm that determines the best action to take from the current state s (or belief state b). Starting from the root state, MCTS iteratively simulates the following four steps to build out a tree of possible reachable futures to a depth d: 1. Selection. An action is selected from the existing children of the current state node or sampled from the action space. The selection process balances exploration and exploitation. Metrics such as UCT [Kocsis and Szepesv´ari, 2006] or PUCT [Silver et al., 2017] have been used in the literature to select the action to take. 2. Expansion. Once an action is selected, it is executed from the current state node to expand the tree. For stochastic state transitions, methods like progressive widening [Cou¨etoux et al., 2011] or state abstraction refinement [Sokota et al., 2021] can be used to control when to execute the action or take an existing tree path. 3. Simulation. From the expanded state, the tree is recursively built from this new root node. Simulation returns an estimate of the value of the expanded state. The value estimate could use a rollout policy [Silver et al., 2016] (which may be expensive for BMDPs), or use function approximators such as neural networks [Silver et al., 2017; Fischer et al., 2022; Moss et al., 2024]. 4. Backpropagation. Finally, the value estimate is combined with the immediate reward to get the Q-value. This Q-value is assigned to the parent state-action node as a running mean. This process backpropagates the signal up the tree path that led to that node. After a prescribed number of iterations, or at anytime as determined by a compute-time constraint, MCTS will select the best action from the children of the root node, often using the Q-values or visit counts [Browne et al., 2012]. Br´azdil et al. [2020] introduce an algorithm for CC-MDPs that uses UCT with a table-based value and risk predictor, and a linear program to compute an action distribution that satisfies an adaptive constraint. Ayton and Williams [2018] introduce an MCTS algorithm for CC-MDPs that selects actions that satisfy a local chance constraint over state histories and prune branches that violate the constraint. MCTS algorithms have also been developed for costconstrained POMDPs (C-POMDPs) [Isom et al., 2008], where a discounted cost is minimized. Algorithms such as C-POMCP [Lee et al., 2018], C-MCTS [Parthasarathy et al., 2023], C-POMCPOW, C-PTF-DPW, and C-POMCP-DPW [Jamgochian et al., 2023] estimate the cost function during search using rollouts, while our approach uses chance constraints and estimates constraint violation probabilities using neural network surrogates. BetaZero. The BetaZero belief-state planning algorithm extends AlphaZero to long-horizon POMDPs [Moss et al., 2024]. BetaZero combines MCTS planning in belief space with neural network surrogates of the value function and action-selection policy. The neural network takes as input the belief, which is converted to an input representation ˜b = ϕ(b) = (µ, σ) of summary statistics, and estimates the value v = Vθ(˜b) and policy vector p = Pθ(˜b) as two heads of the network (p, v) = fθ(˜b). BetaZero improves the neural network through policy iteration by iterating the following: 1. Policy evaluation: Execute parallel MCTS episodes using the current network to collect training data for policy imitation learning and value regression. 2. Policy improvement: Use the recent MCTS data over a specified window to re-train the neural network. Learning from experience through policy iteration reduces the required MCTS depth of search (by estimating the value of future belief states) and breadth of search (by selecting actions prioritized by the policy head of the network). The neural network surrogate also acts as a learned replacement for domain-specific heuristics of the value function and policy. In BetaZero, the root node action selection used during MCTS, which is also the trained policy vector target, is a combination of the observed Q-values and visit counts N seen during search. This combination incorporates all available information in the tree, given that belief-state planning is often limited due to the expensive belief updates that occur every state transition. The root node action is selected according to the Q-weighted policy vector: where τ controls the sampling temperature (used during policy iteration) and returns the argmax when τ → 0 (used during final evaluation). Intuitively, the Q-weighted policy vector uses information from what was found during search (Qvalues) and what the search focused on (visit counts). Moss et al. [2024] show that the combination leads to the highest return on various benchmark POMDPs. ## 3 Approach ConstrainedZero follows the BetaZero policy iteration steps of policy evaluation and policy improvement while also collecting failure event indicators to train the failure probability network head, shown in red in algorithm 1. During policy evaluation, n parallel ∆-MCTS executions are run and a data set D is collected. The data set D = {{bt, πt, gt, et}Tt=1}nj=1 is a tuple of the belief at episode time step t denoted bt, the tree policy πt, the return gt = ∑Ti=t γ (i-t) ri based on the observed reward ri and discount factor γ, and the failure event indicator et, where gt and et are computed at the end of the trajectory for all time t ≤ T . The failure event is computed as the disjunction of all state and action pairs of the CC-POMDP in the execution trajectory to ensure that if a trajectory failed at some point the full trajectory is marked as a failure: where 1{E} is the indicator function that returns 1 when event E is true and 0 otherwise. ## Algorithm 1 Offline ConstrainedZero policy iteration. During policy improvement, the neural network is trained to minimize the MSE or MAE loss LVθ (gt, vt) to regress the value function vt = Vθ(˜bt), minimize the cross-entropy loss LPθ (πt, pt) to imitate the tree policy pt = Pθ(˜bt), and additionally minimize the binary cross-entropy loss LFθ (et, pt) to regress the failure probability function pt = Fθ(˜bt), with added regularization using the L2-norm of the weights θ: The failure probability head of the neural network includes a final sigmoid layer to ensure the output can be interpreted as a probability in the range [0, 1]. ## 3.1 Adaptive Safety Constraints in ∆-MCTS When using online MCTS for CC-BMDP planning, two considerations have to be addressed: 1) how to estimate the observed failure probability in the tree search, and 2) how to select actions constrained by this failure probability. At each node for the belief-state and action (b, a), the immediate failure probability p is computed using the generative model (or by calling p = Fb(b, a) directly). An estimate of the future failure probability p′ can be computed using rollouts, which may be expensive for belief-state planning, thus we use the trained neural network head for failure probability estimation p′ = Fθ(˜b′ ). Similar to the Q-value, we must compute the full failure probability of the trajectory from the immediate time step to the horizon, termed the F-value. Let E be the immediate failure event from belief b when taking action a at time t, and let E′ be the event of failing in the future (from t + 1 to the horizon T ). The probability of failing between the current time t and the horizon T becomes: assuming independence in eq. (11). A discount δ is applied to control the influence of the future failure probability: Unlike Carpin and Thayer [2022], who backup F-values based on the best-case, we backpropagate the F-values up the tree similar to Q-values (alg. 2, line 16): which is a running mean estimate where F(b, a) is initialized using the initialization function F0(b, a) (noting the F0 subscript: which could either be zero, the immediate failure probability Fb(b, a), or the bootstrapped value by taking action a to get a new belief b′ and computing eq. (14) based on the p′ = Fθ(˜b′ ) estimate). Note, the number of times the node (b, a) is visited is indicated as the visit count N(b, a). Using the estimate F(b, a), a simple way to select actions that do not violate the safety constraint set by ∆ would be to use the PUCT algorithm [Silver et al., 2018] with a hard constraint on safety of only choosing actions such that F(b, a) ≤ ∆ is satisfied. PUCT exploits nodes based on their observed Q-values and explores nodes based on their visit counts weighted by the action-selection policy Pθ to explore promising actions. 2 However, if the failure probability threshold ∆ is too conservative, the action-selection process may fail to find any action that satisfies the constraint. Therefore, ∆-MCTS tracks an estimate of the threshold ∆(b) for each belief node and updates it using adaptive conformal inference (ACI) [Gibbs and Candes, 2021]. ACI is a statistical method that provides valid prediction intervals without assumptions on how the time-series data was generated. The adaptive threshold is initialized to the target tolerance ∆(b) = ∆0 where ∆0 = ∆ from the CC-BMDP. Each time the F -value is updated (either by eq. (15) or initialization), the ADAPTATION procedure is called to update the current acceptable safety threshold. 2 The belief node visit count is N(b) = ∑a′ N(b, a′ ) for children a′ ∈ A(b). Following Schrittwieser et al. [2020], we normalize the Q-values between zero and one, denoted ¯Q, to avoid problemspecific heuristics when selecting an exploration constant c: ![Image](https://ijcai.org/proceedings/2024/fulltext/746/image_000001_ce8cee591675582460460e543d52770c7efd16fbee0d298bd5a6e129de5b975b.png) p + δ(1 - p)Fθ (˜b′ ) Figure 2: ConstrainedZero online Monte Carlo tree search with failure threshold adaptation (∆-MCTS). In adaptation, the error term of err = 1{F(b, a) > ∆(b)} indicates when to widen or restrict the estimated threshold ∆(b) based on whether the failure probability estimate of the most recently explored belief-action node F(b, a) is above or below the current threshold. The estimated threshold is updated according to which will widen the threshold if the observed failure probability is outside the threshold (i.e., if the error is one), and will tighten the threshold otherwise: ## Algorithm 2 ConstrainedZero online ∆-MCTS. ``` 1 function ∆MCTS(Pcc, fθ, b) 2 Mcc ← ⟨B,A,Gb, γ,∆0⟩ ▷ convert from generative Pcc 3 for 1 to nonline 4 SIMULATE(fθ, b, d) 5 πtree(b, a) ∝ (( expQ(b,a) ∑a′ expQ(b,a′) )( N(b,a) ∑a′ N(b,a′) ))1/τ 6 return a ∼ πtree(b, a) ▷ let τ → 0 to get argmax 7 s.t. F(b, a) ≤∆′ (b) ▷ ∆′ (b) =max{∆0,∆(b)} 1 function SIMULATE(fθ, b, d) 2 if TERMINAL(b) return 0, 0 3 if b ̸∈ T or d = 0 4 T ← T ∪ {b} 5 N(b) ← N0(b) 6 ˜b ← ϕ(b) ▷ input belief representation 7 return Vθ(˜b), Fθ(˜b) ▷ network lookup 8 N(b) ←N(b) +1 9 a ← ACTIONSELECTION(fθ, b) 10 (b′ , r, p) ← BELIEFSTATEEXPANSION(b, a) 11 v′ , p′ ← SIMULATE(fθ, b′ , d - 1) 12 q ← r + γv′ 13 p ← p+ δ(1 -p)p′ ▷ observed failure probability 14 N(b, a) ←N(b, a) +1 15 Q(b, a) ←Q(b, a) + q-Q(b,a) N(b,a) ▷ backpropagate Q-value 16 F(b, a) ←F(b, a) + p-F(b,a) N(b,a) ▷ backpropagate F-value 17 ADAPTATION(∆, b, a) 18 return q, p ``` Intuitively, the update adjusts the threshold of acceptable failure probability ∆(b) based on recent experience. If the failure probability F(b, a) for a recent action is higher than the current threshold ∆(b), this indicates a higher risk than expected. Thus, the threshold is increased by η(1 -∆0) for η > 0 to allow for more risk in future actions. Otherwise, if F(b, a) is lower than the threshold, this means actions are safer than expected and the threshold is decreased by η∆0 (favoring a more reactive increase than decrease of the threshold). Notably, Gibbs and Candes [2021] prove that ∆(b) converges exactly to the desired target over time. We clip the final threshold to the lower and upper bounds of the observed failure probability for a given belief b to restrict ## Algorithm 3 ∆-MCTS selection, expansion, and adaptation. ``` 1 function ACTIONSELECTION(fθ, b) 2 ˜b ←ϕ(b) 3 if |A(b)| ≤ kaN(b)αa ▷ action progressive widening 4 a ∼ Pθ(˜b, ·) ▷ prioritized from network 5 if a ̸∈ A(b) 6 N(b, a) ← N0(b, a) 7 Q(b, a) ← Q0(b, a) 8 F (b, a) ← F0(b, a) 9 ∆(b) ← ∆0 ▷ target tolerance ∆0 10 ADAPTATION(∆, b, a) 11 A(b) ← A(b) ∪ {a} 12 return arg max a∈A(b) ¯Q(b, a) + c(Pθ(˜b, a) √N(b) 1+N(b,a) ) 13 s.t. F (b, a) ≤ ∆′ (b) ▷ CC-PUCT 1 function BELIEFSTATEEXPANSION(b, a) 2 if |B(b, a)| ≤ kbN(b, a)αb ▷ belief progressive widening 3 b′ , r, p ∼ Gb(b, a) ▷ generative model 4 B(b, a) ← B(b, a) ∪ {(b′ , r, p)} 5 else 6 b′ , r, p ∼ B(b, a) 7 return b′ , r, p 1 function ADAPTATION(∆, b, a) 2 l(b) ← mina′∈A(b) F (b, a′ ) ▷ update bounds 3 u(b) ←maxa′∈A(b) F(b, a′ ) 4 err ← 1{F (b, a) > ∆(b)} 5 ∆(b) ← clip(∆(b) + η(err - ∆0), l(b), u(b)) ``` the change in ∆(b) and, more importantly, to guarantee that at least one action is available for selection: with the lower and upper bounds of l(b) = mina′ F(b, a′ ) and u(b) = maxa′ F(b, a′ ) for a′ in children nodes A(b). The resulting criterion selects actions that satisfy the adaptive constraint of F (b, a) ≤ ∆′ (b) where the selection threshold ∆′ (b) = max{∆0, ∆(b)} upper bounds the failure probability. Together, the ∆-MCTS exploration policy becomes: termed the chance-constrained PUCT criterion (CC-PUCT). The constraint in eq. (22) is also used in root node action selection (line 7, alg. 2). In practice, πexplore is computed using the indicator 1, returning the action a ∈ A(b) that maximizes: The benefit of CC-PUCT is that when our explored samples satisfy the constraint ∆′ (b) (defined over the belief rather than both belief and action) we may explore new actions from this belief which are both safe and have the potential for higher reward. The key idea is that actions are chosen based on the balance between safety and utility; ensuring that we do not over-prioritize safety at the expense of potential rewards, while not exploiting rewards without regarding the risk. The five stages of ∆-MCTS are shown in algorithms 2-3: selection, expansion, simulation, backpropagation, and adaptation, with extensions to BetaZero shown in red. ## 4 Experiments For a fair comparison, ConstrainedZero was evaluated against BetaZero using the same network and MCTS parameters. BetaZero uses a scalarized reward function to penalize failures, while ConstrainedZero omits the penalty and plans using the adaptive safety constraint instead. The BetaZero reward takes the form ¯Rb(b, a) = Rb(b, a)-λC(b, a) with a cost C scaled by λ. Three safety-critical CC-POMDPs were evaluated. The first is the LightDark POMDP, a standard benchmark localization task [Platt Jr. et al., 2010], where a particle filter is used to update the belief with nparticles = 500. A failure occurs if the agent stops outside of the goal (i.e., the origin). The next CC-POMDP is the aircraft collision avoidance problem returns ![Image](https://ijcai.org/proceedings/2024/fulltext/746/image_000002_cf861d1e09d95837e686c87ed16c649d6f86e45b91d400211945e12d4ce66875.png) - (a) Returns from policy iteration. - (b) Safety from policy iteration. ![Image](https://ijcai.org/proceedings/2024/fulltext/746/image_000003_9ebad0997a16541b502d2832d37e31d60c3bea5740af0635744952e2fe99f680.png) Pareto Front for Constrained LightDark returns Figure 3: BetaZero(λ) comparison. ![Image](https://ijcai.org/proceedings/2024/fulltext/746/image_000004_8af564c2cdb07f710d528e473d7c6d6a9e69eaa7672f9d3818b7796e96764753.png) (CAS), modeled after ACAS X [Kochenderfer et al., 2012]. In the CAS problem, the ownship aircraft attempts to avoid a near mid-air collision (NMAC) with an intruding aircraft while minimizing the alert and reversal rates. An NMAC occurs if the ownship is within 50 meters in relative altitude hrel of the intruder at the end of the encounter (i.e., when |hrel| ≤ 50 and time to collision τ =0). The belief is updated with an unscented Kalman filter to track the mean and covariance of the state variables [Wan and Van Der Merwe, 2000]. Lastly, we study safe carbon capture and storage (CCS), which is a promising mitigation of global emissions that captures CO2 and stores it in porous subsurface material [Corso et al., 2022]. A challenge of CCS is safely injecting CO2 into the subsurface while mitigating risk of leakage and earthquakes, where any CO2 leakage indicates a failure. The simplified CCS problem uses spillpoint analysis to model the top surface of the injection site and a sequential importance resampling particle filter is updated with observations at drilling locations [Corso et al., 2022]. ## 4.1 Empirical Results Figure 3 compares ConstrainedZero against BetaZero, where BetaZero uses different values of the penalty λ. The penalties were swept between -10 and -1000 with -100 being the standard for the LightDark POMDP (proportional to the goal reward of 100). A target safety level of ∆0 = 0.01 was chosen for ConstrainedZero. ConstrainedZero exceeds the relative altitude ![Image](https://ijcai.org/proceedings/2024/fulltext/746/image_000005_230d86512fabe755b1b2589c3a0d35b1169293f8fe37aaee8e2f38509a83c971.png) (c) Higher p(fail) near an NMAC. (d) Climb (blue), descend (green). Figure 4: Results for the collision avoidance CC-POMDP. Figure 4d matches the "notch" behavior from Kochenderfer et al. [2012]. | | LightDark ∆0 = 0.01 - p(fail) ↓ | LightDark ∆0 = 0.01 - returns ↑ | Collision Avoidance ∆0 = 0.01 - p(fail) ↓ | Collision Avoidance ∆0 = 0.01 - returns ↑ | Spillpoint CCS ∆0 = 0.05 - p(fail) ↓ | Spillpoint CCS ∆0 = 0.05 - returns ↑ | |-----------------|-----------------------------------|-----------------------------------|---------------------------------------------|---------------------------------------------|----------------------------------------|----------------------------------------| | ConstrainedZero | 0.01±0.01 | 13.07±0.42 | 0.00±0.00 | -0.74±0.03 | 0.05±0.02 | 2.62±0.12 | | No Adaptation∗ | 0.66±0.05 | 27.47±3.90 | 0.03±0.02 | -1.00±0.00 | 0.69±0.04 | 6.18±0.36 | | ∆-MCTS (no fθ)† | 0.01±0.01 | 1.86±0.20 | 0.32±0.05 | 0.00±0.00 | 1.00±0.00 | 6.87±0.50 | | Raw Policy Pθ | 0.01±0.01 | 12.88±0.46 | 0.00±0.00 | -0.86±0.02 | 0.06±0.02 | 2.45±0.11 | | Raw Value‡ Vθ | 0.72±0.05 | 28.00±4.51 | 0.16±0.04 | -0.20±0.04 | 0.38±0.05 | 4.27±0.30 | | Raw Failure‡ Fθ | 0.80±0.04 | 0.05±0.04 | 0.00±0.00 | | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 -1.62±0.08 * Trained with the same parameters as ConstrainedZero without adaptation, i.e., only a hard constraint on ∆0. † ∆-MCTS without the neural network for the value or failure probability and a random policy for CC-PUCT. ‡ One-step look-ahead over all actions using only the value or failure probability network head with 5 obs. per action. Table 1: ConstrainedZero results. Bold indicates the best results within the ∆0 threshold. BetaZero Pareto curve and achieves the target level of safety with a failure probability of 0.01 ± 0.01 computed over 100 episodes. Notably, ConstrainedZero also has less variance in the failure probability and the returns. BetaZero still achieves good performance but at the cost of sweeping the penalty values without explicitly defining a safety threshold to satisfy. Shown in table 1, an ablation study is conducted for ConstrainedZero. Most notably, the adaptation procedure is crucial to enable the algorithm to properly balance safety and utility during planning (also shown in fig. 4a-4b). When comparing ∆-MCTS without network approximators against ConstrainedZero, it is clear that offline policy iteration allows for better online planning. Using only the raw policy head Pθ achieves good performance, which is trained to imitate the tree policy. However, incorporating additional online planning with the full network yields better results overall, enabling planning over potentially unseen information. The full ConstrainedZero algorithm consistently achieves the highest return within the satisfied target level of safety ∆0. Compared to BetaZero, fig. 4a and fig. 4b highlight that ConstrainedZero satisfies the safety constraint earlier during policy iteration, while simultaneously maximizing returns (shown for the CAS problem). The policy trained without adaptation learns to maximize returns but fails to satisfy the safety constraint. This is because without adaptation, the algorithm will attempt to satisfy a fixed constraint, not taking into account the outcomes of its actions. With adaptation, ConstrainedZero adjusts the constraint in response to feedback from the environment, resulting in the algorithm becoming more capable at optimizing its performance within the bounds of the adaptive constraint. This demonstrates the importance of adaptation, as a fixed constraint may be too conservative or too risky, leading to suboptimal decision-making. ## 5 Conclusions This work introduces ConstrainedZero, an extension of the BetaZero POMDP planning algorithm to chance-constrained POMDPs. Along with neural network estimates of the value function and action-selection policy, we include a network head that estimates the failure probability given a belief. By formulating the safe planning problem as a CC-POMDP, we select a target level of safety to optimize towards, instead of traditional POMDP methods that tune the reward function to balance safety and utility as a multi-objective problem. We develop an extension to Monte Carlo tree search that includes an adaptation stage that adjusts the target level of safety during planning with adaptive conformal inference. The resulting ∆-MCTS algorithm modifies MCTS for CC-POMDPs and addresses the issue of overfitting to failure predictions. Additionally, a constrained action-selection criterion (CCPUCT) was developed to enable planning under constraints. The full implementation and experiments are open sourced and are part of the Julia package BetaZero.jl. 3 Limitations. Adapting the safety level when planning with approximations may lead to deviations despite ACI convergence guarantees, but the lack of adaptation also does not guarantee the desired safety. However, our experiments show that this flexibility helps the algorithm find policies matching the targeted safety. Similar to BetaZero, ConstrainedZero may require more computing resources than existing POMDP solvers due to neural network training and parallel ∆-MCTS episodes. However, it is designed for large-scale, uncertain problems in high-dimensional spaces that require long-horizon planning. We focus on real-world scenarios where transition dynamics, not policy training, are the main challenge, using past experiences to learn an approximately optimal policy offline that is refined online using tree search. Future work. A benefit of ∆-MCTS unexplored in this work is that it also applies directly to safety-critical MDPs, such as scheduling [Soualhia et al., 2020]. Future work could focus on the application of ConstrainedZero to fully observable MDP settings and extending the algorithm to work over multiple failure modes. Other future work could improve the data efficiency of ConstrainedZero, extend it to continuous actions similar to algorithms such as A0C [Moerland et al., 2018], or apply it to safety-critical robotics tasks such as navigation [Ong et al., 2010] and object manipulation [Pajarinen and Kyrki, 2017; Pajarinen et al., 2022]. [3 https://github.com/sisl/ConstrainedZero.jl](https://github.com/sisl/ConstrainedZero.jl) ## Acknowledgments This research is funded by OMV and J.F. thanks the Karlsruhe House of Young Scientists (KHYS) for travel grant funding. ## References 1. [Ayton and Williams, 2018] Benjamin J. Ayton and Brian C. Williams. Vulcan: A Monte Carlo Algorithm for Large Chance Constrained MDPs with Risk Bounding Func- tions. arXiv:1809.01220, 2018. 2. [Brázdil et al., 2020] Tomáš Brázdil, Krishnendu Chatterjee, Petr Novotnỳ, and Jiří Vahala. Reinforcement Learning of Risk-Constrained Policies in Markov Decision Processes. In AAAI Conference on Artificial Intelligence, volume 34, pages 9794-9801, 2020. 3. [Browne et al., 2012] Cameron B. Browne, Edward Powley, et al. A Survey of Monte Carlo Tree Search Methods. IEEE Transactions on Computational Intelligence and AI in Games, 4(1):1-43, 2012. 4. [Busch, 1985] Allen C. Busch. Methodology for Establish- ing A Target Level of Safety. Federal Aviation Administra- ton Technical Center, 1985. 5. [Carpin and Thayer, 2022] Stefano Carpin and Thomas C. Thayer. Solving Stochastic Orienteering Problems with Chance Constraints Using Monte Carlo Tree Search. In International Conference on Automation Science and En- gineering (CASE), pages 1170-1177. IEEE, 2022. 6. [Corso et al., 2022] Anthony Corso, Yizheng Wang, Markus Zechner, Jef Caers, and Mykel J. Kochenderfer. A POMDP Model for Safe Geological Carbon Sequestration. NeurIPS Workshop on Tackling Climate Change with Ma- chine Learning, 2022. 7. [Couëtoux et al., 2011] Adrien Couëtoux, Jean-Baptiste Hoock, et al. Continuous Upper Confidence Trees. In Learning and Intelligent Optimization. Springer, 2011. 8. [Coulom, 2007] Rémi Coulom. Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search. In Com- puters and Games, 2007. 9. [Fischer and Tas, 2020] Johannes Fischer and Ömer Sahin Tas. Information Particle Filter Tree: An Online Algo- rithm for POMDPs with Belief-Based Rewards on Contin- uous Domains. In International Conference on Machine Learning, pages 3177-3187. PMLR, 2020. 10. [Fischer et al., 2022] Johannes Fischer, Etienne Bührle, Da- nial Kamran, and Christoph Stiller. Guiding Belief Space Planning with Learned Models for Interactive Merging. In International Conference on Intelligent Transportation Systems (ITSC), pages 2542-2549, 2022. 11. [Flannery, 1989] Mark J. Flannery. Capital Regulation and Insured Banks Choice of Individual Loan Default Risks. Journal of Monetary Economics, 24(2):235-258, 1989. 12. [Gibbs and Candes, 2021] Isaac Gibbs and Emmanuel Can- des. Adaptive Conformal Inference Under Distribution Shift. Advances in Neural Information Processing Systems (NeurIPS), 34:1660-1672, 2021. 13. [Huang et al., 2018] Xin Huang, Ashkan Jasour, et al. Hy- brid Risk-Aware Conditional Planning with Applications in Autonomous Vehicles. In IEEE Conference on Deci- sion and Control (CDC), pages 3608-3614. IEEE, 2018. 14. [Isom et al., 2008] Joshua D. Isom, Sean P. Meyn, and Richard D. Braatz. Piecewise Linear Dynamic Program- ming for Constrained POMDPs. In AAAI Conference on Artificial Intelligence, volume 1, pages 291-296, 2008. 15. [Jamgochian et al., 2023] Arec Jamgochian, Anthony Corso, and Mykel J. Kochenderfer. Online Planning for Con- strained POMDPs with Continuous Spaces through Dual Ascent. International Conference on Automated Planning and Scheduling (ICAPS), 33(1):198-202, 2023. 16. [Kochenderfer et al., 2012] Mykel J. Kochenderfer, Jes- sica E. Holland, and James P. Chryssanthacopoulos. Next- Generation Airborne Collision Avoidance System. Lincoln Laboratory Journal, 19(1), 2012. 17. [Kochenderfer et al., 2022] Mykel J. Kochenderfer, Tim A. Wheeler, and Kyle H. Wray. Algorithms for Decision Mak- ing. MIT Press, 2022. 18. [Kocsis and Szepesvári, 2006] Levente Kocsis and Csaba Szepesvári. Bandit Based Monte-Carlo Planning. In Eu- ropean Conference on Machine Learning. Springer, 2006. 19. [Lauri et al., 2022] Mikko Lauri, David Hsu, and Joni Pa- jarinen. Partially Observable Markov Decision Processes in Robotics: A Survey. IEEE Transactions on Robotics, 39(1):21-40, 2022. 20. [Lee et al., 2018] Jongmin Lee, Geon-Hyeong Kim, Pascal Poupart, and Kee-Eung Kim. Monte-Carlo Tree Search for Constrained POMDPs. In Advances in Neural Information Processing Systems (NeurIPS), volume 31, 2018. 21. [Moerland et al., 2018] Thomas M. Moerland, Joost Broekens, Aske Plaat, and Catholijn M. Jonker. A0C: Alpha Zero in Continuous Action Space. In ICML Planning and Learning (PAL) Workshop, 2018. 22. [Moss et al., 2024] Robert J. Moss, Anthony Corso, Jef Caers, and Mykel J. Kochenderfer. BetaZero: Belief- State Planning for Long-Horizon POMDPs using Learned Approximations. Reinforcement Learning Journal (RLJ), 1(1), 2024. 23. [Ong et al., 2010] Sylvie C. W. Ong, Shao Wei Png, David Hsu, and Wee Sun Lee. Planning under Uncertainty for Robotic Tasks with Mixed Observability. The Interna- tional Journal of Robotics Research, 29(8), 2010. 24. [Pajarinen and Kyrki, 2017] Joni Pajarinen and Ville Kyrki. Robotic Manipulation of Multiple Objects as a POMDP. Artificial Intelligence, 247:213-228, 2017. 25. [Pajarinen et al., 2022] Joni Pajarinen, Jens Lundell, and Ville Kyrki. POMDP Planning Under Object Composition Uncertainty: Application to Robotic Manipulation. IEEE Transactions on Robotics, 39(1):41-56, 2022. 26. [Parthasarathy et al., 2023] Dinesh Parthasarathy, Georgios Kontes, Axel Plinge, and Christopher Mutschler. C- MCTS: Safe Planning with Monte Carlo Tree Search. arXiv:2305.16209, 2023. 27. [Platt Jr. et al., 2010] Robert Platt Jr., Russ Tedrake, Leslie Kaelbling, and Tomas Lozano-Perez. Belief Space Planning Assuming Maximum Likelihood Observations. Robotics: Science and Systems VI, 2010. 28. [Santana et al., 2016] Pedro Santana, Sylvie Thiébaux, and Brian Williams. RAO*: An Algorithm for Chance- Constrained POMDPs. In AAAI Conference on Artificial Intelligence, volume 30, 2016. 29. [Schrittwieser et al., 2020] Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, Timothy Lillicrap, and David Silver. Mastering Atari, Go, chess and shogi by planning with a learned model. Nature, 588(7839), 2020. 30. [Silver et al., 2016] David Silver, Aja Huang, et al. Master- ing the game of Go with deep neural networks and tree search. Nature, 529(7587), 2016. 31. [Silver et al., 2017] David Silver, Julian Schrittwieser, et al. Mastering the game of Go without human knowledge. Na- ture, 550(7676), 2017. 32. [Silver et al., 2018] David Silver, Thomas Hubert, et al. A general reinforcement learning algorithm that mas- ters chess, shogi, and Go through self-play. Science, 362(6419), 2018. 33. [Sokota et al., 2021] Samuel Sokota, Caleb Y. Ho, et al. Monte Carlo Tree Search with Iteratively Refining State Abstractions. Advances in Neural Information Processing Systems (NeurIPS), 34:18698-18709, 2021. 34. [Soualhia et al., 2020] Mbarka Soualhia, Foutse Khomh, and Sofiène Tahar. A Dynamic and Failure-Aware Task Scheduling Framework for Hadoop. IEEE Transactions on Cloud Computing, 8(2):553-569, 2020. 35. [Sunberg and Kochenderfer, 2018] Zachary N. Sunberg and Mykel J. Kochenderfer. Online Algorithms for POMDPs with Continuous State, Action, and Observation Spaces. In International Conference on Automated Planning and Scheduling (ICAPS), volume 28, 2018. 36. [Thrun et al., 2005] Sebastian Thrun, Wolfram Burgard, and Dieter Fox. Probabilistic Robotics. MIT Press, 2005. 37. [Wan and Van Der Merwe, 2000] Eric A. Wan and Rudolph Van Der Merwe. The Unscented Kalman Filter for Non- linear Estimation. In Adaptive Systems for Signal Pro- cessing, Communications, and Control Symposium (AS- SPCC), pages 153-158. IEEE, 2000.