acceptodds
Under review as a conference paper at ICLR 2027

Cross-entropy optimization with prioritized constraints

Abstract

When constraints conflict, an optimizer must determine which requirements to preserve and which to relax. On the one hand, a priority ordering specifies which requirements take precedence. On the other hand, penalty-based formulations encode their relative importance through numerical weights. Depending on these weights, a solution can improve its weighted score while violating intended priorities. We introduce TierCEM, a variant of the cross-entropy method that incorporates strict constraint priorities directly into elite selection without requiring per-constraint importance weights. TierCEM works by sequentially filtering sampled candidates, from highest- to lowest-priority constraint. If and when a constraint eliminates all remaining candidates, TierCEM returns to the last nonempty set and selects elites with the smallest violations of that blocking constraint, recursively preserving satisfaction of all higher-priority constraints. We evaluate TierCEM on 2D navigation and contact-rich pushing tasks in proprioceptive and learned world-model settings. Experiments show that reversing the constraint ordering changes which constraints are violated under conflict. Prioritizing progress toward the task objective also enables TierCEM to relax lower-priority constraints when they would otherwise prevent further progress.

Primary area:
optimization
Keywords:
constrained optimization, cross-entropy method, hierarchical constraints

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_uct2OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper introduces TierCEM, a variant of the Cross-Entropy Method (CEM) for optimisation problems with conflicting, priority-ordered constraints. Unlike conventional penalty-based approaches, which require carefully tuned numerical weights to encode constraint importance, TierCEM explicitly specifies a lexicographic ordering over constraints. It sequentially filters candidate solutions by priority; when a constraint eliminates all remaining candidates, it returns to the previous nonempty set and selects candidates that minimise violations of the blocking constraint while preserving all higher-priority constraints.

The paper evaluates TierCEM on two-dimensional navigation and contact-rich Push-T robotic manipulation tasks, comparing it against scalarised CEM, hierarchical scalarised CEM, and constrained cross-entropy (CCE). Experiments using exact simulator states demonstrate that reversing constraint priorities changes which constraint is violated, while prioritising task progress prevents the optimiser from stalling to preserve all constraints. Further experiments using a learned DINO-WM world model and MLP-based constraint predictors show that this behaviour persists under imperfect predictions, although model errors can cause overly conservative behaviour or unsafe violations. Overall, the results support TierCEM as a simple, weight-free mechanism for priority-aware constraint relaxation in sampling-based planning. However, the evaluation is limited to simulated environments and does not establish formal safety guarantees or real-world robotic performance.

Critical strengths
  1. Explicit priority-based constraint relaxation. TierCEM integrates lexicographic constraint handling directly into CEM’s elite-selection mechanism, avoiding the need to tune numerical penalty weights to encode constraint priorities. When constraints conflict, it preserves higher-priority constraints and minimises violations of the first lower-priority constraint that cannot be satisfied. This is a practical and clearly articulated contribution that addresses a genuine limitation of scalarised optimisation.

  2. Consistent empirical validation across planning settings. Experiments in 2D navigation and Push-T manipulation demonstrate that reversing constraint priorities changes which constraints are violated, including when constraint evaluations rely on a learned world model. Comparisons with scalarised CEM and constrained cross-entropy further illustrate the trade-off between task completion and constraint satisfaction. These results provide convincing evidence that the proposed mechanism behaves as intended in the tested simulated environments, although they do not establish formal safety guarantees or real-world effectiveness.

Critical weaknesses
  1. Limited evidence for robustness and safety under learned-model errors: The evaluation of the learned world model shows that TierCEM’s behaviour can deteriorate when predicted constraint margins or dynamics are inaccurate, potentially resulting in constraint violation. Since the method is motivated by prioritising constraints, the absence of stronger evidence characterising when its priority guarantees hold and when model errors undermine them limits the strengths of the conclusions. The paper acknowledges these limitations, but the current evaluation does not establish reliable constraint satisfaction under realistic model uncertainty.

  2. Limited scope of empirical validation and uncertain advantage over existing methods. The experiments are confined to simulated navigation and the Push-T manipulation task. Although they demonstrate that TierCEM follows the specified priority ordering, they provide limited evidence that the approach offers a substantial practical advantage over existing constrained or hierarchical optimisation methods across a broader range of problems. In particular, the paper does not establish that its benefits persist in real-world robotics or more diverse settings where constraint conflicts and model errors may be more complex. This limits confidence in the generality and practical significance of the contribution.

