← 研踪 PaperTrailarXiv:2611.19795 · v1
Lossless First-Action Menus for Linear-Reward Planning
首次提交 2026-11-15 13:00
版本更新 2026-11-15 13:00
雷达观测 2026-11-17 12:06
摘要
We study sequential decision making where an agent reserves a minimum menu of initial actions before multi-objective trade-offs are revealed, followed by unrestricted continuation planning once linear reward weights arrive. We prove that a menu preserves the unrestricted optimal return across all linear scalarizations if and only if its reachable continuations cover all vertices of the full feature polytope. This geometric equivalence yields an output-sensitive algorithm that is fixed-parameter tractable in the vertex count, combining scalar backward induction with oracle-based facet identification. On explicitly layered graphs with unit feature increments, menu verification is coNP-complete and synthesis is complete for the second existential level of the polynomial hierarchy, even under additive loss strictly below one. In fixed dimensions two and higher, verification is polynomial whereas synthesis remains NP-complete, while one-dimensional instances admit polynomial-time solutions.
作者备注:8 pages, 0 figures
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-15 13:00 · 最新观测版本
Lossless First-Action Menus for Linear-Reward Planning
We study sequential decision making where an agent reserves a minimum menu of initial actions before multi-objective trade-offs are revealed, followed by unrestricted continuation planning once linear reward weights arrive. We prove that a menu preserves the unrestricted optimal return across all linear scalarizations if and only if its reachable continuations cover all vertices of the full feature polytope. This geometric equivalence yields an output-sensitive algorithm that is fixed-parameter tractable in the vertex count, combining scalar backward induction with oracle-based facet identification. On explicitly layered graphs with unit feature increments, menu verification is coNP-complete and synthesis is complete for the second existential level of the polynomial hierarchy, even under additive loss strictly below one. In fixed dimensions two and higher, verification is polynomial whereas synthesis remains NP-complete, while one-dimensional instances admit polynomial-time solutions.
查看此版本解读 →查看此版本原文 ↗