Submodular Reinforcement Learning

Thank you very much for the positive and valuable feedback. Multiplicative approximations are common for complexity analysis, especially in submodular optimization literature, so we used them. For future direction especially for statistical analysis, we will use regret/sample complexity types bounds.

Regarding optimal curvature dependency, a result exists for the simpler problem of set function optimization under cardinality constraints (Vondrak 2010), showing that $1-c$ is near optimal. Thanks, we now incorporated it in the paper.

Vondrak Jan, 2010 Submodularity and curvature: the optimal algorithm

Thank you for the valuable feedback. Please see our response below

Positive results

We would like to emphasize to the reviewer that we have multiple positive results.

Firstly, we consider a $\epsilon$-bandit SMDP which is a generalization of the bandit setting. Even under this simplified setting, it is intractable to achieve optimal value. However, SubPO achieves the information-theoretic optimal approximation ratio of $1-1/e$, which motivates a SuBPO-type approach as a sensible approach for Submodular RL.

Secondly, we would also like to bring the other positive result to the reviewer's attention which is for general SMDPs (i.e, no restrictions on dynamics) in Proposition 3, where, based on the curvature ‘c’ of the submodular function, we can guarantee that policy $\pi$ from SubPO achieves $J(\pi) \geq (1-c)J(\pi^\star)$ where $\pi^\star$ is the optimal non-Markovian policy.

Beyond this, giving any constant factor approximation in full generality is not possible as indicated by our hardness result in Theorem 1. Hence, the two positive results and the hardness result characterize the complete computational complexity of the proposed framework. More importantly, the algorithm SubPO is applicable to full generality without any sort of assumptions and can be used to optimize experiment design, entropy exploration, coverage, etc. objectives as shown in the experiments.

Literature review

Thanks for sharing [1][2], both of them look very interesting. Firstly, about the reward design, we want to emphasize that submodularity is an equivalent characterization of diminishing returns and hence is very general as mentioned by other reviewers as well. Arguably a problem analogous to blocking bandits can be conceptualized with submodular functions as well. For instance, consider a coverage problem on state time $(v,t)$ pairs, where pulling an arm $v$ at time $t$ covers it for the next $\tau_v$ times and hence no reward until $t + \tau_v$ time. If the arm $v$ is pulled after $t + \tau_v$, it will receive a reward again. Thanks for raising this point, we now included a table in the appendix referenced in the related work section summarizing various applications captured using submodular functions.

Secondly, about the differences with respect to the problem setting, we would like to emphasize to the reviewer that our focus is on MDPs i.e., we have states and need to satisfy transition constraints whereas both of these works ([1][2]) focus on bandits.

Throughout the entire paper, both in theory and experiments, we consider general MDPs. Only in the first half of section 5, we analyze a bandit case to motivate our SubPO algorithm with optimal approximation ratios and show interesting connections to generalize bandits. Although the bandits setting is not our focus, in order to connect with submodular bandits literature, we cite (Streeter & Golovin, 2008; Chen et al., 2017; Yue & Guestrin, 2011) in the last paragraph of related works. We are happy to further include [1].

General clarification and questions

Yes, $\pi^h(a)$ represents that the considered policies are state-independent and only depend on the horizons. Since we relax the MDP constraints, but yet have a generalization of bandit problems, we call it $\epsilon$-Bandit SMDP. In particular, if $\epsilon = 0$, we recover the bandit case.

Different communities may use the “planning” word differently, we would like to emphasize that this work considers a general problem of learning with data (samples) from simulations as done in typical policy gradient algorithms e.g., Reinforce, TRPO, PPO, Soft actor-critic, etc. Currently, our theoretical analysis focuses on computational complexity, and we agree quantifying the statistical complexity (i.e., sample complexity) of SubPO is an interesting future direction. A motivation in this direction can be derived from Yuan, et al. 2022 but is an independent research work of its own.

Rui Yuan, Robert M. Gower, Alessandro Lazaric, A general sample complexity analysis of vanilla policy gradient, 2022

