Методы оптимизации и теория управления

Научная статья

Гауссовская аппроксимация для линейной стохастической аппроксимации с приложением к обучению с подкреплением

Даниль Эльдарович Гайнанов¹, Илья Валерьевич Левин²

1,2	Высшая школа экономики, Москва, Россия
2	ivlevin@hse.ru

Аннотация. Рассматривается задача статистического вывода для решения системы линейных уравнений $\overline{\mathbf{A}}$ ${\theta }^{\star }$ = $\overline{\mathbf{b}}$, в которой матрица $\mathbf{A}$ и вектор $\mathbf{b}$ неизвестны, а вместо них доступны зашумлённые наблюдения. Исследуется метод линейной стохастической аппроксимации с постоянным шагом и марковским шумом. Усреднение Поляка–Рупперта (PR) снижает дисперсию, но сохраняет стационарное смещение порядка $\alpha$, ухудшающее нормальную аппроксимацию. Для устранения ведущего смещения используется экстраполяция Ричардсона–Ромберга: средние двух рекурсий с шагами $\alpha$ и $2\alpha$, использующих одну и ту же траекторию марковской цепи, объединяются в одну оценку. Показано, что такая коррекция улучшает нормальную аппроксимацию без изменения предельной дисперсии.
Получена неасимптотическая оценка в расстоянии Колмогорова для скалярных проекций PR-усреднений с экстраполяцией Ричардсона–Ромберга. Для траектории длины $n$ при выборе шага порядка $n^{-1/2}$ полученная верхняя граница убывает как $n^{-1/4}$ с точностью до логарифмических множителей. В качестве приложения исследуемой теории рассматривается построение доверительных интервалов для параметров, оцениваемых алгоритмом TD(0) в обучении с подкреплением. Численные эксперименты на синтетических данных подтверждают коррекцию среднего и улучшение покрытия доверительных интервалов без заметного увеличения их ширины.

Ключевые слова: линейная стохастическая аппроксимация, гауссовская аппроксимация, экстраполяция Ричардсона–Ромберга, доверительные интервалы, обучение с подкреплением

Для цитирования: Гайнанов Д. Э., Левин И. В. Гауссовская аппроксимация для линейной стохастической аппроксимации с приложением к обучению с подкреплением // Программные системы: теория и приложения. 2026. Т. 17. № 4. С. 33–56. https://psta.psiras.ru/2026/4_33-56.

Полный текст статьи (PDF): https://psta.psiras.ru/read/psta2026_4_33-56.pdf.

Статья поступила в редакцию 18.08.2026; одобрена после рецензирования 15.09.2026; принята к публикации 21.09.2026; опубликована онлайн 13.10.2026.