Addressing Myopic Constrained POMDP Planning with Recursive Dual Ascent

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-07 04:05:54

Abstract: Lagrangian-guided Monte Carlo tree search with global dual ascent has been applied to solve large constrained partially observable Markov decision processes (CPOMDPs) online. In this work, we demonstrate that these global dual parameters can lead to myopic action selection during exploration, ultimately leading to suboptimal decision making. To address this, we introduce history-dependent dual variables that guide local action selection and are optimized with recursive dual ascent. We empirically compare the performance of our approach on a motivating toy example and two large CPOMDPs, demonstrating improved exploration, and ultimately, safer outcomes.

Main paper: 
 introduction: 
 Deploying autonomous systems in complex environments requires methods for safe planning under uncertainty. Constrained partially observable Markov decision processes (CPOMDPs) are mathematical models that codify decision making problems whose solutions must satisfy cost constraints under both outcome and state uncertainty (Kochenderfer, Wheeler, and Wray 2022; Kim et al. 2011; Poupart et al. 2015) . From robotics systems (Kurniawati 2022) to geological carbon sequestration (Corso et al. 2022) , the CPOMDP framework enables safe policy generation in a diverse set of applications entailing uncertainty.Offline solutions find approximately optimal policies but are limited to small discrete state, action, and observation spaces. Online methods can scale to larger spaces by searching across reachable outcomes. For example, costconstrained partially observable Monte Carlo tree search (CC-POMCP), searches for safe actions online using a Lagrangian-guided heuristic that trades off future costs and rewards through dual variables λ (Lee et al. 2018) . Crucially, a single set of global dual variables are optimized by dual ascent and shared between all history nodes during search. Lagrangian-guided action selection with global dual variables can lead to myopic decision making. Consider the simple CPOMDP depicted in Figure 1 , where an agent must maximize a terminal reward R while satisfying a cost C ≤ 1. The optimal strategy takes a 1 followed by a 2 towards a belief b 4 that yields maximal reward while satisfying the cost constraint. However, guiding search with a global dual parameter will fail to explore the optimal action sequence, Figure 1 : A CPOMDP illustrating myopic decision making when guiding search with global dual variables. With a global λ, search explores either the cautious green belief or the budget violating red belief and misses the optimal, feasible blue belief.as large dual variables will explore the cautious low-reward node b 2 while small dual variables will explore the infeasible high-reward node b 3 . Exploring the optimal node requires a 45 different strategy after taking the first a 1 action.To address this problem, we augment Lagrangian-guided Monte Carlo tree search (MCTS) (Silver and Veness 2010) algorithms with history-dependent, local dual variables. These local variables are optimized recursively by dual as-50 cent at each history node against local constraint violations. By adapting safe action selection to local constraint violations in different beliefs, we can better explore optimal safe paths, ultimately yielding better policies.To evaluate our approach, which we denote by appending 55 a '+' to the underlying algorithms, we conduct experiments in both discrete and continuous spaces on an illustrative small problem and two larger CPOMDPs. Results demonstrate that constrained MCTS with global dual parameters can lead to either excessively risky or cautious exploration, 60 issues our modifications address.In summary, our main contributions are to (i) highlight myopic decision making in CPOMDPs, (ii) propose recursive dual ascent with history-dependent dual variables to improve online dual-ascent-guided CPOMDP planning, and 65 (iii) empirically demonstrate improved search efficiency and constraint satisfaction in three problem domains.CPOMDPs CPOMDPs provide a structured approach for optimizing decision making under uncertainty 70 when considering competing objectives (Roijers et al. 2013) . A CPOMDP can be defined with the tuple ⟨S, A, O, T, Z, R, C, ĉ, γ, b 0 ⟩. At each step, an agent in a partially observable state s ∈ S takes an action a ∈ A, transitions to a successor state, and emits an observation o ∈ O. Transitions and observations follow Markov distributions T and Z, which model outcome uncertainty and partial observability. Each transition emits an immediate reward following R and k immediate costs following C. Optimal CPOMDP planning selects actions to maximize expected cumulative rewards while satisfying expected cumulative cost budgets ĉ.As states are partially observable, agents must plan using histories of past actions and observations h t , which may be succinctly represented as instantaneous beliefs over state b t = b(s t ) = P r(s t = s | h t ). In infinite horizons, CPOMDP policies π optimize expected discounted cumulative reward V π R from an initial belief b 0 such that expected discounted costs V π C satisfy their budgets in expectation:max π V π R (b 0 ) = E π ∞ t=0 γ t R(b t , a t ) | b 0 (1) s.t. V π C k (b 0 ) = E π ∞ t=0 γ t C k (b t , a t ) | b 0 ≤ ĉk ∀ k,where γ ∈ (0, 1) is a discount factor that bounds objectives.This constrained optimization problem can be expressed equivalently through its LagrangianEQUATIONwhere λ are dual variables.Online Planning in CPOMDPs Offline solution methods to CPOMDPs, such as point-based backups (Kim et al. 2011) , approximate linear programming (Poupart et al. 2015) , column generation (Walraven and Spaan 2018) , and projected gradient ascent (Wray and Czuprynski 2022), cannot be applied to continuous or large problems. In contrast, online planning can scale to large state spaces by consider-100 ing the set of reachable histories at runtime. Online solution methods have coupled search with safety critics from offline solutions (Undurti and How 2010) or previous searches (Parthasarathy et al. 2023) . Rather than rely on a critic, cost-constrained partially observable 105 Monte Carlo planning (CC-POMCP) (Lee et al. 2018) optimizes Equation (1) online directly by interleaving a Lagrangian-guided partially observable MCTS with dual ascent. In MCTS, actions and their resulting transitions are sampled to gradually build a search tree that estimates re-110 ward and cost values.In CC-POMCP exploration, actions are chosen at each history node h to maximizeQ ⊕ λ (h, a) = Q R (h, a) + λ ⊤ Q C (h, a) + κ log N (h) N (h, a) ,(3) where Q R and Q C are reward and cost action value estimates, λ are dual variable estimates, and node visitation counts N are used for optimistic exploration (Auer, Cesa-Bianchi, and Fischer 2002) .In between search simulations, dual variable estimates are updated by gradient descent on Equation (3), updating away from cost violations at the root node. 1 Crucially, though these updates aim to satisfy constraints at the root node, the same dual variables are then used globally for action selection in subsequent decisions. To extend CC-POMCP to continuous action and observation spaces, the constrained partially observable Monte Carlo planning with observation widening (CPOMCPOW) algorithm uses double progressive widening to artificially limit branching factors based on node visit counts (Jamgochian, Corso, and Kochenderfer 2023) .Lagrangian-guided action selection with global dual variables as presented in Equation ( 3) can lead to myopic decision making. Consider the simple CPOMDP depicted in Figure 1 , where an agent must maximize reward while satisfying a cost budget ĉ = 1. Guiding search with a global dual parameter will fail to explore the optimal action sequence, because exploration of the optimal node would necessitate a different strategy than used to take the first action.To address this issue, we propose augmenting Lagrangian-guided tree search algorithms to enable history-dependent constrained exploration. In our augmentation, each history node maintains its own local dual variables λ(h) used to guide local action selection. These dual variables are optimized separately using a recursive dual ascent that updates them away from constraint violations in their subtrees. We refer to our augmentations by adding a '+' to the underlying algorithms.Algorithm 1 depicts our adaptation applied to CC-POMCP, with differences to the underlying algorithm highlighted in blue. The SIMULATE procedure of a constrained MCTS algorithm recursively simulates trajectories to a fixed depth and backpropagates rewards and costs to iteratively build a search tree. A ROLLOUT, where the algorithm runs an estimate policy to completion, provides an initial value approximation when leaf nodes are first encountered. In our augmentation, leaf nodes also initialize local dual variables with the values of their parents (line 13). Actions are then selected using local dual variable estimates (line 16), with optimism guided by Equation (1) (line 27) and a stochastic policy of best actions formed by the STOCHASTICPOLICY method of Lee et al. (2018) .While using backpropagated rewards and costs to update value and single-step cost estimates (lines 21-23), our augmentation performs dual ascent to guide local dual variables to penalize constraint violations in their associated subtrees (line 24). Doing so requires forward propagating cost estimates for earlier actions to estimate the remaining budget in each subtree ĉrem . This is done by using the single-step cost estimates c to estimate ĉ(hao) = (ĉ(h) -c(ha))/γ (line 21). This recursive dual ascent procedure enables history 1 The term dual ascent arises from convention that minimizes the objective rather than maximizing it. a ∼ UCBPOLICY(h, λ, 0, 0)7: λ ← [λ + α i (Q C (h, a) -ĉ)] 8:return UCBPOLICY(h, λ, 0, ν) 9: procedure SIMULATE(s, h, ĉrem ,d) 10:if d = 0 11: return [0, 0] 12: if h / ∈ T 13: λ(h) ← λ(h \ a -o -) 14: T (ha) ← (N init , Q R,init , Q C,init , cinit )∀a 15: return ROLLOUT(s, h, ĉrem , d) 16: a ∼ UCBPOLICY(h, λ(h), κ, ν) 17: s ′ , o, r, c ← G(s, a) 18: [R, C] ← [r, c] + γ • SIMULATE(s ′ , hao, ĉrem-c(ha) γ , d -1) 19: Q R (ha) ← Q R (ha) + R-Q(ha) N (ha) 20: N (h) ← N (h) + 1 21: N (ha) ← N (ha) + 1 22: c(ha) ← c(ha) + c-c(ha) N (ha) 23: Q C (ha) ← Q C (ha) + C-Q C (ha) N (ha) 24: λ(h) ← [λ(h) + α N (h) (Q C (ha) -ĉrem )] + 25: return [R, C] 26: procedure UCBPOLICY(h, λ, κ, ν) 27: Q ⊕ λ (h, a) = Q R (h, a) + λ ⊤ Q C (h, a) + κ log N (h)N (h,a)28:return STOCHASTICPOLICY(Q ⊕ λ , ν)nodes to adapt their exploration strategies based on local constraint violations in their subtrees. This results in more accurate value estimation, as future nodes can make decisions appropriate to their local constraint violations.As with CC-POMCP, planning at each step entails interweaving simulations (line 5) with dual ascent at the root node (line 7). After executing the best root node policy, planning at the next step necessitates updating the belief using new observations and the remaining cost budget using the immediate costs associated with the executed actions, which can be estimated using c. Though not shown, our augmentations extend trivially to CPOMCPOW, which uses progressive widening to overcome the multitude of branching in continuous problems. We note that our method could also be used to plan online in recursively constrained POMDPs (RC-POMDPs), which overcome inconsistencies of Bellman optimality in CPOMDPs through the recursive application of constraints (Ho et al. 2023) .In this section, we compare the overall performance and 190 search efficacy with and without local dual parameters in three CPOMDPs of varying sizes. Our experiments are performed in Julia using the POMDPs.jl framework (Egorov et al. 2017 ). Anonymized code with implementation details is available for peer review and will be released upon publication.We first briefly overview our target problem domains, denoting whether their state, action, and observation spaces are discrete (D) or continuous (C):1. Constrained Tiger (D, D, D) Adapted from Kaelbling, Littman, and Cassandra (1998) Search Efficacy Generating accurate action value estimates within a Monte Carlo search tree requires repeated node visits. It is therefore desirable for an online solver to spend most of its planning budget simulating the highest reward nodes that satisfy constraints. We first see that our modifications can improve search efficacy by spending more time exploring optimal action sequences. Table 1 : Statistics comparing the exploration and execution of initial actions +1, +5, +10 in Constrained LightDark across all runs. CPOMCPOW+ concentrated search on the optimal action for a larger fraction of the 6 × 10 5 search queries, and ultimately chose +5 in more trials.For example, in the Constrained LightDark CPOMDP, a = +5 is the best initial step the agent can take without violating the constraint above s = 12. In Table 1 , we see that the modified solver concentrates more of the search around a = +5 despite it having subtrees with both unsafe and safe subsequent actions. This ultimately results in more trials that select the optimal action.We see similar behavior in the Constrained Tiger CPOMDP. To visualize this, Figure 2 compares key areas of the converged search trees for the first two actions. On the right is CC-POMCP with global dual variables and on the left is our proposed modification with local dual variables.In the CC-POMCP solution, the root node global dual variable λ g converges low, confining the search to actions with high cost and high reward. As a result, the agent immediately opens a door, often incurring an immediate cost violation. In the CC-POMCP+ solution, the root node dual variable converges higher than the subsequent dual variables, allowing the search to explore low cost low reward nodes that listen for the tiger before safely opening a door. This safe exploration is reflected by the larger visitation counts for safe actions.Performance Table 2 compares mean rewards and costs on the three problems; lower rewards that satisfy cost constraints are preferred over violating constraints. In Constrained LightDark, CPOMCPOW+ achieves similar average rewards as CPOMCPOW without violating the constraint limit, as seen in Figure 3 . CPOMCPOW+ is more likely to explore actions at the safety limit because it can avoid subsequent high costs after taking risky initial steps. In contrast, CPOMCPOW+ had similar performance as the original CPOMCPOW when run on Constrained Spillpoint. In problems with small cost budgets, when no cost violation is allowable, a high-value global dual variable suffices to safely guide action selection. When run on Constrained Tiger, the modified algorithm obtained lower discounted total rewards but halved cost violations when over half of trials without the modification violated constraints. with history-dependent dual variables. The resulting finetuned algorithm guides expected action values to converge to the best outcome within their control. The final decision is made with improved information and therefore leads to 265 improved outcomes.Constrained POMDP solvers optimize planning objectives while satisfying cost constraints under state and outcome uncertainty. Constrained Monte Carlo tree search methods 270 guided by global dual variables can be myopic, yielding excessively risky or cautious actions as a result of improper exploration. To address this, we proposed local dual variables to guide safe, history-dependent action selection, and optimized them using recursive dual ascent. We empirically 275 demonstrated that our approach resulted in a decrease in simulations spent exploring unsafe or overly cautious actions, ultimately improving safe outcomes.Limitations Our modification only benefits problems that require adapting safe exploration at different beliefs. Addi-280 tionally, our modifications still inherit the other shortcomings of their underlying algorithms, namely, lack of anytime safety guarantees and high variance in costs and returns. 
 
 Appendix:  


