Анализ и улучшение вычислительной сложности алгоритмов динамического программирования

Задача оптимальной остановки широко известна в экономике и статистике. Эти задачи связаны с процессами принятия решений, где лицо, принимающее решение, должно понять, предпринимать конкретное действие или отложить его на будущее. Естественные приложения для теории оптимальной остановки возникают в финансовой математике, например, оценка опционов является частным случаем задачи оптимальной остановки. Основные проблемы в приближённых методах для решения подобных задач —— проклятие размерности и масштабируемость по времени, то есть возоможность аппроксимировать решение задачи не только в дискретном, но и в непрерывном времени. В этой статье мы хотим представить метод Weighted Grid Monte Carlo и его новый теоретический анализ. Нами показано, что WGMC лучше справляется с аппроксимацией непрерывных задач, чем регрессионный метод, предложенный Tsitsiklis&Van Roy, Longstaff&Schwartz. WGMC основан на идеях stochastic mesh метода Broadie&Glasserman, но позволяет также использовать приближённую переходную плотность, тогда как для оригинального метода она должна быть известна. Мы показываем, что WGMC более устойчив, чем регрессионный метод, когда дискретизация по времени становится более плотной. Этот эффект очень ясно отражён в проведённых численных экспериментах.