Submodular Reinforcement Learning
Authors: Manish Prajapat
Mojmir Mutny
Melanie Zeilinger
Andreas Krause
Venue: ICLR 2024 spotlight (2024)
Keywords: Reinforcement learning
Non-Markovian rewards
Submodular optimization
Policy gradient
Complex objectives in RL
Primary area: reinforcement learning
TL;DR: The paper introduces SubRL, a paradigm for policy optimization under submodular reward functions. It discusses the difficulty of approximating SubRL and proposes SubPO, a simple PG-based algorithm inspired by submodular optimization's greedy strategy

Abstract: In reinforcement learning (RL), rewards of states are typically considered additive, and following the Markov assumption, they are independent of states visited previously. In many important applications, such as coverage control, experiment design and informative path planning, rewards naturally have diminishing returns, i.e., their value decreases in light of similar states visited previously. To tackle this, we propose Submodular RL (subRL), a paradigm which seeks to optimize more general, non-additive (and history-dependent) rewards modelled via submodular set functions, which capture diminishing returns. Unfortunately, in general, even in tabular settings, we show that the resulting optimization problem is hard to approximate. On the other hand, motivated by the success of greedy algorithms in classical submodular optimization, we propose subPO, a simple policy gradient-based algorithm for subRL that handles non-additive rewards by greedily maximizing marginal gains. Indeed, under some assumptions on the underlying Markov Decision Process (MDP), subPO recovers optimal constant factor approximations of submodular bandits. Moreover, we derive a natural policy gradient approach for locally optimizing subRL instances even in large state- and action- spaces. We showcase the versatility of our approach by applying subPO to several applications, such as biodiversity monitoring, Bayesian experiment design, informative path planning, and coverage maximization. Our results demonstrate sample efficiency, as well as scalability to high-dimensional state-action spaces.

