# The Number of Trials Matters in Infinite-Horizon General-Utility Markov Decision Processes

arXiv: https://arxiv.org/abs/2409.15128 · HTML: https://mlsanity.com/paper/2409.15128/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 41 references that are in the map.
- First posted on arXiv 23 Sep 2024.

## Builds on (most cited first, 10 of 10)

- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Diversity is All You Need: Learning Skills without a Reward Function](https://mlsanity.com/paper/1802.06070/) (2018)
- [An Algorithmic Perspective on Imitation Learning](https://mlsanity.com/paper/1811.06711/) (2018)
- [Provably Efficient Maximum Entropy Exploration](https://mlsanity.com/paper/1812.02690/) (2018)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [Variational Option Discovery Algorithms](https://mlsanity.com/paper/1807.10299/) (2018)
- [Variational Policy Gradient Method for Reinforcement Learning with General Utilities](https://mlsanity.com/paper/2007.02151/) (2020)
- [Reward is enough for convex MDPs](https://mlsanity.com/paper/2106.00661/) (2021)
- [Concave Utility Reinforcement Learning: the Mean-Field Game Viewpoint](https://mlsanity.com/paper/2106.03787/) (2021)

## Built on by (most cited first, 3 of 3)

- [The Geometry of Nonlinear Reinforcement Learning](https://mlsanity.com/paper/2509.01432/) (2025)
- [Active Inference as a Convex Markov Decision Process](https://mlsanity.com/paper/2607.20152/) (2026)
- [Global Optimality for Constrained Exploration via Penalty Regularization](https://mlsanity.com/paper/2604.28144/) (2026)

## Abstract (arXiv)

The general-utility Markov decision processes (GUMDPs) framework generalizes the MDPs framework by considering objective functions that depend on the frequency of visitation of state-action pairs induced by a given policy. In this work, we contribute with the first analysis on the impact of the number of trials, i.e., the number of randomly sampled trajectories, in infinite-horizon GUMDPs. We show that, as opposed to standard MDPs, the number of trials plays a key-role in infinite-horizon GUMDPs and the expected performance of a given policy depends, in general, on the number of trials. We consider both discounted and average GUMDPs, where the objective function depends, respectively, on discounted and average frequencies of visitation of state-action pairs. First, we study policy evaluation under discounted GUMDPs, proving lower and upper bounds on the mismatch between the finite and infinite trials formulations for GUMDPs. Second, we address average GUMDPs, studying how different classes of GUMDPs impact the mismatch between the finite and infinite trials formulations. Third, we provide a set of empirical results to support our claims, highlighting how the number of trajectories and the structure of the underlying GUMDP influence policy evaluation.