Authors: Zhao, Qiu Hong
Brimberg, Jack
Mladenović, Nenad 
Title: A variable neighborhood search based algorithm for finite-horizon Markov Decision Processes
Journal: Applied Mathematics and Computation
Volume: 217
Issue: 7
First page: 3480
Last page: 3492
Issue Date: 1-Dec-2010
Rank: M21
ISSN: 0096-3003
DOI: 10.1016/j.amc.2010.09.018
This paper considers the application of a variable neighborhood search (VNS) algorithm for finite-horizon (H stages) Markov Decision Processes (MDPs), for the purpose of alleviating the "curse of dimensionality" phenomenon in searching for the global optimum. The main idea behind the VNSMDP algorithm is that, based on the result of the stage just considered, the search for the optimal solution (action) of state x in stage t is conducted systematically in variable neighborhood sets of the current action. Thus, the VNSMDP algorithm is capable of searching for the optimum within some subsets of the action space, rather than over the whole action set. Analysis on complexity and convergence attributes of the VNSMDP algorithm are conducted in the paper. It is shown by theoretical and computational analysis that, the VNSMDP algorithm succeeds in searching for the global optimum in an efficient way.
Keywords: Finite horizon | Markov Decision Processes (MDPs) | Metaheuristics | Variable action set | Variable neighborhood search (VNS)
Publisher: Elsevier
Project: National Natural Science Foundation of China, Projects No. 70771001 and No. 70821061
New Century Excellent Talents in University of China, Project No. NCET-07-0049
China Scholarship Council (CSC), Project No. 2005 A 03010

Show full item record


checked on Jun 15, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.