F -Discrepancy for Efficient Sampling in Approximate Dynamic Programming.

Area of Science:

• Operations Research
• Artificial Intelligence
• Computational Mathematics

Background:

• Approximate dynamic programming (ADP) relies on accurate value function approximation.
• Efficient selection of state sample points is crucial for ADP performance in continuous-state Markovian decision problems.
• Standard uniform sampling may be inefficient for non-uniformly distributed state trajectories.

Purpose of the Study:

• To develop a novel algorithm for selecting efficient state sample points in continuous-state finite-horizon Markovian decision problems.
• To leverage F-discrepancy for optimizing sample point selection in ADP.
• To demonstrate improved convergence and accuracy compared to traditional methods.

Main Methods:

• Exploitation of F-discrepancy to measure the representativeness of sample points to a probability distribution.
• Development of an algorithm to automatically select point sets optimized for Markovian processes.
• Error analysis to prove convergence properties under regularity conditions.

Main Results:

• The proposed algorithm demonstrates efficient sample point selection for ADP.
• Error analysis confirms convergence of the approximate solution.
• Simulation results on an inventory forecasting problem show superior performance over uniform sampling.
• The algorithm achieved better results using sample sets up to 50 times smaller than uniform sampling.

Conclusions:

• F-discrepancy is a valuable tool for enhancing state sample point selection in ADP.
• The proposed algorithm offers a more efficient and accurate approach to solving Markovian decision problems.
• This method has practical implications for optimizing complex decision-making processes.