Convergence of value iterations for total-cost MDPs and POMDPs with general state and action sets

Eugene A. Feinberg; Pavlo O. Kasyanov; Michael Z. Zgurovsky

doi:10.1109/ADPRL.2014.7010613

Convergence of value iterations for total-cost MDPs and POMDPs with general state and action sets

Eugene A. Feinberg
, Pavlo O. Kasyanov
, Michael Z. Zgurovsky

Applied Mathematics and Statistics

National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

7 Scopus citations

Abstract

This paper describes conditions for convergence to optimal values of the dynamic programming algorithm applied to total-cost Markov Decision Processes (MDPSs) with Borel state and action sets and with possibly unbounded one-step cost functions. It also studies applications of these results to Partially Observable MDPs (POMDPs). It is well-known that POMDPs can be reduced to special MDPs, called Completely Observable MDPs (COMDPs), whose state spaces are sets of probabilities of the original states. This paper describes conditions on POMDPs under which optimal policies for COMDPs can be found by value iteration. In other words, this paper provides sufficient conditions for solving total-costs POMDPs with infinite state, observation and action sets by dynamic programming. Examples of applications to filtration, identification, and inventory control are provided.

Original language	English
Title of host publication	IEEE SSCI 2014 - 2014 IEEE Symposium Series on Computational Intelligence - ADPRL 2014
Subtitle of host publication	2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)	9781479945535
DOIs	https://doi.org/10.1109/ADPRL.2014.7010613
State	Published - Jan 14 2014
Event	2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, ADPRL 2014 - Orlando, United States Duration: Dec 9 2014 → Dec 12 2014

Publication series

Name	IEEE SSCI 2014 - 2014 IEEE Symposium Series on Computational Intelligence - ADPRL 2014: 2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, Proceedings

Conference

Conference	2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, ADPRL 2014
Country/Territory	United States
City	Orlando
Period	12/9/14 → 12/12/14

Access to Document

10.1109/ADPRL.2014.7010613

Cite this

