acceptodds
Under review as a conference paper at ICLR 2027

Deceptive Planning via Last Deceptive State

Abstract

Existing deceptive planning methods face two key limitations. Graph-based deceptive path planning (DPP) splits deception into two phases via a Last Deceptive Point (LDP), but its switching criterion can trigger premature exposure when decoy goals lie near the optimal route to the real goal. The Deceptive Decision Making (DDM) framework handles MDPs via constrained linear programming, yet it optimizes deception uniformly across all states—failing to account that once the agent is sufficiently close to the real goal, continuing deceptive actions not only increases path length but also prolongs the exposure of its true intention. We introduce the Last Deceptive State (LDS) concept within deterministic MDPs and propose LDS-guided deceptive planning (LDS-DP), a framework that integrates the phase-switching intuition of DPP with DDM's LP formulation. LDS-DP identifies the value-maximal LDS candidate through V-differences, then decomposes planning into a deceptive linear programming phase and a shortest-path truthful phase, thereby addressing the premature-exposure issue of DPP while eliminating the post-LDS inefficiency of DDM. Experiments in deterministic and near-deterministic grid worlds show that LDS-DP preserves DDM's deception quality while shortening the post-LDS phase, with the two-phase advantage being robust to mild stochasticity.

Primary area:
applications to robotics, autonomy, planning
Keywords:
deceptive path planning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_P5JfOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes Last Deceptive State-guided Deceptive Planning (LDS-DP). It selects a state classified as deceptive that has the highest value for the real goal, uses a DDM-style linear program to plan from the start to that state, and then follows a shortest path to the real goal. The authors motivate this design by arguing that DPP can expose the real goal prematurely and that DDM can continue taking costly deception-aware actions after the last deceptive state. Experiments in deterministic and mildly stochastic grid worlds compare LDS-DP with DPP, DDM, and other baselines. They report shorter paths after the last deceptive state and broadly similar measured deception to DDM.

Critical strengths

A clear, implementable approach to the paper's chosen objective. Given the objective of placing the last deceptive state as close as possible to the real goal and then minimizing travel after that state, the paper provides a concrete procedure: select a switching state using precomputed goal values, plan a deception-aware route to it, and follow a shortest path thereafter. This makes the chosen objective operational and allows its consequences to be evaluated. The strength of this contribution depends on the separate question of whether this objective is preferable to optimizing deception over the complete trajectory.

Critical weaknesses
  1. The paper does not justify its ordering of optimization objectives.LDS-DP first fixes the deceptive state closest to the real goal, then minimizes deception cost on a route to that state, and finally follows a shortest path. This prioritizes a short post-LDS tail before considering the deception and travel cost of the complete route. It is unclear why this ordering is preferable to a route with a somewhat earlier LDP but stronger deception, fewer truthful states, or lower cost overall. The theoretical result establishes a shortest truthful tail under the stated assumptions; it does not establish that this choice improves the overall deception-travel trade-off. The experiments report similar mean real-goal posteriors for LDS-DP and DDM, rather than an improvement in whole-trajectory deception, and do not report deceptive density or directly compare their full-route deception objectives. This matters because the paper presents DDM's continued optimization after the LDS as a deficiency, whereas DDM deliberately optimizes deception over the complete trajectory.

  2. The claimed LDS contribution is insufficiently distinguished from DPP's LDP. The trajectory-level definition of LDS closely matches DPP's LDP. DPP already aims to bring the LDP as close as possible to the real goal, characterizes the closest deceptive node as the limiting boundary, and explicitly discusses finding it by evaluating nodes. If the DPP baselines expose the goal earlier, the cause may lie in their particular target-selection or path-generation procedures, rather than in the LDP concept or criterion. The paper should state which specific limitation of those procedures its state selection resolves and what, if anything, is conceptually new about LDS.

  3. The first-stage planner appears to be a direct adaptation of DDM. Once the switching state is fixed, the paper uses DDM's deception cost and LP formulation, changing the absorbing target from the real goal to the selected state. This is a concrete integration, but the paper does not clearly identify a new optimization mechanism in this stage or explain what it achieves beyond applying DDM to a different terminal state. In combination with the close relationship between LDS and LDP, this leaves the methodological contribution insufficiently differentiated from the two cited works.

Questions for authors
  1. Justification of the optimization objective: Why is it appropriate to choose the deceptive state closest to the real goal before optimizing the path from the start? A path through this state may have a costly or temporarily truthful prefix, while a path with a more distant LDP may be more deceptive over its full duration. What assumption, application objective, or result establishes that minimizing the final truthful tail should take priority over whole-trajectory deception cost, deceptive density, or the time of first exposure? Without such a justification, it is difficult to assess whether the proposed method solves the motivating problem or simply optimizes a different metric from DDM.

  2. Evidence for the claimed advantage of this objective: The paper already compares mean real-goal posterior along the trajectories and finds no significant difference between LDS-DP and DDM. Can the authors report, under a common observer model, deceptive density or the fraction of truthful states, first exposure, and each method's full-trajectory deception cost, alongside path length? A controlled comparison that varies the switching state while holding the first-stage planner fixed would help show whether prioritizing the closest deceptive state improves whole-route deception or its trade-off with travel cost, rather than only shortening the final tail by construction.

