Strongly polynomial algorithms for transient and average-cost MDPs

Eugene A. Feinberg; Jefferson Huang

doi:10.1145/3152042.3152045

Strongly polynomial algorithms for transient and average-cost MDPs

Eugene A. Feinberg
, Jefferson Huang

Applied Mathematics and Statistics

Cornell University

Research output: Contribution to journal › Conference article › peer-review

Abstract

This paper considers transient total-cost MDPs with transition rates whose values may be greater than one, and average-cost MDPs satisfying the condition that the expected time to hit a certain state from any initial state and under any stationary policy is bounded above by a constant. Linear programming formulations for such MDPs are provided that are solvable in strongly polynomial time.

Original language	English
Pages (from-to)	6-8
Number of pages	3
Journal	Performance Evaluation Review
Volume	45
Issue number	2
DOIs	https://doi.org/10.1145/3152042.3152045
State	Published - Sep 1 2017
Event	Workshop on MAthematical Performance Modeling and Analysis, MAMA 2017, 2017 Greenmetrics Workshop and Workshop on Critical Infrastructure Network Security, CINS 2017 - Urbana-Champaign, United States Duration: Jun 1 2017 → …

Keywords

Algorithm
Average cost
Linear program
Markov decision process
Total cost
Transient

Access to Document

10.1145/3152042.3152045

Cite this

@article{e32cd4dec0be4fd79540573392d74a86,

title = "Strongly polynomial algorithms for transient and average-cost MDPs",

abstract = "This paper considers transient total-cost MDPs with transition rates whose values may be greater than one, and average-cost MDPs satisfying the condition that the expected time to hit a certain state from any initial state and under any stationary policy is bounded above by a constant. Linear programming formulations for such MDPs are provided that are solvable in strongly polynomial time.",

keywords = "Algorithm, Average cost, Linear program, Markov decision process, Total cost, Transient",

author = "Feinberg, \{Eugene A.\} and Jefferson Huang",

note = "Publisher Copyright: Copyright is held by author/owner(s).; Workshop on MAthematical Performance Modeling and Analysis, MAMA 2017, 2017 Greenmetrics Workshop and Workshop on Critical Infrastructure Network Security, CINS 2017 ; Conference date: 01-06-2017",

year = "2017",

month = sep,

day = "1",

doi = "10.1145/3152042.3152045",

language = "English",

volume = "45",

pages = "6--8",

journal = "Performance Evaluation Review",

issn = "0163-5999",

number = "2",

}

TY - JOUR

T1 - Strongly polynomial algorithms for transient and average-cost MDPs

AU - Feinberg, Eugene A.

AU - Huang, Jefferson

N1 - Publisher Copyright: Copyright is held by author/owner(s).

PY - 2017/9/1

Y1 - 2017/9/1

N2 - This paper considers transient total-cost MDPs with transition rates whose values may be greater than one, and average-cost MDPs satisfying the condition that the expected time to hit a certain state from any initial state and under any stationary policy is bounded above by a constant. Linear programming formulations for such MDPs are provided that are solvable in strongly polynomial time.

AB - This paper considers transient total-cost MDPs with transition rates whose values may be greater than one, and average-cost MDPs satisfying the condition that the expected time to hit a certain state from any initial state and under any stationary policy is bounded above by a constant. Linear programming formulations for such MDPs are provided that are solvable in strongly polynomial time.

KW - Algorithm

KW - Average cost

KW - Linear program

KW - Markov decision process

KW - Total cost

KW - Transient

UR - https://www.scopus.com/pages/publications/85041400140

U2 - 10.1145/3152042.3152045

DO - 10.1145/3152042.3152045

M3 - Conference article

AN - SCOPUS:85041400140

SN - 0163-5999

VL - 45

SP - 6

EP - 8

JO - Performance Evaluation Review

JF - Performance Evaluation Review

IS - 2

T2 - Workshop on MAthematical Performance Modeling and Analysis, MAMA 2017, 2017 Greenmetrics Workshop and Workshop on Critical Infrastructure Network Security, CINS 2017

Y2 - 1 June 2017

ER -

Strongly polynomial algorithms for transient and average-cost MDPs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this