Metraipolis › archive › dc_0b64cbebe69b
Strong and Compact Policies for Submodular Markov Decision Processes via LP-Based Submodular Orienteering — arXiv:2609.15539
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.15539
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T00:15:56.476Z
- SHA-256 of the archived text
20f884b360b3c19a618e89a0696f15a58cf9bceba1cd8acab4f7cffa0da03a0f- Stable URL of this page
https://metraipolis.com/documento/dc_0b64cbebe69b
How to cite
Strong and Compact Policies for Submodular Markov Decision Processes via LP-Based Submodular Orienteering — arXiv:2609.15539 — arXiv (en), https://arxiv.org/abs/2609.15539 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0b64cbebe69b (Metraipolis archive dc_0b64cbebe69b, sha256 20f884b360b3c19a618e89a0696f15a58cf9bceba1cd8acab4f7cffa0da03a0f)
BibTeX
@misc{dc0b64cbebe69b,
title = {Strong and Compact Policies for Submodular Markov Decision Processes via LP-Based Submodular Orienteering — arXiv:2609.15539},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.15539},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0b64cbebe69b; sha256 20f884b360b3c19a618e89a0696f15a58cf9bceba1cd8acab4f7cffa0da03a0f},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.15539. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-15 in cs.LG).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.15539 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T23:54:14.971Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).