Improved methods for decision making in submodular Markov processes
Strong and Compact Policies for Submodular Markov Decision Processes via LP-Based Submodular Orienteering
Data Structures and AlgorithmsMachine Learning
Summary
Making decisions over time to maximize rewards can be tricky when outcomes depend on chance and past choices. The authors study a general version of this problem where the rewards have a property called submodularity, which captures many real-world situations with diminishing returns. They develop new mathematical tools and algorithms that find better decision strategies much faster than before. Their approach also shows how to balance how much past information the agent uses when deciding what to do next.
What this means in practice
- •For operations research teams: Design better policies for resource allocation and routing tasks where rewards have diminishing returns and uncertainty.
- •For reinforcement learning developers: Create more efficient learning algorithms that handle complex reward structures beyond simple sums.
Authors
Lars Rohwedder, Rico Zenklusen
Abstract
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 allows for capturing a range of interesting applications. Without the stochastic component, this problem is equivalent to the Submodular Orienteering problem, where the goal is to find an $s$-$t$ walk in a directed graph maximizing a monotone submodular function under a length constraint. We present a novel LP-based algorithm for Submodular Orienteering using ideas from the Sherali-Adams hierarchy and Round-or-Cut. Our guarantees are comparable to the known quasi-polynomial time logarithmic approximation for Submodular Orienteering, but also extend to the setting of Submodular Markov Decision Processes. In the polynomial time regime, we present an $O(n^{\varepsilon})$-approximation (and $O(H^{\varepsilon})$ for Submodular MDPs) for every $\varepsilon >0$, where $n$ is the number of vertices, which was unknown even for Submodular Orienteering. Prior to our work, the best known approximation guarantee for Submodular MDPs had an approximation ratio linear in $H$. Beyond these algorithmic results, our methods reveal a trade-off between the approximation guarantee and the number of previously visited vertices on which an agent conditions its decision.