article

Partially Observed Markov Decision Process Multiarmed Bandits---Structural Results

Authors:

Vikram Krishnamurthy,

Bo WahlbergAuthors Info & Claims

Mathematics of Operations Research, Volume 34, Issue 2

Pages 287 - 302

https://doi.org/10.1287/moor.1080.0371

Published: 01 May 2009 Publication History

Abstract

This paper considers multiarmed bandit problems involving partially observed Markov decision processes (POMDPs). We show how the Gittins index for the optimal scheduling policy can be computed by a value iteration algorithm on each process, thereby considerably simplifying the computational cost. A suboptimal value iteration algorithm based on Lovejoy's approximation is presented. We then show that for the case of totally positive of order 2 (TP2) transition probability matrices and monotone likelihood ratio (MLR) ordered observation probabilities, the Gittins index is MLR increasing in the information state. Algorithms that exploit this structure are then presented.

References

[1]

Bertsimas, D. and Nino-Mora, J., "Conservation laws, extended polymatroids and multiarmed bandit problems; a polyhedral approach to indexable systems," Math. Oper. Res., v21, pp. 257-305, 1996.

Digital Library

[2]

Cassandra, A. R., "Tony's POMDP page,"

[3]

Cassandra, A. R., "Exact and approximate algorithms for partially observed Markov decision process," 1998.

[4]

Cassandra, A. R., Littman, M. L. and Zhang, N. L., "Incremental pruning: A simple fast exact method for partially observed Markov decision processes," Proc. 13th Annual Conf. Uncertainty in Artificial Intelligence (UAI-97), Morgan Kaufmann, San Francisco, 1997.

Digital Library

[5]

Gittins, J. C., Multi-Armed Bandit Allocation Indices, John Wiley and Sons, New York, 1989.

[6]

Kijima, M., Markov Processes for Stochastic Modelling, Chapman and Hall, London, 1997.

[7]

Krishnamurthy, V. and Djonin, D., "Structured threshold policies for dynamic sensor scheduling---A partially observed Markov decision process approach," IEEE Trans. Signal Processing, v55, pp. 4938-4957, 2007.

Digital Library

[8]

Krishnamurthy, V., Vázquez-Abad, F. J. and Martin, K., "Implementation of gradient estimation to a constrained Markov decision problem," 42nd IEEE Conf. Decision and Control, IEEE Press, Piscataway, NJ, 2003.

[9]

Kumar, P. R. and Varaiya, P., Stochastic Systems---Estimation, Identification and Adaptive Control, Prentice-Hall, Upper Saddle River, NJ, 1986.

Digital Library

[10]

Kushner, H. J. and Yin, G., "Stochastic approximation algorithms for parallel and distributed processing," Stochastics, v22, pp. 219-250, 1987.

[11]

Le Cadre, J. P. and Trémois, O., "Bearings-only tracking for maneuvering sources," IEEE Trans. Aerospace Electronic Systems, v34, pp. 179-193, 1998.

[12]

Lovejoy, W. S., "Some monotonicity results for partially observed Markov decision processes," Oper. Res., v35, pp. 736-743, 1987.

Digital Library

[13]

Lovejoy, W. S., "Computationally feasible bounds for partially observed Markov decision processes," Oper. Res., v39, pp. 162-175, 1991.

Digital Library

[14]

Muller, A. and Stoyan, D., Comparison Methods for Stochastic Models and Risk, John Wiley & Sons, Chichester, UK, 2002.

[15]

Papadimitriou, C. H., Computational Complexity, Addison-Wesley, Reading, MA, 1995.

[16]

Rabiner, L. R., "A tutorial on hidden Markov models and selected applications in speech recognition," Proc. IEEE, v77, pp. 257-285, 1989.

[17]

Ross, S., Introduction to Stochastic Dynamic Programming, Academic Press, San Diego, 1983.

Digital Library

[18]

Smallwood, R. D. and Sondik, E. J., "Optimal control of partially observable Markov processes over a finite horizon," Oper. Res., v21, pp. 1071-1088, 1973.

Digital Library

[19]

Spall, J., Introduction to Stochastic Search and Optimization, John Wiley and Sons, New York, 2003.

Digital Library

[20]

Whittle, P., "Multi-armed bandits and the Gittins index," J. R. Statist. Soc. B, v42, pp. 143-149, 1980.

Cited By

Shi LWang JWu TKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Statistical inference on multi-armed bandits with delayed feedbackProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3619705(31328-31352)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3619705
Liberali GFerecatu A(2022)Morphing for Consumer DynamicsMarketing Science10.1287/mksc.2021.134641:4(769-794)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1287/mksc.2021.1346
Bistritz ILeshem A(2021)Game of ThronesMathematics of Operations Research10.1287/moor.2020.105146:1(159-178)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.1287/moor.2020.1051
Show More Cited By

Partially Observed Markov Decision Process Multiarmed Bandits---Structural Results
1. Mathematics of computing
  1. Probability and statistics
    1. Probabilistic representations

Recommendations

Solution Procedures for Partially Observed Markov Decision Processes

We present three algorithms to solve the infinite horizon, expected discounted total reward partially observed Markov decision process POMDP. Each algorithm integrates a successive approximations algorithm for the POMDP due to A. Smallwood and E. Sondik ...
Risk-Sensitive and Risk-Neutral Multiarmed Bandits

For the multiarmed bandit, the classic result is probabilistic: each state of each bandit (Markov chain with rewards) has an index that is determined by an optimal stopping time for that state's bandit, and expected discounted income is maximized by ...
Robust partially observable Markov decision process
ICML'15: Proceedings of the 32nd International Conference on International Conference on Machine Learning - Volume 37

We seek to find the robust policy that maximizes the expected cumulative reward for the worst case when a partially observable Markov decision process (POMDP) has uncertain parameters whose values are only known to be in a given region. We prove that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Mathematics of Operations Research

Mathematics of Operations Research Volume 34, Issue 2

May 2009

256 pages

ISSN:0364-765X

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 May 2009

Received: 24 July 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Shi LWang JWu TKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Statistical inference on multi-armed bandits with delayed feedbackProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3619705(31328-31352)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3619705
Liberali GFerecatu A(2022)Morphing for Consumer DynamicsMarketing Science10.1287/mksc.2021.134641:4(769-794)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1287/mksc.2021.1346
Bistritz ILeshem A(2021)Game of ThronesMathematics of Operations Research10.1287/moor.2020.105146:1(159-178)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.1287/moor.2020.1051
Yemini MLeshem ASomekh-Baruch A(2020)Restless Hidden Markov Bandit with Linear Rewards2020 59th IEEE Conference on Decision and Control (CDC)10.1109/CDC42340.2020.9304511(1183-1189)Online publication date: 14-Dec-2020
https://dl.acm.org/doi/10.1109/CDC42340.2020.9304511
Schwartz EBradlow EFader P(2017)Customer Acquisition via Display Advertising Using Multi-Armed Bandit ExperimentsMarketing Science10.1287/mksc.2016.102336:4(500-522)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1287/mksc.2016.1023
Xu MLiu GGuan J(2015)Towards a secure medium access control protocol for cluster-based underwater wireless sensor networksInternational Journal of Distributed Sensor Networks10.1155/2015/3254742015(40-40)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1155/2015/325474
Yu FTang H(2010)Distributed node selection for threshold key management with intrusion detection in mobile ad hoc networksWireless Networks10.1007/s11276-010-0250-616:8(2169-2178)Online publication date: 1-Nov-2010
https://dl.acm.org/doi/10.1007/s11276-010-0250-6

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents