SOURCE-LINKED INTELLIGENCE

Strong and Compact Policies for Submodular Markov Decision Processes via LP-Based Submodular Orienteering

arXiv · AI, language, vision and robotics · article · Sep 14, 2026 · UTC

Finding policies for Markov Decision Processes (MDPs) is a central problem in areas such as Reinforcement Learning and Operations Research. Here, we have to repeatedly choose an action that should be performed by an agent. Depending on the action and the current state of the agent, the agent collects a reward and randomly transitions into a new state. The goal is to maximize the reward in expectation over a finite time horizon of length $H$. We consider a recently introduced variant that generalizes the traditionally additive reward function in the model to a monotone submodular one, which all

Read original source ↗ Open in workspace

recordType

paper

region

Global