Design of Ordinal Optimization-Based Value Iteration with Computing Budget Allocation
Date Issued
2005
Date
2005
Author(s)
Ho, Yuan-Hsiang
DOI
en-US
Abstract
In many stationary Markov Decision Problems (StMDPs) modeling of real problems: for instance, inventory control problems, computer, and communication networks, both the transition probability and cost function must be generated via computer simulation because of problem complexity and uncertainty. Simulation-Based Policy Iteration (SBPI) is a typical solution in these problems. SBPI includes a sequence of policy evaluation and policy improvement steps. In Policy evaluation step, we evaluate cost-to go value for each state via simulation of multi-stages. It is the most time-consuming step in SBPI algorithm. It means that if we want to decrease CPU time with a good optimal policy accuracy (PA), we have to shorten the CPU time in policy evaluation step Observation of simulation experiment of SBPI is rough estimation accuracy of CTG may lead to good enough policy but much less simulation time. Though the value estimation is rough, policy accuracy improves gradually with iteration process. This motivates our search and idea of improvement approach of algorithm.
In this paper, we first propose Simulation-Based Value Iteration (SBVI) to solve StMDPs. In policy evaluation step compared with SBPI, SBVI evaluates stage-wise cost only to evaluate stage-wise cost and adds estimation of CTG in previous iteration to update the values in current iteration. Estimation of CTG is rougher than SBPI in early iteration but still leads to good enough policy and spends less simulation time. And policy accuracy will approach or reach optimal policy with iteration. In the numerical study that compares SBPI with SBVI by a medium dimension problem, simulation time can be saved around two orders in SBVI than SBPI to get the same level policy accuracy. However, simulation time of SBVI in high range of PA rapidly grows with PA and problem dimensions.
We further exploit the property that ranking of optimal policy has formed, although estimation accuracy is rough in advance. We propose Ordinal Optimization-Based Value Iteration (OOBVI) by using the concept of OO. OOBVI adopts ranking accuracy (APCS) instead of estimation accuracy as stopping criterion to stop simulation of policy evaluation. APCS can modulate simulation replications with iteration to save simulation time at the same desirable policy accuracy.
According to simulation result of a medium dimension problem, OOBVI can save four times simulation time compared with SBVI to reach the same PA in SBVI. And from observation of further simulation, growth of simulation time in OOBVI is approximated by linear but exponential in SBVI to get the same desirable PA. We anticipate that OOBVI is more efficient than SBVI in large dimension problems.
OOBVI uses the same ranking accuracy for all states in policy evaluation step, but we consider that it is unnecessary. The innovative idea is variable stopping criterion for states. Combination of computing budget allocation over states (CBA-S) and OOBVI can be expected to get high PA for high stopping criterion but simulation time decreases obviously. By a medium dimension problem, OOBVI with CBA-S can get almost the same PA for high stopping criterion but simulation time saves tenfold.
Summary of contribution and value of our research is improvement of SBPI which is typical solution to solve StMDP that needs simulation. From our finite simulation experiment, we expect that OOBVI with CBA-S is most potential algorithm to get the same PA but less simulation time.
Subjects
演算法
馬可夫決策
排序佳化
MDP
markov decision proess
ordinal optimazation
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-94-R92921007-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):ca270bbc47e28ba034ae396f694e0ef5