On Finding the Maximal Gain for Markov Decision Processes

Amedeo R. Odoni
Amedeo R. Odoni
Massachusetts Institute of Technology, Cambridge, Massachusetts
Search for more papers by this author

Massachusetts Institute of Technology, Cambridge, Massachusetts

Published Online:1 Oct 1969https://doi.org/10.1287/opre.17.5.857

Abstract

The method of successive approximations for solving problems on single-chain Markovian decision processes has been investigated by White and Schweitzer. This paper shows that White's scheme not only converges, but also can be modified so that monotonic upper and lower bounds on the maximal gain can be obtained.

Cited by
- Dynamic Programming: Average Cost Per Stage Problems
  29 March 2024
- Turnpikes in Finite Markov Decision Processes and Random Walk
  4 May 2023 | Theory of Probability & Its Applications, Vol. 68, No. 1
- Turnpikes in finite Markov decision processes and random walk
  23 January 2023 | Теория вероятностей и ее применения, Vol. 68, No. 1
- Uniformization: Basics, extensions and applications
  Performance Evaluation, Vol. 118
- One-Step Improvement Ideas and Computational Aspects
  11 March 2017
- Allocation in a Vertical Rotary Car Park
  11 March 2017
- MDP for Query-Based Wireless Sensor Networks
  11 March 2017
- Optimal query assignment for wireless sensor networks
  AEU - International Journal of Electronics and Communications, Vol. 69, No. 8
- Determining Optimal Parameters for Expediting Policies
  Raik Özsen,
  Ulrich W. Thonemann
  11 December 2014 | Manufacturing & Service Operations Management, Vol. 17, No. 1
- Weighted difference approximation of value functions for slow-discounting Markov Decision Processes
- Reversible Markov Decision Processes with an Average-Reward Criterion
  SIAM Journal on Control and Optimization, Vol. 51, No. 1
- A multi-period TSP with stochastic regular and urgent demands
  European Journal of Operational Research, Vol. 185, No. 1
- Dynamic Programming: Average Cost Per Stage Problems
- Stochastic Growth Models With No Discounting
  Acta Oeconomica Pragensia, Vol. 15, No. 4
- Blood platelet production: Optimization by dynamic programming and simulation
  Computers & Operations Research, Vol. 34, No. 3
- On the total reward variance for continuous-time Markov reward chains
  14 July 2016 | Journal of Applied Probability, Vol. 43, No. 04
- On the total reward variance for continuous-time Markov reward chains
  14 July 2016 | Journal of Applied Probability, Vol. 43, No. 4
- Suboptimality Bounds in Stochastic Control: A Queueing Example
- Approximate solutions for a stochastic lot-sizing problem with partial customer-order information
  European Journal of Operational Research, Vol. 150, No. 1
- Finite State and Action MDPS
- Efficient buffer sharing in shared memory ATM systems with space priority traffic
  IEEE Communications Letters, Vol. 6, No. 4
- Dynamic Programming: Average Cost per Stage Problems
- Randomized Communication in Radio Networks
- Bibliography
  27 May 2008
- Make-to-order policies for a stochastic lot-sizing problem using overtime
  International Journal of Production Economics, Vol. 56-57
- A New Value Iteration method for the Average Cost Dynamic Programming Problem
  SIAM Journal on Control and Optimization, Vol. 36, No. 2
- Production strategies for a stochastic lot-sizing problem with constant capacity
  European Journal of Operational Research, Vol. 92, No. 2
- An experimental analysis of steady state convergence in simple queueing systems: Implications for flexible manufacturing system models
  Simulation Practice and Theory, Vol. 4, No. 1
- Heuristic procedures for a stochastic lot-sizing problem in make-to-order manufacturing
  Annals of Operations Research, Vol. 59, No. 1
- Mapping discounted and undiscounted Markov Decision Problems onto Hopfield neural networks
  8 June 2005
- Bibliography
  27 May 2008
- 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
- Heuristic Procedures for the Stochastic Lot-Sizing Problem
- Collision resolution algorithms for a time-constrained multiaccess channel
  IEEE Transactions on Communications, Vol. 41, No. 7
- An Error-Bound Theorem for Approximate Markov Chains
  27 July 2009 | Probability in the Engineering and Informational Sciences, Vol. 6, No. 3
- Computationally efficient algorithms for on-line optimization of markov decision processes
  Automatica, Vol. 28, No. 1
- On the Optimality of Trunk Reservation in Overflow Processes
  27 July 2009 | Probability in the Engineering and Informational Sciences, Vol. 5, No. 3
- Stochastic dynamic programming for reservoir optimal control: Dense discretization and inflow correlation assumption made possible by parallel computing
  8 January 2008 | Water Resources Research, Vol. 27, No. 5
- Chapter 8 Markov decision processes
- Some Optimal Algorithms of Random Multiple Access
  Theory of Probability & Its Applications, Vol. 34, No. 3
- Markov decision processes
  European Journal of Operational Research, Vol. 39, No. 1
- A value iteration method for undiscounted multichain Markov decision processes
  Zeitschrift für Operations Research, Vol. 32, No. 2
- A methodology for computation reduction for specially structured large scale Markov decision problems
  European Journal of Operational Research, Vol. 34, No. 1
