Space-progressive value iteration: An anytime algorithm for a class of POMDPs

Nevin L. Zhang; Weihong Zhang

doi:10.1007/3-540-44652-4_8

Space-progressive value iteration: An anytime algorithm for a class of POMDPs

Nevin L. Zhang, Weihong Zhang

Department of Computer Science and Engineering

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

1 Citation (Scopus)

Abstract

Finding optimal policies for general partially observable Markov decision processes (POMDPs) is computationally difficult primarily due to the need to perform dynamic-programming (DP) updates over the entire belief space. In this paper,wefirst study a somewhat restrictive class of specialPOMDPscalled almostdiscernible POMDPs and propose an anytime algorithm called space-progressive value iteration(SPVI). SPVI does not perform DP updates over the entire belief space. Rather it restricts DP updates to a belief subspace that grows over time. It is argued that given sufficient time SPVI can find near-optimal policies for almostdiscernible POMDPs.We then show how SPVI can be applied to more a general class of POMDPs. Empirical results are presented to show the effectiveness of SPVI.

Original language	English
Title of host publication	Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 6th European Conference, ECSQARU 2001, Proceedings
Editors	Salem Benferhat, Philippe Besnard
Publisher	Springer Verlag
Pages	72-83
Number of pages	12
ISBN (Electronic)	3540424644, 9783540424642
DOIs	https://doi.org/10.1007/3-540-44652-4_8
Publication status	Published - 2001
Event	6th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU 2001 - Toulouse, France Duration: 19 Sept 2001 → 21 Sept 2001

Publication series

Name	Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)
Volume	2143
ISSN (Print)	0302-9743

Conference

Conference	6th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU 2001
Country/Territory	France
City	Toulouse
Period	19/09/01 → 21/09/01

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2001.

Access to Document

10.1007/3-540-44652-4_8

Cite this

Zhang, N. L., & Zhang, W. (2001). Space-progressive value iteration: An anytime algorithm for a class of POMDPs. In S. Benferhat, & P. Besnard (Eds.), Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 6th European Conference, ECSQARU 2001, Proceedings (pp. 72-83). (Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science); Vol. 2143). Springer Verlag. https://doi.org/10.1007/3-540-44652-4_8

Zhang, Nevin L. ; Zhang, Weihong. / Space-progressive value iteration : An anytime algorithm for a class of POMDPs. Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 6th European Conference, ECSQARU 2001, Proceedings. editor / Salem Benferhat ; Philippe Besnard. Springer Verlag, 2001. pp. 72-83 (Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)).

@inproceedings{32a8b58586fa494cb708675a31463880,

title = "Space-progressive value iteration: An anytime algorithm for a class of POMDPs",

abstract = "Finding optimal policies for general partially observable Markov decision processes (POMDPs) is computationally difficult primarily due to the need to perform dynamic-programming (DP) updates over the entire belief space. In this paper,wefirst study a somewhat restrictive class of specialPOMDPscalled almostdiscernible POMDPs and propose an anytime algorithm called space-progressive value iteration(SPVI). SPVI does not perform DP updates over the entire belief space. Rather it restricts DP updates to a belief subspace that grows over time. It is argued that given sufficient time SPVI can find near-optimal policies for almostdiscernible POMDPs.We then show how SPVI can be applied to more a general class of POMDPs. Empirical results are presented to show the effectiveness of SPVI.",

author = "Zhang, \{Nevin L.\} and Weihong Zhang",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001.; 6th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU 2001 ; Conference date: 19-09-2001 Through 21-09-2001",

year = "2001",

doi = "10.1007/3-540-44652-4\_8",

language = "English",

series = "Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)",

publisher = "Springer Verlag",

pages = "72--83",

editor = "Salem Benferhat and Philippe Besnard",

booktitle = "Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 6th European Conference, ECSQARU 2001, Proceedings",

}

Zhang, NL & Zhang, W 2001, Space-progressive value iteration: An anytime algorithm for a class of POMDPs. in S Benferhat & P Besnard (eds), Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 6th European Conference, ECSQARU 2001, Proceedings. Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science), vol. 2143, Springer Verlag, pp. 72-83, 6th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU 2001, Toulouse, France, 19/09/01. https://doi.org/10.1007/3-540-44652-4_8

Space-progressive value iteration: An anytime algorithm for a class of POMDPs. / Zhang, Nevin L.; Zhang, Weihong.
Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 6th European Conference, ECSQARU 2001, Proceedings. ed. / Salem Benferhat; Philippe Besnard. Springer Verlag, 2001. p. 72-83 (Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science); Vol. 2143).

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

TY - GEN

T1 - Space-progressive value iteration

T2 - 6th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU 2001

AU - Zhang, Nevin L.

AU - Zhang, Weihong

PY - 2001

Y1 - 2001

N2 - Finding optimal policies for general partially observable Markov decision processes (POMDPs) is computationally difficult primarily due to the need to perform dynamic-programming (DP) updates over the entire belief space. In this paper,wefirst study a somewhat restrictive class of specialPOMDPscalled almostdiscernible POMDPs and propose an anytime algorithm called space-progressive value iteration(SPVI). SPVI does not perform DP updates over the entire belief space. Rather it restricts DP updates to a belief subspace that grows over time. It is argued that given sufficient time SPVI can find near-optimal policies for almostdiscernible POMDPs.We then show how SPVI can be applied to more a general class of POMDPs. Empirical results are presented to show the effectiveness of SPVI.

AB - Finding optimal policies for general partially observable Markov decision processes (POMDPs) is computationally difficult primarily due to the need to perform dynamic-programming (DP) updates over the entire belief space. In this paper,wefirst study a somewhat restrictive class of specialPOMDPscalled almostdiscernible POMDPs and propose an anytime algorithm called space-progressive value iteration(SPVI). SPVI does not perform DP updates over the entire belief space. Rather it restricts DP updates to a belief subspace that grows over time. It is argued that given sufficient time SPVI can find near-optimal policies for almostdiscernible POMDPs.We then show how SPVI can be applied to more a general class of POMDPs. Empirical results are presented to show the effectiveness of SPVI.

UR - https://openalex.org/W1528846058

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

U2 - 10.1007/3-540-44652-4_8

DO - 10.1007/3-540-44652-4_8

M3 - Conference Paper published in a book

T3 - Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)

SP - 72

EP - 83

BT - Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 6th European Conference, ECSQARU 2001, Proceedings

A2 - Benferhat, Salem

A2 - Besnard, Philippe

PB - Springer Verlag

Y2 - 19 September 2001 through 21 September 2001

ER -

Zhang NL, Zhang W. Space-progressive value iteration: An anytime algorithm for a class of POMDPs. In Benferhat S, Besnard P, editors, Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 6th European Conference, ECSQARU 2001, Proceedings. Springer Verlag. 2001. p. 72-83. (Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)). doi: 10.1007/3-540-44652-4_8

Space-progressive value iteration: An anytime algorithm for a class of POMDPs

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this