On Linear Programming in a Markov Decision Problem

Eric V. Denardo
Eric V. Denardo
Yale University
Search for more papers by this author

Yale University

Published Online:1 Jan 1970https://doi.org/10.1287/mnsc.16.5.281

Abstract

This paper treats a Markov decision problem with an infinite planning horizon and no discounting. This model is analyzed by application, perhaps repeated, of a simple linear program.

Cited by
- Flexible Risk Aware Sequential Decision Making
  12 November 2024
- Approximated Dynamic Programming for Production and Inventory Planning Problem in Cold Rolling Process of Steel Production
  13 December 2024 | Mathematics, Vol. 12, No. 24
- Maintenance optimization in a digital twin for Industry 4.0
  29 November 2022 | Annals of Operations Research, Vol. 340, No. 1
- Self-Improving Online Storage Control for Stable Wind Power Commitment
  IEEE Transactions on Smart Grid, Vol. 15, No. 4
- MF-OMO: An Optimization Formulation of Mean-Field Games
  22 January 2024 | SIAM Journal on Control and Optimization, Vol. 62, No. 1
- Markov Decision Processes and Stochastic Control Problems on Networks
  13 January 2024
- LP based upper and lower bounds for Cesàro and Abel limits of the optimal values in problems of control of stochastic discrete time systems
  Journal of Mathematical Analysis and Applications, Vol. 512, No. 1
- On Linear Programming for Constrained and Unconstrained Average-Cost Markov Decision Processes with Countable Action Spaces and Strictly Unbounded Costs
  Huizhen Yu
  15 December 2021 | Mathematics of Operations Research, Vol. 47, No. 2
- A Self-Play and Sentiment-Emphasized Comment Integration Framework Based on Deep Q-Learning in a Crowdsourcing Scenario
  IEEE Transactions on Knowledge and Data Engineering, Vol. 34, No. 3
- Continuous-Action Reinforcement Learning for Portfolio Allocation of a Life Insurance Company
  10 September 2021
- The Stochastic Shortest Path Problem: A polyhedral combinatorics perspective
  European Journal of Operational Research, Vol. 285, No. 1
- On the Minimum Pair Approach for Average Cost Markov Decision Processes with Countable Discrete Action Spaces and Strictly Unbounded Costs
  10 March 2020 | SIAM Journal on Control and Optimization, Vol. 58, No. 2
- Metodología de programación dinámica aproximada para control óptimo basada en datos
  12 June 2019 | Revista Iberoamericana de Automática e Informática industrial, Vol. 16, No. 3
- Polynomial-Time Computation of Strong and n-Present-Value Optimal Policies in Markov Decision Chains
  Michael O’Sullivan,
  Arthur F. Veinott
  14 December 2016 | Mathematics of Operations Research, Vol. 42, No. 3
- OPTIMAL SWITCHING ON AND OFF THE ENTIRE SERVICE CAPACITY OF A PARALLEL QUEUE
  9 October 2015 | Probability in the Engineering and Informational Sciences, Vol. 29, No. 4
- Optimal offloading control for a mobile device based on a realistic battery model and semi-Markov decision process
- Maximum-Stopping-Value Policies in Finite Markov Population Decision Chains
  B. Curtis Eaves,
  Arthur F. Veinott
  24 January 2014 | Mathematics of Operations Research, Vol. 39, No. 3
- Optimizing cloud utilization via switching decisions
  17 April 2014 | ACM SIGMETRICS Performance Evaluation Review, Vol. 41, No. 4
- Lower Bounding Linear Program for the Perimeter Patrol Optimization Problem
  Journal of Guidance, Control, and Dynamics, Vol. 37, No. 2
- A semi-Markovian decision process based control method for offloading tasks from mobile devices to the cloud
- Derman’s book as inspiration: some results on LP for MDPs
  4 January 2012 | Annals of Operations Research, Vol. 208, No. 1
- Approximate Dynamic Programming Applied to UAV Perimeter Patrol
- State partitioning based linear program for stochastic dynamic programs: An invariance property
  Operations Research Letters, Vol. 40, No. 6
- References
  23 August 2012
- A Lower Bounding Linear Programming approach to the Perimeter Patrol Stochastic Control Problem
  6 September 2012
- Bounding procedure for stochastic dynamic programs with application to the perimeter patrol problem
- Optimization of ARQ Protocols in Interference Networks with QoS Constraints
- Dynamic Programming Via Linear Programming
  15 February 2011
- Bibliography
  15 August 2011
