Response to Reviewer 6FV4
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.