Kybernetika 49 no. 5, 720-737, 2013

Approximate dynamic programming based on high dimensional model representation

Miroslav Pištěk

Abstract:

This article introduces an algorithm for implicit High Dimensional Model Representation (HDMR) of the Bellman equation. This approximation technique reduces memory demands of the algorithm considerably. Moreover, we show that HDMR enables fast approximate minimization which is essential for evaluation of the Bellman function. In each time step, the problem of parametrized HDMR minimization is relaxed into trust region problems, all sharing the same matrix. Finding its eigenvalue decomposition, we effectively achieve estimates of all minima. Their full-domain representation is avoided by HDMR and then the same approach is used recursively in the next time step. An illustrative example of N-armed bandit problem is included. We assume that the newly established connection between approximate HDMR minimization and the trust region problem can be beneficial also to many other applications.

Keywords:

approximate dynamic programming, Bellman equation, approximate HDMR minimization, trust region problem

Classification:

90C39

paper.pdf

References:

  1. S. Busygin: A new trust region technique for the maximum weight clique problem. Discrete Appl. Math. 154 (2002), 2006.   CrossRef
  2. M. Demiralp: High dimensional model representation and its application varieties. In: Proc. Fourth International Conference on Tools for Mathematical Modelling, St. Petersburg 2003, pp. 146-159.   CrossRef
  3. K. S. Feil and N. Shah: Volatility calibration using spline and high dimensional model representation models. Wilmott J. 1 (2009), 179-195.   CrossRef
  4. A. Garivier and O. Capp{é}: The {KL}-{UCB} algorithm for bounded stochastic bandits and beyond. In: Proc. 24th Annual Conference on Learning Theory, Budapest 2011.   CrossRef
  5. A. George, W. B. Powell and S. R. Kulkarni: Value function approximation using multiple aggregation for multiattribute resource management. J. Machine Learning Res. 9 (2008), 2079-2111.   CrossRef
  6. J. Gittins: Bandit processes and dynamic allocation indices. J. Roy. Statist. Soc. Ser.B 41 (1979), 2, 148-177.   CrossRef
  7. A. Gosavi: Reinforcement learning: A tutorial survey and recent advances. INFORMS J. Comput. 21 (2009), 178-192.   CrossRef
  8. M. Hauskrecht: Value-function approximations for partially observable markov decision processes. J. Artif. Internat. Res. 13 (2000), 33-94.   CrossRef
  9. T. Jaakkola, S. P. Singh and M. I. Jordan: Reinforcement Learning Algorithm for Partially Observable Markov Decision Problems. MIT Press, 1995.   CrossRef
  10. R. M. Karp: Reducibility among combinatorial problems. In: Complexity of Computer Computations (R. Miller and J. W. Thatcher, eds.), Plenum, New York 1972.   CrossRef
  11. H. Kushner: Introduction to Stochastic Control. Holt, Rinehart and Winston, New York 1970.   CrossRef
  12. M. LeBlanc and R. Tibshirani: Combining estimates in regression and classification. J. Amer. Statist. Assoc. 91 (1996), 1641-1650.   CrossRef
  13. G. Li, J. Hu, S.-W. Wang, P. G. Georgopoulos, J. Schoendorf and H. Rabitz: Random sampling-high dimensional model representation (rs-hdmr) and orthogonality of its different order component functions. J. Phys. Chem. A 110 (2006), 7, 2474-2485.   CrossRef
  14. R. Luus: Iterative Dynamic Programming. Chapman and Hall/CRC Monographs and Surveys in Pure and Applied Mathematics, 2000.   CrossRef
  15. X. Ma and N. Zabaras: An adaptive high-dimensional stochastic model representation technique for the solution of stochastic partial differential equations. J. Comput. Phys. 229 (2010), 3884-3915.   CrossRef
  16. J. Matou{š}ek and J. Ne{š}et{ř}il: Invitation to Discrete Mathematics. Clarendon Press, 1998.   CrossRef
  17. W. Miller, R. Sutton and P. Werbos: Neural Networks for Control. Neural Network Modeling and Connectionism. Mit Press, 1995.   CrossRef
  18. C. Olsson, A. Eriksson and F. Kahl: Solving large scale binary quadratic problems: Spectral methods vs. semidefinite programming. In: Computer Vision and Pattern Recognition, 2007.   CrossRef
  19. V. Peterka: Bayesian system identification. In: Trends and Progress in System Identification (P. Eykhoff, ed.), Pergamon Press, Oxford 1981, pp. 239-304.   CrossRef
  20. M. Pištěk: On implicit approximation of the bellman equation. In: 15th IFAC Symposium on System Identification, Saint-Malo 2009.   CrossRef
  21. W. B. Powell: Approximate Dynamic Programming: Solving the Curses of Dimensionality. Wiley-Interscience, 2007.   CrossRef
  22. H. Rabitz and O. Alis: General foundations of high-dimensional model representations. J. Math. Chem. 25 (1999), 197-233.   CrossRef
  23. S. Rahman: A polynomial dimensional decomposition for stochastic computing. Internat. J. Numer. Methods in Engrg. 76 (2008), 2091-2116.   CrossRef
  24. M. Rojas, S. A. Santos and D. C. Sorensen: A new matrix-free algorithm for the large-scale trust-region subproblem. SIAM J. Optim. 11 (2000), 611-646.   CrossRef
  25. A. Schrijver: Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley and Sons, 1998.   CrossRef
  26. D. C. Sorensen: Newton's method with a model trust region modification. SIAM J. Numer. Anal. 19 (1982), 2, 409-426.   CrossRef
  27. R. S. Sutton and A. G. Barto: Reinforcement Learning: An Introduction. MIT Press, 1998.   CrossRef