Reviewer_T4RcOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Last Deceptive State (LDS) and LDS-guided deceptive planning (LDS-DP). LDS-DP selects the state d_c^* with the highest V_gr from the deceptive states set. The state d_c^* decomposes trajectory planning into two phases: stage 1 (the deceptive LP phase) and stage 2 (the truthful phase). Stage 1 follows the state-action occupancy measure in DDM and uses linear programming with d_c^ as the target* to optimize the deception cost. Stage 2 uses the shortest path from d_c^* to the real goal. LDS-DP supports both exaggeration and ambiguity, and a theoretical analysis shows that d_c^* is a critical deceptive state. The experiment compares LDS with DPP, DDM, AM, and Honest baseline on 40 grid-world problems under deterministic and near-deterministic transitions, showing that the two-phase framework can address the premature-exposure problem of DPP and shorten the post-LDS phase of DDM.

Critical strengths

The paper presents a useful and straightforward planning heuristic, and has clear practical algorithmic value. With a clear switching state, it can minimize the deception cost with LP only in stage 1, and use the shortest path to avoid the deceptive detours after the exposure of its true intention.

Critical weaknesses

The novelty of the proposed LDS is limited. Although the paper credits DPP for the LDP and the two-phase framework, LDS seems to largely overlap with the existing LDP proposed by Masters & Sardina (IJCAI 2017). Specifically, LDP is already defined as the last deceptive node in the trajectory, followed by all truthful nodes, the same as the core definition of LDS. Furthermore, the two-phase planning concept has already been proposed there, and they already choose the LDP target that maximizes path completion.

The value function formulation is unclear. Section 3.2 follows Savas et al. (AAAI 2022) to use a soft Bellman equation, but in Section 4 it is directly assumed that V_gr = -J*, not a non-zero temperature soft value setting. Furthermore, Section 5 sets \gamma=1, while Savas et al. explicitly limit \gamma in (0,1) to ensure the finite solution. With \gamma=\tau=1, the soft value on an 8-connected grid would diverge. Hence, the theory does not cover the value model used in the experiments, which can likely affect the correctness of the experiment results.

Questions for authors
  1. Please clarify the further improvements of the LDP and LDS formulation, for example, whether the optimal switching point/state under the same assumptions is the same; whether the premature exposure issue is a fundamental limitation of LDP, or just a limitation of DPP under specific situations.
  2. For calculating V_g in the experiment, what method is used? Softmax Bellman backup or max backup? When using \gamma=1, how do you ensure the finiteness and the convergence of the soft value?
  3. Savas et al. assume all candidate goal states are absorbing, while this work lets decoy goals be ordinary non-absorbing states. In the experiment, what transition dynamics are used for the DDM baselines?
  4. How effective is the deceptive LP, and how necessary is it? Consider simply changing stage 1 to use the shortest path to demonstrate this.
Reviewer_QTMHOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes LDS-DP, a two-phase deceptive planning framework that combines LP-based deceptive planning with shortest-path execution. It aims to address premature exposure in DPP and unnecessary detours in DDM. Experiments on 40 grid-world problems show reduced post-LDS steps while largely preserving deception quality in the exaggeration setting.

Critical strengths
  1. Clear problem formulation and intuitive design. The paper identifies limitations in DPP and DDM and proposes a simple two-phase framework to balance deception and path efficiency.

  2. Relevant experimental evaluation. Experiments cover 40 grid-world problems, multiple baselines, and deterministic and mildly stochastic settings. The results support the effectiveness of LDS-DP in reducing post-LDS steps while preserving deception quality in the exaggeration setting.

Critical weaknesses
  1. Overall efficiency is not consistently improved. The optimality guarantees for the two individual stages do not establish optimality of the combined policy. In the deterministic setting, LDS-Amb has a trajectory cost of 1.321, higher than DDM-Amb at 1.146. Thus, shortening the post-LDS path does not necessarily reduce overall trajectory cost. The scope of the overall efficiency claims needs clarification.

  2. Insufficient ablation studies. The experiments do not isolate the contribution of the LDS selection rule from that of the two-phase design. Comparisons with alternative switching rules, while keeping the remaining planning procedure unchanged, would help establish the value of the proposed LDS criterion.

Questions for authors
  1. The paper establishes optimality properties for the LP-based first stage over a reduced state space and uses a shortest path in the second stage. However, these component-wise properties do not necessarily imply lower overall trajectory cost. In the deterministic setting, LDS-Amb has a trajectory cost of 1.321, compared with 1.146 for DDM-Amb. How should this result be interpreted in relation to the paper's efficiency claims? Can the authors clarify the objective and guarantees of the complete two-stage policy, and specify the conditions under which it is expected to improve overall trajectory cost?

  2. Can the authors compare LDS-DP with two-phase variants using alternative switching rules to isolate the contribution of the value-maximal LDS selection criterion?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.