Scalable Submodular Policy Optimization via Pruned Submodularity Graph
Aditi Anand, Suman Banerjee, Dildar Ali · 2025
Read Scalable Submodular Policy Optimization via Pruned Submodularity Graph by Aditi Anand, Suman Banerjee, Dildar Ali (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-13834.txt.
Introduction
Aditi Anand and co-authors study how a learning agent can pick acts when gains show falling returns. The work dates to 2025. In many real tasks, like path choice and area cover, each new gain adds less than the last. Gains of this kind can be modeled with a class of set-based scores.
The team gives a graph method that trims weak links to keep the search fast. They prove the method stays close to the best score and check its time and space needs. Tests in a shared test setup show the method earns more than older methods. The work fits tasks where broad cover matters more than raw sums.
Catalog record
| CREATOR | Aditi Anand, Suman Banerjee, Dildar Ali |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-13834
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Scalable Submodular Policy Optimization via Pruned Submodularity Graph Aditi Anand, Suman Banerjee, Dildar Ali 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. 1 Introduction In a reinforcement learning problem, an agent interacts with the environment and learns a policy such that the reward at the end of a finite number of steps gets maximized [ 7 ] . Typically, the environment is modeled as a Markov decision process, which can be expressed as a tuple of six entities: the set of states, the set of actions, the transition function, the reward function, the initial state distribution, and the discount factor [ 29 ] . It has been assumed that the reward function is additive and independent of the trajectory. Bellman’s optimality principle allows us to identify an optimal policy in polynomial time. In practice, there are many problems whose reward function can not be modeled as an additive function. Hence, our goal is to expand the horizon of RL by extending the reward function to a more general class of functions (other than the additive function). In this paper, we study the RL in a setup with a submodular reward function. In practice, there exist several problems where this setup fits, such as coverage control [ 24 ] , experiment design [ 16 ] , entropy maximization [ 25 ] , informative path planning [ 10 ] , and many more. To the best of our knowledge, other than the study by Prajapat et al. [ 23 ] , there does not exist any literature that focuses on the Submodular RL Problem. Given a submodular set function f defined on the ground set \mathcal{V} , a well-studied problem is how can we maximize f under different constraints including cardinality constraint [ 12 ] , knapsack constraint [ 30 ] , matroid constraint [ 17 ] , p -system constraint, and many more. It has been reported in the literature that many real-life problems including sensor placement [ 19 ] , viral marketing [ 13 ] , image segmentation [ 4 ] , document summarization [ 20 ] , speeding up of satisfiability solvers [ 27 ] etc. can be modeled as maximization of submodular function subject to different constraints. There has been a significant study on this problem in the past four decades, and it has been studied in different setups, including streaming [ 5 ] , distributed [ 21 ] , multi-core architecture [ 11 ] , and many more. This leads to a vast amount of literature on this problem, as referenced in the survey on this topic [ 8 , 14 ] . While submodularity is typically considered in discrete domains, this concept is also generalized to the continuous domain, such as DR-submodularity by Bian et al. [ 3 ] . In this direction, Dolhansky and Blimes [ 6 ] introduce the class of deep submodular functions and their neural network models guaranteed to yield to submodular functions as input. This kind of function is useful when the learning is from unknown rewards using function approximation. Among many existing methodologies, one of the methods for solving submodular function maximization is as follows: Starting with an empty set, in each iteration, pick the element that does not belong to the set of selected elements and produces the maximum marginal gain. This process continues until some termination criteria are met. Though this method is easy to understand and easy to implement, it can not be used in practice due to the huge computational time requirement. The primary reason behind this is the large number of marginal gain computations. Several methods have been proposed that try to reduce the number of marginal gain computations [ 18 ] . One such method is the pruned submodularity graph-based approach proposed by Zhou et al. [ 31 ] . Since then, this approach has been used to solve many problems where the input data size is huge. Motivation. Traditional reinforcement learning (RL) framework predominantly assume that the reward function is additive and trajectory-independent, which simplifies the optimization process using tools like Bellman’s principle [ 7 , 29 ] . However, this assumption does not hold in many real-world scenarios, such as coverage control [ 28 ] , informative path planning [ 26 ] , and experiment design [ 15 ] , where the law of diminishing returns plays a critical role. These applications naturally exhibit submodular reward structures, which introduce a fundamentally different optimization landscape. Despite the wide applicability of submodular functions, very limited attention has been given to reinforcement learning with submodular rewards. This gap motivates the need to extend RL methods to better capture such non-additive, diminishing-return scenarios. Our work addresses this challenge by introducing a scalable approach that leverages pruned submodularity graphs to efficiently approximate optimal policies in submodular RL setups, enabling practical deployment in high-dimensional environments. Our Contribution. In this paper, we have made an attempt to use the pruned submodularity graph-based approach to reduce the number of state spaces. In particular, we make the following contributions in this paper: • We study the Submodular RL Problem, for which the literature is limited. • We have used the pruned submodularity graph-based approach to reduce the state space in a given Submodular RL Problem. • The proposed approach has been analyzed to understand its time and space requirements as well as performance guarantee. • We have done a number of experiments with environments that have been used by previous studies, and we observe that our proposed approach leads to more rewards compared to existing methods. The Rest of the paper has been organized as follows. Section 2 describes some background concepts and defines our problem formally. Section 3 contains our proposed solution approach with detailed analysis. The experimental evaluation of the proposed approach has been described in Section 4 . Finally, Section 5 concludes our study and gives future research directions. 2 Background and Problem Definition In this section, we describe the background information related to our problem and define it formally. Initially,