On the Minimum Pair Approach for Average Cost Markov Decision Processes with Countable Discrete Action Spaces and Strictly Unbounded Costs

DOI10.1137/19M1247395zbMATH Open1432.90160arXiv1902.10685MaRDI QIDQ5220188FDOQ5220188

Authors: Huizhen Yu 

Publication date: 11 March 2020

Published in: SIAM Journal on Control and Optimization (Search for Journal in Brave)

Abstract: We consider average-cost Markov decision processes (MDPs) with Borel state spaces, countable, discrete action spaces, and strictly unbounded one-stage costs. For the minimum pair approach, we introduce a new majorization condition on the state transition stochastic kernel, in place of the commonly required continuity conditions on the MDP model. We combine this majorization condition with Lusin's theorem to prove the existence of a stationary minimum pair, i.e., a stationary policy paired with an invariant probability measure induced on the state space, with the property that the pair attains the minimum long-run average cost over all policies and initial distributions. We also establish other optimality properties of a stationary minimum pair, and for the stationary policy in such a pair, under additional recurrence or regularity conditions, we prove its pathwise optimality and strong optimality. Our results can be applied to a class of countable action space MDPs in which the dynamics and one-stage costs are discontinuous with respect to the state variable.

Full work available at URL: https://arxiv.org/abs/1902.10685

Recommendations

• On linear programming for constrained and unconstrained average-cost Markov decision processes with countable action spaces and strictly unbounded costs
• Exact finite approximations of average-cost countable Markov decision processes
• On strong average optimality of Markov decision processes with unbounded costs
• Denumerable continuous-time Markov decision processes with multiconstraints on average costs
• Approximation of average cost optimal policies for general Markov decision processes with unbounded costs
• Value iteration in countable state average cost Markov decision processes with unbounded costs
• Countable state Markov decision processes with unbounded jump rates and discounted cost: optimality equation and approximations
• Average cost Markov decision processes with weakly continuous transition probabilities
• Finite-State Approximations to Discounted and Average Cost Constrained Markov Decision Processes

zbMATH Keywords

Markov decision processesBorel state spacecountable actionsmajorization conditionminimum pairstrong and pathwise average cost optimality

Mathematics Subject Classification ID

Dynamic programming (90C39) Markov and semi-Markov decision processes (90C40) Optimal stochastic control (93E20)

Cites Work

• Markov Chains and Stochastic Stability
• Title not available (Why is that?)
• Title not available (Why is that?)
• Real Analysis and Probability
• General Irreducible Markov Chains and Non-Negative Operators
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Stochastic optimal control. The discrete time case
• Average Cost Optimal Stationary Policies in Infinite State Markov Decision Processes with Unbounded Costs
• The policy iteration algorithm for average reward Markov decision processes with general state space
• Title not available (Why is that?)
• Average Optimality in Dynamic Programming with General State Space
• Title not available (Why is that?)
• On Linear Programming in a Markov Decision Problem
• Average optimality in dynamic programming on Borel spaces -- unbounded costs and controls
• Average cost Markov decision processes with weakly continuous transition probabilities
• Title not available (Why is that?)
• Sample-path average optimality for Markov control processes
• Universally Measurable Policies in Dynamic Programming
• Weak conditions for average optimality in Markov control processes
• On Minimum Cost Per Unit Time Control of Markov Chains
• Sample path average optimality of Markov control processes with strictly unbounded cost
• The Existence of a Minimum Pair of State and Policy for Markov Decision Processes under the Hypothesis of Doeblin
• A mixed value and policy iteration method for stochastic control with universally measurable policies

Cited In (5)

• A survey of average cost problems in deterministic discrete-time control systems
• Convex analytic method revisited: further optimality results and performance of deterministic policies in average cost stochastic control
• Average cost optimality inequality for Markov decision processes with Borel spaces and universally measurable policies
• On structural properties of optimal average cost functions in Markov decision processes with Borel spaces and universally measurable policies
• On linear programming for constrained and unconstrained average-cost Markov decision processes with countable action spaces and strictly unbounded costs

This page was built for publication: On the Minimum Pair Approach for Average Cost Markov Decision Processes with Countable Discrete Action Spaces and Strictly Unbounded Costs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5220188)