Feinberg, E. A., Kasyanov, P. O., & Zgurovsky, M. Z. (2014). Convergence of value iterations for total-cost MDPs and POMDPs with general state and action sets. In IEEE SSCI 2014 - 2014 IEEE Symposium Series on Computational Intelligence - ADPRL 2014: 2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, Proceedings Article 7010613 (IEEE SSCI 2014 - 2014 IEEE Symposium Series on Computational Intelligence - ADPRL 2014: 2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ADPRL.2014.7010613

Feinberg, Eugene A. ; Kasyanov, Pavlo O. ; Zgurovsky, Michael Z. / Convergence of value iterations for total-cost MDPs and POMDPs with general state and action sets. IEEE SSCI 2014 - 2014 IEEE Symposium Series on Computational Intelligence - ADPRL 2014: 2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, Proceedings. Institute of Electrical and Electronics Engineers Inc., 2014. (IEEE SSCI 2014 - 2014 IEEE Symposium Series on Computational Intelligence - ADPRL 2014: 2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, Proceedings).

@inproceedings{973aaead6d6341469a65006bee807de0,

title = "Convergence of value iterations for total-cost MDPs and POMDPs with general state and action sets",

abstract = "This paper describes conditions for convergence to optimal values of the dynamic programming algorithm applied to total-cost Markov Decision Processes (MDPSs) with Borel state and action sets and with possibly unbounded one-step cost functions. It also studies applications of these results to Partially Observable MDPs (POMDPs). It is well-known that POMDPs can be reduced to special MDPs, called Completely Observable MDPs (COMDPs), whose state spaces are sets of probabilities of the original states. This paper describes conditions on POMDPs under which optimal policies for COMDPs can be found by value iteration. In other words, this paper provides sufficient conditions for solving total-costs POMDPs with infinite state, observation and action sets by dynamic programming. Examples of applications to filtration, identification, and inventory control are provided.",

author = "Feinberg, \{Eugene A.\} and Kasyanov, \{Pavlo O.\} and Zgurovsky, \{Michael Z.\}",

note = "Publisher Copyright: {\textcopyright} 2014 IEEE.; 2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, ADPRL 2014 ; Conference date: 09-12-2014 Through 12-12-2014",

year = "2014",

month = jan,

day = "14",

doi = "10.1109/ADPRL.2014.7010613",

language = "English",

series = "IEEE SSCI 2014 - 2014 IEEE Symposium Series on Computational Intelligence - ADPRL 2014: 2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

booktitle = "IEEE SSCI 2014 - 2014 IEEE Symposium Series on Computational Intelligence - ADPRL 2014",

}

Feinberg, EA, Kasyanov, PO & Zgurovsky, MZ 2014, Convergence of value iterations for total-cost MDPs and POMDPs with general state and action sets. in IEEE SSCI 2014 - 2014 IEEE Symposium Series on Computational Intelligence - ADPRL 2014: 2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, Proceedings., 7010613, IEEE SSCI 2014 - 2014 IEEE Symposium Series on Computational Intelligence - ADPRL 2014: 2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, Proceedings, Institute of Electrical and Electronics Engineers Inc., 2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, ADPRL 2014, Orlando, United States, 12/9/14. https://doi.org/10.1109/ADPRL.2014.7010613

Convergence of value iterations for total-cost MDPs and POMDPs with general state and action sets. / Feinberg, Eugene A.; Kasyanov, Pavlo O.; Zgurovsky, Michael Z.
IEEE SSCI 2014 - 2014 IEEE Symposium Series on Computational Intelligence - ADPRL 2014: 2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, Proceedings. Institute of Electrical and Electronics Engineers Inc., 2014. 7010613 (IEEE SSCI 2014 - 2014 IEEE Symposium Series on Computational Intelligence - ADPRL 2014: 2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, Proceedings).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Convergence of value iterations for total-cost MDPs and POMDPs with general state and action sets

AU - Feinberg, Eugene A.

AU - Kasyanov, Pavlo O.

AU - Zgurovsky, Michael Z.

PY - 2014/1/14

Y1 - 2014/1/14

N2 - This paper describes conditions for convergence to optimal values of the dynamic programming algorithm applied to total-cost Markov Decision Processes (MDPSs) with Borel state and action sets and with possibly unbounded one-step cost functions. It also studies applications of these results to Partially Observable MDPs (POMDPs). It is well-known that POMDPs can be reduced to special MDPs, called Completely Observable MDPs (COMDPs), whose state spaces are sets of probabilities of the original states. This paper describes conditions on POMDPs under which optimal policies for COMDPs can be found by value iteration. In other words, this paper provides sufficient conditions for solving total-costs POMDPs with infinite state, observation and action sets by dynamic programming. Examples of applications to filtration, identification, and inventory control are provided.

AB - This paper describes conditions for convergence to optimal values of the dynamic programming algorithm applied to total-cost Markov Decision Processes (MDPSs) with Borel state and action sets and with possibly unbounded one-step cost functions. It also studies applications of these results to Partially Observable MDPs (POMDPs). It is well-known that POMDPs can be reduced to special MDPs, called Completely Observable MDPs (COMDPs), whose state spaces are sets of probabilities of the original states. This paper describes conditions on POMDPs under which optimal policies for COMDPs can be found by value iteration. In other words, this paper provides sufficient conditions for solving total-costs POMDPs with infinite state, observation and action sets by dynamic programming. Examples of applications to filtration, identification, and inventory control are provided.

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

U2 - 10.1109/ADPRL.2014.7010613

DO - 10.1109/ADPRL.2014.7010613

M3 - Conference contribution

AN - SCOPUS:84946686373

T3 - IEEE SSCI 2014 - 2014 IEEE Symposium Series on Computational Intelligence - ADPRL 2014: 2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, Proceedings

BT - IEEE SSCI 2014 - 2014 IEEE Symposium Series on Computational Intelligence - ADPRL 2014

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, ADPRL 2014

Y2 - 9 December 2014 through 12 December 2014

ER -

Feinberg EA, Kasyanov PO, Zgurovsky MZ. Convergence of value iterations for total-cost MDPs and POMDPs with general state and action sets. In IEEE SSCI 2014 - 2014 IEEE Symposium Series on Computational Intelligence - ADPRL 2014: 2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, Proceedings. Institute of Electrical and Electronics Engineers Inc. 2014. 7010613. (IEEE SSCI 2014 - 2014 IEEE Symposium Series on Computational Intelligence - ADPRL 2014: 2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, Proceedings). doi: 10.1109/ADPRL.2014.7010613

Convergence of value iterations for total-cost MDPs and POMDPs with general state and action sets

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this