Decision: The reviewers agree that this paper makes an interesting and valuable contribution to solving Constrained POMDPs.

We ask the authors to follow the reviewers' recommendations and include additional clarifications to improve the clarity and presentation of the paper.

Reviews: review: strength_weakness: strength_weakness: 1. The search efficacy section explaining the choice of action for constrained light-dark CPOMDPP can be improved. It is not directly clear why a=+5 is the best initial action. I understand the space is limited, but adding a few sentences to improve the example would go a long way in improving the readability. The description of CPOMDP Problems can be reduced to make space if needed.

2. Shouldn’t the probabilities in the last column of Table 1 sum to 1? I am not sure if I am missing something.
questions: questions: 1. Why does the modification only benefit problems that require adapting safe exploration at different beliefs?

2. What happens if the solution that conforms to the given constraint/budget does not exist?

3. What is $hao$ in line 169?

4. Shouldn’t the probabilities in the last column of Table 1 sum to 1? I am not sure if I am missing something.
strength_weakness: strength_weakness: The key idea behind the contribution is fairly simple in the end, but it is a natural step to follow to address a weakness of the state of the art.

As far as I understand, the paper requires some familiarity with the state-of-the-art to properly understand why CC-POMCP's exploration behavior fails. The explanations are too "high-level" for me.  It seems to me that one needs to understand what the StochasticPolicy() function does.
In Algorithm 1, I don't see where $\nu$ is set (and don't know what is its purpose since its linked to StochasticPolicy()).

