Strong and Compact Policies for Submodular Markov Decision Processes via LP-Based Submodular Orienteering
Lars Rohwedder, Rico Zenklusen
cs.DS · cs.LG
Quick verdict
LP-based Sherali-Adams rounding gives O(log H)-approx Submodular MDP policies (first o(H)); rigorous theory, but purely theoretical with no experiments.
Summary
The paper develops an LP-based algorithm for Submodular Orienteering — finding an s-t walk in a directed graph that maximizes a monotone submodular function under a length budget — and uses it to obtain the first approximation guarantee for Submodular MDPs that is sublinear in the horizon H. The relaxation Q(r) is a Sherali-Adams-style extended formulation whose variables x_I estimate joint vertex-containment probabilities; a conditioning operation (Lemma 3) supports a recursive randomized rounding (Algorithm 1) that never conditions on future vertices, unlike Recursive Greedy. The pivotal Lemma 5 returns, alongside a random path, a linear function upper-bounding f on all layer-spanning paths with E[f(P)] ≥ E[ℓ(x)]/((d−1)(r+1)); feeding these majorants into a Round-or-Cut loop with the ellipsoid method yields Theorem 1: Ω(OPT/log n) in quasi-polynomial time n^O(log n), and O(n^ε) in time n^O(1/ε) — the latter also achieved combinatorially in Appendix A. Adding transition-probability constraints (7) transfers the machinery to Submodular MDPs (Section 3; Lemma 13 proves the policy reproduces the rounding distribution), giving O(log H)-approximation in quasi-polynomial time and O(H^ε) in polynomial time (Theorem 2), improving the prior best O(H) of Wang et al. (2020), with policies conditioning on only O(log H) past vertices. Limitations: purely theoretical with no experiments, quasi-polynomial running times for the logarithmic guarantee, unoptimized constants, and matching hardness lower bounds remain open.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 2
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- An LP-based algorithm (Sherali-Adams relaxation + Round-or-Cut with linear majorants of the submodular objective) achieves Ω(OPT/log n) for Submodular Orienteering in n^O(log n) time and O(n^ε) in n^O(1/ε) time, matching Chekuri-Pál up to constant factors (Theorem 1).
- Submodular MDPs admit randomized O(log H)-approximate policies computable in n^O(log H) time and O(H^ε)-approximate policies in n^O(1/ε) time, improving the prior best O(H) guarantee of Wang et al. (2020) (Theorem 2).
- The MDP policies are compact: each action choice conditions on only O(log H) (or O(1/ε)) vertices of the past trajectory, addressing the exponential policy-representation issue for non-Markovian rewards.
- The multilinear extension, the standard tool of submodular maximization, is provably uninformative for this problem (footnote 3 Ω(√n)-gap example), which motivates the new LP-based approach.
Strengths
First sublinear-in-H guarantee for Submodular MDPs
Theorem 2 improves the prior best O(H) approximation of Wang et al. [Wan+20] to O(log H) computable in n^O(log H) time, plus an O(H^ε)/n^O(1/ε) trade-off — resolving the open question the authors state in Section 1.1 about whether o(H) is achievable with a compactly represented policy.
Genuinely new LP technique for submodular objectives
Section 2 circumvents the multilinear extension — shown uninformative by a concrete Ω(√n)-gap example (footnote 3: k=Θ(√n) disjoint color paths, symmetric solution value Ω(k) vs integral optimum 1) — by pairing recursive randomized rounding with randomized linear majorants (Lemma 5: E[f(P)] ≥ E[ℓ(x)]/((d−1)(r+1)), with ℓ ≥ f on every layer-spanning path) inside a Round-or-Cut/ellipsoid loop (Algorithms 2-3).
Forward-only conditioning is the key structural insight
Policy compactness quantified
Self-contained, checkable exposition
Weaknesses
No empirical validation of any algorithm
Length feasibility only in expectation
No lower bounds
Unoptimized constants and randomized-only guarantees
For Orienteering alone, no ratio improvement
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
This is a theoretical computer science paper (arXiv 2609.15539, cs.DS/cs.LG, September 2026) on approximation algorithms. It targets two problems: Submodular Orienteering — find an s-t walk in a directed graph maximizing a monotone submodular set function (accessed via a value oracle) subject to a length budget w(W) ≤ C — and its stochastic generalization, Submodular MDPs, where the total reward is f over the visited state-action sequence and the agent moves stochastically (the model of Wang et al. [Wan+20] and Prajapat et al. [PMZK24]). The headline results are stated as Theorems 1 and 2: (i) an LP-based algorithm achieving E[f(W)] ≥ Ω(OPT/log n) in n^O(log n)⟨w⟩^O(1) time, or Ω(OPT/n^ε) in n^O(1/ε) time, both with E[w(W)] ≤ C; (ii) Submodular MDP policies with O(log H)-approximation computable in n^O(log H)⟨p⟩^O(1) time, or O(H^ε) in n^O(1/ε) time, each decision conditioning on only O(log H) (resp. O(1/ε)) trajectory vertices. Prior best for Submodular MDPs was O(H) [Wan+20], with bounded-curvature variants in [DPK24]. The claim of the first o(H) guarantee is the paper's core selling point and is well supported. For plain Orienteering, the guarantee matches Chekuri-Pál [CP05] only up to constant factors — the contribution there is the new method, not the ratio.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is a Submodular MDP?
A Markov Decision Process variant where the total reward is a monotone submodular set function (exhibiting diminishing returns, e.g., counting distinct covered targets) of the visited states and actions, instead of a sum of per-step rewards. It was introduced by Wang et al. (2020) and studied by Prajapat et al. (2024); in the deterministic case it is exactly the Submodular Orienteering problem on directed graphs.
What improvement does this paper make over prior work?
The previous best approximation for Submodular MDPs was a factor O(H), linear in the time horizon H (Wang et al. 2020). This paper achieves O(log H) approximation in quasi-polynomial time n^O(log H) and O(H^ε) approximation in polynomial time n^O(1/ε) for any ε > 0, and its policies depend on only O(log H) previously visited vertices rather than the full trajectory.
Is there code or an implementation available for this paper?
No. This is a purely theoretical paper: all results are worst-case approximation guarantees with full proofs. No code, datasets, or experiments are reported, and the quasi-polynomial LP-based algorithms are not practical to run at scale.
Why doesn't the paper use the multilinear extension like standard submodular maximization work?
Because the multilinear extension is provably useless here: footnote 3 constructs an instance with Θ(√n) disjoint s-t paths where the extension of the symmetric fractional solution (each path weight 1/k) has value Ω(√n) while every integral solution has value 1. Any LP relaxation oblivious to the function would therefore round from a point carrying no signal, so the authors build a Sherali-Adams-style relaxation with linear majorants instead.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- The abstract in the supplied metadata is cut off mid-sentence, but the full abstract appears at the start of the extracted paper text, so no substantive content is missing.
- This is a proof-based theory paper; the review assesses proofs as extracted (with minor OCR artifacts, e.g., '12 Ω(1/dr)' for '≥ Ω(1/dr)') without independent formal verification.
- No figures or tables exist in the extracted text; all content is definitions, algorithms, and proofs.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.