Partially Observed Markov Decision Process Multiarmed Bandits—Structural Results
Mathematics of Operations ResearchPublished 11 April 2009
Vikram Krishnamurthy, Bo Wahlberg
Citations42
SJR quartileQ1
SJR score1.35
SNIP1.90
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown 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.
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.
Keywords
Computer ScienceDecision Sciences
Proceedings of the IEEEA tutorial on hidden Markov models and selected applications in speech recognition
22,785 Citations1989L. R. Rabiner
Computational Complexity
2,263 Citations1995Peter Brucker
Introduction to Stochastic Search and Optimization
1,877 Citations2003James C. Spall
A survey of the range of topics, in a strong, interdisciplinary format that will appeal to both students and researchers.
Comparison Methods for Stochastic Models and Risks
1,512 Citations2002Alfred Müller, Dietrich Stoyan
Operations ResearchThe Optimal Control of Partially Observable Markov Processes over a Finite Horizon
1,499 Citations1973Richard D. Smallwood, Edward J. Sondik
If there are only a finite number of control intervals remaining, then the optimal payoff function is a piecewise-linear, convex function of the current state probabilities of the internal Markov process, and an algorithm for utilizing this property to calculate the optimal control policy and payoff function for any finite horizon is outlined.
Journal of the Royal Statistical Society Series A (Statistics in Society)Multi-Armed Bandit Allocation Indices.
1,056 Citations1990J. A. Bather, John Gittins
3. Multi‐armed Bandit Allocation Indices: A meta-analyses of bandit allocation indices for the period April 1, 1991 to June 30, 1991, as well as a review of the periodical indices published in 1989, show clear trends in allocations between April and June.
Journal of the Royal Statistical Society Series B (Statistical Methodology)Multi-Armed Bandits and the Gittins Index
530 Citations1980Peter Whittle
Markov Processes for Stochastic Modeling
484 Citations1997Masaaki Kijima
Markov processes for stochastic modeling, Markov Processes for Stochastic Modeling, اطلاعات رسانی کشاورزی, £1.5bn in order to model the response of the immune system to shocks in the presence of natural disasters.
Exact and approximate algorithms for partially observable markov decision processes
380 Citations1998Leslie Pack Kaelbling, Anthony R. Cassandra
This work looks at sequential decision making in environments where the actions have probabilistic outcomes and in which the system state is only partially observable and considers a number of approaches for deriving policies that yield sub-optimal control and empirically explore their performance on a range of problems.
arXiv (Cornell University)Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes
343 Citations2013Anthony R. Cassandra, Michael L. Littman +1 more
It is found that incremental pruning is presently the most efficient exact method for solving POMDPS.
Operations ResearchComputationally Feasible Bounds for Partially Observed Markov Decision Processes
310 Citations1991William S. Lovejoy
This paper explains how to approximate the state space by a finite grid of points, and use that grid to construct upper and lower value function bounds, generate approximate nonstationary and stationary policies, and bound the value loss relative to optimal for using these policies in the decision problem.
IEEE Transactions on Signal ProcessingStructured Threshold Policies for Dynamic Sensor Scheduling—A Partially Observed Markov Decision Process Approach
150 Citations2007Vikram Krishnamurthy, D.V. Djonin
This work gives sufficient conditions on the cost function, dynamics of the Markov chain and observation probabilities so that the optimal scheduling policy has a threshold structure with respect to a monotone likelihood ratio (MLR) ordering.
Mathematics of Operations ResearchConservation Laws, Extended Polymatroids and Multiarmed Bandit Problems; A Polyhedral Approach to Indexable Systems
150 Citations1996Dimitris Bertsimas, José Niño‐Mora
Operations ResearchSome Monotonicity Results for Partially Observed Markov Decision Processes
143 Citations1987William S. Lovejoy
There are sufficient conditions for the optimal value in a discrete-time, finite, partially observed Markov decision process to be monotone on the space of state probability vectors ordered by likelihood ratios.
Journal of the Operational Research SocietyMulti-armed Bandit Allocation Indices
124 Citations1989Peter W. Jones
The multi-armed Bandit Allocation Indices were introduced in 1989 as part of a larger effort to understand bandit allocation strategies and their applications in the context of asymmetric warfare.
IEEE Transactions on Aerospace and Electronic SystemsBearings-only tracking for maneuvering sources
72 Citations1998J.-P. Le Cadre, O. Trémois
StochasticsStochastic approximation algorithms for parallel and distributed processing
52 Citations1987Harold J. Kushner, Gang Yin
An interesting class of "distributed" recursive stochastic algorithms that arises when parallel processing methods are used for the Monte Carlo optimization of systems, as well as in applications such as decentralized and asynchronous on-line optimization of the flows in communication networks are treated.
Implementation of gradient estimation to a constrained Markov decision problem
22 Citations2004Vikram Krishnamurthy, Kipp Martin +1 more
This paper identifies the asymptotic bias of the stochastic approximation of the constrained optimization method for the constrained Markov Decision Process, and proposes several means to correct it.