Planning with Submodular Objective Functions
- URL: http://arxiv.org/abs/2010.11863v1
- Date: Thu, 22 Oct 2020 16:55:12 GMT
- Title: Planning with Submodular Objective Functions
- Authors: Ruosong Wang, Hanrui Zhang, Devendra Singh Chaplot, Denis Garagi\'c,
Ruslan Salakhutdinov
- Abstract summary: We study planning with submodular objective functions, where instead of maximizing cumulative reward, the goal is to maximize the value induced by a submodular function.
Our framework subsumes standard planning and submodular objective with cardinality constraints as special cases.
- Score: 118.0376288522372
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study planning with submodular objective functions, where instead of
maximizing the cumulative reward, the goal is to maximize the objective value
induced by a submodular function. Our framework subsumes standard planning and
submodular maximization with cardinality constraints as special cases, and thus
many practical applications can be naturally formulated within our framework.
Based on the notion of multilinear extension, we propose a novel and
theoretically principled algorithmic framework for planning with submodular
objective functions, which recovers classical algorithms when applied to the
two special cases mentioned above. Empirically, our approach significantly
outperforms baseline algorithms on synthetic environments and navigation tasks.
Related papers
- Submodular Framework for Structured-Sparse Optimal Transport [7.030105924295838]
Unbalanced optimal transport (UOT) has recently gained much attention due to its flexible framework for handling unnormalized measures and its robustness.
In this work, we explore learning (structured) sparse transport plans in the UOT setting, i.e., transport plans have an upper bound on the number of non-sparse entries in each column.
We propose novel sparsity-constrained UOT formulations building on the recently explored mean discrepancy based UOT.
arXiv Detail & Related papers (2024-06-07T13:11:04Z) - Data Summarization beyond Monotonicity: Non-monotone Two-Stage
Submodular Maximization [11.296845424426062]
The objective of a two-stage submodular problem is to reduce the ground set using provided training functions that are submodular.
This problem has applications in various domains including data summarization.
arXiv Detail & Related papers (2023-09-11T01:00:10Z) - Reinforcement Learning with Non-Cumulative Objective [12.906500431427716]
In reinforcement learning, the objective is almost always defined as a emphcumulative function over the rewards along the process.
In this paper, we propose a modification to existing algorithms for optimizing such objectives.
arXiv Detail & Related papers (2023-07-11T01:20:09Z) - Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
We present a new algorithm for a policy gradient in TMDPs by a simple extension of the proximal policy optimization (PPO) algorithm.
We demonstrate this on a real-world multiple-objective navigation problem with an arbitrary ordering of objectives both in simulation and on a real robot.
arXiv Detail & Related papers (2022-09-15T07:22:58Z) - Group Equality in Adaptive Submodular Maximization [13.619980548779687]
We study the classic submodular problem subject to a group equality constraint under both non-adaptive and adaptive settings.
We develop the first constant approximation algorithm for this problem.
arXiv Detail & Related papers (2022-07-07T15:12:02Z) - srMO-BO-3GP: A sequential regularized multi-objective constrained
Bayesian optimization for design applications [7.571408082650611]
We propose a novel multi-objective (MO) extension, called srMO-BO-3GP, to solve the MO optimization problems in a sequential setting.
The proposed framework is demonstrated using several numerical benchmark functions, as well as a thermomechanical finite element model for flip-chip package design optimization.
arXiv Detail & Related papers (2020-07-07T14:40:00Z) - Jump Operator Planning: Goal-Conditioned Policy Ensembles and Zero-Shot
Transfer [71.44215606325005]
We propose a novel framework called Jump-Operator Dynamic Programming for quickly computing solutions within a super-exponential space of sequential sub-goal tasks.
This approach involves controlling over an ensemble of reusable goal-conditioned polices functioning as temporally extended actions.
We then identify classes of objective functions on this subspace whose solutions are invariant to the grounding, resulting in optimal zero-shot transfer.
arXiv Detail & Related papers (2020-07-06T05:13:20Z) - Continuous Submodular Function Maximization [91.17492610120324]
Continuous submodularity is a class of functions with a wide spectrum of applications.
We identify several applications of continuous submodular optimization, ranging from influence, MAP for inferences to inferences to field field.
arXiv Detail & Related papers (2020-06-24T04:37:31Z) - On the Global Optimality of Model-Agnostic Meta-Learning [133.16370011229776]
Model-a meta-learning (MAML) formulates meta-learning as a bilevel optimization problem, where the inner level solves each subtask based on a shared prior.
We characterize optimality of the stationary points attained by MAML for both learning and supervised learning, where the inner-level outer-level problems are solved via first-order optimization methods.
arXiv Detail & Related papers (2020-06-23T17:33:14Z) - Divide-and-Conquer Monte Carlo Tree Search For Goal-Directed Planning [78.65083326918351]
We consider alternatives to an implicit sequential planning assumption.
We propose Divide-and-Conquer Monte Carlo Tree Search (DC-MCTS) for approximating the optimal plan.
We show that this algorithmic flexibility over planning order leads to improved results in navigation tasks in grid-worlds.
arXiv Detail & Related papers (2020-04-23T18:08:58Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.