# Scalable Submodular Policy Optimization via Pruned Submodularity Graph

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

## 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 13 of its 31 references that are in the map.
- First posted on arXiv 18 Jul 2025.

## 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, 13 of 13)

- [Learning to Perform Physics Experiments via Deep Reinforcement Learning](https://mlsanity.com/paper/1611.01843/) (2016)
- [Continuous DR-submodular Maximization: Structure and Algorithms](https://mlsanity.com/paper/1711.02515/) (2017)
- [Submodular Reinforcement Learning](https://mlsanity.com/paper/2307.13372/) (2023)
- [Distributed Submodular Maximization](https://mlsanity.com/paper/1411.0541/) (2014)
- [Submodular Maximization Meets Streaming: Matchings, Matroids, and More](https://mlsanity.com/paper/1309.2038/) (2013)
- [Near-Optimal Multi-Agent Learning for Safe Coverage Control](https://mlsanity.com/paper/2210.06380/) (2022)
- [Maximization of Approximately Submodular Functions](https://mlsanity.com/paper/2411.10949/) (2024)
- [Scaling Submodular Maximization via Pruned Submodularity Graphs](https://mlsanity.com/paper/1606.00399/) (2016)
- [A Submodularity-Based Approach for Multi-Agent Optimal Coverage Problems](https://mlsanity.com/paper/1708.04201/) (2017)
- [Influential Billboard Slot Selection using Pruned Submodularity Graph](https://mlsanity.com/paper/2207.06631/) (2022)
- [Influential Billboard Slot Selection using Spatial Clustering and Pruned Submodularity Graph](https://mlsanity.com/paper/2305.08949/) (2023)
- [Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint](https://mlsanity.com/paper/1607.04527/) (2016)
- [GPU-Accelerated Optimizer-Aware Evaluation of Submodular Exemplar Clustering](https://mlsanity.com/paper/2101.08763/) (2021)

## Abstract (arXiv)

In Reinforcement Learning (abbreviated as RL), an agent interacts with the environment via a set of possible actions, and a reward is generated from some unknown distribution. The task here is to find an optimal set of actions such that the reward after a certain time step gets maximized. In a traditional setup, the reward function in an RL Problem is considered additive. However, in reality, there exist many problems, including path planning, coverage control, etc., the reward function follows the diminishing return, which can be modeled as a submodular function. In this paper, we study a variant of the RL Problem where the reward function is submodular, and our objective is to find an optimal policy such that this reward function gets maximized. We have proposed a pruned submodularity graph-based approach that provides a provably approximate solution in a feasible computation time. The proposed approach has been analyzed to understand its time and space requirements as well as a performance guarantee. We have experimented with a benchmark agent-environment setup, which has been used for similar previous studies, and the results are reported. From the results, we observe that the policy obtained by our proposed approach leads to more reward than the baseline methods.