- Computational approaches to variance-penalized Markov decision processes
  Journal of Statistics and Management Systems, Vol. 8, No. 2
- The Linear Programming Approach to Approximate Dynamic Programming
  D. P. de Farias,
  B. Van Roy,
  1 December 2003 | Operations Research, Vol. 51, No. 6
- Achieving Target State-Action Frequencies in Multichain Average-Reward Markov Decision Processes
  Dmitry Krass,
  O. J. Vrieze,
  1 August 2002 | Mathematics of Operations Research, Vol. 27, No. 3
- The Linear Programming Approach
- Stochastic modeling of a power-managed system-construction and optimization
  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 20, No. 10
- Numerical Comparison of Controls and Verification of Optimality for Stochastic Control Problems
  Journal of Optimization Theory and Applications, Vol. 106, No. 1
- Approximation of Infinite-Dimensional Linear Programming Problems which Arise in Stochastic Control
  SIAM Journal on Control and Optimization, Vol. 36, No. 4
- Existence of Markov Controls and Characterization of Optimal Markov Controls
  SIAM Journal on Control and Optimization, Vol. 36, No. 2
- Управляемые случайные последовательности: методы выпуклого анализа и задачи с функциональными ограничениями
  Успехи математических наук, Vol. 53, No. 6
- Average Optimality in Markov Control Processes via Discounted-Cost Problems and Linear Programming
  SIAM Journal on Control and Optimization, Vol. 34, No. 1
- Computational aspects in applied stochastic control
  Computational Economics, Vol. 7, No. 2
- Bibliography
  27 May 2008
- Weak conditions for average optimality in Markov control processes
  Systems & Control Letters, Vol. 22, No. 4
- Survey of linear programming for standard and nonstandard Markovian control problems. Part I: Theory
  ZOR - Methods and Models of Operations Research, Vol. 40, No. 1
- Linear programming formulation of MDPs in countable state space: The multichain case
  ZOR - Methods and Models of Operations Research, Vol. 40, No. 1
- Mean-variance criteria in an undiscounted Markov decision process
  European Journal of Operational Research, Vol. 69, No. 2
- Optimization of file migration policies in distributed computer systems
  Computers & Operations Research, Vol. 19, No. 5
- An infinite-dimensional LP solution to control of a continuous, monotone process
- Remarks on maximal meanstandard devition ratio in undiscounted mdps
  28 November 2010 | Optimization, Vol. 26, No. 3-4
- Average optimal stationary policies and linear programming in countable space Markov decision processes
- A note on maximal mean/standard deviation ratio in an undiscounted MDP
  Operations Research Letters, Vol. 8, No. 4
- Communicating MDPs: Equivalence and LP properties
  Operations Research Letters, Vol. 7, No. 6
- Gain/variability tradeoffs in undiscounted Markov decision processes
- MARKOV DECISION PROCESSES
  29 April 2008 | Statistica Neerlandica, Vol. 39, No. 2
- Linear programming with multiple choice constraints for single chain undiscounted Markov decision problems
  Operations Research Letters, Vol. 3, No. 6
- Approximating general Markovian decision-problems by clustering their state- and action-spaces
  27 June 2007 | Mathematische Operationsforschung und Statistik. Series Optimization, Vol. 15, No. 1
- On the block upper-triangularity of undiscounted multi-chain markov decision problems
  Operations Research Letters, Vol. 2, No. 3
- A survey of algorithms for some restricted classes of Markov decision problems
- Optimal harvesting strategies for stochastic single-species, multiage class models
  Mathematical Biosciences, Vol. 41, No. 3-4
- Optimal choice of reward levels in an organization
  Theory and Decision, Vol. 9, No. 2
- Generalized Markovian decision processes
  Zeitschrift für Operations Research, Vol. 21, No. 5
- Linear Programming Algorithms for the Deterministic Discrete Dynamic Programming Problem
- A new optimality criterion for discrete dynamic programming
  Journal of Mathematical Analysis and Applications, Vol. 37, No. 1

Volume 16, Issue 5

January 1970

Pages 281-411

Article Information

Metrics

Information

Published Online:January 01, 1970

Cite as

Eric V. Denardo, (1970) On Linear Programming in a Markov Decision Problem. Management Science 16(5):281-288.

https://doi.org/10.1287/mnsc.16.5.281

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

On Linear Programming in a Markov Decision Problem

Abstract

Volume 16, Issue 5

Article Information

Metrics

Information

Cite as

Sign Up for INFORMS Publications Updates and News