Monte Carlo tree search for generating vectors of lattice rules

Abstract

Lattice rules are widely studied in the context of quasi-Monte Carlo methods as a means to achieve a small integration error. The rules themselves are determined completely by so called generating vectors, so there is an interest in methods for constructing vectors that perform well. This article introduces a new component-wise construction of a generating vector using the principles of Monte Carlo tree search, with the goal of avoiding local optima. Error bounds are proven for the vectors obtained from this method, which are analogous to existing results for the popular component by component construction.

References

• J. Dick. On the convergence rate of the component-by-component construction of good lattice rules. J. Complex. 20 (2004), pp. 493–522. doi: 10.1016/j.jco.2003.11.008
• J. Dick, F. Y. Kuo, and I. H. Sloan. High-dimensional integration: The quasi-Monte Carlo way. Acta Numer. 22 (2013), pp. 133–288. doi: 10.1017/S0962492913000044
• M. Giles, F. Y. Kuo, I. H. Sloan, and B. J. Waterhouse. Quasi-Monte Carlo for finance applications. ANZIAM J. 50 (2008), pp. C308–C323. doi: 10.21914/anziamj.v50i0.1440
• N. M. Korobov. Approximate evaluation of repeated integrals. Doklady Akademii Nauk SSSR 124 (1959), pp. 1207–1210
• F. Y. Kuo. Component-by-component constructions achieve the optimal rate of convergence for multivariate integration in weighted Korobov and Sobolev spaces. J. Complex. 19 (2003), pp. 301–320. doi: 10.1016/S0885-064X(03)00006-2
• D. Nuyens and R. Cools. Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces. Math. Comput. 75 (2006), pp. 903–920. doi: 10.1090/S0025-5718-06-01785-6
• I. H. Sloan and A. V. Restzov. Component-by-component construction of good lattice rules. Math. Comput. 71 (2002), pp. 263–273. doi: 10.1090/S0025-5718-01-01342-4
• I. H. Sloan and H. Woźniakowski. When are quasi-Monte Carlo algorithms efficient for high-dimensional integrals? J. Complex. 14 (1998), pp. 1–33. doi: 10.1006/jcom.1997.0463
• X. Wang and I. H. Sloan. Efficient weighted lattice rules with applications to finance. SIAM J. Sci. Comput. 28 (2006), pp. 728–750. doi: 10.1137/S1064827502418197