Linear Programming and Markov Decision Chains

A. Hordijk
A. Hordijk
University of Leiden, The Netherlands
Search for more papers by this author
,
L. C. M. Kallenberg
L. C. M. Kallenberg
University of Leiden, The Netherlands
Search for more papers by this author

A. Hordijk

University of Leiden, The Netherlands

Search for more papers by this author

L. C. M. Kallenberg

University of Leiden, The Netherlands

Search for more papers by this author

Published Online:1 Apr 1979https://doi.org/10.1287/mnsc.25.4.352

Abstract

In this paper we show that for a finite Markov decision process an average optimal policy can be found by solving only one linear programming problem. Also the relation between the set of feasible solutions of the linear program and the set of stationary policies is analyzed.

Cited by
- A Note on Zero-Sum Two-Person Undiscounted One Player Control Semi-Markov Games
  28 March 2024 | International Game Theory Review, Vol. 26, No. 03
- 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
- Probabilistic Safety Guarantees for Markov Decision Processes
  IEEE Transactions on Automatic Control, Vol. 68, No. 12
- On Completely Mixed Stochastic Games
  22 September 2022 | Operations Research Forum, Vol. 3, No. 4
- Parameterized MDPs and Reinforcement Learning Problems—A Maximum Entropy Principle-Based Framework
  IEEE Transactions on Cybernetics, Vol. 52, No. 9
- 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
- Value iteration for simple stochastic games: Stopping criterion and learning algorithm
  Information and Computation, Vol. 285
- Linear programming estimates for Cesàro and Abel limits of optimal values in optimal control problems
  Discrete & Continuous Dynamical Systems - B, Vol. 27, No. 3
- Numerical Calculation of Optimal Policy Pairs in Zero‐sum Stochastic Games with Varying Discount Factors
  5 May 2022 | Discrete Dynamics in Nature and Society, Vol. 2022, No. 1
- LP Based Bounds for Cesàro and Abel Limits of the Optimal Values in Non-ergodic Stochastic Systems
- The Stochastic Shortest Path Problem: A polyhedral combinatorics perspective
  European Journal of Operational Research, Vol. 285, No. 1
- Computing semi-stationary optimal policies for multichain semi-Markov decision processes
  14 October 2017 | Annals of Operations Research, Vol. 287, No. 2
- Linear Programming Formulation of Long-Run Average Optimal Control Problem
  13 November 2018 | Journal of Optimization Theory and Applications, Vol. 181, No. 1
- LP Formulations of Discrete Time Long-Run Average Optimal Control Problems: The NonErgodic Case
  21 May 2019 | SIAM Journal on Control and Optimization, Vol. 57, No. 3
- Partial and Conditional Expectations in Markov Decision Processes with Integer Weights
  5 April 2019
- Admission control strategies for tandem Markovian loss systems
  13 January 2018 | Queueing Systems, Vol. 90, No. 1-2
- Linear programming formulation for non-stationary, finite-horizon Markov decision process models
  Operations Research Letters, Vol. 45, No. 6
- Fast and Highly Scalable Bayesian MDP on a GPU Platform
  20 August 2017
- 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
- Long-Term Values in Markov Decision Processes and Repeated Games, and a New Distance for Probability Spaces
  Jérôme Renault,
  Xavier Venel
  28 November 2016 | Mathematics of Operations Research, Vol. 42, No. 2
- A Duality Framework for Stochastic Optimal Control of Complex Systems
  IEEE Transactions on Automatic Control, Vol. 61, No. 10
- Singularly perturbed linear programs and Markov decision processes
  Operations Research Letters, Vol. 44, No. 3
- Linear Programming and Zero-Sum Two-Person Undiscounted Semi-Markov Games
  10 January 2016 | Asia-Pacific Journal of Operational Research, Vol. 32, No. 06
- Determining the optimal strategies for discrete control problems on stochastic networks with discounted costs
  Discrete Applied Mathematics, Vol. 182
- Simple computing of the customer lifetime value: A fixed local-optimal policy approach
  9 December 2014 | Journal of Systems Science and Systems Engineering, Vol. 23, No. 4
- Risk-Constrained Markov Decision Processes
  IEEE Transactions on Automatic Control, Vol. 59, No. 9
- 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
- Maximizing the set of recurrent states of an MDP subject to convex constraints
  Automatica, Vol. 50, No. 3
- Lower Bounding Linear Program for the Perimeter Patrol Optimization Problem
  Journal of Guidance, Control, and Dynamics, Vol. 37, No. 2
- 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
- Bounding procedure for stochastic dynamic programs with application to the perimeter patrol problem
- Approximate dynamic programming with state aggregation applied to UAV perimeter patrol
  26 January 2011 | International Journal of Robust and Nonlinear Control, Vol. 21, No. 12
- Dynamic Programming Via Linear Programming
  15 February 2011
- State aggregation based linear programming approach to approximate dynamic programming
- Risk-constrained Markov decision processes
- Approximate Dynamic Programming with State Aggregation applied to Perimeter Patrol*
  26 June 2012
- Geographic admission control for vehicle area networks
- A Markov Chain Model of Streaming Proxy for Disconnecting Vehicular Networks
- Solving Simple Stochastic Games with Few Random Vertices
  25 May 2009 | Logical Methods in Computer Science, Vol. 5, No. 2
- A structured pattern matrix algorithm for multichain Markov decision processes
  6 February 2007 | Mathematical Methods of Operations Research, Vol. 66, No. 3
- The Linear Programming Approach to Approximate Dynamic Programming
  D. P. de Farias,
  B. Van Roy,
  1 December 2003 | Operations Research, Vol. 51, No. 6
