Novel Time Aggregation-Based Algorithms for Markov Decision Processes
- 25 June 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 70 (12) , 8353-8360
Abstract
We present two novel approaches to accelerate the convergence of a class of Markov decision problems (MDPs) with stationary state space components, which iterate on reduced state and action spaces and converge to an optimal policy. The time aggregation based algorithm (TABA) partitions the state space into disjoint sets, one for each possible combination of the non-stationary components, and iterates in the sets. The local search policy set iteration (LSPSI) algorithm introduces a novel modified policy evaluation procedure that seamlessly performs a local search over a very large set of candidate policies, by sampling a reduced subset of actions at each state's value function update. Both approaches, as well as a combination of them, are validated by means of a mining supply chain application with a large number of stationary state components and a large set of feasible actions. The experiments suggest that the proposed frameworks are very efficient for such a class of problems.Keywords
This publication has 32 references indexed in Scilit:
- A unified framework for stochastic optimizationEuropean Journal of Operational Research, 2019
- A multi-cluster time aggregation approach for Markov chainsAutomatica, 2019
- A heuristic approach for the stochastic optimization of mine production schedulesJournal of Heuristics, 2017
- Simultaneous Stochastic Optimization of Mining Complexes and Mineral Value ChainsMathematical Geosciences, 2017
- Solving average cost Markov decision processes by means of a two-phase time aggregation algorithmEuropean Journal of Operational Research, 2015
- Value set iteration for Markov decision processesAutomatica, 2014
- Policy set iteration for Markov decision processesAutomatica, 2013
- Lambda‐Policy Iteration: A Review and a New Implementation2012
- Wiley Series in Probability and Statistics2008
- Q-learningMachine Learning, 1992