Published as a conference paper at ICLR 2024
SUBMODULAR REINFORCEMENT LEARNING
Manish Prajapat ETH Zurich
Mojmír Mutný ETH Zurich
Melanie N. Zeilinger ETH Zurich
Andreas Krause ETH Zurich
ABSTRACT
In reinforcement learning (RL), rewards of states are typically considered addi- tive, and following the Markov assumption, they are independent of states visited previously. many important applications, such as coverage control, experiment design and informative path planning, rewards naturally have diminishing returns, i.c., their value decreases in light of similar states visited previously. To tackle this, propose submodular RL (SUBRL), a paradigm which seeks to optimize more general, non-additive (and ceitory-dependent) rewards modelled via submodular set functions which capture diminishing returns. Unfortunately, in general, even in tabular settings, we show that the resulting optimization problem is hard to approxi- mate. On the other hand, motivated by the success of greedy algorithms in classical submodular optimization, we propose SUBPO, a simple policy gradient-base al- gorithm for SUBRL that handles non-additive rewards by greedily maximizing marginal gains. Indeed, under some assumptions on the underlying Markov Deci- sion Process (MDP), SUBPO recovers optimal constant factor approximations of submodular bandits. Moreover, we derive natural policy gradient approach for locally optimizing SUBRL instances even large state- and action- spaces. We showcase the versatility of our approach by applying SUBPO to several applications such as biodiversity monitoring, Bayesian experiment design, informative path planning, and coverage maximization. Our results demonstrate sample efficiency, as well as scalability to high-dimensional state-action spaces.
INTRODUCTION
In reinforcement learning (RL), the agent aims to learn a policy by interacting with its environment in order to maximize rewards obtained. Typically, in RL, the environments are modelled as (controllable) Markov chain, and the rewards are considered additive and independent of the trajectory. In this well-understood setting, referred to Markov Decision Processes (MDP), the Bellman optimality principle allows to find an optimal policy in polynomial time for finite Markov chains (Puterman 1994 Sutton & Barto 2018). However, many interesting problems cannot straight- forwardly be modelled via additive rewards. In this paper, we consider a rich and fundamental class of non-additive rewards, in particular submodular reward functions. Applications for planning under submodular rewards abound, from coverage control (Prajapal et al. (022), entropy maximization, experiment design (Krause al., 2008), informative path planning, orienteering problem Gunawan et al. (2016), resource allocation to Mapping (Kegeleirs et al. 2021).
Submodular functions capture an intuitive diminishing returns property that naturally arises in these applications: the reward obtained by visiting a state decreases in light of similar states visited previously. E.g., in a biodiversity monitoring application (see Fig. D. if the agent has covered a particular region, the information gathered from neighbouring regions becomes redundant and tends to diminish. To tackle such history-dependent, non-Markovian rewards, one could naively augment the state to include all the past states visited so far. This approach, however, exponentially increases the state-space size, leading to intractability. In this paper, we make the following contributions:
First, introduce SUBRL, paradigm for reinforcement learning with submodular reward functions. While this is the first work to consider submodular objectives in RL, we connect to related areas such as submodular optimization, convex RL in Section 6 To establish limits of the SUBRL framework. we derive a lower bound that establishes hardness of approximation up to log factors (i.e., ruling out any constant factor approximation) in general (Section Second, despite the hardness,
Code available wttttttttt/ttitieeeeeeeeettptttt cwm mommimaniii iiniish-- sh- Sch-pranne additive-iiii

---

Published as a conference paper at ICLR 2024
(a) Informative path planning over Gorilla nests
(b) Item collection
Figure 1: In Fig. Ia| for monitoring biodiversity, drone needs to plan a path with maximum coverage over critical areas, represented by lighter regions in heatmap. Here, the additional information (coverage) provided by visiting a location (state) depends on which states have been visited before. We therefore must visit diverse locations that maximize coverage of important regions. In Fig. lb the environment contains a group of items (g:) placed on grid. The agent must find trajectory (7) that picks a fixed number of items d: from each group Ii. i.e., max, 2. min(/T n g:l, d,). If the agent picks more than d; it is not rewarded - diminishing gain. Both these tasks cannot be represented with additive rewards (in terms of locations) and serve illustrative examples for this work.
show that, in many important cases, SUBRL instances can often be effectively solved in practice. In particular, we propose algorithm, SUBPO, motivated by the greedy algorithm in classic submodular optimization. It is a simple salicy-gradient-aseee algorithm for SUBRL that handles nod-addieive rewards by greedily maximizing marginal gains (Section 4 Third, we show that in some restricted settings, SUBPO performs provably well. In particular, under specific assumptions on the underlying MDP, SUBRL reduces to an instance of constrained continuous DR-submodular optimization over the policy space. Even though the reduced problem is still NP-hard, we guarantee convergence to the inoomation-theoretiallll optimal constant factor approximation of 1 1/c. generalizing previous results on submodular bandits. Moreover, for general MDPs, if the submodular function has bounded curvature, we show SUBPO achieves a constant factor approximation. (Section [ Lastly, we demonstrate the practical utility of SUBPO in simulation as well as real-world applications. Namely, we showcase its use biodiversity monitoring, Bayesian experiment design, informative path planning, building exploration, car racing and Mujoco robotics tasks. Our algorithm is sample efficient, discovers effective strategies, and scales well high dimensional spaces (Section 7
2 SUBMODULAR RL: PRELIMINARIES AND PROBLEM STATEMENT
Submodularity. Let V be ground set, A function F + R submodular if C CVV. E V. we have, F(Au U {v)) (AA) 2 F(BU U {w}) F(B). The property captures notion of diminishing returns, i.e., adding an element to A will help least as much as adding it to the superset B. We denote the marginal gain of element
A(v(AA = ((AU(o)) - F(A). Functions for which A(v) is independent of A are called modular. F is said to be monotone if AAA C C we have, F(A) S F(B) (or, equiv., A(U A) 2 O for all v, A).
Controlled Markov Process (CMP). CMP is a tuple formed by (V,A, P. H) where the ground set, E V is a state, A is the action space with E A. p denotes the initial state distribution H-
and P = { where (e") v. a) is the distribution of successive state o' after taking action a at state v at horizon We consider an episodic setting with finite horizon H.
Submodular MDP. We define submodular MDP, or SMDP, as a CMP with monotone submodular reward function, i.e., a tuple formed by (S,A, A, p. H, F). Hereby, using
x V to designate time-augmented states (i.c., each s = (h, v) S is a state augmented with the current horizon step), we assume F: 2 + I is a monotone submodular reward function. The non-stationary transition distribution (x |u a) of the CMP can be equivalently converted to P((h + 1, ((,, v), a) P(s'|s, a) since s accounts for time. An episode starts at Sp ~ p. and at each time step 2 0 at state Sh, the agent draws its action aj according to a policy π (see below). The environment evolves to a new state 81+11 following the CMP. A realization of this stochastic process is a trajectory H-1 : sH). an ordered sequence with fixed horizon H. TLE ((*), = sr) denotes the part from time step I to l'. Note that -= To.H- For each (partial) trajectory Tur' we use the notation F(TEC) to refer to the objective F evaluated on the set of (state, timeeettmee-par visited by T.P-
((s,, on)
Without loss of generality, this be extended to state-action hased rewards
2

---

Published as a conference paper at ICLR 2024
The agent acts in the SMDP according to policy, which in general maps histories Tosk to (distributions over) actions a₁. A policy x ( is called Markovian its actions only depend on the current state s, i... (ag To:A (a))(s)). The set of all Markovian policies is denoted by II Similarly, we can consider Kon-Markovian policies π (aA Th-kks)) that only depend on the previous past l steps Ah- The set of all Non-Markovian policies conditioned on history up past ls steps is denoted by 11 and we use UNM == 1n to allow arbitrary history-dependence.
Policies.
Problem Statement. For given submodular MDP, we want find a policy maximize its expected reward. For given policy π, let [(T; T) denote the probability distribution over the random
trajectory following agent's policy I,,
H-1 II A=
[(T;T)= = p(=0)
ap))
The performance measure (xx is defined as the expectation of the submodular set function over the trajectory distribution induced by the policy æ and the goal is to find policy that maximizes the performance measure within given family of policies (e.g., Markovian ones). Precisely,
n arg max JTT, where J(x)= = -(((=)) xell
Given the non-additive reward function F, the optimal policy on Markovian and non-Markovian policy classes can differ (since the reward depends on the history, the policy may need to take the history into account for taking optimal actions). In general, even representing arbitrary non-Markovian policies is intractable, as its description size would grow exponentially with the horizon. It is easy to see that for deterministic MDPs, the optimal policy is indeed attained by deterministic Markovian policy:
Proposition 1. For any deterministic MDP with a fixed initial state, the optimal Markovian policy achieves the same value as the optimal non-Markovian policy.
The following proposition guarantees that, even for stochastic transitions, there always exists an optimal deterministic policy among the family of Markovian policies M- Thus, we do not incur a loss compared to stochastic policies.
Proposition 2. For any set function F, among the Markovian policies The there exists an optimal policy that is deterministic.
The proof is in Appendix A The result extends to any non- Mon-Markvvian policy class I for as well, since one can group together the past states and treat as high high-dimensional Markovian state space.
Examples of submodular rewards. We first observe that classical MDPs are strict special case of submodular MDPs. Indeed, for some classical reward function r V - R,, by setting F(h1, 21).... (hu, uk)) := E ((z) F(r) simply recovers the (discounted) sum of rewards of the states visited by trajectory + (hereby, 7 E [0, 1). i.e., use 7 for the undiscounted setting).
generic way to construct submodular rewards is to take a submodular set function F' :2" - defined on the ground set V, and define F(T) (TT,)), using operator T 2 2 that drops the time indices. Thus, F(T) measures the value of the set of states TT C V visited by r. Note that each state is counted only once, i.e., even if F' is modular function, F exhibits diminishing returns. There are many practical examples of F", such as coverage functions, experimental design criteria such as mutual information and others that have found applications in machine learning tasks (cf. Krause & Golovin 2014 Bilmes 2022). Moreover, many operations preserve submodularity, which can be exploited to build complex submodular objectives from simpler ones (Krause & Golovin 2014, section 1.2) and can potentially be used in reward shaping. While submodularity is often considered for discrete V, the concept naturally generalizes to continuous domains.
SUBMODULAR RL: THEORETICAL LIMITS
We first show that the SUBRL problem is hard to approximate in general. particular, we establish a lower bound that implies SUBRL cannot be approximated up to any constant factor in polynomial time, even for deterministic submodular MDPs. We prove this by reducing our problem to a known hard-to-appe tappoooxiiioitteeeeeeeeee problem the submodular orienteering problem (SOP) (Chekuri & Pal 2005). Since we focus on deterministic SMDP's. according to Proposition and Propositioon22 2 it suffices to consider deterministic, Markovian policies. We now formally state the inapproximability result,
3

---

Published as a conference paper at ICLR 2024
Theorem 1. Let OPT be the optimal value and nj 0. Even for deterministic SMDP's, the SUBRL problem is hard to approximate within factor O 1-7 OPT) unless NP C 7.TTME (TTIME(NPPlylaan )
Thus, under common assumptions in complexity theory (Chekuri Pal 2005 Halperin & Krauthgamer 2003), the SUBRL problem cannot be approximated in general to better than logarithmic factors, i.e., no algorithm can guarantee J(x) 2 lug' OPT for all input instances of SUBRL. The proof is in Appendix B The significance of this result extends beyond submodular RL. As SUBRL falls within the broader category of general non-Markovian reward functions, Theorem Timplies that problems involving general set functions are similarly inapproximable, limited to logarithmic factors.
OPT
T
Since inapproximability result is worst-case in nature, it does not rule out that interesting SUBRL problems remain practically solvable. In the next section, we introduce a general algorithm that is efficiently implementable, recovers constant factor approximation under assumptions (Section 5 and is empirically effective as shown in an extensive experimental study (Section
GENERAL ALGORITHM: SUBMODULAR POLICY OPTIMIZATION SUBPO
We now propose practical algorithm for SUBRL that can efficiently handle submodular rewards. The core of our approach follows a greedy gradient update on the policy æ. As common the modern RL literature, we make use of approximation techniques for the policies to derive method applicable to large state-action spaces. This means the policy गe (a|s] is parameterized by 0 E @ where θ C R is compact. In the case of tabular æ,, 0 specifies an independent distribution over actions for each state.
Approach. The objective from Eq. (2) can be equivalently formulated as E arg m J (TTp) as 0 indexes our policy class. Due to the nonlinearity of the parameterization, is often not feasible to find a global optimum for the above problem. In practice, with appropriate initialization and hyper- parameters, variants of gradient descent known to perform well empirically for MDPs. Precisely,
0 ++ arg max 80 (o)(())) 50:80+0E@
2a |100||
Various PG methods arise with different methods for gradient estimation and applying regularization (Kakade 2001: Schulman al. 2015 2017). The key challenge to all of them computation of the gradient V (mo). Below, we devise an unbiased gradient estimator for general non-additive functions.
Gradient Estimator. As common in the policy gradient (PG) literature, we can use the score function g(T, TT) == Vlooo I To (a (s:) to calculate the gradient V.J. Namely, Given an MDP and the policy parameters 0,
VoJ(TO)
As Eq. (4) shows, we do not require knowledge of the environment if sampled trajectories are available. It also does not require full observability of the states nor any structural assumption on the MDP. On the other hand, the score gradients suffer from high variance due to sparsity induced by trajectory rewards (Fu 2006 Prajapat et al., 202T Sutton Barto 2018). Hence, we take the SMDP structure into account to develop efficient algorithms.
Marginal gain: We define the marginal gain for state in the trajectory To:j up to horizon j as F(s(To.)) = F(To.j U {s}} F(To.))
Our approach aims to maximize the marginal gain associated with each action instead of maximizing state rewards. This approach shares similarities with the greedy algorithm commonly used in submodular maximization, which maximizes marginal gains and is known for its effectiveness. Moreover, decomposing the trajectory return into marginal gains and incorporating it in the policy gradient with suitable baselines Greensmith et al. (2004) removes sparsity and thus helps to reduce variance. Inspired by the policy gradient method for additive rewards (Sutton et al. 1999 Baxter & Bartlet 2001). we propose the following for SMDP:
Theorem 2. Given an SMDP and the policy parameters 0, with any set function F,
F(5)+1lTOG) - b(TO:s) ]
H-1
VoJ(TT)
E
Va lo To (a.ls:)
Σ
(5)
TTS(TT
autoregressive policies (RNNs transformers) can he used capture history-dependence in the same algorithm
4

---

Published as a conference paper at ICLR 2024
Algorithm 1 Submodular Policy Optimization (SUBPO)
1: Input: SMDP.M, n, N, B
Vo
Vo
30
2: for epoch k = 1 N do
3: for batch b b= 1: do
20
4: for h 00: H 1 do
Vi
5:
Sample a₁ ~ (((anls)), execute an
6:
D ( (/2 F(To:++1)]
h=0
h=1
1=2
7: Estimate VeJ as per Theorem 2
Transition probability
8:
Update policy parameters (0) using Eq.
Figure 2: Transitions in c- BBandit MDP
We use an importance sampling estimator (log trick) to obtain Eq. (4). To reduce variance, we subtract a baseline b( Toss) from the score gradient, which can be function of the past trajectory To:j. This incorporates the causality property in the estimator, ensuring that the action at timestep j cannot affect previously observed states. After simplifying and considering marginals, we obtain Theorem 2 (proof is in Appendix D). This estimator assigns a higher weight to policies with high marginal gains and a lower weight to policies with low marginal gains. Empirically this performs very well (Section 7
We can optimize this approach by using an appropriate baseline as a function of the history To:j which leads to actor-critic type method. The versatility of the approach is demonstrated by the fact that Theorem 2 holds for any choice of baseline critic. We explain later in the experiments how to choose a baseline. One can perform Monte Carlo estimate (Baird 1993) or generalized advantage function (GAE) (Schulman et al., (016) to estimate returns based on the marginal gain. To encourage exploration, similar to standard PG,
employ soft policy update based entropy penalization, resulting in diverse trajectory samples. Entropy penalization in SUBRL can be thought of as the sum of modular and submodular rewards, which is a submodular function.
Algorithm. The outline of the steps is given in Algorithm | We represent the agent by a stochastic policy parameterized by neural network. The algorithm operates in epochs and assumes a way to generate samples from the environment, e.g., via a simulator. In each epoch, the agent recursively samples actions from stochastic policy and applies them in the environment leading a roll out of the trajectory where it collects samples (Line 6). We execute multiple (B) batches in each epoch for accurate gradient estimation. To update the policy, we compute the estimator the policy gradient as per Theorem [ where we utilize marginal gains of the trajectory instead of immediate rewards as in standard RL (Line) 7.. Finally, we use stochastic gradient ascent to update the policy parameters.
PROVABLE GUARANTEES IN SIMPLIFIED SETTINGS
In general, Section 33 shows SUBRL is NP-hard to approximate. A natural question is: Is it possible to do better under additional structural assumptions? In this section, we present two interesting cases under which SUBPO can approximate objective 22) up to a constant factor. Firstly, under assumptions on the underlying MDP we show its equivalence to -Rssubmodulaar optimization convex polytope. Secondly, for general MDPs, we capture the deviation of submodular rewards from the modular function using the notion of curvature and present constant factor approximation result for it.
Definition 1 (DR submodularity and DR property, Bian et al. (2017a)) For C Rd a function X IR is DR-submodular (has the DR property) if Va b X, Vi E [d]. Vk E R2 s.I. (ke; + a) and (ke; + bb) are still in X, it holds, f'kke; + a) - ((a) 2 skke; + b) [(b). (Notation: e, denotes ith basis vector and for any two vectors a, b, a S means a; S b,vi E [d)
Monotone DR-submodular functions form family of generally non-convex functions, which can be approximately optimized. As discussed below, gradient- based algorithms find constant factor approximations over general convex, downward-closed polytopes.
Under the following condition on the Markov chain, we can show that as long as the policy is parametrized in a particular way, the objective is indeed monotone DR-submodular.
Definition 2 (e- (e-Batdit SMDP). An SMDP s.t. for any Uj, UR E V. * k, Vh E [H] and Vu' e V. is an e-Bandit SMDP. VI+I
(v 10, (3) = Ej. and (vxlo' ..,) = 1 for eq E 0,
|V
This represents a "nearly deterministic" MDP where there is a unique action for each state in the MDP, which takes us to it with < probability and with the rest, we end up in any other state Fig. 2 While limiting. it generalizes the bandit scenario, which would occur when sider a class state-independent policies that can change in each horizon, denoting the horizon depen- dence with x² (a). We now formally establish the connection between SUBRL and DR- -usuooouuullrrty
0. In the following,
con-
5

---

Published as a conference paper at ICLR 2024
Theorem 3. For horizon dependent policy π parameterized as x² E [H] in an c-Bandit SMDP, and (T) is a monotone submodular function, then (T) is monotone DR-submodular.
The proof is in Appendix [
It builds two steps; firstly, we reparameterization trick to handle policy simplex constraints. We relax the equality constraints on a to lie on a convex polytope P =
(=*(a) 10 < (a) 1, = Σjsøt (ay) S 1, vk [[A]], wh E [H] and enforce the equality constraints directly in the objective Eq. (2). Secondly, under the assumptions of Theorem [ we show that the Hessian of ((r) only has non-positive entries, which is an equivalent characterization of twice differentiable ousuullo functions. Furthermore, the result can be generalized to accommodate state and action spaces that vary with horizons, although, for simplicity, we assumed fixed spaces,
The convex polytope P belongs proposes modified FRANK- WOLFE algorithm for DR-submodular maximization with down-closed constraints. This variant can achieve an (1 - 1/e) approximation guarantee and has sub-linear convergence rate. The algorithm proceeds as follows: the gradient oracle is the same as Theorem 2 while employing tabular policy parameterization. The polytopic constraints P are ensured through a FRANK-WOLAR step, which involves solving a linear program over the policy domain. Finally, the policy is updated with specific step size defined in (Bian et al., 2017c). Furthermore, |Hassani et al.) (2117) shows that any stationary point in the optimization landscape of DR-submodular maximization under general convex constraints is guaranteed to be 1/2 optimal. Therefore, any gradient- based optimizer can be used for the e- c-Bandit SMDP, and will result in an 1/2-optimal policy. In Section 6 we elaborate on how this setting generalizes previous works on submodular bandits.
class of down-closed convex constraints. Bian et al. (2017c)
General SMDP. While cannot obtain a provable result for general SMDP's (Theorem D. we can, interestingly, quantify the deviation of submodular function from a modular function using the notion of curvature (Conforti & Coruuéjoss] 1984). The curvature reflects how much the marginal values A(u(A) can decrease as a function A. The total curvature of F is defined as, = min A.j.A A(j Note that E [0, 1], and if c 0 then the marginal gain is independent of A (i.e., F is modular).
Proposition 3. Consider tabular SMDP, s.t. the reward function F is monotone submodular with bounded curvature e E (0, 1). Then, for the policy π (with tabular parametrization) obtained via SUBPO, it holds that J(T) 2 (1 (1-cl) (TT"), where x² is optimal non-Markovian policy.
Thus, under assumptions of bounded curvature, c (0, 1), we can guarantee constant factor optimality for SUBPO (proof in Appendix E.2). Vondrak (201)) establishes a survature-based hardness result for the simpler problem of submodular set function maximization under cardinality constraints, implying that 1 c is a near-optimal approximation ratio. Moreover, if c 0, i.e., F denotes modular rewards, the SUBPO algorithm reduces to standard PG, and hence recovers the guarantees and benefits of the modular PG. In particular, with tabular policy parameterization, under mild regularity assumptions, any stationary point of the modular PG cost function is a global optimum (Bhandari & Russo 2019).
6 RELATED WORK
Beyond Markovian RL. Several prior works in RL identify the deficiency in the modelling ability of classical Markovian rewards. This manifests itself especially when exploration is desired, e.g., when the transition dynamics are not completely known (Tarbouriech et al., 2020 Hazan al. 2019) or
when the reward is not completely known Lindner et al. (201)): Belogolovsky et al. (2021) Chatterji let al. (202T) considers binary feedback drawn from the logistic model at the end episode and explores state representation, such as additivity, to propose an algorithm capable of learning Mon-Markovian policies. While all these address in some aspect the shortcomings of Markovian rewards, they tend to focus on a specific aspect instead of postulating a new class of reward functions as we do in this work.
Convex RL. Convex RL also seeks to optimize a family of additive rewards. The goal is to find a policy that optimizes convex function over the state visitation distribution (which averages over the randomness in the MDP and the policies actions). This framework has applications, e.g., in exploration and experimental design (Hazan et al. 2019 Zahavy et al. 2021 Duff [2002] TTarbouricch] (ct al.) 2020 Mutny et al. 2023). While sharing some motivating applications, convex and submodular RL are rather different in nature. Beyond the high-level distinction that convex and submodular function classes are complimentary. our non-additive (submodular) rewards are defined over the actual sequence of states visited by the policy, not its average behaviour. |Mutti et al. (2022) points out that this results in substantial differences, noting the deficiency of convex RL in modelling expected utilities of the form in Eq. (2). which we address in our work.

---

Published as a conference paper at ICLR 2024
1.0
0.8
0.8
0.6
0.6
0.6
0.4
SubPO-NM
ModPO
0.5
0.2
0.2
0.4
30
(a) Coverage over Gorilla nests
(b) Item collection
(c) Experiment design
Figure 3: Comparison of SUBPO-M, SUBPO-NA PMPO-NMMA and MODPO, We observe that MODPO get stuck by repeatedly maximizing its modular reward, whereas SUBPO-M achieves comparable performance to SUBPO-NM while being more sample efficient. (Y-axis: normalized [TT), X-axis: epochs)
Submodular Maximization. Submodular functions are widely studied in combinatorial optimization and operations research and have found many applications in machine learning (Krause Golovin 2014, Bilmes] 2022; Tohidi et al., 2020). The seminal work of Nemhauser et al. (1978) shows that greedy algorithms enjoy a constant factor 1 - 1/e approximation for maximizing monotone submodular functions under cardinality constraints, which is information- and complexity- theoreti- cally optimal (Feigel 1998). Beyond simpler cardinality (and matroid) constraints, more complex constraints have been considered: most relevant is the s-t-submodular orienteering problem, which aims to find an s-t-path in a graph of bounded length maximizing a submodular function of the visited nodes (Chekuri & Pal 2005), and can be viewed as special case of SUBRL deterministic SMDP's with deterministic starting state and hard constraint on the goal state. It has been used as abstraction for informative path planning (Singh et al., 2009). We generalize the setup and connect it with modern policy gradient techniques, WWang et al. (2020) considers planning under the surrogate multi-linear extension of submodular objectives. Certain problems considered in our work satisfy a notion called adaptive submodularity, which generalizes the greedy approximation guarantee over a set of policies (Golovin & Krause, (01T). While adaptive submodularity allows capturing distory-dependence,, it fails to address complex constraints (such as those imposed by CMP's). s)).
While submodularity typically considered for discrete domains (i.e., for functions defined on {0, 13111, the concept can be generalized to continuous domains, e.g.. [0, 1] using notions such as DR-submodularity (Bian et al. (0176)) This notion forms a class of non-convex problems admitting
provable approximation guarantees polynomial time, which we exploit in Section 5 The problem of learning submodular functions has also been considered (Balcan & Harvey 2011 Dolhansky &
Bilmes (0166) introduce the class of deep submodular functions, neural network models guaranteed to yield functions that are submodular in their input. These may be relevant when learning unknown rewards using function approximation, which is an interesting direction for future work.
Since submodularity is natural characterization of diminishing returns, numerous tasks involving exploration or discouraging repeated actions (Basu et al., 2019)) can be captured via submodular functions. In addition to our experiments discussing experiment design, item collection and coverage objectives, Table provides a summary of problems that can be addressed with SUBRL.
The submodular bandit problem is at the interface of learning and optimizing submodular functions (Stretter & Golovin 2008; Chen et al.) [017]] Yue & Guestrin 2011). Algorithms with no-regret be improved by exploiting linearity Yuue & Guestrin 2011) or smoothness (Chen et al.) 2017) in the objective. Our results in Section be viewed as addressing (a generalization of) the submodular stochastic bandit problem. Exploiting further linearity or smoothness to improve sample complexity is interesting direction for future work.
(relative the 1- approximation) exist, whose performance
7 EXPERIMENTS
We empirically study the performance of SUBRI. multiple environments. They are i) Informative path planning, ii) Item collection, iii) Bayesian D-experimental design, iv) Building exploration, v) Car racing and vi) Mujoco-Ant. The environments involve discrete (i-iv) and continuous (v-vi) state- action spaces and capture a range of submodular rewards, illustrating the versatility of the framework.
The problem is challenging in two aspects: firstly, how to maximize submodular rewards, and secondly, how to maintain an effective state representation to enable distoryddependent policies. Our experiments mainly focus on the first aspect and demonstrate that even with simple Markovian state representation, by greedily maximizing marginal gains, one can achieve good performance similar to the ideal case of non-Markovian representation in many environments. However,
7

---

Published as a conference paper at ICLR 2024
(a) Building exploration
(b) Car racing
(c) Mujoco Ant
Figure 4: Challenging tasks modelled via submodular reward functions. Primarily, the agent at
location 8 senses a region, Da and seeks a policy to maximize submodular rewards F(r) = |User D* a) The agent, starting from the middle, must learn to explore both rooms. b) The car must learn to drive & finish the racing lap c) Ant must Iearn to walk to cover the maximum 2D space around itself.
do not claim that Markovian state representation is sufficient in general. For instance, in the building exploration and item collection environments, Markovian policies are insufficient, and a iistory-deependet approach is necessary for further optimization. Natural avenues are to augment the state representation to incorporate additional information, e.g.. based on domain knowledge, or use non-Markovian parametric policy class such RNNs. Exploring such representations is application specific, and beyond the scope of our work.
We consider two variants of SUBPO: SUBPO-M and SUBPO-NM, corresponding Markovian and non-Markovian policies, respectively. SUBPO-NE uses a stochastic policy that conditions an action on the history. We model the policy using a neural network that maps the history to a distribution over actions, whereas SUBPO-M maps the state to distribution over actions. Disregarding sample complexity, we expect SUBPO-NM perform the best, since it can track the complete history. In our experiments, we always compare with modular RL (MoDPO), baseline that represents standard RL, where the additive reward for any state is F({)). In MODPO, we maximize of additive rewards, whereas, in contrast, SUBPO maximizes marginal gains. The rest of the process remains the same, i.c., we use the same policy gradient method. We implemented all algorithms in Pytorch and will make the code and the videos public. We deploy Pytorch's automatic differentiation package to compute an unbiased gradient estimator. Experiment details and extended empirical analysis are in Appendix [F] Below explain observations for each environment:
undiscounted sum
Informative path planning. We simulate a bio-diversity monitoring task, where we aim to cover areas with high density of gorilla nests with quadrotor in the Kagwene Gorilla Sanctuary (Fig. [T]. The quadrotor at location s covers a limited sensing region around it, D The quadrotor starts in random initial state and follows deterministic dynamics. It is equipped with five discrete actions representing directions. Let p: V - IR. be the nest density obtained by fitting a smooth rate function (Mutny & Krause 2021) over Gorilla nest counts (Funwi-gabga & Mateu 2011). The objective function is given by F(T) g(U.er D*), where g(V) = 2 p(v). As shown in Fig. 3a we observe that MODPO repeatedly maximizes its modular reward and gets stuck at high-density region, whereas SUBPO achieves performance as good as SUBPO-NM while being more sample efficient. To generalize the analysis, we replace the nest density with randomly generated synthetic multimodal functions and observe a similar trend (Appendix F
Item collection. As shown in Fig. Tb the environment consists of grid with a group of items G = (banana, apple, strawberries, watermelon] located at 9i V. e G. We consider stochastic dynamics such that with probability 0.9, the action we take is executed, and with probability 0. a random action is executed (up, down, left, right, stay). The agent has to find policy that generates trajectories т. which picks de items from group 9i. for each Formally, the submodular reward function can be defined as F(T) Eieg min([7 O 9:l, d,). We performed the experiment with 10 different randomly generated environments and 20 runs in each. this environment, the agent must keep track of items collected so far to optimize for future items. Hence shown in Fig. 3b SUBPO-NM based on non-Marte Markovian policy achieves good performance, and SUBPO-M achieves slightly lower but yet comparable performance just by maximizing marginal gains.
Bayesian D-experimental design. this experiment, we seek to estimate an a-priori unknown function f. The function f is assumed to be regular enough to be modelled using Gaussian Processes. Where should we sample f to estimate it as well as possible? Formally, our goal to optimize over trajectories 7 that provide maximum mutual information between f and the observations y/- = te, at the points т. The mutual information is given by I(y+: f) = H H Hyy-lf), representing the reduction in uncertainty of f after knowing Vr, where H H is entropy. We define the monotonic submodular function F(r) I(y+: f). The gorilla nest density f is an a-priori unknown function. We generate 10 different environments by assuming random initialization and perform 20 runs
8

---

Published as a conference paper at ICLR 2024
0.8
SuNPO
1.0
0.6
ModPO
MedPO
0.8
SubPO-M
SuMPO-NM
0.6
0.6
0.4
0.4
0.2
20 40 60 80
100
200
300
400
100 200 300
400
(a) Building Exploration
(b) Car Racing
(c) Mujoco Ant
Figure 5: a) Coverage in building exploration, SUBPO-NM tracks history and can explore the other room b) Car trained with SUBPO-M M learns to drive through the track (Y-axis: normalized [O-star & 1-finish]) c) Ant trained with SUBPO-M M learns to explore the domain (Y-axis: normalized with the domain area). Both b.c) show that SUBPO scales very well to high dimensional continuous domains.
each to compute statistical confidence. In Fig. 3c we observe similar trend that MODPO gets stuck at high uncertainty region and cannot effectively optimize the information gained by the entire trajectory, whereas SUBPO-M achieves performance as good as SURPO-NM while being very sample efficient due to the smaller search space of the Markovian policy class.
Building exploration. The environment consists of two rooms connected by a corridor. The agent at covers a nearby region De around itself, marked as a green patch in Fig. 4a The task is to find trajectory T that maximizes the submodular function [rr)
U.er D= The agent starts in the corridor's 's middle and has deterministic dynamics. The horizon H is just enough to cover both rooms. Based on the augeeneeeetedd state space, there exists deterministic Markovian policy that can solve the task. However, it is a challenging environment for exploration with Monte Carlo samples using Markovian policies. As shown in Fig. 5a SuBPO achieves sub-optimal solution of exploring primarily one side, whereas SUBPO-NE NM tracks the history and learns to explore the other room.
Car Racing is an interesting high-dimensional environment, with continuous state-action space, where race car tries to finish the racing lap as fast as possible (Prajapat et al. 2021). The environment accompanied by an important challenge of learning a policy to maneuver the car the limit of handling. The track is challenging, consisting of 13 turns with different curvature (Fig. (4b). The car has six-dimensional state space representing position and velocities. The control commands are two-dimensional, representing throttle and steering. Detailed information is in the Appendix [F] The car is equipped with camera and observes patch around its state s as D The objective function is F(r)= User D We set finite horizon of 700. The SUBPO-NM, will have large state space of 700 x 6, which makes it difficult to train. For variance reduction, we use a baseline b(s) in Eq. (5) that estimates the cumulative sum of marginal gains. As shown in Fig. 56 under the coverage- based reward formulation, the agent trained with MODPO tries to explore a little bit but gets stuck with a stationary action at the beginning of the episode to get a maximum modular reward. However, the SUBPO agent tries to maximise the marginal again at each timestep and hence learns to drive on the race track (https://youtu. http://oouuuubbeexppeeee XeQxXXXX Although it is possible to alternative reward functions to train the car using standard RL, the main objective of this study is to demonstrate SUBPO on the continuous domains and how submodular functions can provide versatility achieve surrogate goals.
MuJoCo Ant. The task is a high-dimensional locomotion task, as depicted in Fig. 4c The state space dimension 30, containing information about the robot's pose and the internal actuator's 's orientation. The control input dimension is 8, consisting of torque commands for each actuator. The Ant at any location 8 covers locations in 2D space, D and receives a reward based on it. The goal is to maximize F(T) | User D*I The results depicted in Fig. 5c demonstrate that SUBPO maximizes marginal gain and learns to explore the environment, while MODPO learns to stay stationary, maximizing modular re- wards. The environment carries the core challenge of continuous control and high-dimensional obser- vation spaces. This experiment shows that SUBPO can effectively scale to high-dimensional domains.
8 CONCLUSION
We introduced novel framework, submodular RL for decision-making under submodular rewards. We prove the first-of-its-kind inapproximability result for SUBRL i.e., the problem is not just NP-Hard but intractable even to approximate up to any constant factor. We propose an algorithm, SUBPO for this problem and show that under simplified assumptions, it achieves constant-facta approximation guarantees. We show that the algorithm exhibits strong empirical performance and scales very well to high-dimensional spaces. We hope this work will expand the reach of the RL community to embrace the broad class of submodular objectives which are relevant many practical real-world problems.

---

Published as a conference paper at ICLR 2024
REPRODUCIBILITY STATEMENT
We have included all of the code and environments used in this study in the supplementary materials. These resources will be made open-source later on. The attached code contains README. md file that provides comprehensive instructions for running the experiments. Furthermore, Appendix FF] contains additional emperical results and the parameters reproduce the results. Regarding the theoretical results, all the proofs of the propositions and the theorems can be found in the appendix.
ACKNOWLEDGMENTS
This publication was made possible by an ETH AT Center doctoral fellowship to Manish Prajapat. We would like to thank Mohammad Reza Karimi, Pragnya Alatur and Riccardo De Santi for the insightful discussions. We thank Bhavya Sukhija and Alizée Pace for reviewing the manuscript.
The project has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation program grant agreement No 81 15943 and the Swiss National Science Foundation under NCCR Automation grant agreement 51NF40 180545.
REFERENCES
David Abel, Will Dabney, Anna Harutyunyan, Mark K Ho, Michael Littman, Doina Precup, and Satinder Singh. On the expressivity of markov reward. Advances in Neural Information Processing Systems, 34:7799-7812 7812, 2021.
Leemon C Baird, III. Advantage updating. WRIGHT LAB WRIGHT-PATTERSCE AFB OH, 1993.
Egbert Bakker, Lars Nyborg, and Hans B. Pacejka. Tyre modelling for use in vehicle dynamics studies. In SAE Technical Paper. SAE International, 02 1987. doi: 10.4271/870421.
Maria-Florina Balcan and Nicholas JA Harvey. Learning submodular functions. In Proceedings of the forly-third annual ACM symposium on Theory of computing, pp. 793-802, 2011.
Soumya Basu, Rajat Sen, Sujay Sanghavi, and Sanjay Shakkottai. Blocking bandits. Advances in Neural Information Processing Systems, 32, 2019.
Jonathan Baxter and Peter L Bartlett. Infinite-horizon policy-gradient estimation. journaal of artificial intelligence research, 15:319-350, 2001.
Stav Belogolovsky, Philip Korsunsky, Shie Mannor, Chen Tessler, and Tom Zahavy. Inverse rein- forcement learning in contextual mdps. Machine Learning, 2021.
Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. arXiv preprint 1xxiv:/906.0// 2019.
An Bian, Kfrr Levy, Andreas Krause, and Joachim M Buhmann. Continuous dr-submodular imization: Structure and algorithms. Advances in Neural Information Processing Systems, 30, 2017a.
Andrew An Bian, Joachim M Buhmann, Andreas Krause, and Sebastian Tschiatschek. Guarantees for greedy maximization of nunsuubma functions with applications. In International conference on machine learning, pp. 498-507. PMLR, 2017t 7b.
Andrew An Bian, Baharan Mirzasoleiman, Joachim Buhmann, and Andreas Krause. Guaranteed non- convex optimization: Submodular maximization over continuous domains. Artificial Intelligence and Statistics, pp. 111-120. PMLR, 2017c
Jeff Bilmes.
Submodularity in machine learning and artificial intelligence. arXiv preprint arXiv:2202.00132.. 2022.
Niladri Chatterji, Aldo Pacchiano, Peter Bartlett, and Michael Jordan. On the theory of reinforcement learning with -ece-pe--eiiooee feedback. Advances in Neural Information Processing Systems, 34: 3401-3412, 2021.
10

---

Published as a conference paper at ICLR 2024
Chandra Chekuri and M. Pal. A recursive greedy algorithm for walks in directed graphs. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'OS) pp. 245 045-2553222 2005. doi: S..109//FCS.2005.00
Lin Chen, Andreas Krause, and Amin Karbasi. Interactive submodular bandit. In NIPS, 2017.
Michele Conforti and Gérard Cornuéjols. Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the rado-edmonds theorem. Discrete Applied Mathematics, 7(3):51-223 1984. ISSN 0166-218X.
Brian W Dolhansky and Jeff Bilmes. Deep submodular functions: Definitions and learning. Advances in Neural Information Processing Systems, 29, 2016.
Michael O'Gordon Duff. Optimal learning: Computational procedures for Bayes -adaptive Markov decision processes. PhD thesis, University of Massachusetts Amherst, 2002.
Uriel Feige. A threshold of In for approximating set cover. J. ACM, 45(4))634-652, jul 1998. ISSN 0004-5411. doi: 10.1 145/285055.285559)
Michael C. Fu. Chapter 19 gradient estimation. In Shane G. Henderson and Barry L. Nelson (eds.), Simulation, volume of Handbooks Operations Research and Management Science, pp. 976-616. Elsevier, 2006. doi: http:://oo.oogll0000000000070773 (00010000000002220000000
Neba Funwi-gabga and Jorge Mateu. Understanding the nesting spatial behaviour of gorillas in the kagwene sanctuary, cameroon. Stochastic Environmental Research and Risk Assessment, 26, 08 2011. doi:
0001///000077-11--5411
Daniel Golovin and Andreas Krause. Adaptive submodularity: Theory and applications active learning and stochastic optimization. Journal of Artificial Intelligence Research, 42:427-486, 2011.
Evan Greensmith, Peter L Bartlett, and Jonathan Baxter. Variance reduction techniques for gradient estimates reinforcement learning. Journal of Machine Learning Research, 5(9), 2004.
Aldy Gunawan, Hoong Chuin Lau, and Picter Vanstcenwegen. Orienteering problem: A survey of recent variants, solution approaches and applications. European Journal of Operational Research, 255(2):315 332, 2016. ISSN 0377-2217. doi: http://oi.orr/1...11........ 20..00..5.
Eran Halperin and Robert Krauthgamer. Polylogarithmic inapproximability. In Proceedings of the Thirty-Fifih Annual ACM Symposium on Theory of Computing, STOC '03, pp. 5944 Association for Computing Machinery, 2003. ISBN 1581136749,
doi: 10. 10.114577805227788665
Hamed Hassani, Mahdi Soltanolkotabi, and Amin Karbasi. Gradient methods for submodular maximization. Advances Neural Information Processing Systems, 30, 2017.
Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum entropy exploration. International Conference on Machine Learning, pp. 2681-2691. PMLR, 2019.
Sham M Kakade. A natural policy gradient. Advances in neural information processing systems, 14, 2001.
Mohammad Karimi et Stochastic submodular maximization: The case of coverage functions. Advances in Neural Information Processing Systems, 30, 2017.
Miquel Kegeleirs, Giorgio Grisetti, and Mauro Birattari. Swarm slam: Challenges and perspectives. Frontiers in Robotics and AI, 8:61 8268, 2021.
Andreas Krause and Daniel Golovin. Submodular function maximization. Tructability, 3:71-104, 2014.
Andreas Krause, Ajit Singh, and Carlos Guestrin. Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies. J. Mach. Learn. Res., 9:235-284 jun 2008. ISSN 1532-4435.
11

---

Published as a conference paper at ICLR 2024
David Lindner, Matteo Turchetta, Sebastian Tschiatschek, Kamil Ciosek, and Andreas Krause. Information directed reward learning for reinforcement learning. In Proc. Neural Information Processing Systems (NeurIPS), December 2021.
Alexander Liniger, Alexander Domahidi, and Manfred Morari. Optimization- autonomous racing of 1: 43 scale re cars. Optimal Control Applications and Methods, 36(5):628-66) 647, 2015.
Mojmír Mutný and Andreas Krause. Sensing cox processes via posterior sampling and positive bases. CoRR, abs/21 11181, 2021.
Mojmir Mutny, Tadeusz Janik, and Andreas Krause. Active exploration via experiment design in markov chains. In International Conference on Artificial Intelligence and Statistics, pp. 7349-7374.
PMLR, 2023.
Mirco Mutti, Riccardo De Santi, Piersilvio De Bartolomeis, and Marcello Restelli. Challenging com- mon assumptions in convex reinforcement learning. Advances in Neural Information Processing Systems, 15:4489-4500 2022.
George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions-i. Mathematical programming, 14(1):265 26252244,, 1978.
Manish Prajapat, Kamyar Azizzadenesheli, Alexander Liniger, Yisong Yue, and Anima Anandkumar, Competitive policy optimization. In Uncertainty in Artificial Intelligence, pp. 64-74. PMLR, 2021.
Manish Prajapat, Matteo Turchetta, Melanie Zeilinger, and Andreas Krause. Near-optimal multi- agent learning for safe coverage control. Advances in Neural Information Prucessing Systems, 35: 14998-15012, 2022.
Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., USA, 1st edition, 1994. ISBN 0471619779.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In ICML, pp. 1889-1897. PMLR, 2015.
John Schulman, Philipp Moritz, Sergey Levine, Michael I. Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. In 4th International Conference Learning Representations, ICLR, 2016.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347. 2017.
Amarjeet Singh, Andreas Krause, and William J. Kaiser. Nonmyopic adaptive informative path planning for multiple robots. In Proceedings of the 2 International Joint Conference on Artificial Intelligence, IJCAI'09 09, pp. 1843-1850, San Francisco, CA, USA, 2009.
Matthew Streeter and Daniel Golovin. An online algorithm for maximizing submodular functions. Advances in Neural Information Processing Systems, 21, 2008
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
Jean Tarbouriech, Shubhanshu Shekhar, Matteo Pirotta, Mohammad Ghavamzadeh, and Alessandro Lazaric. Active model estimation in markov decision processes. In Conference on Uncertainty in Artificial Intelligence, pp. 1019-1028, PMLR, 2020.
Ehsan Tohidi, Rouhollah Amiri, Mario Coutino, David Gesbert, Geert Leus, and Amin Karbasi. Submodularity in action: From machine learning to signal processing applications. IEEE Signal Processing Magazine, 37(5):120-133 2020. doi: 10. 10.1109//SP2000033033336
Jan Vondrak. Submodularity and curvature: the optimal algorithm. RIMS Kōkyýroku Bessatsu, 01 2010.
12

---

Published as a conference paper at ICLR 2024
Ruosong Wang, Hanrui Zhang, Devendra Singh Chaplot, Denis Garagié, and Ruslan Salakhutdinov. Planning with submodular objective functions. arXiv preprint arXiv2201011886, 2020.
Yisong Yue and Carlos Guestrin. Linear submodular bandits and their application to diversified retrieval. Advances in Neural Information Processing Systems, 24, 2011.
Tom Zahavy, Brendan O'Donoghue, Guillaume Desjardins, and Satinder Singh. Reward is enough for convex mdps In 35th Conference on Neural Information Processing Systems (NeurIPS 202/). 2021.
13

---

Published as a conference paper at ICLR 2024
Part I Appendix
A PROOF FOR PROPOSITIONS
Proposition 1. For any deterministic MDP with a fixed initial state, the optimal Markovian policy achieves the same value as the optimal non-Markovian policy.
Proof. The proof consists of two parts. First, we establish the existence of an optimal deterministic non-Markovian policy for deterministic MDP M with non-Markovian rewards F. Second, we demonstrate that the trajectory generated by the optimal deterministic NM policy (TNA)) in M can also be generated by a deterministic Markovian policy (TM). Since both policies yield the same trajectory, resulting in: J (TTM)) = J (TT). (Notably, it is sufficient to look at a value of the single induced trajectory since we consider a deterministic policy in a deterministic MDP with fixed initial state.)
i) We can construct an extended MDP, denoted as Me. where the state space consists of trajectories Tu:h for all time steps h [H]. In Me. the trajectory rewards F are Markovian. Due to Markovian rewards in Me. there exists an optimal deterministic Markovian policy for Me (Puterman, 1994) that, when projected back M, corresponds to non-Markovian policy (TTM)-
ii Without loss of generality, let = ((5o, on), (81,01),.. a1),..., ,8H) be a trajectory induced by ANM E T If the states augmented with time, the same trajectory is induced by deterministic Markovian policy defined as TM (s:) = 1 and TM(ay (s:) = 0 for of j. Vi, Due to the identical induced trajectory, we have (TTM (TTM).
Proposition 2. For any set function F, among the Markovian policies Ny, there exists an optimal policy that is deterministic.
Proof. Given any stochastic policy, it is possible to select a state and modify the action distribution at that state to a deterministic action such that the value of the new policy will be least equal the value of the original policy. Below we show a construction to ensure the monotonic improvement of the policy,
W.l.ogg,, suppose there are two actions, denoted as aş and of. available at a state sy. (the argument remains applicable for any finite number of actions). Consider the objective ((r) as shown below (for simplicity, we wrote only the trajectories affected with action at horizon l: at state sx).
H-1
((T] Σ ((s)) ter
II i=0
p" (5 (,)
F F([(so: oo), ... (ok, aw 8H
8-1
= =m((s)) rET:(SL.ELEET
p (s ai) i=
II
p² (S ax) n (arlss)
H II 0
>' (((0))
(8++ (asl8))
p*(4441l80 dh) x² (aklsx) F(()
"
(remaining terms, do not vary with and y) The objective is to maximize J(T) subject simplex constraints. The policy remains fixed for all states except sg. It is important to note that J is a linear function of variables r and y. Given that J is linear within the simplex constraints, the optimal solution lies on a vertex of the simplex (x* (ax (8k) + x *a (aglss) = 1). This vertex represents a deterministic decision for state
+ +constant
We can define new policy x' based on и by adjusting the action distribution at sk to the optimal deterministic action (either a' az). It is evident that J(r') 2 (TT). This process can be repeated for states. By starting with any optimal stochastic policy, we can obtain a deterministic policy that is at least as good as the original stochastic policy. This concludes the proof.
14

---

Published as a conference paper at ICLR 2024
Graph to MDP
SOP
SubRL
step a
f(r))
a 2 2 (log (log!~OPP OPT)
step
step
8 z
step
roll out the policy
Figure 6: Reduction of SUBRL to submodular orienteering problem (SOP)
B INAPPROXIMABILIY PROOF
First, we introduce a set of known hard problems that we will use to establish the hardness of SUBRL.
Group Steiner tree (GST). The input to the group Steiner problem is an edge-weighted graph CV(VE, I) and k subsets of nodes I1, .2....... I. called groups. Starting from root node the goal in GST is to find a minimum weight tree T (V(T"), E(T*)) in G such that each group is visited at least once, i.e., V(T*) ngg + 0. Vi E [k].
Covering Steiner problem (SCP). The input to SCP is an weightei graph G = (V,E, E. and k subsets of groups 91- : 9k, each group has a positive integer d: representing minimum visiting requirement. Starting from a root node r, the goal in SCP is to find a minimum weight tree T (T*)), F(()))) )) in G such that the tree covers at least d, nodes in group 9r. i.e., (V(")))))) 2 d, Vi E [b:] The SCP generalizes GST problem to an arbitrary constraint d,-
Submodular Orienteering Problem (SOP). In rooted SOP, are given a root node r E V and the goal is to find a walk 7 of length at most B that maximizes some submodular function F defined on the nodes of the underlying graph.
Approximation ratio: Let x be an input instance of a maximization problem. The approximation ratio 1, where OPT is the global optimal and ALG is the value attained by the algorithm. The hardness lower bound and approximation upper bounds refer to the lower and upper bound on the approximation ratio B.
OPT(w)
is defined as 3 Z ALG(a)
Let OPT be the optimal value and 7 > 0. Even for deterministic SMDP's, the SUBRL problem is hard approximale within a factor of 2(log" OPT) unless NP C ZZTIE (nooaloooo
Theorem 1.
Proof. We reduce SUBRL to rooted SOP, demonstrating the inapproximability SUBRL. Lemma establishes the hardness of rooted SOP.
Given an instance of SOP with a graph G (V, E)) and a root node r E V. the goal is to find a walk that maximizes submodular function F(7), subject to budget constraint |r] < B. This can be
converted to a SMDP (input to SUBRL), (S, P.p. F, H) tuple in polynomial time as follows:
i) Set S + H x..VAAL E, H + B, p(0,r) r) = and the submodular function F remains unchanged. ti) Iterate over the edges e E E. Let = (v', v), set P((h+ + 1, (/), a) = 1, for all E [H - I] where action
The solution to the SUBRL problem is a policy æ that can be rolled out to obtain a solution for the SOP, which is also polynomial time operation. By assuming the existence of polynomial time algorithm for SUBRL with an approximation ratio 3 = o(log OPT). we can approximate SOP with
(Fig. 60. However, this contradicts the fact that rooted SOP cannot be approximated better than Q(log' OPT) (Lemmal) I Proved by contradiction.
F(7)
P(r") 8
The results shows that there is no algorithm that guarantee ((x) instances. As OPT increases with the input size of the problem, the ratio log OPT degrades and hence algorithm can approximate the problem up any constant factor > O. For the sake of completeness, we include Theorem 4.1 from from/Ched Chekuri & Pal (2005) and modify it for the rooted SOP. The reduction scheme is the same as Chekuri & Pal 20055.
OPT log--7 OPT for all the input
15

---

Published as a conference paper at ICLR 2024
Lemma (Theorem 4.1 from Chekuri & Pal (2005 ). The rooted submodular orienteering problem
(SOP) in undirected graphs is hard to approximate within factor of 22(oo" 17 OPT) unless NP S
ZTIME((Pooslooomm))
Proof. The group Steiner problem (GST) is hard to approximate to within factor of 22log" OPT)
unless NP has quasi-polynomia time Las Vegas algorithms (Halperin & Krauthgamer (003). We
reduce the problem of rooted SOP GST, proving the inapproximability of rooted SOP. This
represents that if we have an efficient algorithm for SOP, then we can recover solution for GST by using the same SOP algorithm.
Submodular function F. Given an SCP instance, define submodular function P(S) =
Σ min(d,, g(). F is monotone submodular set function.
Consider an optimal solution of SCP as 7 of cost OPT. We can take an Euler tour of the tree T and obtain tour from of length most 20PT that covers all groups.
Reduction. We will reduce rooted SOP problem to the SCP (SCP generalises GST with any d,>0). Let's say have algorithm A for SOP with Sillog E, d:). (,, d, is optimal value for SOP). In single iteration, A will generate a walk that covers ((V(T*) J(V(T*)) of length B, which can be converted tour P of length at most BB. We remove the nodes in P and reduce the coverage requirement of the groups that are partially covered and repeat the above procedure. Using Lemma 2 all groups will be covered up to the requisite amount in Ollog Σ, d,) iterations. Combining all the tours yields a tree of length (log" E de) B that is a "feasible solution" of the SCP. B can be evaluated using binary search and is within constant factor of OPT. When specialized to the GST, i.e., d, 1, the approximability ratio becomes O(log* k).
Contradiction. Following the reduction above, assuming an algorithm A for SOP with an approx- imation ratio of log l results O(log" k) approximation ratio for GST. Hence, an a = o(log k) approximation algorithm for SOP will give approximation of O(a log k) for GST. But GST is hard to approximate within a factor of Q(log2 OPT). Hence SOP is hard approximate within factor of
Lemma 2. A algorithm for SOP with approximability ratio M(lo k) can cover k nodes after O(log 2 k) iterations.
Proof. Let La be the nodes available after the th iteration with an algorithm having 3 2 2(logk).
Lo k
Lo log Lo
L + Lo
Ln
Lnt1 +- Ln
log Ln
lng
In the first iteration with k
L log x
x(1 log
S xe loge
ke ket
By definition, L, > L2 ... Lns hence L, kc ke- 1/ Vi E [1,
Nodes available after n iteration Lo log Lo (1
Log Li
log Lum
1
Lo(1 log Lo ((1 log L, (1
) < ke - 1/ logk e llogk 1/ log
log Ln
= ke -n/ log
for n >> log" k. nodes available: -n- log ke log² k/ log k ke- log 1. Hence Proved. 1
16

---

Published as a conference paper at ICLR 2024
C DISCUSSION
Submodularity. Since the algorithm and the theoretical hardness result readily extend to general functions beyond submodular rewards, natural question that arises is how critical is that F is submodular function and what can we say beyond submodular rewards? In this work, submodularity emerges in the lower bound (inapproximability hardness), implying that the problem is not just intractable but intractable even to approximate up to any constant factor. Additionally, it emerges in the upper bound of - c under curvature assumption and in the upper bound of (1 - 1/e) under the simplified SMDP setting. There cannot exist an algorithm for bandit SMDP with better guarantees (Fegee 1998), and St:PO is able to achieve the optimal ratio (1 1/e), thus utilising submodularity to provide intuition on why SUBPO (a REINFORCE type strategy) is right strategy.
Overall, submodularity lets us characterise the spectrum of the computational complexity of the SubRL framework, while some results, e.g., our algorithm SUBPO, inapproximability hardness, naturally carry over to the general non-Markovain rewards beyond submodular F (general non- additive reward function).
Policy class. The restriction to Markovian policies in the theoretical limits section is mainly for emphasizing the "hardness result" even for the simple policy class, implying the source of hardness is not the representation of non- Mon-Markovinn policy (which is an exponential object itself). The overall goal is to learn a policy that achieves higher objective value; hence, we do not, in general, restrict it to the Markovian policy class. We treat the problem of learning state representation separately, which can be done, e.g. with RNN, and is an add-on the SUBPO, e.g. SUBPO-NM optimises in non-Markovian policy class.
The optimal policies for submodular rewards cannot be captured by the Markovian rewards in general since the optimal policies are non-Markovian. However, when the policy search is restricted to the Markovian class, the optimal policy deterministic (Proposition [ and hence there exists a Markovian reward that would lead to the same optimal policy. But this does not help to solve the problem since finding such Markovian rewards has to be NP-hard to approximate Theorem [I
Expressivity of rewards.
In contrast to finding such surrogate Markovian rewards, submodularity provides a natural way to capture the task. Moreover, since do not restrict to the Markovian policies, given policy class with compact history representation, SUBPO can learn behaviours beyond the expressivity of the Markovian rewards (Abel et al.) 2021).
Applications. Since submodularity is a natural characterization of diminishing returns, numerous tasks involving exploration or discouraging repeated actions can be captured via submodular functions. In addition to our experiments discussing experiment design, item collection and coverage objectives, the following Table [ provides summary of problems that can be addressed with SUBRL.
Tasks
Relevant works
Submodular reward function F(T)
State entropy exploration
Hazan et al.
2019
F(T) = न E log [(:().)))))
[-|
D-Optimal Experimental Design
Mutny et al.
2023
F(T) = 1ly+; f), ((y f) = ()r)) (vvls)
Steiner covering
Chekuri & Pal
2005
F(r) = Es min(| n gel. d:), pick d: items of group ga
State coverage functions
Prajapat et al.
2022
F(T) = Evevl [H] (v. t) E T) F(T) = UUerr D
Weighted coverage function
Karimi al.
2017
F(F) = g(U.er gV) Evev
Discourage repeated action/
(Basu et al.
2019)
F(T) = -USEr e.g, (v, and
(including coverage on Time)
D* (c,+t))
2)}
Log determinant objectives
Wang et al.
2020
F(T) = log det (Ener ((())) + AT)
Facility location
Krause & Golovin (0144)
F(T) = E. maxjer Ms.j. M,j 2 0
Table 1: A few examples that can be tackled with submodular reinforcement learning framework
17

---

Published as a conference paper at ICLR 2024
D SUBMODULAR POLICY OPTIMIZATION, SUBPO'S POLICY GRADIENT PROOF
Theorem 2. Given an SMDP and the policy parameters 0, with any set function F,
F(s)+1|TOg) - b(To:s) ]
H -1
H-1
(T)(TT))= = E
Ve mo no (a
Σ
(5)
Tref(TsT))
Proof. The performance measure given by,
J(TA)
E ((r())))))
[F(T)] = Σ ((F
thus, the gradient with respect to 0 is given by
VaJ(mo) Σ ((f(T;=))F(T)
For any (T) o 0 using log trick, Vo log compute the gradient of the objective. Let define Q(T:Te) Vo II # - no (a)(ss))) resulting in Eq.
Vopo(r) from standard calculus and the definition
po(+)
of f(r; TT) in Eq. !
VOJ(TO) = Σ
(log
II
To Fo(a))s:))F( = Σ f( (0)
Σ 1=0
Va log (agl8))) F(T)
(6)
Using marginal gain ((s)Tos) = F(To. U{s}) - F(Tos) and telescopic sum Σ F(s)421T05)) F(r) - F(oo).
H-1
VOJ(TT)) = E ruf(rim))
Σ
V log To (a(lss)))
Σ F(3)-1|TOs)) + F(50)
H
Σ F(sj+1lma)) + F(so) ]
E (eu((ro))
Σ
Vo log (a(a))))
For any function of partial trajectory up to i, b' BT(ss) we have. Σ To(a,)s: (:) log (a ((,)))((TTo)))
= Σ Vans(a. 8; 5,)00' (To..) Thus one can subtract any history-dependent baseline without altering
the gradient estimator,
Σ + b' (TT..) ]
V log (a)ss)
(=f((r
#
]
Σ
Ve log mo (a.ls:)
Σ
F(3
(=((F))))
Finally, we can subtract a baseline again using a similar trick as above and we get the theorem statement:
F(3s+1lTo3) ((TOz) )
Σ
Ve log (a(a)s)))
18

---

Published as a conference paper at ICLR 2024
a1
a1
VO
ao
VO
a0
VO
ag
a0
a1
a1
ag
ao
V1
V1
V1
a1
aj
ag
a0
h=0
h=1
h=2
Transition probability
Figure 7: Nomenclature: With action, a, from any state the agent jumps to state with probability
1 (solid), and with probability it jumps any other state uniformly (dashed)
E PROVABLE GUARANTEES IN SIMPLIFIED SETTINGS
E. DR-SUBMODULARITY PROOF
Theorem For horizon dependent policy a parameterized as n² (a)oh E [H] in an c-Bandit SMDP, and FT) is monotone submodular function, then (xr is monotone DR-submodular.
Proof. e-Bandit MDP considers state independent transitions (only horizon dependent), i.e., Fj E V. * k. Vh [4] and Ve' V. (uylo',
Eh, and Ph (uslt', .a)) - for
en [00, 0.0 1 For simplicity, we consider fixed size V. but it can also vary with the horizon. To denote explicit dependent on the horizon, we use PA, and v instead of directly s.
Similarly, policy parameterization in Theorem 3 considers state independent policy (only horizon dependent) x² (a(l'') = T (alv")th E [H) Yo', v" E V. in short notation we denote them as π (a)..
Note that >" (a./u:) corresponds to the self-loop actions ("stay"). In the proof, we reparameterize the probability of self-loop actions with that of other actions (i.e., n (ax//rz) = Eaza, x2 (alv:))
resulting in relaxation of the simplex constraint CE. n" (alu) 1, Wh, Eafa, T² (all)) $1).
In the following, for ease of notation, denote v; == (i, v). in particular, F((y/, a:) (H) F((i, ax) H-1 (H,v)) Consider the objective J(T).
H-1
((T) = Σ ((vO)
II A=
Pa (Un+1le%, on (anlu) a:) W- vg)
Ter
H-1
Σ ((vo) PET
II
Ph
at) H-1 =i vg) (state independent assumptions)
We show DR-submodularity by showing VT E P. Oeidzn < 0, Vo' T" E P. We first reparame- terize the self-loop actions (which bring the agent back the same state) in J(TT) by substituting T² (a/ = 1 Enjaj (all))) in (TT). Here a' is a looping action for state o at horizon h.
First, prove monotonicity of J (TT) by showing (J(z)
0.
aJ(TT) 0n (ah))
aJ (T) "a)((()) w'ev
Σ
where,
19

---

Published as a conference paper at ICLR 2024
(T) θTh (d/))
En(ro) I [ as)
II n
(an)
F ao)
(ohh (1/+1: an+i); (0++2,a++2) ... u1)) up)
af i=0
H-1
H 1
-E((o)) rET 1=
II p:(0442la))
I n
(an)
F((vo, (oh, oh), (ch+1 ant1), (Uh+2, an+2)....0 UH)
Agpts
B
We prove a),((m) (a 0 for any vt, which implies 0J(m) (n"(a 2 0. Note: For every trajectory in
E (r ere (v/, x)) 7} (1st summation), we have trajectory in L = {r e e: (v an) E r (2nd summation) that differ only in 2/411 and v/__ and all other states are exactly same. For every trajectory in L, there is a trajectory in E with a higher value. We define a short notation H-1
fn = u(vo) II pe ((0++laa))7( denotes trajectory distribution ignoring transition at Uh. 1yhh
E TEL
oo), (.th ah),, (1/+1 0n+1), (vu+2, (142) (..42)..U00 UH)
1olo (1 ah), (1h 1) (14+2, 0142) ....H)))
Note f"r, and Sth are equal due state independent transition and policy. Drop the actions (the function F depends on the states) and let R == T\2,,
Σ
(F(RU (1h+1)) - F(R)) 2 0 1' - Eh |
eh
(since, en S D
[V1-1
TE
The reason for en ( (1- pa(vh+rlah) ph (v/ (a))) and -
ph((/+11ah) = ph (1 In Eq. 7. the two terms (corresponding to set L and E) are sub- tracted, with probability (1 - (n) the first term will be larger since F(R U (v/+11)) F(R) 2 0 and with probability ch - the second term will be larger since the stochastic transition (e.g., looping
action of, can jump to next state 1/411 and n', stays to the same state o This can happen with probability )
In other stochastic transitions, in expectation, the two terms will sum to zero
In the above, have proved the monotonicity of ((x) given F(.) is monotone function. We have,
OJ(x) On (a
|
H-1
H
E (1(oo)(1
II A=0
Pa (n lax)
II n (ax) light
(F(RU (th+1)) -((d))))F(R)))
F(R)) 20
M
To obtain the hessian terms, we can follow the same process as above at some horizon g and state a". Let R (i, ,""), (v" is the state corresponding to action a"),
J²](TT) = ES
|Vlg
|VEAR
)
V
rer
(FRRULY 19t1 v/4z3) (FFt))-F(RRI
F(R))
Σ CT
[
TeT
F(RU (TRUtUTt 1 (lthhul(())))))))))
-FRUU F(RU (((R))))))))))
<0
By submodularity of F, R. (
Hence J(x= is monotone DR-submodular.
20

---

Published as a conference paper at ICLR 2024
E.2 BOUNDED CURVATURE
Proposition 3. Consider labular SMDP, s.t. the reward function F is monotone submodular with bounded curvature e (0, 1). Then, for the policy a (with labular parametrization) obtained via SUBPO, it holds that (x) 2 (1 (x) where n¹ is an optimal non-Markovian policy.
Proof. Consider the objectives (xx and (T) defined with submodular reward F(T) and its corre- sponding modular rewards (T) Eser F(s) respectively,
J(T) = Σ F(T:)) and H(T) [((T)))
For any policy n, J(x) 2 (1 (T) using curvature definition. Consider V ((T),
V+J(x)= Σ V (()
Σ (al(Ti))
3 F(8:41/TO:) + F(tso))
2 Σ V+J(T;))
Σ (1 (1-c) (1-=c)F((s))))
(using curvature definition)
-1- c) Σ (m; =1-
Similarly, since Fm 2 F(T) 2 Pm (T), the following holds component-wise,
(T 2 V J.)( 2 (1 (1=c)V; Va'.
(8)
At the convergence of SuBPO, the stationary point π satisfies,
max (=) - < 0
t'Ell
max ( 0. E'E
(using Eq.
8
c +
1)
Hence π is also a stationary point for modular objective HT)). Under mild regularity assumptions, any stationary point the policy gradient cost function with modular rewards global optimum (Bhandari & Russo 2019). Let π be the policy where SUBPO converges, then,
J(x) (() - c) Σ (((:T)
(9)
(1 c) Σ f(T;T))Fm(())
(10)
= 2 (1 c) Σ -1--)))) ()][()
(11)
Eq. (9) follows using curvature definition for any policy x. Eq. (10 follows since a is optimal of
H (()) where x² E ThM is optimal for J(z). Finally, Eq. (1) follows since (r) ' F(r). n
21

---

Published as a conference paper at ICLR 2024
1.0
1.0
0.8
0.8
0.8
0.5
0.6
SuhPO-M
0.4
SukPO-NM
0.4
ModPO
0.2
0.2
(a) Constant weights
(b) Bimodal distribution
(c) Gaussian Processes
Figure 8: Comparison SUBPO-M, SUBPO-NM and MODPO. We observe that MoDPO gets stuck by repeatedly maximizing its modular reward, whereas SUBPO-M achieves comparable performance to SUBPO-NM while being more sample efficient. (Y-axis: normalized [T), X-axis: epochs)
F EXPERIMENTS
In this work, examined state-action spaces that both discrete (finite) and continuous. Here, provide an overview of the hyperparameters and experiment specifics for each type.
F.1 FINITE STATE ACTION SPACES
We consider grid world environment with domain size 30 30, having total of 900 states. Horizon H = 40, i.e., the agent has to find a path of length 40 that jointly maximize the objective. The action comprised of (right, up, left, down, stay). The agent's policy was parameterized by a two-layer multi-layer perceptron, consisting of 64 neurons in each layer. The non-linearity in the network was induced by employing the Rectified Linear Unit (ReLU) activation function. By employing stochastic policy, the agent generated categorical distribution over the action set for each state. Subsequently, this distribution was passed through softmax probability function. We employed batch size of B = 500 and a low entropy coefficient of a = 0 or 0.005, depending on the specific characteristics of the environment.
We randomly generated ten different environments and conducted 20 runs for each environment, resulting in a total 200 experiments. These experiments were executed concurrently on a server with 400 cores, allocating two cores for each job. It takes less than 20 minutes to complete 150 epochs and obtain a saturated policy, indicating no further improvement. All our plot shows the training curve (objective epochs).
For instances where we utilized randomly sampled environments, such as coverage with GP samples, gorilla nest density, item collection environment, we have included the corresponding environment files in the attached code for easy reference.
To conduct additional analysis using the Informative Path Planning Environment, made modifica- tions to the underlying function previously based on gorilla nest density. Specifically, we introduced three variations: i) constant function, ii) bimodal distribution, and iii) multi-modal distribution randomly sampled from a Gaussian Process (GP). As depicted in Figure g we noticed a consistent trend across all three variations. The MODPO algorithm repeatedly maximized its modular reward but became trapped in high-density regions. In contrast, the SUBPO-M algorithm demonstrated performance comparable SUBPO-NM while exhibiting greater sample efficiency.
F.2 CONTINUOUS STATE-ACTION SPACES
Car Racing. In the car racing environment, our objective is to achieve the fastest completion of one-lap race. To accomplish this, we aim to learn a policy that effectively controls a car operating at its handling limits. Our simulation study closely emulates the experimental platform employed at ETH Zurich, which utilizes miniature autonomous race cars. Building upon Liniger et al. (2015), we model the dynamics of each car using dynamic bicycle model augmented with Pacejka tire models (akkkrr et al. 1987). However, we deviate from the approach presented in (Liniger et al. 2015) by formulating the dynamics in curvilinear coordinates. where the car's position and orientation are represented relative to reference path. This coordinate transformation significantly simplifies the reward definition and facilitates policy learning. The state representation of individual
22