It would seem important to me to discuss the theoretical guarantees of the proposed approach, whatever they are.
[As far as I remember, Bellman's optimality principle does not apply to C-POMDPs (there are temporal inconsistencies), so that a POMCP-based algorithm cannot come with theoretical guarantees.]



Other comments (not really weaknesses):
--------------

- Table captions are usually above the table itself.

- "... converges low" and "... converges higher" are unusual to me.
  But that still may be proper English.

- In Table 2, I would suggest adding intermediate horizontal lines between problems, maybe using \cmidrule{2-8} (if using booktabs).

<- "to explore low cost low reward nodes"
-> "to explore low-cost low-reward nodes" ??

- [References]: There is no "in" field in (Ho et al., 2023).

- [References]: There is no "in" field in (Parthasarathy et al., 2023).

- [References]: There are too many capital letters in the title of (Kurniawati, 2022).
questions: questions: [POST-REBUTTAL COMMENT]
Let me just thank the authors for their responses.
I have no further comment at this stage.


1. How does StochasticPolicy() work?
   What is $\nu$?
  
2. How is $\nu$ set in Algorithm 1?

3. Any comment about weights $\alpha_i$? How is it defined in the experiments? Is it as in previous work?
strength_weakness: strength_weakness: I don't have much to write in terms of major weaknesses because I find it well written for the scope of the paper.

1. Although the motivation and empirical results are convincing, I would have liked if there was more discussion on how the local history-dependent dual variables may impact (rate of) convergence and optimality of the algorithm. It is not directly clear to me that if each local dual variables converge to its own optimal value, that the tree search would (asymptotically) converge to the optimal value for the original problem of Eq. 1.

2. I believe a citation for the Lagrangian form (Eq. 2) of the constrained optimization problem is warranted.

3. The constraint violation rate is not well defined.
questions: questions: 1. Does the augmentation of local dual variables affect the asymptotic convergence and optimality of the CPOMCP(OW) algorithm for CPOMDPs?

2. The constraint violation rate is not defined. Is it the number of runs that violate the cost constraints at the root divided by the total number of runs?


POST REBUTTAL
Thank you for your response. My questions have been sufficiently answered.