mlsanityData to 14 Oct 2026

Scalable Submodular Policy Optimization via Pruned Submodularity Graph

arXiv 2507.13834 ↗First posted 18 Jul 2025cs.LG cs.AI cs.MAcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

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.

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.

Builds on

13 of 31 references.

References · 13

  1. 2016Learning to Perform Physics Experiments via Deep Reinforcement Learningcited by 47
  2. 2017Continuous DR-submodular Maximization: Structure and Algorithmscited by 24
  3. 2023Submodular Reinforcement Learningcited by 23
  4. 2014Distributed Submodular Maximizationcited by 20
  5. 2013Submodular Maximization Meets Streaming: Matchings, Matroids, and Morecited by 14
  6. 2022Near-Optimal Multi-Agent Learning for Safe Coverage Controlcited by 11
  7. 2024Maximization of Approximately Submodular Functionscited by 6
  8. 2016Scaling Submodular Maximization via Pruned Submodularity Graphscited by 3
  9. 2017A Submodularity-Based Approach for Multi-Agent Optimal Coverage Problemscited by 2
  10. 2022Influential Billboard Slot Selection using Pruned Submodularity Graphcited by 2
  11. 2023Influential Billboard Slot Selection using Spatial Clustering and Pruned Submodularity Graphcited by 2
  12. 2016Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraintcited by 1
1 more
  1. 2021GPU-Accelerated Optimizer-Aware Evaluation of Submodular Exemplar Clusteringcited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024Global Reinforcement Learning: Beyond Linear and Convex Rewards via Submodular Semi-gradient Methods
  2. 2026Multi-Agent Reinforcement Learning with Submodular Reward
  3. 2026Submodular Multi-Agent Policy Learning for Online Distributed Task Allocation in Open Multi-Agent Systems ↗
  4. 2026Strong and Compact Policies for Submodular Markov Decision Processes via LP-Based Submodular Orienteering
  5. 2026STO-RL: Offline RL under Sparse Rewards via LLM-Guided Subgoal Temporal Order
  6. 2023Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Space
  7. 2024To the Max: Reinventing Reward in Reinforcement Learning
  8. 2023Reparameterized Policy Learning for Multimodal Trajectory Optimization