acceptodds
Withdrawn from ICLR 2027

Polyhedral Reinforcement Learning: Deep RL with Geometric State Representations

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

In many reinforcement learning (RL) problems, the state already has geometric structure: feasible regions, guards, reachable sets, or collections of objects are represented explicitly by linear constraints. Standard deep RL often discards this structure by flattening the state into a fixed-length vector, forcing the network to recover relationships already explicit in the problem description. We introduce polyhedral reinforcement learning, in which states are finite unions of polytopes and actions induce transitions between them. Representing such states poses a distinctive learning problem: a polytope is a variable-sized, unordered object with several mathematically equivalent but computationally different descriptions. It may be specified by its vertices, by the half-spaces that bound it, by the incidence relations between vertices and facets, or, in structured domains, by a canonical matrix or spatial rendering. We therefore develop representation-aware actor–critic architectures matched to these descriptions: DeepSets over vertices and half-spaces, graph neural networks over relational structure, and convolutional encoders over canonical matrices and rasterised projections. Timed automata provide a controlled comparison in which the same system can be presented through real-valued clock valuations or through its symbolic polyhedral zone. Under the same training budget, point-based agents perform poorly when decisions depend on relations between clocks, while several polyhedral encoders achieve near-perfect success; this advantage largely disappears when such relations are irrelevant. Across five additional domains with intrinsically polyhedral states, no representation dominates universally: performance is strongest when the encoding directly exposes the geometric relationships relevant to the decision. These results show that geometric state representation can provide a powerful inductive bias for RL, and that its benefit depends on the task's relational structure.

Primary area:
reinforcement learning
Keywords:
Reinforcement learning, state representation, geometric deep learning

Reviews

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

This paper studies how reinforcement learning can use polyhedral states directly. It formalizes states as finite unions of polytopes and pairs PPO or DQN with encoders for half-spaces, vertices, relational graphs, difference-bound matrices, and rasterized projections. The experiments compare concrete clock values with symbolic zones in timed automata, then compare encodings across five domains with native geometric structure. The results suggest that exposing geometry relevant to decisions can improve performance under a fixed training budget, although no representation is best across all tasks. I view this as a useful exploratory study of state representation. The motivation is reasonable, and both the positive and negative results are informative.

Critical strengths
  1. Many planning and control problems already provide feasible regions, clock constraints, and spatial adjacency relations, so using this structure directly is well motivated. The two levels of set aggregation also accommodate varying numbers of constraints or vertices and arbitrary component orderings.
  2. The experiments include informative contrasts. Geometric representations have a clear advantage on GridTimed, while the point baseline is competitive on ModeSel. The vertex encoder largely fails on TRMGrid, and there is no clear ranking on Rush Hour or Lawn Mower. These results help establish when the choice of representation matters.
  3. On PHA Navigation, H-Rep augmented with a few neighborhood statistics achieves the highest mean on the easy and hard tiers and exceeds the GNN on all three tiers. This is an interesting finding about the value of selected relational summaries compared with access to the full graph.
Critical weaknesses
  1. Practical value and scope. I find the idea of giving RL direct access to geometry appealing, but would like a clearer account of which practical problems naturally provide the required polyhedral states and what prior knowledge is needed to construct and update them. The benchmarks cover several structured settings, but their connection to practical applications could be more concrete. One representative application could illustrate where the geometric input comes from, what difficulty existing approaches face, and how this framework helps. This would make its value and scope easier to assess.

  2. Contribution relative to existing methods. The framework builds on established DeepSets, GNN, CNN, and RL methods, with its contribution lying mainly in the unified formalism, representation choices, and empirical insights. Please clarify what reusable capabilities or insights this perspective adds to existing approaches to structured state representation. The most direct evidence concerns gains over a point-based MLP under a fixed sample budget. For planning, control, or symbolic methods that already exploit geometric constraints, what difficulty is a learned policy intended to address?

    Positioning the work primarily as a study of RL representations, and explaining how it complements domain-specific methods, would be reasonable. Broader claims of practical solving advantages would need corresponding evidence. My concern is the clarity of this positioning and motivation, rather than an exhaustive comparison with conventional algorithms.

  3. Interpretation of the central comparison. The timed-automata experiments compare current clock values with zones, which describe sets of clock valuations satisfying constraints. Please briefly explain how these inputs correspond, what information the zones incorporate from the environment or execution history, and whether both representations preserve the same task and action semantics. This would help clarify the respective roles of structured encoding and supplied symbolic information in the observed gains.

