Markov Decision Processes with Terminal States: Occupancy Measure and Algorithms

Motivated by text generation in large language models, where the policy determines both the response content and termination via an end-of-sequence token, we study Markov decision processes (MDPs) with terminal states without discounting. In contrast to the fixed-horizon and infinite-horizon MDPs widely studied in the literature, in our setting, both cumulative reward and trajectory length depend on the policy. While infinite-horizon MDPs typically use discounted rewards to ensure finite returns, the undiscounted cumulative reward objective is finite in this setting, provided that every stationary policy terminates almost surely. Assuming every stationary policy terminates almost surely, we establish that feasible state-action occupancy measures form a compact convex polytope, with expected return and termination time acting as linear functionals. Building on this geometry, we prove that any convex combination of these measures is realizable by an explicitly constructed stationary policy, and that the $K$-fold undiscounted Bellman operator is a strict contraction. Finally, we derive Trust-Region Policy Optimization (TRPO) and Natural Policy Gradient (NPG) algorithms for this setting, providing sufficient conditions for monotonic improvement and non-asymptotic convergence rates.