- Dual bounds on the equilibrium distribution of a finite Markov chain
  Journal of Mathematical Analysis and Applications, Vol. 126, No. 2
- Variational characterizations in Markov decision processes
  Journal of Mathematical Analysis and Applications, Vol. 117, No. 2
- A simple technique in Markovian control with applications to resource allocation in communication networks
  Operations Research Letters, Vol. 5, No. 1
- Some basic concepts of numerical treatment of Markov decision models
  Statistics, Vol. 17, No. 1
- Iterative aggregation for solving undiscounted semi-markovian reward processes
  21 March 2007 | Communications in Statistics. Stochastic Models, Vol. 2, No. 1
- Iterative bounds on the relative value vector in undiscounted Markov renewal programming
  Zeitschrift für Operations Research, Vol. 29, No. 7
- Computing optimal (s, S) policies in inventory models with continuous demands
  1 July 2016 | Advances in Applied Probability, Vol. 17, No. 02
- Computing optimal ( s, S ) policies in inventory models with continuous demands
  1 July 2016 | Advances in Applied Probability, Vol. 17, No. 2
- MARKOV DECISION PROCESSES
  29 April 2008 | Statistica Neerlandica, Vol. 39, No. 2
- On the throughput of degenerate intersection and first-come first-served collision resolution algorithms
  IEEE Transactions on Information Theory, Vol. 31, No. 2
- On the Capacity of Sticky Storage Devices
  29 July 2013 | AT&T Bell Laboratories Technical Journal, Vol. 63, No. 7
- Optimal replacement policy for a redundant system
  OR Spektrum, Vol. 6, No. 1
- Optimal Operation of Multipurpose Pool of Elk City Lake
  Journal of Water Resources Planning and Management, Vol. 110, No. 1
- An error bound concerning Howard's Value Determination Equation
  Zeitschrift für Operations Research, Vol. 26, No. 1
- Nonstationary Markov decision problems with converging parameters
  Journal of Optimization Theory and Applications, Vol. 34, No. 2
- Optimal assignments in a markovian queueing system
  Computers & Operations Research, Vol. 8, No. 1
- The method of value oriented successive approximations for the average reward Markov decision process
  1 December 1980 | Operations-Research-Spektrum, Vol. 1, No. 4
- Computation techniques for large scale undiscounted markov decision processes
  29 October 2013 | Naval Research Logistics Quarterly, Vol. 26, No. 4
- Stochastic optimization of a water supply system
  9 July 2010 | Water Resources Research, Vol. 15, No. 4
- Markov programming with policy constraints
  European Journal of Operational Research, Vol. 3, No. 3
- Geometric convergence of value-iteration in multichain Markov decision problems
  1 July 2016 | Advances in Applied Probability, Vol. 11, No. 01
- Geometric convergence of value-iteration in multichain Markov decision problems
  1 July 2016 | Advances in Applied Probability, Vol. 11, No. 1
- Contraction mappings underlying undiscounted Markov decision problems
  Journal of Mathematical Analysis and Applications, Vol. 65, No. 3
- A dynamic programming algorithm in stochastic systems
  USSR Computational Mathematics and Mathematical Physics, Vol. 18, No. 6
- DISCOUNTED AND UNDISCOUNTED VALUE-ITERATION IN MARKOV DECISION PROBLEMS: A SURVEY
- ELIMINATION OF NON-OPTIMAL ACTIONS IN MARKOV DECISION PROCESSES
- A successive approximation algorithm for an undiscounted Markov decision process
  Computing, Vol. 17, No. 2
- References
- A Survey of the Stete of the Art in Dynamic Programming
  16 July 2007 | A I I E Transactions, Vol. 8, No. 1
- An iterative method for approximating average cost optimal (s,S) inventory policies
  Zeitschrift für Operations Research, Vol. 18, No. 5
- Zur Extrapolation in Markoffschen Entscheidungsmodellen mit Diskontierung
  Zeitschrift für Operations Research, Vol. 18, No. 3
- Decision Horizons in Discrete Time Undiscounted Markov Renewal Programming
  IEEE Transactions on Systems, Man, and Cybernetics, Vol. SMC-4, No. 4
- Determining Near-Optimal Policies for Markov Renewal Decision Processes
  IEEE Transactions on Systems, Man, and Cybernetics, Vol. SMC-4, No. 2
- Modeling the Regulation of Lake Superior Under Uncertainty of Future Water Supplies
  9 July 2010 | Water Resources Research, Vol. 10, No. 1
- Grundlagen
- Iterative solution of the functional equations of undiscounted Markov renewal programming
  Journal of Mathematical Analysis and Applications, Vol. 34, No. 3
- New value iteration and Q-learning methods for the average cost dynamic programming problem
- On-line error bounds for steady-state approximations: A potential solution to the initialization bias problem

Volume 17, Issue 5

September-October 1969

Pages 761-925

Article Information

Metrics

Information

Published Online:October 01, 1969

Cite as

Amedeo R. Odoni, (1969) On Finding the Maximal Gain for Markov Decision Processes. Operations Research 17(5):857-860.

https://doi.org/10.1287/opre.17.5.857

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

On Finding the Maximal Gain for Markov Decision Processes

Abstract

Volume 17, Issue 5

Article Information

Metrics

Information

Cite as

Sign Up for INFORMS Publications Updates and News