Sufficiency of Deterministic Policies for Atomless Discounted and Uniformly Absorbing MDPs with Multiple Criteria

Feinberg, Eugene A and Piunovskiy, Aleksey B (2019) Sufficiency of Deterministic Policies for Atomless Discounted and Uniformly Absorbing MDPs with Multiple Criteria. SIAM Journal on Control and Optimization, 57 (1). pp. 163-191.

Text 1806.06170v2.pdf - Submitted version Download (535kB)

Abstract

This paper studies Markov decision processes (MDPs) with atomless initial state distributions and atomless transition probabilities. Such MDPs are called atomless. The initial state distribution is considered to be fixed. We show that for discounted MDPs with bounded one-step reward vector-functions, for each policy there exists a deterministic (that is, nonrandomized and stationary) policy with the same performance vector. This fact is proved in the paper for a more general class of uniformly absorbing MDPs with expected total rewards, and then it is extended under certain assumptions to MDPs with unbounded rewards. For problems with multiple criteria and constraints, the results of this paper imply that for atomless MDPs studied in this paper it is sufficient to consider only deterministic policies, while without the atomless assumption it is well-known that randomized policies can outperform deterministic ones. We also provide an example of an MDP demonstrating that if a vector measure is defined on a standard Borel space, then Lyapunov's convexity theorem is a special case of the described results.

Item Type:	Article
Uncontrolled Keywords:	math.OC, math.OC
Depositing User:	Symplectic Admin
Date Deposited:	20 Aug 2018 10:31
Last Modified:	19 Jan 2023 01:28
DOI:	10.1137/18M1194924
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3025186