# Strong and Compact Policies for Submodular Markov Decision Processes via LP-Based Submodular Orienteering

arXiv: https://arxiv.org/abs/2609.15539 · HTML: https://mlsanity.com/paper/2609.15539/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 10 of its 27 references that are in the map.
- First posted on arXiv 14 Sep 2026.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 10 of 10)

- [Submodular Reinforcement Learning](https://mlsanity.com/paper/2307.13372/) (2023)
- [Constrained Submodular Maximization via a Non-symmetric Technique](https://mlsanity.com/paper/1611.03253/) (2016)
- [Constrained Submodular Maximization via New Bounds for DR-Submodular Functions](https://mlsanity.com/paper/2311.01129/) (2023)
- [Global Reinforcement Learning: Beyond Linear and Convex Rewards via Submodular Semi-gradient Methods](https://mlsanity.com/paper/2407.09905/) (2024)
- [Constrained Submodular Maximization: Beyond 1/e](https://mlsanity.com/paper/1608.03611/) (2016)
- [Planning with Submodular Objective Functions](https://mlsanity.com/paper/2010.11863/) (2020)
- [Algorithms and Adaptivity Gaps for Stochastic k-TSP](https://mlsanity.com/paper/1911.02506/) (2019)
- [On Approximating Degree-Bounded Network Design Problems](https://mlsanity.com/paper/1907.11404/) (2019)
- [Informative Path Planning with Limited Adaptivity](https://mlsanity.com/paper/2311.12698/) (2023)
- [Randomized Rounding over Dynamic Programs](https://mlsanity.com/paper/2511.03490/) (2025)

## Abstract (arXiv)

Finding policies for Markov Decision Processes (MDPs) is a central problem in areas such as Reinforcement Learning and Operations Research. Here, we have to repeatedly choose an action that should be performed by an agent. Depending on the action and the current state of the agent, the agent collects a reward and randomly transitions into a new state. The goal is to maximize the reward in expectation over a finite time horizon of length H. We consider a recently introduced variant that generalizes the traditionally additive reward function in the model to a monotone submodular one, which allows for capturing a range of interesting applications. Without the stochastic component, this problem is equivalent to the Submodular Orienteering problem, where the goal is to find an s-t walk in a directed graph maximizing a monotone submodular function under a length constraint. We present a novel LP-based algorithm for Submodular Orienteering using ideas from the Sherali-Adams hierarchy and Round-or-Cut. Our guarantees are comparable to the known quasi-polynomial time logarithmic approximation for Submodular Orienteering, but also extend to the setting of Submodular Markov Decision Processes. In the polynomial time regime, we present an O(nvarepsilon)-approximation (and O(Hvarepsilon) for Submodular MDPs) for every varepsilon >0, where n is the number of vertices, which was unknown even for Submodular Orienteering. Prior to our work, the best known approximation guarantee for Submodular MDPs had an approximation ratio linear in H. Beyond these algorithmic results, our methods reveal a trade-off between the approximation guarantee and the number of previously visited vertices on which an agent conditions its decision.