Труды КНЦ вып. 11 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ) вып. 8/2020 (11)

DOI: 10.37614/2307-5252.2020.8.11.025 УДК 519.856 А.В. Назин Москва, ИПУ РАН ПОИСК СЕДЛОВОЙ ТОЧКИ ВЫПУКЛО-ВОГНУТОЙ СТОХАСТИЧЕСКОЙ ИГРЫ АДАПТИВНЫМ МЕТОДОМ ЗЕРКАЛЬНОГО СПУСКА* Аннотация Рассматривается стохастическая игровая задача 2-х лиц с нулевой суммой, приводящая к поиску седловой точки функции игры на основе градиентного подхода. Исследуются алгоритмы зеркального спуска, как адаптивные, так и не адаптивные. Доказываются основные результаты. Обсуждается иллюстративный пример. Ключевые слова: стохастическая игровая задача, поиск седловой точки, градиентный подход, метод зеркального спуска, рекуррентные адаптивные алгоритмы. A.V. Nazin Moscow, Institute o f Control Sciences, RAS SEARCH FOR A SADDLE POINT OF A CONVEX-CONCAVE STOCHASTIC GAME BY THE ADAPTIVE METHOD OF MIRROR DESCENT Abstract A stochastic game problem of 2 persons with a zero sum is considered, leading to the search for a saddle point of the game function based on the gradient approach. We study mirror descent algorithms, both adaptive and non-adaptive. The main results are proved. An illustrative example is discussed. Keywords: stochastic game problem; saddle point search; gradient approach; mirror descent method; recursive adaptive algorithms. Игровая задача 2-х лиц с нулевой суммой, как известно, приводит к поиску седловой точки выпукло-вогнутой функции [1, 2]. Она возникает в различных задачах оптимизации и управления, как в теоретическом, так и практическом аспектах [2, 3]. Будем далее говорить об итеративных методах поиска седловой точки при наличии оракула 1-го порядка, то есть использовании стохастических субградиентов функции игры q(x, y), где x G Х и у б Y - управляющие переменные 1-го и 2-го игроков из выпуклых компактов X ^ R , Y ^ R . Тогда 3 седловая точка v J G X x Y , т. е. q ( x *, у ) < q(x*, V*) < q (X у * V ( x, y ) G X x Y . (1) (X* V*) Введем ошибку аппроксимации для точки точкой-кандидатом G X x Y : *Работа поддержанаРоссийскимфондомфундаментальныхисследований, грант 18-08-00140. 182