Placement of sections: Thank you for your suggestion. The positive results are for the proposed algorithm, SubPO, and are therefore introduced in section 5 following the algorithmic details in section 4. Whereas the hardness result is for the framework (independent of the algorithm), hence presented in section 3 right after the framework is introduced in section 2. Presenting positive results for the algorithm prior to introducing the algorithm itself is difficult.

Thank you very much for the valuable feedback and sharing your questions. Please let us know for any further suggestions. We hope that our response clarifies that our focus is on MDPs, the significance of our contributions to both RL theory and practical use cases, and convinces the reviewer that our paper warrants their strong acceptance.

Thanks, we incorporated the suggestions. We agree that the modelling using submodular rewards deserves its own space. We had a paragraph saying “Examples of submodular rewards” in section 2 (preliminaries and problem statement). Now, we included a table in the appendix (reference in related works) summarizing different tasks that can be conceptualized with submodular functions.

We agree with how the reviewer has signified the importance of the contributions. Indeed, there is no attempt with submodular functions in RL, the most general work in this direction still considers planning on graphs.

Thank you very much for the positive and valuable feedback.

Thank you for the valuable feedback. Please see our response below,

Regarding the algorithm Submodular policy optimization (SubPO)

The key novelty in SubPO is to utilize the marginal gain decomposition for the submodular functions which allows for splitting the objective into per-step contributions that only depend on the history. We exploit this decomposition to obtain an unbiased gradient estimator with submodular (non-additive) reward functions (Theorem 2, proof in Appx C). In contrast to maximizing modular (state) reward in classical PG, the SubPO policy gradient theorem utilizes the effectiveness of greedily maximising marginal gains which is central to the literature on submodular maximization.

Analysis in Section 5. Can authors provide analysis in a more general setting?

Although $\epsilon$-bandit SMDP restricts the admissible MDPs, the notion nevertheless strictly generalizes the widely considered submodular bandit setting. The provable guarantee here motivates SuBPO as a sensible approach for Submodular RL since SubPO recovers the optimal approximation ratio of $1-1/e$ at least under this simplified SMDP.

Furthermore, we do provide another result for general SMDPs (general dynamics) in Proposition 3, where, based on the curvature ‘c’ of the submodular function, we can guarantee that policy $\pi$ from SubPO achieves $J(\pi) \geq (1-c)J(\pi^\star)$ where $\pi^\star$ is the optimal non-Markovian policy.

Beyond this, giving any constant factor approximation in full generality is not possible as established by our hardness result in theorem 1.

Location of related works

We appreciate the reviewer's suggestion to bring related work up. However, there is no closely related work, as we address a novel setting and our approach is only distantly related to submodular optimization, convex RL and PG approaches. Instead, we kept it in the end to rather emphasize the connections of our method to different fields. We now included a forward reference to the related works in the introduction section and explained the reasoning for it.

Thank you very much for the valuable feedback. We hope our response clarifies the details of the SubPO algorithm, points to our analysis of the general SMDPs, and convinces the reviewer that our paper warrants their strong acceptance.

Thanks for your question.

The first equality follows by derivative of $log$ function, i.e, $\nabla_{\theta} \log \pi_{\theta}(a_i|s_i) = \frac{\nabla_{\theta} \pi_{\theta}(a_i|s_i)}{\pi_{\theta}(a_i|s_i)}$.

For the second equality, since $b'(\tau_{0:i})$ only depends on history up to state $s_i$ (doesn't depend on action $a_i$), we get $\sum \limits_{a_i} \nabla_\theta \pi_{\theta}(a_i|s_i) b'(\tau_{0:i}) = b'(\tau_{0:i}) \nabla_\theta \sum \limits_{a_i} \pi_{\theta}(a_i|s_i)$.

Since $\sum\limits_{a_i} \pi_{\theta}(a_i|s_i)=1$, we get $b'(\tau_{0:i}) \nabla_\theta \left( \sum\limits_{a_i} \pi_{\theta}(a_i|s_i) \right) = b'(\tau_{0:i}) \nabla_\theta ( 1) = 0$.

If any step remains unclear, we are happy to explain further.