Questions for authors
  1. Clarification on constraint-priority behaviour under model errors. The method sequentially filters candidates using predicted constraint margins. When using the learned world model, what guarantees, if any, remain that higher-priority constraints are preserved when a lower-priority constraint is relaxed? Given the reported constraint violations under dynamics mismatch, can the authors quantify how prediction errors affect the frequency and severity of higher-priority constraint violations? This would help establish the conditions under which TierCEM’s priority-based behaviour is reliable.

  2. Clarification of the empirical advantage over existing methods: The experiments show that TierCEM changes which constraints are violated when their priorities are reversed. Beyond demonstrating that the mechanism behaves as intended, can the authors provide evidence that it achieves a meaningful advantage over the scalarised and constraint CEM baselines in task completion and constraint violations, or robustness across random seeds? In particular, how sensitive are the results to the choice of constraint margins and the sampling budget?

Reviewer_FcMsOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2(+1)
Read review
Paper summary

The paper proposes TierCEM, a modification of the Cross-Entropy Method (CEM) that incorporates ordered constraints directly into elite selection. Sampled trajectories are filtered sequentially according to constraint priorities. If a constraint eliminates all candidates, the algorithm returns to the last nonempty set and ranks candidates by their margin on the blocking constraint. The claimed benefit is avoiding manually tuned penalty weights while preserving the prescribed priorities. Experiments in 2D navigation and Push-T, with exact and learned world models, demonstrate that reversing constraint priorities changes which constraints are violated.

Critical strengths
  1. Simple and interpretable priority handling. TierCEM directly represents constraint priorities without requiring relative penalty-weight calibration. This is practically convenient for black-box trajectory optimizers, particularly when constraint margins have different numerical scales.

  2. Clear qualitative validation of priority-dependent behavior. The controlled navigation experiments demonstrate that reversing the priority ordering changes which constraint is relaxed. Similar behavior is observed in Push-T with learned world-model predictions. These experiments establish that the proposed selection mechanism can implement the intended preference structure in the studied settings.

Critical weaknesses
  1. The optimization mechanism does not establish meaningful progress, even under strict feasibility.

The finite-sample priority-selection mechanism is mathematically consistent, but its broader motivation concerning task progress is not generally supported. More importantly, this is not merely a missing convergence analysis: the selection rule itself can favor stagnation even when strictly feasible goal-reaching solutions exist. The simple 1D counterexample below demonstrates that, in the large-sample limit, the algorithm can concentrate on actions with vanishing progress rather than reaching the goal. This reveals a structural limitation of the proposed optimization mechanism and raises fundamental questions about convergence and the ability to ensure meaningful progress.

Consider the one-dimensional system x0 = 0, x1 = u, with 0 < u < 2 and goal x = 1. Following the paper's task-progress definition, let

m_task(u) = 1 - |u - 1| (highest priority)

m_wall(u) = 2 - u (lowest priority)

Every u in (0,2) strictly satisfies both constraints, and u = 1 reaches the goal exactly. Nevertheless, because all filters pass, Algorithm 1 ranks candidates by m_wall and favors the smallest positive u, rather than u = 1. With a fixed elite count and sufficiently many samples from a distribution with positive density near zero, elite actions approach zero.

Thus, even with exact dynamics and a nonempty interior of the feasible region, the algorithm can concentrate on arbitrarily small positive progress. This does not establish inevitable stagnation in every execution, but it demonstrates that task-first ordering does not generally prevent it. The central anti-stalling motivation is therefore supported only empirically in selected scenarios, not by the optimization principle itself.

  1. Limited evidence of a significant practical advantage over existing optimization approaches.