Questions for authors
  1. Which practical problems are best suited to this framework? Could one representative application illustrate how polyhedral states are obtained and what limitation of existing approaches motivates their use?
  2. What is the main added value over existing structured RL representations and domain methods that directly handle constraints? Which aspects are supported by the current results?
  3. How do concrete states and zones correspond in the timed-automata experiments? What information does each input contain, and are they compared under the same task and action semantics?
Reviewer_zbY3OpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper claims that representing states in reinforcement learning problems as polytopes and actions as their transformations can lead to faster training and better solutions.

Critical strengths
  • I think the problem formulation is generally interesting. The search for relevant prior art has revealed that this formulation has been discussed in the area of optimization of compilers [1]. Authors of [1] has created a Gym, but has not proposed the solution.

[1] Brauckmann, Alexander, Andrés Goens, and Jeronimo Castrillon. "A reinforcement learning environment for polyhedral optimizations." arXiv preprint arXiv:2104.13732 (2021).

Critical weaknesses
  • The treatment of related work is very superficial. For example the work [1] is not mentioned despite being very relevant. Some tested domains are deterministic can very likely can be solved using temporal planning [2]. While the temporal planners might not work on all problems, it might serve as a very strong baseline.
  • From the experimental results I am not convinced the proposed representation delivers the benefits. CNN based representation is among the best on 2 out of 3 problems in Figure 2 and generally very good on problems in Figure 3.
  • The experimental comparison includes randomly selected toy problems without any baselines. Problems like PHA Navigation and Lawn Mover seems to be motivated by robotics and I very certain robotics domain would have solvers for this. Why there is no comparison? For example solving Rush Hour has a dedicated paper [3], which compiles the domain to symbolic langage and solves it with dedicated solvers. This lack of interesting problems raises doubts into usefulness. of the theme.
  • Encoding set of inequalities for neural networks has been treated in [4] in the area of optimising MILP solvers. This seems to me to be very related to the proposed work and should be at least mentioned.
  • The paper is non reproducible. Implementation details are missing as well as details about the problems.

[2] Eyerich, Patrick, and Robert Mattmüller Gabriele Röger. "Temporal fast downward." Department of Computer Science, University of Freiburg (2009). [3] Cian, Lorenzo, Talissa Dreossi, and Agostino Dovier. "Modeling and solving the rush hour puzzle." CEUR Workshop Proceedings. Vol. 3204. CEUR-WS, 2022. [4] Gasse, Maxime, et al. "Exact combinatorial optimization with graph convolutional neural networks." Advances in neural information processing systems 32 (2019).

Questions for authors
  • In the paragraph starting at line 275, you "render" the polytope to grid in order to use standard CNNs. Does not this contradicts you initial statement, that this representation destroys spatial representation?
  • The representation discussed at line 241 proposes "sets of sets" view. The theoretical validity of this construction is discussed in detail in [5].
  • Why there are no baselines?

[5] Pevny, Tomas, and Vojtech Kovarík. "Approximation capability of neural networks on spaces of probability measures and tree-structured domains." arXiv preprint arXiv:1906.00764 (2019).

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

This paper proposes RL implemented on top of polyhedral state representation. It demonstrates that polyhedral state representation provides a nice inductive bias that sometimes accelerates RL. This, along with several implementations of the structural network prior (use of DeepSet etc) is a meaningful contribution. Polytopes especially make sense in robotic applications. Ablations over several polytope representation provides useful information.

Critical strengths

paragraph 1 of the summary.

Critical weaknesses

The big issue of this paper is that it however tries to appear as a theoretical paper. I do not see any value the theorems in Section 2. All conclusions in theorems in Section 2 are reduced from existing theorems, and does not state any theoretical advantage of PMDP over standard MDP. It it just an MDP with a different state represnetation, just like any MDP which uses images or other forms of state representation.

Removing section 2 would allow adding useful figures for domains evaluated in section 4. Indeed, the conclusion at the end of 4.2 is delicately nuanced; Even if some domain is polyhedrally-representable, equivalent information could be deduced from other representation. I appreciate the nuanced argument, but this kind of delicate insight becomes intuitive if there were a detailed visual depiction of the example environment.

Three seeds on ModeSel is rather small.

I did not understand how the authors "measure how much of its optimal policy can be recovered from restricted state information", given an optimal policy.

Questions for authors

I did not understand how the authors "measure how much of its optimal policy can be recovered from restricted state information", given an optimal policy.

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

Related papers

Discussion (0)

Sign in to comment.