- Saddle-point calculation for constrained finite Markov chains
  Journal of Economic Dynamics and Control, Vol. 27, No. 10
- Finite State and Action MDPS
- Finite-Step Algorithms for Single-Controller and Perfect Information Stochastic Games
- 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
- Computing Stationary Nash Equilibria of Undiscounted Single-Controller Stochastic Games
  T. E. S. Raghavan,
  Zamir Syed,
  1 May 2002 | Mathematics of Operations Research, Vol. 27, No. 2
- Convex Analytic Methods in Markov Decision Processes
- The Linear Programming Approach
- PIVOTING ALGORITHMS FOR SOME CLASSES OF STOCHASTIC GAMES: A SURVEY
  20 November 2011 | International Game Theory Review, Vol. 03, No. 02n03
- Call Admission: A New Approach to Quality of Service
  Queueing Systems, Vol. 38, No. 2
- Optimal traffic counting locations for origin–destination matrix estimation
  Transportation Research Part B: Methodological, Vol. 32, No. 2
- Infinite Linear Programming and Multichain Markov Control Processes in Uncountable Spaces
  SIAM Journal on Control and Optimization, Vol. 36, No. 1
- Управляемые случайные последовательности: методы выпуклого анализа и задачи с функциональными ограничениями
  Успехи математических наук, Vol. 53, No. 6
- The Linear Program approach in multi-chain Markov Decision Processes revisited
  ZOR Zeitschrift f�r Operations Research Methods and Models of Operations Research, Vol. 42, No. 2
- Markov Branching Decision Chains with Interest-Rate-Dependent Rewards
  27 July 2009 | Probability in the Engineering and Informational Sciences, Vol. 9, No. 1
- Bibliography
  27 May 2008
- 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
- A new policy iteration scheme for Markov decision processes using Schweitzer's formula
  14 July 2016 | Journal of Applied Probability, Vol. 31, No. 01
- A new policy iteration scheme for Markov decision processes using Schweitzer's formula
  14 July 2016 | Journal of Applied Probability, Vol. 31, No. 1
- Discrete-Time Controlled Markov Processes with Average Cost Criterion: A Survey
  SIAM Journal on Control and Optimization, Vol. 31, No. 2
- 6 Algorithms and complexity for markov processes
- Separable Markovian decision problems
  1 March 1992 | Operations-Research-Spektrum, Vol. 14, No. 1
- Multiobjective dynamic programming for forest resource management
  Forest Ecology and Management, Vol. 48, No. 1-2
- The Separable Multichain Markov Decision Problem
- A Solution for the Variance-Penalized Markov Decision Problem Based on Parametric Linear Programming
- Nonlinear programming and stationary equilibria in stochastic games
  Mathematical Programming, Vol. 50, No. 1-3
- Chapter 8 Markov decision processes
- Linear programming in tector criterion markov and semi-Markov decision processes
  Optimization, Vol. 20, No. 5
- Communicating MDPs: Equivalence and LP properties
  Operations Research Letters, Vol. 7, No. 6
- A value iteration method for undiscounted multichain Markov decision processes
  Zeitschrift für Operations Research, Vol. 32, No. 2
- Sensitive Growth Analysis of Controlled Multiplicative Systems
- Variational characterizations in Markov decision processes
  Journal of Mathematical Analysis and Applications, Vol. 117, No. 2
- Nonlinear programming and stationary strategies in stochastic games
  Mathematical Programming, Vol. 34, No. 2
- Quadratic programming and the single-controller stochastic game
  Journal of Mathematical Analysis and Applications, Vol. 113, No. 1
- Gain/variability tradeoffs in undiscounted Markov decision processes
- Generalized polynomial approximations in Markovian decision processes
  Journal of Mathematical Analysis and Applications, Vol. 110, No. 2
- MARKOV DECISION PROCESSES
  29 April 2008 | Statistica Neerlandica, Vol. 39, No. 2
- The completely mixed single-controller stochastic game
  1 January 1985 | Proceedings of the American Mathematical Society, Vol. 95, No. 4
- A value-iteration scheme for undiscounted multichain Markov renewal programs
  Zeitschrift für Operations Research, Vol. 28, No. 5
- On stationary equilibria of a single-controller stochastic game
  Mathematical Programming, Vol. 30, No. 3
- Transient policies in discrete dynamic programming: Linear programming including suboptimality tests and additional constraints
  Mathematical Programming, Vol. 30, No. 1
- On the block upper-triangularity of undiscounted multi-chain markov decision problems
  Operations Research Letters, Vol. 2, No. 3
- Percentiles and markovian decision processes
  Operations Research Letters, Vol. 2, No. 1
- Linear Programming to Compute a Bias-Optimal Policy
- Linear programming and undiscounted stochastic games in which one player controls transitions
  1 March 1981 | Operations-Research-Spektrum, Vol. 3, No. 1
- Linear Programming Methods for Solving Finite Markovian Decision Problems
- Average optimal stationary policies and linear programming in countable space Markov decision processes
- A graph formulation of some supervisory control problems
- Strict-sense constrained Markov decision processes
- Safety control of partially observed MDPs with applications to machine maintenance problems

Volume 25, Issue 4

April 1979

Pages 301-410

Article Information

Metrics

Information

Published Online:April 01, 1979

Cite as

A. Hordijk, L. C. M. Kallenberg, (1979) Linear Programming and Markov Decision Chains. Management Science 25(4):352-362.

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

Keywords

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Linear Programming and Markov Decision Chains

Abstract

Volume 25, Issue 4

Article Information

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News