Scalable Submodular Policy Optimization via Pruned Submodularity Graph

Aditi Anand, Suman Banerjee, Dildar AliarXiv 2025 · DOI · arXiv

Abstract

In Reinforcement Learning (RL), an agent interacts with an environment to maximize a reward generated from an unknown distribution. Traditional RL frameworks assume that rewards are additive over time. However, many real-world applications—such as path planning and coverage control—exhibit the "law of diminishing returns," where the marginal utility of an action decreases as more actions are taken. This property is formally defined as submodularity. In this paper, we study a variant of the RL problem where the reward function is submodular. We propose Submodularity Graph-based Policy Optimization (SGPO), a pruned graph-based approach that provides a provably approximate solution within feasible computation time. Our analysis covers the algorithm's time and space complexity as well as its performance guarantees. Experimental results on benchmark environments demonstrate that SGPO achieves higher rewards and greater stability compared to existing baseline methods.

Introduction

Standard Reinforcement Learning (RL) algorithms rely on the assumption that the total reward of a trajectory is the sum of individual step-wise rewards. This additive structure allows for the application of Bellman’s optimality principle, enabling efficient dynamic programming and temporal difference learning. However, this assumption fails in scenarios like informative path planning, document summarization, or area coverage, where the value of a state depends on the history of states already visited.

In these contexts, the reward function is submodular. Because the reward depends on the entire trajectory rather than just the current state-action pair, the state space effectively explodes, making standard RL approaches computationally intractable. While recent "Submodular RL" methods have attempted to address this, they often struggle with high-dimensional spaces due to the intensive computational cost of calculating marginal gains. SGPO aims to bridge this gap by introducing a scalable, graph-based sparsification technique.

Methodology: Submodularity Graph-based Policy Optimization (SGPO)

The core innovation of SGPO lies in its ability to manage the complexity of the state space through a pruned submodularity graph. The algorithm follows a four-step process:

  1. Submodularity Graph Construction: The algorithm builds a weighted directed graph where nodes represent states. The edge weights represent the "divergence" between states, measuring the unique information or reward a state provides relative to others in the trajectory.
  2. Graph Pruning (Sparsification): To maintain computational efficiency, SGPO iteratively samples a subset of states and prunes those with low divergence weights. This pruning ensures that the algorithm only focuses on the most "informative" states, significantly reducing the number of marginal gain computations required.
  3. Policy Gradient Estimation: The authors derive a specific gradient estimator (Theorem 3) tailored for submodular rewards. This allows the policy—represented by a neural network—to be updated using regularized gradient ascent.
  4. Complexity Management: By utilizing the pruned graph, the algorithm maintains a logarithmic iteration complexity ($O(\log n)$), making it significantly more scalable than exhaustive greedy search methods.

Theoretical Insights

The paper provides a rigorous theoretical foundation for the necessity of approximation heuristics:

  • Hardness of Submodular RL: Theorem 2 proves that Submodular RL is fundamentally hard. Unless $NP \subseteq ZTIME(n^{polylog(n)})$, no polynomial-time algorithm can guarantee better than a logarithmic approximation. This justifies the use of the proposed graph-pruning heuristic.
  • Variance Reduction: The "Divergence of a state" metric identifies redundant states. By pruning these, the algorithm reduces noise during training. Experiments confirmed that SGPO’s loss curves were smoother than baselines, suggesting that focusing on high-divergence states acts as a form of variance reduction.

Experimental Evaluation

SGPO was evaluated across four environments featuring both continuous and discrete state-action spaces:

  • MuJoCo Ant (Continuous): A quadruped robot task where the objective is to maximize the unique 2D area covered. SGPO achieved a coverage of 2636 units, outperforming the SubPO baseline (2612 units).
  • Car Racing (Continuous): A high-dimensional task where a car must complete a lap. SGPO demonstrated faster learning, requiring fewer horizon steps to complete the lap as training progressed.
  • Entropy-Based Environment (Discrete): This environment focuses on exploration using entropy as the objective. SGPO achieved an objective value of 237.8, a significant improvement over SubPO’s 171.2.
  • Graph-Based Environment (Discrete): Evaluated in both M Mode (unique node weights) and SRL Mode (repeated coverage), SGPO consistently outperformed baselines in reward accumulation and convergence stability.

Conclusion and Future Work

SGPO offers a scalable solution for RL problems with non-additive, submodular rewards. By leveraging a pruned submodularity graph, the method identifies and prioritizes informative states, leading to superior performance and training stability compared to state-of-the-art baselines.

While SGPO reduces computational overhead, the theoretical complexity ($O(N \cdot n^4 s^2 m^2)$) remains a challenge for massive-scale industrial applications. Future research may focus on further optimizing these bounds or extending the framework to broader classes of non-additive reward functions beyond submodularity.

Summary updated

Abstract

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.
BibTeX
@misc{anand2025scalable,
  author = {Aditi Anand and Suman Banerjee and Dildar Ali},
  title = {{Scalable Submodular Policy Optimization via Pruned Submodularity Graph}},
  year = {2025},
  eprint = {2507.13834},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2507.13834},
  howpublished = {arXiv},
}
Figure