The experiments primarily demonstrate that changing the ordering of constraint filters changes which constraints are violated. This behavior follows naturally from the selection rule and does not, by itself, establish superior optimization capability.

In Table 1, tuned hierarchical scalarization matches TierCEM's 20/20 success rate and zero higher-priority violations. In nominal exact-state Push-T (Table 2), CCE obtains comparable position error (21.29 vs. 20.63 px) while exhibiting only 0.2% lane violations, compared with 64.8% for TierCEM. Table 3 shows a meaningful advantage over CCE for distant goals, but these methods encode different preferences: CCE favors joint feasibility, whereas TierCEM prioritizes task progress. This comparison therefore does not isolate an optimization advantage under matched objectives.

Furthermore, the experiments largely reuse a constructed lane-obstacle conflict across different dynamics and representations. Generalization is questionable: Appendix B reports substantial degradation under tighter geometry, while Appendix C, Table 7 shows pronounced sensitivity to proposal variance. Changing the variance scale from 0.75 to 1.0 raises success from 2/5 and 0/5 to 5/5 for the two priority orderings; increasing the sample count at variance 0.75 does not improve success.

Avoiding penalty-weight tuning is useful, but the paper does not convincingly establish that this heuristic provides a substantial practical advantage over established hierarchical constraint-handling methods.

Questions for authors
  1. Progress and convergence. How does the proposed formulation address the counterexample above, in which all constraints are strictly feasible but maximizing the last-tier margin favors arbitrarily small task progress? Is any progress or convergence guarantee intended, or is avoiding stagnation strictly an empirical observation limited to the evaluated scenarios? Clarifying this would materially affect my soundness assessment.

  2. Practical significance. What evidence demonstrates an advantage beyond eliminating penalty-weight tuning? In particular, can the authors isolate the benefit of TierCEM over appropriately tuned methods implementing the same priority structure, rather than comparing different preference specifications? The sensitivity to proposal variance and geometry also raises questions about robustness. Evidence resolving these issues would materially affect my recommendation.

Reviewer_XgSzOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper presents TierCEM, a sampling-based optimizer that embeds lexicographic constraint priorities directly into the elite-selection logic of the Cross-Entropy Method. Rather than expressing constraint importance through numerical weights as in scalarized formulations, TierCEM filters candidates from highest- to lowest-priority constraint; when a filter empties the candidate set, it falls back to the last nonempty set and ranks elites by the smallest violation of the blocking constraint while recursively preserving all higher-priority constraints. The authors validate on 2D navigation and contact-rich Push-T tasks that reversing the priority order reverses which constraint is relaxed; prioritizing task progress prevents "safe-but-stalled" behavior; and the mechanism persists when margins are predicted by a learned world model.

Critical strengths

1.Expressing priorities as an ordering rather than weights sidesteps weight calibration entirely; the weight-sweep experiment convincingly demonstrates the fragility of hierarchical scalarization. 2. Only the elite-selection logic is modified, leaving the CEM update untouched; fully decoupled from candidate representation, dynamics model, and margin source, making it cheap to implement and easy to transfer. 3.Escalates from controlled experiments with exact margins to contact-rich dynamics to a learned world model; appendices proactively expose boundary conditions (geometry perturbations, inertial bodies, noisy signals, non-conflicting scenarios), which is credible.

Critical weaknesses

No formal results on elite-selection properties, fallback probabilities, or convergence behavior — thin for a top-tier venue.Lexicographic optimization is well-established; the delta over the closest prior work (CCE) is essentially the fallback ranking rule, so the incremental contribution needs stronger argumentation.The mechanism depends on per-tier empirical hit rates and degrades under narrow geometries and small sample budgets (visible in Appendix B and Table 4), yet no diagnosis or sample-complexity analysis is provided.

Questions for authors

The scalarized baselines standardize each term within the candidate population, but TierCEM's fallback ranking uses the raw margin value of the blocking constraint. Margins across constraints have very different units and numerical ranges. Could this bias elite selection toward constraints whose margins are naturally larger in magnitude? Should the fallback ranking be standardized, and was the conclusion tested for robustness to this choice?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.