---

Published as a conference paper at ICLR 2024
is denoted
d., , Vy, v0]". Here, p measures the progress along the reference path, quantifies the deviation from the reference path, I characterizes the local heading relative to the reference path, V₂ and Vy represent the longitudinal and lateral velocities in the car's frame, respectively, and & represents the car's yaw rate. The car's inputs represented as [D, 8)3, where D E [-1, 1] represents the duty cycle input to the electric motor, ranging from full braking at -1 to full acceleration at and 8 |-1, corresponds to the steering angle.
The car is equipped with a camera and observes a patch around its state s as D The objective function is ((T) User D*I For simplicity, we define the observation patch of some and spanning the entire width of the race track. We add additive reward penalization to avoid hitting the walls. If narrow-width patch is used, then one can eliminate the use of reward penalization (used to avoid hitting the boundaries) as coverage near the boundaries is low and the agent Iearns to drive in the middle or go to the extreme if they gain due to going fast. The test track, depicted in Figure 4b) consists of 13 turns with varying curvatures. We utilize an optimized X-Y path as the reference path obtained through a lap time optimization tool. is worth noting that using a pre-optimized reference path is not obligatory, but we observed improved algorithm convergence when employing this approach. To convert the continuous-tine dynamics into a discrete-time Markov Decision Process (MDP), we discretize the dynamics using an RK4 integrator with sampling time of 0.03 seconds.
For the training, we started the players the start line (p 0) and randomly assigned d' E (0.1.-0.1] We limit one episode to 700 horizon. For each policy gradient step, we generated a batch of 8 game trajectories and ran the training for roughly 6000 epochs until the player consistently finished the lap. This takes roughly hour of training for a single-core CPU. We use Adam optimizer with slow learning rate of 10 3, For our experiments, we ran 20 different random runs and reported the mean of all the seeds. As a policy, we use a multi-layer perceptron with two hidden layers, each with 128 neurons and used ReLU activation functions and Tanh output layer to enforce the input constraints. For variance reduction, we use a baseline b(s) in Eq. (5) that estimates the cumulative sum of marginal gains. One can think of this as a heuristic to estimate marginal gains. The same setting was also used for the competing algorithm ModPO.
MuJoCo. It is physics engine for simulating digh-dimensional continuous control tasks in robotics. In this experiment, we consider the Ant environment, which is depictive of the core challenges that arise in the Mujoco environment. For detailed information about the Mujoco Ant environment, we refer the reader to https://gymmasiumm.. fwwamaa.aaaaaaaaaaaaaa www///aaiiiooonnns//ooooo///////
For the training, we use the default random initialization of Mujoco-Ant. We consider a bounded domain of [-20, 20 The agent covers discrete grid of 5x5 around its location in the 2D space (only for efficient reward computation, we discretize the domain into a 400 x 400 grid, dynamics is continuous) and receives reward based on the coverage. To train the agent faster, one can also couple MuJoCo's 's inbuilt additive rewards (tuned for faster walking) with the submodular coverage rewards, which results in submodular rewards.
We limit one episode to a horizon of 400. We use a vectorized environment that samples a batch of 15 trajectories once. We trained for roughly 20,000 epochs until the agent consistently walks and explores the domain. This takes roughly 6 hours of training for a single-core CPU. We use Adam optimizer with learning rate of 10 2, For our experiments, we ran 20 different random runs and reported the mean of all the seeds. As policy, we use multi-layer perceptron with two hidden layers, each with 128 neurons and used ReLU activation functions and a Tanh output layer to enforce the input constraints. Similar to the car racing environment, we use baseline b(s) in Eq. (5) that estimates the cumulative sum of marginal gains. The same setting was also used for the competing algorithm MoDPO.
23


Reviews:
[{"review_id": "xXPsQZppTD", "reviewer": "Reviewer_u5A8", "summary": "This paper studies submodular reinforcement learning, i.e. reinforcement learning with submodular set reward function that captures diminishing returns. Specifically, this paper has made the following contributions:\n\n- This paper motivates and develops the framework of submodular reinforcement learning.\n\n- This paper derives a lower bound that establishes hardness of approximation up to log factors in general (Theorem 1, Section 3).\n\n- This paper motivates and develops a general algorithm for the considered problem, referred to as Submodular Policy Optimization (SubPO, Algorithm 1). This is a policy optimization algorithm. Provable guarantees are established in some restricted settings (Section 5).\n\n- Extensive and rigorous experiment results are demonstrated in Section 7.", "questions": "- Please try to address the weaknesses listed above.\n\n- It is not clear to me why the authors chose to put the \"Related Work\" section between an analysis section and the experiment section. Probably the authors should put it after Introduction.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The considered problem is interesting and significant.\n\n- Extensive and rigorous experiment results have been presented in Section 7.\n\n- The paper is well-written in general, and easy to read.", "weaknesses": "- The idea behind the proposed algorithm, Submodulr Policy Optimization, is quite straightforward. It is just a relatively straightforward extension of the classical policy optimization algorithm.\n\n- The analysis in Section 5 seems to be very restricted. Could the authors provide a similar analysis in more general settings?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iHuHqVziza", "reviewer": "Reviewer_uscY", "summary": "In this paper, the authors propose a submodular reinforcement learning (subRL) setting. Different from the existing reinforcement learning settings, they do not assume the rewards are additive. This allows them to work with more general and history-dependent reward models and they characterize these reward models with submodularity. Moreover, they design a policy gradient-based algorithm, called subPO, for  subRL problems by drawing inspiration from the greedy algorithm for classical submodular problems.", "questions": "- Are there other attempts of incorporating submodular functions to reinforcement learning problems?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "Combining submodularity with reinforcement learning in a generalized way seems highly intuitive that I am surprised it has not been proposed before. This emphasizes the significance of the paper's contribution. The main idea of the paper is a simple yet powerful one. Additionally, the paper is well written and the ideas or conveyed clearly.", "weaknesses": "These are more minor suggestions for improvement rather than weaknesses:\n- On the last paragraph of page 1, the adverbs firstly, secondly, thirdly can be just replaced with first, second, and third. Also, we after the firstly should be lowercase.\n- I think there can be a broader discussion of using submodular functions in reinforcement learning setups in the related work section. I am aware that the introduction also mentions some examples of submodular rewards, but I believe it is interesting enough to have its own paragraph in the related work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wAc3Kx6pbB", "reviewer": "Reviewer_6FV4", "summary": "The submission considers a new framework of Submodular Reinforcement Learning (SubRL), where the total reward is given as a submodular function of given trajectories, rather than as an additive sum of rewards from individual time steps. From my understanding, the main applications of interest would have environments where repeated actions (at the same states) are not so much preferred -- this is explicitly embedded in the reward design itself in SubRL. Contributions are the following:\n\n- While the optimal policy can still be Markovian, the authors first show that approximating the optimal value up to any constant factor is computationally hard in polynomial time (that is, planning is computationally hard). \n\n- Given an additional assumption that the reward function is DR-submodular, AND if the underlying MDP is nearly deterministic, then a constant factor approximation is possible.\n\n- The authors present a policy-gradient type algorithm for SubRL, and demonstrate the effectiveness of the method on several interesting synthetic examples and deep-RL settings.", "questions": "- I do not understand what it means by $\\pi$ is parameterized by $\\pi^h(a)$ in Theorem 3. Does this mean $\\pi$ does not depend on the state? \n\n- Definition 2 - why is it named \\epsilon-\"Bandit\" SMDP? \n\n- The submission focuses on the \"planning\" side. Any thoughts on the \"learning\" side? (a.k.a., exploration and sample complexity)", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The submission introduces a novel and \"mathematically\" interesting framework that accounts for diminishing returns of repeated actions. \n\n- The view of submodular rewards is fresh. The hardness result is new and interesting. \n\n- The selected toy examples sound interesting and well-suited for the proposed framework.", "weaknesses": "- I do not see much contribution in positive results. Not only does the assumption sound strong from a practical perspective, but it seems quite contrived only for the sake of analysis. \n\n- Literature review: I agree with the motivation from diminishing returns, but a submodular reward design is not the only way to address that. For example, there is a blocking-bandit style framework that discourages repeated actions [1]. Maybe good to discuss why the submodular reward design is better. \n\nI also encourage authors to survey more existing works that explore similar ideas with submodular reward design. For example, can the authors explain the difference between [2] in terms of the problem setting?\n\n[1] Basu et al., Blocking Bandits, NeurIPS 2019.\n\n[2] Chen et al., Contextual Combinatorial Multi-armed Bandits with Volatile Arms and Submodular Reward, NeurIPS 2018. \n\n- Suggestion: It looks slightly unnatural to have Section 4 (practical algorithms) in between hardness results (Section 3) and positive results (Section 5). A more natural flow would have been having the positive theoretical results first and then presenting practical algorithms, or at least having them connected. \n\n- Overall, I feel that the framework is well-motivated for the \"mathematical\" purpose but less sound for the practical purpose or advancing the theory of RL.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JPYvZZ7btL", "reviewer": "Reviewer_oKKZ", "summary": "This paper proposes and studies submodular MDPs, where the total reward is characterized by a submodular function of the trajectory. The authors first show that computing a logarithmic approximation of the optimal policy is computational intractable. However, there exists a polocy optimization algorithm which gives a (1-c)-approximation where c is the curvature of the submodular function. Specifically, when specified to bandits, this result outperforms existing ones.", "questions": "See weaknesses.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The model is well-motivated and clearly described. It is also easy to understand.\n2. The results contain both upper and lower bounds, which are pretty complete.\n3. Empirical evaluations are conducted for the proposed algorithm.", "weaknesses": "1. I'm not sure why this paper considers multiplicative approximations instead of regret/sample complexity, which are common in theory papers studying episodic MDPs.\n2. The optimal dependency on curvature remains unspecified. Whether Proposition 3 is (near-)optimal?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)