REVIEW 3 major objections 5 minor 18 references
Training Cross-Morphology Embodied AI Agents: From Practical Challenges to Theoretical Foundations
T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read A single policy for many robot bodies is PSPACE-complete to learn.
desk verdict A useful framing but the headline hardness result is a known corollary and the interpretation overreaches. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is a structured POMDP whose state space is the disjoint union of each morphology's state space augmented with a hidden morphology index, paired with a morphology-agnostic observation model that maps every underlying state to a common observation space. The proof machinery is a log-space reduction from finite-horizon POMDP planning to HEAT for hardness, plus a depth-first belief-state enumeration argument for PSPACE membership. That combination locates the difficulty of cross-morphology learning in the single act of inferring which body the agent inhabits.
What would settle it
A polynomial-time algorithm that decides HEAT(P,H,K) for all finite inputs would refute the theorem, since the paper's n=1 reduction would then solve finite-horizon POMDP planning, a known PSPACE-complete problem. A reader could also test the practical claim by training a memory-based policy on the twelve cheetah variants while supplying a one-hot morphology identifier: if training time stops growing with the number of morphologies, the bottleneck the paper attributes to hidden morphology is not operative in that setting.
Extended reading notes
Core claim
The central claim is Theorem 4.1: HEAT(P,H,K) is PSPACE-complete. The argument works by showing that any finite-horizon POMDP can be encoded as a HEAT instance with one morphology, so HEAT inherits the PSPACE-hardness of POMDP planning; membership follows from a depth-first belief-state search that uses only polynomial memory. Because the morphology index is part of the hidden state, a unified policy must carry belief about which body it currently controls, and that belief tracking is what makes the problem hard. If the morphology were revealed at every step, the paper notes, the problem would decompose into n independent MDPs solvable in polynomial time.
Load-bearing premise
The argument assumes a robot never observes its own morphology and receives only shared morphology-agnostic sensor readings; if the robot were told which body plan it has, the problem would split into ordinary MDPs and the PSPACE-completeness would dissolve.
Editorial extensions
If this is right
- No polynomial-time algorithm exists for HEAT unless P equals PSPACE, so cross-morphology RL cannot be fixed by a smarter optimizer alone.
- The empirical bottlenecks of memory-policy entanglement, incompatible trajectories, and sequential training are symptoms of the underlying PSPACE-completeness, not implementation bugs.
- Revealing the morphology index at each step reduces HEAT to n ordinary MDPs and restores polynomial-time solvability, making morphology awareness the key design lever.
- Collective Adaptation, formalized as a Dec-POMDP, is NEXP-complete in the worst case, formally harder than HEAT, yet its decentralized structure permits parallel data collection and deployment that centralized training cannot offer.
- Any scalable HEAT solution must include explicit belief tracking, amortized morphology identification, or training curricula that exploit shared structure across bodies.
Reading between the lines
- The paper's own special-case observation implies a cheap practical fix it does not pursue: give the policy a body-plan descriptor at training and execution time, and the hardness argument no longer applies. This is an inference from Section 4.1, not a claim the paper advocates.
- The PSPACE-completeness result likely transfers to any setting with a latent context variable that must be inferred and that changes both dynamics and action spaces, such as a single robot with interchangeable tools or damaged actuators, extending the result beyond morphology to broader latent-embodiment problems.
- A testable extension would measure whether actual training time in the paper's MuJoCo setup tracks the predicted linear scaling in the number of morphologies, and whether morphology-conditioned architectures bend that curve without ever being told the morphology index.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces the Heterogeneous Embodied Agent Training (HEAT) problem, in which a single memory-based policy must control multiple robot morphologies under partial observability, with the morphology index treated as a latent variable. The authors prove that the decision problem HEAT(P,H,K) is PSPACE-complete by reducing any finite-horizon POMDP to a HEAT instance with n=1 and by giving the standard belief-state enumeration membership argument. They further claim that this complexity result explains the practical bottlenecks observed in a MuJoCo study of twelve cheetah variants, and they contrast HEAT with Collective Adaptation, a decentralized DTDE paradigm modeled as a Dec-POMDP and stated to be NEXP-complete. The paper includes empirical timing comparisons and provides a public code repository.
Significance. The formal PSPACE-completeness result is correct as a theorem: HEAT indeed contains finite-horizon POMDP planning as a special case, and the membership argument is standard. However, the paper's central interpretive claim—that latent morphology inference is the sole or primary source of intractability—is not supported by the proof, because the hardness reduction uses n=1, so morphological diversity plays no role in the hardness. The special-case claim that observable morphology reduces HEAT to polynomially solvable MDPs is false without an additional full-observability assumption. If the authors revise these claims, the paper can still serve as a useful bridge between POMDP complexity theory and cross-morphology RL, but in its current form the main theoretical message overstates what the theorem establishes.
major comments (3)
- [Section 4.1, PSPACE-hardness proof] The proof of PSPACE-hardness reduces an arbitrary finite-horizon POMDP to a HEAT instance by setting n=1. In that reduction the latent morphology index is constant, so the instance contains no morphological diversity and no uncertainty about morphology. The theorem is true, but it only shows that HEAT inherits the hardness of general POMDP planning; it does not show that morphological diversity, latent morphology inference, trajectory incompatibility, or sequential training constraints are the source of intractability. The 'Implications' paragraph states that 'the computational bottleneck of HEAT arises solely from latent morphology inference,' which is contradicted by the reduction itself. Please revise the implications to state that HEAT is hard because it generalizes POMDP planning, and either remove or substantially weaken the claim that morphology inference is the bottleneck.
- [Section 4.1, Special cases] The claim that observing the morphology index m at every time step 'decomposes the problem into n ordinary MDPs, each solvable in polynomial time' is false under the paper's own partial-observability model. Even when m is known, the underlying state s∈S_i is still hidden and is observed only through the shared observation model Ω(o|s). Each single-morphology subproblem therefore remains a finite-horizon POMDP, and the composite problem remains PSPACE-hard in general. The claim would become true only under an additional assumption that each S_i is fully observable; if that is the intended meaning, it should be stated explicitly. As written, the special-case statement is incorrect and should be corrected.
- [Sections 4.2 and 4.5] The training-time analysis claims O(n·K·T) sequential time, worst-case exponential retraining due to catastrophic forgetting, and average-case linear scaling. These are presented in the flow of the complexity section as if they follow from Theorem 4.1, but PSPACE-completeness of the decision problem does not by itself imply any lower bound on the time of a particular RL training algorithm. These are algorithmic/empirical claims that need independent justification or explicit labeling as observations, not corollaries of the PSPACE-completeness result. Please clarify the logical relationship.
minor comments (5)
- [Section 2, Eq. (2)] Equation (2) defines the policy as π: (s_t, h_{t-1}) → a_t, using the full underlying state s_t. This contradicts the partial-observability assumption that the policy receives only observations. Please rewrite Eq. (2) to map observations and memory to actions, or clearly state that s_t denotes the most recent observation.
- [Section 1, Introduction] There is a typo in 'HEA T problem' on the first page; it should read 'HEAT problem'.
- [Section 2, notation] The paper uses notation P(S_i) for probability distributions without defining it; please use Δ(S_i) or define P as the set of probability distributions.
- [Section 5.3] The claim that DTDE is 'strictly harder' than CTDE based on NEXP-completeness versus PSPACE-completeness is too strong. While it is true that NEXP-complete problems are not known to be in PSPACE, a formal separation PSPACE ≠ NEXP would be a major open problem. Please rephrase to say 'at least as hard in the worst case under standard complexity assumptions' or 'believed to be harder.'
- [Section 4.1, membership proof] The membership argument cites the depth-first belief-state enumeration of Papadimitriou and Tsitsiklis but does not spell out why the belief state has polynomial size. Since the horizon is given in unary and the state space is part of the input, a brief justification of why the belief can be represented in polynomial space would make the proof self-contained.
Circularity Check
No significant circularity; complexity results are imported from external literature and the only self-citation is non-load-bearing.
full rationale
The derivation chain is not circular in the sense of fitting a parameter and calling it a prediction, or defining the conclusion into the premises. HEAT is defined in Section 2 as a composite POMDP with a latent morphology index, and Theorem 4.1 is proved by a standard log-space reduction from any finite-horizon POMDP to a HEAT instance with n=1, plus a PSPACE membership argument attributed to Papadimitriou and Tsitsiklis. This imports external complexity results rather than deriving the hardness from the paper's own fitted values or from a self-citation chain. The only author self-citation is [16] (F. Wang and S. Liu), used in Section 5 to frame 'Collective Adaptation' as a form of DTDE; the NEXP-completeness claim is explicitly attributed to Bernstein et al. [18], so the self-citation is not load-bearing. Two interpretive problems do exist but they are not circularity: Section 4.1's 'Implications' paragraph claims the bottleneck 'arises solely from latent morphology inference,' which is not supported by the n=1 reduction that contains no morphological diversity, and the 'Special cases' claim that observable morphology index m yields n 'ordinary MDPs' ignores the shared observation model Ω(o|s), which leaves each single-morphology subproblem partially observable. These are correctness/over-claim issues rather than circular reductions. Accordingly, the score reflects only the minor, non-load-bearing self-citation; no circular step is identified.
Assumptions & free parameters
assumptions (4)
- standard math Finite-horizon POMDP planning with horizon in unary is PSPACE-complete (Papadimitriou and Tsitsiklis, 1987)
- standard math Finite-horizon Dec-POMDP planning is NEXP-complete (Bernstein et al., 2002)
- domain assumption The latent morphology index is sampled once per episode and is unobservable, with a morphology-agnostic observation model
- ad hoc to paper HEAT instances with n=1 are allowed and count as cross-morphology problem instances
Cite this review
Pith. "Pith review of Training Cross-Morphology Embodied AI Agents: From Practical Challenges to Theoretical Foundations." pith.science (2026). https://pith.science/paper/ON56MHK7
@misc{pith2026250603613,
author = {Pith},
title = {Pith review of: Training Cross-Morphology Embodied AI Agents: From Practical Challenges to Theoretical Foundations},
year = {2026},
howpublished = {\url{https://pith.science/paper/ON56MHK7}},
note = {Machine review of arXiv:2506.03613}
}
read the original abstract
While theory and practice are often seen as separate domains, this article shows that theoretical insight is essential for overcoming real-world engineering barriers. We begin with a practical challenge: training a cross-morphology embodied AI policy that generalizes across diverse robot morphologies. We formalize this as the Heterogeneous Embodied Agent Training (HEAT) problem and prove it reduces to a structured Partially Observable Markov Decision Process (POMDP) that is PSPACE-complete. This result explains why current reinforcement learning pipelines break down under morphological diversity, due to sequential training constraints, memory-policy coupling, and data incompatibility. We further explore Collective Adaptation, a distributed learning alternative inspired by biological systems. Though NEXP-complete in theory, it offers meaningful scalability and deployment benefits in practice. This work illustrates how computational theory can illuminate system design trade-offs and guide the development of more robust, scalable embodied AI. For practitioners and researchers to explore this problem, the implementation code of this work has been made publicly available at https://github.com/airs-admin/HEAT
Figures
Reference graph
Works this paper leans on
-
[1]
One policy to control them all: Shared modular policies for agent-agnostic control,
W. Huang, I. Mordatch, and D. Pathak, “One policy to control them all: Shared modular policies for agent-agnostic control,” in International Conference on Machine Learning, pp. 4455–4464, PMLR, 2020
work page 2020
-
[2]
The complexity of markov decision processes,
C. H. Papadimitriou and J. N. Tsitsiklis, “The complexity of markov decision processes,” Mathematics of operations research , vol. 12, no. 3, pp. 441–450, 1987
work page 1987
-
[3]
Intractable problems in control theory,
C. H. Papadimitriou and J. Tsitsiklis, “Intractable problems in control theory,” SIAM journal on control and optimization, vol. 24, no. 4, pp. 639–654, 1986
work page 1986
-
[4]
D. Bertsekas and J. N. Tsitsiklis, Neuro-dynamic programming. Athena Scientific, 1996
work page 1996
-
[5]
On the undecidability of probabilistic planning and related stochastic optimization problems,
O. Madani, S. Hanks, and A. Condon, “On the undecidability of probabilistic planning and related stochastic optimization problems,” Artificial Intelligence, vol. 147, no. 1-2, pp. 5–34, 2003
work page 2003
-
[6]
A. A. Rusu, N. C. Rabinowitz, G. Desjardins, H. Soyer, J. Kirkpatrick, K. Kavukcuoglu, R. Pascanu, and R. Hadsell, “Progressive neural networks,” arXiv preprint arXiv:1606.04671, 2016
arXiv 2016
-
[7]
Overcoming catastrophic forgetting in neural networks,
J. Kirkpatrick, R. Pascanu, N. Rabinowitz, J. Veness, G. Desjardins, A. A. Rusu, K. Milan, J. Quan, T. Ramalho, A. Grabska-Barwi ´nska, et al., “Overcoming catastrophic forgetting in neural networks,” Proceedings of the national academy of sciences, vol. 114, no. 13, pp. 3521–3526, 2017
work page 2017
-
[8]
D. Hernandez, J. Kaplan, T. Henighan, and S. McCandlish, “Scaling laws for transfer,” arXiv preprint arXiv:2102.01293, 2021
arXiv 2021
Show all 18 references
-
[9]
Training a 3-node neural network is np-complete,
A. Blum and R. Rivest, “Training a 3-node neural network is np-complete,” Advances in neural information processing systems, vol. 1, 1988
1988
-
[10]
Gradient surgery for multi-task learning,
T. Yu, S. Kumar, A. Gupta, S. Levine, and K. Hausman, “Gradient surgery for multi-task learning,” inAdvances in Neural Information Processing Systems, vol. 33, pp. 5824–5836, 2020
2020
-
[11]
Deep recurrent q-learning for partially observable mdps.,
M. J. Hausknecht and P. Stone, “Deep recurrent q-learning for partially observable mdps.,” in AAAI fall symposia, vol. 45, p. 141, 2015
2015
-
[12]
Context vector-based visual mapless navigation in indoor using hierarchical semantic information and meta-learning,
F. Li, C. Guo, H. Zhang, and B. Luo, “Context vector-based visual mapless navigation in indoor using hierarchical semantic information and meta-learning,” Complex & Intelligent Systems, vol. 9, no. 2, pp. 2031–2041, 2023
2023
-
[13]
Dtde: A new cooperative multi-agent reinforcement learning framework,
G. Wen, J. Fu, P. Dai, and J. Zhou, “Dtde: A new cooperative multi-agent reinforcement learning framework,” The Innovation, vol. 2, no. 4, 2021
2021
-
[14]
Metagpt: Meta programming for multi-agent collaborative framework,
S. Hong, X. Zheng, J. Chen, Y . Cheng, J. Wang, C. Zhang, Z. Wang, S. K. S. Yau, Z. Lin, L. Zhou,et al., “Metagpt: Meta programming for multi-agent collaborative framework,”arXiv preprint arXiv:2308.00352, vol. 3, no. 4, p. 6, 2023
2023 arXiv
-
[15]
Human- timescale adaptation in an open-ended task space,
A. A. Team, J. Bauer, K. Baumli, S. Baveja, F. Behbahani, A. Bhoopchand, N. Bradley-Schmieg, M. Chang, N. Clay, A. Collister,et al., “Human- timescale adaptation in an open-ended task space,” arXiv preprint arXiv:2301.07608, 2023
2023 arXiv
-
[16]
Conceptual framework toward embodied collective adaptive intelligence,
F. Wang and S. Liu, “Conceptual framework toward embodied collective adaptive intelligence,” arXiv preprint arXiv:2505.23153, 2025
2025 arXiv
-
[17]
Beyond collective intelligence: Collective adaptation,
M. Galesic, D. Barkoczi, A. M. Berdahl, D. Biro, G. Carbone, I. Giannoccaro, R. L. Goldstone, C. Gonzalez, A. Kandler, A. B. Kao, et al., “Beyond collective intelligence: Collective adaptation,”Journal of the Royal Society interface, vol. 20, no. 200, p. 20220736, 2023
2023
-
[18]
The complexity of decentralized control of markov decision processes,
D. S. Bernstein, R. Givan, N. Immerman, and S. Zilberstein, “The complexity of decentralized control of markov decision processes,” Mathematics of operations research, vol. 27, no. 4, pp. 819–840, 2002. Manuscript submitted to ACM
2002
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.