Solving General-Utility Markov Decision Processes in the Single-Trial Regime with Online Planning
Not on the map. Why?
Abstract (arXiv)
In this work, we contribute the first approach to solve infinite-horizon discounted general-utility Markov decision processes (GUMDPs) in the single-trial regime, i.e., when the agent's performance is evaluated based on a single trajectory. First, we provide some fundamental results regarding policy optimization in the single-trial regime, investigating which class of policies suffices for optimality, casting our problem as a particular MDP that is equivalent to our original problem, as well as studying the computational hardness of policy optimization in the single-trial regime. Second, we show how we can leverage online planning techniques, in particular a Monte-Carlo tree search algorithm, to solve GUMDPs in the single-trial regime. Third, we provide experimental results showcasing the superior performance of our approach in comparison to relevant baselines.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 12 of its 31 references that are in the map. First posted on arXiv 21 May 2025.
Builds on
12 of 31 references.
References · 12
- 2015Continuous control with deep reinforcement learningcited by 3,407
- 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
- 2018Diversity is All You Need: Learning Skills without a Reward Functioncited by 752
- 2018An Algorithmic Perspective on Imitation Learningcited by 459
- 2018Provably Efficient Maximum Entropy Explorationcited by 242
- 2020Exploration-Exploitation in Constrained MDPscited by 149
- 2018Variational Option Discovery Algorithmscited by 122
- 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 111
- 2021Reward is enough for convex MDPscited by 84
- 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
- 2021Concave Utility Reinforcement Learning: the Mean-Field Game Viewpointcited by 56
- 2025Polynomial Regret Concentration of UCB for Non-Deterministic State Transitionscited by 1
Built on by
Citing papers per year: 2026: 1.
1 paper.
- 2026Risk-Aware General-Utility Markov Decision Processescited by 0
- 2026Risk-Aware General-Utility Markov Decision Processes10 Jul 2026